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

华农数据结构上机实验答案数据结构上机答案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 struct{int *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!");else{printf("The List is:");for(i=0;i<L.length;i++)printf("% d",L.elem[i]);}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)*size of(ElemType));L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.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.elem[i-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 element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease 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 struct{int *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.elem[i]);printf("\n");return OK;}int ListLength(SqList L){return L.length;}int GetElem(SqList L,int i,ElemType &e){e=L.elem[i-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)*size of(ElemType));L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.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++;}else{ListInsert_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 struct{int *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;}else{for(i=0;i<L.length;i++)printf("%d ",L.elem[i]);}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)*size of(ElemType));if(!newbase){printf("NO2");return ERROR;}L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.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;j>i;i++,j--){temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=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);swap(T,n);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 LNode{int 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!");else{printf("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 element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease 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 LNode{int 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!");else{while(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;}else{pc->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 LNode{int 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 SqStack{SElemType *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)*si zeof(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!");else{printf("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:Push\n2:Pop\n3:Get the Top\n4:Return the Length of the Stack\n5:Load the Stack\n0:Exit\nPlease 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循环队列的基本操作#include<stdio.h>#include<malloc.h>#define OK 1#define ERROR 0typedef int Status;typedef int QElemType;#define MAXQSIZE 100typedef struct{QElemType *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.base[Q.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.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}Status GetHead(SqQueue Q,QElemType &e){if(Q.front==Q.rear)return ERROR;e=Q.base[Q.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!");else{printf("The Queue is:");while(i!=Q.rear){printf("% d",Q.base[i]);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 Queue\n5:Load the Queue\n0:Exit\nPlease 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 SqStack{SElemType *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)*si zeof(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;}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 SqStack{SElemType *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)*si zeof(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 ch[80],*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("isn't matched pairs\n");return ;}else{p++ ;break;}}else{printf("lack of left parenthesis\n");return ;}default: p++;}if(StackEmpty(s))printf("matching\n");elseprintf("lack of right parenthesis\n");}}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 SqStack{SElemType *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)*si zeof(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.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,visit);ClearStack(s);}DestroyStack(s);}int main(){LineEdit();return 1;}2.6表达式求值#include<stdio.h>#include<malloc.h>#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;struct SqStack_T{char *base;char *top;int stacksize;};struct SqStack_N{int *base;int *top;int stacksize;};Status InitStack_T(SqStack_T &S){S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}Status InitStack_N(SqStack_N &S){S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}int Push_T(SqStack_T &S,char e){if(S.top-S.base>=S.stacksize){S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof( char));if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}int Push_N(SqStack_N &S,int e){if(S.top-S.base>=S.stacksize){S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(i nt));if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}int Pop_T(SqStack_T &S,char &e){if(S.top==S.base)return ERROR;e=*--S.top;return OK;}int Pop_N(SqStack_N &S,int &e){if(S.top==S.base)return ERROR;e=*--S.top;return OK;}char GetTop_T(SqStack_T S){char e;if(S.top==S.base)return ERROR;e=*(S.top-1);return e;}int GetTop_N(SqStack_N S){int e;if(S.top==S.base)return ERROR;e=*(S.top-1);return e;}char Precede(char theta1,char theta2) {int a,b;switch(theta1){case '+': a=2; break;case '-': a=2; break;case '*': a=4; break;case '/': a=4; break;case '(': a=0; break;case ')': a=6; break;case '=': a=-1; break;}switch(theta2){case '+': b=1; break;case '-': b=1; break;case '*': b=3; break;case '/': b=3; break;case '(': b=6; break;case ')': b=0; break;case '=': b=-1; break;}if(a<b)return '<';elseif(a==b)return '=';elsereturn '>';}char precede(char e,char c){if(c=='+'||c=='-'){if(e=='+'||e=='-'||e==')'||e=='=') return '>';elsereturn '<';}if(c=='*'||'/'){if(e=='(')return '<';elsereturn '>';}if(c=='('){if(e==')')return '=';elsereturn '<';}if(c==')')return '>';if(c=='='){if(e=='=')return '=';elsereturn '<';}}int In(char c){if(c>='0'&&c<='9')return 1;elsereturn 0;}int Operate(int a,char theta,int b){int s;switch(theta){case '+': s=a+b; break;case '-': s=a-b; break;case '*': s=a*b; break;case '/':if(b!=0)s=a/b;elseprintf("Input error");break;}return s;}int main(){int k=0,m,y,a,b;SqStack_T OPTR;SqStack_N OPND;char c,theta;InitStack_T(OPTR); Push_T(OPTR,'=');InitStack_N(OPND); c=getchar();while(c!='='||GetTop_T(OPTR)!='='){if(In(c)){m=c-'0';if(k==1){Pop_N(OPND,y);y=m+y*10;Push_N(OPND,y);k=1;c=getchar();}else{y=m;Push_N(OPND,y);c=getchar();k=1;}}else{k=0;switch(Precede(GetTop_T(OPTR),c)){case '<': Push_T(OPTR,c); c=getchar(); break;case '=': Pop_T(OPTR,c); c=getchar(); break;case '>':Pop_T(OPTR,theta);Pop_N(OPND,b);Pop_N(OPND,a);Push_N(OPND,Operate(a,theta,b));break;}}}printf("%d",GetTop_N(OPND));return 0;}2.7队列的应用——银行客户平均等待时间#include<malloc.h>#include<stdio.h>#define OK 1#define ERROR 0typedef int Status;typedef int QElemType;#define MAXQSIZE 100typedef struct{QElemType *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.base[Q.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.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}Status GetHead(SqQueue Q,QElemType &e){if(Q.rear==Q.front)return ERROR;e=Q.base[Q.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.rear==Q.front)printf("The Queue is Empty!");else{printf("The Queu is:");while(i!=Q.rear){printf("%d",Q.base[i]);i=(i+1)%MAXQSIZE;}}printf("\n");return OK;}int main(){int i,a;SqQueue S;int p,q,e,r;float t,s=0;InitQueue(S);scanf("%d",&a);getchar();for(i=1;i<=a*2;i++){scanf("%d",&e);getchar();EnQueue(S,e);}p=S.base[S.front];while(S.rear>S.front){q=p+S.base[S.front+1];DeQueue(S,e);DeQueue(S,e);if(S.front==S.rear)break;r=q-S.base[S.front];if(r<0){r=0;p=S.base[S.front];continue;}s=s+r;p=q;}t=s/a;printf("%.2f\n",t);return OK;}3.1计算next值#include<stdio.h>#include<stdlib.h>#include<iostream.h>#define MAXSTRLEN 255typedef unsigned char SString[MAXSTRLEN+1];void get_next(SString T,int next[]){int i=1,j=0;next[1]=0;while(i<T[0]){if(j==0||T[i]==T[j]){i++;j++;next[i]=j;}elsej=next[j];}}。

实验报告二线性表华南农业大学信息（软件）学院《数据结构（JA V A）》综合性、设计性实验成绩单开设时间：2017学年第二学期一，实验目的：（1）理解线性表的逻辑结构、两种存储结构和数据操作，熟练运用JAVA语言实现线性表的基本操作，分析各种操作算法特点和时间复杂度。

（2）掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。

二，实验内容：1、设计一个有序顺序表（元素已排序，递增或递减），实现插入、删除等操作，元素插入位置由其值决定。

实现：（1）升序排序顺序表类名为：SortedSeqList，存成SortedSeqList.java文件；（2）另外编写SortedSeqList_ex.java文件来演示调用排序顺序表public class SortedSeqList {private int MAX_SIZE = 10;private int[] ary = new int[MAX_SIZE];private int length = 0;public SortedSeqList(int[] array) {if (array == null || array.length == 0) {this.length = 0;} else {ary = array;length = array.length;}}public void clear() {length = 0;}public boolean isEmpty() {return length == 0;}public void delete(int index) throws Exception {if (length == 0) {throw new Exception("No elment to delete");}int newAry[] = new int[ary.length - 1];for (int i = 0, j = 0; i < ary.length; i++) {if (i == index) {continue;} else {newAry[j++] = ary[i];}}ary = newAry;length--;}public int insert(int value) throws Exception {if (length == MAX_SIZE) {throw new Exception("List is full, can't insert more");}int[] newAry = new int[length + 1];int i = 0, j = 0;for (; i < ary.length; i++, j++) {if (ary[i] >= value) {newAry[j] = value;break;} else {newAry[j] = ary[i];}}while (i < ary.length) {newAry[++j] = ary[i];i++;}ary = newAry;length++;return value;}public void display() {System.out.println("\nList now is: ");for (int i = 0; i < ary.length; i++) {System.out.print(ary[i] + "\t");}}}（2）SortedSeqList_ex.java文件来演示调用排序顺序表public class SortedSeqList_ex {public static void main(String[] args) throws Exception {int[] ary = {1, 2, 3, 5, 7};SortedSeqList list = new SortedSeqList(ary);list.display();list.insert(4);list.display();list.delete(2);list.display();}}（3）实验结果2、在SinglyLinkedList类中增加下列成员方法。

数据结构实验报告答案数据结构实验报告答案引言：数据结构是计算机科学中的重要概念，它涉及组织和管理数据的方法和技术。

在本次实验中，我们将研究和实践几种常见的数据结构，包括数组、链表、栈和队列。

通过这些实验，我们将深入理解数据结构的原理和应用。

一、数组数组是一种线性数据结构，它由一系列相同类型的元素组成。

数组的特点是可以通过索引来访问和修改元素，具有随机访问的能力。

在本次实验中，我们将实现一个简单的数组类，并进行一些基本操作，如插入、删除和查找。

首先，我们定义一个数组类，包含以下成员变量和方法：- size：数组的大小- elements：存储元素的数组- insert(index, element)：在指定位置插入元素- remove(index)：删除指定位置的元素- get(index)：获取指定位置的元素- search(element)：查找元素在数组中的位置通过实现上述方法，我们可以对数组进行各种操作。

例如，我们可以在数组的末尾插入一个元素，然后在指定位置删除一个元素。

我们还可以通过元素的值来查找其在数组中的位置。

二、链表链表是另一种常见的线性数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

链表的特点是插入和删除操作的效率较高，但随机访问的效率较低。

在本次实验中，我们将实现一个简单的单向链表，并进行一些基本操作。

首先，我们定义一个节点类，包含以下成员变量和方法：- data：节点的数据元素- next：指向下一个节点的指针然后，我们定义一个链表类，包含以下成员变量和方法：- head：链表的头节点- insert(element)：在链表的末尾插入一个节点- remove(element)：删除链表中指定的节点- search(element)：查找链表中指定元素的节点通过实现上述方法，我们可以对链表进行各种操作。

例如，我们可以在链表的末尾插入一个节点，然后删除链表中指定的节点。