Списки. (Списочные структуры)

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

Агрегативные переменные

Простейшей агрегативной переменной является массив (упорядоченный набор данных одного типа).

На метоязыке: declare A(10) integer;

Будем считать, что массив относится к статической структуре данных (нединамические), т.е. структура для которой место выделяется до запуска программы.

Доступ к элементу массива: А(2):=1;

Записи (записные типы) – более сложная структура, чем массив – она состоит из нескольких типов.

На метоязыке

Описание структуры данных:

declare 1 X,

2 Y integer;

2 Z(1) real;

X.Y:=1;

Объявление типа (Pascal):

type

Struct1 = record

x:integer;

y:array 1..10 of real;

end;

var

s:Struct1; - объявление переменной этого типа.

Замечание: Агрегативные структуры данных используются для создания более сложных структур данных: динамических и абстрактных структур данных.

Список – основа любой динамической структуры.

Опр. Список – упорядоченный набор данных одного типа. Отличается от массива тем, что имеет переменный размер (размер списка не определяется при запуске программы).

Список из n элементов --------------------------------->

Список может быть реализован 2-мя способами:

1. на основе статических структур (массивов).
2. на основе динамических переменных.

Пример объявления списка:

1. на основе статических структур:

type

TList = record

| DATA_ENTRIES: тип;

end;

var

List: array [1..N] of TList; {массив, N=const }

SIZE: integer; {, указывает текущий размер}

… {базовые операции}

2. на основе динамических переменных:

type

PTR = ^TList; {новое поле данных имеющий тип указателя на TList }

TList = record

| DATA_ENTRIES: тип;

| NPTR: PTR {указатель на начало списка}

end;

var

LIST_HEAD: PTR; {указатель, который может указывать на начало (или конец) списка}.

Обращение к элементам списка, созданного первым способом:

List[1].DATA_ENTRIES;

List[2].DATA_ENTRIES;

…

List[N].DATA_ENTRIES;

Обращение к элементам списка, созданного вторым способом:

List_HEAD^.DATA_ENTRIES; - обращение к I-ому элементу

List_HEAD^.NPTR^.DATA_ENTRIES; - ко II-ому элементу

List_HEAD^.NPTR^. NPTR^.DATA_ENTRIES;

…

Это однонаправленный (односвязный) список – можно перемещаться только вперед.

Процедуры для динамического списка:

Исходная структура списка:

type

NameStr=string[15];

Link=^Student

Student=record

Name:NameStr;

Mark:integer;

…

Next:Link;

end;

var

First:Link;

Создание и инициализация динамической переменной:

var

P:Link;

…

New(P); {создали элемент списка}

{инициализируем элемент списка}

P^.Name:=’Иванов’;

P^.Mark:=5;

…

P^.Next:=nil; {пустой указатель}

Процедура добавления элемента в начало списка:

procedure AddFirst(A:Link);

{А-указатель на добавляемый элемент}

begin

A^.Next:=First;

First:=A;

end;

Процедура добавления элемента в произвольное место списка:

procedure AddAfter(A,Old:Link);

begin

a^.Next:=Old^.Next; { (1) А-указатель на добавляемый элемент}

Old^.Next:=A; { (2) Old-указатель на элемент списка, за которым

добавляется элемент}

end;

Удаление элемента из начала списка:

procedure DelFirst(var A:Link);

begin

A:=First; {сохраняем указатель на удаляемый элемент}

First:=First^.Next;

end;

Удаление элемента из произвольного места списка:

procedure DelAfter(Old:Link;Var A:Link);

begin

A:=Old^.Next; {сохраняем указатель на удаляемый элемент}

Old^.Next:=Old^.Next^.Next

end;

Поиск элемента:

function FindName(FN:NameStr):Link; {ф-ция возвращает указатель (Link) на найденный элемент}

var Curr:Link; {Curr – указатель на текущий элемент списка }

begin

Curr:=First;

While Curr<>nil do

If Curr^.Name=FN then

begin

FindName:=Curr; {возвращает указатель на найденный

Exit; элемент}

end;

else

Curr:=Curr^.Next;

FindName:=nil; {элемент не найден}

end;

Дата добавления: 2014-01-07