山东大学数据结构实验报告六.doc
《山东大学数据结构实验报告六.doc》由会员分享,可在线阅读,更多相关《山东大学数据结构实验报告六.doc(13页珍藏版)》请在三一文库上搜索。
1、数据结构实验报告实验六实验题目:排序算法 学号: 201411130001日期:2015.12.11班级:计机14.1姓名:刘方铮 Email:实验目的:堆和搜索树任务要求:一、实验目的 1、掌握堆和搜索树的基本概念,插入、删除方法。二、实验内容 创建最大堆类。最大堆的存储结构使用链表。提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。接收键盘录入的一系列整数,输出其对应的最大堆、Huffman编码以及二叉搜索树。堆排序。软件环境:Win7 操作系统开发工具:visual C+ 6.0实验代码:#include #include #include#includ
2、eusing 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 T
3、ravel(BinaryTreeNode* roots) queue q; while(roots) coutdataLeftChild)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) coutdataLeftChild); PrOrder(roots-RightChild);void InOrder(BinaryTr
4、eeNode* roots)if(roots) InOrder(roots-LeftChild); coutdataRightChild);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& In
5、itialize(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: M
6、axHeap *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
7、,k-1); int s=n/2; if(iLeftChild,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 data) swap(u-data, temp-data); if (!u-LeftChild | !u-RightChild) if (!u-LeftChild) u-Le
8、ftChild = temp; p_last=u; state+; else u-RightChild = temp; p_last=u; state+; else if (i 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) (p
9、ow(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); else root = new BinaryTreeNode(x); last=p_last=root;
10、state+; return *this; void MaxHeap:Adjust(BinaryTreeNode *u) if (!u-LeftChild & !u-RightChild) return; else if(u-LeftChild & u-RightChild) if (u-LeftChild-data u-RightChild-data) if (u-data LeftChild-data) swap(u-data, u-LeftChild-data); Adjust(u-LeftChild); else if (u-data RightChild-data) swap(u-d
11、ata, u-RightChild-data); Adjust(u-RightChild); MaxHeap& MaxHeap:DeleteMax(int& x) if (!root) exit(1) ; else if(!last) x=root-data; state=0;root=0; else x = root-data; root-data = last-data; int k = (int)(log(double)(state)/log(double)(2)+ 1; int index = state - (int)(pow(2.0, k - 1) - 1); Adjust(roo
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 山东大学 数据结构 实验 报告
链接地址:https://www.31doc.com/p-5728648.html