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.


 

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

28553. Примеры современных шифров проблема последнего блока DES 26.44 KB
  Альтернативой DES можно считать тройной DES IDEA а также алгоритм Rijndael принятый в качестве нового стандарта на алгоритмы симметричного шифрования. Также без ответа пока остается вопрос возможен ли криптоанализ с использованием существующих характеристик алгоритма DES. Алгоритм тройной DES В настоящее время основным недостатком DES считается маленькая длина ключа поэтому уже давно начали разрабатываться различные альтернативы этому алгоритму шифрования.
28554. Распределение ключей. Использование базовых ключей 13.15 KB
  Он заключается в доставке абоненту сети связи не полного комплекта ключей для связи со всеми другими абонентами а некоторой универсальной заготовки уникальной для каждого абонента по которой он может вычислить необходимый ему ключ. Пусть в сети связи действуют N абонентов занумеруем их от 0 до N1 и поставим каждому абоненту уникальный открытый идентификатор Yi из некоторого множества Y открытый в смысле общеизвестный. Генерация ключей для абонентов сети связи заключается в выработке N секретных ключей Xi из некоторого множества X....
28555. Использование маркантов или производных ключей 15.1 KB
  Заключается в использовании для шифрования не непосредственно ключей хранимых у абонентов а некоторых производных ключей из них получаемых. Заключается в использовании вместо ключа K двоичного вектора S полученного побитным суммированием K и случайного двоичного вектора M называемого маркантом при этом маркант передается в открытом виде отправителем получателю. Действительно использование одного и того же ключа но разных маркантов не снижает стойкости шифра. Однако этот метод обладает одним недостатком восстановление одного...
28557. Несимметричные системы шифрования и их построение 23.7 KB
  Эти системы характеризуются тем что для шифрования и для расшифрования используются разные ключи связанные между собой некоторой зависимостью. Один из ключей например ключ шифрования может быть сделан общедоступным и в этом случае проблема получения общего секретного ключа для связи отпадает. Поскольку в большинстве случаев один ключ из пары делается общедоступным такие системы получили также название криптосистем с открытым ключом. Первый ключ не является секретным и может быть опубликован для использования всеми пользователями...
28558. Новое направление в криптографии, постулаты У. Диффи и М. Хеллмана 23.14 KB
  Это означает что если А является примитивным корнем простого числа Q тогда числа A mod Q A2 mod AQ1 mod Q являются различными и состоят из целых от 1 до Q – 1 с некоторыми перестановками. В этом случае для любого целого B Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х такую что Y =AX mod Q где 0≤ X ≤ Q1. Экспонента X называется дискретным логарифмом или индексом Y по основанию A mod Q. Общеизвестные элементы Q Простое число A A Q и A является примитивным корнем Q Создание...
28559. Описание системы с открытыми ключами 14.42 KB
  Альтернативным вариантом может быть обработка регистрации системой имеющей древовидную структуру: ЦО выдает сертификаты местным представителям которые в дальнейшем действуют в качестве посредников в процессе регистрации пользователя на более низких уровнях иерархии. Сертификаты могут распространяться ЦО пользователями или использоваться в иерархической системе. Поэтому если сертификаты хранятся у пользователей а не выдаются каждый раз ЦО при их использовании ЦО должен время от времени публиковать списки аннулированных сертификатов....
28560. Электро́нная по́дпись (ЭП) 17.3 KB
  Кроме этого использование электронной подписи позволяет осуществить: Контроль целостности передаваемого документа: при любом случайном или преднамеренном изменении документа подпись станет недействительной потому что вычислена она на основании исходного состояния документа и соответствует лишь ему. Защиту от изменений подделки документа: гарантия выявления подделки при контроле целостности делает подделывание нецелесообразным в большинстве случаев. Доказательное подтверждение авторства документа: Так как создать корректную подпись...
28561. Открытое шифрование и электронная подпись 14.08 KB
  Пользователь А вырабатывает цифровую подпись предназначенного для пользователя В сообщения М с помощью следующего преобразования: SIGm=EebnbEdanaM При этом он использует: свое секретное преобразование; открытое преобразование Eebnb пользователя В. Edana Затем он передает пользователю В пару{MSIGM}. Пользователь В может верифицировать это подписанное сообщение сначала при помощи своего секретного преобразованияс целью получения Edbnb EdanaM=EdbnbSIGM=EdbnbEebnbEdanaM и затем открытого Eeana пользователя А для...