IPB
ЛогинПароль:

> Внимание! Действует предмодерация

Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.

> Все о динамических структурах данных.
сообщение
Сообщение #1


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Содержание:
Есть материал по теме? высылайте! ваша информация будет размещена здесь!


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Списки


Указатели являются простым механизмом, позволяющим строить данные со сложной и меняющейся структурой.
Используя указатели можно создавать и обрабатывать структуры данных, компоненты которых связаны явными ссылками.

Самый простой способ связать множество элементов - это расположить их линейно в списке. В этом случае каждый элемент содержит только один указатель на следующий элемент списка.

Пусть тип point описан следующим образом:
Код
Type
  point = ^item;
  item = record
    number: integer;
    next: point
  end;

Каждая переменная типа point состоит из двух компонентов: индентифицирующего номера и указателя на следующий элемент. Из этих переменных, связав их указателями, можно создать линейный список.

Способ построения линейного списка: начиная с пустого списка, последовательно добавлять элементы в его начало.

Процесс формирования списка из n элементов:
Код
  First: = nil; {начало с пустого списка}
  While n>0 do
    begin
      New(r);
      r^.Next:=first;
      r^.Number:=n;
      First:=r;
      n := n-1
    end;


Основные операции со списками

Просмотр списка
Процедура, которая выводит на экран значение поля number элементов списка.
Код
procedure Print (first: point);
Var r: point
Begin
  R: = first;
  While r<>nil do
    begin
      Writeln ('number = ' ,r^.Number);
      R:=r^.Next;
    end;


Поиск в списке
Очень частая операция - поиск в списке элементов с заданным значением ключевого поля X. Так же как в случае файлов, поиск ведется последовательно. Он заканчивается либо когда элемент найден, либо когда достигнут конец списка.
Код
Procedure Search (first: point; x: integer; var q: point);
{
  q - возвращает указатель на найденный элемент;
  q - nil, если элемента с ключем X в списке нет
}
var
  r: point;
  ok: boolean;
begin
  r: = first;
  ok: = true;
  while (r<>nil) and ok do
    if r^.Number=x then ok:=false else r:=r^.Next;
  q: = r
end;


Включить элемент в список
Элемент нужно включить в середину списка после элемента, на который указывает ссылка q. Процедура включения записывается следующим образом.
Код
{включить элемент в середину списка перед q^}
Procedure Insert (Var q: point; x: integer);
{ х - значение информационного поля включаемого элемента }
Var
  r: point;
Begin
  New (r); {размещаем элемент в памяти}
  R^.Number:=x;
  {меняем ссылку}
  r^.next:=q^.Next;
  q^.Next:=r;
end;


Если требуется включить перед элементом q^, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет “прохода” к элементам, предшествующим данному. Однако эту проблему можно решить, используя простой прием, который состоит в том, что новый элемент вставляется после q^, но затем происходит обмен значениями между новым элементом и q^.

Код
{включить элемент в середину списка перед q^}
Procedure insert_before (Var q: point; x: integer);
Var r: point;
Begin
  New(r); {размещаем элемент памяти}
  {включаем элемент после q^}
  r^.Next:=q^.Next;
  q^.Next:=r;
  {выполняем обмен значениями}
  r^.Number:=q^.Number;
  q^.Number:=x
end;


Удалить элемент из списка
Предположим, что надо удалить элемент, расположенный после элемента, на который указывает ссылка q.
Код
{удаление элемента из середины списка после q^}
Procedure Del (Var q: point);
Var r: point;
Begin
  r:=q^.Next;
  q^.Next:=q^.Next^.next;
  r^.Next:=nil
End;


Если следует удалить элемент на который указывается ссылка q, то следует в начале присвоить элементу q^ значение следующего за ним элемента, а затем этот элемент удалить.
Код
{удаление элемента q^}
Procedure Delete(Var q: point);
Var r: point;
Begin
  r:=q^.next;
  q^:=r^;
  r^.Next:=nil;
End;


Обратите внимание на то, что удаляемый из списка элемент остается в памяти и к нему имеется доступ к указателю r, так что в дальнейшем этот элемент можно вставить, например, в другой список. Если требуется освободить занимаемую этим элементом память, то следует выполнить:
Код
  { ... }
  Dispose(r);
  r:=nil;
  { ... }


В присоединенном файле содержится RAR архив с модулем для работы со списками и инструкцией по использованию. В нем описанным все здесь перечисленные операции и еще некоторые. Поддержка списков с заглавным элементом и без него.


Прикрепленные файлы
Прикрепленный файл  LIST.rar ( 2.52 килобайт ) Кол-во скачиваний: 2977


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:21
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name