Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Алгоритмы обработки данных линейной и нелинейной структуры
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 09:30:29 18 марта 2011 Похожие работы
Просмотров: 579 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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

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

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

Кафедра АИКС

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

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

Студентка группы 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();;

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:21:57 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:11:48 29 ноября 2015

Работы, похожие на Курсовая работа: Алгоритмы обработки данных линейной и нелинейной структуры

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(151311)
Комментарии (1844)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru