数据结构实习报告

数据结构实习报告学号：20091002527姓名：金学玉班级：116092—10【实习一】线性表及其应用【问题描述】大数运算——计算n的阶乘（n>=20）。【基本要求】（1）数据的表示和存储；（1.1）累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求；（1.2）试设计合适的存储结构，要求每个元素或节点最多存储数据的3位数值。（2）数据的操作及其实现：基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。【测试数据】（1）n＝20，n！＝2432902008176640000（2）n＝30，n！＝265252859812191058636308480000000算法思想：首先设计数据的存储结构，本题只能采用整型表示累积运算的中间结果和最终的计算结果，故设计一个动态存储结构实现对数据的存储。对数据的操作及其实现，该题中两个乘数的运算要考虑到：乘数的各位数都要与被乘数进行乘法运算，乘法过程中的进位问题及其实现，因每个元素或节点最多存储数据的3位数值，故当元素或节点中的数值大于999，需向前一个元素或节点进位。综上所述：本题可采用链式存储结构实现——普通单链表，其长度可以扩充，每一个数据元素占用一个结点，一个结点由两个域组成，一个域存放数据元素，其数据类型由问题决定，本体数据类型为实型，一个域存放指向该链表中下一个结点的指针，给出下一个结点的开始存储地址。需要注意的是：每个节点存储三位数据，进行运算时，从头节点开始乘，所得数据暂存在节点data域中，如果它大于999，则向前进位，进位为data/1000，如果前位为空，则新建一个节点，新建节点的data为该data/1000，只要某一位有进位，则从该点依次向检查，如果因加了进位后使自己data大于999，则继续向前进位，直到每位节点数据都小于999，输出结果时：如果节点数据域的值不足三位，应注意在前补0以补足三位。程序实现代码：#if!defined_CHAIN_#define_CHAIN_#include"stdafx.h"#include"xcept.h"//循环链表模板template<classT>classChainNode{public: T data; ChainNode<T>* link; ChainNode<T>* back;};template<classT>classChain{public: Chain(); ~Chain(); bool IsEmpty()const { returnfirst->link==first; } int Length()const; bool Find(intk,T&x)const; int Search(constT&x)const; Chain<T>& Delete(intk,T&x); Chain<T>& Insert(intk,constT&x); ChainNode<T>* Iterator(intk); T* ExData(intk); Chain<T>& ChData(ChainNode<T>*p,constT&x); void Output();private: ChainNode<T>* first; //指向第一个节点的指针 int length;// ChainNode<T>* pCurSel;// int nCurSel;};template<classT>Chain<T>::Chain(){ first=newChainNode<T>; first->link=first; first->back=first; length=0;}template<classT>Chain<T>::~Chain(){ ChainNode<T>* p=first->link; ChainNode<T>* q; while(p!=first) { q=p; p=p->link; deleteq; } deletefirst;}template<classT>int Chain<T>::Length()const{ returnlength;}template<classT>bool Chain<T>::Find(intk,T&x)const{ if(k<1||k>length) returnfalse; x=Iterator(k)->data; returntrue;}template<classT>int Chain<T>::Search(constT&x)const{ ChainNode<T>* current=first->link; int index=1; first->data=x; while(current->data!=x) { current=current->link; index++; } return((current==first)?0:index);}template<classT>Chain<T>& Chain<T>::Delete(intk,T&x){ if(k<1||k>length) throwOutOfBounds(); ChainNode<T>* q=Iterator(k-1); ChainNode<T>* p; if(k==1) q=first; p=q->link; q->link=p->link; p->link->back=q; x=p->data; deletep; length--; return*this;}template<classT>Chain<T>& Chain<T>::Insert(intk,constT&x){ if(k<0||k>length) throwOutOfBounds(); ChainNode<T>* q=Iterator(k); ChainNode<T>* p; p=q->link; ChainNode<T>* y=newChainNode<T>; y->data=x;q->link=y; y->link=p;p->back=y; y->back=q; length++; return*this;}template<classT>ChainNode<T>* Chain<T>::Iterator(intk){ ChainNode<T>* current=first; if(k<=length/2) { for(inti=0;i<k;i++) current=current->link; } else { for(inti=0;i<length-k+1;i++) current=current->back; } returncurrent;}template<classT>T* Chain<T>::ExData(intk){ if(k<1||k>length) throwOutOfBounds(); ChainNode<T>* q=Iterator(k); return &(q->data);}template<classT>Chain<T>& Chain<T>::ChData(ChainNode<T>*q,constT&x){ q->data=x%10000; if(x>9999) { if(q->link==first) Insert(length,0); int m=q->link->data; m+=x/10000; ChData(q->link,m); } return*this;}template<classT>void Chain<T>::Output(){}template<classT>classChainIterator{public: T* Initialize(constChain<T>&c) { location=c.first->link; if(c.first) return&location->data; return0; } T* Next() { if(!c.first) return0; location=location->link; if(location!=first) return&location->data; return0; }private: ChainNode<T> *location;};#endif#if!defined_XCEPT_#define_XCEPT_#include"stdafx.h"classOutOfBounds{public: OutOfBounds() {}};#include"stdafx.h"#include"xcept.h" //异常处理头文件#include"Chain.h" //循环链表头文件#include"time.h"#include<iostream>usingnamespacestd;void Factorial(Chain<int>&A,intn);void Output(Chain<int>&A);int_tmain(intargc,_TCHAR*argv[]){ long t_Sta,t_End; Chain<int> A; int n; cout<<"阶乘计算，请输入n："; cin>>n; try { t_Sta=clock(); Factorial(A,n); t_End=clock(); cout<<"计算用时："<<double(t_End-t_Sta)/CLK_TCK<<"秒"<<endl; t_Sta=clock(); cout<<n<<"的阶乘为："; Output(A); cout<<endl; t_End=clock(); cout<<"输出用时："<<double(t_End-t_Sta)/CLK_TCK<<"秒"<<endl; } catch(...) { cerr<<"警告：越界，访问了不存在的元素！"<<endl; } return0;}void Factorial(Chain<int>&A,intn){ int i,j,k; long m; ChainNode<int>* current; A.Insert(0,1); for(i=2;i<=n;i++) { k=A.Length(); current=A.Iterator(0); current=current->back; for(j=k;j>=1;j--) { m=*A.ExData(j); m=m*i; A.ChData(current,m); current=current->back; } }}void Output(Chain<int>&A){ int i,k,Num,m,l; k=A.Length(); for(i=k;i>0;i--) { l=*A.ExData(i); if(i==k) { cout<<l; continue; } m=l; Num=0; while(m) { m=m/10; Num++; } for(intj=0;j<4-Num;j++) cout<<'0'; if(l) cout<<l; }}程序运行效果：【实习二】题目一：数组和矩阵1、扩充Array1D类，重载操作符<<(输入一个数组)、+、*=、/=和-=。并编写程序实现。2、设计一个三维数组类Array3D<T>。并编写程序实现。3、扩充Matrix类，增加一个转置矩阵的功能。并编写程序实现。4、请比较Matrix类和Array2D类的减法和乘法所需时间的性能。程序实现代码：#pragmaonce#include"xcept.h"template<classT>classArray1D{public: Array1D(intsz=0); Array1D(constArray1D<T>&v); ~Array1D(){delete[]element;} intSize(){returnsize;} T&operator[](inti)const; Array1D<T>&operator=(constArray1D<T>&v); Array1D<T>&ReSize(intsz);private: int size; //数组大小 T *element; //一维数组};template<classT>Array1D<T>::Array1D(intsz){ if(sz<0) throwBadInitializers(); size=sz; element=newT[sz];}template<classT>Array1D<T>::Array1D(constArray1D<T>&v){ size=v.size; element=newT[size]; for(inti=0;i<size;i++) element[i]=v.element[i];}template<classT>T&Array1D<T>::operator[](inti)const{ if(i<0||i>=size) throwOutOfBounds(); returnelement[i];}template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&v){ if(this!=&v) { size=v.size; delete[]element; element=newT[size]; for(inti=0;i<size;i++) element[i]=v.element[i]; } return*this;}template<classT>Array1D<T>&Array1D<T>::ReSize(intsz){ if(size!=sz) { size=sz; delete[]element; element=newT[size]; } return*this;}#pragmaonce#include"xcept.h"#include"Array1D.h"//Array1Dtemplate<classT>classArray2D{public: Array2D(intr=0,intc=0); Array2D(constArray2D<T>&m); ~Array2D(){delete[]element;} int Rows()const{returnrows;} int Columns()const{returncols;} Array1D<T>&operator[](inti)const; Array2D<T>&operator=(constArray2D<T>&m); Array2D<T>&ReSize(intr,intc);private: int rows,cols; Array1D<T> *element;};template<classT>Array2D<T>::Array2D(intr,intc){ if(r<0||c<0) throwBadInitializers(); if((!r||!c)&&(r||c)) throwBadInitializers(); rows=r; cols=c; element=newArray1D<T>[r]; for(inti=0;i<r;i++) element[i].ReSize(c);}template<classT>Array2D<T>::Array2D(constArray2D<T>&m){ rows=m.rows; cols=m.cols; element=newArray1D<T>[rows]; for(inti=0;i<rows;i++) element[i]=m.element[i];}template<classT>Array1D<T>&Array2D<T>::operator[](inti)const{ if(i<0||i>rows) throwOutOfBounds(); returnelement[i];}template<classT>Array2D<T>&Array2D<T>::operator=(constArray2D<T>&m){ if(this!=&v) { rows=v.rows; cols=v.cols; delete[]element; element=newArray1D<T>[rows]; for(inti=0;i<rows;i++) element[i]=v.element[i]; } return*this;}template<classT>Array2D<T>&Array2D<T>::ReSize(intr,intc){ if(rows!=r||cols!=c) { rows=r; cols=c; delete[]element; element=newArray1D<T>[rows]; for(inti=0;i<r;i++) element[i].ReSize(c); } return*this;}#pragmaonce#include"Array2D.h"//Array1Dtemplate<classT>classArray3D{public: Array3D(intr=0,intc=0,inth=0); Array3D(constArray2D<T>&m); ~Array3D(){delete[]element;} int Rows()const{returnrows;} int Columns()const{returncols;} intHight()const{returnhights;} Array2D<T>&operator[](inti)const; Array3D<T>&operator=(constArray2D<T>&m);private: int rows,cols,hights; Array2D<T> *element;};template<classT>Array3D<T>::Array3D(intr,intc,inth){ if(r<0||c<0||h<0) throwBadInitializers(); if((!r||!c||!h)&&(r||c||h)) throwBadInitializers(); rows=r; cols=c; hights=h; element=newArray2D<T>[h]; for(inti=0;i<h;i++) element[i].ReSize(r,c);}template<classT>Array3D<T>::Array3D(constArray2D<T>&m){ rows=m.rows; cols=m.cols; hights=m.hights; element=newArray2D<T>[hights]; for(inti=0;i<hights;i++) element[i]=m.element[i];}template<classT>Array2D<T>&Array3D<T>::operator[](inti)const{ if(i<0||i>hights) throwOutOfBounds(); returnelement[i];}template<classT>Array3D<T>&Array3D<T>::operator=(constArray2D<T>&m){ if(this!=&v) { rows=v.rows; cols=v.cols; hights=v.hights; delete[]element; element=newArray1D<T>[hights]; for(inti=0;i<hights;i++) element[i]=v.element[i]; } return*this;}#include"stdafx.h"#include"Array3D.h"#include<iostream>usingnamespacestd;int_tmain(intargc,_TCHAR*argv[]){ Array3D<int> A(8,8,8); intx,y,z; cout<<"***Array3D***"<<endl; try { A[2][3][4]=5; cout<<A[2][3][4]<<endl; } catch(...) { cout<<"Error!"<<endl; } return0;}运行结果：【实习二】题目二：算术表达式求值【问题描述】对一个合法的中缀表达式求值。假设表达式只包含+、-、*、/四个双目运算符，并且允许有括号出现，运算符本身不具有二义性。例如：3.5*(7+2)/(-6)【基本要求】正确解释表达式；符合四则运算规则：先乘除、后加减从左到右运算先括号内，后括号外输出最后的计算结果算法思想：为实现算符优先算法，该题目建立两个工作站，一个为OPTR，另一个为OPND，用以寄存操作数和运算结果。首先，置操作数栈为空，表达式起始符#为运算符栈的栈底元素；其次，一次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。程序实现代码：#include<stdlib.h>#include<string.h>#defineDEBUG#defineNULL0#defineERROR-1#defineSTACKSIZE #include<stdio.h>#include<tchar.h>#include"stdafx.h"classOutOfBounds{public: OutOfBounds() { }};#endif#if!defined_LINKEDSTACK_#define_LINKEDSTACK_#include"xcept.h"template<classT>classNode{public: T data; Node<T> *link;};template<classT>classLinkedStack{public: //构造与析构函数 LinkedStack() { top=0; } ~LinkedStack(); bool IsEmpty()const//如果堆栈为空，则返回true，否则返回false { returntop==0; } bool IsFull()const;//如果堆栈满，则返回true，否则返回false T Top()const;//返回栈顶元素 LinkedStack<T>& Add(constT&x);//向堆栈中添加元素x LinkedStack<T>& Delete(T&x);//删除栈顶元素，并将它的值传递给x LinkedStack<T>& Delete();//删除栈顶元素private: Node<T> *top; //指向栈顶的节点};template<classT>LinkedStack<T>::~LinkedStack(){ Node<T> *next; while(top) { next=top->link; deletetop; top=next; }}template<classT>bool LinkedStack<T>::IsFull()const{}template<classT>T LinkedStack<T>::Top()const{ if(IsEmpty()) throwOutOfBounds(); returntop->data;}template<classT>LinkedStack<T>& LinkedStack<T>::Add(constT&x){ Node<T> *p=newNode<T>; p->data=x; p->link=top; top=p; return*this;}template<classT>LinkedStack<T>& LinkedStack<T>::Delete(T&x){ if(IsEmpty()) throwOutOfBounds(); x=top->data; Node<T> *p=top; top=top->link; deletep; return*this;}template<classT>LinkedStack<T>& LinkedStack<T>::Delete(){ if(IsEmpty()) throwOutOfBounds(); Node<T> *p=top; top=top->link; deletep; return*this;}#endif//Expression.cpp:定义控制台应用程序的入口点。#include"stdafx.h"#include"LinkedStack.h"#include<iostream>#include<string>usingnamespacestd;boolIsNumber(charch){ return(ch>='0'&&ch<='9')||ch=='.';//如果字符为数字，则返回true，否则返回false}boolIsOperator(charch)//如果字符为运算符，则返回true，否则返回false{ switch(ch) { case'+': case'-': case'*': case'/': returntrue; default: returnfalse; }}boolLowerPriority(chara,charb)//如果a的优先级低于b，则返回true，否则返回false{ if((a=='+'||a=='-')&&(b=='*'||b=='/')) returntrue; else returnfalse;}boolIsOpenparen(charch)//如果字符为'('，则返回true，否则返回false{ returnch=='(';}boolIsCloseparen(charch)//如果字符为')'，则返回true，否则返回false{ returnch==')';}boolTransformer(string&inExpr,string&outExpr)//中缀表达式转后缀表达式的算法实现{ string::size_type idx,size; LinkedStack<char> st; char ch; idx=0; size=inExpr.size(); while(idx<size) { ch=inExpr.at(idx); if(IsNumber(ch)) { outExpr+=ch; if(idx!=size-1) { if(!IsNumber(inExpr.at(idx+1))) outExpr+=''; } else outExpr+=''; } elseif(IsOperator(ch)) { while(!st.IsEmpty()&&!IsOpenparen(st.Top())&&!LowerPriority(st.Top(),ch)) { outExpr+=st.Top(); outExpr+=''; st.Delete(); } st.Add(ch); } elseif(IsOpenparen(ch)) { st.Add(ch); } elseif(IsCloseparen(ch)) { if(st.IsEmpty()) { cerr<<"Closeparendon'tmatchopenparen!"; returnfalse; } while(!st.IsEmpty()&&!IsOpenparen(st.Top())) { outExpr+=st.Top(); outExpr+=''; st.Delete(); } if(IsOpenparen(st.Top())) { st.Delete(); } else { cerr<<"Closeparendon'tmatchopenparen!"; returnfalse; } } idx++; } if(idx==size) { while(!st.IsEmpty()&&!IsOpenparen(st.Top())) { outExpr+=st.Top(); outExpr+=''; st.Delete(); } if(!st.IsEmpty()) { cerr<<"Closeparendon'tmatchopenparen!"; returnfalse; } } returntrue;}//后缀式四则计算算法实现doubleCalculate(string&outExpr){ LinkedStack<double> st; string::size_type idx,size; string NumBuff; char ch; double Num=0; idx=0; size=outExpr.size(); while(idx<size) { ch=outExpr.at(idx); if(IsNumber(ch)) { if(outExpr.at(idx+1)!='') { NumBuff+=ch; } else { NumBuff+=ch; Num=atof(NumBuff.c_str()); st.Add(Num); Num=0; NumBuff=""; } } if(IsOperator(ch)) { double Operand1,Operand2; if(!st.IsEmpty()) st.Delete(Operand1); else { cerr<<"ERROR!"; return0; } if(!st.IsEmpty()) st.Delete(Operand2); else { cerr<<"ERROR!"; return0; } switch(ch) { case'+': Operand1=Operand2+Operand1; break; case'-': Operand1=Operand2-Operand1; break; case'*': Operand1=Operand2*Operand1; break; case'/': Operand1=Operand2/Operand1; break; default: break; } st.Add(Operand1); } idx++; } returnst.Top();}int_tmain(intargc,_TCHAR*argv[]){ stringinExpr,outExpr; cout<<"请输入表达式（操作数支持多位数整数）："; cin>>inExpr; if(Transformer(inExpr,outExpr)) { cout<<outExpr<<endl; } else { cerr<<"wrongexpression_r!"<<endl; } cout<<"表达式计算结果："; cout<<Calculate(outExpr)<<endl; return0;}程序运行结果：运行结果：【实习三】二叉树及其应用题目一：二叉树基本算法的实现题目二：确定一棵二叉树功能要求：实现Create方法，要求键盘输入二叉树结点序列，创建一棵二叉树（提示：前序递归）实现SwapTree方法，以根结点为参数，交换每个结点的左子树和右子树（提示：前序递归）增加InorderTree方法，采用非递归方法实现二叉树的中序遍历，可以选择：对BinaryTree模板进行功能扩充；自己定义并实现二叉树类二叉树的创建要求：要求键盘输入二叉树结点序列结点序列可以是前序，也可以是层次空结点以#表示程序实现代码：#ifndefNode_#defineNode_template<classT>classLinkedStack;template<classT>classLinkedQueue;template<classT>classNode{friendLinkedStack<T>;friendLinkedQueue<T>;private:Tdata;Node<T>*link;};#endif#ifndefStack_#defineStack_#include"xcept.h"template<classT>classStack{public:Stack(intMaxStackSize=30);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}TTop()const;Stack<T>&Add(constT&x);Stack<T>&Delete(T&x);private:inttop;//currenttopofstackintMaxTop;//maxvaluefortopT*stack;//elementarray};template<classT>Stack<T>::Stack(intMaxStackSize){MaxTop=MaxStackSize-1;stack=newT[MaxStackSize];top=-1;}template<classT>TStack<T>::Top()const{if(IsEmpty())throwOutOfBounds();//Topfailsreturnstack[top];}template<classT>Stack<T>&Stack<T>::Add(constT&x){if(IsFull())throwNoMem();//addfailsstack[++top]=x;return*this;}template<classT>Stack<T>&Stack<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();//deletefailsx=stack[top--];return*this;}#endif#ifndefxcept_#definexcept_#include<new.h>classBadInitializers{public: BadInitializers(){}};classNoMem{public: NoMem(){}};intmy_new_handler(size_tx){ throwNoMem(); return0;};_PNHOld_Handler_=_set_new_handler(my_new_handler);classOutOfBounds{public: OutOfBounds(){}};classSizeMismatch{public: SizeMismatch(){}};classMustBeZero{public: MustBeZero(){}};classBadInput{public: BadInput(){}};#endifclassBinaryTree;classBinaryTreeNode{ friendBinaryTree;public: BinaryTreeNode(){LeftChild=RightChild=0;} BinaryTreeNode(constint&e) { data=e; LeftChild=RightChild=0; } BinaryTreeNode(constint&e,BinaryTreeNode*l,BinaryTreeNode*r) { data=e; LeftChild=l; RightChild=r; }private: chardata; BinaryTreeNode*LeftChild,*RightChild;};#ifndeflqueue_#definelqueue_#include"Node.h"#include"xcept.h"template<classT>classLinkedQueue{LinkedQueue(){front=rear=0;}//constructor~LinkedQueue();//destructorboolIsEmpty()const{return((front)?false:true);}boolIsFull()const;TFirst()const;//returnfirstelementTLast()const;//returnlastelementLinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x);private:Node<T>*front;//pointertofirstnodeNode<T>*rear;//pointertolastnode};template<classT>LinkedQueue<T>::~LinkedQueue(){Node<T>*next;while(front){next=front->link;deletefront;front=next;}}template<classT>boolLinkedQueue<T>::IsFull()const{Node<T>*p;try{p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}template<classT>TLinkedQueue<T>::First()const{if(IsEmpty())throwOutOfBounds();returnfront->data;}template<classT>TLinkedQueue<T>::Last()const{if(IsEmpty())throwOutOfBounds();returnrear->data;}template<classT>LinkedQueue<T>&LinkedQueue<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=0;if(front)rear->link=p;//queuenotemptyelsefront=p;//queueemptyrear=p;return*this;}template<classT>LinkedQueue<T>&LinkedQueue<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=front->data;Node<T>*p=front;front=front->link;deletep;return*this;}#endif#ifndefBinaryTree_#defineBinaryTree_#include"BinaryTreeNode.h"#include"xcept.h"#include"lqueue.h"#include"Stack.h"int_count;#include<iostream>usingnamespacestd;classBinaryTree{public: BinaryTree(){root=0;} ~BinaryTree(){} boolIsEmpty()const {return((root==0)?false:true);} boolRoot(char&x)const; voidMakeTree(constchar&element,BinaryTree&left,BinaryTree&right); voidBreakTree(char&element,BinaryTree&left,BinaryTree&right); voidPreOrder(void(*Visit)(BinaryTreeNode*u)) {PreOrder(Visit,root);} voidInOrder(void(*Visit)(BinaryTreeNode*u)) {InOrder(Visit,root);} voidPostOrder(void(*Visit)(BinaryTreeNode*u)) {PostOrder(Visit,root);} voidLevelOrder(void(*Visit)(BinaryTreeNode*u)); voidPreOutput() { PreOrder(Output,root); cout<<endl; } voidInOutput() { InOrder(Output,root); cout<<endl; } voidPostOutput() { PostOrder(Output,root); cout<<endl; } voidLevelOutput() { LevelOrder(Output); cout<<endl; } voidDelete() { PostOrder(Free,root); root=0; }intHeight()const {returnHeight(root);} intSize() { _count=0; PreOrder(Add1,root); return_count; }voidCreat(chara[],BinaryTreeNode*&t,intn);//创建一个二叉树 BinaryTree&Creat(chara[],intn);//函数调用，实现返回 voidSwapTree(BinaryTreeNode*&t);//交换二叉树左右孩子 BinaryTree&SwapTree();//调用函数，实现返回 voidInOrder();//中序非递归输出private: BinaryTreeNode*root;voidPreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t); voidInOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t); voidPostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);staticvoidOutput(BinaryTreeNode*t) {cout<<t->data<<'';} staticvoidFree(BinaryTreeNode*t) {deletet;} intHeight(BinaryTreeNode*t)const; staticvoidAdd1(BinaryTreeNode*t) {_count++;}};boolBinaryTree::Root(char&x)const{ if(root) { x=root->data; returntrue; } else returnfalse;}voidBinaryTree::MakeTree(constchar&element,BinaryTree&left,BinaryTree&right){ root=newBinaryTreeNode(element,left.root,right.root); left.root=right.root=0;}voidBinaryTree::BreakTree(char&element,BinaryTree&left,BinaryTree&right){ if(!root) throwBadInput(); element=root->data; left.root=root->LeftChild; right.root=root->RightChild; deleteroot; root=0;}voidBinaryTree::PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t){ if(t) { Visit(t); PreOrder(Visit,t->LeftChild); PreOrder(Visit,t->RightChild); }}voidBinaryTree::InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t){ if(t) { InOrder(Visit,t->LeftChild); Visit(t); InOrder(Visit,t->RightChild); }}voidBinaryTree::PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t){ if(t) { PostOrder(Visit,t->LeftChild); PostOrder(Visit,t->RightChild); Visit(t); }}voidBinaryTree::LevelOrder(void(*Visit)(BinaryTreeNode*u)){ LinkedQueue<BinaryTreeNode*>Q; BinaryTreeNode*t; t=root; while(t) { Visit(t); if(t->LeftChild) Q.Add(t->LeftChild); if(t->RightChild) Q.Add(t->RightChild); try { Q.Delete(t); } catch(OutOfBounds) { return; } }}intBinaryTree::Height(BinaryTreeNode*t)const{ if(!t) return0; inthl=Height(t->LeftChild); inthr=Height(t->RightChild); if(hl>hr) return++hl; else return++hr;}//创建二叉树inti=-1;//数组的下标 voidBinaryTree::Creat(chara[],BinaryTreeNode*&t,intn){ i++; if(i>n) return; if(a[i]=='#')//孩子节点不能为空 { t=NULL; return; } else { t=newBinaryTreeNode(a[i]); Creat(a,t->LeftChild,n); Creat(a,t->RightChild,n); }}BinaryTree&BinaryTree::Creat(chara[],intn){ this->Creat(a,root,n); return*this;}//交换二叉树左右孩子voidBinaryTree::SwapTree(BinaryTreeNode*&t){ if(t) { BinaryTreeNode*temp=NULL; temp=t->LeftChild; t->LeftChild=t->RightChild; t->RightChild=temp; SwapTree(t->RightChild); SwapTree(t->LeftChild); }}BinaryTree&BinaryTree::SwapTree(){ this->SwapTree(root); return*this;}voidBinaryTree::InOrder(){ Stack<BinaryTreeNode*>s;//二叉树指针型的栈 BinaryTreeNode*c; BinaryTreeNode*t=root; while(t) { s.Add(t); t=t->LeftChild; }s.Delete(c); while(c) { printf("%c",c->data); c=c->RightChild; if(c) { while(c) { s.Add(c); c=c->LeftChild; } } if(!c&&!s.IsEmpty()) s.Delete(c); }}#endif#include<iostream>#include"BinaryTree.h"usingnamespacestd;intcount=0;BinaryTreea,x,y,z;voidct(BinaryTreeNode*t){ count++;}BinaryTreeX;#definer100//输入字符的最大长度voidmain(){ intm; y.MakeTree('M',a,a); z.MakeTree('N',a,a); x.MakeTree('F',y,z); y.MakeTree('G',x,a); y.PreOrder(ct); printf("Thesizeis:%d\n",count); printf("逐层遍历得："); y.LevelOutput(); printf("前序遍历得："); y.PreOutput(); printf("中序遍历得："); y.InOutput(); printf("后序遍历得："); y.PostOutput(); m=y.Height(); printf("树的高度为：%d\n",m); charc; intn=0; charar[r]; printf("请输入二叉树的前序序列，空结点以#表示"); while((c=getchar())!='\n')//得到屏幕能够输入的每个字符，赋值给一个数组 { ar[n]=c; n++; } X.Creat(ar,n);//创建一个二叉树 X.PreOutput();//前序输出这个二叉树 X.SwapTree();//交换二叉树左右孩子，并输出 X.PreOutput();printf("输出中序序列为："); X.InOutput(); printf("输出非递归中序序列为："); X.InOrder();//实现中序序列 cout<<endl; system("pause");}运行结果： 【实习四】优先队列及BST一，优先队列基本要求：对Huffman树的方法进行扩充，实现如下功能：1）键盘输入一个字符串，统计每个字符出现的频率；2）输出每个字符的Huffman编码3）计算并输出WPL提高要求：改键盘输入为读文件（任何类型）二，对BST树的方法进行扩充，实现如下功能：1）给定一个节点，寻找并返回：以它为根的子树中，关键值最大的一个节点；TreeMax2）给定一个节点，寻找并返回：以它为根的子树中，关键值最小的一个节点；TreeMin3）寻找并返回：从小到大排序后下标为i的节点，i从0开始；GetByIndex4）给定一个节点，寻找并返回：它在中序遍列中的下一个节点；TreeNext5）给定一个节点，寻找并返回：它在中序遍列中的前一个节点；TreePrev6）把树中节点按照关键字由小到大的顺序，放进一个数组ToArray一，算法思想：程序实现代码：#defineWIN32_LEAN_AND_MEAN #include<stdio.h>#include<tchar.h>#pragmaonce#include"stdafx.h"classOutOfBounds{public: OutOfBounds(){}};#pragmaonceclassBaseChar{public: BaseChar(){BitCode=0;CodeLength=0;} void AddBitCode(constboolb);//向编码尾加入一位，参数为true则加入一位1，反之//加入一位0 int DeleteBitCode();//返回编码头的一位，并删除这一位 int GetBitCode(intn)const;//获取允许范围内的一位编码public: int BitCode; //Huffman编码(二进制) int CodeLength; //bit中编码长度 char AscIIchar; //对应字符};classCharManager{public: CharManager(); ~CharManager(); void InsertChar(charch);//插入一个字符 //根据参数字符返回对应的BaseChar对象 BaseChar& GetBaseChar(charch);public: BaseChar* Char_Array; int* Char_Weight; int CurrentSize;};#pragmaonce#include"CharManager.h"template<classT>classBinaryTree;template<classT>classBinaryTreeNode{ friendclassBinaryTree<T>; friendvoidGetHuffmanCode(CharManager&CM,BinaryTree<int>&tree);public: BinaryTreeNode() { LeftChild=RightChild=NULL; } BinaryTreeNode(constT&e) { data=e; LeftChild=RightChild=NULL; } BinaryTreeNode(constT&e,BinaryTreeNode*l,BinaryTreeNode*r) { data=e; LeftChild=l; RightChild=r; }private: T data; BinaryTreeNode<T> *LeftChild, //Leftsubtree *RightChild; //Rightsubtree};//DefinedBinaryTreetemplate<classT>classBinaryTree{ friendvoidGetHuffmanCode(CharManager&CM,BinaryTree<int>&tree);public: BinaryTree() { root=NULL; } BinaryTree(BinaryTree<T>&ref); ~BinaryTree(); BinaryTree<T>& operator=(BinaryTree<T>&tree); bool IsEmpty()const{return((root)?false:true);} bool Root(T&x)const; BinaryTreeNode<T>*GetpRoot(){returnroot;} bool Create(constchar*str); bool MakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right); bool BreakTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right); void PreOrder(void(*Visit)(BinaryTreeNode<T>*u)){PreOrder(Visit,root);} void InOrder(void(*Visit)(BinaryTreeNode<T>*u)){InOrder(Visit,root);} void PostOrder(void(*Visit)(BinaryTreeNode<T>*u)){PostOrder(Visit,root);}private: BinaryTreeNode<T> *root; //根节点指针 void PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t); void InOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t); void PostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t); staticvoidDestructor(BinaryTreeNode<T>*t) { if(t!=NULL) { deletet; t=NULL; } }};template<classT>BinaryTree<T>::BinaryTree(BinaryTree<T>&ref){ root=ref.root; ref.root=NULL;}template<classT>BinaryTree<T>::~BinaryTree(){ PostOrder(Destructor,root); root=NULL;}template<classT>bool BinaryTree<T>::Root(T&x)const{ if(root) { x=root->data; returntrue; } else returnfalse;}template<classT>bool BinaryTree<T>::Create(constchar*str){ if(!rool) { root=newnewBinaryTreeNode<T>(element); returntrue; } else returnfalse;}template<classT>bool BinaryTree<T>::MakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right){ root=newBinaryTreeNode<T>(element,left.root,right.root); left.root=right.root=NULL; returntrue;}template<classT>bool BinaryTree<T>::BreakTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right){ if(!root) returnfalse; element=root->data; left.root=