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

数据结构实验报告实验六实验题目：排序算法 学号： 201411130001日期：2015.12.11班级：计机14.1姓名：刘方铮 Email：liu191150932163.com实验目的：堆和搜索树任务要求：一、实验目的 1、掌握堆和搜索树的基本概念，插入、删除方法。二、实验内容 创建最大堆类。最大堆的存储结构使用链表。提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。堆排序。软件环境：Win7 操作系统开发工具：visual C+ 6.0实验代码：#include <iostream>#include <string>#include<cmath>#include<queue>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<BinaryTreeNode *> q; while(roots) cout<<roots->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<<roots->data<<"" PrOrder(roots->LeftChild); PrOrder(roots->RightChild);void InOrder(BinaryTreeNode* roots)if(roots) InOrder(roots->LeftChild); cout<<roots->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); 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 < u->LeftChild->data) swap(u->data, u->LeftChild->data); Adjust(u->LeftChild); else if (u->data < u->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<n;i+) Insert(ai); return *this; void MaxHeap:HeapSort(int * a,int n)/创建一个最大堆MaxHeap maxHeap;maxHeap.Initialize(a,n);/从最大堆中逐个抽取元素int x;for(int i=n-1;i>=0;i-) maxHeap.DeleteMax(x);/ cout<<"i="<<i<<"-"<<x<<endl;/ Travel(root);cout<<endl; ai=x;/在堆的析构函数中保存数组a/maxHeap.Deactivate();class HTNodepublic:int weight;/权重int parent,lchild,rchild; ; typedef HTNode * HuffmanTree;HuffmanTree HuffmanCoding(char* &HC,int w,int a,int n);void Select(HuffmanTree HT,int n,int&s1,int&s2); void HTEcode(char* &HC,int w,int code,int codeLen,int a,int aLen );void Select(HuffmanTree HT,int n,int&s1,int&s2)int i=1,j;while(HTi.parent!=0) i+; j=i+1;while(HTj.parent!=0) j+;if(HTi.weight>HTj.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.weight<HTs1.weight) s2=s1; s1=i; else if(HTi.weight<HTs2.weight) s2=i; i+;HuffmanTree HuffmanCoding(char *& HC,int w,int a,int n)int i,start,c,f;HTNode *p;char *cd;if(n<1)return NULL;int m=2*n-1;/定义一个有m+1个节点的霍夫曼树HuffmanTree HT=new HTNodem+1; /初始化for(p=HT+1,i=1;i<=n;i+,p+) p->weight=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+) / cout<<"n序号:"<<f<<" 双亲结点:" <<HTf.parent<<" 左孩子结点:" <<HTf.lchild <<" 右孩子结点:" <<HTf.rchild<< " 权值:"<<HTf.weight<<endl; for(int r=0;r<codeLen;r+) cout<<"n"<<coder<<"的字符的赫夫曼编码为:"<<HCr<<endl;for(int i=0;i<aLen;i+) bool find=false; for(j=0;j<codeLen;j+) if(ai=codej) find=true; cout<<HCj; / 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(e<p->data) p=p->LeftChild; else if(e>p->data) p=p->RightChild;BinaryTreeNode * r=new BinaryTreeNode(e);if(root) if(e<pp->data) pp->LeftChild=r; else pp->RightChild=r;else root=r;return *this;DBSTree & DBSTree:BSInitialize(int a,int len) for(int i=0;i<len;i+) BSInsert(ai); return *this;void main() MaxHeap maxHeap;DBSTree bstree;int s, n,sel,Alen;char *codeA;int* IntA,* w;cout<<"输入最大堆元素个数"int len;cin>>len;int * a=new intlen;for(int i=0;i<len;i+) cout<<"输入第"<<i+1<<"个元素"<<endl; cin>>ai;maxHeap.Initialize(a,len);cout<<"最大堆操作:"<<endl;cout<<"0.堆排序"<<endl;maxHeap.HeapSort(a,len);for(int h=0;h<len;h+) cout <<ah<<" " cout <<endl;cout<<"1.初始化层次遍历输出最大堆"<<endl;Travel(maxHeap.root);cout<<endl;cout<<"前序遍历输出最大堆n"PrOrder(maxHeap.root);cout<<endl;cout<<"2.插入整数元素"<<endl;cin>>s;maxHeap.Insert(s);cout<<"层次遍历输出最大堆n"Travel(maxHeap.root);cout<<endl;cout<<"前序遍历输出最大堆n"PrOrder(maxHeap.root);cout<<endl; cout<<"3.删除最大元素n"maxHeap.DeleteMax(s);cout<<"层次遍历输出最大堆n" Travel(maxHeap.root);cout<<endl; /cout<<"Huffman操作"cout<<"输入元素个数"<<endl;cin>>Alen;IntA=new intAlen;w=new intAlen;for(n=0;n<Alen;n+) cout<<"n输入第"<<n+1<<"个元素n" cin>>IntAn; cout<<"n输入对应权值n" cin>>wn;HuffmanCoding(codeA,w,IntA,len);HTEcode(codeA,w,IntA,Alen,a,len); cout<<endl;/cout<<"二叉搜索树层次遍历"<<endl;cout<<"输入二叉搜索树元素个数" int bslen; cin>>bslen; int * b=new intbslen; for(int j=0;j<bslen;j+) cout<<"输入第"<<j+1<<"个元素"<<endl; cin>>bj; bstree.BSInitialize(b,bslen); cout<<"前序遍历输出二叉搜索树: "<<endl;PrOrder(bstree.root);cout<<endl;cout<<"中序遍历输出二叉搜索树: "<<endl;InOrder(bstree.root);cout<<endl;cout<<"层次遍历输出二叉搜索树: "<<endl; Travel(bstree.root);cout<<endl;实验结果：