华农数据结构上机实验答案数据结构上机答案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];}}。