Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Понятие структур данных и алгоритмов




Структуры данных и алгоритмы являются строительным материалом программного обеспечения. В основе работы вычислительной машины лежит возможность оперировать только с одним видом данных – отдельными битами. Встроенные структуры данных представлены регистрами и словами памяти, в которых хранятся двоичные величины. Однако подлежащие решению задачи редко выражаются на языке битов.

Как правило, данные имеют форму чисел, литер, текстов, символов и более сложных структур – последовательностей, списков, деревьев. Еще разнообразнее алгоритмы, применяемые для решения вычислительных задач; фактически алгоритмов не меньше чем вычислительных задач. Для точного описания абстрактных структур данных и алгоритмов программ используются такие системы формальных обозначений, в которых смысл всякого предложения определяется точно и однозначно.

Среди средств, представляемых языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именем, или, иначе, идентификатором. Одни именованные величины являются константами, которые сохраняют постоянное значение, другие – переменными, которым с помощью оператора может быть присвоено любое новое значение.

Компилятор, транслирующий исходный текст программы в двоичный код, связывает каждый идентификатор с определенным адресом памяти. Чтобы компилятор смог это выполнить, следует сообщить ему о «типе» каждой именованной величины. Человек, решающий задачу «вручную», обладает интуитивной способностью разбираться в типах данных и операциях, которые для каждого типа справедливы. Например, нельзя извлечь квадратный корень из слова или написать число с заглавной буквы.

Одна из причин, позволяющая легко провести такое распознавание, состоит в том, что слова, числа и другие обозначения отображаются по-разному. В машинном представлении все типы данных сводятся к последовательности битов, поэтому различие в типах следует делать явным. Типы данных, принятые в языках программирования, включают натуральные и целые числа, вещественные (действительные) числа (в виде приближенных десятичных дробей), литеры, строки.

В некоторых языках тип каждой константы или переменной определяется компилятором по записи присваиваемого значения; например, наличие десятичной точки может служить признаком вещественного числа. В других языках требуется явное задание типа каждой переменной. Значение переменной может многократно меняться, однако ее тип меняться не должен никогда; это значит, что компилятор может проверить операции, выполняемые над этой переменной, и убедиться в том, что все они согласуются с описанием типа переменной. Такая проверка может быть проведена путем анализа всего текста программы, и в этом случае она охватит все возможные действия, определяемые данной программой.

В зависимости от назначения языка защита типов, осуществляемая на этапе компиляции, может быть более или менее жесткой. Например, язык PASCAL, изначально являющийся, прежде всего, инструментом для иллюстрирования структур данных и алгоритмов, сохраняет от своего первоначального назначения строгую защиту типов. PASCAL-компилятор в большинстве случаев расценивает смешение в одном выражении данных разных типов или применение к типу данных несвойственных ему операций как фатальную ошибку.

Напротив, язык C, предназначенный, прежде всего, для системного программирования, обладает весьма слабой защитой типов. C-компиляторы в таких случаях лишь выдадут предупреждения. Отсутствие жесткой защиты типов дает дополнительные возможности, но за правильностью действий приходится следить самостоятельно.

Структура данных относится, по существу, к «пространственным» понятиям: ее можно свести к схеме организации информации в памяти машины, в то время как алгоритмы является соответствующим процедурным элементом в структуре программы.

Первые алгоритмы были разработаны для решения численных задач, однако в настоящее время в равной степени важны численные и нечисловые алгоритмы: например, поиск в тексте заданного слова, планирование событий, сортировка данных в указанном порядке и т.п. Нечисловые алгоритмы оперируют с данными, которые не обязательно являются числами; более того, не нужны глубокие математические понятия, чтобы их конструировать или понимать. Из этого, однако, не следует, что в изучении таких алгоритмов математике нет места; напротив, точные, математические методы необходимы при поиске наилучших решений нечисловых задач при доказательстве правильности этих решений.

Структуры данных, применяемые в алгоритмах, могут быть чрезвычайно сложными. В результате выбор правильного представления данных часто служит ключом к удачной реализации и может в большей степени сказываться на эффективности решений, чем детали используемого алгоритма. В пособии представлены базовые элементы данных и примеры собранных из них информационных структур.




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 253; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.