華農(nóng)數(shù)據(jù)結構上機實驗答案

數(shù)據(jù)結構上機答案1.1 順序線性表的基本操作#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,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;i<L.length;i+)printf("% d",L.elemi);printf("n");return OK;int ListInsert_Sq(SqList &L,int i,int e)if(i<1|i>L.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(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");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<stdio.h>#include<malloc.h>#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;i<L.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(i<1|i>L.length+1)return ERROR;ElemType *p,*q,*newbase;if(L.listsize<=L.length)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;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;1.3 順序表逆置#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,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.length;i+)printf("%d ",L.elemi);printf("n");return OK;int ListInsert_Sq(SqList &L,int i,int e)ElemType *newbase,*p,*q;if(L.length>=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 s &L,int n)int i,j,temp;for(i=0,j=n-1;j>i;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;i<n+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<stdio.h>#include<malloc.h>#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;i<n;i+)scanf("%d",&e);p=(LinkList)malloc(sizeof(LNode);p->data=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&&j<i-1)p=p->next;j+;if(!p|j>i-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&&j<i-1)p=p->next;j+;if(!(p->next)|j<i-1)return ERROR;q=p->next;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;1.5 合并鏈表#include<stdio.h>#include<malloc.h>#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;i<n;i+)scanf("%d",&e);p=(LinkList)malloc(sizeof(LNode);p->data=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->data<=pb->data)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;1.6 線性鏈表逆置#include<stdio.h>#include<malloc.h>#define OK 1#define ERROR 0#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;i<n;i+)scanf("%d",&e);p=(LinkList)malloc(sizeof(LNode);p->data=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;2.1 順序棧的基本操作#include<stdio.h>#include<malloc.h>#include<stdlib.h>#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(SElem Type);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;2.2 循環(huán)隊列的基本操作#include<stdio.h>#include<malloc.h>#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;Status 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.front=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 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("The 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 %d!n",QueueLength(S); break;case 5: QueueTraverse(S);break;case 0: return 1;2.3 棧的應用進制轉換#include<stdio.h>#include<malloc.h>#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(SElem Type);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;2.4 括號匹配檢驗typedef char SElemType;#include<malloc.h>#include<stdio.h>#include<math.h>#include<process.h>#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(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;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 ;elsep+ ;break;elseprintf("lack of left parenthesisn");return ;default: p+;if(StackEmpty(s)printf("matchingn");elseprintf("lack of right parenthesisn");int main()check();return 1;2.5 行編輯程序typedef char SElemType;#include<malloc.h>#include<stdio.h>#include<math.h>#include<process.h>#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(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;Status StackTraverse(SqStack S,Status(*visit)(SElemType)while(S.top>S.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