Программа для создания двусвязных кольцевых списков
Содержание
Введение
1.
Состав
проекта
.1
Формы
.2
Модули
2.
Статические
данные и структуры
3.
Логическая
структура данных
4.
Логические
схемы операций
5.
Алгоритмы
обработки основных структур
5.1
Добавление нового элемента
5.2
Удаление
элемента
.
Руководство
пользователя
Заключение
Список
использованных источников
Приложение
Введение
Любая программа представляет собой не только
набор операторов и ключевых слов, но также совокупность информационных
объектов, действия над которыми записаны в этих операторах. В любом операторе
фигурируют объекты называемые данными. Значение данного, относящегося к любому
из таких типов логически неразделимо. Поэтому такие данные называются
неструктурированными. Из них формируются структуры данных.
Структуры данных используются повсюду. В этом
понятии приоритетную роль играют не значения элементов данных, т.е. данных
которые образуют структуру, а отношение между этими элементами. Именно
отношение определяет конфигурацию структуры, а самое главное реализацию
операций в структурах.
Связный список - структура данных, состоящая из
узлов, каждый из которых содержит как собственно данные, так и одну или две
ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным
преимуществом перед массивом является структурная гибкость: порядок элементов
связного списка может не совпадать с порядком расположения элементов данных в
памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними
связями.
1.
Состав Delphi проекта
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. Алгоритмы
обработки основных структур
.1 Добавление нового элемента
Алгоритм добавления нового элемента
приведен на рисунок 15.
Рисунок 15 - Добавление нового
элемента
5.2 Удаление элемента
Алгоритм добавления нового элемента
приведен на рисунке 16.
Рисунок 16 - Удаление элемента
6 Руководство пользователя
При запуске программы появляется
главное окно (Рисунок 17).
Рисунок 17 - Начало работы
список программа
структура алгоритм
На форме содержится 5 таблиц с
исходными данными, которые пользователь может редактировать. По нажатию кнопки
«Добавить …», расположенной перед каждой таблицей, пользователю предоставляется
пустая строка для добавления новой информации (Рисунок 18).
Рисунок 18 - Добавление информации в
таблицы с данными
Для отображения списка жильцов по
определенному атрибуту на форме имеется кнопка «Заполнить список» и таблица для
отображения информации. Если выбрать нужный атрибут и нажать на данную кнопку,
таблица заполнится нужной информацией (Рисунок 19).
Рисунок 19 - Вывод полученного
списка
ЗАКЛЮЧЕНИЕ
В ходе курсовой работы мною было
разработано приложение для создания двусвязных кольцевых списков.
Как оказалось, связанные списки -
это наиболее подходящая структура для динамических данных, т.к. они могут иметь
переменное количество элементов. Затраты производительности при работе со
списками незначительны по сравнению с той экономией памяти и гибкостью, которые
они предоставляют.
Пользовательский интерфейс программы
максимально прост и удобен. Тестирование программы показало, что она полностью
работоспособна и отвечает поставленным требованиям.
ПРИЛОЖЕНИЕ
// UnitFourthPlex.pas
//UnitFourthPlex;
interfac
uses Grids;
TMember = record: string[32];:
string[32];: string[32];: string[32];;
TNodePtr = ^TNode;
TNode = record: TMember;
NextFirst: TNodePtr;: TNodePtr;:
TNodePtr;: TNodePtr;;
TPlex = class: TNodePtr;: TNodePtr;:
TNodePtr;: TNodePtr;
fCount: integer;
fNumberPointer: integer;
procedure SwapLinks(left, right:
integer);AddToSecondList(newNode: TNodePtr);AddToThirdList(newNode:
TNodePtr);AddToFourthList(newNode: TNodePtr);RemoveFromSecondList(node:
TNodePtr);RemoveFromThirdList(node: TNodePtr);RemoveFromFourthList(node:
TNodePtr);
public
function Get_pointer(Node:
TNodePtr): TNodePtr;Get_head: TNodePtr;Set_return_pointer(attribute: integer);
procedure Print_to_Grid(Grid:
TStringGrid);GetI(index: integer): TNodePtr;
procedure Add(value:
TMember);AddToIndex(Value: TMember; Index: integer);Del(index:
integer);Sort(attribute: integer);Clear;
property Count: integer read
fCount;;
implementation
uses SysUtils;
function TPlex.Get_pointer(node:
TNodePtr): TNodePtr;
case fNumberPointer of
: result := Node.NextFirst;
: result := Node.NextSecond;
: result := Node.NextThird;
: result := Node.NextFourth;;
end;
function TPlex.Get_head: TNodePtr;
case fNumberPointer of
: result := fFirstHead;
: result := fSecondHead;
: result := fThirdHead;
: result := fFourthHead;;
end;
procedure
TPlex.Set_return_pointer(attribute: integer);:= attribute;;
procedure TPlex.Print_to_Grid(Grid:
TStringGrid);curNode: TNodePtr;
if fCount = 0 then.FixedRows :=
0;.RowCount := 1;;;
Grid.RowCount := 2;.FixedRows := 1;
curNode := Get_head;
with Grid do
while curNode <> nil
docurNode.Value do[0,RowCount - 1] := Surname;[1,RowCount - 1] :=
XDCode;[2,RowCount - 1] := SignXD;[3,RowCount - 1] := City;
RowCount := RowCount + 1;;
curNode := Get_pointer(curNode);;
RowCount := RowCount - 1;
end;;
procedure TPlex.Add(value:
TMember);newNode: TNodePtr;: TNodePtr;
new(newNode);.Value := value;
newNode.NextFirst := nil;.NextSecond
:= nil;.NextThird := nil;.NextFourth := nil;
if fFirstHead = nil then:=
newNode;:= newNode;:= newNode;:= newNode;;;
curNode := fFirstHead;
while curNode.NextFirst <> nil
do:= curNode.NextFirst;;
curNode.NextFirst := newNode;
AddToSecondList(newNode);(newNode);(newNode);;
procedure TPlex.AddToSecondList(newNode:
TNodePtr);: TNodePtr;
if(fSecondHead.Value.XDCode >
newNode.Value.XDCode) then.NextSecond := fSecondHead;:= newNode;;;
curNode := fSecondHead;
while (curNode.NextSecond <>
nil) and
(curNode.NextSecond.Value.XDCode
< newNode.Value.XDCode) do:= curNode.NextSecond;;
newNode.NextSecond :=
curNode.NextSecond;.NextSecond := newNode;
end;
procedure
TPlex.AddToThirdList(newNode: TNodePtr);: TNodePtr;
if(fThirdHead.Value.SignXD >
newNode.Value.SignXD) then.NextThird := fThirdHead;:= newNode;;;
curNode := fThirdHead;
while (curNode.NextThird <>
nil) and
(curNode.NextThird.Value.SignXD <
newNode.Value.SignXD) do:= curNode.NextThird;;
newNode.NextThird :=
curNode.NextThird;.NextThird := newNode;
end;
procedure
TPlex.AddToFourthList(newNode: TNodePtr);: TNodePtr;
if(fFourthHead.Value.City >
newNode.Value.City) then.NextFourth := fFourthHead;:= newNode;;;
curNode := fFourthHead;
while (curNode.NextFourth <>
nil) and
(curNode.NextFourth.Value.City <
newNode.Value.City) do:= curNode.NextFourth;;
newNode.NextFourth :=
curNode.NextFourth;.NextFourth := newNode;
end;
procedure TPlex.Del(index:
integer);i: integer;: TNodePtr;
if(index >= fCount) then;
if index = 0 then
RemoveFromSecondList(fFirstHead);:=
fFirstHead.NextFirst;;
curNode := fFirstHead;
for i := index - 2 downto 0 do:=
curNode.NextFirst;
RemoveFromSecondList(curNode.NextFirst);(curNode.NextFirst);(curNode.NextFirst);
curNode.NextFirst :=
curNode.NextFirst.NextFirst;;
end;
procedure
TPlex.RemoveFromSecondList(node: TNodePtr);: TNodePtr;
if fSecondHead = node then:=
fSecondHead.NextSecond;;;
curNode := fSecondHead;
while curNode.NextSecond <>
node do:= curNode.NextSecond;
curNode.NextSecond :=
curNode.NextSecond.NextSecond;
end;
procedure
TPlex.RemoveFromThirdList(node: TNodePtr);: TNodePtr;
if fThirdHead = node then:=
fThirdHead.NextThird;;;
curNode := fThirdHead;
while curNode.NextThird <>
node do:= curNode.NextThird;
curNode.NextThird :=
curNode.NextThird.NextThird;;
procedure
TPlex.RemoveFromFourthList(node: TNodePtr);: TNodePtr;
if fFourthHead = node then:=
fFourthHead.NextFourth;;;
curNode := fFourthHead;
while curNode.NextFourth <>
node do:= curNode.NextFourth;
curNode.NextFourth :=
curNode.NextFourth.NextFourth;;
procedure TPlex.Sort(attribute:
integer );i: integer;: boolean;
if Count < 2 then;
swap := true;swap do
swap := false;
for i := 0 to Count - 2
doGetI(i).Value.Surname > GetI(i + 1).Value.Surname then:= true;(i, i + 1);;
for i := Count - 1 to 1
doGetI(i).Value.Surname < GetI(i - 1).Value.Surname then:= true;(i - 1,
i);;;;
function TPlex.GetI(index: integer):
TNodePtr;curNode: TNodePtr;: Integer;(index >= Count) or (index < 0)
then;
curNode := fFirsthead;
for I := 0 to index - 1 do:=
curNode.NextFirst;;
result := curNode;;
TPlex.SwapLinks(left, right:
integer);leftNode, rightNode : TNodePtr;:= GetI(left);:= GetI(right);
if (left = 0) then.NextFirst :=
rightNode.NextFirst;.NextFirst := leftNode;
fFirstHead := rightNode;.NextFirst
:= rightNode.NextFirst;.NextFirst := leftNode;
GetI(left - 1).NextFirst :=
rightNode;;
end;
procedure TPlex.Clear;
fCount := 0;
end;
TPlex.AddToIndex(Value: TMember;
Index: integer);current, NewNode: TNodePtr;
if (index > fCount) then;
current :=
fFirstHead;(NewNode);.Value := Value;
if (index = 1) then.NextFirst :=
fFirstHead;:= NewNode;(NewNode);;;
while (index > 2) do:=
current.NextFirst;(index);;
NewNode.NextFirst := current.NextFirst;.NextFirst
:= NewNode;
AddToSecondList(NewNode);(NewNode);(NewNode);;
end.
1.