数据结构第八讲.ppt

《数据结构第八讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本章要点3.1栈3.1.1栈的定义及运算3.1.2栈的顺序存储结构及基本运算的实现3.1.3栈的链式存储结构及基本运算的实现3.2栈的应用3.2.1中缀表达式3.2.2中缀表达式转换为等价的后缀表达式3.2.3后缀表达式及求值3.3栈与递归3.3.1递归与递归程序的设计3.3.2递归程序的执行过程3.3.3递归的应用举例3.4队列3.4.1队列的定义和运算3.4.2队列的顺序存储结构及基本运算的实现3.4.3队列的链式存储结构及基本运算的实现3.4.4队列的应用举例本章小结3.4.3队列的链式存储结构（链队）链队的数据结构定义如下

2、：typedefstructqnode{Elemtypedata;structqnode*next;}QTYPE;typedefstructqptr{QTYPE*front,*rear;}SQUEUESQUEUELQ^LQfrontrear123^LQfrontrear链队基本运算的实现(1)1）队列的初始化voidInitQueue(SQUEUE*LQ){QTYPE*p;p=(QTYPE*)malloc(sizeof(QTYPE));p->next=NULL;LQ->front=LQ->rear=p;}LQfrontrearP^

3、链队基本运算的实现（2）2）入队intEnQueue(SQUEUE*LQ,Elemtypex){QTYPE*s;s=(QTYPE*)malloc(sizeof(QTYPE));s->data=x;s->next=LQ->rear->next;LQ->rear->next=s;LQ->rear=s;return1;}^LQfrontrear123^LQfrontrear链队基本运算的实现（3）3）判队空intEmpty（SQUEUE*LQ）{if(LQ->front==LQ->rear)return1;elsereturn0;}^L

4、Qfrontrear4)出队intOutQueue(SQUEUE*LQ,Elemtype*x){if(Empty(SQ)){printf(“Queueisempty”);return0;}p=LQ->front->next;*x=p->data;LQ->front->next=p->next;if(LQ->front->next==NULL)LQ->rear=LQ->front;free(p);return1;}链队基本运算的实现（4）123^LQfrontrearpp链队基本运算的实现（5）5)取队头元素intGetHead

5、(SQUEUE*LQ,ElemType*x){if(Empty(LQ)){printf(“Queueisempty”);return0;}*x=LQ->front->next->data;return1;}123^LQfrontrear本章要点3.1栈3.1.1栈的定义及运算3.1.2栈的顺序存储结构及基本运算的实现3.1.3栈的链式存储结构及基本运算的实现3.2栈的应用3.2.1中缀表达式3.2.2中缀表达式转换为等价的后缀表达式3.2.3后缀表达式及求值3.3栈与递归3.3.1递归与递归程序的设计3.3.2递归程序的执行过

6、程3.3.3递归的应用举例3.4队列3.4.1队列的定义和运算3.4.2队列的顺序存储结构及基本运算的实现3.4.3队列的链式存储结构及基本运算的实现3.4.4队列的应用举例本章小结1、问题叙述假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。3.4.4队列的应用——舞伴问题2、问题分析先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法

7、的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。具体分析见实例：本章小结：3.1栈3.1.1栈的定义及运算3.1.2栈的顺序存储结构及基本运算的实现3.1.3栈的链式存储结构及基本运算的实现3.2栈的应用3.2.1中缀表达式3.2.

8、2中缀表达式转换为等价的后缀表达式3.2.3后缀表达式及求值3.3栈与递归3.3.1递归与递归程序的设计3.3.2递归程序的执行过程3.3.3递归的应用举例3.4队列3.4.1队列的定义和运算3.4.2队列的顺序存储结构及基本运算的实现3.4.3队