Алгоритмы обработки данных линейной и нелинейной структуры

Алгоритмы обработки данных линейной и нелинейной структуры

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

«ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет автоматики и вычислительной техники

Информатика и вычислительная техника

Кафедра АИКС

АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ ЛИНЕЙНОЙ И НЕЛИНЕЙНОЙ СТРУКТУРЫ

Пояснительная записка к курсовому проекту

Студентка группы 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’s Data”. Вверху под надписью “Array” будет выведен массив.

·       Если Вы желаете ввести данные самостоятельно, в поле над кнопками “Delete Element” и “Add Element”, введите число, затем нажмите кнопку “Add Element”, введенное число появится под надписью “Array”. 

·      Далее следует выбрать тип пирамиды, для этого установите метку напротив желаемой пирамиды, затем нажмите кнопку “Show Tree”. В поле слева от панели параметров вы увидите получившуюся пирамиду. 

·      Если Вы хотите добавить элемент в уже существующую пирамиду , в поле над кнопками “Delete Element” и “Add Element”, введите число, затем нажмите кнопку “Add Element”, введенное число будет добавлено в конец массива. 

·      Если вы хотите удалить элемент, введите его значение в поле над кнопками “Delete Element” и “Add Element” и нажмите кнопку “Delete Element”, если этот элемент является корнем, произойдет его удаление.

пирамида максимальный минимальный алгоритм



3. Пример выполнения программного комплекса



Рис. 1. Общий вид приложения



Рис. 2. Ввод данных и вывод пирамиды



Список используемой литературы

1.    Цапко И.В. Структуры и алгоритмы обработки данных: учебное пособие Томск: Изд-во Томского политехнического университета, 2007. – 184 с.



Приложение А

Листинг программы

#include <vcl.h>

#pragma hdrstop

#include "UnitHeapTree.h"

#include <math.h>

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TFormHeapTree *FormHeapTree;

#define N 1000

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

int array[N]; // используемый массив

int n=0; //фактическое количество элементов в массиве

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

void makeArray() //создание массива, если пользователь

{                 //предпочел использовать данные программы

         randomize();

         for(int i=0;i<10;i++)

                   array[i]=random(20);

         n=10;

}

//-----------------функция преобразования массива в минимальную пирамиду -----------------

void heap_min() 

{

         int temp;

         for(int l =floor((n-1)/2); l>=0; l--)

         {

                   for(int j = floor((n-1)/2); j>=0; j--)

                   {

                            int i=2*j;

                            if((i+2)<n)

                            {

                                      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[i+1] && array[i+1]<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;

                                      }

                   }

         }

}

 //---------------функция преобразования массива в максимальную пирамиду -----------------

void heap_max() 

{

         int temp;

         for(int l =floor((n-1)/2); l>=0; l--)

         {

                   for(int j = floor((n-1)/2); j>=0; j--)

                   {

                            int i=2*j;

                            if((i+2)<n)

                            {

                                      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[i+1] && array[i+1]>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;

                                      }

                   }

         }

}

//-------------------------удаление элемента из пирамиды ----------------------------------------

void delElem(int t) 

{

         int f;

         for(int i=0; i<n; i++)

         {

                   if(array[i]==t && i==0)

                   {

                            array[0]=array[n-1];

                            n=n-1;

                            break;

                   }

                   else

                            {

                            ShowMessage("This element 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();

         int x = FormHeapTree->ImageTree->Width/2;

         int y = 20;

         int pr = 20;//расстояние между элементрами

         if(n!=0)

         {

                   int m = log(n)/log(2);

                   FormHeapTree->ImageTree->Canvas->Ellipse(x,20,x+30,50);

                   FormHeapTree->ImageTree->Canvas->TextOutA(x+10,y+5,array[0]);

                   //левое поддерово снизу вверх

                            for(int i=m; i>0; i--)

                            {

                                      int q=pow(2,i-1)-1;

                                      for(int j=pow(2,i)-1; j<=pow(2,i)+pow(2,i-1)-2; j++)

                                               if(j<n)

                                               {

                                                        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(int j = pow(2,i)+pow(2,i-1)-1; j<=pow(2,i+1)-2; j++)

                                               if(j<n)

                                               {

                                                        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;

                            }

                   }

}

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

__fastcall TFormHeapTree::TFormHeapTree(TComponent* Owner)

         : TForm(Owner)

{

}

//---------------------------------функция вывода массива на экран ------------------------------------

void ShowArray() 

{

         FormHeapTree->LabelArray->Caption = "";

         for(int i=0; i<n; i++)

                   FormHeapTree->LabelArray->Caption = FormHeapTree->LabelArray->Caption + " " + array[i];

}

//--------------------функция добавления элемента в пирамиду---------------------------------------

                    

void __fastcall TFormHeapTree::SpeedButtonAddClick(TObject *Sender)

{

         if(this->EditElem->Text != "")

         {

                   try

                   {

                            int temp = StrToInt(this->EditElem->Text);

                            array[n] = temp;

                            this->LabelArray->Caption = this->LabelArray->Caption + " " + array[n];

                            n++;

                   }

                   catch(EConvertError &e)

                   {

                            ShowMessage("Please enter only numbers.");

                   }

         }

         else

                   ShowMessage("Please enter element!");

}

//----------------------функция непосредственно удаления элемента из пирамиды -----------

                            

void __fastcall TFormHeapTree::SpeedButtonDeleteClick(TObject *Sender)

{

          if(this->EditElem->Text != "")

         {

                   try

                   {

                            int temp = StrToInt(this->EditElem->Text);

                            delElem(temp);

                            this->LabelArray->Caption = "";

                            ShowArray();

                   }

                   catch(EConvertError &e)

                   {

                            ShowMessage("Please enter only numbers.");

                   }

         }

         else

                   ShowMessage("Please enter 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("Please choose type of heap-tree.");

}

//------------ функция использоания данных программы-----------------------------------------------

void __fastcall TFormHeapTree::ButtonProgDataClick(TObject *Sender)

{

         makeArray();

         ShowArray();;

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