Курсовая: Структуры данных: бинарное упорядоченное несбалансированное дерево - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

Структуры данных: бинарное упорядоченное несбалансированное дерево

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 167 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

Казанский Государственный Технический Университет им . А . Н . Туполева Курсовая работа по программированию на тему Структуры данных : бинарное упорядоченное несбалансированное де рево Выполнил : Зверев И . М. Проверил : Рахматуллин А . И. Казань 2003 План работы : 1) Постановка задачи 2) Описание программы 3) Код программы на язы ках Pascal и С ++ 1. Постановка задачи Требуется напи сать программу , реализующую основные операции работы с деревом . Причём , обязательным условие м является использование структуры данных кла сс для описания дерева и методов ра боты с ним. 2. Описание программы Описание ведёт ся для кода на Pascal е , отличия для С ++ будут указаны ниже. В программе основным элементом является класс TTree . Его методы – это основные процедуры рабо ты с деревом : C reate – констр уктор класса – процед ура , создающая д ерево, Add – метод добавления элемента в дер ево, Del – метод удаления элемента из дере ва, View – метод вывода элементов дерева на экран, Exist – метод проверки существования элеме нта с некоторым ключом , по сути поиск элемента, Destroy – дес труктор класса – проце дура , удаляющая дерево. Рассмотрим алгоритмы работы процедур. Create – создание дерева . Присваивает пол ю Root (корень ) значение nil – указателя , который никуда не указывает. Add – добавле ние элемента в дерево . Для построения дере ва используем следующий алгоритм . Первый элемент помещаем в корень (инициализируем д ерево ). Далее поступаем следующим образом . Если добавляемый в дерево элемент имеет ключ больший , чем ключ узла , то , если узел не лист , обходим его справа . Если доба вляемый э л емент имеет ключ не больший чем ключ узла , то , если узел не лист , обходим его слева . Если дошли до листа , то добавляем элемент соответствен но справа или слева. Del – удалени е элемента из дерева. Удаление узла довольно просто если он является листом или им еет одного потомка . Например , если требуется удалить уз ел с ключом М надо просто заменить пр авую ссылку узла К на указатель на L. Т рудность заключается в удалении узла с дв умя потомками , поскольку мы не можем указа ть одним указателем на два направления. Например , если просто удалить узел с ключом N, то левый указатель узла с ключом Т должен указывать одновременно н а К и R что не возможно . В этом случ ае удаляемый узел нужно заменить на друго й узел из дерева . Возникает вопрос , каким же узлом его заменить ? Этот узел должен обладать двумя свойствами : во-первых , он должен иметь не более одного потомка ; во-вторых , для сохранения упорядоченности клю чей , он должен иметь ключ либо не мень ший , чем любой ключ левого поддерева удаля емого узла , либо не больший , чем любой ключ правого поддерева удаляемого уз ла . Таким свойствам обладают два узла , сам ый правый узел левого поддерева удаляемого узла и самый левый узел его правого поддерева . Любым из этих узлов им можно заменить удаляемый узел . Например , на р и сунке это узлы М и Р . Необходимо различать три случая : 1. Узла с ключем , равным х , нет . 2. Узел с ключем , равным х , имеет не более одного потомка . 3. Узел с ключем , равным х , имеет двух потомков Вспомогательная рекурсивная процедура del вызывается только в случае , когда удаляемый узел имеет двух потомков . Она “спускается вдоль” самой прав ой ветви левого поддерева удал яемого узла q^ (при вызове процедуры ей передается в качестве параметра указатель на левое п оддерево ) и , затем , заменяет существенную инфор мацию (в нашем случае ключ data) в q^ соответств ующим значением самого правого узла r^ этого левого поддерева , после чего от r^ можно освободиться. View - печать дер ева , обходя его справа налево . Чем дальше элемент от корня , тем больше ему буде т предшествовать пробелов , т . о . путём несл ожного алгоритма получается вполне удобно чит аемое дерево. Exist – провер ка существо вания элемента с заданным ключом . Ищем элемент , двигаясь от корня и переходя на левое или правое поддерево каждого узла в зависимости от его ключ а. Destroy – удален ие дерева . Обходя дерево слева направо , уд аляет элементы . Сначала удаляются потомки узл а , з атем сам узел. Различия между описаниями кодов программа х на разных языках относятся в основном к конструкторам и деструкторам . В . pas программах они определяются директивами и вызываются явно как методы класса из программы , а в . cpp конструктор вызываетс я при создании элемента класс а и деструктор автоматически при выходе и з программы (для чего объект класса размещ ается в памяти динамически ). 3. Код программы program PTree; $APPTYPE CONSOLE type TInfo = Byte; PItem = ^Item; Item = record Key: TInfo; Left, Right: PItem; end; TTree = class private Root: PItem; public constructor Create; procedure Add(Key: TInfo); procedure Del(Key: TInfo); procedure View; procedure Exist(Key: TI nfo); destructor Destroy; override; end; //------------------------------------------------------------- constructor TTree.Create; begin Root := nil; end; //------------------------------------------------------------- procedure TTree.Add(Key: TInfo); procedure IniTree(var P: PItem; X: TInfo); // создание корня дерева begin New(P); P^.Key :=X; P^.Left := nil; P^.Right := nil; end; procedure InLeft (var P: PItem; X : TInfo); // добавление узла слев а var R : PItem; begin New(R); R^.Key := X; R^.Left := nil; R^.Right := nil; P^.Left := R; end; procedure InRight (var P: PItem; X : TInfo); // добавить узел справа var R : PItem; begin New(R); R^.Key := X; R^.Left := nil; R^.Right := nil; P^.Right := R; end; procedure Tree_Add (P: PItem; X : TInfo); var OK: Boolean; begin OK := false; while not OK do begin if X > P^.Key then // посмотреть направо if P^.Right <> nil / / правый узел не nil then P := P^.Right // обход справа else begin //правый узел - лист и надо добавить к нему элемент InRight (P, X); // и конец OK := true; end else //посмотреть налево if P ^.Left <> nil //левый узел не nil then P := P^.Left //обход слева else begin //левый узел -лист и надо добави ть к нему элемент InLeft(P, X); // и конец OK := true end; end; // цикла while end; begin if Root = nil then IniTree(Root, Key) else Tree_Add(Root, Key); end; //------------------------------------------------------------- procedure TTree.Del(Key: TInfo); procedure Delete (var P: PItem; X: TInfo); var Q: PItem; procedu re Del(var R: PItem); //процедура удаляет узе л имеющий двух потомков , заменяя его на самый правый //узел левого поддерева begin if R^.Right <> nil then //обойти дерево справа Del ( R ^. Right ) else begin //дошли до самог о правого узла //заменить этим узлом удаляемый Q^.Key := R^.Key; Q := R; R := R^.Left; end; end; //Del begin //Delete if P <> nil then // искать удаляемый узел if X < P^.Key then Delete(P^.Left, X) else if X > P^.Key then Delete(P^.Right, X) //искать в правом поддереве else begin //узел найден , надо его удалить //сохранить ссылку на удаленный узел Q := P ; if Q^.Right = nil then // справа nil //и ссылку на узел надо заменить ссылкой на этого потомка P := Q^.Left else if Q^.Left = nil then //слева nil //и ссылку на узел на до з аменить ссылкой на этого потомка P := P^.Right else //узел имеет двух потомков Del(Q^.Left); Dispose(Q); end else WriteLn('Такого элемента в дереве нет '); end; begin Delete(Root, Key); end; //------------------------------------------------------------- procedure TTree.View; procedure PrintTree(R: PItem; L: Byte); var i: Byte; begin if R <> nil then begin PrintTree(R^.Right, L + 3); for i := 1 to L do Write(' '); WriteLn(R^.Key); PrintTree(R^.Left, L + 3); end; end; begin PrintTree (Root, 1); end; //------------------------------------------------------------- procedure TTree.Exist(Key: TInfo); procedure Search(var P: PIt em; X: TInfo); begin if P = nil then begin WriteLn('Такого элемента нет '); end else if X > P^. Key then //ищется в правом поддереве Search (P^. Right, X) else if X < P^. Key then Search (P^. Left, X) else WriteLn('Есть такой элемент '); end; begin Search(Root, Key); end; //------------------------------------------------------------- destructor TTree.Destroy; procedure Node_Dispose(P: PItem); //Удаление узла и вс ех его потомк ов в дереве begin if P <> nil then begin if P^.Left <> nil then Node_Dispose (P^.Left); if P^.Right <> nil then Node_Dispose (P^.Right); Dispose(P); end; end; begin Node_Dispose(Root); end; //------------------------------------------------------------- procedure InputKey(S: String; var Key: TInfo); begin WriteLn(S); ReadLn(Key); end; var Tree: TTree; N: Byte; Key: TInfo; begin Tree := TTree.Create; repeat WriteLn('1-Добавить элемент в дере во '); WriteLn('2-Удалить элемент '); WriteLn('3-Вывести узлы дерева '); WriteLn('4-Проверить существование узла '); WriteLn('5- Выход '); ReadLn(n); with Tree do begin case N of 1: begin InputKey('Введите значе ние добавляемого элемента ', Key); Add(Key); end; 2: begin InputKey('Введите значение удаляемого элемента ', Key); Del ( Key ); end ; 3: View ; 4: begin InputKey('Вв едите элеме нт , существование которого вы хотите проверит ь ', Key); Exist(Key); end; end; end; until N=5; Tree.Destroy; end. #include #pragma hdrstop typedef int TInfo; typedef struct Item* PItem; struct Item TInfo Key; PItem Left, Right; ; class TTree private: PItem Root; public: TTree(); void Add(TInfo Key); void Del(TInfo Key); void View(); void Exist(TInfo Key); ~TTree(); ; //------------------------------------------------------------- TTree::TTree() Root = NULL; //------------------------------------------------------------- static void IniTree(PItem& P, TInfo X) // создание корня дерева P = new Item; P->Key =X; P->Left = NULL; P->Right = NULL; static void Iendleft (PItem& P, TInfo X) // добавление узла слева PItem R; R = new Item; R->Key = X; R->Left = NULL; R->Right = NULL; P->Left = R; static void InRight (PItem& P, TInfo X) // добавить узел справа PItem R; R = new Item; R->Key = X; R->Left = NULL; R->Right = NULL; P->Right = R; static void Tree_Add (PItem P, TInfo X) int OK; OK = false; while (! OK) if (X > P->Key) //посмотреть направо if (P->Right != NULL) //правый узел не NULL P = P->Right; //обход справа else //правый узел - лист и надо добави ть к нему элемент InRight (P, X); // и конец OK = true; else //посмотреть налево if (P->Left != NULL) //левый узел не NULL P = P->Left; //обход слева else //левый узел -лист и надо добавит ь к нему элемент Iendleft(P, X); // и конец OK = true; // цикла while void TTree::Add(TInfo Key) if (Root == NULL) IniTree(Root, Key); else Tree_Add(Root, Key); //-------------------------------------------------------------static void delete_ (PItem& P, TInfo X); static void Del(PItem& R, PItem& Q) //пр оцедура удаляет узел имеющий двух потомков , заменяя его на самый правый //узел левого поддерева if (R->Right != NULL) //обойти дерево справа Del(R->Right, Q); else //дошли до самого правого узла //заменить этим узлом удаляемый Q->Key = R-> Key; Q = R; R = R->Left; //Del static void delete_ (PItem& P, TInfo X) PItem Q; //Delete if (P != NULL) //искать удаляемый у зел if (X < P->Key) delete_(P->Left, X); else if (X > P->Key) delete _(P->Right, X); //искать в правом поддереве else //узел найден , надо его удалить //сохранить ссылку на удаленный узел Q = P ; if (Q->Right == NULL) // справ а NULL //и ссылку на узел надо заменить ссылкой на этого потомка P = Q->Left; else if (Q->Left == NULL) //слева NULL //и ссылку на узел надо заменить ссылкой на этого потомка P = P->Right; else //узел имеет двух потомков Del(Q->Left, Q); delete Q; else cout << "Такого элемента в дереве не т " << endl; void TTree::Del(TInfo Key) delete_(Root, Key); //------------------------------------------------------------- static void PrintTree(PItem R, TInfo L) int i; if (R != NULL) PrintTree(R->Right, L + 3); for( i = 1; i <= L; i ++) cout << ' '; cout << R->Key << endl; PrintTree(R->Left, L + 3); void TTree::View() PrintTree (Root, 1); //------------------------------------------------------------- static void Search(PItem& P, TInfo X) if (P == NULL) cout << "Такого элемента нет " << endl; else if (X > P-> Key) //ищется в правом поддереве Search (P-> Right, X); else if (X < P-> Key) Search (P-> Left, X); else cout << " Есть такой элемент " << endl; void TTree::Exist(TInfo Key) Search(Root, Key); //------------------------------------------------------------- static void Node_Dispose(PItem P) //Удаление узла и всех ег о потомков в дерев е if (P != NULL) if (P->Left != NULL) Node_Dispose (P->Left); if (P->Right != NULL) Node_Dispose (P->Right); delete P; TTree::~TTree() Node_Dispose(Root); //------------------------------------------------------------- void inputKey(string S, TInfo& Key) cout << S << endl; cin >> Key; TTree *Tree = new TTree; int N; TInfo Key; int main(int argc, const char* argv[]) do cout << "1-Добавить э лемент в дерево " << endl; cout << "2-Удалить элемент " << endl; cout << "3-Вывести узлы дерева " << endl; cout << "4-Проверить существование узла " << endl; cout << "5- Выход " << endl; cin >> N; switch (N) case 1: inputKey(" Введите значение добавляемого элемента ", Key); Tree->Add(Key); break; case 2: inputKey("Введите значение удаляемого элемента ", Key); Tree->Del(Key); break; case 3: Tree->View(); break; case 4: inputKey("Введите элемент , существование которо го вы хотите проверить ", Key); Tree->Exist(Key); break; while (!(N==5)); return EXIT_SUCCESS;
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Почему девки в старину прыгали через костер?
- Тогда ещё не изобрели эпилятор.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по программированию "Структуры данных: бинарное упорядоченное несбалансированное дерево", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru