山东大学数据结构实验六.doc

数据结构实验报告实验六实验题目：排序算法 学号： 日期：2014.12.4班级：物联网工程姓名： Email：实验目的：堆和搜索树任务要求：一、实验目的 1、掌握堆和搜索树的基本概念，插入、删除方法。二、实验内容 创建最大堆类。最大堆的存储结构使用链表。提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。堆排序。软件环境：Win7 操作系统开发工具：visual C+ 6.0实验步骤：#include #include #include#includeusing 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) 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(BinaryTreeNode* 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& 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(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-LeftChild = 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) (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); else root = new BinaryTreeNode(x); last=p_last=root; 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-data, 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(root); if(index%2) p_last-LeftChild=0; else p_last-RightChild=0; delete last; state-; k = (int)(log(double)(state-1)/log(double)(2)+ 1; index = state - 1 - (int)(pow(2.0, k - 1) - 1); int p_index = index / 2 + 1; if (index = (int) (pow(2.0, k - 1) p_index=1; p_last=LocateLast(root,k,p_index); else p_last=LocateLast(root,k-1,p_index); if(!p_last-RightChild) last=p_last-LeftChild; else last=p_last-RightChild; return *this; MaxHeap& MaxHeap:Initialize(int a, int n) MaxHeap LMaxHeap,RMaxHeap; MakeHeap(a0,LMaxHeap,RMaxHeap); for(int i=1;i=0;i-) maxHeap.DeleteMax(x);/ couti=i-xendl;/ Travel(root);coutHTj.weight) s1=j;/s1为权重小的 s2=i;else s1=i; s2=j;i=j+1;while(i=n) if(HTi.parent!=0) i+; else if(HTi.weightHTs1.weight) s2=s1; s1=i; else if(HTi.weightHTs2.weight) s2=i; i+;HuffmanTree HuffmanCoding(char *& HC,int w,int a,int n)int i,start,c,f;HTNode *p;char *cd;if(n1)return NULL;int m=2*n-1;/定义一个有m+1个节点的霍夫曼树HuffmanTree HT=new HTNodem+1; /初始化for(p=HT+1,i=1;iweight=wi-1; p-lchild=0; p-rchild=0; p-parent=0; int s1,s2;for(;i=m;+i) Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.parent=0; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;HC=new char* n;cd=new charn; cdn-1=0; for(i=1;i=n;+i) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi-1=new charn-start; strcpy(HCi-1,&cdstart); return HT;void HTEcode(char* &HC,int w,int code,int codeLen,int a,int aLen ) int j;HuffmanTree HT=HuffmanCoding(HC,w,code,codeLen); /for(int f=1;f=2*codeLen-1;f+) / coutn序号:f 双亲结点: HTf.parent 左孩子结点: HTf.lchild 右孩子结点: HTf.rchild 权值:HTf.weightendl; for(int r=0;rcodeLen;r+) coutncoder的字符的赫夫曼编码为:HCrendl;for(int i=0;iaLen;i+) bool find=false; for(j=0;jcodeLen;j+) if(ai=codej) find=true; coutHCj; / if(!find) / cout空; class DBSTreepublic :DBSTree()root=0;BinaryTreeNode * root;DBSTree & BSInitialize(int a,int len); DBSTree & BSInsert(const int& e);DBSTree & DBSTree:BSInsert(const int& e)BinaryTreeNode *p=root,*pp=0;while(p) pp=p; if(edata) p=p-LeftChild; else if(ep-data) p=p-RightChild;BinaryTreeNode * r=new BinaryTreeNode(e);if(root) if(edata) pp-LeftChild=r; else pp-RightChild=r;else root=r;return *this;DBSTree & DBSTree:BSInitialize(int a,int len) for(int i=0;ilen;i+) BSInsert(ai); return *this;void main() MaxHeap maxHeap;DBSTree bstree;int s, n,sel,Alen;char *codeA;int* IntA,* w;coutlen;int * a=new intlen;for(int i=0;ilen;i+) cout输入第i+1个元素ai;maxHeap.Initialize(a,len);cout最大堆操作:endl;cout0.堆排序endl;maxHeap.HeapSort(a,len);for(int h=0;hlen;h+) cout ah ; cout endl;cout1.初始化层次遍历输出最大堆endl;Travel(maxHeap.root);coutendl;cout前序遍历输出最大堆n;PrOrder(maxHeap.root);coutendl;cout2.插入整数