数据结构(长安大学)讲科目课PPT3.pptVIP

数据结构;数据结构 ---------------------------------------------;学习数据结构的方法;第三章 栈与队列;§ 3 栈、队列和数组;§3.1 栈;一、栈的定义和运算;一、栈的定义和运算－术语;二、顺序栈;二、顺序栈－图例;二、顺序栈－图例;二、顺序栈－运算的实现 ;二、顺序栈－运算的实现 ;二、顺序栈－运算的实现入栈;二、顺序栈－运算的实现出栈;二、顺序栈－运算的实现栈满;三、链栈—采用链表来存储的栈 ; 使用不带表头结点的单链表 ,非空链式栈的一般形式;链式栈的进栈算法：//压入元素e到top为顶指针的链式栈 struct node *push_link(struct node *top,Elemtype e) { struct node *p； int leng=sizeof(struct node)； //确定新结点空间的大小 p=(struct node *)malloc(leng)；//生成新结点 p-data=e； //装入元素e p-next=top； //插入新结点 top=p； //top指向新结点 return top； //返回指针top };三、链栈;入栈;出栈;四、栈的应用;四、栈的应用－ 2; void conversion( ) { initstack(s); scanf (“%”,n); while(n){ push(s,n%8); n=n/8; } while(! Stackempty(s)){ pop(s,e); printf(“%d”,e); } } ;3 行编辑程序 例.;行编辑程序算法如下: void lineedit( ){ initstack(s); ch=gether( ); while(ch!=eof){ while(ch!=eof ch!=‘\n’){ switch(ch){ case ‘#’ : pop(s,c); case ‘@’ : clearstack(s); default : push(s,ch); } ; ch=getchar( ); } clearstack(s); if(ch!=eof) ch=gethar( ); } destroystack(s); };4 表达式求值 例：4 + 2 * 3 – 10 / ( 7 – 5 );算法思想： 设立：s1----操作数栈,存放暂不运算的数和中间结果 s2----算符栈,存放暂不运算的算符 1.置s1,s2为空栈；开始符#进s2； 2.重复： { 2.1 从表达式读取“单词”w----操作数/算符 2.2 若w为操作数，则w进s1； 2.3 若w为算符，则： 2.3.1 若ws2的顶算符，则w进s2； 2.3.2 若w=s2的顶算符，且w=“)”，则pop(s2)； 2.3.3 若ws2的顶算符，则： { pop(s1,a)；pop(s1,b)；pop(s2,op)； c=b op a； push(s1,c)； 转2.3.1； } } 直到现在w=“#”=s2的顶算符。;例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ;例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ; 例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ;5迷宫求解 入口;四、栈的应用－ 3;四、栈的应用－ 3;例;四、栈的应用－ 3;四、栈的应用－ 3;四、栈的应用－ 3;§3.2 队列;一、队列定义和运算; 队列相关的定义和术语 ▲ 队列----只允许在表的一端删除元素,在另一端插入