ФЕДЕРАЛЬНОЕАГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственноеобразовательное учреждение высшего профессионального образования
«ТОМСКИЙПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультетавтоматики и вычислительной техники
Информатика ивычислительная техника
Кафедра АИКС
АЛГОРИТМЫОБРАБОТКИ ДАННЫХ ЛИНЕЙНОЙ И НЕЛИНЕЙНОЙ СТРУКТУРЫ
Пояснительнаязаписка к курсовому проекту
Студентка группы 8В84
А. C.Бушанова
Руководитель
Доцент каф. АИКС
И.В. Цапко
Томск – 2011г.
Задание на курсовоепроектирование
Программно реализоватьалгоритмы обработки данных, представленных в виде пирамиды (максимальной илиминимальной – по выбору пользователя): преобразование массива в пирамиду,включение элемента в пирамиду, удаление элемента из пирамиды, вывод пирамиды наэкран.
1. Краткоесловесное описание алгоритмов, используемых при решении поставленной задачи
Пирамида — законченноебинарное дерево, имеющее упорядочение узлов по уровням.
Различают максимальныепирамиды и минимальные.
В максимальной пирамидеродительский узел больше или равен каждому из своих сыновей. Корень содержитнаибольший элемент.
В минимальной пирамидеродительский узел меньше или равен каждому из своих сыновей.
Корень содержитнаименьший элемент.
На каждом уровнепирамида содержит 2nэлементов, где n – номер уровня.Высота пирамиды />, где N —количество элементов пирамиды.
/>
/>
Пирамида используется втех приложениях, где клиенту требуется прямой доступ к минимальному элементу.
Пирамида являетсясписком, который хранит данные в виде бинарного дерева.
Все алгоритмы обработкипирамид сами должны обновлять дерево и поддерживать пирамидальное упорядочение.
Преобразование массивав пирамиду
Индекс последнегоэлемента пирамиды равен n-1.
Индекс его родителяравен (n-2)/2, и он определяет последний нелистовой узел пирамиды. Этот индексявляется начальным для преобразования массива.
Рассмотримцелочисленный массив
int A[10] = {9, 12, 17,30, 50, 20, 60, 65, 4, 19};
Индексы листьев: 5, 6,..., 9.
Индексы родительскихузлов: 4, 3, ..., 0.
Родитель А[4]=50, онбольше своего сына А[9]=19 и поэтому должен поменяться с ним местами.
Родитель А[3]=30, онбольше своего сына А[8]=4 и поэтому должен поменяться с ним местами (еслименьших сына два, то меняется местами с наименьшим сыном).
На уровне 2 родительА[2]=17 уже удовлетворяет условию пирамидальности, поэтому перестановок непроизводится.
Родитель А[1]=12 большесвоего сына А[3]=4 и должен поменяться с ним местами.
Процесс прекращается вкорневом узле. Родитель А[0]=9 должен поменяться местами со своим сыном А[1].
Результирующее деревоявляется пирамидой.
/>
Включение элемента впирамиду
1. Новый элемент добавляетсяв конец списка.
2. Если новый элементимеет значение, меньшее, чем у его родителя, узлы меняются местами.
3. Новый родительрассматривается как сын, и проверяется условие пирамидальности для болеестаршего родителя.
4. Процесс сканируетпуть предков и завершается, встретив родителя, меньше чем новый элемент, илидостигнув корневого узла.
Удаление из пирамиды
Данные удаляются всегдаиз корня дерева.
1. Удалить корневойузел и заменить его последним узлом.
2. Если новый корневойузел больше любого своего сына, то необходимо его поменять местами с наименьшимсыном.
3. Движение по путименьших сыновей продолжается до тех пор, пока элемент не займет правильнуюпозицию в качестве родителя или пока не будет достигнут конец списка.
2. Структурнаясхема программы с описанием
Схема взаимодействияфункций программного комплекса:/> /> /> /> /> /> /> /> /> /> /> /> /> />
delElem(int t)
/>/>/>/>/>/>/>
да
нет
да />/>/>/>
makeArray() />
ShowTree()
Heap_min()
Heap_max() Структурныесхемы алгоритмов:
Преобразование массивав максимальную пирамиду/> /> /> /> /> /> /> /> />
Функция удаленияэлемента из пирамиды
/>
нет
да />/>/>
/>
· программы,нажмите на кнопку “Program’sData”. Вверху под надписью “Array”будет выведен массив.
· ЕслиВы желаете ввести данные самостоятельно, в поле над кнопками “DeleteElement” и “AddElement”, введите число, затемнажмите кнопку “AddElement”, введенное числопоявится под надписью “Array”.
· Далееследует выбрать тип пирамиды, для этого установите метку напротив желаемойпирамиды, затем нажмите кнопку “ShowTree”. В поле слева от панелипараметров вы увидите получившуюся пирамиду.
· ЕслиВы хотите добавить элемент в уже существующую пирамиду, в поле над кнопками “DeleteElement” и “AddElement”, введите число, затемнажмите кнопку “AddElement”, введенное числобудет добавлено в конец массива.
· Есливы хотите удалить элемент, введите его значение в поле над кнопками “DeleteElement” и “AddElement” и нажмите кнопку “DeleteElement”, если этот элементявляется корнем, произойдет его удаление.
пирамида максимальный минимальныйалгоритм
3. Пример выполненияпрограммного комплекса
/>
Рис. 1. Общий видприложения
/>
Рис. 2. Ввод данных ивывод пирамиды
Список используемойлитературы
1. ЦапкоИ.В. Структуры и алгоритмы обработки данных: учебное пособие Томск: Изд-воТомского политехнического университета, 2007. – 184 с.
Приложение А
Листинг программы
#include
#pragmahdrstop
#include«UnitHeapTree.h»
#include
//---------------------------------------------------------------------------
#pragmapackage(smart_init)
#pragmaresource "*.dfm"
TFormHeapTree*FormHeapTree;
#define N 1000
//---------------------------------------------------------------------------
int array[N]; //используемый массив
int n=0; //фактическоеколичество элементов в массиве
//---------------------------------------------------------------------------
void makeArray()//создание массива, если пользователь
{ //предпочелиспользовать данные программы
randomize();
for(inti=0;i
array[i]=random(20);
n=10;
}
//-----------------функцияпреобразования массива в минимальную пирамиду -----------------
void heap_min()
{
inttemp;
for(intl =floor((n-1)/2); l>=0; l--)
{
for(intj = floor((n-1)/2); j>=0; j--)
{
inti=2*j;
if((i+2)
{
if(array[i+2]
{
temp= array[i+2];
array[i+2]= array[j];
array[j]= temp;
}
else
if(array[i+2]>=array[i+1]&& array[i+1]
{
temp= array[i+1];
array[i+1]= array[j];
array[j]= temp;
}
}
else
if(array[i+1]
{
temp= array[i+1];
array[i+1]= array[j];
array[j]= temp;
}
}
}
}
//---------------функцияпреобразования массива в максимальную пирамиду -----------------
void heap_max()
{
inttemp;
for(intl =floor((n-1)/2); l>=0; l--)
{
for(intj = floor((n-1)/2); j>=0; j--)
{
inti=2*j;
if((i+2)
{
if(array[i+2]>=array[i+1]&& array[i+2]>array[j])
{
temp= array[i+2];
array[i+2]= array[j];
array[j]= temp;
}
else
if(array[i+2]array[j])
{
temp= array[i+1];
array[i+1]= array[j];
array[j]= temp;
}
}
else
if(array[i+1]>array[j])
{
temp= array[i+1];
array[i+1]= array[j];
array[j]= temp;
}
}
}
}
//-------------------------удалениеэлементаизпирамиды----------------------------------------
voiddelElem(int t)
{
intf;
for(inti=0; i
{
if(array[i]==t&& i==0)
{
array[0]=array[n-1];
n=n-1;
break;
}
else
{
ShowMessage(«Thiselement is not a root or this element is not found»);
break;
}
}
}
//-------------------функцияочищения области рисования пирамиды -------------------------------
void Re(void)
{
FormHeapTree->ImageTree->Canvas->FillRect(Rect(0,0,FormHeapTree->ImageTree->Width,FormHeapTree->ImageTree->Height));
}
//-------------------------Функциявывода пирамиды на экран -------------------------------------------
void showTree()
{
Re();
intx = FormHeapTree->ImageTree->Width/2;
inty = 20;
int pr =20;//расстояние между элементрами
if(n!=0)
{
intm = log(n)/log(2);
FormHeapTree->ImageTree->Canvas->Ellipse(x,20,x+30,50);
FormHeapTree->ImageTree->Canvas->TextOutA(x+10,y+5,array[0]);
//левоеподдеровоснизувверх
for(inti=m; i>0; i--)
{
intq=pow(2,i-1)-1;
for(intj=pow(2,i)-1; j
if(j
{
FormHeapTree->ImageTree->Canvas->Ellipse(x-q*pr*2-pr-5,y+i*50-5, x-q*pr*2-pr+30-5, y+i*50-5+30);
FormHeapTree->ImageTree->Canvas->TextOutA(x-q*pr*2-pr+5,y+i*50, array[j]);
q--;
}
//правоеподдерево
q=0;
for(intj = pow(2,i)+pow(2,i-1)-1; j
if(j
{
FormHeapTree->ImageTree->Canvas->Ellipse(x+q*pr*2+pr-5,y+i*50-5, x+q*pr*2+pr+30-5, y+i*50-5+30);
FormHeapTree->ImageTree->Canvas->TextOutA(x+q*pr*2+pr+5,y+i*50, array[j]);
q++;
}
pr*=2;
}
}
}
//---------------------------------------------------------------------------
__fastcallTFormHeapTree::TFormHeapTree(TComponent* Owner)
:TForm(Owner)
{
}
//---------------------------------функциявывода массива на экран ------------------------------------
void ShowArray()
{
FormHeapTree->LabelArray->Caption= "";
for(inti=0; i
FormHeapTree->LabelArray->Caption= FormHeapTree->LabelArray->Caption + " " + array[i];
}
//--------------------функциядобавления элемента в пирамиду---------------------------------------
void__fastcall TFormHeapTree::SpeedButtonAddClick(TObject *Sender)
{
if(this->EditElem->Text!= "")
{
try
{
inttemp = StrToInt(this->EditElem->Text);
array[n]= temp;
this->LabelArray->Caption= this->LabelArray->Caption + " " + array[n];
n++;
}
catch(EConvertError&e)
{
ShowMessage(«Pleaseenter only numbers.»);
}
}
else
ShowMessage(«Pleaseenter element!»);
}
//----------------------функциянепосредственно удаления элемента из пирамиды -----------
void__fastcall TFormHeapTree::SpeedButtonDeleteClick(TObject *Sender)
{
if(this->EditElem->Text!= "")
{
try
{
inttemp = StrToInt(this->EditElem->Text);
delElem(temp);
this->LabelArray->Caption= "";
ShowArray();
}
catch(EConvertError&e)
{
ShowMessage(«Pleaseenter only numbers.»);
}
}
else
ShowMessage(«Pleaseenter element!»);
}
//----------------- функциявывода пирамиды на экран ------------------------------------------------
void__fastcall TFormHeapTree::SpeedButtonShowTreeClick(TObject *Sender)
{
if(RadioButtonMin->Checked== true || RadioButtonMax->Checked == true)
{
if(RadioButtonMin->Checked)
{
// RadioButtonMax->Checked= false;
heap_min();
ShowArray();;
}
if(RadioButtonMax->Checked)
{
//RadioButtonMin->Checked= false;
heap_max();
ShowArray();
}
showTree();
}
else
ShowMessage(«Pleasechoose type of heap-tree.»);
}
//------------функцияиспользоанияданныхпрограммы-----------------------------------------------
void__fastcall TFormHeapTree::ButtonProgDataClick(TObject *Sender)
{
makeArray();
ShowArray();;
//---------------------------------------------------------------------------