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

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

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

Примеры создания приложений

9.1 Использование динамических массивов

Задание: создать приложение для вычисления наименьшего и наибольшего из всех значений элементов целочисленной матрицы A={a_ij}, где i=1,2,…, m; j=1,2,…, n. Значения m и n задаются пользователем на панели интерфейса, а элементы матрицы A генерируются с помощью датчика случайных чисел и размещаются в памяти динамически.

Один из возможных вариантов панели интерфейса создаваемого приложения показан на рис.9.1.

9.1.1. Размещение компонентов на Форме

Разместим на Форме компоненты Label, SpinEdit, Button и StringGrid.

Label

SpinEdit

Label

StringGrid

Button

Label

Рис. 9.1

Сохраним модуль под именем UnDinMas (текст модуля приведен в п.9.1.3).

9.1.2 Создание процедур обработки событий FormCreate и Button1Click

Двойным нажатием клавиши “мыши” на Форме и кнопке Button1 создайте соответствующие процедуры обработки событий. Пользуясь текстом модуля UnDinMas, внимательно наберите операторы этих процедур.

При желании можно создать процедуру, которая будет выделять заданным цветом границы ячеек с наименьшим и наибольшим значениями в компоненте StringGrid. Для создания такой процедуры сделайте активным компонент StringGrid и на странице Events(события) Инспектора Объектов дважды щелкните “мышью” в правой части события OnDrawCell. В ответ Delphi создаст обработчик этого события – процедуру procedure TForm1.StringGrid1DrawCell и установит курсор между операторами begin и end этой процедуры. Используя текст модуля UnDinMas, внимательно наберите операторы процедуры TForm1.StringGrid1DrawCell.

9.1.3 Текст модуля UnDinMas

Unit UnDinMas;

interface

uses

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

StdCtrls, Spin, Grids, Buttons;

type

TForm1 = class(TForm)

Label1: TLabel;

SpinEdit1: TSpinEdit;

SpinEdit2: TSpinEdit;

Label8: TLabel;

StringGrid1: TStringGrid;

Label2: TLabel;

Label5: TLabel;

Label3: TLabel;

Button1: TButton;

Label4: TLabel;

Label6: TLabel;

Label7: TLabel;

Label9: TLabel;

procedure FormCreate(Sender: TObject);

procedure SpinEdit1Change(Sender: TObject);

procedure SpinEdit2Change(Sender: TObject);

procedure StringGrid1DrawCell(Sender: TObject; Col, Row: Integer;

Rect: TRect; State: TGridDrawState);

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.DFM}

Type

Mas=array[1..1] of integer; // массив целочисленных значений

pMas=array[1..1] of ^mas; // массив указателей

var // объявление глобальных переменных

pA:^pMas; // указатель на массив указателей

m,n,max,min:integer;

procedure TForm1.FormCreate(Sender: TObject);

begin

m:=6; // начальное значение m

n:=8; // начальное значение n

SpinEdit1.Text:='6';

SpinEdit2.Text:='8';

StringGrid1.RowCount:=m; // количество строк

StringGrid1.ColCount:=n; // количество столбцов

end;

procedure TForm1.SpinEdit1Change(Sender: TObject);

begin

m:=StrToInt(SpinEdit1.Text);// m присваивается содержимое поля редактора

StringGrid1.RowCount:=m;

end;

procedure TForm1.SpinEdit2Change(Sender: TObject);

begin

n:=StrToInt(SpinEdit2.Text);// n присваивается содержимое поля редактора

StringGrid1.ColCount:=n;

end;

procedure TForm1.Button1Click(Sender: TObject);

label 1;

var

i,j,k,l,r:integer;

begin

Randomize; // инициализация датчика случайных чисел

GetMem(pA,4*m); // выделение памяти для массива из m указателей

for i :=1 to m do

begin // формирование i-й строки массива

{ Выделение памяти для n элементов i-й строки}

GetMem(pA^[i],SizeOf(integer)*n);

pA^[1]^[1]:=Random(1000);// случайное целое число занести в массив

for j:=1 to n do

begin // формирование j-го элемента строки

1: r:=Random(1000); // генерирование случайного числа

for k:=1 to i do

for l:=1 to j do

if r=pA^[k]^[l] then // если такое число уже есть в массиве тогда...

goto 1;

pA^[i]^[j]:=r; // случайное число занести в массив

end;

end;

for i:=1 to m do // элементы массива занести в ячейки

for j:=1 to n do // компонента StringGrid1

StringGrid1.Cells[j-1,i-1]:=IntToStr(pA^[i]^[j]);

{ Поиск min и max значений среди элементов массива}

max:=pA^[1]^[1];

min:=max;

for i:=1 to m do

for j:=1 to n do

if pA^[i]^[j]then

min:=pA^[i]^[j]

else

if pA^[i]^[j]>max then

max:=pA^[i]^[j];

Label7.Caption:=IntToStr(min); // вывод min значения

Label9.Caption:=IntToStr(max); // вывод max значения

for i:=1 to m do

{ Освобожение памяти, занимаемой n элементами i-й строки}

FreeMem(pA^[i],SizeOf(integer)*n);

{ Освобождение памяти, занимаемой массивом из m указателей}

FreeMem(pA,4*m);

end;

procedure TForm1.StringGrid1DrawCell(Sender: TObject; Col, Row: Integer;

Rect: TRect; State: TGridDrawState);

begin

with StringGrid1.Canvas do

if StringGrid1.Cells[Col,Row]=IntToStr(min) then // если элемент ячейки

begin // равен min тогда...

Brush.Color:=clGreen; // установить цвет кисти зеленый

FrameRect(Rect); // выделить границы ячейки заданным цветом

end

else

if StringGrid1.Cells[Col,Row]=IntToStr(max) then // если элемент ячейки

begin // равен max тогда...

Brush.Color:=clRed; // установить цвет кисти красный

FrameRect(Rect); // выделить границы ячейки заданным цветом

end

end;

end.

9.2 Использование динамических списков

Задание2: создать приложение для формирования стека, который заполняется путем ввода целых положительных чисел с клавиатуры. Как только будет введено первое отрицательное число, содержимое стека выводится на панель интерфейса, а память занимаемая его элементами освобождается.

Один из возможных вариантов панели интерфейса создаваемого приложения показан на рис.9.2.

9.2.1. Размещение компонентов на Форме

Разместим на Форме компоненты Label, Edit, Button и Memo.

Label

Memo

Edit

Button

Рис. 9.2

Сохраним модуль под именем UnStek (текст модуля приведен в п.9.2.3).

9.2.2 Создание процедур обработки событий FormCreate и Button1Click

Двойным нажатием клавиши “мыши” на Форме и кнопке Button1 создайте соответствующие процедуры обработки событий. Используя текст модуля UnStek, внимательно наберите операторы этих процедур.

9.2.3 Текст модуля UnStek

Unit UnStek;

interface

uses

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

StdCtrls;

type

TForm1 = class(TForm)

Label1: TLabel;

Edit1: TEdit;

Button1: TButton;

Label2: TLabel;

Label3: TLabel;

Memo1: TMemo;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.DFM}

Type

PSt=^Zap;

Zap=record

inf:integer;

adr:PSt

end;

Var // объявление глобальных переменных:

PVer, // указатель вершины стека

PTek:PSt; // текущий указатель

ElSt:integer; // элемент стека

procedure TForm1.Button1Click(Sender: TObject);

begin

New(PTek); // выделить память

ElSt:=StrToInt(Edit1.Text);// в ElSt занести значение из Edit1

PTek^.inf:=ElSt; // в информационную часть стека занести ElSt

PTek^.adr:=PVer; // в адресную часть занести указатель на вершину

PVer:=PTek;// указатель вершины должен указывать на последний элемент

if ElSt>=0 then // если элемент стека неотрицательный тогда...

begin

Edit1.Text:='';// очистить окно редактора Edit1

Edit1.SetFocus;// передать фокус ввода редактору Edit1

end

else

begin

Memo1.Lines.Add('Элементы стека:'); // вывести заголовок

repeat

Memo1.Lines.Add(#9+IntToStr(PTek^.inf));// вывод элементов

PVer:=PTek^.adr;

Dispose(PTek); // освободить память

PTek:=PVer

until PTek=nil;

end;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

PVer:=nil; // инициализировать указатель вершины

ElSt:=0; // инициализировать элемент стека

end;

end.

9.3. Выполнение индивидуального задания

По указанию преподавателя выберите два варианта индивидуальных заданий. В заданиях №1-№15 необходимо использовать динамические массивы, а в заданиях №16-№30 – динамические списки. Во всех заданиях необходимо предусмотреть контрольный вывод исходных данных.

1. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры, меняет местами элементы с наибольшим и наименьшим значениями среди четных и выводит полученный массив.

2. Создать приложение, которое осуществляет ввод m строк и n столбцов двумерного массива с клавиатуры и выводит номер строки и номер столбца наименьшего из всех значений его элементов.

3. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры и выводит порядковый номер элемента с наименьшим значением среди нечетных.

4. Создать приложение, которое осуществляет ввод значений элементов двумерного массива n-го порядка с клавиатуры и выводит значение наибольшего из элементов главной диагонали.

5. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры, изменяет порядок следования элементов на противоположный и выводит полученный массив.

6. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры и выводит порядковый номер элемента с наибольшим значением среди четных.

7. Создать приложение, которое осуществляет ввод значений элементов двумерного массива n-го порядка с клавиатуры и выводит значение суммы элементов главной диагонали.

8. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры, меняет местами элементы с минимальным и максимальным значениями и выводит полученный массив.

9. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры и выводит порядковый номер элемента с наименьшим значением среди положительных.

10. Создать приложение, которое осуществляет ввод значений элементов двумерного массива n-го порядка с клавиатуры, изменяет порядок следования элементов главной диагонали на противоположный и выводит преобразованный массив.

11. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры, меняет местами элементы с минимальным и максимальным значениями среди положительных и выводит полученный массив.

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

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

14. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры и выводит среднее арифметическое значение элементов массива.

15. Создать приложение, которое осуществляет ввод k значений элементов одномерного массива с клавиатуры, меняет местами элементы с наименьшим значением среди четных и наибольшим среди нечетных и выводит полученный массив.

16. Создать приложение, которое заносит в стек целые положительные числа с клавиатуры, выводит содержимое стека и среднее арифметическое значение его элементов.

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

18. Создать приложение, которое заносит в каждый элемент стека английское слово с клавиатуры и, как только будет введено слово “end”, выводит содержимое стека.

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

20. Создать приложение, которое заносит в стек символы с клавиатуры, выводит содержимое стека и сообщение о том, упорядочены ли элементы стека по алфавиту или нет.

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