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

精选优质文档-倾情为你奉上8576 顺序线性表的基本操作时间限制:1000MS 内存限制:1000K提交次数:9027 通过次数:2456 题型: 编程题 语言: 无限制Description编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。 #include<stdio.h>#include<malloc.h>#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，表示程序结束输入样例11 211 32130输出样例A Sequence List Has Created.1:Insert element2:Delete 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 Deleted!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<stdio.h>#include<malloc.h>#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/ 请补全代码 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!"); / 请填空elseprintf("The List is: ");for(i=0;i<L.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(i<1|i>L.length+1)return ERROR; 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)/ 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值/ i的合法值为1iL.length/ 请补全代码 ElemType *p,*q; if(i<1|i>L.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"); / 判断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;解法二：（C+STL list）#include<stdio.h>#include<malloc.h>#include<list>using namespace std;int main() list<int> 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<1|i>(int)T.size()+1) printf("Insert Error!n"); / 判断i值是否合法 else int j=1,p=0; list<int>: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<1|i>(int)T.size() printf("Delete Error!n"); / 判断i值是否合法 else int j=1; list<int>:iterator iter; for(iter=T.begin();iter!=T.end();+iter) if(j=i) list<int>: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<int>: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<stdio.h>#include<malloc.h>#include<string.h>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 elementsn0:ExitnPlease choose:n"); scanf("%d",&a); switch(a) case 1: scanf("%d%d",&i,&x); if(i<1|i>k) 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(i<1|i>k-1) printf("Delete Error!n"); / 判断i值是否合法，请填空 else e=Ti; for(int j=i; j<k; 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; j<k; j+) printf("%d ",Tj); printf("n"); break; case 0: return 1; 8577 合并顺序表时间限制:1000MS 内存限制:1000K提交次数:5339 通过次数:2251 题型: 编程题 语言: 无限制Description编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。本题不提供代码，请同学们独立完成，所需子函数参考前面完成的内容。 输入格式第一行：顺序表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<stdio.h>#include<stdlib.h>#include<malloc.h>#define OK 1#define ERROR 0#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; i<L.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; i<L.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.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+=*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<stdio.h>#include<stdlib.h>#include<malloc.h>#include<list>using namespace std;void load(list<int> L) list<int>:iterator plist; for(plist = L.begin(); plist != L.end(); plist+) printf("%d ",*plist); printf("n");int main() list<int> T,R; int a,b,x; scanf("%d",&a); for(int i=0; i<a; i+) scanf("%d",&x); T.push_back(x); scanf("%d",&b); for(int i=0; i<b; i+) scanf("%d",&x); R.push_back(x); printf("List A:"); load(T); printf("List B:"); load(R); T.merge(R); printf("List C:"); load(T);解法三：（数组）#include<stdio.h>#include<stdlib.h>#include<string.h>int InitList_Sq(int L,int n) int i; for(i=0; i<n; i+) scanf("%d",&Li); return 1;int Load_Sq(int L,int n) int i; if(n=0) return 0; / 请填空 else for(i=0; i<n; 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(i<a_length&&j<b_length) if(ai<=bj) ck+=ai+; else ck+=bj+; while(i<a_length) ck+=ai+; while(j<b_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,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)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。本题不提供代码，请同学们独立完成，所需子函数参考前面完成的内容。 输入格式第一行：输入顺序表的元素个数第二行：输入顺序表的各元素，用空格分开输出格式第一行：逆置前的顺序表元素列表第二行：逆置后的顺序表元素列表输入样例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<stdio.h>#include<malloc.h>#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,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;i<n;i+) scanf("%d",&L.elemi); return OK;int Load_Sq(SqList &L,int n)/ 输出顺序表中的所有元素int i;for(i=0;i<n;i+)printf("%d ",L.elemi);printf("n");return OK;int f(SqList &L,int n) int i,t; for(i=0;i<n/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 is:");Load_Sq(T,n);解法二（C+STL list）#include<stdio.h>#include<malloc.h>#include<list>using namespace std;void load(list<int> L) list<int>:iterator plist; for(plist = L.begin(); plist != L.end(); plist+) printf("%d ",*plist); printf("n");int main()list<int> T;int n,x;scanf("%d",&n);for(int i=0;i<n;i+) scanf("%d",&x); T.push_back(x); printf("The List is:");load(T);T.reverse();printf("The turned List is:");load(T);解法三：（数组）#include<stdio.h>#include<malloc.h>int Load_Sq(int L,int n)for(int i=0;i<n;i+)printf("%d ",Li);printf("n");return 1;int f(int L,int n) int i,t; for(i=0;i<n/2;i+) t=Li; Li=L