Курсовая работа: Алгоритмы обработки данных линейной и нелинейной структуры
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение высшего профессионального образования
«ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультет автоматики и вычислительной техники
Информатика и вычислительная техника
Кафедра АИКС
АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ ЛИНЕЙНОЙ И НЕЛИНЕЙНОЙ СТРУКТУРЫ
Пояснительная записка к курсовому проекту
Студентка группы 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. Структурная схема программы с описанием
Схема взаимодействия функций программного комплекса:
 |
|||
 |
|||
 |
|||
|
|
|
|
|
|
|
|
Преобразование массива в максимальную пирамиду
 |
|||
 |
Функция удаления элемента из пирамиды
|
|
· программы, нажмите на кнопку “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();;
//---------------------------------------------------------------------------
| Препроцессорные средства в C и С++ | |
|
Препроцессорные средства в C и С++ 3.1 Основные понятия препроцессорной обработки Препроцессорная обработка (макрообработка) - это преобразование ... void addElem(int& el); // Добавление элемента в конец массива { T temp; |
Раздел: Рефераты по информатике, программированию Тип: учебное пособие |
| Алгоритмический язык Паскаль | |
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ им. А.В. ЛУНАЧАРСКОГО КАФЕДРА ИНФОРМАТИКИ Дипломная ... и пусть переменная А - переменная типа U. Тогда A[I] - переменная типа R, а А[I][J] - переменная типа S. Таким образом, получается переменная, представляющая собой двумерный массив ... ° if I > J then write(H,I) else write(H,J); |
Раздел: Рефераты по информатике, программированию Тип: дипломная работа |
| Основы C | |
|
Кафедра: Автоматика и Информационные Технологии ОСНОВЫ С ОГЛАВЛЕНИЕ Введение Глава 1. Основы языка Си 1.1. Алфавит 1.2. Основные конструкции Си 1.3 ... void set_j(int n); Массив a[1:k,1:k] задан, в нем все a[i,j]>0;и a[i,j] м.б. не равно a[j,i]. |
Раздел: Рефераты по информатике, программированию Тип: учебное пособие |
| Система математических расчетов MATLAB | |
|
ГОСУДАРСТВЕННЫЙ ИНЖЕНЕРНЫЙ УНИВЕРСИТЕТ АРМЕНИИ MATLAB УЧЕБНОЕ ПОСОБИЕ Гаспарян Олег Николаевич Д.т.н, с.н.с 2005 СОДЕРЖАНИЕ Система математических ... * Array Editor (Редактор Массивов Данных) - Просмотр содержимого массивов данных, где через TEMP обозначен массив четырехмерных данных. |
Раздел: Рефераты по информатике, программированию Тип: учебное пособие |
| Объектно-ориентированное программирование на Borland C++ | |
|
Объектно-ориентированное программирование на Borland C++ Тексты лекций, прочитанных в Московском государственном университете экономики, статистики и ... int a [ 5 ] ; // Массив из пяти элементов типа int В этом примере указатель pint инициализирован адресом пятого элемента массива Array, а затем седьмому элементу этого массива присвоено значение 1. |
Раздел: Рефераты по информатике, программированию Тип: учебное пособие |