- •1. Этапы решения задач на эвм
- •2. Понятие алгоритма и структуры данных
- •5. Классификация структур данных
- •6. Основы организации данных на физическом уровне
- •7. Классификация базовых типов и структур данных
- •8. Встроенные типы данных
- •9. Уточняемые типы данных
- •10. Перечисляемые типы данных
- •11. Конструируемые типы данных (сразу и ответы на 12: Массивы, на 14: Записи, 15: Множества)
- •11.1. Массивы
- •11.2. Записи
- •11.3. Записи с вариантами
- •11.4. Множества
- •13. Строки
- •16. Указатели
- •17. Задачи и многообразие алгоритмов их решения
- •17.1 Правила построения алгоритма задачи.
- •17.2 Нисходящее пошаговое проектирование
- •2.2 Структурное программирование
- •Односвязный линейный список
- •Циклические списки
- •38. Двусвязный линейный список
- •39 Стеки
- •40 Очереди
- •43 Универсальные функции расстановки
- •44 Методы разрешения коллизий
2. Понятие алгоритма и структуры данных
Как было указано в предыдущем параграфе, в процессе преобразования информации от постановки задачи до получения компьютерной программы выделяются два взаимосвязанных объекта – данные и алгоритм их преобразования. Уточним эти понятия.
Алгоритм – это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых и точно определенных элементарных операций для решения задачи, общее для класса возможных исходных данных.
К алгоритму предъявляется следующий ряд общих требований:
алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т.е. удовлетворять требованию конечности записи;
алгоритм должен выполнять конечное количество шагов при решении задачи, т. е. удовлетворять требованию конечности действий;
алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;
алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности.
3,4. Согласно приведенному определению, алгоритм это описание на некотором языке. В практике программирования наибольшее распространение получили следующие языки описания алгоритмов: словесно-формульный язык описания, графические языки (например, языки блок-схем, Р-схем, структурограммы), псевдокоды и языки программирования. Выбор способа записи алгоритма зависит от цели его описания. На указанных языках алгоритмы могут быть описаны с разной степенью детализации и формализации.
Наиболее наглядной и допускающей любой уровень абстракции является графическая форма записи алгоритма. Она позволяет отчетливо представить все логические связи между частями алгоритма. Среди графических языков наиболее популярным является язык блок-схем алгоритмов и программ.
Блок-схема алгоритма представляет собой набор геометрических фигур (блоков), соединенных линиями или линиями со стрелками для указания направления перехода от блока к блоку. Движение от блока к блоку сверху вниз или слева направо считается стандартным. В этом случае стрелки можно не указывать. Если же направление отлично от стандартного, то стрелки обязательны.
Необходимая для выполнения очередного действия информация помещается в блок в виде текста или математических обозначений. Перечень блоков, их форма и отображаемые функции установлены ГОСТ 19.701-90 ЕСПД. В таблице 1.1 приведены графические обозначения основных блоков.
Описание данных в процессе создания программы выполняется в терминах так называемых структур данных.
Данные – это значения или наборы значений, описывающие любую информацию, которую можно обработать на компьютере. В зависимости от назначения программы, данные могут иметь разный уровень сложности или организованности, начиная от самых простых (числа или символы) и заканчивая достаточно сложными образованиями, включающими как сами элементы данных, так и информацию об их количестве и взаимосвязях между этими элементами. Модель организованности данных принято называть структурой данных.