Высокоуровневые методы информатики и программирования

 

АВТОНОМНАЯ  НЕКОММЕРЧЕСКАЯ ОРГАНИЗАЦИЯ

 ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ 

ЕВРАЗИЙСКИЙ ОТКРЫТЫЙ ИНСТИТУТ

 

 

Кафедра Информатики

 

 

 

 

 

Лабораторная  работа  № 2

по дисциплине

 

Высокоуровневые методы информатики 

и программирования

 

 

 

 

 

 

 

 

 

 

Выполнил: студент  группы ОПИ – 201с

Масленкин А.А.

Руководитель: Калмыкова О.В.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 2011 

Задание

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

Результатом выполнения лабораторной  работы  должна стать полностью отлаженная программа, снабженная соответствующей документацией в форме отчета. К отчету прилагается дискета (CD), содержащая все материалы по лабораторной работе – исходный текст программ, отчет, тестовые наборы данных.

При проектировании и написании программы должны быть применены методы нисходящего проектирования и модульного программирования.

 

Каждый вариант  задания состоит из общей и  индивидуальной частей, которые приведены ниже.

В состав общей части  входит реализация следующих действий.

1. Создание пустого списка.
2. Подсчет количества элементов списка.
3. Вывод на экран содержимого списка в виде таблицы.
4. Вставка элемента в начало или в конец списка (оба варианта).
5. Исключение элемента из начала или конца списка (оба варианта).
6. Сохранение списка в файле.
7. Восстановление списка из файла.
8. Уничтожение списка с освобождением памяти.

 

Примечания.

     1. Каждый элемент списка имеет  ключевой признак и информационное поле. Ключ - целое без знака с произвольным значением. Содержание информационного поля произвольно (может быть числовым, символьным или строковым).

2. Управление выбором  функций  организовать  с помощью иерархических меню.
3. Вывод списка на экран должен иметь вид:

 

N п/п	Ключ	Информация

                                 Всего в списке ____ элементов.

    

4. Вид организации списка – линейный однонаправленный без головного элемента.

 

Индивидуальные  задания:

1. Включить новый элемент после i-го по номеру элемента;
2. Исключить элемент перед элементом с заданным ключом;
3. Поменять местами элемент с максимальным значением ключа и последний.

 

 

Теоретическая часть

Приложение  представляет содой программный  продукт под операционные системы семейства Windows XP, Vista, Seven, выполняющий заданную работу по созданию и манипуляциям различных видов с однонаправленным списком без головного элемента.

Список  всех выполняемых программой действий над списком полностью соответствует поставленному заданию. Для доступа к функциям приложения на главной форме расположен ряд элементов Button, объединенный с помощью элемента GroupBox.

Для отображения  списка на главной форме используется визуальный элемент StringGrid.

Для обеспечения  возможности сохранения списка в  файл и восстановления списка из файла применения два невизуальных элемента OpenDialog и SaveDialog. Используется текстовый формат файлов, расширение *.txt.

Для ввода  ключа и индекса элемента в  некоторых операциях используется диалоговая форма ввода данных с текстовым полем.

Все основные процедуры и функции для работы со списком вынесены в отдельный  модуль uList.

При запуске  приложения на 2000 миллисекунд отображается заставка приложения, содержащая данные о работе. Для сокрытия заставки спустя указанное время использован невизуальный элемент Timer.

.

 

Структура разработанного ПО

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

Рисунок 1. Функциональная структура приложения.

 

 

Спецификации на модули/процедуры

Приведены спецификации на основные процедуры и функции.

Наименование процедуры/функции	Описание вызова процедуры/функции	Входные параметры	Выходные параметры	Список процедур, вызываемых из данной
CreateEmptyList – для создания пустого списка	CreateEmptyList(var first : link);	first, запись, указатель на первый элемент списка	-	-
DropList - удаление списка с освобождением памяти	DropList(var first : link);	first, запись, указатель на первый элемент списка	-	-
OutputInTable – для вывода списка в StringGrid	OutputInTable(var first : link; var DataSG : TStringGrid);	first, запись, указатель на первый элемент списка; DataSG, TStringGrid , объект StringGrid, с которым работаем	-	CounterElement;
ClearTable – для очистки StringGrid	ClearTable(var DataSG : TStringGrid);	DataSG, TStringGrid , объект StringGrid, с которым работаем	-	-
InsertElementInBegin – для вставки элемента в начало	InsertElementInBegin(var el : link; var first : link);	el, запись, указатель на элемент, который вставляем; first, запись, указатель на первый элемент списка	-	-
InsertElementInEnd – для вставки элемента в конец списка	InsertElementInEnd(var el : link; var first : link);	el, запись, указатель на элемент, который вставляем; first, запись, указатель на первый элемент списка	-	-
InsertPostIndex – для вставки элемента в список после элемента с указанным индексом	InsertPostIndex(var el : link; var first : link; var index : integer);	el, запись, указатель на элемент, который вставляем; first, запись, указатель на первый элемент списка; index, целочисленный тип, индекс элемента	-	CounterElement;
DeleteElementInBegin – для удаления элемента в начале списка	DeleteElementInBegin(var first : link);	first, запись, указатель на первый элемент списка;	-	-
DeleteElementInEnd – для удаления элемента в конце списка	DeleteElementInEnd(var first : link);	first, запись, указатель на первый элемент списка;	-	-
DeletePostKey – исключение элемента перед элементом с заданным ключом	DeletePostKey(var key : integer; var first : link);	key, целочисленный тип, ключ элемента, перед которым удаляем; first, запись, указатель на первый элемент списка;	-	DeleteIntermediateElement; CounterElement;
DeleteIntermediateElement – для удаления элемента по его индексу	DeleteIntermediateElement(var first : link; var index : integer);	index, целочисленный тип, index элемента, который удаляем; first, запись, указатель на первый элемент списка;	-	CounterElement; DeleteElementInEnd;
CounterElement – для определения количества элементов списка	CounterElement(var first : link) : integer;	first, запись, указатель на первый элемент списка;	integer, количество элементов списка	-
SaveInFile – для сохранения списка в файле	SaveInFile(var fn : TFileName; var first : link) : boolean;	fn, имя текстового файла; first, запись, указатель на первый элемент списка	Boolean, результат выполнения операции	CounterElement;
LoadOutFile – для восстановления списка из файла	LoadOutFile(var fn : TFileName; var first : link) : boolean;	fn, имя текстового файла; first, запись, указатель на первый элемент списка	Boolean, результат выполнения операции	InsertElementInEnd;
ChangeMaxKeyAndLast – для перемены местами элемента с максимальным значением ключа и последнего	ChangeMaxKeyAndLast(var first : link);	first, запись, указатель на первый элемент списка		CounterElement; InsertPostIndex;

 

 

План машинного эксперимента

Проведено тестирование разработанного приложения с созданием списка из 10 элементов, и проведением над ним ряда манипуляций, включая операции сохранения в файл, уничтожения текущего экземпляра списка и последующее его восстановление из файла.

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

 

Листинги модулей и исходного файла данных

Листинг 1. Текст  программы модуля главной формы.

unit uMain;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, Grids;

type

  TfrmMain = class(TForm)

    GroupBox1: TGroupBox;

    GroupBox2: TGroupBox;

    Button1: TButton;

    Button2: TButton;

    Button3: TButton;

    Button4: TButton;

    Button5: TButton;

    Button6: TButton;

    Button7: TButton;

    Button8: TButton;

    Button9: TButton;

    Button10: TButton;

    Button11: TButton;

    Button12: TButton;

    Button13: TButton;

    Button14: TButton;

    Button15: TButton;

    DataSg: TStringGrid;

    SaveDialog1: TSaveDialog;

    OpenDialog1: TOpenDialog;

    procedure Button15Click(Sender: TObject);

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

    procedure Button1Click(Sender: TObject);

    procedure Button11Click(Sender: TObject);

    procedure FormCreate(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

    procedure Button4Click(Sender: TObject);

    procedure Button5Click(Sender: TObject);

    procedure Button6Click(Sender: TObject);

    procedure Button9Click(Sender: TObject);

    procedure Button10Click(Sender: TObject);

    procedure Button7Click(Sender: TObject);

    procedure Button8Click(Sender: TObject);

    procedure Button12Click(Sender: TObject);

    procedure Button13Click(Sender: TObject);

    procedure Button14Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  frmMain: TfrmMain;

implementation

uses uList, uInputIndex;

{$R *.dfm}

var

  creates : boolean;

  first : link;

 procedure TfrmMain.Button15Click(Sender: TObject);

begin

  Close;

end;

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

begin

  if (Application.MessageBox(Завершить работу приложения?','Внимание!',MB_OKCANCEL + MB_ICONQUESTION)=IDOK) then

    Action := caFree

  else

    Action := caNone;

end;

procedure TfrmMain.Button1Click(Sender: TObject);

begin

  try

    if creates = true then

      ShowMessage('Список уже создан!')

    else

    begin

      CreateEmptyList(first);

      ShowMessage('Пустой список создан!');

      creates := true;

    end;

  except

    ShowMessage('Ошибка создания списка!');

  end;

end;

procedure TfrmMain.Button11Click(Sender: TObject);

begin

  if creates = true then

  begin

    try

      creates := false;

      DropList(first);

      ShowMessage('Список удален!');

    except

      ShowMessage('Ошибка удаления списка!');

    end

  end

    else

  begin

    ShowMessage('Список уже удален!');

  end;

end;

procedure TfrmMain.FormCreate(Sender: TObject);

begin

  creates := False;

end;

procedure TfrmMain.Button2Click(Sender: TObject);

begin

  ShowMessage('Число элементов списка - ' + IntToStr(CounterElement(first)));

end;

procedure TfrmMain.Button3Click(Sender: TObject);

begin

  OutputInTable(first, DataSG);

end;

procedure TfrmMain.Button4Click(Sender: TObject);

begin

  ClearTable(DataSG);

end;

procedure TfrmMain.Button5Click(Sender: TObject);

var

  el : link;

begin

  if creates = true then

  begin

    new(el);

    el^.info := '';

    el^.key := CounterElement(first) + 1;

    el^.next := nil;

    InsertElementInBegin(el, first);

  end

    else

    ShowMessage(' Создайте список!');

end;

procedure TfrmMain.Button6Click(Sender: TObject);

var

  el : link;

begin

  if creates = true then

  begin

    new(el);

    el^.info := '';

    el^.key := CounterElement(first) + 1;

    el^.next := nil;

    InsertElementInEnd(el, first);

  end

    else

    ShowMessage(' Создайте список!');

end;

procedure TfrmMain.Button9Click(Sender: TObject);

var

  fn : TFileName;

begin

  if (creates <> false) and (CounterElement(first) > 0) then

  begin

    with SaveDialog1 do begin

      InitialDir := ExtractFilePath(Application.ExeName);

      Filter := 'Text files (*.txt)|*.txt';

    end;

    if SaveDialog1.Execute then

      fn := SaveDialog1.FileName + '.txt';

      SaveInFile(fn, first);

  end

    else

  begin

    ShowMessage('Создайте список и задайте хотя бы один элемент!');

  end;

end;

procedure TfrmMain.Button10Click(Sender: TObject);

var

  fn : TFileName;

begin

  if (creates = false) then

  begin

    with OpenDialog1 do begin

      InitialDir := ExtractFilePath(Application.ExeName);

      Filter := 'Text files (*.txt)|*.txt';

    end;

    if OpenDialog1.Execute then

      fn := OpenDialog1.FileName + '.txt';

      LoadOutFile(fn, first);

  end

    else

  begin

    ShowMessage('Удалите текущий список перед загрузкой нового списка из файла!');

  end;

end;

procedure TfrmMain.Button7Click(Sender: TObject);

begin

  if creates = true then

  begin

    DeleteElementInBegin(first);

  end

    else

    ShowMessage(' Создайте список!');

end;

procedure TfrmMain.Button8Click(Sender: TObject);

begin

  if creates = true then

  begin

    DeleteElementInEnd(first);

  end

    else

    ShowMessage(' Создайте список!');

end;

procedure TfrmMain.Button12Click(Sender: TObject);

var

  el : link;

  index : integer;

begin

  if creates = true then

  begin

    new(el);

    el^.key := CounterElement(first) + 1;

    el^.info := '';

    el^.next := nil;

    if (frmInputIndex.ShowModal and frmInputIndex.ModalResult = mrOk) then

    begin

      try

        index := StrToInt(frmInputIndex.Edit1.Text);

      except

        index := 0;

      end;

      InsertPostIndex(el, first, index);

    end

  end

    else

    ShowMessage('Создайте список!');

end;

procedure TfrmMain.Button13Click(Sender: TObject);

var

  key : integer;

begin

  if creates = true then

  begin

    if (frmInputIndex.ShowModal and frmInputIndex.ModalResult = mrOk) then

    begin

      try

        key := StrToInt(frmInputIndex.Edit1.Text);

      except

        key := 0;

      end;

      DeletePostKey(key, first);

    end

  end

    else

    ShowMessage('Создайте список!');

end;

procedure TfrmMain.Button14Click(Sender: TObject);

begin

  if creates = true then

  begin

    ChangeMaxKeyAndLast(first);

  end

    else

    ShowMessage('Создайте список!');

end;

end.

Листинг 2. Модуль работы со cписком.

unit uList;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, Grids;

type

  link = ^element;

  element  = record

       key : integer;      

       info : variant;     

       next : link         

end;

  procedure CreateEmptyList(var first : link);

  procedure DropList(var first : link);

  procedure OutputInTable(var first : link; var DataSG : TStringGrid);

  procedure ClearTable(var DataSG : TStringGrid);

  procedure InsertElementInBegin(var el : link; var first : link);

  procedure InsertElementInEnd(var el : link; var first : link);

  procedure InsertPostIndex(var el : link; var first : link; var index : integer);

  procedure DeleteElementInBegin(var first : link);

  procedure DeleteElementInEnd(var first : link);

  procedure DeletePostKey(var key : integer; var first : link);

  procedure DeleteIntermediateElement(var first : link; var index : integer);

  function CounterElement(var first : link) : integer;

  function SaveInFile(var fn : TFileName; var first : link) : boolean;

  function LoadOutFile(var fn : TFileName; var first : link) : boolean;

  procedure ChangeMaxKeyAndLast(var first : link);

implementation

procedure CreateEmptyList(var first : link);

begin

  first := nil;

end;

procedure DropList(var first : link);

var

  temp, temp2 : link;

begin

  if first <> nil then

  begin

    temp := first;

    temp2 := nil;

    while temp <> nil do

    begin

      temp2 := temp;

      temp := temp^.next;

      dispose(temp2);

    end;

    first := nil;

  end;

end;

procedure OutputInTable(var first : link; var DataSG : TStringGrid);

var

  i, count : integer;

  temp : link;

begin

  i := 0;

  count := CounterElement(first);

  temp := first;

  DataSG.Cells[0, i] := 'Key';

  DataSG.Cells[1, i] := 'Information';

  DataSG.Cells[2, i] := 'Link';

  if first <> nil then

  begin

    repeat

      i := i + 1;

      DataSG.RowCount := i + 1;

      DataSG.Cells[0, i] := IntToStr(temp^.key);

      DataSG.Cells[1, i] := temp^.info;

      if (temp^.next = nil) then

        DataSG.Cells[2, i] := '-1'

      else

        DataSG.Cells[2, i] := IntToStr(temp^.next.key);

      temp := temp^.next;

    until i = count;

  end

    else

      ClearTable(DataSG);

end;

procedure ClearTable(var DataSG : TStringGrid);

begin

  DataSg.RowCount := 2;

  DataSG.Cells[0, 1] := '';

  DataSG.Cells[1, 1] := '';

  DataSG.Cells[2, 1] := '';

end;

procedure InsertElementInBegin(var el : link; var first : link);

begin

  if first = nil then

  begin

    first := el          

  end

    else

  begin

    el^.next := first; 

    first := el;

  end;

end;

procedure InsertElementInEnd(var el : link; var first : link);

var

  temp : link;

begin

  if first = nil then

  begin

    first := el

  end

    else

  begin

    temp := first;

    while temp^.next <>nil do

      temp := temp^.next;

    temp^.next := el;

    el^.next := nil;

  end;

end;

procedure InsertPostIndex(var el : link; var first : link; var index : integer);

var

  temp1, temp2 : link;

  k, count : integer;

begin

  count := CounterElement(first);

 

  if (index < 1) or (index > count) then

  begin

    ShowMessage('Индекс задан некорректно!');

    Exit;

  end

    else

  begin

    if index = 1 then

    begin                  

      temp1 := first;

      temp2 := temp1^.next;

      temp1^.next := el;

      el^.next := temp2;

    end

      else

    if (index = count) then        

    begin