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

目 录实验一 线性表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(三) 实验报告41实验八 图和图的遍历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 图的应用8047实验一 线性表(一) 实验目的（1） 掌握线性表的顺序存储（2） 掌握线性表的链式存储（3） 掌握基本算法（建表、插入、删除）的实现(二) 实验内容1. 线性表的顺序存储：掌握线性表的顺序存储结构及其基本操作、合并、逆置等算法设顺序表的存储结构定义如下：（同学们可扩展考虑其他形式的存储结构定义）#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef structint *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量（以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，构造一个空的线性表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 ListDelete_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,&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;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 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;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(SqList &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 ListDelete_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 elementn3: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 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的元素列表测试样例： 第一组自测数据 键盘输入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 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 OK;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,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)GetElem(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_Sq(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 10 正确输出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. 线性表的链式存储：掌握线性表的链式存储结构及其基本操作、合并、逆置等算法。本实验以单链表为例，在完成题目的过程中，同学们可扩展考虑双链表及循环链表等结构的操作。设单链表的存储结构定义如下：（同学们可扩展考虑其他形式的存储结构定义）#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(SqList &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+LISTINCREMENT)*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;return 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#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; 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中，删除第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 elementn2: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(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 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)printf(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 LinkDelete_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 linklist: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 Successfully 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的元素个数第二行：单链表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 struct 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-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 B:);LoadLink_L(Lb);MergeList_L(La,Lb,Lc);printf(List C:);LoadLink_L(Lc);return 0;题目6：设有一线性表A=（a0,a1,., ai,.an-1)，其逆线性表定义为A=( an-1,., ai,.,a1, a0)，设计一个算法，将链式线性表逆置，要求线性表仍占用原线性表的空间。本题不提供代码，请同学们独立完成，所需子函数参考题目4完成的内容。测试样例格式说明：键盘输入第一行：输入n，表示单链表的元素个数第二行：输入单链表的各元素，用空格分开正确输出第一行：输出单链表逆置前的元素列表第二行：输出单链表逆置后的元素列表测试样例：键盘输入 832 97 54 65 35 84 61 75 正确输出The List is:32 97 54 65 35 84 61 75 The turned List is:75 62 84 35 65 54 97 32 完整代码:#include#include#define OK 1#define ERROR 0#define ElemType int typedef struct 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-next;if(!p)printf(The List is Empty!);elsewhile(p)printf(%d ,p-data);p=p-next;printf(n);return OK;int inversion(LinkList &L)LinkList p=L-next,q;L-next=NULL;while(p)q=p-next;p-next=L-next;L-next=p;p=q;return OK;int main()LinkList T;int n;scanf(%d,&n);CreateLink_L(T,n);printf(The List is:);LoadLink_L(T);inversion(T);printf(The turned List is:);LoadLink_L(T);return 0;(三) 实验报告（1） 本实验所有题目要求在JudgeOnline上提交通过。（2） 实验报告针对以上所有实验内容。（3） 实验目的主要是阐述本实验需要掌握的知识要点。（4） 实验总结主要是对实验内容的掌握及理解程序作一个归纳性的叙述。（5） 对于思考题进行分析和思考，并做出相应的结论。（6） 本次实验报告可以在堂下完成。实验二 堆栈(一) 实验目的(1) 理解堆栈的结构及操作特点(2) 实现堆栈的PUSH、POP等基本操作算法(3) 熟练掌握入栈、出栈时栈顶指针的变化情况(4) 掌握堆栈的实际应用(二) 实验内容1. 顺序栈的基本操作题目1：创建一个空的顺序栈，并实现栈的入栈、出栈、返回栈的长度、返回栈顶元素、栈的遍历等基本算法。请将下面的程序补充完整。#include #include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 / 存储空间初始分配量#define STACKINCREMENT 10 / 存储空间分配增量typedef int SElemType; / 定义栈元素类型typedef int Status; / Status