Программа для создания двусвязных кольцевых списков

Содержание Введение

1. Состав проекта

1.1 Формы

1.2 Модули

2. Статические данные и структуры

3. Логическая структура данных

4. Логические схемы операций

5. Алгоритмы обработки основных структур

5.1 Добавление нового элемента

5.2 Удаление элемента

6. Руководство пользователя

Заключение

Список использованных источников Приложение

Введение

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

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

Связный список — структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

1. Состав Delphi проекта

1.1 Формы При запуске программы на экране появляется главная форма (Рисунок 1).

Рисунок 1 — Главная форма программы

1.2 Модули Программа представлена в виде трех модулей:

— UnitFourthPlex. pas

— UnitMainForm. pas

— UnitFuncs. pas

В модуле UnitFourthPlex. pas содержится класс TPlex, который позволяет работать с данными плекса. Он содержит 4 указателя на головы соответствующих списков и все необходимые методы для работы с плексом. Также в данном модуле описана запись TMember, которая представляет собой данные, которые хранятся в узлах списка, и запись TNode, которая определяет узел списка.

В модуле UnitMainForm. pas содержится описание формы для работы с пользователем.

В модуле UnitFuncs. pas описаны различные служебные функции, которые необходимо выполнять при работе с программой.

2. Статические данные и структуры Расположение элементов списка в памяти имеет следующий вид:

а) Обход списка по первым указателям (Рисунок 2);

б) Обход списка по вторым указателям (Рисунок 3);

в) Обход списка по третьим указателям (Рисунок 4);

г) Обход списка по четвертым указателям (Рисунок 5);

Рисунок 2 — Обход списка по первым указателям Рисунок 3 — Обход списка по вторым указателям Рисунок 4 — Обход списка по третьим указателям Рисунок 5 — Обход списка по четвертым указателям Ниже представлена информация о полях структуры TMember (Рисунок 6)

Рисунок 6 — Объект записи TMember

3. Логическая структура данных

Логическая структура двусвязного кольцевого списка имеет вид, представленный на рисунке 6.

Рисунок 6 — Структура списка Каждый элемент имеет указатели на следующий элемент соответствующего списка.

4 Логические схемы операций Наиболее важные операции со списками:

Добавление элемента в конец списка (Рисунок 9, 10).

Исключение элемента (Рисунок 11, 12).

Сортировка списка (Рисунок 13, 14).

Рисунок 9 — Перед добавлением элемента в конец списка Рисунок 10 — После добавления элемента в конец списка Рисунок 11 — До исключения элемента из списка Рисунок 12 — После исключения элемента из списка При сортировке списка методом Шейкера нужно переставлять соседние элементы. Схема перестановки элементов представлена на рисунках 13, 14.

Рисунок 13 — Нахождение элементов, подлежащих перестановке Рисунок 14 — Список после перестановки элементов

5. Алгоритмы обработки основных структур

5.1 Добавление нового элемента Алгоритм добавления нового элемента приведен на рисунок 15.

Рисунок 15 — Добавление нового элемента

5.2 Удаление элемента Алгоритм добавления нового элемента приведен на рисунке 16.

Рисунок 16 — Удаление элемента

6 Руководство пользователя При запуске программы появляется главное окно (Рисунок 17).

Рисунок 17 — Начало работы список программа структура алгоритм На форме содержится 5 таблиц с исходными данными, которые пользователь может редактировать. По нажатию кнопки «Добавить …», расположенной перед каждой таблицей, пользователю предоставляется пустая строка для добавления новой информации (Рисунок 18).

Рисунок 18 — Добавление информации в таблицы с данными Для отображения списка жильцов по определенному атрибуту на форме имеется кнопка «Заполнить список» и таблица для отображения информации. Если выбрать нужный атрибут и нажать на данную кнопку, таблица заполнится нужной информацией (Рисунок 19).

Рисунок 19 — Вывод полученного списка

ЗАКЛЮЧЕНИЕ

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

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

Пользовательский интерфейс программы максимально прост и удобен. Тестирование программы показало, что она полностью работоспособна и отвечает поставленным требованиям.

ПРИЛОЖЕНИЕ

// UnitFourthPlex. pas //

unit UnitFourthPlex;

interfac

uses Grids;

type

TMember = record

Surname: string[32];

XDCode: string[32];

SignXD: string[32];

City: string[32];

end;

TNodePtr = ^TNode;

TNode = record

Value: TMember;

NextFirst: TNodePtr;

NextSecond: TNodePtr;

NextThird: TNodePtr;

NextFourth: TNodePtr;

end;

TPlex = class

private

fFirstHead: TNodePtr;

fSecondHead: TNodePtr;

fThirdHead: TNodePtr;

fFourthHead: TNodePtr;

fCount: integer;

fNumberPointer: integer;

procedure SwapLinks (left, right: integer);

procedure AddToSecondList (newNode: TNodePtr);

procedure AddToThirdList (newNode: TNodePtr);

procedure AddToFourthList (newNode: TNodePtr);

procedure RemoveFromSecondList (node: TNodePtr);

procedure RemoveFromThirdList (node: TNodePtr);

procedure RemoveFromFourthList (node: TNodePtr);

public

function Get_pointer (Node: TNodePtr): TNodePtr;

function Get_head: TNodePtr;

procedure Set_return_pointer (attribute: integer);

procedure Print_to_Grid (Grid: TStringGrid);

function GetI (index: integer): TNodePtr;

procedure Add (value: TMember);

procedure AddToIndex (Value: TMember; Index: integer);

procedure Del (index: integer);

procedure Sort (attribute: integer);

procedure Clear;

property Count: integer read fCount;

end;

implementation

uses SysUtils;

function TPlex. Get_pointer (node: TNodePtr): TNodePtr;

begin

case fNumberPointer of

0: result := Node. NextFirst;

1: result := Node. NextSecond;

2: result := Node. NextThird;

3: result := Node. NextFourth;

end;

end;

function TPlex. Get_head: TNodePtr;

begin

case fNumberPointer of

0: result := fFirstHead;

1: result := fSecondHead;

2: result := fThirdHead;

3: result := fFourthHead;

end;

end;

procedure TPlex. Set_return_pointer (attribute: integer);

begin

fNumberPointer := attribute;

end;

procedure TPlex. Print_to_Grid (Grid: TStringGrid);

var curNode: TNodePtr;

begin

if fCount = 0 then

begin

Grid.FixedRows := 0;

Grid.RowCount := 1;

exit;

end;

Grid.RowCount := 2;

Grid.FixedRows := 1;

curNode := Get_head;

with Grid do

begin

while curNode <> nil do

begin

with curNode. Value do

begin

Cells[0,RowCount — 1] := Surname;

Cells[1,RowCount — 1] := XDCode;

Cells[2,RowCount — 1] := SignXD;

Cells[3,RowCount — 1] := City;

RowCount := RowCount + 1;

end;

curNode := Get_pointer (curNode);

end;

RowCount := RowCount — 1;

end;

end;

procedure TPlex. Add (value: TMember);

var newNode: TNodePtr;

curNode: TNodePtr;

begin

fCount := fCount + 1;

new (newNode);

newNode.Value := value;

newNode.NextFirst := nil;

newNode.NextSecond := nil;

newNode.NextThird := nil;

newNode.NextFourth := nil;

if fFirstHead = nil then

begin

fFirstHead := newNode;

fSecondHead := newNode;

fThirdHead := newNode;

fFourthHead := newNode;

exit;

end;

curNode := fFirstHead;

while curNode. NextFirst <> nil do

begin

curNode := curNode. NextFirst;

end;

curNode.NextFirst := newNode;

AddToSecondList (newNode);

AddToThirdList (newNode);

AddToFourthList (newNode);

end;

procedure TPlex. AddToSecondList (newNode: TNodePtr);

var

curNode: TNodePtr;

begin

if (fSecondHead.Value.XDCode > newNode.Value.XDCode) then

begin

newNode.NextSecond := fSecondHead;

fSecondHead := newNode;

exit;

end;

curNode := fSecondHead;

while (curNode.NextSecond <> nil) and

(curNode.NextSecond.Value.XDCode < newNode.Value.XDCode) do

begin

curNode := curNode. NextSecond;

end;

newNode.NextSecond := curNode. NextSecond;

curNode.NextSecond := newNode;

end;

procedure TPlex. AddToThirdList (newNode: TNodePtr);

var

curNode: TNodePtr;

begin

if (fThirdHead.Value.SignXD > newNode.Value.SignXD) then

begin

newNode.NextThird := fThirdHead;

fThirdHead := newNode;

exit;

end;

curNode := fThirdHead;

while (curNode.NextThird <> nil) and

(curNode.NextThird.Value.SignXD < newNode.Value.SignXD) do

begin

curNode := curNode. NextThird;

end;

newNode.NextThird := curNode. NextThird;

curNode.NextThird := newNode;

end;

procedure TPlex. AddToFourthList (newNode: TNodePtr);

var

curNode: TNodePtr;

begin

if (fFourthHead.Value.City > newNode.Value.City) then

begin

newNode.NextFourth := fFourthHead;

fFourthHead := newNode;

exit;

end;

curNode := fFourthHead;

while (curNode.NextFourth <> nil) and

(curNode.NextFourth.Value.City < newNode.Value.City) do

begin

curNode := curNode. NextFourth;

end;

newNode.NextFourth := curNode. NextFourth;

curNode.NextFourth := newNode;

end;

procedure TPlex. Del (index: integer);

var i: integer;

curNode: TNodePtr;

begin

if (index >= fCount) then

exit;

if index = 0 then

begin

RemoveFromSecondList (fFirstHead);

fFirstHead := fFirstHead. NextFirst;

exit;

end

else

begin

curNode := fFirstHead;

for i := index — 2 downto 0 do

curNode := curNode. NextFirst;

RemoveFromSecondList (curNode.NextFirst);

RemoveFromThirdList (curNode.NextFirst);

RemoveFromFourthList (curNode.NextFirst);

curNode.NextFirst := curNode.NextFirst.NextFirst;

end;

end;

procedure TPlex. RemoveFromSecondList (node: TNodePtr);

var

curNode: TNodePtr;

begin

if fSecondHead = node then

begin

fSecondHead := fSecondHead. NextSecond;

exit;

end;

curNode := fSecondHead;

while curNode. NextSecond <> node do

curNode := curNode. NextSecond;

curNode.NextSecond := curNode.NextSecond.NextSecond;

end;

procedure TPlex. RemoveFromThirdList (node: TNodePtr);

var

curNode: TNodePtr;

begin

if fThirdHead = node then

begin

fThirdHead := fThirdHead. NextThird;

exit;

end;

curNode := fThirdHead;

while curNode. NextThird <> node do

curNode := curNode. NextThird;

curNode.NextThird := curNode.NextThird.NextThird;

end;

procedure TPlex. RemoveFromFourthList (node: TNodePtr);

var

curNode: TNodePtr;

begin

if fFourthHead = node then

begin

fFourthHead := fFourthHead. NextFourth;

exit;

end;

curNode := fFourthHead;

while curNode. NextFourth <> node do

curNode := curNode. NextFourth;

curNode.NextFourth := curNode.NextFourth.NextFourth;

end;

procedure TPlex. Sort (attribute: integer);

var i: integer;

swap: boolean;

begin

if Count < 2 then

exit;

swap := true;

while swap do

begin

swap := false;

for i := 0 to Count — 2 do

if GetI (i).Value.Surname > GetI (i + 1).Value.Surname then

begin

swap := true;

SwapLinks (i, i + 1);

end;

for i := Count — 1 to 1 do

if GetI (i).Value.Surname < GetI (i — 1).Value.Surname then

begin

swap := true;

SwapLinks (i — 1, i);

end;

end;

end;

function TPlex. GetI (index: integer): TNodePtr;

var curNode: TNodePtr;

I: Integer;

begin

if (index >= Count) or (index < 0) then

exit;

curNode := fFirsthead;

for I := 0 to index — 1 do

begin

curNode := curNode. NextFirst;

end;

result := curNode;

end;

procedure TPlex. SwapLinks (left, right: integer);

var leftNode, rightNode: TNodePtr;

begin

leftNode := GetI (left);

rightNode := GetI (right);

if (left = 0) then

begin

leftNode.NextFirst := rightNode. NextFirst;

rightNode.NextFirst := leftNode;

fFirstHead := rightNode;

end

else

begin

leftNode.NextFirst := rightNode. NextFirst;

rightNode.NextFirst := leftNode;

GetI (left — 1).NextFirst := rightNode;

end;

end;

procedure TPlex. Clear;

begin

fCount := 0;

fFirstHead := nil;

fSecondHead := nil;

fThirdHead := nil;

fFourthHead := nil;

end;

procedure TPlex. AddToIndex (Value: TMember; Index: integer);

var current, NewNode: TNodePtr;

begin

if (index > fCount) then

exit;

current := fFirstHead;

new (NewNode);

NewNode.Value := Value;

if (index = 1) then

begin

NewNode.NextFirst := fFirstHead;

fFirstHead := NewNode;

AddToSecondList (NewNode);

exit;

end;

while (index > 2) do

begin

current := current. NextFirst;

dec (index);

end;

NewNode.NextFirst := current. NextFirst;

current.NextFirst := NewNode;

AddToSecondList (NewNode);

AddToThirdList (NewNode);

AddToFourthList (NewNode);

end;

end.