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.


 

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

64159. Розробка тестових завдань та автоматизованої системи тестування для перевірки та оцінювання поточних знань студентів з дисциплін «Інформатика. Обчислювальна математика та програмування» та «Комп’ютерні мережі» 1.44 MB
  Використання комп’ютерів для контролю знань є економічно вигідним і забезпечує підвищення ефективності навчального процесу. Як зазначає І. Булах, комп’ютерне тестування успішності дає можливість реалізувати основні дидактичні принципи контролю навчання: принцип індивідуального характеру перевірки й оцінки знань...
64160. Разработка и исследование ускоренного алгоритма калибровки моделей больших сетей по коэффициенту кластеризации 1.56 MB
  Целью работы является изучение алгоритмов генерации случайных графов, разработка нового алгоритма, его реализация, проведение необходимых испытаний. В работе изложены необходимые понятия из теории случайных графов, подробно разбираются методы генерации графов Барабаши-Альберт, Эрдеша-Реньи, Уатса-Строгатса...
64162. Аналіз та прогнозування потоків вхідної та вихідної кореспонденції у Ширяївському ЦПЗ №4 Одеської дирекції «Укрпошта» 2.65 MB
  Зміст розрахунково-пояснювальної записки перелік питань які потрібно розробити Основні методи аналізу часових рядів Тенденція і коливання часових рядів Періодизація динаміки часових рядів Стійкість рівня ряду та тренда Регресійний аналіз Сингулярний спектральний аналіз...
64163. Определение оптимальных способов обеспечения безопасности на железнодорожных переездах Ижевского отделения ГЖД 9.19 MB
  Автомобилисты не осознают что шлагбаум это не очередное препятствие которое железнодорожники установили у них на пути а устройство прямое назначение которого уберечь автомобиль и находящихся в нем людей от проходящего железнодорожного состава эффект от вложенных в охрану переездов средств будет минимальным.
64164. Синтез ансамблей гетероциклов на основе тиазола 2.91 MB
  В данном дипломном проекте разрабатываются методы получения 4 оксотиазолидин 25 диилиденов Составлена технологическая схема получения роданина и приведено описание технологического процесса производства. Химическая схема получения роданина...
64165. Разработка и обоснование мероприятий по усовершенствованию укрытия и защиты населения Октябрьского района города Ижевска 896 KB
  Размещение защитных сооружений гражданской обороны Укрытие населения района категорированного города Размещение и укрытие населения Октябрьского района г. Ижевска в защитных сооружениях гражданской обороны подвальных и других заглубленных помещениях Расчет строительства простейших укрытий...
64166. Разработка предложений по совершенствованию контроля качества тяжелых бетонных смесей на предприятии ООО «ПКФ Стройбетон» 233.98 KB
  Во втором разделе описывается существующие технологии контроля качества бетона на различных этапах его использования: при погрузке транспортировке укладке уходе за бетоном. Показатели качества бетона и бетонной смеси Приготовление бетонной смеси и ее использование в строительстве...
64167. Процесс управления рисками в отношении качества услуг ООО «ПИТЦ «Геофизика» 12.75 MB
  Описание существующего процесса управления рисками Обоснование необходимости улучшения процесса управления рисками в отношении качества услуг ООО ПИТЦ Геофизика Разработка предложений по улучшению процесса управления рисками Сбор информации и анализ существующих методов оценки рисками...