数据结构chapt3课件

1、第三章 栈和队列3.1栈的表示和实现3.2递归过程3.3队列的表示和实现栈和队列的逻辑结构、物理结构，以及它们之间的相互关系；定义与之相适应的运算；设计相应的算法；分析算法的效率。一、栈的概念 栈（stack）是插入和删除操作限定在表尾进行的线性表。 栈的逻辑表示为：S =（a1,a2, ,an） 表尾元素an称为栈顶(top) 表头元素a1称为栈底(bottom)不含元素的空表称为空栈栈的运算特性是后进先出(Last In First Out-LIFO) 或先进后出(First In Last Out-FILO) 3.1 栈的表示和实现 3.1 栈的表示和实现二、栈的基本运算InitStac

2、k(&S) 初始化操作，设定一个空栈SStackEmpty(S) 判栈S是否为空函数（true/false）Push(&S, x) 入栈操作，在栈S顶部插入元素x， 相当于线性表的INSERT(L, n+1, x)Pop(&S,&e) 出栈函数，若S不空，则返回栈顶元素， 并删除栈顶元素；否则返回空元素NULL， 相当于线性表的DELET(L, n)GetTop(S,&e) 取栈顶元素函数， 与Pop(S,&s)的差别在不删除栈顶元素， 相当于线性表的GET(L, n)Stacklength(S) 求S栈中当前元素个数函数， 相当于线性表的LENGTH(L)ClearStack(&S) 置栈空

3、操作 3.1 栈的表示和实现 DestroyStack(&S) 释放一个已经存在的栈。StackTraverse(S,visit() 从栈底到栈顶，依次对其中元素作 visit( )操作。一旦visit失败，则整个操作失败。3.1 栈的表示和实现三. 栈的表示和实现1. 顺序栈的存储结构描述及出入栈运算 /=ADT Stack的表示与实现= /-栈的顺序存储表示- #define STACK_INIT_SIZE 100 /存储空间初始分配量 #define STACKINCREMENT 10 /存储空间分配增量 typedef struct SElemType *base;/在栈构造之前和销毁

4、之后，值为NULL SElemType *top; /栈顶指针 int stacksize; /当前已分配空间，已元素为单位 /SqStack; S-elemi表示第i个进栈的元素 S-elemS-top 表示栈顶元素 当S-top = 0 表示空栈 当S-top = S-base+S-stacksize 表示栈满3.1 栈的表示和实现初始化栈函数InitStack(&S)的实现算法思想：分配一个连续存储空间，成功，则栈顶和栈底都指向同一个地址，否则，均为NULL。 Status InitStack(SqStack &S) /构造一个空栈S S.base=(SElemType *)malloc

5、(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW);/存储分配失败 S.top=S.base; S.Stacksize=STACK_INIT_SIZE; return OK; /InitStack3.1 栈的表示和实现取栈顶元素函数GetTop(S，&e)的实现算法思想：若栈不为空；则将栈顶元素取出，并由e返回，否则，返回ERROR。 Status GetTop(SqStack S,SElemType &e) /若栈不空，则用e返回栈顶元素，并返回OK，否则返回ERROR。 if(S.top=S.base) return

6、 ERROR; e=*(S.top-1); return OK; /GetTop3.1 栈的表示和实现入栈函数Push(&S，e)的实现算法思想：若栈满则追加分配存储空间；否则将e入栈，并返回OK。 Status Push(SqStack &s, SElemType e) /插入元素e为新的栈顶元素 if(S.top-S.base=S.Stacksize)/栈满，追加分配存储空间 S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLO

7、W);/存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCDEMENT; *S.top+ = e; return OK; /Push3.1 栈的表示和实现出栈函数Pop(&S,&e)的实现算法思想：若栈空则返回空元素NULL； 否则由e返回栈顶元素，同时删除栈顶元素。 Status Pop(SqStack &S, SElemType &e) /若栈不空，则删除栈顶元素，用e 返回其值，并返回/OK,否则，返回ERROR if(S.top=S.base) return ERROE; e=*-S.top; return OK; /Pop3.

8、1 栈的表示和实现2. 链栈的存储结构描述 typedef struct SNode SElemtype data; struct SNode *next; SNode,*SLinkList;3.2 栈的应用 1.数制转换对于任意进制与十进制之间的转换原理为: N=(N div d)d+N mod d 则有转换 (1348)10=(2504)8转换过程为: N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 23.2 栈的应用 则对于任意进制与十进制之间的转换算法可以为: void conversion( ) /对于输入的任意一个非负十进制整数，打

9、印出与其等值的对应进制数 InitStack (&S); /构造空栈 scanf (N); scanf(d); while (N) push (S, N % d); /d为8，则为对应八进制数 N=N/d; while(!StackEmpty(S) Pop (&S, e); printf(e); /conversion3.2 栈的应用 2. 括号匹配的检验 ( ) 3. 行编辑程序 whli#ilr#e(s#*s) /#表示退格符号 outchaputchar(*s=#+);/表示退行符 4. 迷宫求解问题 5. 表达式求值3.3 递归过程 递归是栈的另一个重要应用，也是程序设计的一个强有力的

10、工具。1. 应用递归的原因和领域 递归定义 1 当n = 0 阶乘 n!= n*(n-1)! 当n 0 0 n = 0 Fibonacci数列 Fib(n)= 1 n = 1 Fib(n-1)+Fib(n-2) n 1 递归结构 后面将要介绍的二叉树，广义表结构本身固有递归特性，操作也可递归描述。用递归求解更简单 例：计算两个非负整数a*b的算法1. 递归方式：a*b = b+ (a-1)*b int mul1(int a，int b) if(a = = 0) return0; else return( b + mul1( a-1，b) /mul13.3 递归过程2. 迭代方式：a*b = a

11、个b之和 int mul2(int a，int b) z= 0； for( i=1;i1：若能将压在n号盘上的n-1个圆盘按规则移至Y，然后把n号盘从X移到Z上，最后再将Y上的n-1个圆盘按规则移至Z上。原问题为：hanoi(n，X，Y，Z) 化简为：hanoi(n-1，X，Z，Y) move(X，n，Z) 把X上的n号盘移到Z上 hanoi(n-1，Y，X，Z)3.3 递归过程 void hanoi(int n, char X, char Y, char Z) if(n=1) move(X，1，Z) else hanoi(n-1，X，Z，Y)； move (X， n， Z)； hanoi(n

12、-1，Y，X，Z) ; / hanoi一、队列的概念队列（Queue）是限定仅在一端插入,另一端删除的线性表。允许插入的一端叫队尾( rear),允许删除的一端叫队头(front),不含元素的空表称为空队列队列的运算特性是先进先出(First In First Out-FIFO) 3.4 队列的表示和实现出队列入队列a1 a2 . an队头队尾二、队列的基本运算 InitQueue（&Q） 初始化操作，设置一个空队列 QueueEmpty(Q) 判定队列是否为空函数 （TRUE/FALSE） EnQueue(&Q，e) 入队列操作，队尾插入元素x DeQueue(&Q,&e) 出队函数,删除队

13、头元素,用e返回 GetHead(Q,&e) 取队头元素 ClearQueue(&Q) 队列置空操作 QueueLength(Q) 求队列Q当前元素个数 DestroyQueue(&Q) 销毁已经存在的队列 QueueTraverse(Q,visit( ) 遍历队列函数 3.4 队列的表示和实现三、队列的链式存储结构链队列 1存储结构 链队列需要队头和队尾两个指针来确定。typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针 Queue

14、Ptr rear; /队尾指针LinkQueue;给链队列添加个头结点，并令头指针指向头结点。空链队列有头尾指针均指向头结点即q-front = q-rear 3.4 队列的表示和实现next = NULL; /? return OK; /InitQueue 3.4 队列的表示和实现思考：在判断存储是否分配成功中，可以用Q-rear来判断吗？ 3撤消队列算法 Status DestroyQueue(LinkQueue &Q) /销毁队列Q while( Q.front) Q.rear = Q.front-next; free(Q.front); Q.front=Q-rear; return O

15、K; /DestroyQueue 3.4 队列的表示和实现 4 入队算法 Status EnQueue(LinkQueue &Q,QElemType e) /插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; /EnQueue 3.4 队列的表示和实现 2出队算法 Status DeQueue(LinkQueue &Q, QElemType &e) /若队列不空，则删除Q的队头元素，用e

16、返回其值，并返回OK /否则，返回ERROR if(Q.front = = Q.rear) return ERROR; p=Q.front-next； e=p-data; Q.front-next=p-next; if(Q.rear= =p) Q.rear=Q.front; free(p); return OK; /DeQueue删除时的三种情形：a.删除前已空；b.删除前只有一个结点，删除后为空队列；c.其他情形（删除前结点数1） 3.4 队列的表示和实现思考：在什么情况下出队要修改Q-rear (队尾)指针？为什么？四、队列的顺序存储结构1. 一般顺序存储结构 用一个向量来存放队列元素，并

17、用两个指针来指示队头和队尾。并约定：头指针Q.front总是指向队头元素的前一个位置；尾指针Q.rear指向队尾元素。 3.4 队列的表示和实现SqQueue Q;初始时：Q.front = Q.rear = 0空队列条件：Q.front= Q.rear出队时：if(Q.rear = Q.front)return ERROR(队空） else Q.front= Q.front+1入队时：if(Q.rear = maxsize) return ERROR(队满) elxe Q.rear= Q.rear+1； Q.elemQ.rear= x； 3.4 队列的表示和实现 3.4 队列的表示和实现考虑

18、队满条件，即当Q-rear=maxsize时，是否整个存储空间都已占用？maxsize1Q.rearQ.front此时，Q-rear=maxsize 且队满。maxsize1Q.rearQ.front此时，尽管Q.rear = maxsize,但队列中实际元素并不足maxsize个，仍有Q.front个空闲单元，称这种情形为“假溢出”。 3.4 队列的表示和实现2. 循环队列结构 把队列视为一个循环表，即Q.elemMAXSIZE之后是数组的第一个元素。 #define MAXQSIZE 100/最大队列长度 typedef struct QElemType *base;/初始化的动态分配存储

19、空间 int front;/头指针(相当于游标) int rear;/尾指针 /SqQueue; 可采用取余数运算来实行循环队列的运算: 入队时：Q.rear =(Q.rear+1)mod MAXSIZE ； Q.elemQ.rear =x； 出队时： Q.front =(Q.front+1) mod MAXSIZE if(Q.rear+1= =maxsize) Q.rear =0 else Q.rear =Q.rear+1此时, 队空. 有Q.front=Q.rear此时, 队满. 有Q.front=Q.rear例. m=5,初始状态和操作过程如下: 3.4 队列的表示和实现ABCEDQ.frontQ.rearABCEDQ.frontQ.rearF将F入队EQ.frontQ.rear连续4次出队Q.frontQ.rear再出队 队满和队空时，均有Q.front=Q.rear。 因此，只凭Q.front=Q.rear还无法区分是满还是空。 如何判定队满还是空？是循环队列要解决的新问题。 3.4 队列的表示和实现方法一 ：用一个计数变量来记载队列中的元素个数。 初始化队列时c=0; 当入队时，计数变量1（