数据结构第八讲.ppt
数据结构第八讲桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹 桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹本章要点本章要点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队列的链式存储结构（链队）队列的链式存储结构（链队）链队的数据结构定义如下：typedef struct qnodeElemtype data;struct qnode*next;QTYPE;typedef struct qptrQTYPE*front,*rear;SQUEUESQUEUE LQ LQfrontrear 1 2 3 LQfrontrear桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹链队基本运算的实现链队基本运算的实现(1)1）队列的初始化void InitQueue(SQUEUE*LQ)QTYPE*p;p=(QTYPE*)malloc(sizeof(QTYPE);p-next=NULL;LQ-front=LQ-rear=p;LQfrontrearP 桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹链队基本运算的实现（链队基本运算的实现（2）2）入队int EnQueue(SQUEUE*LQ,Elemtype x)QTYPE*s;s=(QTYPE*)malloc(sizeof(QTYPE);s-data=x;s-next=LQ-rear-next;LQ-rear-next=s;LQ-rear=s;return 1;LQfrontrear 1 2 3 LQfrontrear桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹链队基本运算的实现（链队基本运算的实现（3）3）判队空int Empty（SQUEUE*LQ）if(LQ-front=LQ-rear)return 1;else return 0;LQfrontrear桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹4)出队int OutQueue(SQUEUE*LQ,Elemtype*x)if(Empty(SQ)printf(“n Queue is empty”);return 0;p=LQ-front-next;*x=p-data;LQ-front-next=p-next;if(LQ-front-next=NULL)LQ-rear=LQ-front;free(p);return 1;链队基本运算的实现（链队基本运算的实现（4）1 2 3 LQfrontrearpp桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹链队基本运算的实现（链队基本运算的实现（5）5)取队头元素int GetHead(SQUEUE*LQ,ElemType*x)if(Empty(LQ)printf(“n Queue is empty”);return 0;*x=LQ-front-next-data;return 1;1 2 3 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递归程序的执行过程递归程序的执行过程3.3.3递归的应用举例递归的应用举例3.4队队列列3.4.1队列的定义和运算队列的定义和运算3.4.2队列的顺序存储结构及基本运算的实现队列的顺序存储结构及基本运算的实现3.4.3队列的链式存储结构及基本运算的实现队列的链式存储结构及基本运算的实现3.4.4队列的应用队列的应用举例举例本章小结本章小结桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹1、问题叙述、问题叙述假假设设在在周周末末舞舞会会上上，男男士士们们和和女女士士们们进进入入舞舞厅厅时时，各各自自排排成成一一队队。跳跳舞舞开开始始时时，依依次次从从男男队队和和女女队队的的队队头头上上各各出出一一人人配配成成舞舞伴伴。若若两两队队初初始始人人数数不不相相同同，则则较较长长的的那那一一队队中中未未配配对对者者等等待待下下一一轮轮舞舞曲曲。现现要要求求写写一一算算法法模模拟拟上上述述舞伴配对问题。舞伴配对问题。3.4.4 队列的应用舞伴问题桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹2、问题分析、问题分析先先入入队队的的男男士士或或女女士士亦亦先先出出队队配配成成舞舞伴伴。因因此此该该问问题题具具体体有有典典型型的的先进先出特性，可用队列作为算法的数据结构。先进先出特性，可用队列作为算法的数据结构。在在算算法法中中，假假设设男男士士和和女女士士的的记记录录存存放放在在一一个个数数组组中中作作为为输输入入，然然后后依依次次扫扫描描该该数数组组的的各各元元素素，并并根根据据性性别别来来决决定定是是进进入入男男队队还还是是女女队队。当当这这两两个个队队列列构构造造完完成成之之后后，依依次次将将两两队队当当前前的的队队头头元元素素出出队队来来配配成成舞舞伴伴，直直至至某某队队列列变变空空为为止止。此此时时，若若某某队队仍仍有有等等待待配配对对者者，算算法法输输出出此此队队列列中中等等待待者者的的人人数数及及排排在在队队头头的的等等待待者者的的名名字字，他他（或或她她）将将是下一轮舞曲开始时第一个可获得舞伴的人。是下一轮舞曲开始时第一个可获得舞伴的人。具体分析见实例：具体分析见实例：桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹本章小结：本章小结：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队列的应用队列的应用举例举例桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院赵莹莹赵莹莹本章作业本章作业P76:四:1,6
