数据结构实验上机题答案.doc

《数据结构实验上机题答案.doc》由会员分享，可在线阅读，更多相关《数据结构实验上机题答案.doc（182页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、实验一#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef structint *elem,length,listsize;SqList;int InitList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int Loa

2、d_Sq(SqList &L)int i;if(L.length=0)printf(The List is empty!);elseprintf(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)if(iL.length+1)return ERROR;ElemType *newbase,*q,*p;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.

3、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)ElemType *q,*p;if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;p+

4、)*(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(In

5、sert Error!n);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);elseprintf(The Element %d is Successfully Deleted!n,e);break;case 3: Load_Sq(T);break;case 0: return 1;2#include#include#define OK 1#define ERROR 0#define

6、LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef structint *elem,length,listsize;SqList;int InitList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int Load_Sq(SqList &L)int i;for(i=0;iL.length;i+)printf(%d ,L

7、.elemi);printf(n);return OK;int ListLength(SqList L)return L.length;int GetElem(SqList L,int i,ElemType &e)e=L.elemi-1;return OK;int ListInsert_Sq(SqList &L,int i,int e)if(iL.length+1)return ERROR;ElemType *p,*q,*newbase;if(L.listsize=q;p-)*(p+1)=*p;*q=e;L.length+;return OK;void MergeList(SqList La,

8、SqList Lb,SqList &Lc)int i,j,k,La_len,Lb_len,ai,bj;i=j=1;k=0;InitList_Sq(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert_Sq(Lc,+k,ai);i+;elseListInsert_Sq(Lc,+k,bj);j+;while(i=La_len)GetElem(La,i+,ai);ListInsert_Sq(Lc,+k

9、,ai);while(j=Lb_len)GetElem(Lb,j+,bj);ListInsert_Sq(Lc,+k,bj);Load_Sq(Lc);int main()int an,bn,i,e;SqList La,Lb,Lc;InitList_Sq(La);scanf(%d,&an);for(i=1;i=an;i+)scanf(%d,&e);ListInsert_Sq(La,i,e);printf(List A:);Load_Sq(La);InitList_Sq(Lb);scanf(%d,&bn);for(i=1;i=an;i+)scanf(%d,&e);ListInsert_Sq(Lb,i

10、,e);printf(List B:);Load_Sq(Lb);printf(List C:);MergeList(La,Lb,Lc);return 0;3#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType int typedef structint *elem,length,listsize;SqList;int InitList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_

11、SIZE*sizeof(ElemType);if(!L.elem)printf(NO1);return ERROR;L.length=0;L.listsize=LIST_INIT_SIZE;return OK;int Load_Sq(SqList &L)int i;if(!L.length)printf(This List is empty!n);return ERROR;elsefor(i=0;i=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newba

12、se)printf(NO2);return ERROR;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 swap(SqList &L,int n)int i,j,temp;for(i=0,j=n-1;ji;i+,j-)temp=L.elemi;L.elemi=L.elemj;L.elemj=temp;return OK;int main()SqList T;int n,i;ElemType

13、 x;scanf(%d,&n);InitList_Sq(T);for(i=1;in+1;i+)scanf(%d,&x);ListInsert_Sq(T,i,x);printf(The List is:);Load_Sq(T);swap(T,n);printf(The turned List is:);Load_Sq(T);return 0;4#include#include#define ERROR 0#define OK 1#define ElemType int typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;

14、int CreateLink_L(LinkList &L,int 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=q-next;return OK;int LoadLink_L(LinkList &L)LinkList p=L-next;if(!p)printf(The List is empty!);elseprintf(The Li

15、nkList is:);while(p)printf(%d ,p-data);p=p-next;printf(n);return OK;int LinkInsert_L(LinkList &L,int i,ElemType e)LNode *p=L,*s;int j=0;while(p&jnext;j+;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;int LinkDelete_L(LinkList &L,int i,ElemType &e)L

16、Node *p=L,*q;int j=0;while(p-next&jnext;j+;if(!(p-next)|jnext;p-next=q-next;e=q-data;free(q);return OK;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(CreateLink_L(T,n)printf(A Li

17、nk 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(!LinkInsert_L(T,i,x)printf(Insert Error!n);elseprintf(The Element %d is Successfully Inserted!n,x);break;case 2:scanf(%d

18、,&i);if(!LinkDelete_L(T,i,e)printf(Delete Error!n);elseprintf(The Element %d is Successfully Deleted!n,e);break;case 3:LoadLink_L(T);break;case 0:return 1;5#include#include#define ERROR 0#define OK 1#define ElemType inttypedef struct LNodeint data;struct LNode *next;LNode,*LinkList;int CreateLink_L(

19、LinkList &L,int 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=q-next;return OK;int LoadLink_L(LinkList &L)LinkList p=L-next;if(!p)printf(The List is empty!);elsewhile(p)printf(%d ,p-data);p=p

20、-next;printf(n);return OK;void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)LinkList pa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);int main()LinkList La,Lb,Lc;int n;scanf(%d,&n);CreateLin

21、k_L(La,n);printf(List A:);LoadLink_L(La);scanf(%d,&n);CreateLink_L(Lb,n);printf(List B:);LoadLink_L(Lb);MergeList_L(La,Lb,Lc);printf(List C:);LoadLink_L(Lc);return 0;6#include#include#define OK 1#define ERROR 0#define ElemType int typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;int C

22、reateLink_L(LinkList &L,int 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=q-next;return OK;int LoadLink_L(LinkList &L)LinkList p=L-next;if(!p)printf(The List is Empty!);elsewhile(p)printf(%d

23、,p-data);p=p-next;printf(n);return OK;int inversion(LinkList &L)LinkList p=L-next,q;L-next=NULL;while(p)q=p-next;p-next=L-next;L-next=p;p=q;return OK;int main()LinkList T;int n;scanf(%d,&n);CreateLink_L(T,n);printf(The List is:);LoadLink_L(T);inversion(T);printf(The turned List is:);LoadLink_L(T);re

24、turn 0;实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二1#include#include#include#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef int Status;struct SqStackSElemType *base;SElemType *top;int stacksize;Status InitStack(SqStack &S)S.base=(SElemType*)mal

25、loc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(S.base)return ERROR;S.top=S.base+S.stack

26、size;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;Status GetTop(SqStack S,SElemType &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;int StackLength(SqStack S)int i=0;while(S.top!=S.base)i+;S.top-;return i;S

27、tatus StackTraverse(SqStack S)SElemType *p=(SElemType*)malloc(sizeof(SElemType);p=S.top;if(S.top=S.base)printf(The Stack is Empty!);elseprintf(The Stack is:);p-;S.base-;while(p!=S.base)printf(% d,*p);p-;printf(n);return OK;int main()int a;SqStack S;SElemType x,e;if(InitStack(S)printf(A Stack Has Cre

28、ated.n);while(1)printf(1:Pushn2:Popn3:Get the Topn4:Return the Length of the Stackn5:Load the Stackn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1:scanf(%d,&x);if(!Push(S,x)printf(Push Error!n);elseprintf(The Element %d is Successfully Pushed!n,x);break;case 2:if(!Pop(S,e) printf(Pop Error!n);

29、elseprintf(The Element %d is Successfully Poped!n,e);break;case 3:if(!GetTop(S,e) printf(GetTop Error!n);elseprintf(The Top Element is %d!n,e);break;case 4:printf(The Length of the Stack is %d!n,StackLength(S);break;case 5:StackTraverse(S);break;case 0:return 1;2#include#include#define ERROR 0#defin

30、e OK 1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef int Status;struct SqStackSElemType *base;SElemType *top;int stacksize;Status InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK

31、_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)if(S

32、.top=S.base)return ERROR;e=*-S.top;return OK;Status StackEmpty(SqStack &S)if(S.top=S.base)return 0;elsereturn 1;int main()int N,e;SqStack S;InitStack(S);scanf(%d,&N);while(N)Push(S,N%8);N=N/8;while(StackEmpty(S)Pop(S,e);printf(%d,e);return 0;3typedef char SElemType;#include#include#include#include#d

33、efine OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status;#define STACK_INIT_SIZE 10#define STACKINCREMENT 2struct SqStackSElemType *base;SElemType *top;int stacksize;Status InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return 0;S.top=S.ba

34、se;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;elsereturn FALSE;Status Push(SqStack &S,SElemType e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)return 0;S.top=S.base+S.stacksi

35、ze;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;void check() SqStack s; SElemType ch80,*p,e; if(InitStack(s) gets(ch); p=ch; while(*p) switch(*p) case (: case :Push(s,*p+); break; case ): case :if(!StackEmpty(s) Pop(s,e); if(*p=)&e!=(|*p=&e!=) printf(isnt matched pairsn); return ; else p+ ;