Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
|
МИНОБРНАУКИ РОССИИ |
||
Федеральное государственное бюджетное образовательное учреждениевысшего профессионального образования"Московский государственный технический университет радиотехники,электроники и автоматики"МГТУ МИРЭА |
ОТЧЕТ
Лабораторная работа № 3
по предмету «Информатика»
на тему «Структура данных – связный список»
Группа ИСБ-4-12
Исполнитель: Морнев А.А
Руководитель: асс. Мирзоян Д.И.
Москва, 2013
Задание:
Теоретическая часть :
Односвязные списки.
Динамические структуры характеризуются непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки, отсутствием физической смежности элементов структуры в памяти. Часто динамические структуры представляются в виде связных списков.
Связный список – структура, элементы которой имеют один и тот же формат и связаны друг с другом с помощью указателей, хранящихся в самих элементах.
В односвязном списке каждый элемент состоит из двух различных по назначению полей: содержательного поля (поле данных) и служебного поля (поля указателя), где хранится адрес следующего элемента списка. Поле указателя последнего элемента списка содержит нулевой указатель, свидетельствующий о конце списка.
Линейность односвязного списка вытекает из линейной логической упорядоченности его элементов: для каждого элемента, за исключением первого и последнего, имеются единственный предыдущий и единственный последующий элементы. Односвязные списки всегда линейны, поэтому особое внимание следует уделить проблеме перестройки списка при его повреждении.
Логическая структура линейного односвязного списка:
Логическая структура элемента линейного односвязного списка:
Основные операции над линейным односвязным списком:
Продвижение в линейном односвязном списке возможно только в одном направлении. Результаты выполнения операций включения элемента в линейный односвязный список и исключения элемента из линейного односвязного списка – линейный односвязный список.
Алгоритм решения задач:
Алгоритм 1 (Процедура добавления элемента в конец списка)
Алгоритм 2 (Функция чтения элементов списка)
Алгоритм 3 (Процедура удаления элемента элементов списка)
Алгоритм 4 (Count)
Алгоритм 5 (Кнопка «Добавить»)
Алгоритм 6 (Кнопка «Чтение»)
Алгоритм 7 (Кнопка «Удаление»)
Алгоритм 8 (Кнопка «Count»)
Тестирование:
Листинг программы:
unit Unit1;
{$mode objfpc}{$H+}
interface
uses
Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls,
Spin, EditBtn;
type
{ TForm1 }
TForm1 = class(TForm)
Button1: TButton;
Button2: TButton;
Button3: TButton;
Button4: TButton;
DateEdit1: TDateEdit;
Edit1: TEdit;
Edit2: TEdit;
Edit3: TEdit;
Edit4: TEdit;
Edit5: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Label6: TLabel;
Label7: TLabel;
Label8: TLabel;
SpinEdit1: TSpinEdit;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
{ private declarations }
public
{ public declarations }
end;
type
PList =^TList; //Указатель на TList
TList=record //Список
FirstName:String;
LastName:String;
Patronics:string;
BirthDate:TDateTime;
Department:string[5];
Profession:string[6];
Next:PList; //Следующий элемент списка
end;
var
Form1: TForm1;
Head:Plist;
implementation
{$R *.lfm}
{ TForm1 }
function Count(x:plist):integer; //Count
begin
Result:=0;
while (x<>nil) do
begin
Result:=Result+1;
x:=x^.Next;
end;
end;
procedure AddItem(var x:Plist;NewStudent:PList); //Процедура добавления элемента в конец списка
var
Tail:Plist;
i:integer;
begin
if x=nil then
begin
x:=NewStudent;
x^.Next:=nil;
end
else
begin
Tail:=x;
while tail^.Next<>nil do
tail:=tail^.Next;
Tail^.Next:=NewStudent;
NewStudent^.Next:=nil;
end;
end;
Function ReadItemN(x:plist; n:integer):Plist; //Функция чтения элемеентов списка
begin
Result:=nil;
while (x<>nil) and (n>0) do
begin
Dec(n);
Result:=x;
x:=x^.next;
end;
end;
Procedure DeleteItemN(var tail:Plist;N:integer); //Процедура удаления элемента
var
x,q:Plist;
i:integer;
begin
q:=Tail;
if q<>nil then//Если список не пуст
begin
if n=1 then
begin
Tail:=q^.Next;
if q<>nil then
Dispose(q);
end
else
begin
i:=0;
while (i<N-2) and (q<>nil) do
begin
q:=q^.Next;
Inc(i);
end;
x:=q^.Next;
if x<>nil then
begin
q^.Next:=x^.Next;
if x<> nil then
Dispose(x);
end;
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject); //Кнопка добавления элемента в конец списка
var
NewStudent:PList;
begin
New(NewStudent);
NewStudent^.FirstName:=Edit1.Text;
NewStudent^.LastName:=Edit2.Text;
NewStudent^.Patronics:=Edit3.Text;
NewStudent^.BirthDate:=DateEdit1.Date;
NewStudent^.Department:=Edit4.Text;
NewStudent^.Profession:=Edit5.Text;
AddItem(Head,NewStudent);
end;
procedure TForm1.Button2Click(Sender: TObject); //Кнопка чтения элемента
var
Student:PList;
begin
Student:=ReaditemN(Head,SpinEdit1.Value);
Edit1.Text:=Student^.FirstName;
Edit2.Text:=Student^.LastName;
Edit3.Text:=Student^.Patronics;
DateEdit1.Date:=Student^.BirthDate;
Edit4.Text:=Student^.Department;
Edit5.Text:=STudent^.Profession;
end;
procedure TForm1.Button3Click(Sender: TObject); //Кнопка удаления элемента
begin
DeleteItemN(Head,SpinEdit1.Value)
end;
procedure TForm1.Button4Click(Sender: TObject); //Count
begin
Label1.Caption:=IntToStr(Count(Head));
end;
end.
Скриншоты :
Скриншот форм в режиме разработки, с сеткой.