数据结构

数据结构与算法栈栈的应用举例队列第三章栈和队列数据结构2前言栈和队列是两种特殊的线性表，其特殊性在于栈和队列的基本操作是线性表的子集，它们是操作受限的线性表，可称为限定性的DS.数据结构3第一节栈栈(stack)限定仅在表尾进行插入或删除操作的线性表表尾—栈顶表头—栈底不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,…,an)数据结构4栈的基本操作教材P44-45关于栈的抽象描述数据结构5栈的顺序存储结构顺序栈—实现：一维数组s[M]当堆栈中数据全部弹出后，在内存中的是什么？栈顶指针top,指向实际栈顶后的空位置，初值为0top123450Atop出栈栈满BCDEFtop=0栈空,此时出栈则下溢(underflow)top=M栈满,此时入栈则上溢(overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptop栈空top=0top=0进栈空栈数据结构6顺序栈算法入栈算法出栈算法用数组实现的顺序栈的评价栈的容量在使用前难以估计操作简便intpush(ints[],intx,inttop){if(top==M){printf(overflow);return(-M);}s[top]=x;return(++top);}intpop(ints[],inttop,int*q){if(top==0){printf(stackempty);return(0);}*q=s[--top];return(top);}数据结构7共享顺序栈顺序栈所需容量在使用前难以估计，而且有些CPU内存有限，可供堆栈使用的空间有限，如单片机。常在一个程序中将两个堆栈使用的空间放在一起。0M-1栈1底栈1顶栈2底栈2顶数据结构8栈的链式存储结构若一个程序中要使用多于两个的栈，则可以采用链表作为存储结构，这种存储结构通常称为链栈(linked-stack).nextdatatop栈底…^结点定义typedefstructtagLinkedStack{intdata;structtagLinkedStack*next;}LinkedStack;入栈算法出栈算法数据结构9链栈算法链栈通常都在链表头端操作。^…...栈底toptopxptop^…...栈底topqLinkedStack*LSPush(LinkedStack*top,intx){LinkedStack*p;p=(LinkedStack*)malloc(sizeof(LinkedStack));p-data=x;p-next=top;top=p;return(p);}LinkedStack*LSPop(LinkedStack*top,int*x){LinkedStack*q;if(top){q=top;*x=top-data;top=top-next;free(q);}return(top);}在尾端操作呢数据结构10第二节栈的应用举例过程的嵌套调用数制转换括号的匹配回文游戏走迷宫地图着色问题表达式求值数据结构11过程的嵌套调用子程序调用-调用时入栈，返回时出栈r主程序srrrs子过程1rst子过程2rst子过程3数据结构12数制转换把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2top732toptoptop数据结构13括号的匹配考虑下列括号序列[([][])]要求成对出现,但可以嵌套进一步考虑算术表达式中的括号，只允许大(花)括号中套中括号、中括号中套小括号{[()]}数据结构14回文游戏顺读与逆读字符串一样(不含空格)例如：inimadamimadam算法读入字符串去掉空格（原串）压入栈原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文数据结构15走迷宫O1234567890123456789入口出口数据结构16地图着色问题地图着色问题12345671223414334231#紫色2#黄色3#红色4#绿色(1)(2)(4)(5)(6)(7)(3)已经证明，地图可以只用四种颜色着色邻接矩阵R[7][7]123456710000100111110101011010110101101100100110000000001234567数据结构17#表达式求值运算规则：从左到右先乘除、后加减先括号内、后括号外表达式实例a*b+ca+b*ca+(b*c+d)/e操作数栈和运算符栈例计算2+4-3*6算法见教材P53.2#操作数运算符2+#42+#6#6-#36-#36*-#636*-#186-#-12#-*##数据结构18第三节队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)数据结构19队列的抽象描述数据结构20双端队列定义：限定插入和删除操作可在表的两端进行的线性表。a1a2a3…………………….an端1端2入队出队入队出队数据结构21链队列用链表表示的队列称链队列。头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^数据结构22链队列基本操作数据结构23链队列基本操作算法实现设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1数据结构24队列的顺序表示队列作为线性表，也可以用顺序存储结构存储。除了可以用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需附设两个指针front和rear分别指向队头元素和队尾元素的位置。front=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[++front];数据结构25顺序队列存在的问题设数组维数为M，则-当front=-1,rear=M-1时，当再次有元素入队时发生溢出——真溢出当front-1,rear=M-1时，当再次有元素入队时发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;重复利用已经用过的空间数据结构26循环队列基本思想：把队列sq设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;实现：利用“模”运算入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];队满、队空判定条件0M-11frontrear数据结构27循环队列插入与删除012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front队空：front==rear队满：front==rear数据结构28循环队列插入与删除入队voiden_cycque(intsq[],intfront,intrear,intx){if(((rear+1)%M)==front)printf(overflow);else{rear=(rear+1)%M;sq[rear]=x;}}出队intde_cycque(intsq[],intfront,intrear,int*q){if(front==rear)return(0);else{front=(front+1)%M;*q=sq[front];return(1);}}