华南农业大学数据结构上机实验答案.doc

华南农业大学实验一实验一实验一实验一实验一实验一实验一实验一实验一实验一实验一实验一实验一111111111111111111111111111111111111111111111111111111111111111111111111111111#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 Load_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.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+)*(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);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;222222222222222222222222222222222222222222222222222222222222222222222222222222#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 Load_Sq(SqList &L)int i;for(i=0;iL.length;i+)printf(%d ,L.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,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,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,e);printf(List B:);Load_Sq(Lb);printf(List C:);MergeList(La,Lb,Lc);return 0;333333333333333333333333333333333333333333333333333333333333333333333333333333#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_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(!newbase)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 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;444444444444444444444444444444444444444444444444444444444444444444444444444444#include#include#define ERROR 0#define OK 1#define ElemType int typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;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 LinkList 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)LNode *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 Link 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,&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;555555555555555555555555555555555555555555555555555555555555555555555555555555#include#include#define ERROR 0#define OK 1#define ElemType inttypedef struct LNodeint data;struct LNode *next;LNode,*LinkList;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!);elsewhile(p)printf(%d ,p-data);p=p-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);CreateLink_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;666666666666666666666666666666666666666666666666666666666666666666666666666666#include#include#define OK 1#define ERROR 0#define ElemType int typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;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!);elsewhile(p)printf(%d ,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);return 0;实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二实验二111111111111111111111111111111111111111111111111111111111111111111111111111111#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*)malloc(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.stacksize;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;Status 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 Created.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);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;222222222222222222222222222222222222222222222222222222222222222222222222222222#include#include#define ERROR 0#define 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_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.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;333333333333333333333333333333333333333333333333333333333333333333333333333333typedef char SElemType;#include#include#include#include#define 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.base;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.stacksize;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+ ; break; else printf(lack of left parenthesisn); return ; default: p+; if(StackEmpty(s) printf(matchingn); else printf(lack of right parenthesisn); int main()check();return 1;444444444444444444444444444444444444444444444444444444444444444444444444444444typedef char SElemType;#include#include#include#include#define 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;FILE *fp;Status InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)return 0;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;elsereturn FALSE;Status ClearStack(SqStack &S)S.top=S.base;return OK;Status DestroyStack(SqStack &S)free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;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 0;S.top=S.base+S.stacksize;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 StackTraverse(SqStack S,Status(*visit)(SElemType)while(S.topS.base)visit(*S.base+);printf(n);return OK;Status visit(SElemType c)printf(%c,c);return OK;void LineEdit()SqStack s;char ch,c;int n,i;InitStack(s);scanf(%d,&n);ch=getchar();for(i=1;i=n;i+)ch=getchar();while(ch!=n)switch(ch)case #: Pop(s,c);break;case : ClearStack(s);break;default:Push(s,ch);ch=getchar();StackTraverse(s,visit);ClearStack(s);DestroyStack(s);int main()LineEdit();return 1;555555555555555555555555555555555555555555555555555555555555555555555555555555#include#in