Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Элемент списка в общем случае представляет собой комбинацию поля записи (информационного поля) и одного или нескольких указателей.

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

Под односвязными списками понимают упорядоченную последовательность элементов, каждый из которых имеет 2 поля : информационное поле info и поле указателя ptr .
Особенностью указателя является то, что он дает только адрес последующего элемента списка. У однонаправленных списков поле указателя последнего элемента в списке является пустым nil.
Lst — указатель начала списка. Он представляет список как единое целое. Иногда список может быть пустым, т.е. в данном списке нет ни одного элемента. В этом случае lst = nil.

Алгоритм

Операции с односвязными списками.
1.Вставка элемента в начало односвязного списка.

Вставим в начало данного списка элемент, информационное поле которого содержит переменную D. Чтобы это осуществить, необходимо произвести следующие действия :
а) Создать пустой элемент, на который указывает указатель p.

b) Информационному полю созданного элемента присвоить значение D.

с) Связать новый элемент со списком.

Ptr(p)=lst             (lst — уже не указывает на начало списка)

d) Перенести указатель lst на начало списка.

Окончательно:

Удаление элемента из начала односвязного списка

Удалим 1-й элемент списка, но при этом запомним информацию содержащиеся в поле info этого элемента.

Чтобы это осуществить, необходимо произвести следующие действия :
a)  Ввести указатель р, который будет указывать на удаляемый элемент.
P=lst
b) Запомнить поле info элемента, на который ссылается указатель р, в некоторую переменную (х).
X=info( P )
c) Перенести указатель lst на новое начало списка.
lst=ptr( P )
d) Удалить элемент на который указывает указатель р.
Freenode( P )
Окончательно:

Вставка элемента в список

Вставим в данный список перед элементом на который указывает указатель р, элемент с информационным полем х.

Чтобы это осуществить необходимо произвести следующие действия :
a) Создать пустой элемент на который указывает указатель q.
Q=getnode
b) Внести х в информационное поле созданного элемента.
Info(Q)=x
c) Связать элемент х с элементом В.
Ptr(Q)=Ptr(P) — это значит, что указателю созданного элемента присваивается значение указателя элемента р.
d) Связать элемент А с элементом х.
Ptr(p)=Q — это значит, что следующим за элементом А будет элемент на который указывает указатель Q.
Окончательно :

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

Удалим из списка элемент, который следует за элементом с рабочим указателем р.

Чтобы это осуществить необходимо произвести следующие действия :
a) Ввести указатель Q, который будет указывать на удаляемый элемент.
Q=ptr(p)
b) Поставить за элементом А элемент В.
Ptr(p)=Ptr(Q)
с) Запомнить информацию, которая содержится в поле info удаляемого элемента.
K=info(Q)
d) Удалим элемент с указателем Q.
Freenode(Q)
Окончательно :

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники