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

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

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 inttypedef structi

2、nt *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

3、 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

4、: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 El

5、ement %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，表示程序结束输入样例11 211 32130输出样例A Sequence List Has Created.1:Insert element2:Delete element3:Load all elements

6、0:ExitPlease choose:The Element 2 is Successfully Inserted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 3 is Successfully Inserted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 3 is Successfully Deleted!1:Insert element2:Dele

7、te element3:Load all elements0:ExitPlease choose:The List is: 2 1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:作者yqm 解法一：（正规解法）#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef structint *elem;int length;i

8、nt listsize;SqList;int 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!); / 请填空elseprint

9、f(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)/ 算法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.l

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

11、th)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:ExitnPleas

12、e choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d%d,&i,&x);if(!ListInsert_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

13、 Successfully Deleted!n, e);break;case 3: Load_Sq(T);break;case 0: return 1;解法二：（C+STL list）#include#include#includeusing 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 ch

14、oose: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

15、); printf(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+; prin

16、tf(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(The List is: ); for(plist = T.begin(); plist != T.end(); plist+) printf(%d ,*plist); printf(n); break; case 0: return 1;解法三：（数组）#include#include#includeint main(

17、) 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 elementsn0: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=

18、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=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

19、 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编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。本题不提供代码，请同学们独立完成，所需子函数参考前面完成的内容。 输入格式第一行：顺序表A的元素个数第二行：顺序表A的各元素（非递减），用空格分开

20、第三行：顺序表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 作者yqm 解法一：（正规解法）#include#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define E

21、lemType int#define OVERFLOW -2typedef 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; for(i=0; iL.length; i+) scanf(%d,&L.elemi); return OK;int Load_Sq(SqList &L) int i; if(L.length=0)

22、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_last,*pb_last; pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.len

23、gth; 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) *pc+=*pa+; while(pb=pb_last) *pc+=*pb+;int main() SqList T,R,Y;

24、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#includeusing namespace std;void load(list L) list:iterator plist; for(plist = L

25、.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.merge(R); printf(L

26、ist C:); load(T);解法三：（数组）#include#include#includeint 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

27、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)

28、; mergeList_Sq(T,R,Y,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)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。本题不提供代码，请同

29、学们独立完成，所需子函数参考前面完成的内容。 输入格式第一行：输入顺序表的元素个数第二行：输入顺序表的各元素，用空格分开输出格式第一行：逆置前的顺序表元素列表第二行：逆置后的顺序表元素列表输入样例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作者yqm 解法一：（正规解法）#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREME

30、NT 10#define ElemType inttypedef structint *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);

31、 return OK;int Load_Sq(SqList &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_S

32、q(T,n);f(T,n);printf(The turned List is:);Load_Sq(T,n);解法二（C+STL list）#include#include#includeusing 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

33、); T.push_back(x);printf(The List is:);load(T);T.reverse();printf(The turned List is:);load(T);解法三：（数组）#include#includeint 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;sca

34、nf(%d,&n);for(int i=0;in;i+) scanf(%d,&Ti);printf(The List 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#defi

35、ne 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; in; i+) scanf(%d, &e); p = (LinkList)malloc(sizeof(LNode); / 生成新结点 / 请补全代码 return OK;int LoadLink_L(LinkList &L)