B.ch3.队列.ppt

3.4 栈的应用 1、数制的转换 要求：把正整数n转化为其他r进制的字符串 算法设计思想： (123)10=(173)8 (1)将待转换的十进制数除以8得到的余数转换成字符入栈， (2)再将商数除以8得到的余数转换成字符入栈， (3)重复 (2)，直到商为0止 (4)弹出栈中元素构成字符串 关键： (1)数值转换成对应字符？ 1 1 11 b (2)使用字符类型的顺序栈实现 算法实现： void Trans(int n, int r, char str[]) { int i, c; SeqStack s; InitStack(s); do{ c=n%r; if(c10) c=c+0; else c=c-10+a; Push(s,c); } while(n/=r); 2、括号匹配的检验 要求：检查一字符串中凡出现的括号是否匹配 例： 匹配的表达式： x=(a+b*[c-d]+{e+f}*g) 不匹配的表达式： {1*2+[5*(a-b)] 不匹配的情况 (1) 交叉型：[ ( ] ) (2) 右括号在前型：) ( [ ] (3) 右括号比左括号多：[ ( ) ] ( ) } (4) 左括号比右括号多： { [ ( ) ] 算法实现(顺序栈) void check( char *str) { char ch,d; int i; SeqStack s; InitStack(s); for(i=0;ch=str[i];i++) { switch(ch) { case (: case [: case {: Push(s,ch); break ; case ]: if(EmptyStack(s)) Error(\nMismatch); d=Pop(s); if( d!=[ ) Error(\n [ ] Mismatch) ; break; case }: if(EmptyStack(s)) Error(\nMismatch); d=Pop(s); if( d!={ ) Error(\n { } Mismatch) ; break; 队列 3.5 队列的定义及运算 3.6 队列的顺序存储结构 3.7 队列的链式存储结构 3.5 队列的定义及运算 1、队列的基本概念 队列也是线性表，删除运算在队列一端(队头front) 插入运算在队列另一端(队尾rear) 特点：先进先出(FIFO) 2、队列的例子及用途 例一：输入缓冲队列。 例二：打印机打印排队。 例三：食堂排队。 3、队列的基本运算 判队空 判队满 置空队列 入队 出队 读队头元素 3.6 队列的顺序存储结构——顺序队列 1、顺序队列的存储 采用数组表示队列 设定数组体积为MAX，队头位置front,队尾位置rear 3、顺序队列不同状态示意图(MAX=5) 4、顺序存储的循环队列 5、循环队列的基本运算实现 (1)初始化队列——置空队列 形参：队列的地址 返回值：无 void InitQueue (SQptr q) { q-front=q-rear=0; } (2)判队空 形参：队列的地址 返回值：1——队空 0——队不空 int EmptyQueue (SQptr q) { return q-front==q-rear; } (4)入队 形参：队列的地址 、入队元素 返回值：无 void EnQueue (SQptr q, datatype x) { if( FullQueue(q) ); /*若队满*/ Error(Queue Full); q-rear=(q-rear+1)%MAX; q-data[q-rear]=x; } (5)出队 形参：队列的地址 返回值：出队元素 datatype DeQueue (SQptr q) { if( EmptyQueu