数据结构超级有用文件课件

1、数 据 结 构 Data Structure主讲人： 刘 玮第三章 栈和队列栈(Stack)3.1栈的应用3.2递归3.3队列(Queue)3.43.1 栈限定只能在表的一端进行插入和删除操作的线性表。3.1.1 栈的定义其中a1为栈底元素(bottom) an为栈顶元素(top)a1a2an进 栈出 栈topbottom栈顶：允许插入和删除的一端栈底：不允许插入和删除的一端特点：先进后出(LIFO)例：有三个元素按a，b，c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列？c b ac a ba b ca c bb c ab a c3.1 栈3.1.2 栈的抽象数据类型ADTADT

2、 Stack 数据对象: D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitStack ( &S) : 栈的初始化 DestoryStack(&S) : 销毁栈S Push ( &S, e) :进栈 Pop (&S ) : 出栈 GetTop (S ): 取栈顶元素 IsEmpty (S): 判栈空否 3.1 栈3.1.3 栈的表示和实现-顺序存储结构：顺序栈(Sequential Stacks)-链式存储结构：链栈(Linked Stacks)1、顺序栈1) 存储特点： 利用一组地址连续的存储单元依次存

3、放栈元素 附设指针top指示栈顶元素在顺序栈中的位置2) 顺序栈的表示 typedef struct SElemType *base； SElemType *top； int stacksize； SqStack#define STACK_INIT_SIZE 100;typedef struct SElemType dataSTACK_INIT_SIZE； int top； SqStackbasetopAbasetopBAbasetopDCBAbasetoptop=0Atop=1BAtop=2DCBAtop=4空栈栈满1、顺序栈3) 基本操作的实现 栈的初始化 进栈（PUSH） 出栈（POP）

4、 栈的初始化 算法思想：构造一个空栈，设置栈的参数Status InitStack(SqStack &S) S.base = (SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; 进栈（PUSH） 算法思想 首先判断栈满？ 若栈满，则不能进栈操作; 数据元素入栈;栈顶指针加1。a5a4a3a2a1topa6baseStatus Push(SqStack &S, SEl

5、emType e) if(S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT *sizeof(SElemType); if(!S.base) exit(OVERFLOW)； S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *(S.top+)=e； return OK； 1、顺序栈 出栈（POP） 算法思想 首先判断栈空？ 栈顶指针减1，数据元素出栈a5a4a3a2a1topa6Status Pop(SqStac

6、k &S, SElemType &e) if(S.top=S.base) return ERROR； e=*(-S.top); return OK； 2、链栈1）存储特点是一种特殊形式的单链表（插入、删除操作限定在表一端进行）链式栈无栈满问题，空间可扩充2、链栈2) 链栈的表示（C语言描述） typedef struct int len； SNode *top； LStack； typedef struct SNode SElemType data； struct SNode *next； SNode； 进栈（PUSH）.topp=(SNode *)malloc(sizeof(SNode);p

7、ep-data = e;p-next = top;top = p;top 出栈（POP）.tope = p-data;S.top = p-next;free(p);p = S.top;if(!StackEmpty(S) return ERROR;petop顺序栈和链栈的比较时间性能: 相同，都是常数时间O(1)。空间性能： 顺序栈:有元素个数的限制和空间浪费的问题。 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，产生结构性开销。总之，当栈的使用过程中元素个数变化较大时或不清楚栈元素个数时，用链栈适宜；反之，应该采用顺序栈。3.2 栈的应用3.2.1

8、数制转换问题 对于输入的任意一个非负十进制整数，打印输出与其等值的N进制数。原理：即用该十进制数值除以n，并保留其余数；重复此操作，直到该十进制数值为0。最后将所有的余数反向输出就是所对应的N进制数值。（692）10 = （1010110100）2（159）10 = （237）8例：把十进制数159转换成八进制数。void Decimal_Binary() ListStack S; InitStack(&S); scanf(“%d”,data); while(data) Push(S,data%8); data/=8; while(!StackEmpty(S) Pop(S,data); pri

9、ntf(“%d”,data) 3.2.2 回文游戏（顺读与逆读字符串一样）算法思想: 读入字符串； 去掉空格（原串）； 压入栈 原串字符与出栈字符依次比较； 若不等，非回文； 若直到栈空都相等，则为回文。3.2.3 括号匹配的检验 括号匹配检验算法，即检查表达式或者语句中的 , ,( )等括号是否成对出现。其算法是各种编译器中的基本组成部分。 例如：表达式 a=a+b-(d-c(b+d) 设置一个工作栈 工作栈stack 依次读入表达式中的每个字符 若是左括号（(,），则将其入栈； 若是右括号（），）： 若工作栈stack为空栈，则错误返回； 若工作栈stack不为空：若栈顶元素与当前字符不匹

10、配则错误退出；否则将栈顶元素出栈；算法思想： 表达式读取完毕，若栈非空则错误退出；3.2.4 表达式求值 表达式的组成： 操作数（operand）：常数、变量。 运算符（operator）: 算术运算符、关系运算符和逻辑运算符。 界限符（delimiter）：左右括弧和表达式结束符。 算术运算的规则： 先乘除后加减 先左后右 先括弧内后括弧外例：4+2*3-10/5 =4+6-10/5 =10-10/5 =10-2 =8 设置两个工作栈 运算符栈OPTR，运算符栈的栈底为表达式的起始符#。 操作数栈OPND，操作数为空栈。 依次读入表达式中的每个字符 若是操作数则进OPND栈； 若是运算符，则

11、和OPTR中的栈顶元素做比较在操作。 若运算符优先级高于OPTR中的栈顶元素，则运算符入栈； 若运算符优先级低于OPTR中的栈顶元素，则从OPND栈顶弹出两个操作数，与OPTR中的栈顶元素做运算，并将运算结果入OPND； 若运算符优先级等于OPTR中的栈顶元素，则将OPTR中的栈顶元素出栈。算法思想： 直至表达式求值完毕。例：计算2+4-3*6OperandType Evaluate_Expression() InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c = getchar(); while(c!=# | GetTop(OPTR)!=#)

12、if(!In(c,OP) Push(OPND,c); c=getchar(); else switch (Precede(GetTop(OPTR),c) case : Pop(OPTR,theta); break; Pop(OPND,b); Pop(OPND,a); Push(OPND，Operate(a,theta,b); break; /switch return GetTop(OPND);3.2.5 迷宫求解43121234567891012345678910yx算法思想： 当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事： 将所有的实参、返回地址等信息传递给

13、被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 而从被调用函数返回调用函数之前，应该完成： 保存被调用函数的计算结果； 释放被调用函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。 由于函数的运行规则是：后调用先返回，因此各函数占有的存储管理应实行“栈式管理”。3.2.6 函数的调用3.3 递归3.3.1 递归的概念递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。以下三种情况常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的

14、3.3 递归3.3.2 定义递归求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n*Factorial (n-1);例如，阶乘函数3.3 递归3.3.3 数据结构递归 某些数据结构就是递归的。例如，链表就是一种递归的数据结构。链表结点LNode的定义由数据域data和指针域next组成；而指针域next则又由LNode定义。 不仅单链表，广义表、树和图也都是递归结构。所以关于它们的一些算法，也需要用递归思想实现。3.3 递归3.3.4 解法递归 有些问题只能用递归方法来解决，若不用递归就只能用枚举法

15、了。 一个典型的例子就是“Tower of Hanoi”问题：婆罗门神庙里有一个塔台，台上有3根柱子(假设叫x,y,z)。在x柱上有64个金盘，每一个都比下面的小。把x柱上的金盘全部移到z柱上，移动的条件是：一次只能移动一个金盘，移动过程中大盘子只能放在小盘子下面。 汉诺塔(Tower of Hanoi)问题有A、B、C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔，编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循以下原则： 每次只能移动一个圆盘； 圆盘可在三个塔座上任意移动； 任何时刻，每个塔座上不能将大盘压倒小盘上。 算法思想 n=1时，直接把圆

16、盘从A移到C。 把上面n-1个圆盘从A移动到B； 然后将n号盘从A移到C； 将n-1个盘从B移到C。 n1时， 即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。main() int m; printf(“Input number of disks”); scanf(“%d”, &m); printf(“Step: %3d disk”, m); hanoi(m,a,b,c);(0)Void hanoi(int n, char x, char y, char z)(1)(2) if(n=1)(3) move(1,x,z);(

17、4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) 递归的思想 我们把这种解决问题的“先分解再求解”的策略称为“分而治之”(divide and conquer)的策略，简称“分治法”。一个问题如能用“分治法”解决，就可以用递归算法实现。 前面看到的阶乘函数、幂函数、单链表的、汉诺塔等问题的求解过程都蕴含着分而治之或先分解再求解的思想，因此都能用递归方法解决。而在其他学科中，如“运筹学”和“现代控制论”中的“动态规划”也是采用了分治的思想。 递归的结构 递归本身具有一定的特点，它是自己调用自己的过程，

18、只不过每次调用时，问题的规模更小而已。 任何一个递归函数都由两部分组成 初始情况：又叫结束条件或终止条件，即可以直接解决而无需再做递归的简单输入 递归部分：包含对本算法的递归调用，但每次调用时传递进去的参数较上次调用时传递进去的参数更接近于初始情况。 递归函数的基本结构就非常清晰了，它是一个if-else结构。3.4 队列限定只能在表的一端进行插入，在表另一端进行删除。3.4.1 队列的定义约定其中a1为队头元素(front) an为队尾元素(rear)队尾：允许插入的一端队头：允许删除的一端特点：先进先出(FIFO)a1a2a3an出队列入队列队头队尾3.4 队列3.4.2 队列的抽象数据类

19、型ADTADT Queue 数据对象: D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitQueue ( &Q) : 初始化队列 DestoryQueue (&Q) : 销毁队列 EnQueue (&Q, e) :进队列 DeQueue (&Q, &e): 出队列 GetHead (Q, &e): 取队头元素值 QueueEmpty (S): 判队列空否 3.4 队列3.4.3 队列的表示和实现-顺序存储结构：线性队列、循环队列-链式存储结构：链队列1、链队列存储特点：队头在链头，队尾在链尾。设置队头、队

20、尾指针分别保存队头、队尾地址1、链队列链队列的表示结点类型：typedef struct Qnode QElemtype data; struct Qnode *next; Qnode,*Queueptr; 链队列类型typedef struct Queueptr front; Queueptr rear; LinkQueue; 1、链队列基本操作的实现 构造队列1、链队列入队列 分析 首先为插入队列元素p分配空间； 为插入队列元素赋值； 数据元素入队尾 Q.rear-next = p; Q.rear = p; p1、链队列出队列 分析 首先判断队列是否为空？ 删除队头第一个元素； p = Q

21、.front-next; Q.front-next = p-next; 若只有一个元素，删除后为空队列， 需修改队尾指针； Q.rear = Q.front;2、线性队列1）存储特点利用地址连续的存储单元依次存放队列各元素。设置两个指示器 front, rear 分别指示队头、队尾。2）线性队列的表示#define MAXQSIZE 100typedef struct QElemtyope *base; int front; int rear; SqQueue; 2、线性队列 存在问题：“假溢出”现象！ 解决方法：循环队列FEDCfrontrearCDEFfrontrearG3、循环队列1）存储特点 同上存储队列的数组被当作