《華農數據結構上機實驗答案》由會員分享，可在線閱讀，更多相關《華農數據結構上機實驗答案（91頁珍藏版）》請在裝配圖網上搜索。
1、數據結構上機答案1.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_SI
2、ZE;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
3、*)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.le
4、ngth-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(!ListInser
5、t_Sq(T,i,x)printf(Insert Error!n);elseprintf(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;1.2 合并順序表#include#include#defin
6、e 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
7、(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+;retur
8、n 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
9、(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+)s
10、canf(%d,&e);ListInsert_Sq(Lb,i,e);printf(List B:);Load_Sq(Lb);printf(List C:);MergeList(La,Lb,Lc);return 0;1.3 順序表逆置#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 &
11、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+LIS
12、TINCREMENT)*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 s &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 mai
13、n()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);s);printf(The turned List is:);Load_Sq(T);return 0;1.4 鏈式線性表的基本操作#include#include#define ERROR 0#define OK 1#define ElemType inttypedef struct LNodeint data;st
14、ruct 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
15、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_
16、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
17、);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 In
18、serted!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;1.5 合并鏈表#include#include#define ERROR 0#define OK 1#define ElemType inttypedef struct LNodeint data;struct LNo
19、de *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
20、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()Link
21、List 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;1.6 線性鏈表逆置#include#include#define OK 1#define ERROR 0#define ElemType inttypedef struct LNod
22、eint 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
23、)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);inversi
24、on(T);printf(The turned List is:);LoadLink_L(T);return 0;2.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)
25、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(SElem Type);if(S.base)return ER
26、ROR;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.b
27、ase)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
28、(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
29、(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;2.2 循環(huán)隊列的基本操
30、作#include#include#define OK 1#define ERROR 0typedef int Status;typedef int QElemType;#define MAXQSIZE 100typedef structQElemType *base;int front;int rear;SqQueue;Status InitQueue(SqQueue &Q)Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType); if(!Q.base)return ERROR;Q.front=Q.rear=0;return OK;Statu
31、s EnQueue(SqQueue &Q,QElemType e)if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,QElemType &e)if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;Status GetHead(SqQueue Q,QElemType &e)if(Q.fron
32、t=Q.rear)return ERROR;e=Q.baseQ.front;return OK;int QueueLength(SqQueue Q)return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status QueueTraverse(SqQueue Q)int i;i=Q.front;if(Q.front=Q.rear)printf(The Queue is Empty!);elseprintf(The Queue is:);while(i!=Q.rear)printf(% d,Q.basei);i=i+1;printf(n);return OK;int
33、 main()int a;SqQueue S;QElemType x,e;if(InitQueue(S)printf(A Queue Has Created.n);while(1)printf(1:Enter n2:Delete n3:Get the Front n4:Return the Length of the Queuen5:Load the Queuen0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d,&x);if(!EnQueue(S,x)printf(Enter Error!n);elseprintf(T
34、he Element %d is Successfully Entered!n,x); break;case 2: if(!DeQueue(S,e)printf(Delete Error!n);elseprintf(The Element %d is Successfully Deleted!n,e); break;case 3: if(!GetHead(S,e)printf(Get Head Error!n);elseprintf(The Head of the Queue is %d!n,e);break;case 4: printf(The Length of the Queue is
35、%d!n,QueueLength(S); break;case 5: QueueTraverse(S);break;case 0: return 1;2.3 棧的應用進制轉換#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(S
36、qStack &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(SElem Type);if(S.base
37、)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)
38、Push(S,N%8);N=N/8;while(StackEmpty(S)Pop(S,e);printf(%d,e);return 0;2.4 括號匹配檢驗typedef 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 *t
39、op;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
40、=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElem Type);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;SElemT
41、ype 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 ;elsep+ ;break;elseprintf(lack of left parenthesisn);return ;default: p+;if(StackEmpty(s)printf(matchingn);elsep
42、rintf(lack of right parenthesisn);int main()check();return 1;2.5 行編輯程序typedef 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 s
43、tacksize;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
44、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(SElem Type);if(!S.base)return 0;S.top=S.base+S.stacksize;S.stacksize+=STA
45、CKINCREMENT;*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,vi
華農數據結構上機實驗答案
