Новости

Приложение для сортировки числового массива с помощью кучи

Работа добавлена:






Приложение для сортировки числового массива с помощью кучи на http://mirrorref.ru

Содержание

1. Введение

1.1. Задание на курсовую работу

Разработать приложение для сортировки числового массива с помощью кучи. Во время выполнения данной курсовой работы должны учитываться следующие требования:

  • Разработать оконное приложение в средеBorlandC++Builder или .Net;
  • Полная справочная информация по данной теме;
  • Сохранение данных в файл (при необходимости);
  • Подсказки пользователю;
  • Обязательный контроль введенной пользователем информации;
  • Контроль доступа к операциям;
    • Информирование пользователя об ошибках (факт ошибки и причина) и указывать допустимые значения.

1.2. Постановка задачи

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

Во время выполнения приложения ведётся диалог с пользователем. Пользователь должен ввести в память компьютера числовые данные (массив элементов), которые необходимо отсортировать. Предварительно задаётся количество элементов. Также данные могут быть введены автоматически с помощью генератора случайных чисел. После выполнения необходимых операций на экран будут выведены массива. В первом элементы отсортированы по возрастанию, во втором – по убыванию.

Интерфейс приложения должен обеспечивать выполнение следующих действий:

  • Ввод количества элементов;
  • Выбор способа задания массива (вручную или автоматически);
  • Просмотр справочных сведений о приложении;
  • Помощь пользователю в работе с приложением;
  • Выход из приложения.

В приложении должны быть предусмотрены следующие возможные ошибки пользователя:

  • Ввод слишком большого количества элементов массива;
  • Ввод буквенных символов вместо чисел;

2. Описание метода и алгоритм решения задачи

2.1. Последовательность решения задачи и числовой пример использования алгоритма.

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

  1. Кучи

Двоичной кучей(binaryheap) называют массив с определёнными свойствами упорядоченности. Чтобы сформулировать эти свойства, будем рассматривать массив как двоичное дерево (рис. 2.1). Каждая вершина дерева соответствует элементу массива. Если вершина имеет индексi, то её родитель имеет индекс [i/2] (вершина с индексом 1 является корнем), а её дети – индексы 2i и 2i+1. Будем считать, что куча может не занимать всего массива, и поэтому будем хранить не только массив А и его длинуlength[А], но также специальный параметрheap-size[А] (размер кучи), причёмheap-size[А] ≤length[А]. Куча состоит из элементов А[1],…,A[heap-size[A]]. Движение по дереву осуществляется процедурами :

Parent(i)

return [i/2]

Left(i)

return 2i

Right(i)

return 2i+1

(а)       (б)

Кучу можно рассматривать как дерево (а) или как массив (б). Внутри вершины показано её значение. Около вершины показан её индекс в массиве.

Рисунок 2.1.

Элемент А[1] является корнем дерева.

Элементы, хранящиеся в куче, должны обладатьосновным свойством кучи(heapproperty): для каждой вершиныi, кроме корня (т.е. при 2 ≤iheap-size[A]),

A[Parent(i)] ≥ A[i].(1)

Отсюда следует, что значение потомка не превосходит значения предка. Таким образом, наибольший элемент дерева (или любого поддерева) находится в корневой вершине дерева (этого поддерева).

Высотой(height) вершины дерева называется высота поддерева с корнем в этой вершине (число рёбер в самом длинном пути с началом в этой вершине вниз по дереву к листу). Высота дерева, таким образом, совпадает с высотой его корня. В дереве, составляющем кучу, все уровни (кроме, быть может, последнего) заполнены полностью.

Перечислим основные операции над кучей:

  • Процедура Heapify позволяет поддерживать основное свойство (1).
  • Процедура Build-Heap строит кучу из исходного (неотсортированного) массива.
  • Процедура Heapsort сортирует массив, не используя дополнительной памяти.

  1. Сохранение основного свойства кучи

ПроцедураHeapify – важное средство работы с кучей. Её параметрами являются массив А и индексi. Предполагается, что поддеревья с корнямиLeft(i) иRight(i) уже обладают основным свойством. Процедура переставляет элементы поддерева с вершиной i, после чего оно будет обладать основным свойством. Идея проста: если основное свойство не выполнено для вершины i, то её следует поменять с большим из её детей и т.д., пока элемент А[i] не "погрузится" до нужного места.

Heapify(A,i)

  1. l ← Left(i)
  2. r ← Right(i)
  3. if l ≤ heap-size[A]и A[l] > A[i]
  4.  then largest ← l
  5.  else largest ← i
  6. If r ≤ heap-size[A]и A[r] > A[largest]
  7.  then largest ← r
  8. If largest ≠ i
  9.  thenобменять A[i] ↔ A[largest]
  10.  Heapify(A, largest)

Работа процедурыHeapify показана на рис. 2.2. В строках 3-7 в переменнуюlargest помещается индекс наибольшего из элементов А[i], А[Left(i)] иA[Right(i)]. Еслиlargest=i, то элемент А[i] уже "погрузился" до нужного места, и работа процедуры закончена. Иначе процедура меняет местами А[i] и А[largest] (что обеспечивает выполнение свойства (1) в вершине i, но, возможно, нарушает это свойство в вершинеlargest) и рекурсивно вызывает себя для вершиныlargest, чтобы исправить возможные нарушения.

(а)      (в)

  (б)

Работа процедуры Heapify(A,2) при heap-size[A]=10. (а) Начальное состояние кучи. В вершине i=2 основное свойство нарушено. Чтобы восстановить его, необходимо поменять А[2] и А[4]. После этого (б) основное свойство нарушается в вершине с индексом 4. Рекурсивный вызов процедуры Heapify(A,4) восстанавливает основное свойство в вершине с индексом 4 путём перестановки А[4] ↔ А[9] (в). После этого основное свойство выполнено для всех вершин, так что процедура Heapify(A,9) уже ничего не делает.

Рисунок 2.2.

  1. Построение кучи

Пусть дан массив А[1…n], который мы хотим превратить в кучу, переставив его элементы. Для этого можно использовать процедуруHeapify, применяя её по очереди ко всем вершинам, начиная с нижних. Поскольку вершины с номерами [n/2]+1,…,n являются листьями, поддеревья с этими вершинами удовлетворяют этому свойству. Для каждой из оставшихся вершин, в порядке убывания индексов, мы применяем процедуруHeapify. Порядок обработки вершин гарантирует, что каждый раз условия вызова процедуры (выполнение основного свойства для поддеревьев) будут выполнены.

Build-Heap(A)

  1. heap-size[A] ← length[A]
  2. for i ← [length[A]/2] downto 1
  3.  do Heapify(A, i)

Пример работы процедурыBuild-Heap показан на рис. 2.3.

  (а)       (б)

  (в)       (г)

  (д)       (е)

Работа процедуры Build-Heap. Показано состояние данных перед каждым вызовом процедуры Heapify в строке 3.

Рисунок 2.3.

  1. Алгоритм сортировки с помощью кучи

Алгоритм сортировки с помощью кучи состоит из двух частей. Сначала вызывается процедураBuild-Heap, после выполнения которой массив становится кучей. Идея второй части проста: максимальный элемент массива теперь находится в корне дерева (А[1]). Его следует поменять с А[n], уменьшить размер кучи на 1 и восстановить основное свойство в корневой вершине (поскольку поддеревья с корнямиLeft(1) иRight(1) не утратили основного свойства кучи, это можно сделать с помощью процедурыHeapify). После этого в корне будет находиться максимальный из оставшихся элементов. Так делается до тех пор, пока в куче не останется всего один элемент.

Heapsort(A)

  1. Build-Heap(A)
  2. for i ← length[A] downto 2
  3.  doпоменять A[1] ↔ A[i]
  4.  heap-size[A] ← heap-size[A] – 1
  5.  Heapify(A,1)

Работа второй части алгоритма показана на рис. 2.4. Изображены состояния кучи перед каждым выполнением циклаfor (строка 2).

(а) (б) (в)

(г) (д) (е)

(ж) (з) (и)

(к)  (л)

Работа процедуры Heapsort. Показано состояние массива перед каждым вызовом процедуры Heapify. Затемнённые элементы уже не входят в кучу.

Рисунок 2.4.

2.2. Обобщённая блок-схема алгоритма

ПроцедураHeapsort(A):

2.3. Таблица переменных

Имя переменной

Тип

Назначение

Область действия

i

int

Переменная цикла

Глобальная

j

int

Переменная цикла

Глобальная

kol

int

Количество элементов массива

Глобальная

length

int

Длина массива

Глобальная

heap_size

int

Размер кучи

Глобальная

largest

int

Индекс наибольшего из двух сравниваемых элементов

Глобальная

L

int

Индекс левого потомка элемента

Глобальная

R

int

Индекс правого потомка элемента

Глобальная

c

int

Вспомогательная переменная для смены элементов местами

Локальная

cc

int

Вспомогательная переменная для смены элементов местами

Локальная

*a

int

Неотсортированный массив элементов

Глобальная

*mas

int

Массив элементов

Глобальная

t

AnsiString

Элемент, введённый с клавиатуры

Локальная

3. Структура приложения

4. Распечатки форм и таблицы значений свойств объектов, отличающихся от установленных по умолчанию

Form1

Form2

Form3

Form4

AboutBox

Таблица значений свойств объектов

Элемент

Свойство

Значение

Form1

Caption

"Программа сортировки с помощью кучи"

Position

poScreenCenter

Label1

Alignment

taCenter

Autosize

false

Caption

"Сортировка с помощью кучи"

Transparent

true

Wordwrap

true

MainMenu1

N1

N2

N3

N4

N5

N6

N7

Caption

Caption

Caption

Caption

Caption

Caption

Caption

"С&тарт"

"&Начать работу"

"С&правка"

"&Помощь"

"&О программе"

"&Справка"

"&Выход"

Image1

Picture

(TJPEGImage)

Form2

Caption

"Работа с массивом"

Color

clInactiveCaption

Image 23

Picture

(TJPEGImage)

GroupBox1

Caption

"Ввод массива"

Visible

false

BitBtn1

Caption

"Выход"

Glyph

(TBitmap)

Visible

false

BitBtn2

Caption

"Исходное"

Visible

false

BitBtn3

Caption

"По возрастанию"

Visible

false

BitBtn4

Caption

"По убыванию"

Visible

false

Button1

Caption

"Задать"

Default

true

Visible

false

Button2

Caption

"Отсортировать"

Visible

false

Edit4

MaxLength

2

Text

"10"

Visible

false

Image2

Picture

(TJPEGImage)

Label1

Caption

"Введите количество

элементов:"

Transparent

true

Visible

false

Label25

Alignment

taCenter

Caption

"Отобразить дерево:"

Transparent

true

Visible

false

WordWrap

true

RadioGroup1

Caption

"Способ задания массива"

ItemIndex

1

Items

"Ввод вручную"

"Ввод автоматически"

Visible

false

GroupBox2

Caption

"Сортировка массива"

Visible

false

Edit1

ReadOnly

true

Visible

false

Text

""

Edit2

ReadOnly

true

Visible

false

Text

""

Edit3

ReadOnly

true

Visible

false

Text

""

Image24

Picture

(TJPEGImage)

Label2

Caption

Transparent

"Исходный массив:"

true

Label3

Caption

"Массив, отсортированный по возрастанию:"

Transparent

true

Label24

Caption

"Массив, отсортированный по убыванию:"

Transparent

true

GroupBox3

Caption

"Дерево"

Visible

false

Color

clSkyBlue

Image1

Image43

Picture

(TBitmap)

Transparent

true

Image3…22

Transparent

true

Visible

false

Label4…23

Alignment

taCenter

Caption

""

Transparent

true

Visible

false

MainMenu1

N1

Caption

"&Массив"

N2

Caption

"&Задать"

N4

Caption

"&Справка"

N5

Caption

"&Помощь"

N6

Caption

"&О программе"

N7

Caption

"&Выход"

N8

Caption

"Вернуться в главное &окно"

N9

Caption

"Выход из &программы"

N10

Caption

"&Справка"

Form3

Caption

"Помощь"

Color

clInactiveCaption

Position

poScreenCenter

BitBtn1

Caption

"OK"

Glyph

(TBitmap)

Panel1

Color

clSkyBlue

RichEdit1

Lines

LoadFromFile("Help.rtf")

Form5

Caption

"Справка"

Color

clInactiveCaption

Position

poScreenCenter

BitBtn1

Caption

"OK"

Glyph

(TBitmap)

Image1…4

Picture

(TBitmap)

Label1

Autosize

false

Caption

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

WordWrap

true

Label2

Caption

"массив"

Label3

Caption

"преобразуется в кучу вида"

Label4

Caption

"Результат работы программы - массив и куча:"

RichEdit1

Lines

"Все элементы кучи обладают основным свойством…"

AboutBox

Caption

"About"

Position

poScreenCenter

BitBtn1

Caption

"OK"

Glyph

(TBitmap)

Image1

Picture

(TJPEGImage)

Panel1

Color

clSkyBlue

Image2

Picture

(TBitmap)

Label1

Caption

WordWrap

"Сортировка c помощью кучи"

Label2

Caption

WordWrap

"Курсовой проект студентки гр.ПИЭ-21 Ветошкиной Е.А."

Label3

Caption

WordWrap

"ВятГУ Киров 2008 г."

5. Блок-схемы алгоритмов и программные коды

void __fastcall TForm2::N2Click(TObject *Sender)

int Left() int Right()

void __fastcall TForm2::BitBtn2Click(TObject *Sender)

void __fastcall TForm2::BitBtn3Click(TObject *Sender)

void __fastcall TForm2::BitBtn4Click(TObject *Sender)

void Build_Heap() void Heapsort()

void __fastcall TForm2::Button2Click(TObject *Sender)

void Heapify_L()

void Heapify()

void __fastcall TForm2::Button1Click(TObject *Sender)

Unit1.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

#include "Unit2.h"

#include "Unit3.h"

#include "Unit4.h"

#include "Unit5.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

       : TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm1::N2Click(TObject *Sender)

{

Form1->Hide();

Form2->Show();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::N5Click(TObject *Sender)

{

if (Application->MessageBoxA("Выдействительнохотитевыйтиизпрограммы?", "Подтверждениевыхода",MB_YESNO+MB_ICONQUESTION)!=IDYES ) return;

Form1->Close();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::N6Click(TObject *Sender)

{

AboutBox->ShowModal();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::N7Click(TObject *Sender)

{

Form5->ShowModal();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::N4Click(TObject *Sender)

{

Form3->Show();

}

//---------------------------------------------------------------------------

Unit2.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit2.h"

#include "Unit1.h"

#include "Unit3.h"

#include "Unit4.h"

#include "Unit5.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma link "CSPIN"

#pragma resource "*.dfm"

TForm2 *Form2;

int i, j, kol, length, heap_size, largest, L, R, c, cc, *a=0, *mas=0;

//---------------------------------------------------------------------------

__fastcall TForm2::TForm2(TComponent* Owner)

       : TForm(Owner)

{

Form2->Height=559;

Form2->Width=609;

}

//---------------------------------------------------------------------------

void __fastcall TForm2::N9Click(TObject *Sender)

{

delete mas;

delete a;

Form2->Close();

Form1->Close();

}

//---------------------------------------------------------------------------

void __fastcall TForm2::N8Click(TObject *Sender)

{

Form2->Close();

Form1->Show();

}

//---------------------------------------------------------------------------

void __fastcall TForm2::N2Click(TObject *Sender)

{

Form2->Height=663;

Form2->Width=919;

Image23->Visible=false;

GroupBox3->Visible=true;

Image1->Visible=false;

Image43->Visible=true;

GroupBox1->Visible=true;

Label1->Visible=true;

Edit4->Visible=true;

RadioGroup1->Visible=true;

Button1->Visible=true;

BitBtn1->Visible=true;

Edit4->SetFocus();

}

//---------------------------------------------------------------------------

void __fastcall TForm2::Button1Click(TObject *Sender)//вводмассива

{

Edit2->Text="";

Edit3->Text="";

Image43->Visible=false;

Image1->Visible=true;

GroupBox3->Caption="Дереводосортировки";

if (Edit4->Text=="")

{

 Application->MessageBox("Введите количество элементов массива!","Ошибка",MB_OK);

return;

}

try

{

 kol=StrToInt(Edit4->Text);

}

catch(EConvertError&)

{

 Application->MessageBox("Введённыйсимволнеявляетсяцелымчислом!", "Повторитеввод", MB_OK+MB_ICONWARNING);

return;

}

if (kol>20)

{

 Application->MessageBox("Количество элементов превышает 20. Не все элементы будут отображены на дереве.", "Предупреждение", MB_OK+MB_ICONWARNING);

}

if (kol<1)

{

 Application->MessageBoxA("Количество не может быть отрицательным!", "Повторите ввод", MB_OK+MB_ICONWARNING);

}

length=kol;

heap_size=kol;

mas=new int[kol+1];

a=new int[kol+1];

if (RadioGroup1->ItemIndex==1)

{

 randomize();

 for (i=1;i<kol+1;i++)

 {

 mas[i]=random(51)+1;

 a[i]=mas[i];

 }

}

if (RadioGroup1->ItemIndex==0)

{

 for(i=1; i<kol+1; i++)

 {

  t=InputBox("Массив","Введите ["+IntToStr(i)+"]-йэлементмассива","");

  if(t=="") return;

  try

  {

   mas[i]=StrToInt(t);

   a[i]=mas[i];

  }

  catch(EConvertError&)

  {

   Application->MessageBox("Введённыйсимволнеявляетсяцелымчислом!", "Повторитеввод", MB_OK+MB_ICONWARNING);

   return;

  }

 }

}

Button2->Visible=true;

Edit1->Text="";

Edit1->Visible=true;

for (i=1;i<kol+1;i++) Edit1->Text=Edit1->Text+IntToStr(mas[i])+"; ";

Image4->Visible=false;

Image5->Visible=false;

Image6->Visible=false;

Image7->Visible=false;

Image8->Visible=false;

Image9->Visible=false;

Image10->Visible=false;

Image11->Visible=false;

Image12->Visible=false;

Image13->Visible=false;

Image14->Visible=false;

Image15->Visible=false;

Image16->Visible=false;

Image17->Visible=false;

Image18->Visible=false;

Image19->Visible=false;

Image20->Visible=false;

Image21->Visible=false;

Image22->Visible=false;

Label4->Visible=false;

Label5->Visible=false;

Label6->Visible=false;

Label7->Visible=false;

Label8->Visible=false;

Label9->Visible=false;

Label10->Visible=false;

Label11->Visible=false;

Label12->Visible=false;

Label13->Visible=false;

Label14->Visible=false;

Label15->Visible=false;

Label16->Visible=false;

Label17->Visible=false;

Label18->Visible=false;

Label19->Visible=false;

Label20->Visible=false;

Label21->Visible=false;

Label22->Visible=false;

Label23->Visible=false;

Image3->Canvas->Brush->Color = clGreen;

Image4->Canvas->Brush->Color = clGreen;

Image5->Canvas->Brush->Color = clGreen;

Image6->Canvas->Brush->Color = clGreen;

Image7->Canvas->Brush->Color = clGreen;

Image8->Canvas->Brush->Color = clGreen;

Image9->Canvas->Brush->Color = clGreen;

Image10->Canvas->Brush->Color = clGreen;

Image11->Canvas->Brush->Color = clGreen;

Image12->Canvas->Brush->Color = clGreen;

Image13->Canvas->Brush->Color = clGreen;

Image14->Canvas->Brush->Color = clGreen;

Image15->Canvas->Brush->Color = clGreen;

Image16->Canvas->Brush->Color = clGreen;

Image17->Canvas->Brush->Color = clGreen;

Image18->Canvas->Brush->Color = clGreen;

Image19->Canvas->Brush->Color = clGreen;

Image20->Canvas->Brush->Color = clGreen;

Image21->Canvas->Brush->Color = clGreen;

Image22->Canvas->Brush->Color = clGreen;

Image3->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image4->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image5->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image6->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image7->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image8->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image9->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image10->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image11->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image12->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image13->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image14->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image15->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image16->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image17->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image18->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image19->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image20->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image21->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image22->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

if (kol>0) Image3->Visible=true;

if (kol>1) Image4->Visible=true;

if (kol>2) Image5->Visible=true;

if (kol>3) Image6->Visible=true;

if (kol>4) Image7->Visible=true;

if (kol>5) Image8->Visible=true;

if (kol>6) Image9->Visible=true;

if (kol>7) Image10->Visible=true;

if (kol>8) Image11->Visible=true;

if (kol>9) Image12->Visible=true;

if (kol>10) Image13->Visible=true;

if (kol>11) Image14->Visible=true;

if (kol>12) Image15->Visible=true;

if (kol>13) Image16->Visible=true;

if (kol>14) Image17->Visible=true;

if (kol>15) Image18->Visible=true;

if (kol>16) Image19->Visible=true;

if (kol>17) Image20->Visible=true;

if (kol>18) Image21->Visible=true;

if (kol>19) Image22->Visible=true;

Label4->Caption=IntToStr(mas[1]);

Label5->Caption=IntToStr(mas[2]);

Label6->Caption=IntToStr(mas[3]);

Label7->Caption=IntToStr(mas[4]);

Label8->Caption=IntToStr(mas[5]);

Label9->Caption=IntToStr(mas[6]);

Label10->Caption=IntToStr(mas[7]);

Label11->Caption=IntToStr(mas[8]);

Label12->Caption=IntToStr(mas[9]);

Label13->Caption=IntToStr(mas[10]);

Label14->Caption=IntToStr(mas[11]);

Label15->Caption=IntToStr(mas[12]);

Label16->Caption=IntToStr(mas[13]);

Label17->Caption=IntToStr(mas[14]);

Label18->Caption=IntToStr(mas[15]);

Label19->Caption=IntToStr(mas[16]);

Label20->Caption=IntToStr(mas[17]);

Label21->Caption=IntToStr(mas[18]);

Label22->Caption=IntToStr(mas[19]);

Label23->Caption=IntToStr(mas[20]);

if (kol>0) Label4->Visible=true;

if (kol>1) Label5->Visible=true;

if (kol>2) Label6->Visible=true;

if (kol>3) Label7->Visible=true;

if (kol>4) Label8->Visible=true;

if (kol>5) Label9->Visible=true;

if (kol>6) Label10->Visible=true;

if (kol>7) Label11->Visible=true;

if (kol>8) Label12->Visible=true;

if (kol>9) Label13->Visible=true;

if (kol>10) Label14->Visible=true;

if (kol>11) Label15->Visible=true;

if (kol>12) Label16->Visible=true;

if (kol>13) Label17->Visible=true;

if (kol>14) Label18->Visible=true;

if (kol>15) Label19->Visible=true;

if (kol>16) Label20->Visible=true;

if (kol>17) Label21->Visible=true;

if (kol>18) Label22->Visible=true;

if (kol>19) Label23->Visible=true;

}

//----------------------------------------------------------------------------

int Parent()// индекс родительского элемента

{

return (i/2);

}

//---------------------------------------------------------------------------

int Left()//индекс левого дочернего элемента

{

return 2*i;

}

//---------------------------------------------------------------------------

int Right()

{

return (2*i+1);

}

//---------------------------------------------------------------------------

void Heapify_L()

{

A:

i=largest;

L=2*i;

R=2*i+1;

if (L<=heap_size && mas[L]>mas[i]) largest=L;

else largest=i;

if (R<=heap_size && mas[R]>mas[largest]) largest=R;

if (largest!=i){c=mas[i]; mas[i]=mas[largest]; mas[largest]=c;goto A;}

}

//---------------------------------------------------------------------------

void Heapify()//поддерживает основное свойство кучи

{

L=2*i;

R=2*i+1;

if (L<=heap_size && mas[L]>mas[i]) largest=L;

else largest=i;

if (R<=heap_size && mas[R]>mas[largest]) largest=R;

if (largest!=i){c=mas[i]; mas[i]=mas[largest]; mas[largest]=c;}

Heapify_L();

}

//---------------------------------------------------------------------------

void Build_Heap()//построение кучи из исходного массива

{

heap_size=length;

for(i=(length/2); i>=1; i--)

       {

        Heapify();

       }

}

//---------------------------------------------------------------------------

void Heapsort()//сортировкамассива

{

Build_Heap();

for(j=length; j>=2; j--)

       {

        cc=mas[j]; mas[j]=mas[1]; mas[1]=cc;

        heap_size--;

        i=1;

        Heapify();

       }

}

//---------------------------------------------------------------------------

void __fastcall TForm2::Button2Click(TObject *Sender)

{

GroupBox3->Caption="Дерево после сортировки";

Heapsort();

GroupBox2->Visible=true;

Label2->Visible=true;

Edit2->Text="";

Edit2->Visible=true;

for (i=1;i<kol+1;i++) Edit2->Text=Edit2->Text+IntToStr(mas[i])+"; ";

Label3->Visible=true;

Edit3->Text="";

Edit3->Visible=true;

BitBtn2->Visible=true;

BitBtn3->Visible=true;

BitBtn4->Visible=true;

Label25->Visible=true;

for (i=kol;i>0;i--) Edit3->Text=Edit3->Text+IntToStr(mas[i])+"; ";

Image3->Canvas->Brush->Color = clRed;

Image4->Canvas->Brush->Color = clRed;

Image5->Canvas->Brush->Color = clRed;

Image6->Canvas->Brush->Color = clRed;

Image7->Canvas->Brush->Color = clRed;

Image8->Canvas->Brush->Color = clRed;

Image9->Canvas->Brush->Color = clRed;

Image10->Canvas->Brush->Color = clRed;

Image11->Canvas->Brush->Color = clRed;

Image12->Canvas->Brush->Color = clRed;

Image13->Canvas->Brush->Color = clRed;

Image14->Canvas->Brush->Color = clRed;

Image15->Canvas->Brush->Color = clRed;

Image16->Canvas->Brush->Color = clRed;

Image17->Canvas->Brush->Color = clRed;

Image18->Canvas->Brush->Color = clRed;

Image19->Canvas->Brush->Color = clRed;

Image20->Canvas->Brush->Color = clRed;

Image21->Canvas->Brush->Color = clRed;

Image22->Canvas->Brush->Color = clRed;

Image3->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image4->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image5->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image6->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image7->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image8->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image9->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image10->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image11->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image12->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image13->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image14->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image15->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image16->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image17->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image18->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image19->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image20->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image21->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image22->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Label4->Caption=IntToStr(mas[1]);

Label5->Caption=IntToStr(mas[2]);

Label6->Caption=IntToStr(mas[3]);

Label7->Caption=IntToStr(mas[4]);

Label8->Caption=IntToStr(mas[5]);

Label9->Caption=IntToStr(mas[6]);

Label10->Caption=IntToStr(mas[7]);

Label11->Caption=IntToStr(mas[8]);

Label12->Caption=IntToStr(mas[9]);

Label13->Caption=IntToStr(mas[10]);

Label14->Caption=IntToStr(mas[11]);

Label15->Caption=IntToStr(mas[12]);

Label16->Caption=IntToStr(mas[13]);

Label17->Caption=IntToStr(mas[14]);

Label18->Caption=IntToStr(mas[15]);

Label19->Caption=IntToStr(mas[16]);

Label20->Caption=IntToStr(mas[17]);

Label21->Caption=IntToStr(mas[18]);

Label22->Caption=IntToStr(mas[19]);

Label23->Caption=IntToStr(mas[20]);

}

//---------------------------------------------------------------------------

void __fastcall TForm2::N6Click(TObject *Sender)

{

AboutBox->ShowModal();

}

//---------------------------------------------------------------------------

void __fastcall TForm2::N10Click(TObject *Sender)

{

Form5->ShowModal();

}

//---------------------------------------------------------------------------

void __fastcall TForm2::N5Click(TObject *Sender)

{

Form3->ShowModal();

}

//---------------------------------------------------------------------------

void __fastcall TForm2::BitBtn1Click(TObject *Sender)

{

if (Application->MessageBoxA("Выдействительнохотитевыйтиизпрограммы?", "Подтверждениевыхода",MB_YESNO+MB_ICONQUESTION)!=IDYES ) return;

delete mas;

Form2->Close();

Form1->Close();

}

//---------------------------------------------------------------------------

void __fastcall TForm2::BitBtn2Click(TObject *Sender)

{

Image3->Canvas->Brush->Color = clGreen;

Image4->Canvas->Brush->Color = clGreen;

Image5->Canvas->Brush->Color = clGreen;

Image6->Canvas->Brush->Color = clGreen;

Image7->Canvas->Brush->Color = clGreen;

Image8->Canvas->Brush->Color = clGreen;

Image9->Canvas->Brush->Color = clGreen;

Image10->Canvas->Brush->Color = clGreen;

Image11->Canvas->Brush->Color = clGreen;

Image12->Canvas->Brush->Color = clGreen;

Image13->Canvas->Brush->Color = clGreen;

Image14->Canvas->Brush->Color = clGreen;

Image15->Canvas->Brush->Color = clGreen;

Image16->Canvas->Brush->Color = clGreen;

Image17->Canvas->Brush->Color = clGreen;

Image18->Canvas->Brush->Color = clGreen;

Image19->Canvas->Brush->Color = clGreen;

Image20->Canvas->Brush->Color = clGreen;

Image21->Canvas->Brush->Color = clGreen;

Image22->Canvas->Brush->Color = clGreen;

Image3->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image4->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image5->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image6->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image7->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image8->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image9->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image10->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image11->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image13->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image14->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image15->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image16->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image17->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image18->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image19->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image20->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image21->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image22->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Label4->Caption=IntToStr(a[1]);

Label5->Caption=IntToStr(a[2]);

Label6->Caption=IntToStr(a[3]);

Label7->Caption=IntToStr(a[4]);

Label8->Caption=IntToStr(a[5]);

Label9->Caption=IntToStr(a[6]);

Label10->Caption=IntToStr(a[7]);

Label11->Caption=IntToStr(a[8]);

Label12->Caption=IntToStr(a[9]);

Label13->Caption=IntToStr(a[10]);

Label14->Caption=IntToStr(a[11]);

Label15->Caption=IntToStr(a[12]);

Label16->Caption=IntToStr(a[13]);

Label17->Caption=IntToStr(a[14]);

Label18->Caption=IntToStr(a[15]);

Label19->Caption=IntToStr(a[16]);

Label20->Caption=IntToStr(a[17]);

Label21->Caption=IntToStr(a[18]);

Label22->Caption=IntToStr(a[19]);

Label23->Caption=IntToStr(a[20]);

}

//---------------------------------------------------------------------------

void __fastcall TForm2::BitBtn3Click(TObject *Sender)

{

Image3->Canvas->Brush->Color = clRed;

Image4->Canvas->Brush->Color = clRed;

Image5->Canvas->Brush->Color = clRed;

Image6->Canvas->Brush->Color = clRed;

Image7->Canvas->Brush->Color = clRed;

Image8->Canvas->Brush->Color = clRed;

Image9->Canvas->Brush->Color = clRed;

Image10->Canvas->Brush->Color = clRed;

Image11->Canvas->Brush->Color = clRed;

Image12->Canvas->Brush->Color = clRed;

Image13->Canvas->Brush->Color = clRed;

Image14->Canvas->Brush->Color = clRed;

Image15->Canvas->Brush->Color = clRed;

Image16->Canvas->Brush->Color = clRed;

Image17->Canvas->Brush->Color = clRed;

Image18->Canvas->Brush->Color = clRed;

Image19->Canvas->Brush->Color = clRed;

Image20->Canvas->Brush->Color = clRed;

Image21->Canvas->Brush->Color = clRed;

Image22->Canvas->Brush->Color = clRed;

Image3->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image4->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image5->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image6->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image7->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image8->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image9->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image10->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image11->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image12->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image13->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image14->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image15->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image16->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image17->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image18->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image19->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image20->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image21->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image22->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Label4->Caption=IntToStr(mas[1]);

Label5->Caption=IntToStr(mas[2]);

Label6->Caption=IntToStr(mas[3]);

Label7->Caption=IntToStr(mas[4]);

Label8->Caption=IntToStr(mas[5]);

Label9->Caption=IntToStr(mas[6]);

Label10->Caption=IntToStr(mas[7]);

Label11->Caption=IntToStr(mas[8]);

Label12->Caption=IntToStr(mas[9]);

Label13->Caption=IntToStr(mas[10]);

Label14->Caption=IntToStr(mas[11]);

Label15->Caption=IntToStr(mas[12]);

Label16->Caption=IntToStr(mas[13]);

Label17->Caption=IntToStr(mas[14]);

Label18->Caption=IntToStr(mas[15]);

Label19->Caption=IntToStr(mas[16]);

Label20->Caption=IntToStr(mas[17]);

Label21->Caption=IntToStr(mas[18]);

Label22->Caption=IntToStr(mas[19]);

Label23->Caption=IntToStr(mas[20]);

}

//---------------------------------------------------------------------------

void __fastcall TForm2::BitBtn4Click(TObject *Sender)

{

Image3->Canvas->Brush->Color = clPurple;

Image4->Canvas->Brush->Color = clPurple;

Image5->Canvas->Brush->Color = clPurple;

Image6->Canvas->Brush->Color = clPurple;

Image7->Canvas->Brush->Color = clPurple;

Image8->Canvas->Brush->Color = clPurple;

Image9->Canvas->Brush->Color = clPurple;

Image10->Canvas->Brush->Color = clPurple;

Image11->Canvas->Brush->Color = clPurple;

Image12->Canvas->Brush->Color = clPurple;

Image13->Canvas->Brush->Color = clPurple;

Image14->Canvas->Brush->Color = clPurple;

Image15->Canvas->Brush->Color = clPurple;

Image16->Canvas->Brush->Color = clPurple;

Image17->Canvas->Brush->Color = clPurple;

Image18->Canvas->Brush->Color = clPurple;

Image19->Canvas->Brush->Color = clPurple;

Image20->Canvas->Brush->Color = clPurple;

Image21->Canvas->Brush->Color = clPurple;

Image3->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image4->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image5->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image6->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image7->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image8->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image9->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image10->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image11->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image12->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image13->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image14->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image15->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image16->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image17->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image18->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image19->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image20->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image21->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Image22->Canvas->Ellipse(0, 0, Image3->Width, Image3->Height);

Label4->Caption=IntToStr(mas[kol]);

Label5->Caption=IntToStr(mas[kol-1]);

Label6->Caption=IntToStr(mas[kol-2]);

Label7->Caption=IntToStr(mas[kol-3]);

Label8->Caption=IntToStr(mas[kol-4]);

Label9->Caption=IntToStr(mas[kol-5]);

Label10->Caption=IntToStr(mas[kol-6]);

Label11->Caption=IntToStr(mas[kol-7]);

Label12->Caption=IntToStr(mas[kol-8]);

Label13->Caption=IntToStr(mas[kol-9]);

Label14->Caption=IntToStr(mas[kol-10]);

Label15->Caption=IntToStr(mas[kol-11]);

Label16->Caption=IntToStr(mas[kol-12]);

Label17->Caption=IntToStr(mas[kol-13]);

Label18->Caption=IntToStr(mas[kol-14]);

Label19->Caption=IntToStr(mas[kol-15]);

Label20->Caption=IntToStr(mas[kol-16]);

Label21->Caption=IntToStr(mas[kol-17]);

Label22->Caption=IntToStr(mas[kol-18]);

Label23->Caption=IntToStr(mas[kol-19]);

}

//---------------------------------------------------------------------------

Unit3.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit3.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm3 *Form3;

//---------------------------------------------------------------------------

__fastcall TForm3::TForm3(TComponent* Owner)

       : TForm(Owner)

{

RichEdit1->Lines->LoadFromFile("Help.rtf");

}

//---------------------------------------------------------------------------

void __fastcall TForm3::BitBtn1Click(TObject *Sender)

{

Form3->Close();

}

//---------------------------------------------------------------------------

Unit4.cpp

//---------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit4.h"

//---------------------------------------------------------------------

#pragma resource "*.dfm"

TAboutBox *AboutBox;

//---------------------------------------------------------------------

__fastcall TAboutBox::TAboutBox(TComponent* AOwner)

: TForm(AOwner)

{

}

//---------------------------------------------------------------------

void __fastcall TAboutBox::BitBtn1Click(TObject *Sender)

{

AboutBox->Close();

}

//---------------------------------------------------------------------------

Unit5.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit5.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm5 *Form5;

//---------------------------------------------------------------------------

__fastcall TForm5::TForm5(TComponent* Owner)

       : TForm(Owner)

{

//RichEdit1->Lines->LoadFromFile("Information.rtf");

}

//---------------------------------------------------------------------------

void __fastcall TForm5::BitBtn1Click(TObject *Sender)

{

Form5->Close();

}

//---------------------------------------------------------------------------

Project1.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

//---------------------------------------------------------------------------

USEFORM("Unit1.cpp", Form1);

USEFORM("Unit2.cpp", Form2);

USEFORM("Unit3.cpp", Form3);

USEFORM("Unit4.cpp", AboutBox);

USEFORM("Unit5.cpp", Form5);

//---------------------------------------------------------------------------

WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)

{

       try

       {

                Application->Initialize();

                Application->CreateForm(__classid(TForm1), &Form1);

                Application->CreateForm(__classid(TForm2), &Form2);

                Application->CreateForm(__classid(TForm3), &Form3);

                Application->CreateForm(__classid(TAboutBox), &AboutBox);

                Application->CreateForm(__classid(TForm5), &Form5);

                Application->Run();

       }

       catch (Exception &exception)

       {

                Application->ShowException(&exception);

       }

       catch (...)

       {

                try

                {

                        throw Exception("");

                }

                catch (Exception &exception)

{

                        Application->ShowException(&exception);

                }

       }

       return 0;

}

//---------------------------------------------------------------------------

6. Результаты решения

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

7. Заключение

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

Таким образом, все поставленные цели по выполнению курсовой работы достигнуты.

8. Список использованной литературы

  • Т. Кормен, Ч. Лейзерсон, Р. Ривест "Алгоритмы: построение и анализ" / Пер. с англ. под ред. А. Шеня. — М.:МЦНМО: БИНОМ. Лаборатория знаний, 2004. — 2-е изд., стереотип. — 960 с.: 263 ил.
  • Лавров С. С. "Программирование. Математические основы, средства, теория" — СПб.: БХВ-Петербург, 2001. — 320 с.: ил.

Приложение для сортировки числового массива с помощью кучи на http://mirrorref.ru


Похожие рефераты, которые будут Вам интерестны.

1. Структурированные типы данных. Массивы. Одномерные массивы. Многомерные массивы. Объявление массива. Тип массива

2. Алгоритмы поиска и сортировки

3. Алгоритм сортировки методом пузырька

4. Методы сортировки. Их сравнительный анализ

5. Понятие сортировки. Виды сортировок

6. ИГРОВОЕ ПРИЛОЖЕНИЕ DELL

7. Многопользовательское игровое приложение

8.  Лабораторная работа. Методы сортировки в MATLAB

9. Изменение порядка сортировки по высоте для фигур

10. Разработка Android приложение Я Переводчик