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.


 

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

71273. Системы управления автоматизированным технологическим оборудованием. История развития вычислительной техники 1.15 MB
  Период становления отечественной электронной вычислительной техники занимает промежуток времени с момента появления в 1946 г. первой ЭВМ ЭНИАК и до 1955 г. Начиная с 1955 г. каждые последующие пять лет в вычислительной технике обновлялись конструктивно-технологические...
71274. Накопители 499.5 KB
  Магазинные загрузочные устройства МЗУ комплекс функциональных механизмов предназначенных для приемки в ориентированном положении изделий хранения с расположением их в один ряд и автоматической выдачи изделий в рабочую зону технологических машин или в зону захвата...
71275. Токарные автоматы и полуавтоматы 1.77 MB
  Токарные автоматы и полуавтоматы предназначены для изготовления деталей с использованием нескольких инструментов в крупносерийном и массовом производстве. Автомат - станок, автоматически и многократно выполняющий все рабочие и вспомогательные элементы цикла обработки детали, кроме наладки.
71277. Понятие «способности». Структура и виды способностей 2.29 MB
  Структура и виды способностей Проблема способностей всегда волновала умы и с теоретической и с практической стороны. Встречая проявления ярких способностей мы удивляемся и восхищаемся ими. Почти каждому хочется узнать потенциал своих способностей.
71278. Обработка сталей и чугунов резанием 169 KB
  Пластичные сплавы обрабатываются труднее чем менее пластичные сплавы обладающие большей теплопроводностью и теплоемкостью легче так как температура резания при обработке этих сплавов ниже. Алюминиевые сплавы.
71279. Понятие о темпераменте. Физиологические основы темперамента 167.02 KB
  Темперамент выступает в качестве общей основы многих личностных характеристик человека и прежде всего характера. Физиологические основы характера В психологии понятие характер греч. Понятие характера весьма различается в теоретических построениях отдельных авторов.