Версия для печати темы
Форум «Всё о Паскале» _ Теоретические вопросы _ Преобразование списка в дерево
Автор: BlackShadow 9.08.2004 15:12
Так тема будет оформлена ближе к правилам...
По-подробнее о методе преобразования можно?
Список - это что-то линейное. Т. е. у него есть корень, и все элементы кроме корня и посденего имеют предыдущий и следующий.
Дерево - более развитая структура. Тут тоже есть корень (обычно один), а у него может быть много-много ветвей (в общем случае, хотя у бинарных деревьев не более двух ветвей). Так же и у остальных элементов...
Так что давай тихо, спокойно, без паники, не сумбурно ( ) объясни по какому принципу список преобразуется в дерево, а потом уже и разберёмся что тут к чему.
З. Ы. :
Цитата
два разных задания решаются одной программой
Ну... Так и есть... При небольшой толике фантазии...
Автор: biba 9.08.2004 21:31
Ну значит так.
В первой части проги создается однонаправленный линейный список без головного элемента и там есть к каждому элементу ключ (цифры). С ним производятся какие-то действия. Часть вторая - создание дерева (двоичного наверно, хотя написано в задании бинарного) а) из элементов списка б) из файла в) в диалоге с пользователем . Способ формирования дерева: с учетом значения признака. Вот задание А я не могу сделать
Автор: BlackShadow 10.08.2004 15:55
Цитата
без головного элемента
что-то новое...
список он на то и список, чтобы начинаться и заканчиваться...
Ладно, попробую описать работу со списком.
ООП, я так понял тебе не знакомо, придётся извращаться...
Код
Type
{Структура описывает элемент списка}
PListRec=^TListRec;
TListRec=Record
Key:Integer; {Ключ}
Item:String; {для удобства возбмём элементы спсиска - строки}
Next:PListRec {Следующий элемент}
End;
{Бредовая функция, но преподы её любят. Создаёт пустой список.
Мы будем обозначать список Nil'ом}
Function List_Create:PListRec;
Begin
CreateList:=Nil
End;
{Добавляет элемент Item с ключом Key в список List}
Procedure List_Add(Var List:PListRec;Key:Integer;Item:String);
Var
p:PListRec;
Beign
New(p);
p^.Key:=Key;
p^.Item:=Item;
p^.Next:=List;
List:=p
End;
{Очищает список освобождая всю память}
Procedure List_Clear(Var List:PListRec);
Var
p:PListRec
Begin
While List<>Nil Do
Begin
p:=List^.Next;
Dispose(List);
List:=p
End
End;
{Проверяет, есть ли элемент с ключом Key в списке. Если есть, то возвращает указатель на элемент списка с этим ключом, иначе - Nil}
Function List_Contains(Key:Integer;List:PListRec):PListRec;
Var
p:PListRec;
Begin
p:=List;
While p<>Nil Do
If p^.Key=Key Then
Begin
Contains:=p;
Exit
End
Else
p:=p^.Next;
Contains:=Nil
End;
{Доработанная функция List_Add, которая проверяет, есть ли элемент с таким ключом в списке. Если есть, то изменяет его значение, иначе добавляет его.}
Procedure List_Set(Var List:PListRec;Key:Integer;Item:String);
Var
p:PListRec;
Begin
p:=Contains(Key);
If p=Nil Then
Add(List,Key,Item)
Else
p^.Item:=Item
End;
Думаю, что это всё, что может понадобиться для работы со списком в данном контексте...
Могут быть описки, т. к. пишу без компилятора...
Остальное чуть позже... Надо же мне хотя бы вид делать, что работаю
Автор: biba 10.08.2004 16:56
Пасибики :p2:
И еще тогада вопросик, можно :p2:
У меня написана программа для титульного листа и оформлена в виде процедуры, а еще есть процедура рамки и как сделать, чтобы они работали одновременно, т.е. в рамке были слова, у меня сейчас сначала рамка вылезает, а потом слова ( рамка без grapth'а )
Автор: APAL 10.08.2004 17:12
Неужели эти процедурки так медленно работают, что даже заметна очередность вывода на экран?
Или имеется в виду, что процедуры делают вывод на принтер, а не на экран? Тогда надо их переделывать - совмещать вместе. А проще всего создать файл с титульной страницей и его посылать на печать.
Автор: BlackShadow 10.08.2004 17:32
Я так понял, что идёт попытка чего-то типа
Код
DrawBorder();
PrintTitle();
а на экране появляется
Цитата
Титульный лист
кого-то-там---------------+
который чего-то смог |
а смог именно это |
и вообще |
| дата |
| подпись |
| |
+---------------------------+
а предполагалось, что весь текст поместится в рамку.
Если я прав, то тебе надо дописать вот такую штуку:
Код
Uses CRT;
.......
DrawBorder();
{Создаём окно. Теперь весь текст будет выводится не на всём экране, а вот только в этом окошке. Координаты его должны быть внутри рамки.}
Window(Left,Top,Right,Bottom);
PrintTitle();
.....
End.
Или я не правидьно понял?
Автор: BlackShadow 10.08.2004 17:57
Цитата
Часть вторая - создание дерева (двоичного наверно, хотя написано в задании бинарного)
Это одно и то же. А по-англицки это звучиь как Full Shit
Ближе к теме. Двоичное дерево выглядит так: есть корень. У корня может быть до двух ветвей. У каждой ветви может быть до двух "подветвей" и т. д. Чем оно удобно? Например тем, что можно задавать путь к элементу серией указаний типа "налво, налево, налево (это уже измена выйдет) направо, направо, налево (иногда же можно), направо"
. В соответствие этим командам можно поставить 0 или 1. Таким образом описанное выше можно записать как 1110010, что соответствует 114 в деятичной. Теперь смотри: берём список (сотворенный ранее), перебираем все его элементы, ключ расцениваем ка маршрут, а элемент как элемент
. Таким вот образом и составляем дерево. Так же надо учесть, что тут мы пользуемся очаровательным моментом: чичло 1110010 - это число 1110010. Его можно записать только так. Если что-то записано не так, то это уже не число 1110010
От теории к практике:
Код
Type
{Элемент дерева}
PTreeItem=^TTreeItem;
TTreeItem=Record
Item:String; {Значение}
Left:PTreeItem; {Левая ветвь}
Right:PTreeItem {Правая ветвь}
End;
{Ещё одна тупость для преподов}
Function Tree_Create:PTreeItem;
Begin
Tree_Create:=Nil
End;
{Освобождение памяти}
Procedure Tree_Free(Var Tree:PTreeItem);
Begin
If Tree=Nil Then
Exit;
Tree_Free(Tree^.Left);
Tree_Free(Tree^.Right);
Dispose(Tree);
Tree:=Nil
End;
{Добавление элемента}
Procedure Tree_Set(Var Tree:PTreeItem;Key:String;Item:String);
Begin
If (Tree=Nil) Then
Begin
New(Tree);
Tree^.Left:=Nil;
Tree^.Right:=Nil;
Tree^.Item:=''
End;
If (Key="")
Tree^.Item:=Item
Else
If Key[1]="1" Then
Tree_Set(Tree^.Left,Copy(Key,2,255),Item)
Else
Tree_Set(Tree^.Right,Copy(Key,2,255),Item)
End;
{Для удобства может понадобиться ф-ция перевода числа в строку}
Function IntToStr(n:Integer):String;
Var
Result:String;
Begin
Str(n,s);
IntToStr:=Result
End;
{А процедура перевода списка в дерево будет выглядеть примерно так...}
Function Convert(List:PListRec):PTreeItem;
Var
Result:PTreeItem;
p:PListRec;
Begin
Result:=Tree_Create;
p:=List;
While p<>Nil Do
Tree_Set(Result,IntToStr(p^.Key),p^.Item);
Convert:=Result
End;
Ну, напоминать про ошибочки не буду
При работе с файлом можно сделать что-то типа такого:
Код
Var
n:Integer;
f:Text;
s:String;
Tree:PTreeItem;
Begin
Assign(f,"Input.Txt");
Reset(f);
n:=1;
Tree:=Tree_Create;
While Not Eof(f) Do
Begin
ReadLn(f,s);
Tree_Set(Tree,IntToStr(n),s);
Inc(n)
End;
Close(f)
End.
При работе с юзьверем можно сделать так:
Код
Var
n:Integer;
s:String;
Tree:PTreeItem;
Begin
n:=1;
Tree:=Tree_Create;
While Not Eof(f) Do
Begin
ReadLn(s);
If s="end" Then
Break;
Tree_Set(Tree,IntToStr(n),s);
Inc(n)
End
End.
будет считывать, пока юзверь не введёт "end".
А про рамку я понял теперь окончательно. Выводит у тебя не так, как я написал, а поочерёдно. Но лечение прежнее
Автор: biba 10.08.2004 18:13
Спасибики, будем пробовать :P
Насчет рамки => когда запускается программа-> появляется рамка, нажимаю
<Enter> появляются слова, рамка пропадает. Вот. Я пробывала текст процедуры для рамки загнать перед программой для текста (сделать как одну), но все равно сначала рамка, а потом текст ( все выводится на экран )
Автор: Guest 10.08.2004 18:44
Слова затирают рамку.
Без кода сложно сказать, где.
Нужно либо использовать Window (copyright BlackShadow), либо
в процедуру давать Rect - границ рамки для вывода текста и самому следить за выходом из границ Rect.
Автор: buy prednisone 10mg online for h 14.11.2021 20:37
Acheter Lioresal 25mg
Автор: can i buy priligy over the count 15.11.2021 23:00
Accessrx Complaints
Автор: azithromycin for throat infectio 20.12.2021 5:09
Viagra Kaufen Ohne Rezept Deutschland