Студопедия

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

КАТЕГОРИИ:

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






Однонаправленные (односвязные) списки






Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа.

Однонаправленный (односвязный) список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка (рис. 29.1). В последнем элементе указатель на следующий элемент равен NULL.


Рис. 29.1. Линейный однонаправленный список

 

Описание простейшего элемента такого списка выглядит следующим образом:

 

struct имя_типа

{

информационное поле;

адресное поле;

};

 

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

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

Например:

struct pointer

{

int d; //информационное поле

pointer *p; //адресное поле

};

 

Информационных полей может быть несколько.

Например:

struct point

{

char *name; //информационное поле

int age; //информационное поле

point *next; //адресное поле

};

Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом, либо строкой.

Основными операциями, осуществляемыми с однонаправленными списками, являются:

  • формирование списка;
  • добавление в список
  • печать или просмотр (извлечение) списка;
  • вставка элемента в список;
  • удаление элемента из списка;
  • поиск элемента в списке
  • проверка пустоты списка;
  • удаление списка.

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

Рассмотрим подробнее каждую из приведенных операций.

Для описания алгоритмов этих основных операций используется следующее объявления:

struct pointer

{

int d; //информационное поле

pointer *p; //адресное поле

};

..........

pointer *ph; //указатель на первый элемент списка

pointer *pk; //указатель на конец списка

..........

pointer *pc; //указатель на текущий элемент списка (при необходимости)


Поделиться с друзьями:

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