第四章 栈和队列 4.1栈 4.2栈的应用 4.3队列 4.3队列应用

4.1栈 定义：栈（Stack）是限定只能在表得一端进行插入和删除操作得线性表，又称限定性线性表结构 4.1.1栈的结构特点和操作 栈顶(Top)、栈底(Bottom),先入后出(LIFO) 栈的基本操作 InitStack（&S） DestroyStack(&S) ClearStack(&S) StackEmpty（S） StackLength（S） GetTop(S,&e) Push(&S, e) Pop(&S,&e) StackTraverse(S)

4.1.2栈的表示和操作的实现 顺序栈 Const STACK_INIT_SIZE=1000; Const STACKINCREMENT=10; Typedef struct{ Selemtype *elem; Int top; Int stacksize; Int increment; }SqStack;

相关操作实现 InitStack_Sq(SqStack &S,int maxsize= STACK_INIT_SIZE, int incresmentize= STACKINCREMENT) GetTop_Sq(SqStack S,SelemType &e) Push_Sq(SqStack &S ,SelemType e) Pop_Sq(SqStack S ,SelemType &e) IncrementStacksize(&S){ SElemtype *a; a=new SElemType[S.stacksize+S. increment]; for(i=0;i<=S.top;i++)a[i]=S.elem[i]; delete [] S.elem; S.elem=a; S.stacksize+=S.increment; }

链栈 typedef LinkList LinkStack; InitStack_L(LinkStack &S) Push_L(LinkStack &S ,SelemType e) Pop_L(LinkStack S ,SelemType &e) Bool GetTop_L(Linkstack S,SElemType &e){ if(!S) return FALSE; e=S->data; return TRUE; }

4.2栈的应用 例4.1数制转换 例4.2括号匹配检验 例4.3 背包问题求解 例4.4 后缀表达式求值 算法4.1 void conversion() N=an*dn+an-1*dn-1+…+a1*d+a0 例4.2括号匹配检验 算法4.2 void matching() 例4.3 背包问题求解 算法4.3 void knapsack() 若可以w[n-1]>T，则应在pop前加入 if(!StackEmpty (S)) 外循环结束条件是：!(StackEmpty(S)&&k==n) 例4.4 后缀表达式求值 算法4.4 void evaluation()

原表达式转化为后缀表达式 规则 1)设立运算符栈 2)设运算符的结束符为“#”预设栈底为“#” 3)若当前字符是操作数，直接发送后缀表达式 算法4.5 void transform(char suffix[],char exp[]) 规则 1)设立运算符栈 2)设运算符的结束符为“#”预设栈底为“#” 3)若当前字符是操作数，直接发送后缀表达式 4)若当前字符是运算符，且优先级大于栈顶运算符，则入栈，否则退出栈顶运算符发送给后缀表达式。 5)若当前字符是结束符“#”，则自栈顶至栈底依次将栈中所有运算符发送给后缀表达式。 6)若当前运算符是“(”，进栈，对其之前底运算符起隔离作用。 7)若当前运算符是“)”，可视为自相应的“(”开始的表达式的结束，从栈顶起依次退出栈顶运算符发送给后缀表达式，直至栈顶相应运算符为“(”，再将“(”也出栈

例4.5 递归函数的实现 算法4.6 int Ackerman(int n,int x,int y) 汉诺塔问题：有三个塔座X、Y、Z，X座上插有n个直径大小各不相同编号为1…n的圆盘。现在要求将X上的圆盘移动到Z塔座上。要求遵循以下规则： 每次只能移动一个圆盘 圆盘可以插在X、Y、Z中任一个上 任何时刻都不能将一个大盘压在小盘上

4.3队列 定义：队列（Queue）是限定只能在表得一端进行插入在表的另一端进行删除操作的线性表 4.3.1队列的结构特点和操作 队列头(front)、队列尾(rear)，先入先出(FIFO) 队列的基本操作 InitQueue(&Q) DestroyStack(&S) ClearQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q,&e) EnQueue(&Q,e) Dequeue(&Q,&e) QueueTraverse(Q)

4.3.2队列的表示和操作的实现 链队列 表示结构:带头结点的单链表 typedef Linklist Queueptr; typedef struct { Queueptr front; //指向头结点 Queueptr rear; //指向队尾 }LinkQueue; 操作实现 void InitQueue_L(LinkQueue &Q); void DestroyQueue_L(LinkQueue &Q); void EnQueue_L(LinkQueue &Q,Qelemtype e); void DeQueue_L(LinkQueue &Q,Qelemtype &e); 注意：删除元素时为最后一个元素时应改写rear指针。

循环队列：队列首尾相接 表示结构 typedef struct { Qelemtype *elem; int front; int rear; int queuesize; int incrementsize; }SqQueue; 空队列判断 不可用用首尾指针相等来判断队列的空 解决办法：1：增加标志位 2：少用一个元素

实现 InitQueue_Sq(SqQueue &Q,int maxsize,int incresize) 【更正】Q.queuesize=maxsize+1; QueueLength_Sq（SqQueue Q） EnQueue_Sq（SqQueue &Q, ElemType e） Dequeue(SqQueue &Q, ElemType &e)

4.3队列应用 例4.6 打印二项式系数 例4.7 为比赛划分无冲突子集 算法4.7 void yanghui(int n) 注意：最后一行单独处理 例4.7 为比赛划分无冲突子集 算法4.8 void Division(int R[][],int n,int result) 注意：队列是否为空，不能由front和rear相等来判 【更正】EnQueue_Sq函数调用都多一个参数0