Студопедия

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

КАТЕГОРИИ:

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






Формирование односвязного списка




Как правило, элементы связанного списка являются структурами, так как, помимо данных, они содержат ссылку на следующий элемент. Поэтому необходимо определить структуру:

struct List

{

int info;//информационная часть

struct List *next;//указатель на следующий элемент списка

};

В приведенном примере информационная часть представляет собой одну целочисленную переменную (info), которая имеет тип int. Списки с элементами других типов описываются аналогично.

Пример. Список символов (‘a’,’b’,’c’), состоит из трех элементов. Первый элемент в этом списке – ‘a’, второй – ‘b’, третий – ‘c’. Представление этого списка стеком изображается на рис. 1, очередью – на рис. 2.

Рис.1 – Стек из трех элементов

Рис. 2 – Очередь из трех элементов

 

При этом в программе выражение pbeg означает указатель на первое звено в цепочке; *pbeg означает само первое звено, (*pbeg).info — первый элемент списка. По-другому первыйэлемент обозначается с помощью операции доступа к члену структуры через указатель: pbeg−>info. Выражение pbeg−>next означает указатель на второе звено. Далее,

*pbeg−>next — само второе звено,

pbeg−>next−>info — второй элемент списка,

pbeg−>next−>next — указатель на третье звено,

*pbeg–>next−>next — само третье звено,

pbeg−>next−>next−>info — третий элемент списка,

pbeg−>next−>next−>next — пустой указатель (конец списка).

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

 


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал