#define STACK_INIT_SIZE 10

Presentation on theme: "#define STACK_INIT_SIZE 10"— Presentation transcript:

1

2 #define STACK_INIT_SIZE 10
void InitStack_sq(SqStack &S,int msize=STACK_INIT_SIZE) {//构造一个容量是msize的顺序栈S S.elem=new ElemType[msize];S.stacksize=msize; S.top=-1; // 顺序栈初始时空栈 }// end InitStack_sq

3 void DestroyStack_sq(SqStack &S)
delete [] S.elem; // 释放数组空间 S.top=-1; S.stacksize=0; }// end DestroyStack_sq

4 bool GetTop_sq(SqStack S,ElemType &e)
{//若顺序栈S非空，用e返回S的栈顶元素，并返回TRUE，否则返回FALSE if(S.top==-1)return FALSE; e=S.elem[S.top]; return TRUE; }//end GetTop_sq

5 void Push_sq(SqStack &S,ElemType e)
{//将e插入栈S，作为S新的栈顶元素 if(top==S.stacksize-1) Increment(S); S.elem[++S.top]=e; }// end Push_sq

6 bool Pop_sq(SqStack &S,ElemType &e)
{//若顺序栈S非空，删除栈顶元素并赋予e，返回TRUE，栈空则返回FALSE if(S.top==-1)return FALSE; e=S.elem[S.top--]; return TRUE; }//end Pop_sq

7 void InitStack_L(LinkStack &S)
S=NULL; //链栈栈初始时空栈 }// end InitStack_L

8 void DestroyStack_L(LinkStack &S)
while(S){ p=S; S=S->next; //S指针后移 delete p; } }// end DestroyStack_L

9 bool GetTop_L(LinkStack S,ElemType &e)
{//若链栈S非空，用e返回S的栈顶元素，并返回TRUE，否则返回FALSE if(!S)return FALSE; e=S->data; return TRUE; }// end GetTop_L

10 void Push_L(LinkStack &S,ElemType e)
{//将e插入S的栈顶，作为S新的栈顶元素 p=new LNode; p->data=e; p->next=S; S=p; }// end Push_L

11 bool Pop_L(LinkStack &S,ElemType &e)
{//若链栈S非空，删除栈顶元素并赋予e，返回TRUE，栈空则返回FALSE if(!S)return FALSE; p=S; S=S->next; //S删除栈顶元素 e=p->data; delete p; //释放该结点内存空间 return TRUE; }// end Pop_L

12 void conversion(int N,int d)
{//把非负整数N转换位d进制数并按从高到底的顺序输出数位 InitStack(S); //初始化栈S while(N){ //N非零继续处理 push(S,N%d); //取模入栈 N=N/d; //N/d再赋予N循环处理 }//while while(!StackEmpty(s)){ pop(S,e); cout<<e; }//end conversion

13 bool match(char exp[])
{//检查表达式exp中的括号是否嵌套正确，是则返回TRUE，否则返回FALSE int matchstat=1; InitStack(S); //初始化栈S ch=*exp++; while(ch!=’#’&&matchstat){ //exp没有处理完 switch (ch){ case ‘(‘: case ‘[‘: case ‘{‘: push(S,ch); break;

14 case ‘)’: if(!Pop(S,e)||e!=’(’)matchstat=0; break; //栈空或栈顶不是“(”，则表示不匹配 case ‘]’: if(!Pop(S,e)||e!=’[’)matchstat=0; break; case ‘}’: if(!Pop(S,e)||e!=’{’)matchstat=0; }//switch ch=*exp++; }//while if（matchstat&&StackEmpty(S)）return TRUE; else return FALSE; }//end match

15 void knapsack(int w[],int T,int n)
{ InitStack(S); k=0; //初始化栈S do{ while(T>0 && k<n){ //背包未满，物品也没有尝试到最后一个 if(T-w[k]>=0){ //序号为k的物品可以放进背包 push(S,k); //当前物品入栈 T-=w[k]; //背包剩余体积减少 }//if k++; //继续考虑下一个物品 }//while //循环结束时：T==0找到解或k==n尝试到最后一个物品 if(T==0)StackTraverse(S); //找到一组解，输出 if(!StackEmpty(S)){ //无论是找到一组解或尝试到最后物品均要回溯 pop(S,k);T+=w[k]; //退出栈顶物品，背包剩余体积增加 k++; //从退出物品下一个继续尝试 }while(!StackEmpty(S)||k!=n) DestroyStack(S); }//end knapsack

16 int calculate(char suffix[])
char *p=suffix; InitStack(S); //初始化栈S ch=*p++; while(ch!=’#’){ //表达式没有结束 if(!isoperator(ch))push(S,ch); //非运算符直接入栈 else { pop(S,b);pop(S,a); /两个操作数出栈 push(S,operate(a,ch,b)); } ch=*p++; //继续处理下一个 }//while pop(S,e); //表达式结果 DestroyStack(S); return e; }//end calculate

17 void getsuffix(char exp[]，char suffix[])
{//将串exp表示的原表达式（#结束）转换为后缀表达式suffix InitStack(S); push(S,'#'); //初始化栈S char *p=exp; k=0; //初始化后缀表达式下标 while(!StackEmpty(S)){ ch=*p++; //处理原表达式一个字符 if(!isoperator(ch)){ suffix[k++]=ch; continue; //非运算符直接发送 } switch(ch){ case '(':Push(S,ch);break; case ')': while(Pop(S,c)&&c!='(')suffix[k++]=c; break; default: while(GetTop(S,c)&&preop(c,ch)) {suffix[k++]=c;Pop(S,c);} if(ch!='#')push(S,ch); //'#'除外当前字符入栈 }//switch }//while suffix[k]='\0';DestroyStack(S); }//end getsuffix

18 OperandType EvaluateExp(char exp[])
InitStack(SOP); Push(SOP,'#'); //初始化运算符栈 InitStack(SVAL); //初始化操作数栈 char *p=exp; while(!StackEmpty(SOP)){ ch=*p++; //处理原表达式一个字符 if(!isoperator(ch)){ Push(SVAL,ch);continue; //非运算符直接入操作数栈 } switch(ch){ case '(': Push(SOP,ch);break; case ')': //碰到右括号一直出栈运算符，直到’(‘ while(Pop(SOP,c)&&c!='('){ Pop(SVAL,b); Pop(SVAL,a); //出栈两操作数 Push(SVAL,operate(a,c,b)); //计算后再入栈 break;

19 default: while(GetTop(SOP,c)&&preop(c,ch)){ Pop(SOP,c); Pop(SVAL,b); Pop(SVAL,a); //出栈两操作数 Push(SVAL,operate(a,c,b)); //计算后再入栈 } if(ch!='#')Push(SOP,ch); //除'#'外当前运算符入栈 break; }//switch }//while GetTop(SVAL,e); //操作数栈中是计算的结果 DestroyStack(SOP); DestroyStack(SVAL); return e; }//end EvaluateExp

20 #define QUEUE_INIT_SIZE 10
void InitQueue_sq(SqQueue &Q,int msize=QUEUE_INIT_SIZE) { Q.elem=new ElemType[msize]; Q.queuesize=msize; Q.front=Q.rear=0; //顺序栈初始时空栈 }// end InitQueue_sq

21 void DestroyQueue_sq(SqQueue &Q)
delete [] Q.elem; // 释放数组空间 Q.front=Q.rear=0; Q.queuesize=0; }// end DestroyQueue_sq

22 int Queuelength_sq(SqQueue Q)
{//返回循环队列的长度 return (Q.rear+Q.queuesize-Q.front)%Q.queuesize; }// end Queuelength_sq

23 void Enqueue_sq(SqQueue &Q,ElemType e)
{//将e插入Q队尾，作为Q新的队尾元素 if((Q.rear+1)%Q.queuesize==Q.front)Increment(Q); //如果队列满则增加空间 Q.elem[Q.rear]=e; Q.rear=(Q.rear+1)%Q.queuesize; }// end Enqueue_sq

24 bool DeQueue_sq(SqQueue &Q,ElemType &e)
{ if(Q.front==Q.rear)return FALSE; e=Q.elem[Q.front]; Q.front=(Q.front+1)%Q.queuesize; return TRUE; }// end DeQueue_sq

25 void InitQueue_L(LinkQueue &Q)
Q.front=Q.rear=New LNode; Q.front->next=NULL; }// end InitQueue_L

26 void DestroyQueue_L(LinkQueue &Q)
while(Q.front){ Q.rear=Q.front->next; //Q.rear不断后移指针 delete Q.front; //释放Q.front结点 Q.front=Q.rear; } }// end DestroyQueue_L

27 bool GetHead_L(LinkQueue Q,ElemType &e)
{//若链队列Q非空，用e返回Q的队首元素，并返回TRUE，否则返回FALSE if(Q.front==Q.rear)return FALSE; e=Q.front->next->data; return TRUE; }// end GetHead_L

28 void Enqueue_L(LinkQueue &Q,ElemType e)
{//将e插入Q的队尾，作为Q新的队尾元素 p=new LNode; p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p }// end Enqueue_L

29 bool DeQueue_L(LinkQueue &Q,ElemType &e)
{//若链队列Q非空，删除队首元素并赋予e，返回TRUE，队列空则返回FALSE if(Q.front=Q.rear)return FALSE; p=Q.front->next; Q.front->next=p->next; e=p->data; if(Q.rear==p)Q.rear=Q.front; //删掉的恰好是最后一个结点 delete p; //释放该结点内存空间 return TRUE; }// end DeQueue_L

30 void yanghui(int n) {//输出n行的二项式系数表 InitQueue(Q,n+2); EnQueue(Q,0); EnQueue(Q,1); EnQueue(Q,1); //一阶系数入队列”0 1 1” k=1; while(k<n){ //计算出n行系数，输出前n-1行系数 for(i=1;i<=n-k;i++)cout<<’ ’; //根据k输出空格保持三角形 EnQueue(Q,0); //入队列行界符0 do{ DeQueue(Q,s); GetHead(Q,e); //出队列左上方、读取队首元素(右上方) if(e)cout<<e<<’ ’; else cout<<endl; //e非行界0，输出e,否则换行 EnQueue(Q,s+e); //k+1行数据入队列 }while(e!=0); //k+1行数据计算结束 k++; }//while DeQueue(Q,e); //n行行界符0，出队列 while(!QueueEmpty(Q)){ //单独输出n行数据 DeQueue(Q,e); cout<<e<<’ ’; } }// end yanghui

31 void DancePartner() {//为m位男士和n位女士组合舞伴，一次最多X对舞伴可以同时跳舞m>n>X Queue Qm,Qf; InitQueue(Qm,m); //初始化男士队列 InitQueue(Qf,n); //初始化女士队列 for(i=0;i<m;i++) EnQueue(Qm,i); //男士入队列,入的是数组下标 for(i=0;i<n;i++) EnQueue(Qf,i); //女士入队列 for(i=0;i<X;i++){ DeQueue(Qm,mk); DeQueue(Qf,nk); printf(“%s和%s组成舞伴。\n”,M_name[mk],F_name[nk]); }

32 endflg=0; //舞会结束标志 while(!endflg){ evt=getevent(); //取得下一个事件，E表示有舞伴跳完，Q表示舞会结束 switch(evt){ case ’E’: //有舞伴跳完，进入队列，新的组合进入舞池 getcurid(mk,nk);//获得当前结束舞伴的男女id（数组下标） EnQueue(Qm,mk); EnQueue(Qf,nk); //刚跳完的舞伴进入队列 printf(“%s和%s跳舞结束。\n”,M_name[mk],F_name[nk]); DeQueue(Qm,mk); DeQueue(Qf,nk);//队首男、女士组成舞伴 printf(“%s和%s组成舞伴。\n”,M_name[mk],F_name[nk]); break; case ‘Q’: printf(”舞会结束！\n”)；endflg=1; }//switch }//while Destroy(Qm); Destroy(Qf); //销毁队列 }// end DancePartner

33 void Ackerman1(int n,int x,int y)
if(n==0)return (x+1); if(y!=0) return Ackerman1(n-1,Ackerman1(n,x,y-1),x); return (n==1)?x: (n==2)?0: (n==3)?1:2; }//end Ackerman1

34 void Ackerman2(int n,int x,int y)
InitStack(S);e={n,x,y}; push(S,e); //初始化任务(n,x,y) do{ GetTop(S,e); while(e.n!=0 && e.y!=0){ //无法直接求解 e.y--; //形成任务(n,x,y-1) push(S,e); }//while pop(S,e); //e是可以直接求解的任务 u=getvalue(e.n,e.x,e.y); if(!StackEmpty(S)){ //e不是初始任务 pop(S,e); //出栈(n,x,y) e.n--;e.y=e.x;e.x=u; //形成(n,x,y)的等价任务(n-1,u,x) push(S,e); //入栈(n-1,u,x) }//if }while(!StackEmpty(S)) return u; }//end Ackerman2

35 int getvalue(int n,int x,int y)
{//计算n=0或y=0时Ackerman函数的值 （n,x,y）可以直接计算 if(n==0)return(x+1); return (n==1)?x: (n==2)?0: (n==3)?1:2; }//end getvlaue

36 void hannuo(int n,char A,char B，char C)
{//将汉诺塔中A柱子上的n个盘移动到C盘，B用作辅助柱子 if(n==1)move(A,1,C); //一个盘子直接移动到C else{ hannuo(n-1,A,C,B); //把n-1的盘子A->B,C作辅助 move(A,n,C); //把第n个盘A->C hannuo(n-1,B,A,C); //把n-1的盘子B->C,A作辅助 } }//end hannuo

37 #define N 8 int X[N]; //存放解向量 int B[2*N-1];C[2*N-1]; //+1 -1斜率方向有皇后的标记 int A[N]; //某一列是否有皇后的标记 void mark(int i,int j，int flag) {//在R[i,j]放入或取走皇后，flag=1放入，flag=0取走 A[j]=B[i+j]=C[i-j+7]=flag; }//end mark bool place(int i,int j) {//检查R[i,j]是否可以放皇后，TRUE表示可以放 return (A[j]==0 && B[i+j]==0 && C[i-j+7]==0); }//end place

38 void Queen(int i) {//从第i行开始放第i个皇后，调用Queen(0)得到全部的解。 for (j=0; j<N; j++){ //逐列尝试 if (place(i,j)){ //R(i,j)能放置吗 X[i] = j; //第i个皇后放在j列 mark(i,j,1); //标记R（i,j）已放置皇后 if(i==N-1){for(k=0;k<N;k++)cout<<X[k];cout<<endl;} //最后一个皇后已放入，输出解向量。 else queen(i+1); //接着试下一行的皇后 mark(i,j,0); //回溯，取走最后放置的皇后尝试下一个j }//if }//for }//end Queen