数据结构第八讲.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队列的链式存储结构 链队 链队的数据结构定义如下 typedefstructqnode Elemtypedata structqnode next QTYPE typedefstructqptr QTYPE front rear SQUEUESQUEUELQ 链队基本运算的实现 1 1 队列的初始化voidInitQueue SQUEUE LQ QTYPE p p QTYPE malloc sizeof QTYPE p next NULL LQ front LQ rear p LQ front rear P 链队基本运算的实现 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 1 2 3 LQ front rear 链队基本运算的实现 3 3 判队空intEmpty SQUEUE LQ if LQ front LQ rear return1 elsereturn0 4 出队intOutQueue SQUEUE LQ Elemtype x if Empty SQ printf nQueueisempty 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 1 2 3 LQ front rear p p 链队基本运算的实现 5 5 取队头元素intGetHead SQUEUE LQ ElemType x if Empty LQ printf nQueueisempty return0 x LQ front next data return1 本章要点 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递