数据结构动态查找表实验报告

1、成都信息工程学院计算机系课程实验报告实验课程：经典算法导论实验项目:动态查找表指导教师：李莉丽学生姓名：周恒超学生学号：2010051148班 级：10级计算机应用一班实验地点：5409教室实验时间：2011年12月13日实验成绩：评阅老师：一【上机实验目的】1、深入理解数据结构的算法思想，将算法理论与实际应用相结合，培养学生的编程能力与 编程兴趣，让学生清楚从项目分析、编码、调试、程序维护的整个程序开发流程。2、使学生清楚解决一个编程问题的基本流程，即首先确定逻辑结构，然后在逻辑结构的基 础上确定相应的存储结构，最后在设计一套合理而简便实用的算法，整个过程都是在用 到数据结构的事项解决问题，

2、是学生能够对线性表、二叉树、图的基本操作较为熟悉， 并轻松控制。3、让学生明白在编程调试的过程中学习程序设计的思想、分析方法，培养并提高编程能力。二【实验环境】PC机每人1台三【上机实验内容】.实现所有的动态查找表。该部分算法有一定的难度，尤其二叉排序树与平衡二叉树，涉及树的插入与删除等复杂操 作。实现不易，尽管书中给出的代码较为详细，主要是能较好的掌握二叉树的插入、删除、 与遍历，并能很好说明平衡二叉树的动态查找效率明显高于二叉排序树。【上机调试程序流程图】您输入N退出五【上机调试中出现的错误信息、错误原因及解决办法】1、传参数时出现的问题、传递过去数值的话不能改变数据值，必须传递地址才行：

3、2、空指针异常，老问题了，指针在使用之前必须要初始化分配空间才能够使用：3、调试过程中输入数据时出现的低级错误，忘加地址符，导致异常；4、对文件的操作出现了问题，写入的数据，读出来不正确或是读不出来，解决方法是以相 同的格式和方法读写文件，中途加些pnntf语句检查读出来是否正确，并多次采用单步 调试法，一步一步的调试即可。六【上机调试后的源程序及还存在的问题】文件 dtczb.li#iiiclude#iiiclude#iiiclude#define EQ(a,b) (a)=(b)#define LT(a.b) (a)(b)define TRUE 1#define FALSE 0define

4、OVERFLOW .1#define LH +1#define EH 0#define RH -1typedef int Status;typedef int KeyType;typedef char Name;typedef char Sex;typedef int Age;结点数据域的定义typedef stmctKeyType key;Name name20;Sex sex20;Age age;JElemType;动态表的数据结构typedef stmct DSTableElemType data;Status bf;stmct DSTable *lcluld.*rchild; *BiT

5、ree,BiTNode;/构造一个只含根节点的动态表Status IiiitDSTable(BiTree *DT);动态表中数据元素序列的输入void InputData(ElemType array。,int n);销毁一个动态表Status DestioyDSTable(BiTree *DT);查找表中是否有关键字等于key的记录Status SearcliDSTable(BiTree DT.KeyType key.BiTree f,BiTiee *p);动态表的插入函数Status IiiseitDSTable(BiTree *DT,ElemType e);动态表的删除函数Status

6、DeleteDSTable(BiTree *DT,KeyType key);Status Delete(BiTree *p);动态表中节点的右旋void R_Rotate(BiTree *p);动态表中节点的左旋void L_Rotate(BiTiee *p);二叉平衡树的插入Status IiisenAVL(BiTiee *DLElemType eStatus *talleij;/左平衡函数void LeftBalaiice(BiTree *DT);/右平衡函数void RightBalance(BiTree *DT);void Piiiit(BiTree DT);小界面的函数void me

7、nu();/dtczb.c 文件#include dtczb.h/构造一个只含根节点的动态表Status IiiitDSTable(BiTree *DT)*DT=NULL;retuin(TRUE);动态表中数据元素序列的输入void InputData(ElemType array。,int n)int i;fbi(i=O;idata.key)f*p=DT;retuni(TRUE);else if LT(key,DT-data.key)fretuni(SeaicliDSTable(DT-lchild,keyDT.p);else fretuni(SeaicliDSTable(DT-rchild,

8、key.DT.p);动态表的插入函数Status IiiseitDSTable(BiTree *DT,ElemType e)BiTree s;BiTree p;p=(BiTree)inalloc(sizeof(BiTNode);if(!SearcliDSTable(*DT,e.key,NULL,&p) fs=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lcluld=NULL;s-rchild=NULL;谊!P)(*DT=s;else if LT(e.key;p-data.key)p-lcluld=s;)else(p-rcluld=s;)retuni(TR

9、UE);elseretuni(FALSE);动态表的删除函数Status DeleteDSTable(BiTree *DT,KeyType key)if(!(*DT)/Ipnntf(”你要删除的学生不存在!n”)； retuni(FALSE);elseif(EQ(key,(*DT)-data.key)(return(Delete (DT);)else if (LT(key,(*DT)-data.key)(return(DeleteDSTable(&(*DT)-lchild),key)；)else(retum(DeleteDSTable(&(*DT)-rchild),key);)Status D

10、elete(BiTree *p)BiTree q,s;if(!(*p)-rchild)*p=(*p)-lchild;fiee(q);*p=(*p)-r child;fiee(q);elseq=*p;s=(*p)-lchild;while(s-rchild)q=s；s=s-ichild;)(*p)-data=s-data;】f(q!=*p)q-rcluld=s-lcluld;)elseq-lcluld=s-rchild;free(s);)letum(TRUE);动态表结点的右旋函数void R_Rotate(BiTree *p)BiTree 1c;lc=(*p)-lcluld;(*p)-lcli

11、ild=lc-rchild;lc-rcliild=*p;*p=lc;动态表中节点的左旋void L_Rotate(BiTree *p)BiTree rc;rc=(*p)-rchild;(*p)-rcluld=rc-lchild;rc-lcliild=*p;*p=ic;二叉平衡树的插入Status IiisenAVL(BiTree *DLElemType e.Status *talleijif(!(*DT)JI*DT=(BiTree)malloc(sizeof(BiTNode);(*DT)-data=e;(*DT)-lcluld=(*DT)-rchild=NULL;(*DT).b 仁 EH;*t

12、aller=TRUE;elseif(EQ(e.key,(*DT)-data.key)*tallei-=FALSE;return(O);)if(LT(e.key,(*DT)-data.key)if(!InsertAVL(&(*DT)-lchild),e,taller) return(O);if(*taller)switch(*DT)-bf)(case LH:LeftBalance(DT);*tallei-=FALSE;break:case EH:(*DT)-bf=LH;*tallei-=FALSE;break:case RH:(*DT)-bf=EH:*tallei-=FALSE;break:el

13、seif(!InsertAVL(&(*DT)-rcliild),e,taller) return(O);if(*taller)(switch(*DT)-bf)(case LH:(*DT)-bf=EH: *tallei-=FALSE; break;case EH:(*DT)-bf=RH;*tallei-=FALSE; break;case RH:RightBalance(DT); *tallei-=FALSE; break;)retuin(l);左平衡函数void LeftBalaiice(BiTree *DT)BiTree Icjd;lc=(*DT)lchild;switch(lc-bf)ca

14、se LH:(*DT).bfHc.b 仁 EH;R_Rotate(DT); break;case RH:rd=lc-rchild;switch(rd-bf)(case LH:(*DT).b 仁 RH; lc-bf=EH;break:case EH:(*DT)-bMc-bfEH; break:case RH:(*DT).b&EH;lc-bf=LH;break:)rd-bMH;L.Rotate(&(*DT)-lchild);R_Rotate(DT);右平衡函数void RightBalance(BiTree *DT)BiTree rcjd;rc=(*DT)-rchild;switch(rc-bf)

15、case RH:rc.b&EH;(*DT).b 仁 EH;L_Rotate(DT);case LH:ld=rc-lchild;switch(ld-bf)(case LH:(*DT).b&EH;ldb 仁 RH;break:case EH:(*DT).b&EH;ld.b 仁 EH;break:case RH:(*DT)-bfRH: ld.b&EH;break:中序遍历，打印出二叉树中的结点数据值 void Priiit(BiTree DT)】f(DT)Print(DT-lcliild);printf(”d %s %s %dn,DT-data.keyDT-data.iiame.DT-data.se

16、x.DT-data.age);Print(DT-ichild);/小界面的函数void menu()pnntfC* 欢迎进入二叉排序树系统 *nn);、文件信息的读取 * *n”)；pnntf(”&l、文件 A的动态查找表va、平衡,B、排序,C、删 除&O；prmtf(”*2、文件B的动态查找表*蛆)；、文件C的动态查找表va、平衡,B、排序,C、删除#舟1T);pnntf(,，AAAAAAAAAA4、文件的生 成%1)；pnntf(”5、退出系统 iT);/zhuhanshu.c 文件/主函数的实现#include dtczb.h”#iiicludeLARGE_INTEGER stait;

17、LARGE.INTEGER end ;LARGE_INTEGER fiequency;hit mam(void)ElemType block 120,group 120;int ii.i.j,k,ni;mt tall;BiTree T3;int number;char filename320.gilename320;char decided20,c;FILEmenuQ;wlule(l)pnntf(”n请输入数字选择你要进行的操作:”)； scanf(”d.&k); getcharQ;switch(k)(case 0:(fi-fbpenCfhameVrb);邮=NULL) (puts(”文件尚未

18、写入，请写入文件!) exit(0);fbr(i=0;i3;i+)(fread(gilenamei,sizeof(gileiiaiiiei), 1 ,fr);fclose(fi);pnntf(”文件读取成功!n”)； break;case 1:(InitDSTable(&TO);pimtf(ii欢迎进入文件A的动态查找表n”)； fq=fbpen(gilename 0, ”rb ”);if(fq=NULL) (pnntf(f 打开文件失败，程序自动退出！ 3); exit(0);fread(&m,sizeof(mt), 1 ,fq);fbi(i=0;im;i-H-) ( fiead(&grou

19、pi.sizeof(ElemTy7pe), 1 ,fq);fclose(fq);piintR”请输入 A or B or C 选择:”)； scanf(%c”,&c); getchaiQ;switch(c) (case A:if (!QueiyPeiibrmanceFiequency(&fiequency) return -1;QueiyPerfbrnianceCounter(&stait); 开始计时IiisertDSTable(& T 0 .group i);QueiyPerfbrnianceCounter(&end); 结束计时printf(Hn 此次查找耗时:%lf (us)微秒,(d

20、ouble)(end.QuadPart start. QuadPart) / (double)fiequency. QuadPart);pnntffNn学生的学号姓名性别年龄为:n”)；Print(T0);break;case B:if (!Quei-yPeiidrmanceFrequency(&fiequency)return -1;QueiyPerfbrnianceCounter(&stait); 开始计时IiisertAVL(&T0,groupi.&tall);QueiyPerfbrnianceCounter(&end); 结束计时printf(Hn 此次查找耗时:%lf (us)微秒,

21、(double)(end.QuadPart start. QuadPart) / (double)fiequency. QuadPart);pnntffNn学生的学号姓名性别年龄为:n”)；Print(T0);break;case C:IiisertDSTable(& T 0 .group i);pnntfC*n请输入你要删除的学生学号scanf(%d”,&mimber);if(DeleteDSTable(&TO,number)Pnnt(T0);pnntf(”n 删除成功iT);break;)break;case 2:(InitDSTable(&Tl);pimtf(ii欢迎进入文件B的动态查找

22、表n”)；fq=fbpen(gilename 1 ,rb);if(!fq)(pnntfCXn打开文件失败，程序自动退出!n ”)；exit(O);fiead(&m,sizeof(int)? 1 .fq);fdr(i=0;im;i+)(fiead(&groupi,sizeof(gioupi). 1 .fq);fclose(fq);pnntfp请输入 A or B or C 选择:”)； scanf(”c”,&c); getchaiQ;switch(c)(case A:if (!Quei-yPeiidrmanceFiequency(&fiequency)return -1;QxieiyPerfbr

23、nianceCounter(&stait); 开始计时IiisertDSTable(& Tl,gioup i);QxieiyPerfbrnianceCounter(&end); 结束计时printf(Mn 此次查找耗时：%lf (us)微秒,(double)(end.QuadPait - start. QuadPart) / (double)fiequency. QuadPart);pnntffXn学生的学号姓名性别年龄为:n”)；Print(Tl);break;case B:if (!Quei-yPeiidrmanceFrequency(&fiequency)return -1;QueiyP

24、erfbrnianceCounter(&start); 开始计时fbi(i=O;im;i-H-)IiisertAVL(&Tl , group i ,&tall);QueiyPerfbrnianceCounter(&end); 结束计时printf(n 此次查找耗时:%lf (us)微秒,(double)(end.QuadPart start. QuadPart) / (double)fiequency. QuadPart);pnntffNn学生的学号姓名性别年龄为:n”)； Prnit(Tl);break;case C:IiisertDSTable(& T 0 .group i);pnntf(

25、”请输入你要删除的学生学号:”)；scanfj”d”,&mmiber);if(DeleteD STable(&Tl ,numbei) Prnit(Tl);break;)break;case 3:(InitDSTable(&T2);priiitf(H%s,gilename2);pimtf(ii欢迎进入文件C的动态查找表n”)； fq=fbpen(gilename 2 , rb ”);if(!fq)(pnntfCn打开文件失败，程序自动退出！ 3);exit(0);fread(&m,sizeof(int), 1 ,fq);fbr(i=O;im;i-H-)fiead(&groupi,sizeof(g

26、ioupi). 1 .fq);fclose(fq);pnntR”请输入 A or B or C 选择:”)； scanf(”c”,&c); getcharQ;switch(c)(case A:if (!Quei-yPeiidrmanceFrequency(&fiequency)return -1;QueiyPerfbrnianceCounter(&start); 开始计时fbi(i=O;im;i-H-)IiisertDSTable(&T2,gioupi);QiieiyPerfbrnianceCounter(&end); 结束计时printf(Mn 此次查找耗时：%lf (us)微秒(doubl

27、e)(end.QuadPart - start. QuadPart) / (double)fiequency. QuadPart);pnntffNn学生的学号姓名性别年龄为:n”)；Print(T2);break;case B:if (!Quei-yPeiidrmanceFiequency(&fiequency)return -1;QueiyPerfbrnianceCounter(&start); 开始计时fbi(i=O;im;i-H-)IiisertAVL(&T2,groupi.&tall);QiieiyPerfbrnianceCounter(&end); 结束计时printf(Mn 此次查

28、找耗时：%lf (us)微秒,(double)(end.QuadPait - start. QuadPart) / (double)fiequency. QuadPart);pnntffNn学生的学号姓名性别年龄为:n”)； Print(T2);break:case C:IiisertDSTable(&T0.gioupi);pnntf(”请输入你要删除的学生学*:”)；scanf(%d”,&miniber);if(DeleteDSTable(&T2,number) Print(T2);break:i)break;case 4:(fi=fopen(Hfhame,nwbM);for(j=0j3j+

29、)(pnntf(”请输入第%d个动态查找表的表长为+1); scanf(”d”,&n);InputData(blockai);pnntf(”请输入文件c的文件名:”,A+j);hvrite(filenamelj5sizeof(filenamej), 1 ,fi);fp=fbpen(filenamej/wbn);if(fp=NULL)pnntf(”打开文件失败,程序自动退出！ ”)； exit(O);fwrite(&n,sizeoRint), 1 ,功)；fbi(i=O;in;i+)fvvrite(&blocki,sizeof(blocki), 1 ,fp);fclose(fp);ifclose(fi);break;case 5:print町欢迎使用，再见!) exit(O);)prmtf(nii 是否继续:n);scaiif(M%sdecided);if(strcmp(decided；rNH)=O)(pnntf(”欢迎使用，再见!n”)； exit(O);else(contmue;)retuin(O);有些隐形的漏洞还需好好维护修改。七【上机实验中的其他它问题及心得】这是本学期学完数据结构后的一次相对长一些的程序，我之所以选择这道题目是因为我感觉我二叉树这部分掌握得不太好，想以此 来练习并好好 学习一下 二叉树