数据结构实验报告图的基本运算及飞机换乘次数最少问题.doc

实验报告实验名称：二叉树的基本操作及哈夫曼编码译码系统的实现 一、问题描述1.实验目的和要求a.创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。b.哈夫曼编码/译码系统。2.实验任务：能成功演示二叉树的有关运算，运算完毕后能成功释放二叉树所有结点占用的系统内存3. 实验内容：a. 创建一棵二叉树；先序、中序和后序遍历这棵二叉树；计算二叉树结点个数b. 哈夫曼编码译码系统二 程序设计三 .程序代码主函数：#includeCreateHfmTree.h#include#includeusing namespace std;void main() coutendlendl; coutM-Show this menu.endl; coutB-Build up tree: read character set and frequency of each character, build up hfm tree.endl; coutT-Trace the tree: PreOrder and InOrder the BTree.endl; coutE-Generate code: According to the builded up hfm tree, generate the codes for all character.endl; coutC-Encode: Input arbitary string formed by characters which have been generated code, utilize the codes to ecode and print the result of encoding.(end with #)endl; coutD-Translate: read codefile.txt, utilize the exisiting hfm tree to translate code and restore code Into hardware file result.txt.endl; coutP-Print: Print the contents of file: textfile.txt, codefile.txt, result.txt on the screen.endl; coutX-Exit: Exit this system.endl; cout-Delete: Delete character set, character frequencies, codes and HfmTree if they are exist.endl; int w100; char data100; int n; char choice; int i,j; HfmTree hfm; HfmNode* ht; HfmCode* hc;char s1000;repeat1:coutendl; coutchoice;coutendl;if(choice=b | choice=B) coutn; cout-endl; coutAllocating the memory.endl; coutAllocating the complete.endl; cout-endl; coutPlease input all the elementary codes: endl; for(int i=0;idatai; coutPlease input all the Frenquencies: endl; for(i=0;iwi; hfm=CreateHfmTree(w,data,4); goto repeat1; if(choice=t | choice=T) couthfm; hfm.PreOrder(Visit); couthfm; hfm.InOrder(Visit); goto repeat1; if(choice=e | choice=E) coutGenerating code.endl; ht=new HfmNode2*n-1; hc=new HfmCoden; hfm.Grcode(w,data,n,ht,hc); for( i=0;in;i+) couthti.word:; for( j=hci.start+1;jn;j+) couthci.bitj; coutendl; coutCode Generate complete.endl; goto repeat1; if(choice=c | choice=C)coutPlease input the article that you want to code: ch;si+=ch;if(ch=#)break;int length=i; ofstream outf(testfile.txt); if(!outf) coutCant Open the file!; return; i=0; while(si!=#) outf.put(si); i+; outf.close();coutendl; coutResult of encoding: ; hfm.Encode(ht,hc,n,testfile.txt,codefile.txt);coutendl;coutEncoding complete.endlendl;goto repeat1;if(choice=d | choice=D)coutStarting translating code.endl;coutResult:;hfm.Decode(ht,n,codefile.txt,resultfile.txt);coutendl;goto repeat1;if(choice=p | choice=P)cout-testfile.txt-endl; hfm.Print(testfile.txt);cout-endl; coutendlendl; cout-codefile.txt-endl; hfm.Print(codefile.txt);cout-endl; coutendlendl; cout-resultfile.txt-endl; hfm.Print(resultfile.txt);cout-endl; coutendlendl;goto repeat1; if(choice=x | choice=X)return;if(choice=-)hfm.Clear();coutDelete All.endl;goto repeat1;二叉树类：#includeBTNode.h#includeseqqueue.htemplateclass BinaryTreepublic:BinaryTree() root=NULL; bool IsEmpty() const; void Clear(); bool Root(T& x) const; void MakeTree(const T& x,BinaryTree& left,BinaryTree& right); void MakeTree(const T& x,const T& y,BinaryTree& left,BinaryTree& right);void BreakTree(T& x,BinaryTree& left,BinaryTree& right); void PreOrder(void (*Visit) (T& x); void InOrder(void (*Visit) (T& x); void PostOrder(void (*Visit) (T& x); void LevalOrder(); int Size();protected:BTNode *root;private:void Clear(BTNode* t);void PreOrder(void (*Visit) (T& x),BTNode *T); void InOrder(void (*Visit) (T& x),BTNode *T); void PostOrder(void (*Visit) (T& x),BTNode *T); void LevalOrder(BTNode* t); int Size(BTNode* t);templatebool BinaryTree:IsEmpty() constreturn root=NULL;templatevoid BinaryTree:Clear(BTNode* t) if(t) if(t-lChild) Clear(t-lChild); if(t-rChild) Clear(t-rChild); delete t; t=NULL; templatevoid BinaryTree:Clear()Clear(root);template bool BinaryTree:Root(T &x) const if (root)x=root-element;return true;else return false;template void BinaryTree:MakeTree(const T& x, BinaryTree& left, BinaryTree& right) couthere in BinaryTree:MakeTree.endl; if(root | &left=&right) return;root=new BTNode(x,left.root,right.root);left.root=right.root=NULL;template void BinaryTree: MakeTree(const T& x,const T& y,BinaryTree& left,BinaryTree& right) if(root | &left=&right) return;root=new BTNode(x,y,left.root,right.root);left.root=right.root=NULL;template void BinaryTree:BreakTree(T &x,BinaryTree&left, BinaryTree& right) couthere in BinaryTree:BreakTree.element;left.root=root-lChild; right.root=root-rChild;delete root;root=NULL;templatevoid Visit(T& x)coutx ;template void BinaryTree:PreOrder(void (*Visit)(T& x) cout先序遍历为： ;PreOrder(Visit,root);coutendl;templatevoid BinaryTree:PreOrder(void (*Visit) (T& x),BTNode *t) if(t)Visit(t-element);PreOrder(Visit,t-lChild);PreOrder(Visit,t-rChild);template void BinaryTree:InOrder(void (*Visit)(T& x) cout中序遍历为： ;InOrder(Visit,root);coutendl;template void BinaryTree:InOrder (void (*Visit)(T& x),BTNode* t) if (t)InOrder(Visit,t-lChild);Visit(t-element);InOrder(Visit,t-rChild);template void BinaryTree:PostOrder(void (*Visit)(T& x) cout后序遍历为： ;PostOrder(Visit,root);coutendl;template void BinaryTree:PostOrder(void (*Visit)(T& x),BTNode* t) if (t) PostOrder(Visit,t-lChild);PostOrder(Visit,t-rChild);Visit(t-element);template void BinaryTree:LevalOrder(BTNode* t) SeqQueueBTNode* q(100); if(!t) return ; q.EnQueue(t); while(!q.IsEmpty() t=q.DeQueue(); coutelementlChild) q.EnQueue(t-lChild); if(t-rChild) q.EnQueue(t-rChild); coutendl; templatevoid BinaryTree:LevalOrder()LevalOrder(root);templateint BinaryTree:Size(BTNode* t) if(!t) return 0; elsereturn Size(t-lChild)+Size(t-lChild)+1;templateint BinaryTree:Size()return Size(root);二叉树结点类：#includetemplatestruct BTNode BTNode() lChild=rChild=NULL; BTNode(const T& x) element=x; lChild=rChild=NULL; BTNode(const T& x,BTNode* l,BTNode* r) element=x; lChild=l; rChild=r; BTNode(const T& x,const T& y,BTNode* l,BTNode* r) element=x; word=y; lChild=l; rChild=r; T element;T word; BTNode *lChild,*rChild; ;哈夫曼树类：#includeBinaryTree.h #includestruct HfmNodechar word; int weight; int parent; int lchild; int rchild;struct HfmCode int bit10000; int start; int weight;templateclass HfmTree:public BinaryTreepublic:operator T()const return weight; T getW() return weight; void putW(const T& x) weight=x; void SetNull() root=NULL; void Grcode(T w,char c,int n,HfmNode ht,HfmCode hc);void Encode(HfmNode ht,HfmCode hc,int count,char *record,char *tranvers);void Decode(HfmNode ht,int count,char *in,char *fout);void Print(char *in);private: T weight;templatevoid HfmTree:Grcode(T w,char c,int n,HfmNode ht,HfmCode hc) int m1,m2,x1,x2;char d1,d2; int i,j; for(i=0;i2*n-1;i+) if(in) hti.weight=wi; hti.word=ci; else hti.weight=0; hti.word=#; hti.parent=0; hti.lchild=-1; hti.rchild=-1; for(i=0;in-1;i+) m1=m2=1000; x1=x2=0; d1=d2=#; for( j=0;jn+i;j+) if(htj.weightm1 & htj.parent=0) m2=m1; m1=htj.weight; d2=d1; d1=htj.word; x2=x1;x1=j; else if(htj.weightm2 & htj.parent=0) m2=htj.weight; d2=htj.word; x2=j; htx1.parent=n+i; htx2.parent=n+i; htn+i.weight=htx1.weight+htx2.weight; htn+i.lchild=x1; htn+i.rchild=x2; HfmCode cd; int child,parent; for(i=0;in;i+) cd.start=n-1; cd.weight=hti.weight; child=i; parent=htchild.parent; while(parent!=0) if(htparent.lchild=child) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; child=parent; parent=htchild.parent; for(j=cd.start+1;jn;j+) hci.bitj=cd.bitj; hci.start=cd.start; hci.weight=cd.weight; templatevoid HfmTree:Encode(HfmNode ht,HfmCode hc,int count,char *record,char *tranvers) ifstream infile(record); if(!infile)coutCant Open the file!; return; ofstream outf(tranvers); if(!outf)coutCant Open the file!; return; char ch;while(infile.get(ch) for(int i=0;icount;i+) if(ch=hti.word) for(int j=hci.start+1;jcount;j+) outfhci.bitj; couthci.bitj; break; outf#;infile.close();outf.close();templatevoid HfmTree:Decode(HfmNode ht,int count,char *in,char *fout)int i=0; char ch,buffer100; /用来存放编码文件中的字符ifstream infile(in); if(!in)coutCant Open the file!; return;while(infile.get(ch) bufferi+=ch;infile.close();int j=i;int p=2*count-2; ofstream outf(fout); if(!fout)coutCant Open the file!; return;char null= ;/将译码存放在resultfile文件中for(i=0; bufferi!=# &ij;i+ )if(bufferi=0)p=htp.lchild;else p=htp.rchild;if(htp.lchild=-1 & htp.rchild=-1)outfhtp.word; couthtp.word;p=2*count-2;outf.close();templatevoid HfmTree:Print(char *in) ifstream infile(in); if(!infile) coutCant Open the file!; return;char ch;while(infile.get(ch)coutch;coutendl;infile.close();构建哈夫曼树：#includeHfmTree.h #includePrioQueue.htemplateHfmTree CreateHfmTree(T w,char c,int n) PrioQueue HfmTree pq(n);/定义一个元素类型为hfmtree的优先权队列 HfmTree x,y,z,zero; for(int i=0;in;i+) z.MakeTree(wi,ci,x,y); /构造只有一个节点的哈夫曼树对象 z.putW(wi); pq.Append(z); z.SetNull(); for(i=1;in;i+) pq.Serve(x); pq.Serve(y); z.MakeTree(x.getW()+y.getW(),x,y);z.putW(x.getW()+y.getW(); pq.Append(z); z.SetNull(); pq.Serve(z); return z;队列类，优先权队列类：#includetemplateclass Queuepublic:virtual bool IsEmpty() const=0;virtual bool IsFull() const=0;virtual bool Front(T& x) const=0;virtual bool EnQueue(T x)=0;virtual T DeQueue()=0;virtual bool Clear()=0;#includequeue.htemplateclass SeqQueue:public Queuepublic:SeqQueue(int mSize);SeqQueue() delete q;bool IsEmpty() const return front=rear;bool IsFull() const return (rear+1) % maxSize=front;bool Front(T& x)const;bool EnQueue(T x);T DeQueue();bool Clear() front=rear=0;return true;private:int front,rear;int maxSize;T *q;templateSeqQueue:SeqQueue(int mSize)maxSize=mSize;q=new TmaxSize;front=rear=0;/在x中返回队头元素。操作成功返回true,否则返回falsetemplatebool SeqQueue:Front(T& x) constif(IsEmpty()coutEmptyendl; return false; x=q(front+1) % maxSize;return true;/在队尾插入元素x。操作成功返回true,否则返回falsetemplatebool SeqQueue:EnQueue(T x)if(IsFull()coutFullendl; return false;qrear=(rear+1) % maxSize=x;return true;/在队列中删除对头元素。操作成功返回true,否则返回falsetem