数据结构复习(3).ppt

《数据结构复习(3).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据结构复习（3）第三章栈和队列重点：栈和队列的基本特征，表示与实现难点：递归、循环队列栈和队列是两种特殊的线性表。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称运算受限制的线性表。栈和队列-----WangWenjie栈（1）定义栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈和队列-----WangWenjie栈（2）只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(top)，

2、另一端称为栈底(bottom)特点后进先出(LIFO)栈和队列-----WangWenjie栈（3）基本操作创建一个空栈；判断栈是否为空栈；往栈中插入（或称推入）一个元素；从栈中删除（或称弹出）一个元素；求栈顶元素的值。栈和队列-----WangWenjie栈的表示和实现由于栈是运算受限的线性表，因此线性表的存储结构对栈也是适用的，只是操作不同而已。两种存储结构顺序存储链式存储栈和队列-----WangWenjie顺序栈（1）利用顺序存储方式实现的栈称为顺序栈。base空栈a进栈b进栈atopbasetopbas

3、etopab约定：top指向栈顶元素的下一个位置栈和队列-----WangWenjie顺序栈（2）basee进栈f进栈溢出e出栈edcbatopbasetopbasetopedcbadcba栈和队列-----WangWenjie顺序栈（3）说明1.对于顺序栈，入栈时，首先判栈是否满了。栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。2.出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。栈和队列-----WangWenjie链栈用链式存储结构实现

4、的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相同。无栈满问题(除非分配不出内存),空间可扩充栈顶----链表的表头可以不必引入头结点约定：top指向栈顶元素所在的结点N^top栈和队列-----WangWenjie栈与递归的实现递归的定义递归的对象：一个对象部分地包含它自己，或用它自己给自己定义。如树的定义递归的过程：一个过程直接或间接地调用自己递归的应用定义(阶乘)、数据结构(表)、问题求解(Hanoi塔)栈和队列-----WangWenjie栈与递归的实现–阶乘函数定义是递归的求解阶乘函数

5、的递归算法longfact(longn){if(n==0)return1;//递归结束条件elsereturnn*fact(n-1);//递归的规则}栈和队列-----WangWenjie栈与递归的实现–阶乘函数主程序main():fact(4)参数传递结果返回递归调用回归求值fact(4):计算4*fact(3)返回24fact(3):计算3*fact(2)返回6fact(2):计算2*fact(1)返回2fact(1):计算1*fact(0)返回1fact(0):直接定值为1返回1栈和队列-----WangW

6、enjie栈与递归的实现–数据结构数据结构是递归的--表空表非空表:(表头元素+除表头元素以外的剩余元素)查找表L中是否有元素值eLinkListsearch(LinkListL,ElemTypee)//L为不带头结点的单向非循环链表{if(L==NULL)returnNULL;elseif(L->data==e)returnL;elsereturnsearch(L->next,e);}栈和队列-----WangWenjie栈与递归的实现–Hanoi塔问题求解是递归的—Hanoi塔voidhanoi(intn,c

7、hara,charb,charc)n-圆盘数a-源塔座b-中介塔座c-目标塔座搬动方法n=1,a->cn>1:hanoi(n-1,a,c,b)a->chanoi(n-1,b,a,c)注意用递归调用的结果，不关注该结果如何获得的细节栈和队列-----WangWenjie栈与递归的实现–递归/回溯递归与回溯—N皇后问题在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指：找到这n个皇后的互不攻击的布局栈和队列-----WangWenjie栈与递归的实现

8、–N皇后问题1#主对角线3#主对角线5#主对角线♛♛♛0#次对角线2#次对角线4#次对角线6#次对角线1#次对角线3#次对角线5#次对角线0#主对角线2#主对角线4#主对角线6#主对角线♛01230123k=i+jk=n+i-j-1栈和队列-----WangWenjie栈与递归的实现–N皇后问题基本思路依次为每一行确定该行皇后的合法位置安放第i行皇后时，需要在列的方向从0