数据结构-3栈和队列.ppt

文档介绍：?选做题目:假设某机场共有m次航班,第i次航班有ni个座位,且每次航班达到一个目的机场。设计一个满足该机场需要的用户定票、退票程序。∧∧∧∧∧∧姓名身份证号目的地0 126 861 282 168票数航班号M-1链式存储每个订票者信息,构成一个结点(如图示)。所有订同一航班的旅客结点形成一个双链表。当订票成功时,航班总票数减去订票数。退票时,要检验退票数与订票数是否相符。顺序存储从数据结构上看,栈和队列也是线性表,不过是两种特殊的线性表:?栈只允许在表的一端进行插入或删除操作;?队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而,栈和队列也可以被称作为操作受限的线性表。通过本章的学****读者应能掌握栈和队列的逻辑结构和存储结构,以及栈和队列的基本运算以及实现算法。本章学****导读第三章栈和队列栈的定义和特点:?定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶(top),表头—栈底(bottom),不含元素的空表称空栈;?特点:先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)(Stack)关于“栈”要掌握的操作?栈的构造:顺序或链式;?空栈的判断:TOP==BOTTOM;?入栈或进栈(push):栈的插入操作;?出栈或退栈(pop):栈的删除操作。练****假设有线性表(a b c d ),按顺序输入一个栈进行处理。问能否得到下列几种输出序列注意:每个元素只能进一次栈,也只能退一次栈。bcad; cadb;dcba;abcd;cdba;bdac;cbda;bacd;dbca;cdab;adcb;acbd;1、栈的存储结构?顺序栈一维数组s[M]top=0123450空栈栈顶top,指向实际栈顶后的空位置,初值为0top123450进栈Atop出栈栈满BCDEF设数组长度为Mtop=0,栈空,此时出栈,则下溢(underflow)top=M,栈满,此时入栈,则上溢(overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空用C语言实现栈的顺序存储表示如下:typedefstruct {SElemType*base;SElemType*top;intstacksize;} SqStack ;3 2 1 0 a b c d进栈99栈顶端basetop退栈生成一个空栈功能:在内存构成一个名字为S的空栈。Void InitStack(SqStack*s) {S->base = (SElemType* ) malloc(STACK_INIT_SIZE*sizeof(SElemType));if (!S->base) exit(0); // 分配空间失败S->top = S->base; // 栈顶指示器初值S->stacksize = STACK_ INIT_ SIZE; }注意:此时栈顶指示器与栈底指示器的值相等。即指示栈中同一位置。也就是M个连续空间的第一个空间的地址。进栈运算( PUSH )?对于一个非空栈,栈顶指示器top始终是在当前栈顶数据元素位置加1的位置上。?用C语言编写的算法如下:Status Push (SqStack*S, SElemType e) {if (S->top – S->base >= S->stacksize) { //判预分空间是否用完S->base =( SElemType*)realloc(S->base, (S->stacksize+STACKINCREMENT)*sizeof(SElemType)); if (!S->base) exit ( ); // 空间分配失败S->top =S->base +S->stacksize; // 修改栈顶指示器S->stacksize + =STACKINCREMENT; }*(s->top ++) = e; // 把数据进栈后TOP再加1}出栈运算(pop)把栈顶上的元素删除(即最后进栈的数据)。用C语言编写的算法如下:void pop(SqStack*S, SElemType*e) { if (S->top == S->base) return; // 栈空*e = *(--S->top);//当前栈顶指示器减1位置上的数据删除return; }