华中科技大学13级数据结构课程实验报告.doc

《华中科技大学13级数据结构课程实验报告.doc》由会员分享，可在线阅读，更多相关《华中科技大学13级数据结构课程实验报告.doc（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课 程 实 验 报 告课程名称： 数 据 结 构 专业班级：计算机科学与技术1305班学 号： U201314907 姓 名： 韩非 指导教师： 许贵平 报告日期： 2015/5/31 计算机科学与技术学院目 录1课程实验概述12实验一 基于顺序结构的线性表实现12.1实验内容与要求12.2程序概要设计12.3数据结构与算法设计22.4输入输出设计32.5源程序及注释42.6程序测试与结果182.7复杂性分析213实验二 基于链式结构的线性表实现223.2 程序概要设计223.2 程序概要设计223.3 数据结构与算法设计223.4 输入输出设计243.5 源程序及注释243.6 程序测试与结

2、果393.7 复杂性分析424 实验三 基于二叉链表的二叉树实现434.1 实验内容与要求434.2 程序概要设计434.3 数据结构与算法设计444.4 输入输出设计464.5 源程序及注释464.6 程序测试与结果574.7 复杂性分析605实验总结与评价606 参考书目611课程实验概述本次课程实验旨在加强学生课堂理论学习之后增强上机能力，熟练掌握并应用数据结构中的两种逻辑结构的典型代表线性表和树。线性表的顺序存储具有随机存取的功能，而链式存储能有效的利用动态存储空间，学会合理的选择这两种存储方式，看似简单，但在实际应用具有很大的用处。而树（二叉树）是非线性逻辑结构的代表，树模型的建立可

3、以说完全建立在递归思想之上，树的几乎所有操作都涉及到递归调用，当然我们也可以用栈来实现非递归调用，但是其思想也是相近的。因此树的实验旨在帮助我们递归思想的建立和成熟。2实验一 基于顺序结构的线性表实现2.1实验内容与要求实验内容：基于顺序存储结构，实现线性表ADT，具有10种基本运算。具体要求：1.提供一个实现功能的演示系统。 2.具体物理结构和数据元素类型自定。 3.线性表数据可以使用磁盘文件永久保存。2.2程序概要设计 1.明确基本功能程序需要实现的12个基本功能分别是：IntiaList（初始化），DestroyList（摧毁线性表），ClearList（清空线性表），ListEmpty

4、（判断表空），ListLength（求表长），GetElem（取表中元素），LocatElem（获得元素地址），PriorElem（取前继），NextElem（取后继）。ListInsert（插入）， ListDelete（删除），ListTrabverse（遍历显示），此外还有辅助功能：Load（载入），Save（保存）2. 确定各功能实现的函数参数status IntiaList(SqList * L);status DestroyList(SqList * L);status ClearList(SqList L);status ListEmpty(SqList L);int ListL

5、ength(SqList L);status GetElem(SqList L,int i,Elemtype *e);int 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, Elemtype e,int i);status ListDelete(SqList * L,Elemtype * e,i

6、nt i);status ListTrabverse(SqList L,void (* visit)(Elemtype e);void Save(SqList L);status Load(SqList*L);2.3数据结构与算法设计为了满足概述中的功能，结合线性表结构，给出以下结构的定义：typedef int status;typedef structint item1;Elemtype;typedef structElemtype * elem;int length;int listsize;SqList,*L;算法设计： 1.IntiaList：初始化线性表，传入的是头结点地址。申请一

7、个大小为LIST_INT_SIZE、类型为Elemtype的线性存储空间，并用头结点中的首结点指针指向该空间首地址。2.DestroyList：销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。3.ClearList：与Destroy类似但是又有不同，ClearList并不销毁物理空间，而是修改逻辑关系值。4.ListEmpty：判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需要对头结点进行修改。若长度为0，表空，否则不空。5.ListLength：求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可。6.GetElem：获取第i号元素，传

8、入的是头结点值、元素编号i、以及出口表结点地址。7.LocatElem：取指定元素编号，传入头结点值、存储了所需元素信息的一个临时表结点值、equal函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编号i。8.PriorElem：求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用LocatElem确定指定元素的位置，如果不是首结点则可直接取到PriorElem的地址。9.NextElem：与PriorElem功能类似，不再赘述。10.ListInset：插入一个数据元素，传入头结点地址、插入位置i、临时表结点值。

9、在调用插入函数前构造一个临时表结点，用于存储数据元素信息。进入插入子函数，插入前先判断插入位置是否合理，再判断是否“满载”。如果满载则重新申请更大的存储空间。接下来正式插入数据元素，“先空位置再插入”。11. ListDelete: 删除一个数据元素，传入头结点地址、删除位置i。删除前先判断位置是否合理，先删除元素，然后将所有删除元素之后的元素前移一个位置。12. ListTrabverse: 传入头结点，循环访问各个元素，直至到表尾停止。2.4输入输出设计1. 输入： 在输入方面，我采用了用户自定义输入的方式，既可以采用用户自行输入，又可以载入之前保存的数据。在每次操作之后，会提示是否保存刚

10、才的数据，以便下次再次使用，以下是用户自行输入的功能实现： void creat(SqList *L) int a=0; printf(Input the number of your datas?n); scanf(%d,&a); L-elem=(Elemtype*)malloc(a*sizeof(Elemtype); L-length=a; int i; printf(Please input your datan); for (i=1;ielemi.item1); L-listsize=LIST_INIT_SIZE; printf(You have to save your data);

11、 getchar(); Save(*L);2. 输出： 采用遍历输出，即功能10的输出。2.5源程序及注释/* Linear Table On Sequence Structure */#include #include #include #include #define LIST_INIT_SIZE 10#define OK 1#define FALSE 0#define TRUE 1#define ERROR -1#define OVERFLOW -2#define LISTINCREMENT 1/*-*/typedef int status;typedef structint item1

12、;Elemtype;typedef structElemtype * elem;int length;int listsize;SqList,*L;int changed=0;/*-*/status IntiaList(SqList * L);status DestroyList(SqList * L);status ClearList(SqList L);status ListEmpty(SqList L);int ListLength(SqList L);status GetElem(SqList L,int i,Elemtype *e);int LocatElem(SqList L,El

13、emtype *e);status PriorElem(SqList *L,Elemtype cur,Elemtype * pre_e);status NextElem(SqList L,Elemtype cur,Elemtype * next_e);status ListInsert(SqList *L, Elemtype e,int i);status ListDelete(SqList * L,Elemtype * e,int i);status ListTrabverse(SqList L,void (* visit)(Elemtype e);/*-*/status compare(E

14、lemtype e1,Elemtype e2);status equal(Elemtype x, Elemtype y);void display(Elemtype e);void Save(SqList L);status Load(SqList*L);void creat(SqList *L);/*-*/void menu(void);/*-*/char file020;int main(void)SqList L;L.listsize=LIST_INIT_SIZE;int op=0;char req;do system(cls); menu(); printf(Do you want t

15、o input new liear table?Y/N); req=getchar();getchar(); if (req=Y |req=y) creat(&L); else printf(Do you want to load saved data?Y/N); req=getchar(); if (req=Y |req=y) while (!Load(&L) L.elem=(Elemtype*)malloc(L.listsize+)*sizeof(Elemtype); else printf(You still use the data use before!n); getchar();

16、getchar(); system(cls); menu(); printf( Then please input your option0-12:); scanf(%d,&op); switch(op) case 0: break; case 1: printf(n here is IntiaList(),which being realizedn);getchar();getchar(); if (IntiaList(&L) printf(Successfully realized!n);getchar();getchar(); /printf(Dou you want to save?Y

17、/N) else printf(Not realised!n); getchar();getchar(); break; case 2: printf(n here is DestroyList(),which being realizedn); getchar();getchar(); if (DestroyList(&L) printf(Successfully realized!n); getchar();getchar(); else printf(Not realised!n); getchar();getchar(); break; case 3: printf(n here is

18、 ClearList(),which being realizedn); getchar();getchar(); if (ClearList(L) printf(Successfully realized!n); getchar();getchar(); else printf(Not realised!n); getchar();getchar(); break; case 4: printf(n here is ListEmpty(),which being realizedn); getchar();getchar(); if (ListEmpty(L) printf(It is an

19、 empty listn); getchar();getchar(); else printf(It is not an empty listn); getchar();getchar(); break; case 5: printf(n here is ListLength() ,which being realizedn); if (&L!=NULL) printf(%d,L.elem1.item1); printf(Successfully realized!The length of L is %dn,ListLength(L); getchar();getchar(); else p

20、rintf(Not realised!n); getchar();getchar(); break; case 6: printf(n here is GetElem(),which being realizedn);getchar();getchar(); int i; Elemtype e; printf(which elem do you want to pick?i=?); scanf(%d,&i); if (GetElem(L,i,&e) printf(Successfully realized!n); printf(And the %dth elem data is %d,i,e.

21、item1); getchar();getchar(); else printf(Not realised!n); getchar();getchar(); break; case 7: printf(n here is LocatElem(),which being realizedn); getchar();getchar(); int t,i,a; Elemtype e; printf(What do you want to locate?item=); scanf(%d,&t); for (i=1;i=L.length;i+) if (L.elemi.item1=t) break; i

22、f (i=L.length+1) printf(There is no such item in this list!n); e=L.elemi; if (a=LocatElem(L,&e) printf(Successfully realized!n); printf(e is in the %dth locationn,a); getchar();getchar(); else printf(Not realised!n); getchar();getchar(); break; case 8: printf(n here is PriorElem(),which being realiz

23、edn);getchar();getchar();Elemtype e,cur;int i;printf(To find the prio of who?i=);scanf(%d,&i);cur=L.elemi; if (PriorElem(&L,cur,&e) printf(Successfully realized!n); printf(And the prio of elem%d is %dn,i,e.item1); getchar();getchar(); else printf(Not realised!n); getchar();getchar(); break; case 9:

24、printf(n here is NextElem(),which being realizedn);getchar();getchar();Elemtype e,cur;int i;printf(To find the next of who?i=);scanf(%d,&i);cur=L.elemi; if (NextElem(L,cur,&e) printf(Successfully realized!n); printf(And the nextelem of elem%d is %dn,i,e.item1); getchar();getchar(); else printf(Not r

25、ealised!n); getchar();getchar(); break; case 10: printf(n here is ListInsert(),which being realizedn);getchar();getchar(); int i,j; Elemtype e; printf(choose where to insert?i=); scanf(%d,&i); printf(nInsert new data=); scanf(%d,&(e.item1); if (ListInsert(&L,e,i) printf(Successfully realized!n); pri

26、ntf(the list data is now:n); for (j=1;j=L.length;j+) printf(%d ,L.elemj.item1); getchar();getchar(); else printf(Not realised!n); getchar();getchar(); break; case 11: printf(n here is ListDelete(),which being realizedn);getchar();getchar(); int i,j; Elemtype *e; printf(choose where to delete?i=); sc

27、anf(%d,&i); if (ListDelete(&L,e,i) printf(Successfully realized!n); printf(The deleted data is %dn,(*e).item1);getchar();getchar(); printf(the list data is now:n); for (j=1;jelem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype); if (!L) exit(OVERFLOW); L-length=0; L-listsize=LIST_INIT_SIZE; return

28、OK;status DestroyList(SqList * L) free(L); L=NULL; char req; printf(Are you sure to destroy the file?Y/N); req=getchar(); if (req=y|req=Y) remove(file0); printf(The file has been destroyed!n); return OK;status ClearList(SqList L) L.length=0; return OK;status ListEmpty(SqList L) if (L.length=0) retur

29、n TRUE; else return FALSE;int ListLength(SqList L) return L.length;status GetElem(SqList L,int i, Elemtype * e) if (!(L.length=0|iL.length) *e=L.elemi; return OK; else return ERROR;int LocatElem(SqList L,Elemtype *e) int i; for(i=1;ielem) return ERROR; else for(i=1;ilength;i+) if (compare(L-elemi,cu

30、r) break; if(i=1) return FALSE; else *pre_e=(L-elemi-1); return OK; status NextElem(SqList L,Elemtype cur,Elemtype * next_e) int i; if(!L.elem) return ERROR; else for(i=1;ilength=0) L-length+; L-elem1=e; return OK; if(iL-length) return FALSE; if(L-length=L-listsize) newbase=(Elemtype*)realloc(L-elem

31、,(L-listsize+LISTINCREMENT)*sizeof(Elemtype); if(!newbase) return(OVERFLOW); L-elem=newbase; L-listsize+=LISTINCREMENT; q=&(L-elemi); for(p=&(L-elemL-length);p=q;p-) *(p+1)= *p; *q=e; +L-length; return OK;status ListDelete(SqList * L,Elemtype * e, int i) Elemtype *q,*p; if(!L-elem) return ERROR; if(

32、iL-length) return FALSE; q=&(L-elemi); for(p=&(L-elemL-length-1);p=q;p-) *p= *(p+1); (*e)=L-elemi; -L-length; return OK;status ListTrabverse(SqList L, void (* visit)(Elemtype e)int i;if(!L.length) return(0);printf(n-all elements of liear table-n);for(i=1;i=L.length;i+) visit(L.elemi);return(1);status compare(Elemtype e1 ,Elemtype e2 ) if (