数据结构课程实验报告13

1、课 程 实 验 报 告课程名称： 数据结构 专业班级：信安1302 学 号： 姓 名： 指导教师: 报告日期： 2015/5/14 计算机科学与技术学院目 录1 课程实验概述12 实验一 基于顺序结构的线性表实现2.1 问题描述22.2 系统设计22.3 系统实现22.4 效率分析23 实验二 基于链式结构的线性表实现3.1 问题描述33.2 系统设计33.3 系统实现33.4 效率分析34 实验三 基于二叉链表的二叉树实现4.1 问题描述44.2 系统设计44.3 系统实现44.4 效率分析45 实验总结与评价56 源程序附录1 课程实验概述实验（一）基于顺序存储结构，实现线性表的基本的，常

2、见的运算：提示：（1）提供一个实现功能的演示系统；（2）具体物理结构和数据元素类型自行选定；（3）线性表数据可以使用磁盘文件永久保存 实验（二）基于链式存储结构，实现线性表的基本的，常见的运算：提示：（1）提供一个实现功能的演示系统；（2）具体物理结构和数据元素类型自行选定；（3）线性表数据可以使用磁盘文件永久保存 实验（三）基于二叉链表，实现二叉树的基本的、常见的运算：提示：（1）提供一个实现功能的演示系统；（2）具体物理结构和数据元素类型自行选定；（3）可采用递归和非递归算法实现。 2 实验一 基于顺序结构的线性表实现2.1 问题描述基于顺序存储结构，实现线性表的基本的、常见的运算。2.2

3、 系统设计该程序共有12个功能： 数据元素类型定义为：typedef int status;typedef int elemtype;顺序表（顺序结构）的定义为：typedef struct elemtype * elem;int length;int listsize;sqlist;2.3 系统实现2.3.1intialist功能初始化线性表，传入的是头结点地址。申请一个大小为list_int_size、类型为elemtype的线性存储空间，并用头结点中的首结点指针指向该空间首地址。具体实现如下：status intialist(sqlist & l)l.elem = (elemtype *

4、)malloc( list_init_size * sizeof (elemtype); if(!l.elem) exit(overflow);l.length=0; l.listsize=list_init_size;return ok;测试结果：2.3.2destroylist功能销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。具体实现如下：status destroylist(sqlist & l) free(l.elem); l.elem=null; l.length=0; l.listsize=0; return ok;测试结果：2.3.3clearlist功能与des

5、troy类似但是又有不同，clearlist并不销毁物理空间，而是修改逻辑关系值：status clearlist(sqlist &l) l.length=0; return ok;测试结果：2.3.4listempty功能判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需要对头结点进行修改。实现如下：status listempty(sqlist l) if(!l.length) return ok; else return error;测试结果：空表时： 非空表时：2.3.5listlength 功能求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即

6、可：int listlength(sqlist l) return l.length;测试结果：空表时2.3.6getelem功能获取第i号元素，传入的是头结点值、元素编号i、以及出口表结点地址：status getelem(sqlist l,int i,elemtype & e) if(il.length) printf(wrong value of the serial number %d,i); return error; e=l.elemi-1; return ok;测试结果：表中元素分别为：0, 2, 4, 62.3.7locatelem功能获取指定元素编号，传入头结点值、存储了所需

7、元素信息的一个临时表结点值、equal函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编号i。时间复杂度为,o(n)。status locatelem(sqlist l,elemtype e) int j; for(j=1;j1) pre_e=l.elemloc-1; return 1; else printf(the element is the first one in the list); else printf(the element is not exited); return 0;测试结果：表中元素为：1, 2, 3, 42.3.9nextelem功能求指定元素的后一个元素

8、的内容，与priorelem功能类似，不再赘述。status nextelem(sqlist l,elemtype cur,elemtype & next_e) int loc; if(loc=locatelem(l,cur) if(locl.length) next_e=l.elemloc+1; return 1; else printf(the element is the last one in the list); else printf(the element is not exited); return 0;测试结果：表中元素为：1, 2, 3, 4, 52.3.10listins

9、ert功能插入一个数据元素，传入头结点地址、插入位置i、临时表结点值。在调用插入函数前构造一个临时表结点，用于存储数据元素信息。进入插入子函数，插入前先判断插入位置是否合理，再判断是否“满载”。如果满载则重新申请更大的存储空间。接下来正式插入数据元素，“先空位置再插入”。 平均时间复杂度为 ，o(n)。status listinsert(sqlist & l,int i,elemtype e) elemtype *q; elemtype *p; elemtype *newbase; if(il.length+1) return error; if(l.length=l.listsize) ne

10、wbase=(elemtype*)realloc(l.elem,(l.listsize+listincrement)*sizeof(elemtype); if(!newbase)exit(overflow); l.elem=newbase; l.listsize+=listincrement; q=&(l.elemi-1); for(p=&(l.eleml.length-1);p=q;-p)*(p+1)=*p; *q=e; +l.length; return ok;测试结果：插入前： 插入后： 2.3.11listdelete功能删除指定编号的数据元素，传入头结点地址、编号i、表结点类型结构体

11、地址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执行删除操作之后，进行“移位”运算。时间复杂度仍为o(n)。如下：status listdelete(sqlist & l,int i,elemtype & e) elemtype *q; elemtype *p; if(il.length) return error; p=&(l.elemi-1); e=*p; q=l.elem+l.length-1; for(+p;p=q;+p)*(p-1)=*p; -l.length; return ok; 测试结果：删除前：删除后：2.3.12listtrabverse功能顺序遍历顺序

12、表元素，传入头结点值。时间复杂度为o(n)。status listtrabverse(sqlist l) int i; printf(n- all elements -n); for(i=0;il.length;i+) printf(%d ,l.elemi); printf(n- end -n); return l.length;测试结果：2.4 效率分析在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。具有同数量级复杂度的功能在实现方法上一般近似。locatelem、priorelem、nextelem是基于locatelem，平均效率为o(n)；由于在头结点结构体中已经包含

13、了listempty、listlength所需信息，所以效率为o(1)；listinsert、listdelete都要对顺序表进行“移位”运算，平均效率为o(n)。3 实验二 基于链式结构的线性表实现3.1 问题描述基于链式存储结构，实现线性表的基本的、常见的运算。3.2 系统设计该程序共有12个功能： 数据元素类型定义为：typedef int status;typedef int elemtype;线性表（链式结构）的定义为：typedef struct lnode int length;elemtype data;struct lnode *next;lnode,*linklist;3.

14、3 系统实现3.3.1 createlist功能创建一个有n个元素的链表，每次输入新元素后，生成新结点，添加到表尾，设置新表尾。 status createlist(linklist & l,int n) int e,i=1; lnode *p,*tail; l=(linklist)malloc(sizeof(lnode); tail=l; scanf(%d,&e); while(idata=e; tail-next=p; tail=p; scanf(%d,&e); i+; tail-next=null; return ok;测试结果：3.3.2.destroylist功能需要遍历链表，同时释

15、放掉每个元素。 status destroylist(linklist & l) lnode *p,*q; p=l-next; free(l); while(p) q=p-next; free(p); p=q; return ok;测试结果：3.3.3 clearlist功能 由于链表不同于数序表，这里不仅要在逻辑上清空，还要在物理结构上清空，实现上与destroy类似。status clearlist(linklist &l) lnode *p,*q; p=l-next; while(p) q=p-next; free(p); p=q; l-next=null; return ok;测试结果

16、：3.3.4listempty功能 判空操作，l-next不为null即不空。status listempty(linklist l) if(l-next=null) return ok; else return error;测试结果：clearlist前：clearlist后：3.3.5listlength功能求表长，将整个表遍历一遍，每移动一次长度加一，最后返回表长。int listlength(linklist l) lnode *p; p=l; int length=0; while(p) +length; p=p-next; return length;测试结果：3.3.6getel

17、em功能取第i号元素并用一个数据元素类型结构体指针传出其信息。status getelem(linklist l,int i,elemtype & e) int j=0; lnode *p; p=l; while (jnext; e=p-data; return ok;测试结果： 3.3.7locateelem功能基于遍历链表实现定位。status locateelem(linklist l,elemtype e) lnode *p; p=l; int i=0; while(p) if(e=p-data) return i; p=p-next; +i; return 0;测试结果：表中元素为：

18、1,2,3,4,5,6,3.3.8priorelem功能 基于遍历找到指定元素的前一个元素。status priorelem(linklist l,elemtype cur,elemtype & pre_e) lnode *p; p=l; while(p) if(cur=p-next-data) pre_e=p-data; return 1; p=p-next; return 0;测试结果：表中元素为：1,2,3,4,5,63.3.9nextelem功能与priorelem思路同status nextelem(linklist l,elemtype cur,elemtype & next_e)

19、 lnode *p; p=l; while(p) if(cur=p-data) if(p=null) return error; next_e=p-next-data; return 1; p=p-next; return 0;测试结果：表中元素为：1,2,3,4,5,63.3.10listinsert功能插入一个新元素在第i个位置。status listinsert(linklist & l,int i,elemtype e) lnode *p,*s; int j=0; p=l; while(p&jnext; +j; if(!p|ji-1) return error; s=(linklist

20、)malloc(sizeof(lnode); s-data=e; s-next=p-next; p-next=s; return ok;测试结果：原表中元素为：1,2,3,4,5插入后：变成：1,2,100,3,4,53.3.11listdelete功能删除第i号元素。status listdelete(linklist & l,int i,elemtype & e) lnode *p,*q; int j=0; p=l; while(p-next&jnext; +j; if(!(p-next)|ji-1)return error; q=p-next; p-next=q-next; e=q-da

21、ta; free(q); return ok;测试结果：原表中元素为：1,2,100,3,4,5删除后：变成：1,2,3,4,53.3.12listtrabverse功能顺序遍历链表。status listtrabverse(linklist l) lnode *p; p=l-next; while(p) printf(t %d,p-data); p=p-next; return ok;测试结果：表中元素为：1,2,3,4,53.4 效率分析很多功能都基于遍历：destroylist、clearlist、listtraverse、savelist、loadlist，效率为o(n); getel

22、em、locatelem、priorelem、nextelem、listinsert、listdelete，平均效率也为o(n)。4 实验三 基于二叉链表的二叉树实现4.1 问题描述基于二叉链表，实现二叉树的下列运算：1.二叉树生成 creatbitree2.前序遍历 preordertraverse 3.中序遍历 inordertraverse4.后序遍历 postordertraverse5.按层遍历 levelordertraverse6.计算叶子数目 bitreeleaf7.计算二叉树高度 bitreedepth8.保存 save9.读取 open4.2 系统设计使用链式结构，树结点类

23、型为结构体：typedef struct bitnode telemtype elem; struct bitnode *lchild,*rchild;bitnode;其他所用到的相关的定义：typedef struct elemtype char data;telemtype;typedef struct sqstackselemtype *base;selemtype *top;int stacksize;sqstack;typedef struct sqqueueqelemtype *base;int front;int rear;sqqueue;4.3 系统实现4.3.1.二叉树生成

24、creatbitree按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树t。status creatbitree(bitnode * t,char *s,int *num)char ch;printf(nplease input the bitree(preorder): );scanf(%c,&ch);*(s+(*num)+)=ch;if(ch=n) (*t)=null;elseif(ch= )(*t)=null;elseif(!(*t)=(bitnode *)malloc(sizeof(bitnode)printf(节点空间分配失败！n);exit(er

25、ror);(*t)-elem.data=ch;creatbitree(&(*t)-lchild,s,num);creatbitree(&(*t)-rchild,s,num);return 0;测试结果：4.3.2.前序遍历 preordertraverse先输出，再入栈，访问左子树，出栈，访问右子树status preordertraverse(bitnode * t,status(*visit)(telemtype e)sqstack s;initstack(&s);if(!t)printf(this is an ampty bitree!n);elseprintf(nthe preorde

26、r:t);while(t!=null|s.top!=s.base)if(t!=null)printf(%c,t-elem.data);putchar( );push(&s,t);t=t-lchild;else pop(&s,&t);t=t-rchild;/whilereturn 0;4.3.3.中序遍历 inordertraverse先入栈，访问左子树，出栈，输出，访问右子树status inordertraverse(bitnode * t,status(*visit)(telemtype e)sqstack s;initstack(&s);if(!t)printf(this is an a

27、mpty bitree!n);elseprintf(nthe inorder:t);while(t!=null|s.top!=s.base)if(t!=null)push(&s,t);t=t-lchild;elsepop(&s,&t);printf(%c,t-elem.data);putchar( );t=t-rchild;return 0;4.3.4.后序遍历 postordertraverse用两个栈，访问左子树，入栈s1，访问右子树，入栈s2,当栈顶s1=s2时，表明栈顶元素的左右子树都被访问，此时 出栈，输出status postordertraverse(bitnode * t,st

28、atus(*visit)(telemtype e)sqstack s1,s2;initstack(&s1);initstack(&s2);if(!t)printf(this is an ampty bitree!n);elseprintf(nthe postorder:t);while(t!=null| s1.top!=s1.base)if(t!=null)push(&s1,t);t=t-lchild;elseif(s2.top!=s2.base&*(s1.top-1)=*(s2.top-1)pop(&s1,&t);s2.top-;printf(%c,t-elem.data);putchar(

29、 );t=null;elsepop(&s1,&t);push(&s1,t);push(&s2,t);t=t-rchild;/whilereturn 0;4.3.5.按层遍历 levelordertraverse将根结点指针入队，出队，输出，将左右孩子指针入队status levelordertraverse(bitnode * t,status(*visit)(telemtype e)sqqueue q;initqueue(&q);if(!t)printf(this is an ampty bitree!n);return 0;elseprintf(nthe levelorder:t);en(

30、&q,t);while(q.front!=q.rear)de(&q,&t);printf(%c,t-elem.data);putchar( );if(t-lchild)en(&q,t-lchild);if(t-rchild)en(&q,t-rchild);return 0;4.3.6.计算叶子数目 bitreeleaf参照层次遍历，出队，判断左右孩子是否为空，是则输出，计数加1；否则将左右孩子入队。status bitreeleaf(bitnode * t)sqqueue q;int leaf=0;initqueue(&q);if(!t)printf(this is an ampty bitr

31、ee!n);return 0;printf(nthe leaf(leaves) is(are): );if(t!=null) en(&q,t);while(q.front!=q.rear)de(&q,&t);if(t-lchild=null&t-rchild=null)printf(%c,t-elem.data);putchar( );leaf+;elseif(t-lchild)en(&q,t-lchild);if(t-rchild)en(&q,t-rchild);printf(nthe number(s) of leaf(leaves) is %d,leaf);return leaf;4.3

32、.7.计算二叉树高度 bitreedepth递归，树的深度等于左右子树深度的较大值加1status bitreedepth(bitnode * t)int depth,depthleft,depthright;if(!t)depth=0;else depthleft=bitreedepth(t-lchild);depthright=bitreedepth(t-rchild);depth=1+(depthleftdepthright?depthleft:depthright);return depth;/bitreedepthstatus visit(telemtype e)printf(%c,

33、e.data);putchar( );return 0;4.3.8.保存 savestatus save(bitnode *t)file *fin=fopen(c:bitree.txt,w+);sqstack s;initstack(&s);while(t!=null|s.top!=s.base)if(t!=null)fprintf(fin,%c,t-elem.data);push(&s,t);t=t-lchild;else fprintf(fin,%c,bitreesp);pop(&s,&t);t=t-rchild;/whileif(t=null&s.top=s.base)fprintf(f

34、in,%c,bitreesp);fclose(fin);printf(n已保存!n);return 0;4.3.9.读取 openstatus open(bitnode *t)file *fout;char smax;int i=0;fout=fopen(c:bitree.txt,r+);if(!fout)printf(文件不存在!n);return 0;fscanf(fout,%s,s);writebitree(t,s,&i);printf(n已打开!n);return 0;总测试结果：4.4 效率分析建立二叉树,由于是基于递归先序遍历建立二叉树，所以效率为o(n)。traverse对于递归

35、实现的三种遍历、非递归实现的先序和中序遍历以及队列法实现的层遍历，由于每个元素被访问到且仅访问一次，且不要进行其他额外大型运算，所以效率为 o(n)。对于非递归堆栈的后序遍历，每个元素被访问到的次数为2，而且还要把所有左子树的指向关系保存，假设结点数为n，则左子树个数平均为n(n-1)/2n，综上，平均时间复杂度为o(5n/2)=o(n)。求叶子数基于遍历实现，效率也为o(n)。求深度也是基于遍历，所以也是o(n)。5 实验总结与评价在开始上机的过程中就遇到过很多的困难，也觉得这几个实验是很难完成的几座大山，但是随着时间的推移，慢慢的从中学到了很多的知识。从开始的寸步难行，到慢慢的可以写出几个

36、子函数，到发现错误自己能通过与同学交流或自己解决，再到现在基本完成，这对我来说是很大的进步，也是对我一种很好的锻炼另外在整个实验中，最潜移默化的影响就是对c有了更熟练的掌握，尤其是指针。其次，就是对数据结构有了更系统的理解，对逻辑结构和物理结构的关系更有体会。这对我今后的生活学习很有帮助。在实验过程中，许多的错误都是由于自己的不细心所导致，经常是*，：，-等的小问题，但是在不断地编写中慢慢熟练，这些错误也越来越少。第一次上机实验，由于准备不是很充分写的不是很快，第二次上机随着知识体系的增加，难度的加大进度也不是很快，大部分工作还是在课下完成的。虽然过程很坎坷，但是最后还是完成了这次任务，前两个

37、程序功能基本都能实现，第三个程序稍有不足功能比较少，与其他同学相比还有差距，但我相信通过今后的学习，我会慢慢提高自己，一点一点缩小这种差距，使自己做的更好，更全面。源程序附录：实验一：/* linear table on sequence structure */#include #include #include /*-page 10 on textbook -*/#define true 1#define false 0#define ok 1#define error 0#define infeastable -1#define overflow -2typedef int status

38、;typedef int elemtype; /数据元素类型定义/*-page 22 on textbook -*/#define list_init_size 100#define listincrement 10typedef struct /顺序表（顺序结构）的定义elemtype * elem;int length;int listsize;sqlist;/*-page 19 on textbook -*/status intialist(sqlist & l);status destroylist(sqlist & l);status clearlist(sqlist &l);sta

39、tus listempty(sqlist l);int listlength(sqlist l);status getelem(sqlist l,int i,elemtype & e);status locatelem(sqlist l,elemtype e); /简化过status priorelem(sqlist l,elemtype cur,elemtype & pre_e);status nextelem(sqlist l,elemtype cur,elemtype & next_e);status listinsert(sqlist & l,int i,elemtype e);sta

40、tus listdelete(sqlist & l,int i,elemtype & e);status listtrabverse(sqlist l); /简化过/*-*/main(void) sqlist l; int op=1; while(op)system(cls); printf(nn);printf( menu for linear table on sequence structure n);printf(-n);printf( 1. intialist 7. locateelemn);printf( 2. destroylist 8. priorelemn);printf(

41、3. clearlist 9. nextelem n);printf( 4. listempty 10. listinsertn);printf( 5. listlength 11. listdeleten);printf( 6. getelem 12. listtrabversen);printf( 0. exitn);printf(-n); printf( 请选择你的操作012:);scanf(%d,&op); switch(op) case 1: /printf(n-intialist功能待实现！n); if(intialist(l) printf(线性表创建成功！n); else pr

42、intf(线性表创建失败！n); getchar();getchar(); break; case 2: if(destroylist(l) printf(n list l is destroyed!); else printf(n error!); getchar();getchar(); break; case 3: if(clearlist(l) printf(n list l is cleared!); else printf(n error!); getchar();getchar(); break; case 4: if(l.elem=null) printf(n error! ); else if(listempt