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.


 

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

75314. Периодизация истории средних веков и феодализма в отечественной и зарубежной историографии 34.5 KB
  Западной Римской империи. Встреча двух миров античного грекоримского и варварского германского кельтского славянского стала началом глубокого переворота который открыл новый средневековый период в истории Западной Европы. В практике преподавания пока принято считать условным концом средневековья первую буржуазную революцию общеевропейского значения английскую революцию 1640-1660х годов положившую начало господству капитализма в Западной Европе и совпавшую с окончанием первой общеевропейской Тридцатилетней войны 16181648 гг....
75315. Источники по истории средних веков (V-XV вв) 41.5 KB
  Источники по истории средних веков VXV вв. Законодательные и документальные источники по истории средних веков. Они являлись ценными источниками по истории VI в. Источники по истории XI XV вв.
75317. Понятие “феодализма” в западноевропейской историографии 39.5 KB
  Понятие феодализма в западноевропейской историографии. Понимание феодализма в историографии XVIII в. Главными чертами феодализма некоторые из них считали политическую раздробленность и как следствие ее господство в средние века папской теократии. в определении сущности феодализма недалеко ушли от историков эпохи Просвещения хотя в отличие от них оценивали феодализм как положительное историческое явление: реакционные романтики потому что видели в нем свой политический идеал...
75318. Проблема генезиса феодализма в отечественной и зарубежной историографии 46.5 KB
  Проблема генезиса феодализма в отечественной и зарубежной историографии. Проблема генезиса феодализма и связанный с нею вопрос о путях складывания феодально зависимого крестьянства представляет трудность и с источниковедческой и с теоретической точек зрения. В советской историографии становление феодализма рассматривалось в первую очередь в аспекте вскрытия сдвигов в производительных силах в отношениях собственности...
75319. Образование государства и возникновение писаного права у франков 38.5 KB
  Образование государства и возникновение писаного права у франков. В исторических памятниках имя франков появилось начиная с III в. Франки распадались на две большие ветви приморских или салических франков от латинского слова slum что значит море живших у устья Рейна и прибрежных или рипуарских франков от латинского слова rip что значит берег живших южнее по берегам Рейна и Мааса. Из вождей франков известен Меровей при котором франки сражались против Аттилы на Каталаунских полях 451 г.
75320. Рост крупного землевладения и ослабление центральной власти у франков при преемниках Хлодвига. Объединение страны майордомами Австразии 33.5 KB
  После смерти Хлодвига началось дробление королевства. намечается обособление самостоятельных политических единиц в составе Франкского королевства: Нейстрии СевероЗападной Галлии с центром в Париже; Австразии северовосточной части Франкского королевства включавшей исконные франкские области по обоим берегам Рейна и Мааса; Бургундии территории бывшего королевства бургундов. В Нейстрии которая к моменту франкского завоевания была сильно романизована галлоримляне составлявшие и после завоевания большинство населения раньше чем в...
75321. Франция в IX-XI веках 39.5 KB
  В начале этого периода в стране имелось еще много крестьян не находившихся в какойлибо зависимости от частных лиц и подчинявшихся непосредственно короне. Вместе с тем возрастало число крестьян находившихся в личнонаследственной зависимости сервов и колонов а также жителей иммунитетных территорий. В результате все жители округи будь они в личной либо поземельной зависимости от данного или какогонибудь другого феодала или нет становились его людьми в судебноадминистративном отношении. Для по земельно и лично зависимых крестьян...
75322. Англия в XI-XII вв. Завершение феодализации английского общества 47 KB
  в Англии в основном уже господствовали феодальные порядки но процесс феодализации еще не завершился. Вильгельм со своим войском на больших ладьях переплыл ЛаМанш и высадился на юге Англии в бухте Павенси. Во главе последнего выступил избранный советом мудрых новый король Англии Гарольд. Герцог Нормандский же двинулся к Лондону захватил его и стал королем Англии под именем Вильгельма I Завоевателя.