Файл: Динамические структуры данных. Списки (Структура программы и языка программирования).pdf

При работе со списками на практике чаще всего приходится выполнять следующие операции:

• найти элемент с заданным свойством;
• определить первый элемент в линейном списке;
• вставить дополнительный элемент до или после указанного узла;
• исключить определенный элемент из списка;
• упорядочить узлы линейного списка в определенном порядке.

Для работы со списком в программе требуется определить указатель на его начало. Чтобы упростить добавление новых элементов в конец списка, можно также завести указатель на конец списка.

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

Методы хранения линейных списков разделяются на методы последовательного и связанного хранения.

При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида

float d[100]; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d[0]=7; d[1]=10; l=2;

Полученный список хранится в памяти согласно схеме:

Рисунок 2. Последовательное хранение линейного списка

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

Описание структуры и указателя в этом случае может имееть вид:

Рисунок 3. Код описания структуры и указателя

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:

Рисунок 4. Применение функции malloc для выделения памяти

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рисунке:

Рисунок 5. Связное хранение линейного списка

При выборе метода хранения линейного списка следует учитывать, какие операции будут выполняться и с какой частотой, время их выполнения и объем памяти, требуемый для хранения списка.

Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка).

В программе двусвязный список можно реализовать с помощью описаний:

Рисунок 6. Описание двусвязного списка

Графическая интерпретация метода связанного хранения списка F=< 2,5,7,1 > как списка с двумя связями приведена на рисунке:

Рисунок 7. Список с двумя связями

Вставка нового узла со значением new за элементом, определяемым указателем p, осуществляется при помощи операторов:

Рисунок 8. Вставка нового узла

Удаление элемента, следующего за узлом, на который указывает p

Рисунок 9. Удаление элемента

Связанное хранение линейного списка называется циклическим списком, если его последний указывает на первый элемент, а указатель dl- на последний элемент списка.

Схема циклического хранение списка F=< 2,5,7,1 > приведена на рисунке ниже [4]:

Рисунок 10. Схема циклического хранения списка

ЗАКЛЮЧЕНИЕ

Рассмотренная тема наглядно показывает насколько широк выбор инструментов для программирования. Алгоритмизация процесса позволяет четко спланировать сценарий дальнейшей техники написания кода, что приведет в конечном итоге с ожидаемому результату, а соблюдение правил оформления программного кода облегчит процесс отладки приложения. Прогресс не стоит на месте – в руках ИТ-специалистов появляется все больше инструментов для автоматизации тех или иных процессов. Главная задача – научиться правильно и рационально ими распорядится, чтобы на свет появилось очередное необходимое обществу приложение или программа, не только выполняющее свою функцию, но и отличающееся высоким быстродействием. А это, в свою очередь, возможно только при грамотном использовании оперативной памяти. Ведь всем знакома ситуация, когда в критический момент нужная именно в этот момент программа начинает «подвисать», что ведет к сбою в работе нервной системы пользователя.