Все о динамических структурах данных. |
Все о динамических структурах данных. |
Altair |
4.10.2004 6:07
Сообщение
#1
|
Ищущий истину Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Содержание:
-------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Altair |
5.10.2004 10:56
Сообщение
#2
|
Ищущий истину Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: 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 килобайт ) Кол-во скачиваний: 2689 -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Текстовая версия | 9.06.2024 3:17 |