Абстрактные типы данных
Разработка класса TDate для работы с датой. Сущность и назначение методов create и construtor. Реализация списков с помощью массивов. Составление процедуры, которая удаляет из дерева все четные элементы. Представление графа в виде списка смежности.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 15.05.2014 |
| Размер файла | 855,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
var
s, s1 : string;
ps : PAnsiChar;
i : integer;
begin
{ s := cbFrom.Text;
s1 := cbTo.Text;
if ( s <> '' ) and ( s1 <> '' ) then
begin
graph.disconnect( strtoint(s), strtoint(s1), cbBoth.Checked);
end
else
begin
try
ps := PAnsiChar(treeview1.Selected.Text);
strScan( ps, ' ' )^ := #0;
graph.disconnect( strtoint( treeview1.Selected.Parent.Text ), strtoint( ps ));
except
on EAccessViolation do ;
end;
end;
updateData();}
end;
procedure TfrmMain.btSaveClick(Sender: TObject); //сохранение в файл
begin
if sdf.Execute then
begin
graph.serialize( sdf.FileName );
end
end;
procedure TfrmMain.btLoadClick(Sender: TObject); //загрузка из файла
begin
if odf.Execute then
begin
graph.clear;
id := graph.deserialize( odf.FileName );
inc(id );
updateData();
end;
end;
procedure TfrmMain.edCostKeyPress(Sender: TObject; var Key: Char); //установка веса
begin
if ( Key < '0' ) or ( Key > '9' ) or (length(edCost.Text) > 7 ) then
Key := #0;
end;
end.
unit SmegnGraph; //модуль описания свойств и процедур списка смежности
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls;
Type //создание списка и полей его элементов
PListNode = ^TListNode;
PGraphNode = ^TGraphNode;
TListNode = record
node : PGraphNode;
next : PListNode;
cost : integer;
end;
TGraphNode = record
id : integer;
next : PGraphNode;
list : PListNode;
end;
type
TSmegnGraph = class
private
graph : PGraphNode;
procedure addToList( list: PGraphNode; nn: PListNode ); //добавить элемент в список
procedure delFromList( list : PGraphNode; val : PGraphNode ); //удалить из списка
procedure disconnect( f, t : PGraphNode );overload; //процедура удаления связи
procedure delHost( h : PGraphNode );overload; //удалить вершину из списка
function find( id : integer ): PGraphNode; //найти вершину с определенным номером
(чтобы удалить ее или добавить связь)
public
constructor Create(); //создать список
destructor Free(); //удалить список смежности и освободить память
procedure serialize( fName : string ); //сохранить в файл
function deserialize( fName : string ) : integer; //считать из файла
procedure addHost( id : integer ); //добавление вершины
procedure connect( fromId, toId, cost : integer); //добавить связь
procedure delHost( id : integer );overload; //удалить заданную вершину
procedure disconnect( fromId, toId : integer);overload; //убрать заданную связь
procedure clear(); //очистить мемо
procedure import( mm : TMemo );overload; //вывод списка в мемо
procedure import( cb : TComboBox );overload; //вывод номеров вершин для назначения связй
end;
implementation
{ TSmegnGraph }
procedure TSmegnGraph.addHost(id: integer); //добавление вершины
var
tmp : PGraphNode;
begin
New( tmp );
tmp.id := id;
tmp.list := nil;
if ( graph <> nil ) then
begin
tmp.next := graph;
graph := tmp;
end
else
begin
graph := tmp;
tmp.next := nil;
end;
end;
procedure TSmegnGraph.connect(fromId, toId, cost: integer); //добавить связь
var
f, t : PGraphNode;
tmp : PListNode;
begin
f := find( fromId );
if ( f = nil ) then
exit;
t := find( toId );
if ( t = nil ) then
exit;
New( tmp );
tmp.node := t;
tmp.cost := cost;
addToList( f, tmp );
end;
procedure TSmegnGraph.delHost(h: PGraphNode); //удаление вершины
var
cur : PGraphNode;
begin
if ( h = nil ) or ( graph = nil ) then
exit;
cur := graph;
while( cur <> nil ) do
begin
if ( cur <> h ) then
disconnect( h, cur );
cur := cur.next;
end;
if ( h <> graph ) then
begin
cur := graph;
while( cur.next <> h ) do
cur := cur.next;
cur.next := cur.next.next;
end
else
begin
graph := graph.next;
end;
Dispose( h );
end;
constructor TSmegnGraph.Create; //создать список
begin
graph := nil;
end;
procedure TSmegnGraph.delHost(id: integer); //удалить заданную вершину
begin
delHost( find( id ) );
end;
function TSmegnGraph.deserialize(fName: string): integer; //считать из файла
var
sl : TstringList;
i : integer;
begin
Result := 0;
sl := TStringList.Create;
sl.LoadFromFile( fName );
i := 0;
while( i < sl.Count - 1 ) do
begin
if ( sl.Strings[i] = 'c' ) then
begin
inc ( i );
connect(
strtoint( sl.Strings[i] ),
strtoint( sl.Strings[i+1] ),
strtoint( sl.Strings[i+2] ),
);
inc(i);
inc(i);
end
else if ( sl.Strings[i] = 'p' ) then
begin
inc( i );
addHost( strtoint( sl.Strings[i] ) );
if ( strtoint( sl.Strings[i] ) > result ) then
result := strtoint( sl.Strings[i] );
end
else
raise ERangeError.Create( 'Error! File damaged' );
inc( i );
end;
end;
procedure TSmegnGraph.disconnect(fromId, toId: integer); //убрать заданную связь
begin
disconnect( find( fromId ), find( toId ) );
end;
procedure TSmegnGraph.disconnect(f, t: PGraphNode); //процедура удаления связи
begin
if ( f = nil ) or ( t = nil ) then
exit;
delFromList( f, t );
end;
destructor TSmegnGraph.Free; //очистить список
begin
clear();
end;
procedure TSmegnGraph.serialize(fName: string); //записать в файл
var
t : PGraphNode;
l : PListNode;
sl : TStringList;
begin
sl := TStringList.Create;
t := graph;
while( t <> nil ) do
begin
sl.Add( 'p' + #13#10 + inttostr( t.id ) );
t := t.next;
end;
t := graph;
while( t <> nil ) do
begin
l := t.list;
while( l <> nil ) do
begin
sl.Add( 'c' + #13#10 + inttostr( t.id ) + #13#10 + inttostr( l.node.id )
+ #13#10 + inttostr( l.cost ) );
l := l.next;
end;
t := t.next;
end;
sl.SaveToFile( fName );
end;
function TSmegnGraph.find(id: integer): PGraphNode; //найти вершину с определенным
var номером(чтобы удалить ее или добавить связь)
tmp : PGraphNode;
begin
tmp := Graph;
result := nil;
while( tmp <> nil ) do
begin
if ( tmp.id = id ) then
begin
Result := tmp;
break;
end;
tmp := tmp.next;
end;
end;
procedure TSmegnGraph.addToList(list: PGraphNode; nn: PListNode); //добавить вершину в
var tmp : PListNode; список
begin
tmp := list.list;
while( tmp <> nil ) do
begin
if ( tmp.node = nn.node ) then
exit;
tmp := tmp.next;
end;
if ( list.list <> nil ) then
begin
nn.next := list.list;
list.list := nn;
end
else
begin
list.list := nn;
nn.next := nil;
end;
end;
procedure TSmegnGraph.delFromList(list, val: PGraphNode); //удалить список из формы
var
tmp, t : PListNode;
begin
tmp := list.list;
if ( tmp <> nil ) and ( tmp.node <> val ) then
begin
while ( tmp <> nil ) do
begin
if ( tmp.next <> nil) then
begin
if ( tmp.next.node = val ) then
begin
break;
end;
end;
tmp := tmp.next;
end;
end;
if ( tmp = nil ) then
exit;
if ( tmp = list.list ) then
begin
list.list := list.list.next;
t := tmp;
end
else
begin
t := tmp.next;
tmp.next := tmp.next.next;
end;
Dispose( t );
end;
procedure TSmegnGraph.clear; //очистить список (убрать связи и вершины)
var
t, t1 : PGraphNode;
begin
t := graph;
while( t <> nil ) do
begin
t1 := graph;
while( t1 <> nil ) do
begin
if ( t <> t1 ) then
disconnect( t, t1);
t1 := t1.next;
end;
t := t.next;
end;
t := graph;
while( t <> nil ) do
begin
t1 := t;
t := t.next;
Dispose( t1 );
end;
graph := nil;
end;
procedure TSmegnGraph.import(cb: TComboBox); //вывод номеров вершин для назначения
var связей
tmp : PGraphNode;
begin
cb.Clear;
tmp := graph;
while( tmp <> nil ) do
begin
cb.AddItem( inttostr( tmp.id), nil );
tmp := tmp.next;
end;
end;
procedure TSmegnGraph.import(mm: TMemo); //вывод списка через мемо
var
t : PGraphNode;
l : PListNode;
begin
mm.Clear;
t := graph;
while( t <> nil ) do
begin
mm.Lines.Add( 'Вершина: ' + inttostr( t.id ) );
l := t.list;
while( l <> nil ) do
begin
mm.Lines.Add( 'Связана с ' + inttostr( l.node.id ) + ' ( Вес: ' + inttostr( l.cost ) + ')' );
l := l.next;
end;
t := t.next;
end;
end;
end.
Размещено на Allbest.ru
Подобные документы
Описание процедуры выбора структуры хранения данных. Программная реализация одномерного неоднородного массива. Представление бинарного дерева в виде динамической структуры данных. Изучение способов поиска в упорядоченном дереве. Содержание базы данных.
практическая работа [850,0 K], добавлен 16.04.2015Составление алгоритма сортировки линейной вставкой. Понятие однонаправленного циклического списка символов, реализация процедуры подсчета суммы элементов и составление алгоритма. Прямое представление дерева, алгоритм работы с ним на абстрактном уровне.
контрольная работа [32,8 K], добавлен 20.01.2012Использование метода абстракции в программировании на примере построения польской записи выражения с помощью стека. Абстрактные типы данных. Анализ классов реализации списков. Вставка и удаление элемента в список. Вычисление значения выражения на стеке.
презентация [166,7 K], добавлен 19.10.2014Понятие и обработка списков. Имя домена списка. Примеры записи списков. Основные принципы работы со списками. Рекурсивная программа обработки списка. Определение номера элемента или элемента по номеру. Решение задач, использующих структуру графа.
презентация [65,0 K], добавлен 29.07.2012Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.
курсовая работа [8,1 M], добавлен 07.09.2012Составление программной функции, которая вычисляет среднее арифметическое элементов непустого списка. Функция, которая находит наименьший элемент дерева. Нахождение искомых элементов, добавление элементов в дерево. Выведение состояния дерева на экран.
лабораторная работа [636,3 K], добавлен 02.04.2014Понятия и методика создания списков и баз данных в Microsoft Excel. Фильтрация списков, виды сортировки данных и структурирования листа. Сортировка с помощью списка автозаполнения и "слева направо". Создание сводки о реализации товара за один день.
курсовая работа [618,3 K], добавлен 25.04.2013Организация работы базы данных с помощью сбалансированных В-деревьев: принципы, методы добавления, поиска, удаления элементов из структуры. Процедуры, производящие балансировку и слияние записей в блоке. Реализация программы в Научной библиотеке ОрелГТУ.
курсовая работа [95,3 K], добавлен 12.08.2011Реализация линейных списков в языке программирования C++. Основные операции при работе с ними. Разработка интерфейса и алгоритмов. Описание работы программы на псевдокоде. Составление программного кода. Тестирование, отладка и результат работы программы.
курсовая работа [1,1 M], добавлен 07.01.2014Представление (построение, создание) списка данных в виде линейного однонаправленного списка. Формирование массива данных. Вывод данных на экран. Алгоритм удаления, перемещения данных. Сортировка методом вставки. Алгоритм загрузки данных из файла.
курсовая работа [2,1 M], добавлен 16.05.2015
