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.


 

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

1336. Международный маркетинг 1.22 MB
  Сущность международного маркетинга. Сущность и особенности международного маркетинга. Предпосылки возникновения международного маркетинга. Маркетинговые исследования международных рынков. Формы и методы выхода на международный рынок.
1337. Математический аппарат для инвестора 1.41 MB
  Методика статистического анализа прогнозирования, дескрептивная статистика, анализ временных рядов, оценка автокорреляционных свойств, адаптивные методы прогнозирования.
1338. Экономико-правовые основы рынка ПО 1.61 MB
  Программы, программные средства и информационные технологии как продукты на рынке информационных услуг. Продвижение на рынок: формирование стоимости и ценовая политика, формы продажи, реклама, презентации, скидки, сопровождение. Политика и опыт ведущих производителей в области информационных технологий. Программы и информационные технологии как формы интеллектуальной собственности.
1339. Методические указания к выполнению расчетов на производстве 230 KB
  Методические указания по выполнению расчетов показателей эффективности использования основных. Методические указания по выполнению расчетов затрат на производство. Методические указания по выполнению расчетов прибыли и рентабельности.
1340. Анализ следящей системы автоматического регулирования на постоянном токе 271 KB
  Проверка устойчивости системы. Определение области устойчивости по коэффициенту усиления разомкнутой системы. Точность системы в установившемся режиме. Зависимость точности системы от коэффициента передачи. Построение переходных процессов и определение показателей качества.
1341. Экономический анализ фирмы Престиж 436.5 KB
  Отклонение в стоимости материалов. Предполагаемый пробег автомобиля. Повышающий коэффициент для расчета амортизации. Предполагаемое количество продукции, выпущенной с использованной технологии раздвижения дверей. Пособие по временной нетрудоспособности.
1342. Разработка корпоративной мультисервисной сети передачи данных филиала компании ООО Скартел 521.5 KB
  Обоснование необходимости создания мультисервисной корпоративной сети. Проектирование мультисервисной корпоративной сети. Расчет характеристик пропускной способности мультисервисных пакетных сетей при реализации метода инжиниринга трафика. Обоснование выбора оборудования на основе метода расстановки приоритетов. Расчет срока окупаемости проекта.
1343. Дослідження страхів у дітей старшого дошкільного віку 441.5 KB
  Емпіричне вивчення проблеми страху у дітей дошкільного віку. Загальнi уявлення про природу страху. Огляд використаних діагностичних методик при вивченні страху у дітей старшого дошкільного віку. Психолого-педагогічні рекомендації щодо позбавлення дитини від почуття страху.
1344. Вопросы и ответы к госэкзамену для механиков 361 KB
  Система ремонта автомобиля. Мойка и очистка деталей перед ремонтом. Восстановление деталей методами ремонтных размеров и дополнительной ремонтной детали. Технологический процесс нанесения лакокрасочных покрытий. Сборка резьбовых, прессовых соединений, зубчатых передач, соединений с подшипниками качения. Восстановление размеров изношенных поверхностей деталей методом пластической деформации.