Struct имя_типа

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

Динамические структуры данных

Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные структуры. К таким структурам относят:

1) линейные списки;

2) стеки;

3) очереди;

4) бинарные деревья.

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

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

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

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

{

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

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

};

Информационное поле – это поле любого, ранее объявленного или стандартного, типа. Информационных полей может быть несколько.

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

Пример 104

1. struct Node

{

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

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

};

2. struct point

{

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

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

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

};

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

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

1) начальное формирование списка (создание первого элемента);

2) добавление элемента в конец списка;

3) добавление элемента в начало списка;

4) удаление элемента с заданным номером;

5) чтение элемента с заданным ключом;

6) вставка элемента в заданное место списка (до или после элемента с заданным ключом);

7) упорядочивание списка по ключу;

8) и др.

Пример 105. Создание и печать однонаправленного списка

#include <iostream.h>

#include<string.h>

//описание структуры

Дата добавления: 2014-11-29