华南农业大学数据结构实验答案(包含STL版)6163.pdf

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

1、8576 顺序线性表的基本操作 时间限制:1000MS 存限制:1000K 提交次数:9027 通过次数:2456 题型:编程题 语言:无限制 Description 编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全容。#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType int typedef struct int*elem;int length;int l

2、istsize;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!);/请填空 else printf(The List is:);for(_)printf(%d,_);/请填空 printf(n);return OK;int ListInsert_Sq(SqList&L,int i,int e)/算法2.4，在顺序线性表L中第i个位置之前插入新

3、的元素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:ExitnPl

4、ease 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

5、_Sq(T);break;case 0:return 1;输入格式 测试样例格式说明：根据菜单操作：1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开 2、输入2，表示要实现删除操作，紧跟着要输入删除的位置 3、输入3，表示要输出顺序表的所有元素 4、输入0，表示程序结束 输入样例 1 1 2 1 1 3 2 1 3 0 输出样例 A Sequence List Has Created.1:Insert element 2:Delete element 3:Load all elements 0:Exit Please choose:The Element 2 is Su

6、ccessfully Inserted!1:Insert element 2:Delete element 3:Load all elements 0:Exit Please choose:The Element 3 is Successfully Inserted!1:Insert element 2:Delete element 3:Load all elements 0:Exit Please choose:The Element 3 is Successfully Deleted!1:Insert element 2:Delete element 3:Load all elements

7、 0:Exit Please choose:The List is:2 1:Insert element 2:Delete element 3:Load all elements 0:Exit Please choose:作者 yqm 解法一：（正规解法）#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType int typedef struct int*elem;int length;int listsize;SqList;int

8、 InitList_Sq(SqList&L)/算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE/请补全代码 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);L.length=0;L.listsize=LIST_INIT_SIZE;return 0;int Load_Sq(SqList&L)/输出顺序表中的所有元素 int i;if(L.length=0)printf(The List is empty!);/请填空 else printf(The List is:);for(i=0;iL.len

9、gth;i+)printf(%d,L.elemi);/请填空 printf(n);return OK;int ListInsert_Sq(SqList&L,int i,int e)/算法2.4，在顺序线性表L中第i个位置之前插入新的元素e/i的合法值为1iL.length+1/请补全代码 ElemType*newbase,*p,*q;if(iL.length+1)return ERROR;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);L.e

10、lem=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)/算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值/i的合法值为1iL.length/请补全代码 ElemType*p,*q;if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for

11、(+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(!ListIn

12、sert_Sq(T,i,x)printf(Insert Error!n);/判断i值是否合法，请填空 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);/判断i值是否合法，请填空 else printf(The Element%d is Successfully Deleted!n,e);break;case 3:Load_Sq(T);break;case 0:return 1;解法二：（

13、C+STL list）#include#include#include using namespace std;int main()list T;int a,i;int e,x;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(i(int)T.size()+1)printf(Insert

14、 Error!n);/判断i值是否合法 else int j=1,p=0;list:iterator iter=T.begin();if(i=1)T.push_front(x);p=1;while(iter!=T.end()if(j=i&i!=1)T.insert(iter,x);p=1;iter+;break;else j+;iter+;if(!p)T.push_back(x);printf(The Element%d is Successfully Inserted!n,x);break;case 2:scanf(%d,&i);if(i(int)T.size()printf(Delete

15、Error!n);/判断i值是否合法 else int j=1;list:iterator iter;for(iter=T.begin();iter!=T.end();+iter)if(j=i)list:iterator tmp;tmp=iter;e=*iter;iter+;T.erase(tmp);break;else j+;printf(The Element%d is Successfully Deleted!n,e);break;case 3:if(T.empty()printf(The List is empty!n);else list:iterator plist;printf(

16、The List is:);for(plist=T.begin();plist!=T.end();plist+)printf(%d,*plist);printf(n);break;case 0:return 1;解法三：（数组）#include#include#include int main()int T1000;memset(T,0,sizeof(T);int a,i,k=1,e,x;printf(A Sequence List Has Created.n);while(1)printf(1:Insert elementn2:Delete elementn3:Load all elemen

17、tsn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1:scanf(%d%d,&i,&x);if(ik)printf(Insert Error!n);/判断i值是否合法，请填空 else for(int j=k-1;j=i;j-)Tj+1=Tj;Ti=x;k+;printf(The Element%d is Successfully Inserted!n,x);break;case 2:scanf(%d,&i);if(ik-1)printf(Delete Error!n);/判断i值是否合法，请填空 else e=Ti;for(int j

18、=i;jk;j+)Tj=Tj+1;k-;printf(The Element%d is Successfully Deleted!n,e);break;case 3:if(k=1)printf(The List is empty!);else printf(The List is:);for(int j=1;jk;j+)printf(%d,Tj);printf(n);break;case 0:return 1;8577 合并顺序表 时间限制:1000MS 存限制:1000K 提交次数:5339 通过次数:2251 题型:编程题 语言:无限制 Description 编写算法，将两个非递减有序顺

19、序表A和B合并成一个新的非递减有序顺序表C。本题不提供代码，请同学们独立完成，所需子函数参考前面完成的容。输入格式 第一行：顺序表A的元素个数 第二行：顺序表A的各元素（非递减），用空格分开 第三行：顺序表B的元素个数 第四行：顺序表B的各元素（非递减），用空格分开 输出格式 第一行：顺序表A的元素列表 第二行：顺序表B的元素列表 第三行：合并后顺序表C的元素列表 输入样例 5 1 3 5 7 9 5 2 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 作者 yqm 解法一：（正规解法）#

20、include#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType int#define OVERFLOW-2 typedef struct int*elem;int length;int listsize;SqList;int InitList_Sq(SqList&L,int n)int i;L.elem=(ElemType*)malloc(n*sizeof(ElemType);L.listsize=n;L.length=n;f

21、or(i=0;iL.length;i+)scanf(%d,&L.elemi);return OK;int Load_Sq(SqList&L)int i;if(L.length=0)return 0;/请填空 else for(i=0;iL.length-1;i+)printf(%d,L.elemi);printf(%d,L.elemL.length-1);printf(n);/if(ch=A)ch=B;/else if(ch=B)ch=C;return OK;void mergeList_Sq(SqList La,SqList Lb,SqList&Lc)int*pa,*pb,*pc,*pa_l

22、ast,*pb_last;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb)*pc+=*pa+;else *pc+=*pb+;while(pa=pa_last)*

23、pc+=*pa+;while(pb=pb_last)*pc+=*pb+;int main()SqList T,R,Y;int a,b;scanf(%d,&a);InitList_Sq(T,a);scanf(%d,&b);InitList_Sq(R,b);mergeList_Sq(T,R,Y);printf(List A:);Load_Sq(T);printf(List B:);Load_Sq(R);printf(List C:);Load_Sq(Y);解法二（C+STL list）#include#include#include#include using namespace std;void

24、 load(list L)list:iterator plist;for(plist=L.begin();plist!=L.end();plist+)printf(%d,*plist);printf(n);int main()list T,R;int a,b,x;scanf(%d,&a);for(int i=0;ia;i+)scanf(%d,&x);T.push_back(x);scanf(%d,&b);for(int i=0;ib;i+)scanf(%d,&x);R.push_back(x);printf(List A:);load(T);printf(List B:);load(R);T.

25、merge(R);printf(List C:);load(T);解法三：（数组）#include#include#include int InitList_Sq(int L,int n)int i;for(i=0;in;i+)scanf(%d,&Li);return 1;int Load_Sq(int L,int n)int i;if(n=0)return 0;/请填空 else for(i=0;in;i+)printf(%d,Li);printf(n);return 1;void mergeList_Sq(int a,int b,int c,int a_length,int b_lengt

26、h)int i=0,j=0,k=0;while(ia_length&jb_length)if(ai=bj)ck+=ai+;else ck+=bj+;while(ia_length)ck+=ai+;while(jb_length)ck+=bj+;int main()int T100,R100,Y100;memset(T,0,sizeof(T);memset(R,0,sizeof(R);memset(Y,0,sizeof(Y);int a,b;scanf(%d,&a);InitList_Sq(T,a);scanf(%d,&b);InitList_Sq(R,b);mergeList_Sq(T,R,Y

27、,a,b);printf(List A:);Load_Sq(T,a);printf(List B:);Load_Sq(R,b);printf(List C:);Load_Sq(Y,a+b);8578 顺序表逆置 时间限制:1000MS 存限制:1000K 提交次数:3660 通过次数:2149 题型:编程题 语言:无限制 Description 设有一顺序表A=（a0,a1,.,ai,.an-1)，其逆顺序表定义为A=(an-1,.,ai,.,a1,a0)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。本题不提供代码，请同学们独立完成，所需子函数参考前面完成的容。输入格式 第一行

28、：输入顺序表的元素个数 第二行：输入顺序表的各元素，用空格分开 输出格式 第一行：逆置前的顺序表元素列表 第二行：逆置后的顺序表元素列表 输入样例 10 1 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 作者 yqm 解法一：（正规解法）#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemTy

29、pe int typedef struct int*elem;int length;int listsize;SqList;int InitList_Sq(SqList&L,int n)/算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE/请补全代码 int i;L.elem=(ElemType*)malloc(n*sizeof(ElemType);if(!L.elem)return ERROR;L.listsize=n;L.length=0;for(i=0;in;i+)scanf(%d,&L.elemi);return OK;int Load_Sq(SqLis

30、t&L,int n)/输出顺序表中的所有元素 int i;for(i=0;in;i+)printf(%d,L.elemi);printf(n);return OK;int f(SqList&L,int n)int i,t;for(i=0;in/2;i+)t=L.elemi;L.elemi=L.elemn-i-1;L.elemn-i-1=t;return OK;int main()SqList T;int n;scanf(%d,&n);InitList_Sq(T,n);printf(The List is:);Load_Sq(T,n);f(T,n);printf(The turned List

31、is:);Load_Sq(T,n);解法二（C+STL list）#include#include#include using namespace std;void load(list L)list:iterator plist;for(plist=L.begin();plist!=L.end();plist+)printf(%d,*plist);printf(n);int main()list T;int n,x;scanf(%d,&n);for(int i=0;in;i+)scanf(%d,&x);T.push_back(x);printf(The List is:);load(T);T.

32、reverse();printf(The turned List is:);load(T);解法三：（数组）#include#include int Load_Sq(int L,int n)for(int i=0;in;i+)printf(%d,Li);printf(n);return 1;int f(int L,int n)int i,t;for(i=0;in/2;i+)t=Li;Li=Ln-i-1;Ln-i-1=t;return 1;int main()int T100,n;scanf(%d,&n);for(int i=0;in;i+)scanf(%d,&Ti);printf(The Li

33、st is:);Load_Sq(T,n);f(T,n);printf(The turned List is:);Load_Sq(T,n);8579 链式线性表的基本操作 时间限制:1000MS 存限制:1000K 提交次数:5567 通过次数:2176 题型:编程题 语言:无限制 Description 编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全容。#include#include#define ERROR 0#define OK 1#define ElemType int typedef struct LNode int data

34、;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(_)/

35、请填空 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

36、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(_

37、)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，表示要实现插入

38、操作，紧跟着要输入插入的位置和元素，用空格分开 2、输入2，表示要实现删除操作，紧跟着要输入删除的位置 3、输入3，表示要输出顺序表的所有元素 4、输入0，表示程序结束 输入样例 3 3 6 9 3 1 4 12 2 1 3 0 输出样例 Please input the init size of the linklist:Please input the 3 element of the linklist:A Link List Has Created.The LinkList is:3 6 9 1:Insert element 2:Delete element 3:Load all ele

39、ments 0:Exit Please choose:The LinkList is:3 6 9 1:Insert element 2:Delete element 3:Load all elements 0:Exit Please choose:The Element 12 is Successfully Inserted!1:Insert element 2:Delete element 3:Load all elements 0:Exit Please choose:The Element 3 is Successfully Deleted!1:Insert element 2:Dele

40、te element 3:Load all elements 0:Exit Please choose:The LinkList is:6 9 12 1:Insert element 2:Delete element 3:Load all elements 0:Exit Please choose:作者 yqm 解法一：（正规解法）#include#include#define ERROR 0#define OK 1#define ElemType int typedef struct LNode int data;struct LNode*next;LNode,*LinkList;int C

41、reateLink_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;idata=e;p-next=q-next;q-next=p;q=p;return OK;int LoadLink_L(LinkList&L)/单链表遍历 LinkList p=L-next;if(p=NULL)printf(The List

42、is empty!);/请填空 else printf(The LinkList is:);while(p!=NULL)/请填空 printf(%d,p-data);p=p-next;/请填空 printf(n);return OK;int LinkInsert_L(LinkList&L,int i,ElemType e)/算法2.9/在带头结点的单链线性表L中第i个位置之前插入元素e/请补全代码 LinkList p,s;int j;p=L;j=0;while(p&jnext;+j;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode

43、);s-data=e;s-next=p-next;p-next=s;return OK;int LinkDelete_L(LinkList&L,int i,ElemType&e)/算法2.10/在带头结点的单链线性表L中，删除第i个元素，并用e返回其值/请补全代码 LinkList p,q;int j;p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;int main()LinkList T;int a,n,i;ElemTy

44、pe 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 choos

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

46、ted!n,e);break;case 3:LoadLink_L(T);break;case 0:return 1;解法二:(C+STL list)#include#include#include using namespace std;void load(list L)if(L.size()=0)printf(The List is empty!);else printf(The LinkList is:);list:iterator plist;for(plist=L.begin();plist!=L.end();plist+)printf(%d,*plist);printf(n);int

47、 main()list T;int a,n,i,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);printf(A Link List Has Created.n);for(i=0;in;i+)scanf(%d,&x);T.push_back(x);load(T);while(1)printf(1:Insert elementn2:Delete elementn3:Load all element

48、sn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1:scanf(%d%d,&i,&x);if(i(int)T.size()+1)printf(Insert Error!n);/判断i值是否合法 else int j=1,p=0;list:iterator iter=T.begin();if(i=1)T.push_front(x);p=1;while(iter!=T.end()if(j=i&i!=1)T.insert(iter,x);p=1;iter+;break;else j+;iter+;if(!p)T.push_back(x);pr

49、intf(The Element%d is Successfully Inserted!n,x);break;case 2:scanf(%d,&i);if(i(int)T.size()printf(Delete Error!n);/判断i值是否合法 else int j=1;list:iterator iter;for(iter=T.begin();iter!=T.end();+iter)if(j=i)list:iterator tmp;tmp=iter;e=*iter;iter+;T.erase(tmp);break;else j+;printf(The Element%d is Succe

50、ssfully Deleted!n,e);break;case 3:load(T);break;case 0:return 1;解法三：（数组）#include#include#include int main()int T1000;memset(T,0,sizeof(T);int a,i,k=1,e,x,n;printf(Please input the init size of the linklist:n);scanf(%d,&n);printf(Please input the%d element of the linklist:n,n);for(int i=1;i=n;i+)scan