数据结构与算法 课件 第1--3章 绪论、 线性表、 栈和队列.ppt

栈顶位置top的两种定义方式本书采用(a)的方式初始化栈、清空栈判空、判满入栈入栈时，新元素放在element[top]处，然后top加1第1个元素入栈时放在数组下标为0的位置因为数组空间有限，最大容量是maxSize，所以入栈时需要判定栈不能是满的出栈出栈时，需要先将top值减1，然后将element[top]处的值通过参数x返回出栈时需要判定栈不是空的获取栈顶元素效率top的值既是保存下一个入栈元素的位置，也是栈中所含元素个数的计数器因为栈的入栈操作及出栈操作都在栈顶进行，所以入栈、出栈、获取栈顶元素时都不需要移动栈中已有的元素，故时间复杂度都是O(1)判定栈空及栈满等操作的时间复杂度也是O(1)例3-6也可以将数组下标最大的一端作为栈底若一个栈保存在数组V[0..n-1]中，初始时栈顶指针top为n，则下列选项中，能够正确实现x入栈操作的语句序列是（）。A．top=top+1;V[top]=x;B．V[top]=x;top=top+1;C．top=top-1;V[top]=x;D．V[top]=x;top=top-1;答案为C对顶栈数组的两个端点分别作为两个栈的栈底左侧栈占用数组0到k的单元，栈顶在k+1位置右侧栈占用数组m-1到h的单元，栈顶在h-1位置此时必须满足kh，才能保证两个栈不会重叠栈S1入栈时，栈顶值增大，出栈时栈顶值减小栈S2刚好相反，入栈时栈顶值减小，出栈时栈顶值增大例2-14设双向静态有序链表L保存在含8个元素的数组A中，表头结点在A[0]中。依次执行下列操作，画出每个操作后得到的数组A（1）初始化L（2）将序列618,205,103,501,781,910依次插入到L中，建立双向静态有序链表（3）从L中依次删除元素501、103（4）将元素301插入到L中（1）初始化L（2）插入数据序列后（3）删除两个元素后（4）再插入一个元素后第五节单链表的应用创建单链表从键盘读入值创建单链表从数组读入值创建单链表查找单链表倒数第k个结点如果知道了单链表的长度，那么访问倒数第k个结点就很容易了。假设单链表长度为n，则倒数第k个结点即是第n-k+1个结点使用两个指针front和rear，均从表头开始同步向表尾方向移动初始时，先令front前进k步，当个“排头兵”这样front和rear指向的位置相距k个结点然后两个指针同步前进当front到达表尾时，rear即位于倒数第k个结点查找倒数第k个结点程序查找单链表的中间结点使用两个指针，并同时从表头开始向表尾方向移动，一个指针一次走两步，另一个指针一次走一步。这样，当“排头兵”指针到达表尾时，后面的指针即指向链表的中间结点。与findKth函数中一样，两个指针分别是front和rear程序将单链表逆置对于单链表的其他结点，让middle所指结点的next域指向left所指结点，即left所指结点的原后继（middle所指）变为它的新前驱。然后，三个指针依次后移一个位置当所有结点中的next域都转向后，再将head所指的头结点链接在表头处程序验证程序全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第三章栈和队列学习目标掌握栈和队列的逻辑定义、特点及基本操作，了解它们的逻辑表示方法及使用场掌握栈的两种存储方式及各自的特点，掌握两种方式下基本操作的实现及复杂度分析掌握队列的两种存储方式及各自的特点，掌握两种方式下基本操作的实现，重点掌握循环队列的实现及复杂度分析掌握结合了栈和队列特点的双端队列了解线性表与栈及队列的关系灵活运用栈和队列的基本操作，设计算法解决与此相关的实际问题本章主要内容栈12进一步讨论栈与队列3队列4栈和队列的应用栈和队列是线性表的两个经典特例，它们都是操作受限的线性表，即操作的位置需要满足各自的条件因为这些条件的特殊性，使得实现各自的操作时过程简捷，效率更高第一节栈栈是一种特殊的线性表，它的特殊性体现在操作的位置上。在含n个元素的线性表中进行插入或删除时，操作位置可以有n+1个或n个当将操作位置限定在线性表的同一端时，得到的数据结构就是栈它是一种受限的线性表栈的定义及其基本操作定义3-1栈（stack）是限定仅在一端进行插入和删除的线性表能进行插入和删除的这一端称为栈顶，线性表的另一端称为栈底在栈顶插入一个元素称为入栈（push）、进栈或压栈，从栈顶删除一个元素称为出栈（pop）或退栈栈的表示将栈S表示为：S=(a0,a1,…,an-1)

通常指定an-1一端为栈顶，a0一端是栈底栈中元素个数n称为栈的长