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.


 

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

61348. Складання таблиці множення числа 3. Знаходження значень виразів на дії різного ступеня 19.03 KB
  Яке число залишилось без виразу Добутком яких чисел воно є б бліцтурнір Скільки крил у чотирьох горобців Скільки ніг у п’яти страусів Скільки вух у шести мавп Скільки разом крил у восьми гусей і одного горобця...
61349. Основи технології писанкарства. Орнаменти писанкарства. Символи в писанкарстві 4.18 MB
  Символи в писанкарстві. Символи в писанкарстві. Згодом виникли символи неначе букви тієї чарівної мови. Символи в писанкарстві.
61350. План-конспект уроку, Групи слів за значенням: синоніми, антоніми, омоніми 24.62 KB
  Мета: поглибити знання учнів щодо синонімів, антонімів, омонімів; удосконалити вміння пятикласників відрізняти омоніми від багатозначних слів, правильно вживати їх у мовленні; навчити добирати фразеологічні синоніми...
61351. Людина і природа. Проблеми екології. Природні катаклізми. Введення лексики 72.63 KB
  МЕТА: Навчальна: ознайомити учнів з новою лексикою та активізувати її вживання в мові, розширити знання учнів про проблеми екології та навколишнього середовища, природні катаклізми; збагачувати словниковий запас учнів...
61353. Алюміній. Положення в ПСХЕ. Будова атому. Основні хімічні властивості 57.63 KB
  Цілі уроку: Надати інформацію про історію відкриття та добування алюмінію. Ознайомити з фактами біографії видатних вчених пов’язаних з дослідженням алюмінію.
61354. Релаксация на уроках немецкого языка на начальном этапе обучения 38.3 KB
  Современный урок иностранного языка характеризуется большой интенсивностью и требует от учеников концентрации внимания, напряжения сил. Хорошо известно, что внимание учащихся, особенно в V—VI классах неустойчиво.
61355. Использование компьютерных технологий при изучении иностранного языка 41.75 KB
  Преимущества и недостатки обучения иностранного языка с помощью ПК. Но этот метод обучения еще не оценен по достоинству. В своей работе я докажу что ПК может быть использован как вспомогательное средство как любое другое техническое средство обучения или учебник.
61356. Гидденс Э. Устроение общества: Очерк теории структурации 835 KB
  Основанием для написания настоящей книги является ряд важных открытий и разработок, которые имели место в общественных науках в течение последнего полутора десятка лет. Эти открытия концентрировались главным образом в области социальной теории, и в максимальной степени затронули самую опасную