Динамический массив структур

Рассмотрим пример решения практической задачи с использованием динамического массива структур. Задача формулируется следующим образом. Есть набор текстовых файлов с дискретными целыми значениями Х и вещественными значениями Y для каждого Х. Необходимо просмотреть любое количество файлов и построить график результатов, в котором для каждой точки Х вывести среднее арифметическое значение Y по всем просмотренным файлам. В качестве десятичного разделителя при записи вещественного значения используется точка.

Разместим на форме 3 кнопки: кнопка Input – «Ввод файлов», Show – «График результатов», Clear – «Очистка»; компонент Tchart – для визуализации результатов работы программы; компонент Tlabel – для того, чтобы вывести число уникальных значений X (число точек графика); компонент TopenDialog для выбора файла. Вид интерфейса программы показан на рис. 4.

Рис. 4. Вид программы для расчета среднего значения

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

1. Объявим структуру для хранения значения Х, суммы всех Y для этого Х и количество точек, у которых было найдено это значение Х.

point = record

X:integer; Y:double; Count:Cardinal;

end;

2. Объявим глобально динамический массив типа описанной выше структуры и переменную для хранения количества точек с уникальным значением Х.

var

Form1: TForm1;

Mas: array of Point;

TotalPoints:integer;

3. Разработаем процедуру обработки события – нажатие кнопки «Очистка».

procedure TForm1.ClearClick(Sender: TObject);

begin

TotalPoints:=0;

Label1.Caption:='Количество точек = 0';

Chart1.Series[0].Clear;

If Assigned(Mas) then SetLength(Mas,0);

end;

В этой процедуре обнуляем переменную для хранения количества точек, чистим график и проверяем, если память под динамический массив распределена, то ее освобождаем. Последняя проверка нужна обязательно. Если пользователь начнет работу с программой с того, что нажмет на кнопку «Очистка», то без такой проверки попытка освободить нераспределенную память приведет к возникновению ИС – ошибки адресации.

4. Обработчик события «Создание формы».

procedure TForm1.FormCreate(Sender: TObject);

begin

ClearClick(Nil);// вызов процедуры очистки как метода формы

end;

5. Обработчик события «Закрытие формы».

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

If Assigned(Mas) then SetLength(Mas,0);

end;

Освобождаем память, предварительно убедившись, что она была распределена под массив.

6. Обработчик события – нажатие кнопки «Ввод файлов».

procedure TForm1.InputClick(Sender: TObject);

var F:TextFile; i,x:integer; y:double; flag:boolean;

begin

if not OpenDialog1.Execute then exit; // отмена выбора файла

AssignFile(F,OpenDialog1.FileName); // связывание файла с //файловой переменной

reset(F); // открытие текстового файла для чтения

while not EOF(F) do // цикл пока не закончится файл

begin

Read(F, x); Readln(F, y); // чтение Х и Y с дес. разд. точка

if(TotalPoints=0) then // если точек еще нет

begin

SetLength(Mas,TotalPoints+1);// первая точка,распределить //память под один элемент

Mas[0].x:=x; // занести считанное из файла х

Mas[0]. y:=y; // занести считанное из файла y

Mas[0].count:=1; // с этим х – одна точка

inc(TotalPoints); // инкременировать счетчик точек

end else // какие-то точки уже есть

begin

flag:=false;

for i:=0 to High(Mas) Do // цикл по всему массиву точек

if Mas[i].x = x then // есть уже точка с таким х

begin

Mas[i].y:=Mas[i].y + y; //добавить y в сумму всех y

inc(Mas[i].Count); // увеличить счетчик точек с этим х

flag:=true; // перебросить флаг – точка была найдена

end;

if flag=false then // новая точка, такого х в массиве нет

begin

SetLength(Mas,TotalPoints+1);//запросить память еще под //один элемент массива

Mas[TotalPoints].x:=x; //занести x

Mas[TotalPoints].y:=y; //занести y

Mas[TotalPoints].count:=1; //такая точка пока одна

inc(TotalPoints); // инкременировать счетчик точек

end;

end;

end;

CloseFile(F); // закрыть текстовый файл

end;

Некоторые фрагменты кода процедуры InputClick следует объяснить. Первый оператор SetLength(Mas,TotalPoints+1), который исполняется в случае, когда TotalPoints=0, динамически запрашивает выделение 20 байтов памяти под структуру point. Оператор SetLength(Mas,TotalPoints+1) выполняется, когда массив уже существует и прочитано из файла новое уникальное значение Х. В этом случае программа просит «довыделить» еще 20 байтов памяти под размещение новых данных. Компилятор поступает следующим образом: выделяется новый непрерывный кусок памяти, увеличенный по сравнению с прежним на 20 байтов, данные из предыдущего размещения переписываются в отведенную новую память, после чего память предыдущего размещения массива освобождается. Таким образом, при работе с динамическими массивами следует помнить, что под него выделяется непрерывный блок памяти. Несколько иначе осуществляется работа с двумерными динамическими массивами. Они реализуются как массивы указателей на массивы. Например, вызов SetLength(A, 2, 4) создает три массива: A – массив указателей размерностью 2 на блоки памяти, выделенные под массивы A[0] и A[1] соответственно и A[0], A[1] – два массива размерностью по 4 для размещения данных. ПодA[0] и A[1] выделяются два непрерывных блока памяти. Такая организация позволяет создавать непрямоугольные массивы.

7. Обработчик события – нажатие кнопки «График результатов».

procedure TForm1.ShowClick(Sender: TObject);

var i:integer;

begin

Chart1.Series[0].Clear;

if not Assigned(Mas) then exit;

for i:=0 to High(Mas) do //цикл по всему динамич. массиву

Chart1.Series[0].AddXY(i,Mas[i].y/Mas[i].Count);

Label1.Caption:= 'Количество точек = '+ IntToStr(High(Mas)+1);

end;

3.4.2. Двухсвязный список

Решим предыдущую задачу с использованием «разреженного массива», реализованного в виде двухсвязного списка.

Здесь следует рассматривать «разреженный массив» как название определенного способа хранения информации в памяти, а не как языковую конструкцию Delphi. Двухсвязный список может быть реализован в виде стуктуры, которая в своем составе помимо переменных имеет два указателя: на предыдущий элемент и на следующий (рис. 5). Наличие указателей на предыдущий и следующий элементы позволяет просматривать весь информационный массив (список) в двух направлениях. Каждый элемент списка произвольно расположен в памяти, которая выделяется ему при создании.

Рис. 5. Структура двухсвязного списка

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

Структура, реализующая двухсвязный список:

type CellPointer = ^cell;

cell = record

index: double; // уникальное значение Х

value: double; //сумма Y значений для Х

count: integer; //количество точек со значением Х

next: CellPointer; //указатель на следующий элемент

prev: CellPointer; //указатель на предыдущий элемент

end;

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

type

TLinkedList = class(TObject)

First, Last: CellPointer; //указатели на первый и последний

//элементы списка

constructor TLinkedList;

function Store(info: CellPointer): CellPointer;

end;

Конструктор класса TlinkedList:

constructor TLinkedList.TLinkedList;

begin

new(First);

new(Last);

end;

Метод Store класса TLinkedList для проверки Х и сохранения информации реализован в виде функции:

function TLinkedList.Store(info: CellPointer): CellPointer;

var old, top: CellPointer;

iter: CellPointer;

begin

old:= nil;

done:= false;

new(iter);

if First = nil then begin //первый элемент списка

info^.next:= nil;

new(Last);

new(First);

First^.index:= info^.index;

First^.value:= info^.value;

First^.count:= 1;

First^.next:= nil;

First^.prev:= nil;

Store:= info;

end

else begin //First <> nil

if First^.next = nil then begin

if First^.index = info^.index then begin //при //совпадении элемент не добавляется, а изменяется

First^.count:= First^.count + 1;

First^.value:= First^.value + info^.value;

end

else begin //вставка нового

First^.next:= info;

info^.prev:= First;

info^.next:= nil;

Store:= info;

end;

end //First^.next = nil

else begin

iter^.index:= First^.index;

iter^.value:= First^.value;

iter^.count:= First^.count;

iter^.next:= First^.next;

iter^.prev:= First^.prev;

while(iter<>nil) do begin

if iter^.index = info^.index then begin

iter^.count:= iter^.count + 1;

iter^.value:= info^.value + iter^.value;

Store:= info;

break;

end;

if iter^.next=nil then begin

iter^.next:= info;

info^.prev:= iter;

info^.next:= nil;

Store:= info;

break;

end;

iter:= iter^.next;

end;//while

end; //else of First^.next = nil

end; //else of start <> nil

end; //function Store

Функция проверяет наличие в списке элемента со значением index = Х. Если элемент присутствует, изменяются его параметры. Если элемент с таким индексом отсутствует, под него выделяется память и он добавляется в конец списка. Функция возвращает указатель на элемент списка.

Заполнение структуры cell и вызов метода Store класса TLinkedList:

LList: TLinkedList; // объявление глобальной переменной

tempL: CellPointer;

... // часть кода, отвечающая за чтение из текстового файла

new(tempL); //создание и формирование структуры

tempL^.index:= Х; // индекс (Х)

tempL^.value:= Y; // значение Y

tempL^.count:= 1; // количество точек с индексом Х

tempL^.next:= nil; // указатель на следующий элемент

tempL^.prev:= nil; // указатель на предыдущий элемент

LList.Store(tempL); // сохранение элемента в памяти

Обращение к сформированному списку для добавления значений точки на график:

var start: CellPointer;

new(start);

start:= LList.First; //получение указателя на первый элемент

while start<>nil do begin //перебор всех элементов

Chart1.SeriesList[0].AddXY(start^.index, start^.value/start^.count);

if start.next <> nil then

start:= start.next

else break;

end;