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.


 

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

72404. Работа с макросами в CORELDRAW. Формирование календаря 2.16 MB
  Задание. Создайте изображение настенного календаря для вывода на печать. Создайте новый документ Файл - Новый (File - New). В меню Средства (Инструменты) - Visual Basiс - выбрать Воспроизвести (Tools - Visual Basiс - Play):...
72405. CorelDraw. Работа с растровыми объектами. Завернутый уголок 1.39 MB
  Существует растровый фильтр Page Curl (Завернутый угол страницы): Bitmaps > 3D Effects > Page Curl (Точечная графика > Трехмерные эффекты > Завернутый угол страницы). Где вы сможете выбрать место сворачивания уголка (слева, справа, снизу, сверху), направление...
72406. Повышение эффективности работы гальванической линии завода «ВЗЭП» г. Витебск 1.51 MB
  Обзор современных решений программ автоматического управления автооператорами гальванической линии; систематизация собранного материала для выполнения дипломного проекта, выбор физической среды реализации; изучение существующего программного обеспечения для проектирования выбранной системы; построение алгоритма управляющей программы. Определение протокола связи с модулями автооператоров, построение диаграммы состояний, вариантов использования...
72407. Форматирование таблицы, работа с формулами 1.08 MB
  Цель работы: ознакомиться со способами форматирования данных внутри ячеек, видами выравнивания и ориентации текста, прорисовки границ и выделения цветом. Изучить различные виды адресации ячеек, правила написания формул, работу Мастера функций и назначение кнопочек ленточной вкладки Формула.
72408. Работа с текстовыми данными 180.5 KB
  Цель работы: изучить основные сведения по работе с текстовыми данными, научиться обрабатывать текст. Уметь связывать данные в разных таблицах, освоить работу логических функций. Изучить пользовательские форматы данных. Научиться использовать средство Условное форматирование для выделения диапазона данных.
72409. Работа с датами и временем 116.5 KB
  Цель работы: Изучить правила организации и хранения даты и времени в EXCEL. Изучить функции для работы с датами и временем. Научиться работать с текущей датой и временем. Освоить способы связывания данных в таблицах при помощи функций...
72410. ОПРЕДЕЛЕНИЕ СРЕДНЕЙ ДЛИНЫ СВОБОДНОГО ПРОБЕГА И ЭФФЕКТИВНОГО ДИАМЕТРА МОЛЕКУЛЫ ГАЗА 165 KB
  Согласно молекулярно-кинетической теории газа хаотическое молекулярное движение является физической причиной наблюдаемых в газах явлений переноса энергии - при выравнивании температур (теплопроводность), массы - при выравнивании концентраций...
72411. Регулювання рульового механізму 131.5 KB
  Регулювання рульового механізму залежить від його конструкції. На автомобілях ГАЗ – 53 використовується передача типу глобоідальний черв’як – трьохгребневий ролик, а на автомобілях ЗИЛ – 431410 та КамАЗ – передача типу сектор та рейка – поршень.
72412. ЛОГИСТИКА СНАБЖЕНИЯ 158.5 KB
  Идея концепции синхронизация процессов доставки МР и ГП в необходимых количествах точно к тому моменту когда звенья логистической цепи в них нуждаются для выполнения заказа заданного подразделением-потребителем. Математические модели управления запасами УЗ позволяют найти оптимальный уровень запасов...