Для хранения списка указателей на размещенные в адресном пространстве структуры (объекты, динамические массивы, переменные) предназначен класс TList. Так же, как и список строк TstringList, список указателей обеспечивает эффективную работу с элементами списка.

Класс TList

Основой класса TList является список указателей. Сам список представляет собой динамический массив указателей, к которому можно обратиться через индексированное свойство
property Items: Pointer;
Нумерация элементов начинается с нуля.
Прямой доступ к элементам массива возможен через свойство
type
PPointerList = ^TPointerList;
TPointerList = array of Pointer;
property List: PPointerList;
которое имеет атрибут "только для чтения".
Так как элементы списка являются указателями на некоторые структуры, прямое обращение к составным частям этих структур через свойство items невозможно. Как это можно сделать, рассказывается ниже в примере.

Примечание

В списке могут содержаться указатели на разнородные структуры. Не обязательно хранить в списке только указатели на объекты или указатели на записи.
Реализованные в классе TList операции со списком обеспечивают потребности разработчика и совпадают с операциями списка строк.
Для добавления в конец списка нового указателя используется метод
function Add(Item: Pointer): Integer;
Прямое присваивание значения элементу, который еще не создан при помощи метода Add, вызовет ошибку времени выполнения.
Новый указатель можно добавить в нужное место списка. Для этого используется метод
procedure Insert(Index: Integer; Item: Pointer);
В параметре index указывается необходимый порядковый номер в списке.
Перенос существующего элемента на новое места осуществляется методом
procedure Move(Curlndex, Newlndex: Integer);
Параметр CurIndex определяет старое положение указателя. Параметр NewIndex задает новое его положение.
Также можно поменять местами два элемента, определяемые параметрами Indexl и Index2:
procedure Exchange(Indexl, Index2: Integer);
Для удаления указателей из списка используются два метода. Если известен индекс, применяется метод
procedure Delete(Index: Integer);
Если известен сам указатель, используется метод
function Remove(Item: Pointer): Integer;
Эти методы не уменьшают объем памяти, выделенной под список. При необходимости сделать это следует использовать свойство capacity. Также существует метод Expand, который увеличивает отведенную память автоматически в зависимости от текущего размера списка.
function Expand: TList;
Для того чтобы метод сработал, необходимо, чтобы count = Capacity.
Метод
procedure Clear; dynamic;
используется для удаления всех элементов списка сразу. Для поиска указателя по его значению используется метод
function IndexOf(Item: Pointer): Integer;
Метод возвращает индекс найденного элемента в списке. При неудачном поиске возвращается - 1.
Для сортировки элементов списка применяется метод

procedure Sort(Compare: TListSortCompare);
Так как состав структуры, на которую указывает элемент списка, невозможно заранее обобщить, разработка процедуры, осуществляющей сортировку, возлагается на программиста. Метод Sort лишь обеспечивает попарное сравнение указателей на основе созданного программистом алгоритма (пример сортировки см. выше в разд. "Класс TStringList").
Полностью все свойства и методы класса TList представлены в табл. 7.2.
Таблица 7.2. Свойства и методы класса TList
Объявление

Описание
property Capacity: Integer;
Определяет число строк, для которых выделена память
property Count: Integer;
Возвращает число строк в списке
property Items : Pointer;
Список указателей
type
TPointerList = array of Pointer;
PPointerList = ATPointerList; property List: PPointerList;
Динамический массив указателей
function Add (Item: Pointer): Integer;
Добавляет к списку новый указатель
procedure Clear; dynamic;
Полностью очищает список
procedure Delete (Index: Integer:;
Удаляет указатель с индексом
Index
class procedure Error (const Ksg: string; Data: Integer); virtual;
Генерирует исключительную
Ситуацию EListError.
Сообщение об ошибке создается из форматирующей строки Msg и числового параметра Data
procedure Exchange (Indexl, Index2: Integer);
Меняет местами указатели с индексами Indexl и Index2
function Expand: TList;
Увеличивает размер памяти, отведенной под список
function First: Pointer;
Возвращает первый указатель из списка
function IndexOf (Item: Pointer): Integer;
Возвращает индекс указателя, заданного параметром Item
procedure Insert (Index: Integer; Item: Pointer) ;
Вставляет новый элемент Items позицию Index
function Last: Pointer;
Возвращает последний указатель в списке
procedure Move (Curlndex, Newlndex: Integer);
Перемещает элемент списка на новое место
procedure Pack;
Удаляет из списка все пустые (Nil) указатели
function Remove (Item: Pointer): Integer;
Удаляет из списка указатель
Item
type TListSortCompare = function (Iteml, Item2: Pointer): Integer;
procedure Sort (Compare: TListSortCompare);
Сортирует элементы списка

Пример использования списка указателей

Рассмотрим использование списков указателей на примере приложения DemoList. При щелчке мышью на форме приложения отображается точка, которой присваивается порядковый номер. Одновременно координаты и номер точки записываются в соответствующие свойства создаваемого экземпляра класса TMypixel. Указатель на этот объект передается в новый элемент списка pixList.
В результате после очистки формы всю последовательность точек можно восстановить, использовав указатели на объекты точек из списка.
Список точек можно отсортировать по координате X в порядке возрастания.

Листинг. Модуль главной формы проекта DemoList

Unit Main;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Buttons;
type
TMainForm = class(TForm)
ListBtn: TBitBtn;
ClearBtn: TBitBtn;
DelBtn: TBitBtn;
SortBtn: TBitBtn;
procedure FormCreate(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure FormMouseDown(Sender: TObject; Button: TMouseButton;

procedure ListBtnClick(Sender: TObject);
procedure ClearBtnClick(Sender: TObject);
procedure DelBtnClick(Sender: TObject);
procedure SortBtnClick(Sender: TObject);
private
PixList: TList;
PixNum: Integer; public
{ Public declarations }
end;
TMyPixel = class(TObject)
FX: Integer;
FY: Integer;
FText: Integer;
constructor Create(X, Y, Num: Integer);
procedure SetPixel;
end;
var
MainForm: TMainForm;
implementation
{$R *.DFM}
const PixColor = clRed;
var CurPixel: TMyPixel;
constructor TMyPixel.Create(X, Y, Num: Integer);
begin
inherited Create;
FX:= X;
FY:= Y;
FText:= Num;
SetPixel;
end;
procedure TMyPixel.SetPixel;
begin
MainForm.Canvas.PolyLine();
MainForm.Canvas.TextOut(FX +1, FY + 1, IntToStr(FText));
end;
function PixCompare(Iteml, Item2: Pointer): Integer;
var Pixl, Pix2: TMyPixel;
begin
Pixl:= Iteml;
Pix2:= Item2;
Result:= Pixl.FX - Pix2.FX;
end;
procedure TMainForm.FormCreate(Sender: TObject);
begin
PixList:= TList.Create;
PixNum:= 1; {Счетчик точек}
Canvas.Pen.Color:= PixColor; (Цвет точки}
Canvas.Pen.Width:= 3; {Размер точки}
Canvas.Brush.Color:= Color; (Цвет фона текста равен цвету формы}
end;
procedure TMainForm.FormClose(Sender: TObject; var Action: TCloseAction);
begin
PixList.Free;
end;
procedure TMainForm.FormMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
PixList.Add(TMyPixel.Create(X, Y, PixNum));
Inc(PixNum);
end;
procedure TMainForm.ListBtnClick(Sender: TObject);
var i: Integer;
begin
with PixList do
for i:= 0 to Count - 1 do
begin
CurPixel:= Items[i]; CurPixel.SetPixel;
end; end;
procedure TMainForm.ClearBtnClick(Sender: TObject);
begin
Canvas.FillRect(Rect(0, 0, Width, Height));
end;
procedure TMainForm.DelBtnClick(Sender: TObject);
begin
PixList.Clear;
PixNum:= 1;
end;
procedure TMainForm.SortBtnClick(Sender: TObject);
var i: Integer;
begin
PixList.Sort(PixCompare);
with PixList do
for i:= 0 to Count - 1 do TMyPixel(Items[i]).FText:= i + 1;
end;
end.
Класс TMyPixel обеспечивает хранение координат точки и ее порядковый номер в серии. Эти параметры передаются в конструктор класса. Метод setPixel обеспечивает отрисовку точки на канве формы.
Экземпляр класса создается для каждой новой точки при щелчке кнопкой мыши в методе-обработчике FormMouseDown. Здесь же указатель на новый объект сохраняется в создаваемом при помощи метода Add элементе списка PixList. Таким образом, программа "запоминает" расположение и порядок следования точек.
Метод-обработчик ListBtnClick обеспечивает отображение точек. Для этого в цикле текущий указатель списка передается в переменную объектного типа curPixel, т. е. в этой переменной по очереди "побывают" все созданные объекты, указатели на которые хранятся в списке.
Это сделано для того, чтобы получить доступ к свойствам объектов (непосредственно через указатель этого сделать нельзя). Второй способ приведения типа рассмотрен в методе-обработчике SortBtnClick.
Перед вторичным отображением точек необходимо очистить поверхность формы. Эту операцию выполняет метод-обработчик clearBtnClick.
Список точек можно отсортировать по координате X в порядке возрастания. Для этого в методе-обработчике SortBtnClick вызывается метод Sort списка PixList. В параметре метода (переменная процедурного типа) передается функция PixCompare, которая обеспечивает инкапсулированный в методе Sort механизм перебора элементов списка алгоритмом принятия решения о старшинстве двух соседних элементов.
Если функция возвращает положительное число, то элемент item1 больше элемента item2. Если результат отрицательный, то item1 меньше, чем item2. Если элементы равны, функция должна возвращать ноль.
В нашем случае сравнивались координаты X двух точек. В результате такой сортировки по возрастанию объекты оказались расположены так, что первый элемент списка указывает на объект с минимальной координатой X, а последний - на объект с максимальной координатой X.
После сортировки осталось заново пронумеровать все точки. Это делает цикл в методе-обработчике SortBtnclick. Обратите внимание на примененный в этом случае способ приведения типа, обеспечивающий обращение к свойствам экземпляров класса TMypixel.
Метод-обработчик DeiBtnClick обеспечивает полную очистку списка pixList.

Введение

1. Определение АТД

2. Общие положения

3. Описание операций

3.1 Операция добавления элемента

3.2 Операция добавления элемента после указанного

3.3 Операция удаления указанного элемента

3.4 Операция распечатки записей списка

4. Реализация АТД-список

4.1 Главная функция

4.2 Интерфейс

4.3 Реализация методов

Заключение

Список литературы

Приложение A: граф-схемы алгоритмов

Введение

Независимо от типа решаемых задач, любая программа оперирует какими-то данными, а сама программа предстваляет собой методы управления и обработки этих данных. Скорость выполнения программой поставленной задачи зависит не только от алгоритмов, использованных в ней для обработки и управления данными, но также и от самой организации данных. Таким образом, мы приходим к понятию о структурах данных.

Прямое взаимодействие между программой через пользователя и структурами данных оставляет открытыми множество данных, модификация которых нелегитимным способом (минуя интерфейс) может привести к нежелательным последствиям. Чтоб миновать данную проблему необходимо "возвести стены" между данными и программой, оставив лишь "окошко" в виде интерфейса. Для этого необходимо определить абстрактные типы данных, с помощью которых эти стены воздвигаются.

В данной работе разрабатывается абстрактный тип данных (АТД) – список, который впоследствии реализуется в виде связного списка, реализованного при помощи косвенной адресации, основанной на указателях. Более подробно вопросы разработки АТД рассматриваются в .

1. Определение АТД

Абстракция данных описывает, что можно делать с набором данных, игнорируя вопрос "каким образом это делается?". Абстракция данных – это способ разрабатывать отдельные компоненты программы, независимо от остальной ее части (остальных компонентов). Таким образом, абстракция данных – естественное расширение функциональной абстракции, позволяющей разрабатывать функции в относительной изоляции друг от друга. Набор данных в сочетании с совокупностью операций над ними называется абстрактным типом данных. Описание операций, входящих в АТД, должно быть достаточно строгим, чтоб точно указать их воздействие на данные. Но в нем не должен указываться способ хранения данных или детали выполнения операций. Конкретный способ хранения данных (структура данных) выбирается только при реализации АТД. Структура данных – конструкция, определенная в языке программирования для хранения набора данных. Согласно варианту задания, определены следующие данные:

1. Наименование микросхемы

2. Стоимость

3. Количество

Над ними определены следующие операции:

1.Добавление элемента в неупорядоченный список

2.Удаление элемента с заданным полем из неупорядоченного списка

3.Добавление элемента после указанного

4.Удаление всех элементов с заданным полем

5.Распечатка списка

Данный набор определяет множество допустимых операций над опеределенными в задании данными, т.е. нам задан абстрактный тип данных.

2. Общие положения

Абстрактный список можно реализовать в виде массива – на первый взгляд, очевидный шаг. Массив имеет фиксированный размер (в большинстве языков программирования), в то время как длина абстрактного списка неограничена. Таким образом, структура данных становится статической, что является недостатком.

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

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

Каждый узел связанного списка состоит из двух частей: непосредственно данных и указателя на следующий элемент – такой же узел или константу NULL.

Поскольку, согласно принципу инкапсуляции, доступ к данным должен осуществляться только посредством методов, определенных для этой цели, для данных определен спецификатор доступа private.

Механизм выделения памяти под элементы списка, основанного на указателях, предполагает динамическое выделение памяти при помощи операторов new и delete. Таким образом, при создании нового элемента имеет смысл выделять память только лишь под новые данные, а не под уже определенные методы – операции списка. Следовательно, необходимо вынести методы из структуры данных. В данной работе, была применена методика расширения интерфейса созданием структуры методов – дружественного класса, методы которого имеют доступ к закрытым членам класса узла.

Подробней о принципах объектно-ориентированного программирования можно узнать из .

Указатели на голову и хвост списка объявлены в классе List поскольку по сути необходимы для реализации методов АТД, в то время как для самой структуры данных они не имеют ни малейшего смысла.

Методы, которые не должны никоим образом модифицировать данные, объявлены с использованием ключевого слова const.

водить все действия, что и с обычными переменными. Для работы с динамическим распределением памяти очень удобно использовать связанные структуры данных, например односвязные списки. Простейшим примером списка является массив, в котором последовательно расположены все его элементы. Но у такого представления есть существенный недостаток – требуется заранее точно указать количество элементов...

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

Данных будет нести больше смысла, если его отсортировать каким‑либо образом. Часто требуется сортировать данные несколькими различными способами. Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве. Наконец, сортировка...

Мощность (заменять процессоры), расширять емкость оперативной памяти, добавлять внешние устройства. Машины имеют большие наборы команд, развитое системное программное обеспечение, включающее трансляторы языков программирования Ассемблер, ФОРТРАН, ПЛ/1, КОБОЛ, АЛГОЛ, ПАСКАЛЬ, операционные системы с различными функциональными возможностями. Основная особенность управляющих вычислительных машин...

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

Объекты называются элементами списка. Элементом списка обычно является запись, которая содержит, по крайней мере, два поля (рис. 2.13):

Информационное;

Указатель.

Сам список представляется в виде рис. 2.14.

Каждый элемент списка имеет указатель на соседа. У последнего элемента указатель – Nil . Элементы списка и указатели описываются так:

Указатель = ^Эл_Списка; {Опережающее описание }

{допускается только в этом случае }

Эл_Списка = Record

Инф _ поле : Тип_Инф_поля;

Поле_указателя: Указатель ; {Этот тип уже определен выше}

Тип информационного элемента - любой (скалярный, строка, массив и т. д.).

Пример . Т ype

Ptr = ^El;

El = Record

Buk: Char;

Ukaz: Ptr;

tUk , PrUk , NUk ,q: Ptr; {Указатели на элемент списка}

ElSp : El ; { Элемент списка (запись типа El ) }

С помощью списков достаточно просто представляются очереди .

Очередь – это понятие, которое широко используется в вычислительной технике. Список позволяет моделировать операции добавления элементов в очередь и выборки из нее.

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

1) переход от одного элемента к другому (следующему);

2) включение нового элемента в список;

3) удаление элемента из списка.

1) Первая операция выполняется просто: значению переменной-указателю, которая сейчас указывает на некоторый элемент, необходимо присвоить значение, находящееся в поле указателя этого элемента (см. рис. 2.15):

tUk := tUk ^. Ukaz

ВрезультатеtUk станет ссылкой на следующий элемент или Nil , если элемент последний.

2) Удаление элемента из списка выполняется наиболее просто, если имеется ссылка (указатель) на элемент, предшествующий удаляемому . При этом сначала переносятся ссылки, а потом удаляется элемент (освобождается занимаемая им динамическая память). Ссылка на удаляемый элемент не должна теряться, пока он не будет уничтожен или включен в другой список, иначе из него получится "мусор".

Процесс удаления элемента, расположенного в списке после элемента, на который указывает ссылка PrUk , иллюстрируется рис. 2.16, а фрагмент соответствующей программы может иметь вид, приведенный далее.

{Запомним указатель на удаляемый элемент}

tUk:= PrUk^.Ukaz;

{Полю указателя элемента, стоящего перед удаляемым, присвоим}

{ значение поля указателя удаляемого элемента }

PrUk^.Ukaz:= PrUk^.Ukaz^.Ukaz;

На этом удаление элемента из списка закончено: связь этого элемента с предыдущим разорвана. Но элемент продолжает занимать память и для его физического удаления нужно выполнить процедуру:

Dispose (tUk); {Физически удалили элемент }

Если нет необходимости освобождать память, то иногда полезно записать в поле указателя удаленного элемента Nil :

tUk^.Ukaz:= Nil.

3)Включение в список элемента, на который имеется указатель N Uk , после элемента, на который имеется указатель PrUk , иллюстрирует рис. 2.17. Для выполнения этой операции нужно задать ссылку из вставляемого элемента на следующий (она равна ссылке из предыдущего элемента на следующий – см. рис. 2.17, а), а затем – изменить ссылку из предыдущего элемента на вставляемый (см. рис. 2.17, б). Существующая связь разрывается последней, чтобы не потерять элемент.

Фрагмент программы будет иметь вид

New(NUk); {Создали вставляемый элемент}

Readln(NUk^.Buk);