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.


 

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

19488. Основні характеристики шини 16.34 KB
  Основні характеристики шини Розрядність шини визначається числом паралельних провідників що входять в неї. Перша шина ISA для IBM PC була восьмирозрядний тобто по ній можна було одночасно передавати 8 біт. Системні шини сучасних ПК наприклад Pentium IV 64розрядні. Пропус...
19489. Создание окного приложения 18.61 KB
  Создание окного приложения Первым шагом в разработке приложения C Builder является создание проекта. Файлы проекта содержат сгенерированный автоматически исходный текст который становится частью приложения когда оно скомпилировано и подготовлено к выполнению. Чтобы с
19491. ОСНОВНЫЕ ПОНЯТИЯ ПРОЦЕССОВ ПРОЕКТИРОВАНИЯ 26 KB
  ОСНОВНЫЕ ПОНЯТИЯ ПРОЦЕССОВ ПРОЕКТИРОВАНИЯ Процесс создания описания нового объекта может выполняться различными способами. Если весь процесс проектирования осуществляет человек то проектирование называют неавтоматизированным. В настоящее время неавтома
19492. Распределенная система управления 29.5 KB
  Распределенная система управления А. Развитая сетевая структура. наличие всех трех уровней сетей информационная системная полевая с имеющимися вариантами сетей отдельных уровней; использование мощных системных сетей позволяющих подсоединять к одной шине сот...
19493. Требования к надёжности системы управления 45.5 KB
  Требования к надёжности Уровень надежности АС в существенной степени зависит от следующих основных факторов: Состав и уровень надежности используемых технических средств их взаимодействие и взаимосвязь в структуре Комплекса Технических Средств АС. Состав ...
19494. Интегрированная система автоматизации предприятия 45 KB
  Интегрированная система автоматизации предприятия В современном промышленном производстве все большее значение приобретает возможность оперативного доступа к достоверной и точной информации из любой точки управления производством поскольку это определяющим обр...
19495. Классы микропроцессорных комплексов 49 KB
  Классы микропроцессорных комплексов 1. Контроллер на базе персонального компьютера PC based control. Это направление существенно развилось в последнее время ввиду повышения надежности работы персональных компьютеров; наличия их модификаций в обычном и промышлен...
19496. АРХІТЕКТУРА СУЧАСНИХ ПЕРСОНАЛЬНИХ КОМП’ЮТЕРІВ 80.5 KB
  Персональний комп’ютер – це складна обчислювальна система, яка являє собою сукупність апаратних (основні технічні пристрої) та програмних (сукупність програмних засобів для обробки інформації) засобів, що дають змогу накопичувати і автоматизувати обробку будь-якої інформації.