数据结构试验报告

1、 数据结构实验报告 班级： 姓名： 学号： 实验三一实验内容：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。一个完整的系统应具有以下功能：（1） I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2） E：编码（Encoding）。利用以建好的哈夫曼树（如不

2、在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3） D：译码（Decoding）。利用已经建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4） P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码，同时将此字符形式的编码写入文件CodePrint中。T：打印哈夫曼树（Tree printing）。将已经在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。二实验目的（1） 掌握二

3、叉树的存储结构及其相关操作。（2） 掌握构造哈夫曼树的基本思想，及其编码/译码过程。三程序清单#include #include #include /定义赫夫曼树结点的结构体typedef struct char ch; /增加一个域，存放该节点的字符int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode; /指向赫夫曼编码的指针void tips(); /打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int); /建立赫夫

4、曼树的算法void select(HuffmanTree HT,int j,int *x,int *y); /从已建好的赫夫曼树中选择parent为0，weight最小的两个结点void Init();void Coding(); /编码void Decoding(); /译码void Print_code(); /打印译码好的代码void Print_tree(); /打印哈夫曼树int Read_tree(HuffmanTree &); /从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m); /译码时

5、根据01字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T100100,int s,int *i,int j); /将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; /全局变量int n=0; /全局变量，存放赫夫曼树叶子结点的数目int main() printf(班级：中法121 姓名：郝雨微 学号：122887n);char select;while(1) tips(); scanf(%c,&select); switch(select) /选择操作，根据不同的序号选择不同的操作 case I:Init();bre

6、ak; case E:Coding();break; case D:Decoding();break; case P:Print_code();break; case T:Print_tree();break; case Q:exit(1); default :printf(Input error!n); getchar();return 0;void tips() /操作选择界面printf( -n);printf( - 请选择操作 -n);printf( -n);printf( n);printf( -I初始化赫夫曼树 -n);printf( -E编码 -n);printf( -D译码 -

7、n);printf( -P打印代码文件 -n);printf( -T打印赫夫曼树 -n);printf( -Q退出 -n);printf( -n);/初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中void Init()FILE *fp;int i,n,w52; /数组存放字符的权值char character52; /存放n个字符printf(n输入字符个数 n:);scanf(%d,&n); /输入字符集大小printf(输入%d个字符及其对应的权值:n,n);for (i=0;in;i+) char b=getchar(); scanf(%c,

8、&characteri); scanf(%d,&wi); /输入n个字符和对应的权值 HuffmanCoding(HT,character,w,n); /建立赫夫曼树if(fp=fopen(hfmtree.txt,w)=NULL) printf(Open file hfmtree.txt error!n);for (i=1;i=2*n-1;i+) if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1) /将建立的赫夫曼树存入文件hfmtree.txt中 printf(File write error!n);printf(n赫夫曼树建立成功，并已存于文件hfmtree.t

9、xt中n);fclose(fp);/建立赫夫曼树的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,x,y;HuffmanTree p;if(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;ich=*character;p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;ich=0;p-weight=0;p-parent=0;p-lchild=

10、0;p-rchild=0;for(i=n+1;i=m;+i) select(HT,i-1,&x,&y); HTx.parent=i;HTy.parent=i; HTi.lchild=x;HTi.rchild=y; HTi.weight=HTx.weight+HTy.weight;/从HT1到HTj中选择parent为0，weight最小的两个结点，用x和y返回其序号void select(HuffmanTree HT,int j,int *x,int *y)int i;/查找weight最小的结点for (i=1;i=j;i+) if (HTi.parent=0) *x=i;break;for

11、 (;i=j;i+) if (HTi.parent=0)&(HTi.weightHT*x.weight) *x=i; HT*x.parent=1;/查找weight次小的结点for (i=1;i=j;i+) if (HTi.parent=0) *y=i;break;for (;i=j;i+) if (HTi.parent=0)&(i!=*x)&(HTi.weightHT*y.weight) *y=i;/对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中void Coding()FILE *fp,*fw;int i,f,c,start;char *cd;Huffman

12、Code HC;if(n=0) n=Read_tree(HT);/从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数/求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char *)malloc(n*sizeof(char);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=(

13、char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart);free(cd);if(fp=fopen(tobetrans.txt,rb)=NULL) printf(Open file tobetrans.txt error!n);if(fw=fopen(codefile.txt,wb+)=NULL) printf(Open file codefile.txt error!n);char temp;fscanf(fp,%c,&temp); /从文件读入第一个字符while(!feof(fp) for(i=1;i=n;i+) if(HTi.c

14、h=temp) break; /在赫夫曼树中查找字符所在的位置 for(int r=0;HCir!=0;r+) /将字符对应的编码存入文件 fputc(HCir,fw); fscanf(fp,%c,&temp); /从文件读入下一个字符fclose(fw);fclose(fp);printf(n已将文件hfmtree.txt成功编码,并已存入codefile.txt中！nn);/将文件codefile中的代码进行译码，结果存入文件textfile中void Decoding()FILE *fp,*fw;int m,i;char *code,*text,*p; if(n=0) n=Read_tr

15、ee(HT);/从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数if(fp=fopen(codefile.txt,rb)=NULL) printf(Open file codefile.txt error!n); if(fw=fopen(textfile.txt,wb+)=NULL) printf(Open file textfile.txt error!n);code=(char *)malloc(sizeof(char);fscanf(fp,%c,code); /从文件读入一个字符for(i=1;!feof(fp);i+) code=(char *)realloc(code,(i

16、+1)*sizeof(char); /增加空间 fscanf(fp,%c,&codei); /从文件读入下一个字符codei-1=0;/ codefile.txt文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100*sizeof(char);p=text; m=2*n-1;if(*code=0) find(HT,code,text,HTm.lchild,m); /从根节点的左子树去找else find(HT,code,text,HTm.rchild,m); /从根节点的右子树去找 for(i=0;pi!=0;i+) /把译码好的字符存入文件textfil

17、e.txt中 fputc(pi,fw);fclose(fp);fclose(fw);printf(n已将codefile.txt文件成功译码，兵已存入textfile.txt文件！nn);/将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。void Print_code()FILE *fp,*fw;char temp;int i; if(fp=fopen(codefile.txt,rb)=NULL) printf(Open file codefile.txt error!n);if(fw=fopen(codeprint.txt

18、,wb+)=NULL) printf(Open file codeprint.txt error!n);printf(n文件codefi1e显示如下:n);fscanf(fp,%c,&temp); /从文件读入一个字符for (i=1;!feof(fp);i+) printf(%c,temp); if(i%50=0) printf(n); fputc(temp,fw); /将该字符存入文件codeprint.txt中 fscanf(fp,%c,&temp); /从文件读入一个字符printf(nn已将此字符形式的编码写入文件codeprint.txt中！nn);fclose(fp);fclos

19、e(fw);/将已在内存中的哈夫曼树显示在屏幕上，并将此字符形式的哈夫曼树写入文件treeprint中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *fp;if(n=0) n=Read_tree(HT); /从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数Convert_tree(T,0,&m,2*n-1); /将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if(fp=fopen(treeprint.txt,wb+)=NULL) printf(Open file treeprint.txt error!n);

20、printf(n打印已建好的赫夫曼树：n);for(i=1;i=2*n-1;i+) for (j=0;Tij!=0;j+) if(Tij= ) printf( );fputc(Tij,fp); else printf(%d,Tij);fprintf(fp,%dn,Tij); printf(n);fclose(fp);printf(n已将该字符形式的哈夫曼树写入文件treeprint.txt中！nn);/从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数int Read_tree(HuffmanTree &HT)FILE *fp;int i,n;HT=(HuffmanTree)mallo

21、c(sizeof(HTNode); if(fp=fopen(hfmtree.txt,r)=NULL) printf(Open file hfmtree.txt error!n);for (i=1;!feof(fp);i+) HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode); /增加空间 fread(&HTi,sizeof(HTNode),1,fp); /读入一个节点信息fclose(fp);n=(i-1)/2;return n;/译码时根据01字符串寻找相应叶子节点的递归算法void find(HuffmanTree &HT,char *code,

22、char *text,int i,int m)if(*code!=0) /若译码未结束 code+; if(HTi.lchild=0&HTi.rchild=0) /若找到叶子节点 *text=HTi.ch; /将叶子节点的字符存入text中 text+; if(*code=0) find(HT,code,text,HTm.lchild,m); /从根节点的左子树找 else find(HT,code,text,HTm.rchild,m); /从根节点的右子树找 else /如果不是叶子节点 if(*code=0) find(HT,code,text,HTi.lchild,m); /从该节点的左

23、子树去找 else find(HT,code,text,HTi.rchild,m); /从该节点的右子树去找else *text=0; /译码结束/将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来void Convert_tree(unsigned char T100100,int s,int *i,int j)int k,l;l=+(*i);for(k=0;ks;k+) Tlk= ;Tlk=HTj.weight;if(HTj.lchild) Convert_tree(T,s+1,i,HTj.lchild);if(HTj.rchild) Convert_tree(T,s+1,i,HTj.r

24、child); Tl+k=0;四调试步骤 1.赫夫曼树节点的数据类型定义为：typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild; HTNode,*HuffmanTree;2. void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼树的算法，此函数块调用了Select（）函数。void select(HuffmanTree HT,int j,int *x,int *y);从已建好的赫夫曼树中选择parent为0，weight最小的两个结点。3利用已

25、建好的哈夫曼树从文件hfmtree.txt中读入，对文件中的正文进行编码，然后将结果存入文件codefile.txt中。4. coding 编码功能：对输入字符进行编码5. Decoding译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.txt 中。6. Print() 打印功能函数：输出哈夫曼树以及对应的编码。5 运行结果 六分析与思考 我的课程设计题目是赫夫曼编译码器。最初做这个程序的时候，让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料，在写这个程序的时候也参考了网上的设计流程，写完刚运行时出现了很多

26、问题。尤其是编码错误，导致内存无法read，通过同组人员的交流请教，逐渐明白过来，然后经过不知道多少次修改才顺利运行。本次试验也让我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。 通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解决问题的方法，更是解决问题的思想。 数据结构实验报告 实验五 一实验内容：查找表是数据处理的重要操作， 试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树， 并比较两者的平均查找长度。【基本要求】（1） 以链表作为存储结构

27、，实现二叉排序树的建立、查找和删除。（2） 根据给定的数据建立平衡二叉树。（3）比较二叉排序树和平衡二叉树的平均查找长度。 二实验目的熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。三程序清单#include#include#include#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)using namespace std;typedef int Keytype;typedef struct Keytype key; /关键字域ElemType;typedef struct BSTnode Ele

28、mType data; int bf;struct BSTnode *lchild,*rchild;BSTnode,*BSTree;void InitBSTree(BSTree &T)T=NULL;void R_Rotate(BSTree &p)BSTnode *lc; lc=p-lchild; p-lchild=lc-rchild; lc-rchild=p; p=lc;void L_Rotate(BSTree &p)BSTnode *rc; rc=p-rchild; p-rchild=rc-lchild; rc-lchild=p; p=rc;void Leftbalance(BSTree &

29、T)BSTnode *lc,*rd; lc=T-lchild; switch(lc-bf) case +1: T-bf=lc-bf=0; R_Rotate(T); break; case -1: rd=lc-rchild; switch(rd-bf) case 1: T-bf=-1; lc-bf=0; break; case 0: T-bf=lc-bf=0; break; case -1: T-bf=0; lc-bf=1; break; rd-bf=0; L_Rotate(T-lchild); R_Rotate(T); void Rbalance(BSTree &T)BSTnode *lc,*

30、ld; lc=T-rchild; switch(lc-bf) case 1: ld=lc-lchild; switch(ld-bf) case 1: T-bf=0; lc-bf=-1; break; case 0: T-bf=lc-bf=0; break; case -1: T-bf=1; lc-bf=0; break; ld-bf=0; R_Rotate(T-rchild); L_Rotate(T); case -1: T-bf=lc-bf=0; L_Rotate(T); break; int InsertAVL(BSTree &T,ElemType e,bool &taller) if(!

31、T) T=(BSTree)malloc(sizeof(BSTnode); T-data=e; T-lchild=T-rchild=NULL; T-bf=0; taller=true; else if(EQ(e.key,T-data.key) taller=false; cout结点 e.key 不存在。data.key) if(!InsertAVL(T-lchild,e,taller) return 0; if(taller) switch(T-bf) case 1: Leftbalance(T); taller=false; break; case 0: T-bf=+1; taller=tr

32、ue; break; case -1: T-bf=0; taller=false; break; else if(!InsertAVL(T-rchild,e,taller) return 0; if(taller) switch(T-bf) case 1: T-bf=0; taller=false; break; case 0: T-bf=-1; taller=true; break; case -1: Rbalance(T); taller=false; break; return 1;bool SearchBST(BSTree T,ElemType key,BSTree f,BSTree

33、&p) if(!T) p=f; cout结点不存在。data.key) ) p=T; cout查找成功，存在结点; coutdata.keydata.key) return SearchBST(T-lchild,key,T,p); else return SearchBST(T-rchild,key,T,p);void Leftbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-bf=+1) /p结点的左子树高，删除结点后p的bf减1,树变矮 p-bf=0; shorter=1; else if(p-bf=0)/p结点左、右子树等高，删

34、除结点后p的bf减1,树高不变 p-bf=-1; shorter=0; else p1=p-rchild;/p1指向p的右子树 if(p1-bf=0)/p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变 L_Rotate(p); p1-bf=1; p-bf=-1; shorter=0; else if(p1-bf=-1)/p1的右子树高，左旋处理后，树变矮 L_Rotate(p); p1-bf=p-bf=0; shorter=1; else p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchil

35、d; p2-lchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=-1) p-bf=+1; p1-bf=0; else p-bf=0; p1-bf=-1; p2-bf=0; p=p2; shorter=1; void Rbalance_div(BSTree &p,int &shorter) BSTree p1,p2; if(p-bf=-1) p-bf=0; shorter=1; else if(p-bf=0) p-bf=+1; shorter=0; else p1=p-lchild; if(p1-bf=0) R_Rotate(p); p1-b

36、f=-1; p-bf=+1; shorter=0; else if(p1-bf=+1) R_Rotate(p); p1-bf=p-bf=0; shorter=1; else p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=0; p1-bf=0; else if(p2-bf=1) p-bf=-1; p1-bf=0; else p-bf=0; p1-bf=1; p2-bf=0; p=p2; shorter=1; void Delete(BSTree

37、q,BSTree &r,int &shorter) if(r-rchild=NULL) q-data=r-data; q=r; r=r-lchild; free(q); shorter=1; else Delete(q,r-rchild,shorter); if(shorter=1) Rbalance_div(r,shorter); ElemType DeleteAVL(BSTree &p,ElemType key,int &shorter) ElemType k,a,b; a.key=1; b.key=0; BSTree q; if(p=NULL) cout结点不存在。data.key) )

38、/在p的左子树中进行删除 k=DeleteAVL(p-lchild,key,shorter); if(shorter=1) Leftbalance_div(p,shorter); return k; else if(LQ(key.key,p-data.key) )/在p的右子树中进行删除 k=DeleteAVL(p-rchild,key,shorter); if(shorter=1) Rbalance_div(p,shorter); return k; else q=p; if(p-rchild=NULL) /右子树空则只需重接它的左子树 p=p-lchild; free(q); shorte

39、r=1; else if(p-lchild=NULL)/左子树空则只需重接它的右子树 p=p-rchild; free(q); shorter=1; else Delete(q,q-lchild,shorter); if(shorter=1) Leftbalance_div(p,shorter); p=q; return a; void Print_BSTTree(BSTree T,int i) if(T) if(T-rchild) Print_BSTTree(T-rchild,i+1); for(int j=1;j=i;j+) cout ; coutdata.keylchild) Print

40、_BSTTree(T-lchild,i+1); int main() cout班级：中法121 姓名：郝雨微 学号：122887endl; BSTree T; ElemType e; InitBSTree(T); bool tall=false; bool choice=true; char y; while(choice) coute.key; InsertAVL(T,e,tall); Print_BSTTree(T,0); couty; if(y=Y|y=y) choice=true; else choice=false; BSTree f,p; choice=true; while(choice) coute.key; SearchBST( T,e,f,p); couty; if(y=Y|y=y) choice=true; else choice=false; int shorter; choice=true; while(choice) coute.key; DeleteAVL(T,e,shorter); P