華南農(nóng)業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)答案(包含STL版)(共128頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上8576 順序線(xiàn)性表的基本操作時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):9027 通過(guò)次數(shù):2456 題型: 編程題 語(yǔ)言: 無(wú)限制Description編寫(xiě)算法，創(chuàng)建初始化容量為L(zhǎng)IST_INIT_SIZE的順序表T，并實(shí)現(xiàn)插入、刪除、遍歷操作。本題目給出部分代碼，請(qǐng)補(bǔ)全內(nèi)容。 #include<stdio.h>#include<malloc.h>#define OK 1 #define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemTyp

2、e inttypedef structint *elem;int length;int listsize;SqList;int InitList_Sq(SqList &L)/ 算法2.3，構(gòu)造一個(gè)空的線(xiàn)性表L，該線(xiàn)性表預(yù)定義大小為L(zhǎng)IST_INIT_SIZE/ 請(qǐng)補(bǔ)全代碼int Load_Sq(SqList &L)/ 輸出順序表中的所有元素int i;if(_) printf("The List is empty!"); / 請(qǐng)?zhí)羁誩lseprintf("The List is: ");for(_) printf("%d &qu

3、ot;,_); / 請(qǐng)?zhí)羁誴rintf("n");return OK;int ListInsert_Sq(SqList &L,int i,int e)/ 算法2.4，在順序線(xiàn)性表L中第i個(gè)位置之前插入新的元素e/ i的合法值為1iL.length +1/ 請(qǐng)補(bǔ)全代碼int ListDelete_Sq(SqList &L,int i, int &e)/ 算法2.5,在順序線(xiàn)性表L中刪除第i個(gè)位置的元素，并用e返回其值/ i的合法值為1iL.length/ 請(qǐng)補(bǔ)全代碼int main()SqList T;int a, i;ElemType e, x;if

4、(_) / 判斷順序表是否創(chuàng)建成功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"); /

5、判斷i值是否合法，請(qǐng)?zhí)羁誩lse printf("The Element %d is Successfully Inserted!n", x); break;case 2: scanf("%d",&i);if(_) printf("Delete Error!n"); / 判斷i值是否合法，請(qǐng)?zhí)羁誩lse printf("The Element %d is Successfully Deleted!n", e);break;case 3: Load_Sq(T);break;case 0: return 1;輸

6、入格式測(cè)試樣例格式說(shuō)明：根據(jù)菜單操作：1、輸入1，表示要實(shí)現(xiàn)插入操作，緊跟著要輸入插入的位置和元素，用空格分開(kāi)2、輸入2，表示要實(shí)現(xiàn)刪除操作，緊跟著要輸入刪除的位置3、輸入3，表示要輸出順序表的所有元素4、輸入0，表示程序結(jié)束輸入樣例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 elem

7、ent3: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

8、 element3:Load all elements0:ExitPlease choose:作者yqm 解法一：（正規(guī)解法）#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，

9、構(gòu)造一個(gè)空的線(xiàn)性表L，該線(xiàn)性表預(yù)定義大小為L(zhǎng)IST_INIT_SIZE/ 請(qǐng)補(bǔ)全代碼 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!"); / 請(qǐng)?zhí)羁誩lseprintf("The List is: ");for(i=0;

10、i<L.length;i+) printf("%d ",L.elemi); / 請(qǐng)?zhí)羁誴rintf("n");return OK;int ListInsert_Sq(SqList &L,int i,int e)/ 算法2.4，在順序線(xiàn)性表L中第i個(gè)位置之前插入新的元素e/ i的合法值為1iL.length +1/ 請(qǐng)補(bǔ)全代碼 ElemType *newbase,*p,*q; if(i<1|i>L.length+1)return ERROR; if(L.length>=L.listsize) newbase=(ElemTyp

11、e*)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,在順序線(xiàn)性表L中刪除第i個(gè)位置的元素，并用e返回其值/ i的合法值為1i

12、L.length/ 請(qǐng)補(bǔ)全代碼 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) / 判斷順序表是否創(chuàng)建成功printf("A Sequence List Has Created.n");while(1)

13、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值是否合法，請(qǐng)?zhí)羁誩lse printf("The Element %d is Successf

14、ully Inserted!n", x);break;case 2: scanf("%d",&i);if(!ListDelete_Sq(T,i,e) printf("Delete Error!n"); / 判斷i值是否合法，請(qǐng)?zhí)羁誩lse 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>

15、#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)

16、; 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+; b

17、reak; 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

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

19、ist is: "); for(plist = T.begin(); plist != T.end(); plist+) printf("%d ",*plist); printf("n"); break; case 0: return 1; 解法三：（數(shù)組）#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("

20、;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值是否合法，請(qǐng)?zhí)?/p>

21、空 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值是否合法，請(qǐng)?zhí)羁?else e=Ti; for(int j=i; j<k; j+) Tj=Tj+1; k-; printf("Th

22、e 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 合并順序表時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):5339 通過(guò)次數(shù)

23、:2251 題型: 編程題 語(yǔ)言: 無(wú)限制Description編寫(xiě)算法，將兩個(gè)非遞減有序順序表A和B合并成一個(gè)新的非遞減有序順序表C。本題不提供代碼，請(qǐng)同學(xué)們獨(dú)立完成，所需子函數(shù)參考前面完成的內(nèi)容。 輸入格式第一行：順序表A的元素個(gè)數(shù)第二行：順序表A的各元素（非遞減），用空格分開(kāi)第三行：順序表B的元素個(gè)數(shù)第四行：順序表B的各元素（非遞減），用空格分開(kāi)輸出格式第一行：順序表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

24、4 5 6 7 8 9 10 作者yqm 解法一：（正規(guī)解法）#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

25、&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; / 請(qǐng)?zhí)羁?else for(i=0; i<L.length-1; i+) printf("%d ",L.elemi);

26、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.lengt

27、h; 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

28、+;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&

29、lt;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; in

30、t 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); p

31、rintf("List C:"); load(T);解法三：（數(shù)組）#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; / 請(qǐng)?zhí)羁?else for(i=0; i<n; i+) printf

32、("%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,Y

33、100; 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("

34、;List C:"); Load_Sq(Y,a+b);8578 順序表逆置時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):3660 通過(guò)次數(shù):2149 題型: 編程題 語(yǔ)言: 無(wú)限制Description設(shè)有一順序表A=（a0,a1,., ai,.an-1)，其逆順序表定義為A'=( an-1,., ai,.,a1, a0)。設(shè)計(jì)一個(gè)算法，將順序表逆置，要求順序表仍占用原順序表的空間。本題不提供代碼，請(qǐng)同學(xué)們獨(dú)立完成，所需子函數(shù)參考前面完成的內(nèi)容。 輸入格式第一行：輸入順序表的元素個(gè)數(shù)第二行：輸入順序表的各元素，用空格分開(kāi)輸出格式第一行：逆置前的順序表元素列表第二行：逆

35、置后的順序表元素列表輸入樣例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 解法一：（正規(guī)解法）#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

36、length;int listsize;SqList;int InitList_Sq(SqList &L,int n)/ 算法2.3，構(gòu)造一個(gè)空的線(xiàn)性表L，該線(xiàn)性表預(yù)定義大小為L(zhǎng)IST_INIT_SIZE/ 請(qǐng)補(bǔ)全代碼 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

37、 &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);

38、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 !=

39、 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:");l

40、oad(T);解法三：（數(shù)組）#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=Ln-i-1; Ln-i-1=t; return 1;int main()int T100,n;scanf("%d",&n)

41、;for(int i=0;i<n;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 鏈?zhǔn)骄€(xiàn)性表的基本操作時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):5567 通過(guò)次數(shù):2176 題型: 編程題 語(yǔ)言: 無(wú)限制Description編寫(xiě)算法，創(chuàng)建一個(gè)含有n個(gè)元素的帶頭結(jié)點(diǎn)的單鏈表L并實(shí)現(xiàn)插入、刪除、遍歷操作。本題目提供部分代碼，請(qǐng)補(bǔ)全內(nèi)容。 #

42、include<stdio.h>#include<malloc.h>#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)/ 創(chuàng)建含有n個(gè)元素的單鏈表 LinkList p,q; int i; ElemType e; L = (LinkList)malloc(sizeof(LNode); L->next = NULL

43、; / 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 q = (LinkList)malloc(sizeof(LNode); q = L; for (i=0; i<n; i+) scanf("%d", &e); p = (LinkList)malloc(sizeof(LNode); / 生成新結(jié)點(diǎn) / 請(qǐng)補(bǔ)全代碼 return OK;int LoadLink_L(LinkList &L)/ 單鏈表遍歷 LinkList p = L->next; if(_)printf("The List is empty!"); / 請(qǐng)?zhí)羁?else prin

44、tf("The LinkList is:"); while(_) / 請(qǐng)?zhí)羁?printf("%d ",p->data); _ / 請(qǐng)?zhí)羁?printf("n"); return OK;int LinkInsert_L(LinkList &L,int i,ElemType e)/ 算法2.9/ 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中第i個(gè)位置之前插入元素e/ 請(qǐng)補(bǔ)全代碼int LinkDelete_L(LinkList &L,int i, ElemType &e)/ 算法2.10/ 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中，刪除第

45、i個(gè)元素，并用e返回其值/ 請(qǐng)補(bǔ)全代碼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(_) / 判斷鏈表是否創(chuàng)建成功，請(qǐng)?zhí)羁?printf("A Link List Has Created.n"

46、;); 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值是否合法，請(qǐng)?zhí)羁?else printf("The Element %d i

47、s Successfully Inserted!n", x); break;case 2: scanf("%d",&i); if(_) printf("Delete Error!n"); / 判斷i值是否合法，請(qǐng)?zhí)羁?else printf("The Element %d is Successfully Deleted!n", e); break;case 3: LoadLink_L(T); break;case 0: return 1;輸入格式測(cè)試樣例格式說(shuō)明：根據(jù)菜單操作：1、輸入1，表示要實(shí)現(xiàn)插入操作，緊跟著要

48、輸入插入的位置和元素，用空格分開(kāi)2、輸入2，表示要實(shí)現(xiàn)刪除操作，緊跟著要輸入刪除的位置3、輸入3，表示要輸出順序表的所有元素4、輸入0，表示程序結(jié)束輸入樣例33 6 9314 122130輸出樣例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 element2:Delete element3:Load all elements0:ExitPlease choose:The LinkList is:3 6 9 1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 12 is Successfully Inserted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 3 is Successfully Deleted!1:Insert element2:Delete e