Вопросы для повторения
Понятие абстрактного типа данных.
Понятие O-символики.
АТД список, операторы списка.
Реализация списков посредством массивов.
Реализация списков с помощью указателей.
Реализация списков с помощью курсоров.
АТД стек, операторы стека.
Реализация стеков.
АТД очередь, операторы очереди.
Реализация очередей.
Понятие графа (неориентированного графа).
Понятие вершины графа.
Понятие ребра графа.
Понятие ориентированного графа.
Понятие дуги орграфа.
Понятие смежности.
Понятие концевой вершины.
Понятие инцидентности.
Понятие петли.
Понятие кратных ребер.
Понятие параллельных дуг.
Понятие цепи.
Понятие пути.
Понятие маршрута.
Понятие цикла.
Понятие контура.
Понятие связного графа.
Понятие ациклического графа.
Понятие дерева.
Понятие леса.
Понятие подграфа.
Понятие покрывающего (или остовного) дерева.
Понятие матрицы смежности.
Понятие матрицы инцидентности.
Хранение взвешенных графов с помощью матриц весов.
Упаковка матриц.
Хранение графов с помощью массивов ребер.
Хранение графов с помощью списков смежности.
Хранение графов с помощью списков ребер.
Хранение деревьев.
Резюме по теме
В данной теме рассмотрены различные методы организации данных в памяти ЭВМ.
Тема 7. Некоторые алгоритмы обработки данных
Цели и задачи изучения темы
В данной теме рассматриваются некоторые из алгоритмов, которые наиболее часто используются в экономических информационных системах. Также выбор алгоритмов обусловлен их достаточной простотой. Все из рассмотренных алгоритмов могут быть реализованы студентами самостоятельно.
7.1.Алгоритмы поиска
Задача поиска встречается очень часто. В общем случае под задачей поиска понимается задача нахождения среди исходных данных нужных данных, т.е. данных удовлетворяющих условиям поиска. Например, задан список абонентов АТС, необходимо найти номер телефона абонента по его фамилии. Алгоритмы поиска зависят от организации исходных данных.
В данном разделе более подробно рассматривается поиск в неупорядоченном и упорядоченном массиве. Задача поиска элемента в массиве заключается в том, чтобы определить наличие в данном массиве элемента, равного заданному элементу. Если такой элемент есть, то выдается его номер, в противном случае выдается номер элемента, следующего за последним элементом массива.
Также в данном разделе рассматривается так называемый фонетический поиск. Задача фонетического поиска - найти нужные данные сопоставленные фамилии человека, если фамилия была воспринята на слух и может содержать ошибки. Подобные методы находят применение в системах, где оператор воспринимает фамилию заказчика на слух и выполняет некоторые действия, например, в системах заказа билетов, бронирования мест в гостиницах, различных справочных системах и т.д.
7.1.1.Поиск элемента в неупорядоченном массиве
Работа алгоритма поиска элемента в неупорядоченном массиве заключается в том, что элементы массива, начиная с первого, последовательно сравнивается с искомым элементом. Сравнение элементов продолжается до тех пор, пока не будут просмотрены все элементы или очередной элемент массива не равен искомому. Такой поиск называется линейным поиском.
Один из вариантов реализации процедуры поиска элемента в неупорядоченном массиве был рассмотрен при реализации АТД список на массиве при реализации оператора LOCATE (см. рис. 6.4). Данная реализация алгоритма поиска содержит проверку на окончание массива и проверку на равенство текущего элемента массива с искомым. Обе проверки осуществляется для каждого очередного элемента массива. Поэтому в том случае, когда искомого элемента в массиве нет, будет произведено 2n проверок, где n число элементов массива. Однако число проверок можно уменьшить, если в конец массива включить (n+1)-й элемент, равный искомому. Тогда проверка на окончание массива становится лишней. Остается лишь проверка на совпадение очередного элемента с искомым. Если этот элемент находится внутри массива, то поиск заканчивается удачно и элемент считается найденным. Если же этот элемент оказался (n+1)-ым, то искомого элемента в массиве нет. Подобный прием позволяет упростить условия выхода из цикла и используется в программировании довольно часто. Применив этот прием, получим модифицированный алгоритм оператора LOCATE. Данный алгоритм представлен блок-схемой на рис. 7.1.
