Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Однонаправленные (односвязные) списки
|
|
Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа.
Однонаправленный (односвязный) список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка. В последнем элементе указатель на следующий элемент равен NULL.
|
|
|
|
|
|
|
|
Линейный однонаправленный список
Описание простейшего элемента такого списка выглядит следующим образом:
struct имя_типа { информационное поле; адресное поле; };
где информационное поле – это поле любого, ранее объявленного или стандартного, типа;
адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка.
Например:
struct Node { int key; //информационное поле Node*next; //адресное поле };Информационных полей может быть несколько.
Например:
struct point { char*name; //информационное поле int age; //информационное поле point*next; //адресное поле };Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.
Основными операциями, осуществляемыми с однонаправленными списками, являются:
· создание списка;
· печать (просмотр) списка;
· вставка элемента в список;
· удаление элемента из списка;
· поиск элемента в списке
· проверка пустоты списка;
· удаление списка.
Особое внимание следует обратить на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.
Для описания алгоритмов этих основных операций используется следующее объявление:
struct Single_List {//структура данных int Data; //информационное поле Single_List *Next; //адресное поле };.......... Single_List *Head; //указатель на первый элемент списка.......... Single_List *Current; //указатель на текущий элемент списка (при необходимости)