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

1、华南农业大学数据结构实验答案包含STL版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 struct int

2、*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!); / 请填空 else printf(The List is: ); for(_) printf(%d ,_); / 请填空 printf(n); return OK;int ListInsert_Sq(SqList

3、&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:Ins

4、ert 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值是否合法，请

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

6、element3:Load all elements0: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 Dele

7、ted!1:Insert element2:Delete 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 st

8、ruct int *elem; int length; int 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

9、List is empty!); / 请填空 else printf(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) ne

10、wbase=(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)/ 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值/ i的合法值为1iL.leng

11、th/ 请补全代码 ElemType *p,*q; 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:Dele

12、te 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); / 判断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 Er

13、ror!n); / 判断i值是否合法，请填空 else printf(The Element %d is 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 elem

14、entn2: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 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)

15、; 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 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

16、=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(The List is: ); for(plist = T.begin(); plist != T.end(); plist+) printf(%d ,*plist); printf(n); break; c

17、ase 0: return 1; 解法三：（数组）#include#include#includeint 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 elementsn0:ExitnPlease choose:n); scanf(%d,&a); switch(a) case 1: scanf(%d%d,&i,&x); if(

18、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=i; jk; j+) Tj=Tj+1; k-; printf(The Element %d is Successf

19、ully 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编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。本题不提供代码，请同学们独立

20、完成，所需子函数参考前面完成的内容。 输入格式第一行：顺序表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 作者yqm 解法一：（正规解法）#include#include#include#define OK 1#define ERROR 0

21、#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType 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.elem

22、i); 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_last,*pb_last; pa=

23、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) *pc+=

24、*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#includeusing namespa

25、ce 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,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

26、:); load(T); printf(List B:); load(R); T.merge(R); printf(List 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_length) int i=0,j=0,k=0; while(ia_le