Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

Линейный список F, состоящий из элементов D1, D2,..., Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически.

Например, F1=< 2, 3, 1>, F2=< 7, 7, 7, 2, 1, 12>, F3=< >. Длина списков F1, F2, F3 равна соответственно 3, 6, 0.

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

- найти элемент с заданным свойством;

- определить первый элемент в линейном списке;

- вставить дополнительный элемент до или после указанного узла;

- исключить определенный элемент из списка;

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

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

Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. Рассмотрим простейшие варианты этих методов для списка с целыми значениями F=< 7, 10>.

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

float d[100]; int l;

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

d[0]=7; d[1]=10; l=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. Получаемый список изображен на рис.1.


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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.