数据结构实验报告——实验六
实验题目：排序算法 学号： 201411130001 日期：2015.12.11 班级：计机14.1 姓名：刘方铮 Email：liu191150932@163.com 实验目的：堆和搜索树 任务要求： 一、实验目的 1、掌握堆和搜索树的基本概念，插入、删除方法。 二、实验内容 创建最大堆类。最大堆的存储结构使用链表。 提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。 接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。 堆排序。 软件环境： Win7 操作系统 开发工具：visual C++ 6.0 实验代码： #include #include #include #include using namespace std; class BinaryTreeNode { public: BinaryTreeNode(){ LeftChild=RightChild=0;} BinaryTreeNode(const int & e) { data=e; LeftChild=RightChild=0; } BinaryTreeNode(const int& e,BinaryTreeNode *l,BinaryTreeNode *r) { data=e; LeftChild=l; RightChild=r; } int data; BinaryTreeNode *LeftChild,*RightChild; }; void Travel(BinaryTreeNode* roots){ queue q; while(roots){ cout<data<<\ if(roots->LeftChild)q.push(roots->LeftChild); if(roots->RightChild)q.push(roots->RightChild); try{ roots=q.front(); q.pop (); } catch(...) {return;} } } void PrOrder(BinaryTreeNode* roots){ if(roots){ cout<data<<\ \ PrOrder(roots->LeftChild); PrOrder(roots->RightChild);} } void InOrder(BinaryTreeNode* roots){ if(roots){ InOrder(roots->LeftChild); cout<data<<\ InOrder(roots->RightChild);} } class MaxHeap { public: MaxHeap() { root = 0; state = 0; } void MakeHeap(int element, MaxHeap& left, MaxHeap& right); int Max() { if (!root) return 0; return root->data; } MaxHeap& Insert(const int& x); MaxHeap& DeleteMax(int& x); MaxHeap& Initialize(int a[], int n); void Deactivate(){heap=0;} void HeapSort(int a[],int n); BinaryTreeNode *root, *last,*p_last; int state; void ConditionOrder(BinaryTreeNode *u, int k, int i,BinaryTreeNode *temp); void Adjust(BinaryTreeNode *u); BinaryTreeNode* LocateLast(BinaryTreeNode *u,int k,int i); private: MaxHeap *heap; }; void MaxHeap::MakeHeap(int element, MaxHeap& left, MaxHeap& right) { root = new BinaryTreeNode(element, left.root, right.root); left.root = right.root = 0; last=p_last=root; state++; } BinaryTreeNode* MaxHeap::LocateLast(BinaryTreeNode *u,int k,int i) { if(k<=1) return u; else { int n=(int)pow(2.0,k-1); int s=n/2; if(i<=s) return LocateLast(u->LeftChild,k-1,i); else return LocateLast(u->RightChild,k-1,i-s); } } void MaxHeap::ConditionOrder(BinaryTreeNode *u, int k, int i,BinaryTreeNode *temp) { int half = (int) pow(2.0, k - 2); if (u->data < temp->data) { swap(u->data, temp->data); } if (!u->LeftChild || !u->RightChild) { if (!u->LeftChild) { u->LeftChild = temp; p_last=u; state++; } else { u->RightChild = temp; p_last=u; state++; } } else { if (i <= half) ConditionOrder(u->LeftChild, k - 1, i, temp); else ConditionOrder(u->RightChild, k - 1, i - half, temp); } } MaxHeap& MaxHeap::Insert(const int& x) { if(root){ int k = (int) (log((double)(state)) / log(2.0)) + 1; int index = state - (int) (pow(2.0, k - 1) - 1); int p_index = index / 2 + 1; BinaryTreeNode *temp = new BinaryTreeNode (x); last = temp; if (index == (int) (pow(2.0, k - 1))) { p_index = 1; ConditionOrder(root, k, p_index, temp); } else ConditionOrder(root, k - 1, p_index, temp);}
loading