Переход от обычного дерева к бинарному происходит по следующему алгоритму:
берется узел (очередной) дерева, который содержит n ветвей, при этом в новое бинарное дерево в левую ветку последовательно переписываются все n узлов и от каждого из них в правую ветку идут ссылки.
Более общим случаем дерева является сеть-это аналог графов (граф, отличается от дерева тем, что в нем есть циклы, т. е. обратные связи). Особенностью дерева является тот факт, что из вершины дерева (корня) можно попасть в любой узел только одним путём, а в сети таких путей может быть множество.
Очереди и стек
Как правило реализуются на основе линейных списков (обычно двусвязных), однако, их особенность заключается в том, что каждая из этих структур имеет свою строгую дисциплину размещения нового элемента и извлечения из очереди или стека очередного элемента. Это такие дисциплины обслуживания в программировании принято обозначать:
для очереди FIFO (FirstInFirstOut) и LIFO(LastInFirstOut)
Для очереди и для стека обязательно существуют процедуры размещения нового элемента в памяти и извлечения очереди элемента из памяти.
Очередь: добавляем в хвост, извлекаем из головы.
Стек: добавляем в голову, извлекаем из головы.
Коллекции
Это как правило динамическая структура данных, которая предусмотрена в основных языках программирования Pascal, C++.
Технические коллекции представляют собой линейные двухсвязные списки. Элементами могут быть различные структуры. Коллекция может сочетать списки, деревья.
В документации по языкам программирования всегда можно найти назначение и описание элементов коллекции.
 |
Линейные списки. Схематичные обозначения основных операций
К основным операциям с линейными списками относятся:
1. Создание списка;
2. Добавление нового элемента в список:
А) в голову списка;
Б) в хвост списка;
В) после текущего элемента списка;
Г) перед текущим элементом списка;
3. Удаление элемента из списка:
А) удаление текущего элемента;
Б) удаление текущего, совпадающего с головой;
В) удаление текущего, совпадающего с хвостом;
4.Обход списка с целью его обработки.
Создание списка
· Необходимо выделить память
· Необходимо обнулить указатель
· 
|
 |
 |
· Внести в информационную часть списка данные
Для двухсвязного списка изменится только второй шаг (обнуляется указатель на предыдущий элемент списка).
Добавление нового узла в список
 |
· Выделяем память под новый узел
· Запоминаем указатель на этот узел
· Запоминаем старый указатель на голову списка Hold
Hold:=H;
· Заносим в новый узел данные
· Присвоить указателю головы списка значение указателя на новый узел
· Указателю на следующий элемент после нового присвоить значение
N.^next:=Hold;
*для двусвязного списка
Добавление в голову
- Выделить память и запомнить указатель Заполняем данные Hold:=H; Запоминаем старый указатель Обнуляем указатель на предыдущий элемент H:=N; Устанавливаем указатель на голову списка на новый элемент Следующий элемент после нового
N.^next:=Hold;
Hold.^back:=H;
Добавление в хвост
- Выделяем память для нового элемента и запоминаем указатель на него Заполняем данными Обнуляем указатель на следующий элемент Запоминаем указатель на хвост списка Hold:=T T:=N – устанавливаем указатель на хвост списка на новый элемент Для предыдущего элемента делаем указатель Hold
N.^back:=Hold;
Hold.^next:=N;
*для двусвязного списка
- Выделяем память и запоминаем указатель на него Заполняем данными Запоминаем указатель на хвост списка Hold:=T Обнуляем указатель на следующий элемент Устанавливаем указатель на хвост списка на новый элемент T:=N Предыдущий элемент перед новым делаем Hold
T.^ back:=Hold
- Hold.^next:=T
Добавление после текущего элемента
- Создаем новый элемент, выделяем память Занести данные Запоминаем текущий элемент
CurOLD:=Cur;
- N.^next:=Cur.^next; Cur.^next:=N; N.^next.^back:=N; N.^back:=CurOLD; Cur:=N
Добавление перед текущим элементом
- Создаем новый элемент, вносим данные и запоминаем указатель Запоминаем текущий элемент CurOlD:=Cur N.^back:=Cur.^back; Cur.^back:=N; N.^back.^next:=N N.^next:=CurOLD; Cur:=N;
Удаление
· Cur.^back.^next:=Cur.^next;
· Cur.^next.^back:=Cur.^back;
· Cur.^next:=0;
· Cur:=Cur.^back;
· Освободить память под указатель CurOLD
Function DISPOSE(CurOLD)
Пример: Добавление элемента
Var H, T: ^List
Type
List=record
Info:string;
Back:^List;
Next:^List;
end;
Function createlist(s:string): ^List;
Var p:^List;
Begin
New(p);
H:=p;
T:=p;
p. string:=s;
createlist:=p;
end;
Function addlist (s:string): ^List;
. . .
Пример программы работы со списком
Добавление к списку, удаление, изменение текущего:
1.Createlist-создание линейного списка
2.Addlist-добавление в хвост
3.DelCur-удалить текущий
4.Printlist-распечатать список
Параметры:
1.(ptr)-указывает на тот узел, который добавляется к списку
2.(p cur)-удаление
3.(p head)указывает на голову
Меню:
1.Добавить студента
2.Перейти к следующему
3.Перейти к предыдущему
4.Показать данные
5.Удалить данные о текущем студенте
6.Вывести весь список
7.Выход;
Type
P Node=^Node;
Student=record
FIO:string;
STIP:real;
GROUP:string;
end;
Node=record
STUD:Student;
Next:p Node;
Back:p Node;
Begin
Ch:=’1’;
While Ch<>7 do begin
Ch:=readkey;
Doselection(Ch);
End.
Procedure Doselection(Ch:char);
Begin
Case Ch of
‘1’: Head:=addlistTail;
‘2’: Cur:=Listnext;
‘3’: Cur:=Listback;
‘4’: ShowNode(Cur);
‘5’: DelCur(Cur);
‘6’: Printlist (Head);
end;
End;
Function addlistTail:pNode;
Begin
New(p);
Readln(p.^FIO,
p.^STIP
p.^GROUP) ;
p.^next:=Nil;
if (Tail=Nil) and (Head=Nil) then begin
Tail:=p
Head:=p;
end
else begin
Tail.^next:=p;
Tail:=p;
end;
addlist:=Head;
End;
Function ListNext:pNode;
Begin
If (Head=Nil) then ListNext:=Nil
else
if (Cur=Tail);
if (Cur.^next<>Nil) then Cur:=Head
else Cur:=Cur.^next;
ListNext:=Cur;
End;
Procedure ShowNode (p:pNode);
Begin
Writeln(p.^FIO, p.^STIP, p.^GROUP)
End;
Procedure DelCur(p:pNode):pNode;
Begin
If (p<>Nil) then begin
If (p.^next=Nil) then begin
Tail:=Tail.^back;
Tail.^next:=Nil;
Dispose (cur);
Cur:=Tail;
End;
Else if (Head=p ) then
Head:=Head.^next;
Dispose (cur);
Cur:=Head;
end;
else Cur.^back.^next:=Cur.^back;
T:=Cur;
Cur:=T.^next;
Dispose (T);
End;
Function Printlist (p:pNode);
Var
T:pNode;
Begin
T:Head;
While T<> Nil do begin
ShowNode(T);
T:=T.^next;
End;
End;
Function CntList(p:pNode):integer;
Var
T:pNode;
i:integer;
Begin
T:=p;
i:=0;
while T<> Nil do begin
i:=i+1;
T:=T.^next;
End;
CntList:=I;
End;
Function GotoNode (p:pNode, i:integer):pNode;
Var
T, Head, Tail, Cur:pNode;
i:integer;
Begin
Head:=Nil; Tail:=Nil; Cur:=Nil;
T:=p;
i:=0;
while T<> Nil and I<Cnt do begin
i:=i+1;
T:=T.^next;
GotoNode:=T;
End;
End;
Пример использования динамической структуры - стек
Рассмотрим работу с записями, содержащим компонент типа ссылки (будем использовать стек – совокупность однотипных элементов), где в записи должен быть указатель на предшествующий элемент, а при считывании данных из стека в первую очередь должны извлекаться данные, поступившие в него последними.
При работе со стеком обычно используются 2 процедуры:
- PUSH – добавление в стек; POP – удаление из стека;
После чтения стека всё, что было прочитано в стеке, стирается. Мы читаем информационную часть того элемента, на который указывает указатель стека.
 |
 |
После чего в указатель стека пишется ссылка на предыдущий считанному элемент, а последний уничтожается.
Элементы стека должны содержать информационную часть(например типа «символ») и ссылочную часть.
Type
Point=^elsteka;
Elsteka=record
Info:char;
Pred:point;
End.
Сначала исполняется тип elsteka и только потом он определяется. Это единственное исключение в Pascal.
Обратная польская запись (ОПЗ)
ОПЗ - это способ записи выражений(как правило математических) в так называемом постфиксном виде, т. е. в таком виде, когда сначала записываются все операнды, а потом выполняемые над ними операции.
ОПЗ как правило используется в трансляторах и компиляторах для преобразования выражений, а также синтаксических конструкций языка к виду, удобному для генерации машинного кода. Особенность выражения (в более общем виде программы), написанного в ОПЗ, является тот факт, что вычислить это выражение (перевести программу в машинный код) можно одним проходом слева направо фактически символ за символом вычисляя значение выражения.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
