华南农业大学数据结构上机实验指导书及答案(137页).doc

《华南农业大学数据结构上机实验指导书及答案(137页).doc》由会员分享，可在线阅读，更多相关《华南农业大学数据结构上机实验指导书及答案(137页).doc（137页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-华南农业大学数据结构上机实验指导书及答案-第 134 页目 录实验一 线性表2(一) 实验目的2(二) 实验内容2(三) 实验报告10实验二 堆栈11(一) 实验目的11(二) 实验内容11(三) 实验报告18实验三 队列19(一) 实验目的19(二) 实验内容19(三) 实验报告22实验四 模式匹配23(一) 实验目的23(二) 实验内容23(三) 实验报告26实验五 二叉树27(一) 实验目的27(二) 实验内容27(三) 实验报告34实验六 查找35(一) 实验目的35(二) 实验内容35(三) 实验报告39实验七 内部排序40(一) 实验目的40(二) 实验内容40(三) 实验报告4

2、1实验八 图和图的遍历42(一) 实验目的42(二) 实验内容42(三) 实验报告48数据结构课程设计（2007级用，仅做参考）49(一) 数据结构课程设计安排49(二) 图算法实验题目49(三) 团队题目（各种排序算法效率分析）49数据结构模拟试卷一53数据结构模拟试卷二56附录1：实验报告及习题59实验名称：线性表（一）59实验名称：堆栈（二）61实验名称：队列（三）63实验名称：模式匹配（四）66实验名称：二叉树（五）68实验名称：查找（六）70实验名称：内部排序（七）72实验名称：图和图的遍历（八）76设计性、综合性实验78附录2 数据结构课程设计完成情况登记表79附录3 图的应用80

3、实验一 线性表(一) 实验目的（1） 掌握线性表的顺序存储（2） 掌握线性表的链式存储（3） 掌握基本算法（建表、插入、删除）的实现(二) 实验内容1. 线性表的顺序存储：掌握线性表的顺序存储结构及其基本操作、合并、逆置等算法设顺序表的存储结构定义如下：（同学们可扩展考虑其他形式的存储结构定义）#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef structint *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前

4、分配的存储容量（以sizeof(int)为单位）SqList;题目1：编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。#include#include#define OK 1 #define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef structint *elem;int length;int listsize;SqList;int InitList_Sq(SqList &L)/ 算法2.3

5、，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE/ 请补全代码int Load_Sq(SqList &L)/ 输出顺序表中的所有元素int i;if( ) printf(The List is empty!); / 请填空elseprintf(The List is: );for( ) printf(%d , ); / 请填空printf(n);return OK;int ListInsert_Sq(SqList &L,int i,int e)/ 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e/ i的合法值为1iL.length +1/ 请补全代码int Li

6、stDelete_Sq(SqList &L,int i, int &e)/ 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值/ i的合法值为1iL.length/ 请补全代码int main()SqList T;int a, i;ElemType e, x;if( ) / 判断顺序表是否创建成功，请填空printf(A Sequence List Has Created.n);while(1)printf(1:Insert elementn2:Delete elementn3:Load all elementsn0:ExitnPlease choose:n);scanf(%d,

7、&a);switch(a)case 1: scanf(%d%d,&i,&x);if( ) printf(Insert Error!n); / 判断i值是否合法，请填空else printf(The Element %d is Successfully Inserted!n, x); break;case 2: scanf(%d,&i);if( ) printf(Delete Error!n); / 判断i值是否合法，请填空else printf(The Element %d is Successfully Deleted!n, e);break;case 3: Load_Sq(T);break

8、;case 0: return 1;测试样例格式说明：根据菜单操作：1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开2、输入2，表示要实现删除操作，紧跟着要输入删除的位置3、输入3，表示要输出顺序表的所有元素4、输入0，表示程序结束完整代码:#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef structint *elem,length,listsize;SqList;int Ini

9、tList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int Load_Sq(SqList &L)int i;if(L.length=0)printf(The List is empty!);elseprintf(The List is:);for(i=0;iL.length;i+)printf(% d,L.elemi);printf(n);return OK;int ListInsert_Sq(SqLi

10、st &L,int i,int e)if(iL.length+1)return ERROR;ElemType *newbase,*q,*p;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);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;int L

11、istDelete_Sq(SqList &L,int i,int &e)ElemType *q,*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;int main()SqList T;int a,i;ElemType e,x;if(InitList_Sq(T)printf(A Sequence List Has Created.n);while(1)printf(1:Insert elementn2:Delete ele

12、mentn3:Load all elementsn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d%d,&i,&x);if(!ListInsert_Sq(T,i,x)printf(Insert Error!n);else printf(The Element %d is Successfully Inserted!n,x);break;case 2: scanf(%d,&i);if(!ListDelete_Sq(T,i,e)printf(Delete Error!n);elseprintf(The Element %d

13、 is Successfully Deleted!n,e);break;case 3: Load_Sq(T);break;case 0: return 1; 题目2：编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。本题不提供代码，请同学们独立完成，所需子函数参考前面题目1完成的内容。测试样例格式说明：键盘输入第一行：顺序表A的元素个数第二行：顺序表A的各元素（非递减），用空格分开第三行：顺序表B的元素个数第四行：顺序表B的各元素（非递减），用空格分开正确输出第一行：顺序表A的元素列表第二行：顺序表B的元素列表第三行：合并后顺序表C的元素列表测试样例： 第一组自测数据 键

14、盘输入51 3 5 7 952 4 6 8 10 正确输出List A:1 3 5 7 9 List B:2 4 6 8 10 List C:1 2 3 4 5 6 7 8 9 10 第二组自测数据键盘输入612 24 45 62 84 96415 31 75 86正确输出List A:12 24 45 62 84 96 List B:15 31 75 86 List C:12 15 24 31 45 62 75 84 86 96 完整代码:#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define

15、LISTINCREMENT 10#define ElemType inttypedef structint *elem,length,listsize;SqList;int InitList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int Load_Sq(SqList &L)int i;for(i=0;iL.length;i+)printf(%d ,L.elemi);printf(n);return O

16、K;int ListLength(SqList L)return L.length;int GetElem(SqList L,int i,ElemType &e)e=L.elemi-1;return OK;int ListInsert_Sq(SqList &L,int i,int e)if(iL.length+1)return ERROR;ElemType *p,*q,*newbase;if(L.listsize=q;p-)*(p+1)=*p;*q=e;L.length+;return OK;void MergeList(SqList La,SqList Lb,SqList &Lc)int i

17、,j,k,La_len,Lb_len,ai,bj;i=j=1;k=0;InitList_Sq(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert_Sq(Lc,+k,ai);i+;elseListInsert_Sq(Lc,+k,bj);j+;while(i=La_len)GetElem(La,i+,ai);ListInsert_Sq(Lc,+k,ai);while(j=Lb_len)GetEle

18、m(Lb,j+,bj);ListInsert_Sq(Lc,+k,bj);Load_Sq(Lc);int main()int an,bn,i,e;SqList La,Lb,Lc;InitList_Sq(La);scanf(%d,&an);for(i=1;i=an;i+)scanf(%d,&e);ListInsert_Sq(La,i,e);printf(List A:);Load_Sq(La);InitList_Sq(Lb);scanf(%d,&bn);for(i=1;i=an;i+)scanf(%d,&e);ListInsert_Sq(Lb,i,e);printf(List B:);Load_S

19、q(Lb);printf(List C:);MergeList(La,Lb,Lc);return 0;题目3：设有一顺序表A=（a0,a1,., ai,.an-1)，其逆顺序表定义为A=( an-1,., ai,.,a1, a0)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。本题不提供代码，请同学们独立完成，所需子函数参考前面题目1完成的内容。测试样例格式说明：键盘输入第一行：输入顺序表的元素个数第二行：输入顺序表的各元素，用空格分开正确输出第一行：逆置前的顺序表元素列表第二行：逆置后的顺序表元素列表测试样例： 第一组自测数据键盘输入 101 2 3 4 5 6 7 8 9 1

20、0 正确输出The List is:1 2 3 4 5 6 7 8 9 10 The turned List is:10 9 8 7 6 5 4 3 2 1 第二组自测数据键盘输入832 97 54 65 35 84 61 75正确输出The List is:32 97 54 65 35 84 61 75 The turned List is:75 61 84 35 65 54 97 32 2. 线性表的链式存储：掌握线性表的链式存储结构及其基本操作、合并、逆置等算法。本实验以单链表为例，在完成题目的过程中，同学们可扩展考虑双链表及循环链表等结构的操作。设单链表的存储结构定义如下：（同学们可扩

21、展考虑其他形式的存储结构定义）#includetypedef struct LNode int data; / 存储在结点中的数据 struct LNode *next; / 指向下一结点的指针LNode,*LinkList;完整代码:#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType int typedef structint *elem,length,listsize;SqList;int InitList_Sq(SqLis

22、t &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)printf(NO1);return ERROR;L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int Load_Sq(SqList &L)int i;if(!L.length)printf(This List is empty!n);return ERROR;elsefor(i=0;i=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+L

23、ISTINCREMENT)*sizeof(ElemType);if(!newbase)printf(NO2);return ERROR;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;int swap(SqList &L,int n)int i,j,temp;for(i=0,j=n-1;ji;i+,j-)temp=L.elemi;L.elemi=L.elemj;L.elemj=temp;retur

24、n OK;int main()SqList T;int n,i;ElemType x;scanf(%d,&n);InitList_Sq(T);for(i=1;in+1;i+)scanf(%d,&x);ListInsert_Sq(T,i,x);printf(The List is:);Load_Sq(T);swap(T,n);printf(The turned List is:);Load_Sq(T);return 0;题目4：编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容#include#include#define ERROR 0

25、#define OK 1 #define ElemType inttypedef struct LNode int data; struct LNode *next;LNode,*LinkList;int CreateLink_L(LinkList &L,int n)/ 创建含有n个元素的单链表 LinkList p,q; int i; ElemType e; L = (LinkList)malloc(sizeof(LNode); L-next = NULL; / 先建立一个带头结点的单链表 q = (LinkList)malloc(sizeof(LNode); q = L; for (i=0

26、; inext; if( )printf(The List is empty!); / 请填空 else printf(The LinkList is:); while( ) / 请填空printf(%d ,p-data); / 请填空 printf(n); return OK;int LinkInsert_L(LinkList &L,int i,ElemType e)/ 算法2.9/ 在带头结点的单链线性表L中第i个位置之前插入元素e/ 请补全代码int LinkDelete_L(LinkList &L,int i, ElemType &e)/ 算法2.10/ 在带头结点的单链线性表L中，删

27、除第i个元素，并用e返回其值/ 请补全代码int main() LinkList T; int a,n,i; ElemType x, e; printf(Please input the init size of the linklist:n); scanf(%d,&n); printf(Please input the %d element of the linklist:n, n); if( ) / 判断链表是否创建成功，请填空 printf(A Link List Has Created.n); LoadLink_L(T); while(1)printf(1:Insert element

28、n2:Delete elementn3:Load all elementsn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d%d,&i,&x); if( ) printf(Insert Error!n); / 判断i值是否合法，请填空 else printf(The Element %d is Successfully Inserted!n, x); break;case 2: scanf(%d,&i); if( ) printf(Delete Error!n); / 判断i值是否合法，请填空 else printf(

29、The Element %d is Successfully Deleted!n, e); break;case 3: LoadLink_L(T); break;case 0: return 1;测试样例格式说明：根据菜单操作：1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开2、输入2，表示要实现删除操作，紧跟着要输入删除的位置3、输入3，表示要输出顺序表的所有元素4、输入0，表示程序结束完整代码:#include#include#define ERROR 0#define OK 1#define ElemType int typedef struct LNodeint

30、 data;struct LNode *next;LNode,*LinkList;int CreateLink_L(LinkList &L,int n)LinkList p,q;int i;ElemType e;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;q=(LinkList)malloc(sizeof(LNode);q=L;for(i=0;idata=e;p-next=q-next;q-next=p;q=q-next;return OK;int LoadLink_L(LinkList &L)LinkList p=L-next;if(!p)pri

31、ntf(The List is empty!);elseprintf(The LinkList is:);while(p)printf(%d ,p-data);p=p-next;printf(n);return OK;int LinkInsert_L(LinkList &L,int i,ElemType e)LNode *p=L,*s;int j=0;while(p&jnext;j+;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;int Lin

32、kDelete_L(LinkList &L,int i,ElemType &e)LNode *p=L,*q;int j=0;while(p-next&jnext;j+;if(!(p-next)|jnext;p-next=q-next;e=q-data;free(q);return OK;int main()LinkList T;int a,n,i;ElemType x,e;printf(Please input the init size of the linklist:n);scanf(%d,&n);printf(Please input the %d element of the link

33、list:n,n);if(CreateLink_L(T,n)printf(A Link List Has Created.n);LoadLink_L(T);while(1)printf(1:Insert elementn2:Delete elementn3:Load all elementsn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1:scanf(%d%d,&i,&x);if(!LinkInsert_L(T,i,x)printf(Insert Error!n);elseprintf(The Element %d is Success

34、fully Inserted!n,x);break;case 2:scanf(%d,&i);if(!LinkDelete_L(T,i,e)printf(Delete Error!n);elseprintf(The Element %d is Successfully Deleted!n,e);break;case 3:LoadLink_L(T);break;case 0:return 1;题目5：设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。本题不提供代码，请同学们独立完成，所需子函数参考题目4完成的内容。测试样例格式说明：键盘输入第一行：单链表A的元素个数第二行：单链

35、表A的各元素（非递减），用空格分开第三行：单链表B的元素个数第四行：单链表B的各元素（非递减），用空格分开正确输出第一行：单链表A的元素列表第二行：单链表B的元素列表第三行：合并后单链表C的元素列表测试样例：键盘输入612 24 45 62 84 96415 31 75 86正确输出List A:12 24 45 62 84 96 List B:15 31 75 86 List C:12 15 24 31 45 62 75 84 86 96 完整代码:#include#include#define ERROR 0#define OK 1#define ElemType inttypedef s

36、truct LNodeint data;struct LNode *next;LNode,*LinkList;int CreateLink_L(LinkList &L,int n)LinkList p,q;int i;ElemType e;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;q=(LinkList)malloc(sizeof(LNode);q=L;for(i=0;idata=e;p-next=q-next;q-next=p;q=q-next;return OK;int LoadLink_L(LinkList &L)LinkList p=L-

37、next;if(!p)printf(The List is empty!);elsewhile(p)printf(%d ,p-data);p=p-next;printf(n);return OK;void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)LinkList pa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);int main()LinkList La,Lb,Lc;int n;scanf(%d,&n);CreateLink_L(La,n);printf(List A:);LoadLink_L(La);scanf(%d,&n);CreateLink_L(Lb,n);printf(List