Классификация структур данных. (Лекция 8) презентация

L.elems[i] - i -й элемент списка

после 1-го этапа вставки: после 2-го этапа вставки:

3-я компонента свобо-
дна для записи нового
значения

бывшие третий
теперь занимает
четвертую
компоненту

в 3-ей компоненте новое
значение

для вставки элемента в пустой список

make_null(L); insert(L, 9,1):

Для удаления i-го элемента
procedure delete(var L: list; i:integer);
var p: integer;
begin
for p:=i to L.last-1 do
L.elems[p]:=L.elems[p+1];
L.last:=L.last-1
end;

function is_full(var L: list):boolean;
begin
is_full:=L.last=maxlen
end;
function is_empty(var L: list):boolean;
begin
is_empty:=L.last=0
end;
function is_valid(var L: list;i:integer):boolean;
begin
is_valid:=(1<=i) and (i<=L.last)
end;

list = record
elems: array[1..max_elem] of elem;
first:byte
end;

procedure add_beg (var t: list; X:elem_type);
var cur:byte;
begin
cur:=t.first+1;
t.elems[cur].info := X;
t.elems [cur].next := first;
t.first := cur
end;

procedure trav_info (var t:list);
var
cur: byte;
begin
cur := t.first;
while (cur <> 0) do
begin write(t.elems [cur].info,' * ');
cur := t.elems [cur].next
end
end;

Вызов процедуры:
writeln (‘удалить элемент со значением :');
readln(r);
if r>0 then DEL(t1,r);
if r<0 then DEL(t2,r);

list = record
elems:array[1..max_elem] of elem;
first, last: byte
end;

0

0

начало

конец

Вставка
L.elems[new_el].next:= L.elems[cur].next;
L.elems[new_el].prev:= L.elems[cur+1].prev;
L.elems[cur].next:=new_el;
L.elems[cur+1].prev:=new_el;

Var L:list;

Удаление
L.elems[cur].next:= L.elems[del].next;
L.elems[L.elems[del].next].prev:= L.elems[del].prev;

cur

new_el

del

Текущий элемент

В очереди (queue) всегда удаляется элемент, который содержится в множестве дольше других. Стратегия "первым вошел - первым вышел" (first-in, first-out ).

top

Push (S,5)

5

Push (S,2)

2

Pop (S)

Pop (S)

function Stacktop : integer;
begin
Stacktop := S.elems[S.top];
end;

procedure init_stack (var S: stack);
begin
S.top:=0;
end;

function full_stack(var S: stack):boolean;
Begin
full_stack:=S.top=stacksize
end;

function empty_stack(var S: stack):boolean;
Begin
empty_stack:=S.top=0
end;

Для очереди определены три примитивные операции.

Очистка очереди;
Считывание первого элемента очереди; Операция remove(q) удаляет элемент из начала очереди q и присваивает его значение переменной х.
Вставка элемента в конец очереди; Операция insert (q,x) помещает элемент х в конец очереди q.
Проверка, является ли очередь пустой. Третья операция, empty (q), возвращает значение true или false в зависимости от того, является ли данная очередь пустой или нет

Function Insert(a : data) : boolean;
begin
if (Q.tail mod SIZE)+1=Q.head then
insert:=false
else begin
Q.ELEMS[tail]:=a;
Q.tail:=(Q.tail mod SIZE)+1;
Insert:=true;
end;
end;

Function Remove(var a: data) : boolean;
begin
if Q.tail=Q.head then
Remove:=false
else
begin
a:=Q.elems[head];
q.head:=(q.head mod SIZE) + 1;
Remove:=true;
end;
end;

Дерево характеризуется следующими признаками:
дерево имеет 1 элемент, на которого нет ссылок от других элементов. Этот элемент называется корнем дерева;
в дереве можно обратиться к любому элементу путем прохождения конечного числа вершин;
каждый элемент дерева связан только с одним предыдущим элементом.

Высота - это количество уровней дерева.
Количество ветвей, растущих из узла дерева, называется степенью исхода узла.

2

1

4

5

8

9

10

3

6

7

Способы обхода узлов дерева

j

info

count

sun

Type
node= record
Data: intеger;
Leftsun, rightsun : intеger
End;

BTree= record
Nodes: array [1..maxlen] of node;
First:integer
End;