Библиографический список
Архангельский АЯ Программирование в C++Builder 6. – М: ЗАО «Издательство БИНОМ», 2003 – 1152 с – С 25–29 42–89, 941–942 960
Лабораторная работа 1
ФОРМИРОВАНИЕ И ОБРАБОТКА ДИНАМИЧЕСКИХ МАССИВОВ
ОДНОМЕРНЫЕ МАССИВЫ
Формирование динамического массива осуществляется в два этапа: на первом – выделяют под массив динамическую память, на втором – инициализируют (заполняют данными) выделенную память. После обработки массива и получения результатов использованную память необходимо освобождать. Выделение и освобождение динамической памяти под массив производится по указателю при помощи операций new и delete соответственно. Контроль за правильностью выполнения операции выделения динамической памяти осуществляется с помощью макроса assert, определенного в файле <assert.h>. Например,
int n, *iptr; // n – размер массива
------------ инициализация n -------------
iptr = new int[n];
assert(iptr!=0);
// инициализация элементов массива случайными числами
// в диапазоне значений от -9 до 9
for(int i=0: i<n; i++)
iptr[i]= (rand()-16383)%10; }
--------- обработка динамического массива --------
delete[]iptr;
iptr=0;
Операция new выделяет непрерывный участок динамической памяти под массив длиной n, состоящий из целых чисел, и возвращает адрес этого участка, т.е. адрес элемента массива с индексом 0 – iptr[0]. Если память не выделена, то значение указателя iptr окажется равным нулю, а значение выражения iptr!=0 – ложным (нулевым). Тогда макрос assert прерывает выполнение программы. При завершении работы выводится сообщение об ошибке вида: Assertion failed: expression, file <имя файла>, line <номер строки>. После того, как отладка программы будет закончена и макросы assert будут больше не нужны, в начале программы достаточно добавить строку #define NDEBUG вместо того, чтобы удалять в программе каждый макрос assert вручную. Операция delete объявляет участок памяти под массивом свободным. После применения операции delete указатель рекомендуется обнулять, с целью защиты программного продукта.
ДВУМЕРНЫЕ МАССИВЫ (МАТРИЦЫ)
Выделение и освобождение динамической памяти для размещения двумерного массива (матрицы) выполняется, например, следующим образом.
int n, m, **iptr; // n – число строк, m – число столбцов матрицы
------------ инициализация n, m -------------
// выделение памяти под массив указателей на строки
iptr=new int*[n];
assert(iptr!=0);
for(int i=0; i<n; i++) {
// выделение памяти под i – ю строку
iptr[i]=new int[]m;
assert(iptr[i]!=0);
for(int j=0; j<m; j++)
// инициализация строк матрицы случайными
// числами в диапазоне значений от -99 до 99
iptr[i][j] = (rand()-16383)%100;
}
------------- обработка динамической матрицы ------------
for(int i=0: i<n; i++)
// освобождение памяти под i – й строкой
delete[]iptr[i];
// освобождение памяти под массивом указателей на строки
delete[]iptr;
iptr=0;
Возможен и другой вариант, когда память выделяется под столбцы. В этом случае приведенный выше фрагмент программы будет выглядеть следующим образом.
int n, m, **iptr; // n – число строк, m – число столбцов матрицы
------------ инициализация n, m -------------
// выделение памяти под массив указателей на столбцы
iptr=new int*[m];
assert(iptr!=0);
for(int j=0; j< m; j++) {
// выделение памяти под j – й столбец
iptr[j]=new int[]n
assert(iptr[j]!=0);
for(int i=0: i<n; i++)
// инициализация столбцов матрицы случайными
// числами в диапазоне значений от -99 до 99
iptr[j][i]= (rand()-16383)%100; }
------------- обработка динамической матрицы ------------
for(int j=0; j<m; j++)
// освобождение памяти под j– м столбцом
delete[]iptr[j];
// освобождение памяти под массивом указателей на столбцы
delete[]iptr;
iptr=0;
Задания
1. В одномерном массиве нулевые элементы удалить, положительные элементы расставить по убыванию, отрицательные - по возрастанию. Получить зависимость затрат машинного времени от размера массива.
2. В матрице удалить строки с последними отрицательными элементами, а затем добавить строку из сумм элементов по столбцам.
Проектирование приложения.
Выбор, размещение и задание свойств компонентов.
Коды обработчиков событий и функций.
Запустите C++Builder 6.
Создайте новый проект командой Файл/Новый/Приложение.
Сохраните файлы модуля и проекта командой Файл/Сохранить все под именами LR_1 и PR_LR_1 в каталоге ТЕХН_ПРОГР. Для этого удобно использовать соответствующую быструю кнопку (Сохранить все). В последующих сеансах работы сохраненный проект можно открыть командой Файл/Открыть проект (или Повторно открыть). Теперь перейдем к проектированию приложения - переносам на форму необходимых компонентов и заданию их свойствам значений, а в обработчиках событий – размещению кодов соответствующих алгоритмов. (Рекомендуется нажимать кнопку Сохранить все по окончании работы с каждым компонентом.) В результате проектирования получим форму, представленную на рис.1.1,2,3.
Выделите форму, щелкнув на ней левой кнопкой мыши, и в свойство Caption (надпись) впишите ДИНАМИЧЕСКИЕ МАССИВЫ
Вначале перенесите на форму многостраничную панель – компонент PageControl1 (страница Win32). Для размещения остальных компонентов приложения достаточно использовать две страницы компонента – по заданиям 1 и 2 соответственно.
Щелкните на компоненте PageControl1 правой кнопкой мыши и во всплывшем меню дважды используйте команду Новая страница. В свойство Caption первой страницы впишите массив, второй – матрица. Установите свойства компонента PageControl1: MultiLine – false, Style – tsTabs, TabPosition – tpTop.
Рис.1.1
Рис.1.2
Рис.1.3
Перенесите на первую страницу (массив) компонент PageControl2 и, как и в PageControl1, создайте две страницы, с надписями тестирование и использование и графики соответственно.
На страницу тестирование и использование (рис.1.1) перенесите 7 меток Label (страница Стандарт), в свойство Caption (надпись) которых соответственно впишите размер массива, начальный, конечный, шаг, диапазон чисел, макс, мин; 5 компонентов ввода целых чисел – CSpinEdit (страница Примеры) для задания параметров формируемых массивов. У компонента CSpinEdit1, расположенного правее метки начальный, занесите в свойство MaxValue – 1000, MinValue – 1, Value – 10; правее метки конечный(CSpinEdit2) - MaxValue – 10000, MinValue – 1, Value – 10; правее метки шаг(CSpinEdit3) - MaxValue – 1000, MinValue – 0, Value – 1, правее метки макс(CSpinEdit4) - MaxValue – 99, MinValue – -99, Value – 9, правее метки мин(CSpinEdit5) - MaxValue – 99, MinValue – -99, Value – - 9. Для разрешения или запрещения вывода на экран исходных и результирующих массивов, а также графиков полученных зависимостей, в правую верхнюю часть страницы перенесите 2 компонента-индикатора CheckBox (страница Стандарт), в свойство Caption которых впишите соответственно вывод в таблицу и графики, а свойство Alignment обоих компонентов установите в taRightJustify. Ниже индикаторов CheckBox поместите панель Panel1( страница Стандарт) для вывода в нее сообщений: Макс значение не м.б. меньше мин значения!, В массиве только нули!, Кол-во сравнений = <число> Кол-во обменов = <число> . Очистите свойство Caption у панели Для вывода массивов на экран при тестировании перенесите на страницу компонент StringGrid1 (страница Дополнительно). Установите следующие значения свойств компонента StringGrid1: ColCount – 11, DefaultColWidth -24, FixedCols – 1, FixedRows – 0, Font – черный, обычный, размер 8, RowCount – 8. Правее компонента StringGrid1 разместите 2 кнопки (страница Стандарт) с надписями соответственно: Button1 – ПУСК1, Button2 – СБРОС1. Для отображения процесса обработки массива ниже компонента StringGrid1 поместите компонент ProgressBar1 (страница Win32). Еще ниже поместите компонент StatusBar1 (страница Win32), который представляет собой ряд панелей, отображающих полосу состояния. Поскольку в нашем случае достаточно одной панели (для одного сообщения), то установите свойство SimplePanel = true. Свойство SimpleText представляет собой текст, который задается во время проектирования или программно (в нашем случае во время проектирования). Итак, в свойство SimpleText впишем кратко задание 1: Нули - удалить, "+" - элементы расставить по убыванию, "-" - по возрастанию.
Затраты машинного времени на обработку массива оценивают косвенно – по количествам сравнений и обменов. Для вывода на экран зависимостей количеств сравнений и обменов от размера массива, на страницу графики (рис.1.2) компонента PageControl2 перенесите компоненты Chart1 и Chart2 (страница Additional). Задайте свойства компонента Chart1. Для этого щелкните правой кнопкой мыши на компоненте Chart1 и в появившемся меню выберите Edit Chart…. На экране появится окно Редактора Диаграмм (Editing Chart1) с открытой страницей Chart, которая имеет несколько закладок. В данный момент открыта закладка Series. Щелкните на кнопке Add… - добавить серию. В появившемся окне выберите тип графика – Line и выключите индикатор 3D. На закладке Panel, нажав кнопку Panel Color…, выберите белый цвет. Перейдите на закладку Titles. В окне редактирования, которое в данный момент соответствует Title – заголовку графика, сотрите TChart и напишите (шрифт Font… - черный, жирный, размер 8) количество сравнений. Цвет фона Back Color.. установите белый. В выпадающем списке от окна редактирования Title перейдите в окно редактирования Foot и напишите тем же шрифтом размер массива. Цвет фона Back Color.. также установите белый. Нажмите кнопку Close и выйдите из режима редактирования компонента Chart1. Свойства компонента Chart2 задаются так же.
Перейдем к обработчикам событий – щелчков на кнопках ПУСК1 и СБРОС1. В первом - размещен алгоритм формирования и обработки массива по заданию 1, а также вывод сообщений и результатов в виде таблицы и графиков, а во втором – подготовка компонентов к выводу новых сообщений и новых результатов. Перед, после и в обработчике щелчка на кнопке ПУСК1 напишите (курсив):
int i=0,*vptr=0;
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Series1->Clear();
Series2->Clear();
void __fastcall sort(int*p,int n);
Panel1->Caption="";
if(CSpinEdit4->Value<CSpinEdit5->Value){
Panel1->Caption="Макс значение не м.б. меньше мин значения!";
return;}
int count,current=0;
count=(CSpinEdit2->Value-CSpinEdit1->Value)/CSpinEdit3->Value+1;
for(int n=CSpinEdit1->Value;n<=CSpinEdit2->Value;n+=CSpinEdit3->Value)
{
vptr=new int[n];
assert(vptr!=0);
for(int j=0;j<n;j++)
vptr[j]=random(CSpinEdit4->Value-CSpinEdit5->Value+1)+
CSpinEdit5->Value;
if(CheckBox1->Checked){
StringGrid1->Cells[0][i]="Исходный массив";
for(int j=0;j<n;j++)
StringGrid1->Cells[j+1][i]=IntToStr(vptr[j]);
i++;}
sort(vptr,n);
current+=1;
ProgressBar1->Position=100*current/count;
delete[]vptr;
}
vptr=0;
}
//---------------------------------------------------------------------------
void __fastcall sort(int*p,int n)
{
int k=0,sr=0,obm=0,m=n;
void __fastcall swap(int&x,int&y);
for(int j=0;j<n;j++)
if(!p[j])k++;
else p[j-k]=p[j];
n-=k;
sr+=n;
if(!n){Form1->Panel1->Caption="В массиве только нули!"; return;}
for(int m=0;m<n-1;m++)
for(int j=m+1;j<n;j++){
if(p[m]>0&&p[j]>0&&p[m]<p[j]){swap(p[m],p[j]);obm++;}
if(p[m]<0&&p[j]<0&&p[m]>p[j]){swap(p[m],p[j]);obm++;}
sr+=6;}
if(Form1->CheckBox1->Checked){
Form1->StringGrid1->Cells[0][i]="Получен массив";
for(int j=0;j<n;j++)
Form1->StringGrid1->Cells[j+1][i]=IntToStr(p[j]);
i++;}
if(Form1->CSpinEdit1->Value==Form1->CSpinEdit2->Value)
Form1->Panel1->Caption=
"Кол-во сравнений = "+IntToStr(sr)+
" Кол-во обменов = "+IntToStr(obm);
if(Form1->CheckBox2->Checked){
Form1->Series1->AddXY(m,sr,"",clBlack);
Form1->Series2->AddXY(m,obm,"",clBlack);}
}
//-----------------------------------------------------
void __fastcall swap(int&x,int&y)
{int z=x;x=y;y=z;}
В обработчике щелчка на кнопке СБРОС1 напишите (курсив):
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Panel1->Caption="";
ProgressBar1->Position=0;
for(int k=0;k<StringGrid1->RowCount;k++)
for(int j=0;j<StringGrid1->ColCount;j++)
StringGrid1->Cells[j][k]="";
i=0;
Series1->Clear();
Series2->Clear();
}
Перенесите на вторую страницу (матрица) компонента PageControl1 (рис.1.3) 8 меток Label (страница Стандарт), в свойство Caption (надпись) которых впишите значения размеры, число строк, число столбцов, диапазон чисел, макс, мин, исходная матрица, матрица-результат; 4 компонента ввода целых чисел – CSpinEdit6…9 (страница Примеры) для задания параметров формируемых матриц. У компонента, расположенного правее метки число строк (CSpinEdit6), занесите в свойство MaxValue – 100, MinValue – 1, Value – 10; правее метки число столбцов(CSpinEdit7) - MaxValue – 100, MinValue – 1, Value – 10; правее метки макс(CSpinEdit8) - MaxValue – 99, MinValue – -99, Value – 9, правее метки мин (CSpinEdit9) - MaxValue – 99, MinValue – -99, Value – -9. Перенесите также 2 кнопки Button1,2 (страница Стандарт) с надписями ПУСК2, СБРОС2. Сюда же поместите панель Panel2 (страница Стандарт) для вывода в панель сообщений: Макс не м.б. меньше мин!, В матрице удалены все строки!, В матрице нет удаленных строк!, В матрице удалено <кол-во> строк(и)!. Очистите свойство Caption у панели Кроме того, на этой странице разместите две таблицы - компоненты StringGrid1,2 (страница Дополнительно) - для вывода матриц – исходной и матрицы-результата. Задайте следующие значения свойств обоих компонентов StringGrid: ColCount – 10, DefaultColWidth - 32, FixedCols – 0, FixedRows – 0, Font – черный, обычный, размер 8, RowCount – 10. И, наконец, в нижней части страницы поместите компонент StatusBar2 (страница Win32). Установите свойство SimplePanel = true. В свойство SimpleText впишите кратко задание 2: Строки с "-" на конце - удалить, а затем добавить строку из сумм по столбцам.
В обработчике щелчка на кнопке ПУСК2 находится алгоритм формирования и обработки динамической матрицы согласно заданию 2 с выводом результатов и сообщений, а в обработчике щелчка на кнопке СБРОС2 - зачистка выведенных результатов и сообщений (курсив):
int n,m;
void __fastcall TForm1::Button3Click(TObject *Sender)
{int i,j,**ptr,k,q;
Panel2->Caption="";
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
StringGrid2->Cells[j][i]="";
StringGrid3->Cells[j][i]="";}
if(CSpinEdit8->Value<CSpinEdit9->Value){
Panel2->Caption="Макс не м.б. меньше мин!";
return;}
n=CSpinEdit6->Value;
m=CSpinEdit7->Value;
ptr=new int*[n];
assert(ptr!=0);
for(i=0;i<n;i++){
ptr[i]=new(int[m]);
assert(ptr[i]!=0);
for(j=0;j<m;j++){
ptr[i][j]=random(CSpinEdit8->Value-CSpinEdit9->Value+1)
+CSpinEdit9->Value;
StringGrid2->Cells[j][i]=IntToStr(ptr[i][j]);}}
q=0;
k=0;
do{
if(ptr[q][m-1]<0){
delete[]ptr[q];
for(i=q;i<n-k-1;i++)ptr[i]=ptr[i+1];
k++; continue;}
q++;}
while(q+k<n);
if(k==n){Panel2->Caption=
"В матрице удалены все строки!"; return;}
if(k==0){Panel2->Caption=
"В матрице нет удаленных строк!";return;}
Panel2->Caption="В матрице удалено "+IntToStr(k)+" строк(и)!";
for(i=0;i<n-k;i++)
for(j=0;j<m;j++){
StringGrid3->Cells[j][i]=IntToStr(ptr[i][j]);}
ptr[n-k]=new(int[m]);
assert(ptr[n-k]!=0);
for(j=0;j<m;j++){
ptr[n-k][j]=0;
for(i=0;i<n-k;i++)
ptr[n-k][j]+=ptr[i][j];}
for(i=0;i<=n-k;i++)
for(j=0;j<m;j++){
StringGrid3->Cells[j][i]=IntToStr(ptr[i][j]);}
for(i=0;i<=n-k;i++)delete[]ptr[i];
delete[]ptr;
ptr=0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)
{
Panel2->Caption="";
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
StringGrid2->Cells[j][i]="";
StringGrid3->Cells[j][i]="";}
}
//---------------------------------------------------------------------------
По окончании проектирования файл LR_1.cpp может выглядеть так:
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "LR_1.h"
#include<assert.h>
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma link "CSPIN"
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
int i=0,*vptr=0;
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Series1->Clear();
Series2->Clear();
void __fastcall sort(int*p,int n);
Panel1->Caption="";
if(CSpinEdit4->Value<CSpinEdit5->Value){
Panel1->Caption="Макс значение не м.б. меньше мин значения!";
return;}
int count,current=0;
count=(CSpinEdit2->Value-CSpinEdit1->Value)/CSpinEdit3->Value+1;
for(int n=CSpinEdit1->Value;n<=CSpinEdit2->Value;n+=CSpinEdit3->Value)
{
vptr=new int[n];
assert(vptr!=0);
for(int j=0;j<n;j++)
vptr[j]=random(CSpinEdit4->Value-CSpinEdit5->Value+1)+
CSpinEdit5->Value;
if(CheckBox1->Checked){
StringGrid1->Cells[0][i]="Исходный массив";
for(int j=0;j<n;j++)
StringGrid1->Cells[j+1][i]=IntToStr(vptr[j]);
i++;}
sort(vptr,n);
current+=1;
ProgressBar1->Position=100*current/count;
delete[]vptr;
}
vptr=0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Panel1->Caption="";
ProgressBar1->Position=0;
for(int k=0;k<StringGrid1->RowCount;k++)
for(int j=0;j<StringGrid1->ColCount;j++)
StringGrid1->Cells[j][k]="";
i=0;
Series1->Clear();
Series2->Clear();
}
//---------------------------------------------------------------------------
void __fastcall sort(int*p,int n)
{
int k=0,sr=0,obm=0,m=n;
void __fastcall swap(int&x,int&y);
for(int j=0;j<n;j++)
if(!p[j])k++;
else p[j-k]=p[j];
n-=k;
sr+=n;
if(!n){Form1->Panel1->Caption="В массиве только нули!"; return;}
for(int m=0;m<n-1;m++)
for(int j=m+1;j<n;j++){
if(p[m]>0&&p[j]>0&&p[m]<p[j]){swap(p[m],p[j]);obm++;}
if(p[m]<0&&p[j]<0&&p[m]>p[j]){swap(p[m],p[j]);obm++;}
sr+=6;}
if(Form1->CheckBox1->Checked){
Form1->StringGrid1->Cells[0][i]="Получен массив";
for(int j=0;j<n;j++)
Form1->StringGrid1->Cells[j+1][i]=IntToStr(p[j]);
i++;}
if(Form1->CSpinEdit1->Value==Form1->CSpinEdit2->Value)
Form1->Panel1->Caption=
"Кол-во сравнений = "+IntToStr(sr)+
" Кол-во обменов = "+IntToStr(obm);
if(Form1->CheckBox2->Checked){
Form1->Series1->AddXY(m,sr,"",clBlack);
Form1->Series2->AddXY(m,obm,"",clBlack);}
}
//-----------------------------------------------------
void __fastcall swap(int&x,int&y)
{int z=x;x=y;y=z;}
//-----------------------------------------------------
int n,m;
void __fastcall TForm1::Button3Click(TObject *Sender)
{int i,j,**ptr,k,q;
Panel2->Caption="";
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
StringGrid2->Cells[j][i]="";
StringGrid3->Cells[j][i]="";}
if(CSpinEdit8->Value<CSpinEdit9->Value){
Panel2->Caption="Макс не м.б. меньше мин!";
return;}
n=CSpinEdit6->Value;
m=CSpinEdit7->Value;
ptr=new int*[n];
assert(ptr!=0);
for(i=0;i<n;i++){
ptr[i]=new(int[m]);
assert(ptr[i]!=0);
for(j=0;j<m;j++){
ptr[i][j]=random(CSpinEdit8->Value-CSpinEdit9->Value+1)
+CSpinEdit9->Value;
StringGrid2->Cells[j][i]=IntToStr(ptr[i][j]);}}
q=0;
k=0;
do{
if(ptr[q][m-1]<0){
delete[]ptr[q];
for(i=q;i<n-k-1;i++) ptr[i]=ptr[i+1];
k++; continue;}
q++;}
while(q+k<n);
if(k==n){Panel2->Caption=
"В матрице удалены все строки!"; return;}
if(k==0){Panel2->Caption=
"В матрице нет удаленных строк!";return;}
Panel2->Caption="В матрице удалено "+IntToStr(k)+" строк(и)!";
for(i=0;i<n-k;i++)
for(j=0;j<m;j++){
StringGrid3->Cells[j][i]=IntToStr(ptr[i][j]);}
ptr[n-k]=new(int[m]);
assert(ptr[n-k]!=0);
for(j=0;j<m;j++){
ptr[n-k][j]=0;
for(i=0;i<n-k;i++)
ptr[n-k][j]+=ptr[i][j];}
for(i=0;i<=n-k;i++)
for(j=0;j<m;j++){
StringGrid3->Cells[j][i]=IntToStr(ptr[i][j]);}
for(i=0;i<=n-k;i++)delete[]ptr[i];
delete[]ptr;
ptr=0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)
{
Panel2->Caption="";
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
StringGrid2->Cells[j][i]="";
StringGrid3->Cells[j][i]="";}
}
//--------------------------------------------------------------------------------------------------