《数据结构第三章(1)》由会员分享，可在线阅读，更多相关《数据结构第三章(1)（40页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS 3.1 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO）,栈的表示和实现 顺序栈 实现：一维数组sM,栈顶指针top,指向实际栈顶 后的空位置，初值为0,A,出栈,栈满,B,C,D,E,F,设数组维数为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow),栈空,初始化算法,取栈项元素算法,栈的顺序存储表示： #define STAC
2、K_INIT_SIZE 100; #define STACKINCREMENT 10; Typedef struct SElemType *base;SElemType *top;int stacksize; SqStack;,Status InitStack(SqStack /InitStack,构造空栈,Stack GetTop (SqStack S,SElemType /GetTop,入栈算法,出栈算法,在一个程序中同时使用两个栈,Status Push(SqStack /Push,入栈,int push(int s,int x,int top) if(top=M) printf(“ov
3、erflow“);return(-M);stop=x;return(+top); ,Stack Pop (SqStack /Pop,出栈,int pop(int s,int top,int *q) if(top=0) printf(“stack empty“);return(0);*q=s-top;return(top); ,链栈,结点定义,入栈算法,出栈算法,typedef struct node int data;struct node *link; JD;,JD *lzjz(JD *top,int x) JD *p;p=(JD *)malloc(sizeof(JD);p-data=x;p
4、-link=top;top=p;return(p); ,入栈,JD *lztz(JD *top,int *p) JD *q;if(top!=NULL) q=top;*p=top-data;top=top-link;free(q);return(top); ,出栈：,栈的应用 过程的嵌套调用,例 递归的执行情况分析,递归过程及其实现 递归：函数直接或间接的调用自身叫 实现：建立递归工作栈,void print(int w) int i;if ( w!=0) print(w-1);for(i=1;i1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个
5、圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题 算法：,执行情况： 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示,main() int m;printf(“Input number of disks”);scanf(“%d“, (8) (9) ,main() int m;printf(“Input the number of disksscanf(“%d“, (8) (9) ,main() int m;printf(“Input the number of disksscanf(“%d“, (8) (9)
6、,main() int m;printf(“Input the number of disksscanf(“%d“, (8) (9) ,回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串 2.去掉空格（原串） 3.压入栈 4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文,多进制输出：,字符串：“madam im adam”,括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（）（） （）行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时
7、可以及时更正。,行编辑程序算法如下:void lineedit( )initstack(S);ch=getchar( );while(ch!=eof)while(ch!=eof /LineEdit,表达式求值,中缀表达式 后缀表达式（RPN)a*b+c ab*c+a+b*c abc*+a+(b*c+d)/e abc*d+e/+,中缀表达式：操作数栈和运算符栈,例 计算 2+4-3*6,后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1,例 计算 4+3*5
8、,后缀表达式：435*+,栈的应用举例,例2 表达式求值 1）问题的提出 设计一个小计算器: 对键入的表达式进行求值。,高级语言中的赋值语句：变量=表达式；,2） 表达式的构成 操作数+运算符+界符（如括号） 3） 表达式的求值：例 5+6 (1+2)- 4按照四则运算法则，上述表达式的计算过程为：5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19,1,2,3,4,4） 算符优先关系表表达式中任何相邻运算符c1、c2的优先关系有： c1c2：c1的优先级高于c2,算符间的优先关系表,注： c1 c2是相邻算符， c1在左， c2在右,5 算符优先算法,从左向右扫描表
9、达式：遇操作数保存；遇运算符号cj与前面的刚扫描过的运算符ci比较 若cicj 则说明ci是已扫描的运算符中优先级最高者，可进行运算； 若ci = cj 则ci为（，cj 为 ），说明括号内的式子已计算完，需要消去括号；,5 + 4 (1 + 2) - 6,后面也许有优先级更高的算符,+,+,(,后保存的算符有优先级高,用两个栈分别保存扫描过程中遇到的操作数和运算符,在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符一个是OPND栈，用以保存操作数或运算结果。 int express ( ) /运算数栈，OP为运算符集合。InitStack(OPTR); Push (OPTR
10、, # );InitStack(OPND); w=getchar( );While(w!= # | GetTop(OPTR)!=#)if(! In(w,OP)Push(OPND,w);w=getchar(); /不是运算符则进栈else / In(w, OP)判断c是否 是运算符的函数,续 switch (Precede(GetTop(OPTR), w) case : /新输入的算符c优先级低，即栈顶算符优先权高，/出栈并将运算结果入栈OPNDop=Pop(OPTR);b=Pop(OPND); a= Pop(OPND);Push(OPND, Operate(a, op, b);break; r
11、eturn GetTop(OPND); ,3.2 队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点：先进先出(FIFO),双端队列,链队列 结点定义,typedef struct Qnode QElemType data;struct Qnode *next; Qnode,*QueuePtr; Typedef structQueuePtr front;QueuePtr rear; /LinkQueue;,设队首、队尾指针front和rear, front指向头结点，rear指
12、向队尾,入队算法,出队算法,队列的顺序表示和实现 实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素位置 初值front=rear=0,空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,存在问题 设数组维数为M，则： 当front=0,rear=M-1时，再有元素入队发生溢出真溢出 当front0,rear=M-1时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： rear=(rear+1)%M; sqrear=x; 出队： front=(front+1)%M; x=sqfront; 队满、队空判定条件,队空：front=rear 队满：front=rear,解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间：队空：front=rear队满：(rear+1)%M=front,入队算法：,出队算法：,
