华农数据结构上机实验答案

华农数据结构上机实验答案

数据结构上机答案

1.1顺序线性表的基本操作

#include<stdio.h>

#include<malloc.h>

ftdefineOK1

#defineERROR0

#defineLIST_INIT_SIZE100

ttdefineLISTINCREMENT10

#defineElemTypeint

typedefstruct

(

int*elem,length,listsize;

)SqList;

intInitList_Sq(SqList&L)

(

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

L.length=0;

Llistsize=LIST_INIT_SIZE;

returnOK;

)

intLoad_Sq(SqList&L)

(

inti;

if(Llength=0)

printf(*TheListisempty!");

else

f

printf("TheListis:");

for(i=0;i<L.length;i++)

printf("%d*,L.elem[i]);

}

printf(*\n*);

returnOK;

}

intListInsert_Sq(SqList&L,inti,inte)

(

if(i<l||i>Llength+1)

returnERROR;

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-l]);

for(p=&(L.elem[Llength-1]);p>=q;-p)

*(p+l)=*p;

*q=e;

++L.length;

returnOK;

)

intListDelete_Sq(SqList&L,inti,int&e)

(

ElemType*q,*p;

if(i<l||i>L.length)

returnERROR;

p=&(LelemLi-U);

e=*p;

q=L.elem+L.length-1;

for(-H-p;p<=q;p++)

*(p-l)=*p;

L.length—;

returnOK;

)

intmainO

(

SqListT;

inta,i;

ElemTypee,x;

if(InitList_Sq(T))

("“

printf(*ASequenceListHasCreated.\n*);

)

while(1)

(

printf(*l:Insertelement\n2:Deleteelement\n3:Loadall

elements\nO:Exit\nPleasechoose:\n");

scanf&a);

switch(a)

case1:scanf("%d%d”,&i,&x);

if(!ListInsert_Sq(T,i,x))

printf(*InsertError!\n*);

else

printf(*TheElement%disSuccessfullyInserted!\n*,x);

break;

case2:scanf&i);

if(!ListDelete_Sq(T,i,e))

printf(*DeleteEiror!\n");

else

printf("TheElement%disSuccessfullyDeleted!\n*,e);

break;

case3:Load_Sq(T);

break;

case0:return1;

)

}

)

1.2合并顺序表

#include<stdio.h>

#include<malloc.h>

#defineOK1

#defineERROR0

#defineLIST_INIT_SIZE100

ftdefineLISTINCREMENT10

#defineElemTypeint

typedefstruct

(

int*elem,length,listsize;

}SqList;

intInitList_Sq(SqList&L)

(

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

Llength=0;

Llistsize=LIST_INIT_SIZE;

returnOK;

}

intLoad_Sq(SqList&L)

inti;

for(i=0：i<L.length:1++)

printf("%dL.elem[i]);

printf('\n");

returnOK;

)

intListLength(SqListL)

(

returnL.length;

)

intGetElem(SqListL,inti,ElemType&e)

(

e=L.elem[i-l];

returnOK;

)

intListInsert_Sq(SqList&L,inti,inte)

(

if(i<l||i>L.length+1)

returnERROR;

ElemType*p,*q,*newbase;

if(L.listsize<=L.length)

(

newbase=(ElemType*)realloc(L.elem,(Llistsize+LISTINCREMENT)*size

of(ElemType));

L.elem=newbase;

L.listsize+=LISTINCREMENT;

)

q=&(L.elem[i-l]);

for(p=&(L.elem[Llength-1]);p>=q;p­)

*(p+l)=*p;

*q=e；

L.length++;

returnOK;

)

voidMergeList(SqListLa,SqListLb,SqList&Lc)

(

inti,j,k,La_len,Lb_len,ai,bj;

i=j=l；

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」en)

{

GetElem(Lb,j++,bj);

ListInsert_Sq(Lc,++k,bj);

)

Load_Sq(Lc);

)

intmainO

(

intan,bn,i,e;

SqListLa,Lb,Lc;

InitList_Sq(La);

scanf&an);

for(i=l;i<=an;i++)

(

scanffee);

ListInsert_Sq(La,i,e);

)

printfCListA:*);

Load_Sq(La);

InitList_Sq(Lb);

scanf("%d”,&bn):

for(i=l;i<=an;i++)

scanf("象T,fee);

ListInsert_Sq(Lb,i,e);

)

printf(*ListB:");

Load_Sq(Lb);

printf(*ListC:");

MergeList(La,Lb,Lc);

return0;

)

1.3顺序表逆置

#include<stdio.h>

#include<malloc.h>

#defineOK1

#defineERROR0

#defineLIST_INIT_SIZE100

#defineLISTINCREMENT10

#defineElemTypeint

typedefstruct

(

int*elem,length,listsize;

)SqList;

intInitList_Sq(SqList&L)

(

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)):

if(!L.elem)

(

printf("N01”);

returnERROR;

)

Llength=0：

L.listsize=LIST_INIT_SIZE;

returnOK;

}

intLoad_Sq(SqList&L)

inti;

if(!Llength)

printfCThisListisempty!\n");

returnERROR;

)

else

(

for(i=0;i<L.length;i++)

printf("%d*,Lelem[i]);

)

printf("\n");

returnOK;

)

intListInsert_Sq(SqList&L,inti,inte)

(

ElemType*newbase,*p,*q;

if(L.length>=L.listsize)

(

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*size

of(ElemType));

if(!newbase)

(

printf("N02”);

returnERROR;

)

L.elem=newbase;

L.listsize+=LISTINCREMENT;

)

q=&(L.elemTi-ll):

for(p=&(L.elem[L.length-1]);p>=q;p—)

*(p+l)=*p;

*q=e；

L.length++;

returnOK;

)

intswap(SqList&L,intn)

(

inti,j,te叩；

for(i=0,j=n-l;j>i;iH,j-)

{

temp=L.elem[i];

L.elem[i]=L.elen:[j];

L.elem[j]=temp:

)

returnOK;

)

intmainO

(

SqListT;

intn,i;

ElemTypex;

scanf&n);

InitList_Sq(T);

for(i=l;i<n+l;i++)

(

scanf&x);

ListInsert_Sq(T,i,x);

)

printfCTheListis:*);

Load_Sq(T);

swap(T,n);

printf(""TheturnedListis:");

Load_Sq(T);

return0;

)

1.4链式线性表的基本操作

#include<stdio.h>

#include<malloc.h>

#defineERROR0

ttdftfinAOK1

ftdefineElemTypeint

typedefstructLNode

(

intdata;

structLNode*next;

}LNode,*LinkList;

intCreateLink_L(LinkList&L,intn)

(

LinkListp,q;

inti;

ElemTypee;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL:

q=(LinkList)malloc(sizeof(LNode));

q=L;

for(i=0;i<n;i++)

{

scanf&e);

p=(LinkList)malloc(sizeof(LNode));

p->data=e;

p->next=q->next;

q->next=p;

q=q->next;

}

returnOK;

)

intLoadLink_L(LinkList&L)

(

LinkListp=L->next;

if(!p)

printf(*TheListisempty!*);

else

(

printf(*TheLinkListis:");

while(p)

(

printf("%d”,p->data);

p=p->next;

)

)

printf("\n"):

returnOK;

)

intLinkInsert_L(LinkList&L,inti,ElemTypee)

(

LNode*p=L,*s;

intj=0;

while(p&&j<i­l)

(

p=p>next;

j++；

)

if(!p||j>i-l)

returnERROR;

s=(LinkList)malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

returnOK;

)

intLinkDelete_L(LinkList&L,inti,ElemType&e)

(

LNode*p=L,*q;

intj=0;

while(p->next&&j<i-l)

(

p=p->next;

j++；

}

if(!(p->next)||j<i-l)

returnERROR;

q=p->next;

p->next=q->next;

e=q->data;

free(q);

returnOK;

)

intmainO

(

LinkListT;

inta,n,i;

ElemTypex.e:

printfCPleaseinputtheinitsizeofthelinklist:\n*);

scanf&n);

printf("Pleaseinputthe%delementofthelinklist:\n*,n);

if(CreateLink_L(T,n))

(

printf(*ALinkListHasCreated.\n^);

LoadLink_L(T);

)

while(1)

(

printfCl:Insertelement\n2:Deleteelement\n3:Loadall

elements\nO:Exit\nPleasechoose:\n");

scanf&a);

switch(a)

case1:scanf("%d%d”,&i,&x);

if(!LinkInsert_L(T,i,x))

printf(*InsertError!\n*);

else

printf(*TheElement%disSuccessfullyInserted!\n*,x);

break;

case2:scanf&i);

if(!LinkDelete_L(T,i,e))

printf(*DeleteEiror!\n");

else

printf(*TheElement%disSuccessfullyDeleted!\n*,e);

break;

case3:Lx)adLink_L(T);

break;

case0:return1;

)

}

)

1.5合并链表

#include<stdio.h>

#include<malloc.h>

#defineERROR0

#defineOK1

ftdefineElemTypeint

typedefstructLNode

(

intdata:

structLNode*next;

)LNode,*LinkList;

intCreateLink_L(LinkList&L,intn)

(

LinkListp,q;

inti;

ElemTypee;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;

q=(LinkList)malloc(sizeof(LNode));

q=L；

for(i=0;i<n;i++)

scanf&e):

p=(LinkList)malloc(sizeof(LNode));

p->data=e;

p->next=q->next;

q->next=p;

q=q->next;

}

returnOK;

)

intLoadLink_L(LinkList&L)

(

LinkListp=L->next;

if(1p)

printfC*TheListisempty!*);

else

{

while(p)

{

printf("%d”,p->data);

p=p->next;

)

)

printfC\n*);

returnOK;

)

voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)

(

LinkListpa,pb,pc:

pa=La->next;

pb=Lb->next;

Lc=pc=La;

while(paMpb)

(

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);

)

intmainO

(

LinkListLa,Lb,Lc;

intn;

scanf&n);

CreateLink_L(La,n);

printf("ListA:");

LoadLink_L(La);

scanf&n);

CreateLink_L(Lb,n);

printf("ListB:*);

LoadLink_L(Lb);

MergeList_L(La,Lb,Lc);

printfCListC:");

LoadLink_L(Lc);

return0;

}

1.6线性链表逆置

#include<stdio.h>

#include<malloc.h>

ttdpfinROK1

#defineERROR0

#defineElemTypeint

typedefstructLNode

(

intdata;

structLNode*next;

}LNode,*LinkList;

intCreateLink_L(LinkList&L,intn)

(-

LinkListp,q;

inti;

ElemTypee;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;

q=(LinkList)malloc(sizeof(LNode));

q=L;

for(i=0;i<n;i++)

(

scanffee);

p=(LinkList)malloc(sizeof(LNode));

p->data=e;

p->next=q->next;

q>next=p;

q=q->next;

)

returnOK;

)

intLoadLink_L(LinkList&L)

(

LinkListp=L->next;

if(!p)

printf(^TheListisEmpty!”);

else

while(p)

(

printf("%d”,p->data);

p=p->next;

)

printfC\n*);

returnOK;

)

intinversion(LinkList&L)

(

LinkListp=L->next,q;

L->next=NULL;

while(p)

(

q=p->next;

p->next=L->next;

L>next=p;

p=q;

)

returnOK;

)

intmain()

(

LinkListT;

intn;

scanf("%d",&n);

CreateLink_L(T,n);

printf("TheListis:");

LoadLink_L(T);

inversion(T);

printf("TheturnedListis:");

LoadLink_L(T);

return0;

)

2.1顺序栈的基本操作

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

ftdefineOK1

ftdefineERROR0

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

typedefintSElemType;

typedefintStatus;

structSqStack

(

SElemType*base;

SElemType*top;

intstacksize;

)；

StatusInitStack(SqStack&S)

(

S.base=(SElemType*)nalloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)

returnERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

)

StatusPush(SqStack&S,SElemTypee)

if(S.top-S.base>=S.stacksize)

(

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*si

zeof(SElemType));

if(S.base)

returnERROR：

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

)

StatusPop(SqStack&S,SElemType&e)

(

if(S.top=S.base)

returnERROR;

e=*-S.top;

returnOK;

)

StatusGetTop(SqStackS,SElemType&e)

(

if(S.top=S.base)

returnERROR;

e=*(S.top-1):

returnOK;

}

intStackLength(SqStackS)

(

inti=0;

while(S.top!=S.base)

{

i++；

S.top—;

)

returni;

)

StatusStackTraverse(SqStackS)

(

SElemType*p=(SElemType*)malloc(sizeof(SElemlype));

p=S.top;

if(S.top=S.base)

printf(*TheStackisEmpty!");

else

(

printf("TheStackis:");

P-；

S.base一;

while(p!=S.base)

(

printf("%d",*p);

p—；

)

}

printf("\n");

returnOK;

)

intmainO

(

inta;

SqStackS;

SElemTypex,e;

if(InitStack(S))

printf(*AStackHasCreated.\n*);

while(l)

(

printf(*1:Push\n2:Pop\n3:GettheTop\n4:ReturntheLengthofthe

Stack\n5:LoadtheStack\nO:Exit\nPleasechoose:\n*);

scanf&a);

switch(a)

(

case1:scanf&x);

if(!Push(S,x))

printf("PushError!\n");

else

printf("TheElement%disSuccessfullyPushed!\n*,x);

break;

case2:if(!Pop(S,e))

printf("PopError!\n");

else

printf(*TheElement%disSuccessfullyPoped!\n*,e):

break;

case3:if(!GetTcp(S,e))

printf(*GetTopError!\n*);

else

printf("TheTopElementis%d!\n”,e);

break;

case4:printf("TheLengthoftheStackis%d!\n”,StackLength(S));

break;

case5:StackTraverse(S);

break;

case0:return1;

)

}

}

2.2循环队列的基本操作

#include<stdio.h>

#include<malloc.h>

ftdefineOK1

#defineERROR0

typedefintStatus;

typedefintQElemType;

#defineMAXQSIZE100

typedefstruct

(

QElemType*base;

intfront;

intrear;

}SqQueue:

StatusInitQueue(SqQueue&Q)

(

Q.base=(QElemType*)nalloc(MAXQSIZE*sizeof(QElemType));

if(!Q.base)

returnERROR;

Q.front=Q.rear=0;

returnOK;

}

StatusEnQueue(SqQueue&Q,QElemTypee)

(

if((Q.rear+l)%MAXQSIZE=Q.front)

returnERROR;

Q.baseTQ.rearl=e;

Q.rear=(Q.rear+l)%MAXQSIZE;

returnOK;

)

StatusDeQueue(SqQueue&Q,QElemType&e)

(

if(Q.front=Q.rear)

returnERROR;

e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;

)

StatusGetHead(SqQueueQ,QElemType&e)

(

if(Q.front=Q.rear)

returnERROR;

e=Q.base[Q.front];

returnOK;

)

intQueueLength(SqQueueQ)

(

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;

)

StatusQueueTraverse(SqQueueQ)

(

inti:

i=Q.front;

if(Q.front=Q.rear)

printfCTheQueueisEmpty!");

else

(

printf(*TheQueueis:");

while(i!=Q.rear)

(

printfC%d*,Q.base[i]);

i=i+l;

)

)

printf('\n");

returnOK;

)

intmain()

(

inta;

SqQueueS;

QElemTypex,e;

if(InitQueue(S))

printf(*AQueueHasCreated.\n");

while(1)

(

printf(*1:Enter\n2:Delete\n3:GettheFront\n4:Returnthe

LengthoftheQueue\n5:LoadtheQueue\nO:Exit\nPleasechoose:\n");

scanf&a);

switch(a)

(

case1:scanf&x);

if(!EnQueue(S,x))

printf(*EnterError!\n");

else

printf("TheElement%disSuccessfullyEntered!\n",x);

break;

case2:if(!DeQueue(S,e))

printf("DeleteError!\n*);

else

printf(*TheElement%disSuccessfullyDeleted!\n*,e);

break;

case3:if(!GetHead(S,e))

printf(*GetHeadError!\n*);

else

printf("TheHeadoftheQueueis%d!\n*,e);

break;

case4:printf(*TheLengthoftheQueue

is!\n”,QueueLength(S));

break;

case5:QueueTraverse(S);

break;

case0:return1;

)

}

)

2.3栈的应用一进制转换

#include<stdio.h>

#includfi<mal1oc.h>

#defineERROR0

#defineOK1

#defineSTACK」NIT_SIZE100

#defineSTACKINCREMENT10

typedefintSElemType;

typedefintStatus;

structSqStack

(

SElemType*base;

SElemType*top;

intstacksize;

)；

StatusInitStack(SqStack&S)

(

S.base=(SElemType*)iialloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)

returnERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

)

StatusPush(SqStack&S,SElemTypee)

(

if(S.top-S.base>=S.stacksize)

(

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*si

zeof(SElemType));

if(S.base)

returnERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

)

StatusPop(SqStack&S,SElemType&e)

if(S.top=S.base)

returnERROR;

e=*-S.top;

returnOK;

)

StatusStackEmpty(SqStack&S)

(

if(S.top=S.base)

return0;

else

return1;

)

intmainO

(

intN,e;

SqStackS;

InitStack(S);

scanf&N);

while(N)

(

Push(S,N%8);

N=N/8;

}

while(StackEmpty(S))

(

Pop(S,e);

printf("%d”,e);

)

return0;

}

2.4括号匹配检验

typedefcharSElemType;

#include<malloc.h>

#include<stdio.h>

#include<math.h>

#include<process.h>

^defineOK1

#defineERROR0

#defineTRUE1

#defineFALSE0

typedefintStatus;

#defineSTACK_INIT_SIZE10

#defineSTACKINCREMENT2

structSqStack

(

SElemType*base;

SElemType*top;

intstacksize;

)；

StatusInitStack(SqStack&S)

(

S.base=(SElemType*)nalloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)

return0;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

)

StatusStackEmpty(SqStackS)

(

if(S.top=S.base)

returnTRUE;

else

returnFALSE;

)

StatusPush(SqStack&S,SElemTypee)

(

if(S.top-S.base>=S.stacksize)

(

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*si

zeof(SElemType));

if(!S.base)

return0;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

)

StatusPop(SqStack&S,SElemType&e)

(

if(S.top=S.base)

returnERROR;

e=*-S.top;

returnOK;

)

voidcheck()

(

SqStacks;

SElemTypech[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);

(

printf("isn'tmatchedpairs\n*);

return:

)

else

(

P++；

break;

)

}

else

(

printfClackofleftparenthesis\n*);

return;

)

default:p++;

}

if(StackEmpty(s))

printf("matching\n");

else

printf(*lackofrightparenthesis\n*);

}

}

intmainO

(

check();

return1;

)

2.5行编辑程序

typedefcharSElemType;

#include<malloc.h>

#include<stdio.h>

#include<math.h>

#include<process.h>

tfdefineOK1

#defineERROR0

#defineTRUE1

#defineFALSE0

typedefintStatus;

#defineSTACK_INIT_SIZE10

#defineSTACKINCREMENT2

structSqStack

(

SElemType*base:

SElemType*top;

intstacksize;

J；

FILE*fp;

StatusInitStack(SqStack&S)

(

S.base=(SElemType*)iialloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)

return0;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}

StatusStackEmpty(SqStackS)

(

if(S.top=S.base)

returnTRUE;

else

returnFALSE;

)

StatusClearStack(SqStack&S)

(

S.top=S.base;

returnOK;

)

StatusDestroyStack(SqStack&S)

(

free(S.base);

S.base=NULL;

S.top=NULL;

S.stacksize=0;

returnOK;

)

StatusPush(SqStack&S,SElemTypee)

(

if(S.top-S.base>=S.stacksize)

(

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*si

zeof(SElemType)):

if(!S.base)

return0;

S.top=S.base+S.stacksize;

S.stacksize+二STACKINCREMENT;

}

*S.top++=e;

returnOK;

)

StatusPop(SqStack&S,SElemType&e)

(

if(S.top=S.base)

returnERROR;

e=*-S.top;

returnOK:

)

StatusStackTraverse(SqStackS,Status(*visit)(SElemType))

(

while(S.top>S.base)

visit(*S.base++);

printf('\n");

returnOK;

)

Statusvisit(SElemTypec)

(

printfc);

returnOK;

)

voidLineEdit()

(

SqStacks;

charch,c;

intn,i;

InitStack(s);

scanf&n);

ch=getchar();

for(i=l;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);

)

intmainO

(

LineEditO;

return1;

)

2.6表达式求值

#include<stdio.h>

#include<malloc.h>

#defineOK1

ftdefineERROR0

ftdefineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

typedefintStatus;

structSqStack_T

(

char*base;

char*top;

intstacksize;

)；

structSqStack_N

(

int*base;

int*top;

intstacksize;

)；

StatusInitStack_T(SqStack_T&S)

(

S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char))：

if(!S.base)

returnERROR;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

)

StatusInitStack_N(SqStack_N&S)

(

S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));

if(!S.base)

returnERROR:

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

)

intPush_T(SqStack_T&S,chare)

(

if(S.top-S.base>=S.stacksize)

(

S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(

char));

if(!S.base)

returnERROR;

S.top=S.base+S.stacksize;

S.stacksize+:STACKINCREMENT;

}

*S.top++=e;

returnOK;

)

intPush_N(SqStack_N&S,inte)

(

if(S.top-S.base>=S.stacksize)

(

S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(i

nt));

if(!S.base)

returnERROR;

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

*S.top++=e;

returnOK;

)

intPop_T(SqStack_T&S,char&e)

(

if(S.top=S.base)

returnERROR;

e=*-S.top;

returnOK;

}

intPop_N(SqStack_N&S,int&e)

(

if(S.top=S.base)

returnERROR;

e=*-S.top;

returnOK;

)

charGetTop_T(SqStack_TS)

(

chare;

if(S.top=S.base)

returnERROR;

e=*(S.top-1);

returne;

)

intGetTop_N(SqStack_NS)

(

inte;

if(S.top=S.base)

returnERROR;

e=*(S.top-1);

returne;

)

charPrecede(charthetal,chartheta2)

(

inta,b;

switch(thetal)

(

case'+':a=2;break;

case'-':a=2;break;

case':a=4;break;

casea=4;break;

casea=0;break;

casea=6;break:

case=:a=~l;break;

)

switch(theta2)

case'+':b=l;break;

case':b=l:break:

case'*':b=3;break;

case'I':b=3;break;

case'C:b=6;break;

case')':b=0;break;

case'='：b="l;break;

)

if(a<b)

return'<';

else

if(a=b)

return'=';

else

return'>';

}

charprecede(chare,charc)

(

if(c='+'||c='-')

(

if(e=，+'||e=：||e=)||e=~)

return'>';

else

return'；

}

if(c='*'II'/')

(

if(e=C)

return'〈'；

else

return'>';

)

if(c=C)

(

if(e二))一

return，=';

else

return'<';

)

if-)

return'>';

if(c='=')

if(e='=,)

return=:

else

return'<';

intIn(charc)

if(c〉='O'&&c<=9')

return1;

else

return0;

intOperate(inta,chartheta,intb)

(

ints;

switch(theta)

(

cases=a+b;break;

case'一'：s=a-b;break;

cases=a*b;break;

case'I':

if(b!=O)

s=a/b;

else

printfC*Inputerror*);

break;

returns

intmain()

intk=0,m,y,a,b;

SqStack_TOPTR;

SqStack_NOPND;

charc,theta;

InitStack_T(OPTR);Push_T(OPTR,J=)；

InitStack_N(OPND);c=getchar();

while(c!==||GetTop_T(OPTR)!='=')

if(In(c))

m=c'0':

if(k=l)

Pop_N(OPND,y);