数据结构chap003

第三章栈和队列通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈的类型定义3.2栈的应用举例3.3栈类型的实现3.4队列的类型定义3.5队列类型的实现3.1栈的类型定义ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1……3.2栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归例一、数制转换算法基于原理：N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序voidconversion(){InitStack(S);scanf(%d,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}}//conversion例二、括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:•到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：[([][])]12345678•到来的是“不速之客”；•直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。Statusmatching(string&exp){intstate=1;while(i=Length(exp)&&state){switchofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case”)”:{if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);ii++;}else{state=0;}break;}……}if(StackEmpty(S)&&state)returnOK;…...例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?并不恰当！设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：假设从终端接收了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;}ch=getchar();//从终端接收下一个字符}ClearStack(S);//重置S为空栈if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；例四、迷宫求解通常用的是“穷举求解”的方法############$$$####$$$###$$#####################################求迷宫路径算法的基本思想是：•若当前位置“可通”，则纳入路径，继续前进;•若当前位置“不可通”，则后退，换方向继续探索;•若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；do｛若当前位置可通，则｛将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；｝否则{｝｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法：……若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数例五、表达式求值表达式的三种标识方法：设Exp=S1+OP+S2则称OP+S1+S2为前缀表示法S1+OP+S2为中缀表示法S1+S2+OP为后缀表示法例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。如何从后缀式求值？先找运算符，再找操作数例如：abcde/f+abd/ec-d/e(c-d/e)f如何从原表达式求得后缀式？每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f从原表达式求得后缀式的规律为：1)设立操作数栈；2)设表达式的结束符为“#”，予设运算符栈的栈底为“#”；3)若当前字符是操作数，则直接发送给后缀式。4)若当前运算符的优先数高于栈顶运算符，则进栈；5)否则，退出栈顶运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}if(ch!=#){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}}//while}//CrtExptree……switch(ch){case(:Push(S,ch);break;case):Pop(S,c);while(c!=(){Pass(Suffix,c);Pop(S,c)}break;defult:while(Gettop(S,c)&&(precede(c,ch))){Pass(Suffix,c);Pop(S,c);}if(ch!=#)Push(S,ch);break;}//switch例六、实现递归•将所有的实在参数、返回地址等信息传递给被调用函数保存；•为被调用函数的局部变量分配存储区；•将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：•保存被调函数的计算结果；•释放被调函数的数据区；•依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){………a();b();……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用，例如：voidhanoi(intn,charx,chary,charz){//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1if(n==1)2move(x,1,z);//将编号为１的圆盘从x移到z3else{4hanoi(n-1,x,z,y);//将x上编号为１至n-1的//圆盘移到y,z作辅助塔5move(x,n,z);//将编号为n的圆盘从x移到z6hanoi(n-1,y,x,z);//将y上编号为１至n-1的//圆盘移到z,x作辅助塔7}8}83abc返址nxyz52acb51abc71cabvoidhanoi(intn,charx,chary,charz){1if(n==1)2move(x,1,z);3else{4hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7}8}3.3栈类型的实现顺序栈链栈//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base=S.stacksize){//栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)e