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.


 

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

68505. Ядерная физика 426.5 KB
  Активность является характеристикой радиоактивного вещества как источника радиоактивного излучения. Поглощенная доза количество энергии ядерного излучения поглощенное единицей массы вещества. Поглощенная доза не учитывает качественный состав падающего излучения.
68506. Понятие финансового права и его сущность 62 KB
  Финансовая деятельность государства - это осуществление им функций по планомерному образованию, распределению и использованию денежных фондов (фин ресурсов) в целях реализации задач социально-экономического развития и обеспечения обороноспособности и безопасности страны.
68507. Правовые системы современности 195 KB
  Романо-германская правовая семья. Становления и развития романо-германского права. Основные черты и особенности романо-германского права. Существенные различия правовых систем Германии и Франции. Англосаксонская правовая семья. Традиционная правовая семья. Религиозная правовая семья
68508. Фізичний рівень передачі інформації: цифрові канали передачі даних 372.5 KB
  Крім того до апаратною складовою комп’ютерної мережі відносяться кабельні системи ліній зв’язку та комунікаційне обладнання що дозволяє об’єднувати окремі сегменти мережі і організовувати інформаційні потоки. Структурована кабельна система Кабельна система є базою для будьякої мережі.
68509. ФІЛОСОФІЯ, ЇЇ ПРЕДМЕТ ТА ФУНКЦІЇ 176.5 KB
  Завдання для самостійної роботи: Доведіть чому кожна людина є філософом хоча й не завжди усвідомлює це Проаналізуйте хто ближче до істини у поясненні суттєвості світу матеріалісти чи ідеалісти Чим відрізняється релігія наука і філософія Проаналізуйте визначення філософії.
68510. ЭТИКА И ЭСТЕТИКА В КОНТЕКСТЕ КУЛЬТУРЫ 111.5 KB
  Каждой целостной исторической формации присущ свой тип культуры. В его развитии решающую роль отводят материальным факторам, связанным с доминирующим типом социально-экономических отношений. Культура — это, прежде всего характерный для членов данного общества образ мыслей и образ действий.
68511. ОСНОВНЫЕ КАТЕГОРИИ ЭТИКИ И ИХ РЕАЛИЗАЦИЯ В ДЕЯТЕЛЬНОСТИ ЮРИСТОВ 101.5 KB
  Например есть категория долга а есть и представление индивида о том что такое долг. Имея много общего с категориями других наук этические категории обладают и некоторыми особенными чертами выполняющими социальные функции Во-первых они отражают ту сторону общественных отношений которая связана...
68512. МОРАЛЬ И ПОЛИТИКА 242.5 KB
  Осознание человека личностью членом группы противопоставления морали одного морали другого еще не происходит. Но вместе с тем она сосредотачивает энергию не на человеке его внутреннем мире и мотивах а на внешних для человека целях способствует раздвоению личности насаждает ложь терпимость...
68513. Предмет философии. Философия и мировоззрение 136.5 KB
  Чтобы подойти к пониманию того что такое философия необходимо отталкиваться от отличий человека как особого типа живых существ. Назовем еще одно отличие человека. Сознание есть способность человека отличать самого себя от окружающего мира и от самого себя как части окружающего мира.