4913

Организация списочных и древовидных структур

Лекция

Информатика, кибернетика и программирование

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

Русский

2012-11-29

16.05 KB

1 чел.

Организация списочных и древовидных структур.

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

В данных случаях используется динамическое размещение данных в памяти непосредственно в процессе работы программы. Основными структурами для такой работы являются списки и древовидные структуры.

Однонаправленные списки.

Определяется некоторая запись, содержащая помимо основных информационных полей дополнительное поле, в котором хранится указатель на следующую такую же запись в памяти.

 

р

н

к

Описания в паскале.

Type ppp:^student;

Student=record

 Fio: string;

 Age: integer;

 P_next: ppp; // если написать :^student; , выдаст ошибку

 End;

Для работы с такими записями и списками записей любой длинны достаточно всего 3 указателей - указатель на начало списка, указатель, при помощи которого осуществляется перемещение по списку, и указатель, используемый при создании нового элемента списка.  

Пример: Программа запрашивает у пользователя количество записей в списке, создает и заполняет этот список, печатает его на экране, после чего освобождает память, уничтожая список.

Type p_student=^student;

Student=record

 Name:string;

 Age:integer;

 P_next:p_student;

 End;

Var count:integer;

I:integer;

P_start, p_work, p_dop :p_student;

Begin

Writeln(‘ введите количество записей ‘);

Readln(count);

P_start:=NIL;

P_work:=NIL;

P_dop:=NIL;

 For i:=1 to count do

 Begin

 New(p_dop);// где-то появилась запись.

 Write(‘введите имя ‘);

 Readln(p_dop^.name);

 Write(‘введите возраст’);

 Readln(p_dop^.age);

 P_dop.p_next:=NIL;

 If p_start=NIL then  //списка ещё нет, создан 1 элемент.

  p_start:=p_dop;

 else 

p_work^.p_next:=p_dop;

 p_work:=p_dop;

 end;

 // печать списка

P_work:=p_start;

 For i:=1 to count do

 Begin

 Writeln(p_work^.name,’  ‘,p_work^.age);

 P_work:=p_work^.p_next;

 End;

 {While p_work<>NIL do

 Begin

 Writeln(p_work^.name,’  ‘,p_work^.age);

 P_work:=p_work^.p_next;

 End;}

// если мы закончим программу, не удалив из памяти размещённые нами элементы, то

//после закрытия программы windows будет считать, что эта память по прежнему кем-то занята.

//удаление списка из память

While p_work<>NIL do

 Begin

 P_start:=p.work^.next;

 Dispose(p_work);

 P_work:=p_start;

 End;

End.


 

А также другие работы, которые могут Вас заинтересовать

79631. ОБУСЛОВЛЕННОСТЬ И ОПЫТ УГОЛОВНО-ПРАВОВОЙ БОРЬБЫ С УКЛОНЕНИЯМИ ОТ ОТБЫВАНИЯ ЛИШЕНИЯ СВОБОДЫ В ЗАРУБЕЖНОМ ЗАКОНОДАТЕЛЬСТВЕ 131.5 KB
  В зависимости от типичных правовых систем мира сначала будет предпринята попытка рассмотреть наиболее показательный зарубежный опыт кратковременного пребывания осужденного к лишению свободы за пределами исправительного учреждения и отсрочки отбывания наказания либо исполнения приговора суда...
79632. ЗАКОННОСТЬ И ОБОСНОВАННОСТЬ СУДЕБНОГО ПРИГОВОРА 110.5 KB
  Цель уголовного процесса: установление истины по уголовному делу изобличение и наказание лица совершившего преступление и защита невиновного человека от необоснованного обвинения и осуждения достигается при постановлении судом правосудного приговора.
79633. ДОТАЛЬНЫЕ СОГЛАШЕНИЯ И DONATIO PROPTER NUPTIAS В РИМСКОМ ПРАВЕ 76 KB
  Поимущественные отношения супругов в римском праве определялись не браком, а переходом женщины во власть мужа, эффект которого подобен усыновлению. Брак сам по себе никак не сказывается на имущественных правах сторон: женщина по прежнему остается под опекой и не терпит никаких дополнительных...
79634. ЗАКОННЫЙ РЕЖИМ ИМУЩЕСТВА СУПРУГОВ 73.5 KB
  Имущество имеющееся у супругов состоит из имущества собственником которого является каждый из супругов личное имущество и имущества приобретенного во время брака совместное имущество супругов. Определяющим признаком правового режима является бездолевой характер поскольку доли супругов в их общем...
79635. ПЕРСПЕКТИВЫ РАЗВИТИЯ ОРГАНОВ ГОСУДАРСТВЕННОГО ФИНАНСОВОГО КОНТРОЛЯ 92.5 KB
  В 2002 году на IV Конференции Ассоциации контрольно-счетных органов Российской Федерации была принята Декларация принципов деятельности контрольно-счетных органов России что заложило основу для объединения усилий всех органов государственной власти и органов местного самоуправления усилий...
79636. ПОРЯДОК И ОСОБЕННОСТИ ОФОРМЛЕНИЯ ДОГОВОРА ИПОТЕКИ ЖИЛЫХ ПОМЕЩЕНИЙ 175 KB
  Договор о залоге недвижимого имущества договор об ипотеке это договор в котором одна сторона залогодержатель являющийся кредитором по обязательству обеспеченному ипотекой имеет право получить удовлетворение своих денежных требований к должнику по этому обязательству из стоимости...
79637. АДМИНИСТРАТИВНО-ПРАВОВОЙ РЕЖИМ СТРАХОВОЙ ДЕЯТЕЛЬНОСТИ В РОССИЙСКОЙ ФЕДЕРАЦИИ 159 KB
  В правовой научной литературе вопрос о природе правового режима вообще и административно-правового режима в частности поднимался неоднократно. Российский энциклопедический словарь определяет режим как установленный порядок жизни совокупность правил мероприятий норм для достижения...
79638. О БРАЧНОМ ДОГОВОРЕ В РОССИЙСКОЙ ФЕДЕРАЦИИ 92 KB
  Принятие Семейного кодекса России поставило юридическую науку вообще и науку семейного права в частности перед необходимостью исследовать феномен брачного договора (контракта) как института семейного права, его роль и значение в регулировании имущественных семейно-брачных отношений, условия...
79639. КОНФЕДЕРАТИВНЫЕ СОЮЗЫ: ИСТОРИЧЕСКАЯ ХАРАКТЕРИСТИКА И ПРАВОВАЯ ОСНОВА 237.5 KB
  Наиболее остро устаревшие характеристики конфедерации обнаруживают свою несостоятельность в вопросе о правовых основах конфедерации, ибо решение именно этого вопроса обусловливает изучение конфедерации конкретной отраслью юридической науки.