- •Предназначено студентам очной формы обучения.
- •Введение
- •1. Оценки сложности алгоритмов
- •1.1. Определение понятия алгоритм
- •1.2. Оценка сложности алгоритмов
- •2. Линейные структуры данных
- •2.1. Методы организации и хранения линейных списков
- •2.2. Операции со списками при последовательном хранении
- •2.3. Операции со списками при связном хранении
- •2.4. Организация двусвязных списков
- •Задания для самоконтроля
- •2.5. Стеки и очереди
- •2.6. Сжатое и индексное хранение линейных списков
- •3. Сортировка и слияние
- •3.1. Пузырьковая сортировка
- •3.2. Сортировка вставкой
- •3.3. Сортировка посредством выбора
- •3.4. Сортировка квадратичной выборкой
- •3.5. Слияние списков
- •3.6. Сортировка списков путем слияния
- •3.7. Быстрая и распределяющая сортировки
- •4. Поиск
- •4.1. Последовательный поиск
- •4.2. Бинарный поиск
- •4.4. Методы вычисления адреса
- •4.5. Выбор в линейных списках
- •5. Рекурсия
- •6. Алгоритмы на графах и сетях
- •6.1. Исходные понятия
- •6.2. Матричные представления графов
- •6.3. Другие представления графов
- •6.4. Поиск в глубину как система исследования графа
- •6.5. Перебор цепей поиском в глубину
- •6.6. Взвешенные графы. Ориентированные графы
- •6.7. Нахождение фундаментального множества циклов
- •6.8. Выявление мостов и точек сочленений
- •6.9. Поиск в ширину как система исследования графа
- •6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим
- •6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе
- •6.12. Улучшения алгоритма Дейкстры
- •6.13. Построение кратчайшего каркаса
- •6.14. Нахождение всевозможных кратчайших путей в графе
- •6.15. Потоковые задачи
- •6.16. Пример практической задачи на графах
- •7. Генераторы случайных и псевдослучайных последовательностей
- •7.1. Общая постановка задачи
- •7.3. Генератор случайных чисел, поставляемый с системой
- •7.4. Генератор с малым кодом
- •7.5. Генератор Парка-Миллера
- •7.6. Улучшенная версия генератора Парка-Миллера
- •7.7. Быстрый генератор для 32-битового представления целых и действительных чисел
- •7.8. Алгоритм л'Экюера, комбинирующий две последовательности
- •Оглавление
- •7. Генераторы случайных и псевдослучайных последовательностей 144
- •394026 Воронеж, Московский просп., 14
2. Линейные структуры данных
2.1. Методы организации и хранения линейных списков
Линейный список– это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться.
Линейный список F, состоящий из элементов D1, D2, ..., Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически (рис. 1).
Рис. 1. Изображение линейного списка
Например, F1=< 2,3,1>, F2=< 7,7,7,2,1,12 >, F3=<>. Длина списков F1, F2, F3 равна соответственно 3,6,0.
При работе со списками на практике чаще всего приходится выполнять следующие операции:
- найти элемент с заданным свойством;
- определить первый элемент в линейном списке;
- вставить дополнительный элемент до или после указанного узла;
- исключить определенный элемент из списка;
- упорядочить узлы линейного списка в определенном порядке.
В реальных языках программирования нет какой-либо структуры данных для представления линейного списка так, чтобы все указанные операции над ним выполнялись в одинаковой степени эффективно. Поэтому при работе с линейными списками важным является представление используемых в программе линейных списков таким образом, чтобы была обеспечена максимальная эффективность и по времени выполнения программы, и по объему требуемой памяти.
Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. Рассмотрим простейшие варианты этих методов для списка с целыми значениями F=<7,10>.
При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида
floatd[100]; intl;
Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:
d[0]=7; d[1]=10; l=2;
Полученный список хранится в памяти согласно схеме на рис.2.
Рис. 2. Последовательное хранение линейного списка
При связанном хранении в качестве элементов хранения используются структуры, связанные по одной из компонент в цепочку, на начало которой (первую структуру) указывает указатель dl. Структура образующая элемент хранения, должна кроме соответствующего элемента списка содержать и указатель на соседний элемент хранения.
Описание структуры и указателя в этом случае может иметь вид:
typedef struct snd { /* структура элемента хранения */
float val; /* элемент списка */
struct snd *n ; /* указатель на элемент хранения */
}
DL;
DL *p; /* указатель текущего элемента */
DL *dl; /* указатель на начало списка */
Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:
p=malloc(sizeof(DL));
p->val=10;
p->n=NULL;
dl=malloc(sizeof(DL));
dl->val=7;
dl->n=p;
В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рис.3.
Рис. 3. Связное хранение линейного списка