数据结构 第3章.ppt

《数据结构 第3章.ppt》由会员分享，可在线阅读，更多相关《数据结构 第3章.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构第第3章章【学习目标】【学习目标】1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。问题中正确选用它们。2.2.熟练掌握栈类型的两种实现方法。熟练掌握栈类型的两种实现方法。3.3.熟练掌握循环队列和链队列的基本操作实现算法。熟练掌握循环队列和链队列的基本操作实现算法。4.4.理解递归算法执行过程中栈的状态变化过程。理解递归算法执行过程中栈的状态变化过程。【知识点】【知识点】顺序栈、链栈、循环队列、链队列顺序栈、链栈、循环队列、链队列注意它们的基本操作实现时的特殊情况，如栈满和栈空、注意它们的基本操

2、作实现时的特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法队满和队空的条件以及它们的描述方法。【学习指南】【学习指南】1数据结构 栈栈和和队列队列是在程序设计中被广泛使用的两种线性数是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，据结构，它们的特点在于基本操作的特殊性，栈必须按栈必须按后进先出后进先出的规则进行操作的规则进行操作，而，而队列必须按队列必须按先进先出先进先出的规则进行操作的规则进行操作。和线性表相比，它们的插入和删除操。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。作受更多的约束和限定，故又称为限定性的线性

3、表结构。和线性表相比，从和线性表相比，从数据结构数据结构的角度看，它们都的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是同外，主要区别是对插入和删除操作的对插入和删除操作的限定限定。2数据结构 线性表：线性表：Insert(L,i,x)Delete(L,i)(1in+1)(1in)栈：栈：Insert(L,n+1,x)Delete(L,n)队列：队列：Insert(L,n+1,x)Delete(L,1)插插入入删删除除线性表允许

4、在表内任一位置进行插入和删除；线性表允许在表内任一位置进行插入和删除；栈只允许在表尾一端进行插入和删除；栈只允许在表尾一端进行插入和删除；队列只允许在表尾一端进行插入，在表头一端进行删队列只允许在表尾一端进行插入，在表头一端进行删除。除。3数据结构栈和队列是两种特殊的线性结构，特点：栈和队列是两种特殊的线性结构，特点：栈：栈：后进先出后进先出 如铁路调度站如铁路调度站队列：先进先出队列：先进先出 如购物排队问题如购物排队问题栈顶栈顶栈底栈底队尾队尾队首队首4数据结构3.1.1栈的类型定义栈的类型定义 栈（栈（Stack）是限定只能在表的一端进行插入和删除操作的是限定只能在表的一端进行插入和删除

5、操作的线性表。在表中，允许插入和删除的一端称作线性表。在表中，允许插入和删除的一端称作栈顶栈顶(top)，不，不允许插入和删除的另一端称作允许插入和删除的另一端称作栈底栈底(bottom)。通常称通常称往栈顶插入元素的操作为往栈顶插入元素的操作为入栈入栈，称，称删除栈顶元素的操作为删除栈顶元素的操作为出栈出栈。因为后入栈的元素先于先入。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种栈的元素出栈，故被称为是一种后后进先出进先出的结构，因此又称的结构，因此又称LIFO（LastInFirstOut的缩写）表的缩写）表如左图所示的铁路调度站表示栈的特点如左图所示的铁路调度站表示栈的特点 5数据

6、结构类型定义如下类型定义如下：ADTStack数据数据对对象：象：Dai|ai ElemSet,i=1,2,.,n,n0数据关系：数据关系：R1|ai-1,ai D,i=2,.,n约定约定an端为栈顶，端为栈顶，a1端为栈底端为栈底。基本操作：基本操作：InitStack(&S)构造一个空栈构造一个空栈S。DestroyStack(&S)初始条件：栈初始条件：栈S已存在。操作结果：栈已存在。操作结果：栈S被销毁。被销毁。ClearStack(&S)初始条件：栈初始条件：栈S已存在。操作结果：将已存在。操作结果：将S清为空栈。清为空栈。StackEmpty(S)判空，通常以它作为循环结束的条件判

7、空，通常以它作为循环结束的条件GetTop(S,&e)取栈顶元素，只以取栈顶元素，只以e返回栈顶元素，并不从栈中删除返回栈顶元素，并不从栈中删除Push(&S,e)入栈操作入栈操作Pop(&S,&e)出栈操作，不仅以出栈操作，不仅以e返回栈顶元素，并将它从栈中删除。返回栈顶元素，并将它从栈中删除。ADTStack6数据结构3.1.2栈的存储表示和操作的实现栈的存储表示和操作的实现一、顺序栈类型的定义一、顺序栈类型的定义和线性表类似，栈也有两种存储表示，其顺序存储结构简称为和线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。顺序栈。和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最

8、和顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间，多元素的存储空间，base为这个存储空间的基地址，也即一维为这个存储空间的基地址，也即一维数组的地址。数组的地址。从名称来讲，从名称来讲，“栈顶指针栈顶指针”意为指示栈顶元素在栈中的位置，但意为指示栈顶元素在栈中的位置，但它的值实际是栈中元素的个数，和顺序表中的它的值实际是栈中元素的个数，和顺序表中的length值的意义值的意义相同。相同。为了应用方便，这个为了应用方便，这个最大空间的容量最大空间的容量应由使用这个顺序栈的应由使用这个顺序栈的程序员决定，它的默认值和顺序表的默认值相同。程序员决定，它的默认值和顺序表的默认值

9、相同。7数据结构顺序栈的结构顺序栈的结构top指向压栈时下一个元素将要存放的位置。指向压栈时下一个元素将要存放的位置。出栈时出栈时top减一指向弹栈时下一个元素的取值位置。减一指向弹栈时下一个元素的取值位置。栈空的条件：栈空的条件：top=base栈满的条件：栈满的条件：top-base=stacksizetoptopbase空栈空栈basetopABCABCbase满栈满栈DE栈的表示和实现栈的表示和实现非空非满栈非空非满栈8数据结构顺序表示顺序表示#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct SEl

10、emType*base;SElemType *top;int stacksize;SqStack;其中其中stacksize表示栈当前可以使用的最大容量。表示栈当前可以使用的最大容量。Base为栈底，为栈底，Top为栈顶。栈顶指针指向栈顶元素为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置）的下一个位置（即下次压栈时元素所放的位置）9数据结构基本操作的实现基本操作的实现：初始化栈初始化栈 Status InitStack(SqStack&S)/构造一个空栈构造一个空栈 S.base=(SElemType*)malloc (STACK_INIT_SIZE*sizeof(SEl

11、emType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack10数据结构压栈压栈: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)ex

12、it(OVERFLOW);S.top =S.base+S.stacksize;S.stacksize+=STACKINCREMENT;/if *S.top+=e;return OK;/Push11数据结构弹栈弹栈:Status Pop(SqStack&S,SElemType&e)/从栈顶读取数据放入从栈顶读取数据放入e内，栈中下一元素所内，栈中下一元素所 /在位置成为新的栈顶在位置成为新的栈顶 if（S.top=S.base）return ERROR;/栈空栈空 e=*-S.top;return OK;/Pop 注意注意top的操作顺序和值的变化。的操作顺序和值的变化。压栈：压栈：valuet

13、op;top+;弹栈：弹栈：top-;top-value;12数据结构Status GetTop(SqStack S,SElemType&e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;思考：语句思考：语句e=*(S.top-1);改为改为e=*(-S.top);是否正是否正确？确？13数据结构二、链栈二、链栈链栈即为栈的链式存储结构。链栈即为栈的链式存储结构。链栈的定义更简单，结点结构链栈的定义更简单，结点结构和单链表中的结点结构相同，和单链表中的结点结构相同，无须重复定义。注意无须重复定义。注意链栈中指链栈中指针的方向是从栈顶指向

14、栈底的，针的方向是从栈顶指向栈底的，这正好和单链表是相反的。这正好和单链表是相反的。14数据结构能否将链栈中的指针方向反过来，从栈底到栈顶？能否将链栈中的指针方向反过来，从栈底到栈顶？不行不行，如果反过来的话，删除栈顶元素时，为修改其，如果反过来的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。前驱指针，需要从栈底一直找到栈顶。因为链栈的操作是线形表链式存储结构的特例，因因为链栈的操作是线形表链式存储结构的特例，因此，相关操作可以自己总结出来。此，相关操作可以自己总结出来。15数据结构压栈的处理：压栈的处理：p=malloc(Lnode);p-next=s-next;s-next

15、=p;弹栈的处理弹栈的处理:p=s-next;s-next=s-next-next;spp栈的链式表示：栈的链式表示：假设以首结点作为栈顶，链带有头结点。假设以首结点作为栈顶，链带有头结点。16数据结构补充：一种新的栈的类型定义#define StackSize 100 typedef char datatype;typedef struct datatype datastacksize;int top;seqstack;SeqStack*s;思考：如何判断空栈和满栈思考：如何判断空栈和满栈17数据结构top6 5 4 3 2 1 0 -1思考：如何判断空栈和满栈思考：如何判断空栈和满栈18数

16、据结构 设设S S是是SeqStackSeqStack类型的指针变量。若栈底类型的指针变量。若栈底位置在向量的低端，即位置在向量的低端，即sdata0sdata0是栈底元是栈底元素，那么栈顶指针素，那么栈顶指针stopstop是正向增加的，即是正向增加的，即进栈时需将进栈时需将sstop加加1，退栈时需将，退栈时需将stop 减减1。因此，。因此，stoptop=stacksize-1表示栈满。当栈满时再做进栈运表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称算必定产生空间溢出，简称“上溢上溢”;当栈空时当栈空时再做退栈运算也将产生溢出，简称再做退栈运算也将产生溢出，简称“下溢下溢”。19

17、数据结构3.2、栈的应用举例、栈的应用举例 3.2.1数制转换数制转换 由于栈的操作具有后进先出的固有特性，致使栈成为程序由于栈的操作具有后进先出的固有特性，致使栈成为程序设计中的有用工具。反之，凡应用问题求解的过程具有设计中的有用工具。反之，凡应用问题求解的过程具有后进后进先出先出的天然特性的话，则求解的算法中也必然需要利用的天然特性的话，则求解的算法中也必然需要利用栈栈。十进制数十进制数N和其他和其他d进制数的转换是计算机实现计算的基本问题，进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)

18、d+Nmodd(其中：其中：div为整除运算，为整除运算，mod为求余运算为求余运算)例如：例如：(1348)10=(2504)8 N N div 8 N%8 1348 168 4 168 21 0 21 2 5 2 0 2 20数据结构假设现要编制一个满足下列要求的程序：对假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。出与其等值的八进制数。八进制的各个数位产生的顺序是从低位到高八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位的，而打印输出的顺序，一般来说应从高位到低位，这恰

19、好和计算过程相反。位到低位，这恰好和计算过程相反。21数据结构voidconversion()/对于输入的任意一个非负十进制整数，打印输出与其等值的八进对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数制数InitStack(S);/构造空栈构造空栈scanf(“%d”,N)/输入一个十进制数输入一个十进制数while(N)Push(S,N%8);/“余数余数”入栈入栈N=N/8;/非零非零“商商”继续运算继续运算/whilewhile(!StackEmpty)/和和“求余求余”所得相逆的顺序输出八进制的各位数所得相逆的顺序输出八进制的各位数Pop(S,e);printf(“%d”,

20、e);/while/conversion22数据结构2.括号匹配算法括号匹配算法 （）的配对问题。（）的配对问题。（5+（2-6）+10）+6*2 （5+（2-6）+10+6）*2 （5+2-6）+10）+6）*2 判断的标准：判断的标准：方法：见到左括号压栈，方法：见到左括号压栈，见到右括号弹栈，并和弹出的数见到右括号弹栈，并和弹出的数 据配对。据配对。课堂练习：课堂练习：假设表达式结束符为假设表达式结束符为#,试写出其算法试写出其算法23数据结构int MatchJudge()/匹配返回匹配返回1，不匹配返回，不匹配返回0 InitStack(S);scanf(“%c”,&ch);whil

21、e(ch!=#)if (ch=(|ch=|ch=)push(s,ch);if (ch=)）pop(s,e);if(e()return 0;if (ch=)pop(s,e);if(e)return 0;if (ch=)pop(s,e);if(e“”)return 0;scanf(“%c”,&ch);/while if (StackEmpty(s)return 1 else return 0;/MatchJudge24数据结构3.2.3 行编辑程序行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用输入

22、的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。户输入错误，并在发现有误时可以及时更正。字符字符“#”为删节符，删除左边一个可见字符。字符为删节符，删除左边一个可见字符。字符“”为删行符，删除当前一行。用栈来处理一行，一行结为删行符，删除当前一行。用栈来处理一行，一行结束即用户输入束即用户输入n。例如：例如：用户输入：用户输入：whli#ilr#e(s#*s)outchaputchar(*s=#+);则实际有效为：则实际有效为：while(*s)putchar(*s+);25数据结构void LineEdit()Initstack(S);ch=getchar(

23、);while(ch!=EOF)while(ch!=EOF&ch!=n)switch(ch)case#:Pop(s,c);case :Clearstack(s);default:Push(S,ch);ch=getchar();ClearStack(s);if(ch!=eof)ch=gethar();DestroyStack(s);26数据结构3.2.5表达式求值：表达式求值：任何一个表达式都是由任何一个表达式都是由操作数操作数(operand)、运算符、运算符(operator)和界限符和界限符(delimiter)组成，其中，操作数可以组成，其中，操作数可以是常数也可以是被说明为变量或常量的

24、标识符；运算符可是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符等三类；基以分为算术运算符、关系运算符和逻辑运算符等三类；基本界限符有左右括弧和表达式结束符等。为了叙述简洁，本界限符有左右括弧和表达式结束符等。为了叙述简洁，在此仅限于讨论只含二元运算符的算术表达式。可将这种在此仅限于讨论只含二元运算符的算术表达式。可将这种表达式定义为：表达式定义为：表达式表达式=操作数操作数运算符运算符操作数操作数操作数操作数=简单变量简单变量|表达式表达式简单变量简单变量=标识符标识符|无符号整数无符号整数算术运算的规则算术运算的规则是：是：先乘除后加减、先左后右和

25、先括弧内后先乘除后加减、先左后右和先括弧内后括弧外括弧外。则对表达式进行运算不能按其中运算符出现的先后。则对表达式进行运算不能按其中运算符出现的先后次序进行次序进行27数据结构算符优先算法：利用运算优先关系的规定来实算符优先算法：利用运算优先关系的规定来实 现对表达式的编译或解释执行。现对表达式的编译或解释执行。表达式的组成：操作数表达式的组成：操作数+算符（操作符算符（操作符+界限符）界限符）算符优先关系算符优先关系 +_*/()#+_*/(#=28数据结构算符优先算法的实现算符优先算法的实现1）置操作数栈为空栈，表达式起始符为运算符栈的）置操作数栈为空栈，表达式起始符为运算符栈的栈底。栈底

26、。2）依次读入表达式的元素，）依次读入表达式的元素，a.若是操作数若是操作数,则进操作数栈。则进操作数栈。b.若是运算符则同运算符栈栈顶栈元素进行优先级若是运算符则同运算符栈栈顶栈元素进行优先级比较，比较，b.1若栈顶元素优先级高，则弹出该运算符，若栈顶元素优先级高，则弹出该运算符，取其操作数进行相应运算，之后结果进操作数栈，再将取其操作数进行相应运算，之后结果进操作数栈，再将此算符和算符新的栈顶元素比较。此算符和算符新的栈顶元素比较。b.2否则，将此运算符压栈。否则，将此运算符压栈。b.3否则，则是一对括号，要脱括号否则，则是一对括号，要脱括号29数据结构OperandType Evalua

27、teExpression()InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,C);c=getchar();else switch(Precede(GetTop(OPTR),c)case:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch /while return GetTop(OPND);/program 30数据结构

28、步骤OPTR栈OPND栈输入字符主要操作1 3*(7-2)#PUSH(OPND,3)23 *(7-2)#PUSH(OPTR,*)3*3 (7-2)#PUSH(OPTR,()4*(3 7-2)#PUSH(OPND,7)5*(-37 -2)#PUSH(OPTR,-)6*(-37 2)#PUSH(OPND,2)7*(372 )#Operate(7,-,2)8*(35 )#POP(OPTR)去括号9*35#operate(3,#,5)1015#RETURN(GETTOP(OPND)31数据结构思考将从键盘输入的字符序列逆置输出32数据结构Status reverse()while(ch=getchar

29、()!=n)/从键盘输入字符，直到输入换行符为止从键盘输入字符，直到输入换行符为止 Push(S,ch);/将输入的每个字符入栈将输入的每个字符入栈while(!StackEmpty(S)/依次退栈并输出退出的字符依次退栈并输出退出的字符 Pop(S,ch);putchar(ch);putchar(n);33数据结构3.3、递归函数的实现、递归函数的实现 在程序设计中，经常会碰到多个函数的嵌套调用。和汇编程序设计中主在程序设计中，经常会碰到多个函数的嵌套调用。和汇编程序设计中主程序和子程序之间的链接和信息交换相类似，在高级语言编制的程序中，调程序和子程序之间的链接和信息交换相类似，在高级语言编

30、制的程序中，调用函数和被调用函数之间的链接和信息交换也是由编译程序通过栈来实施的。用函数和被调用函数之间的链接和信息交换也是由编译程序通过栈来实施的。当一个函数在运行期间调用另一个函数时，在运行该被调当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：用函数之前，需先完成三件事：1)将所有的实在参数、返回地址等信息传递给被调用函数保存；将所有的实在参数、返回地址等信息传递给被调用函数保存；2)为被调用函数的局部变量分配存储区；为被调用函数的局部变量分配存储区；3)将控制转移到被调用函数的入口。将控制转移到被调用函数的入口。而从被调用函数返回调用函数之前，应该完成：而从

31、被调用函数返回调用函数之前，应该完成：1)保存被调函数的计算结果；保存被调函数的计算结果；2)释放被调函数的数据区；释放被调函数的数据区；3)依照被调函数保存的返回地址将控制转移到调用函数。依照被调函数保存的返回地址将控制转移到调用函数。34数据结构 当多个函数嵌套调用时，由于函数的运行规则是：当多个函数嵌套调用时，由于函数的运行规则是：后调后调用先返回用先返回，因此各函数占有的存储管理应实行，因此各函数占有的存储管理应实行栈式管理栈式管理。假设主函数调用函数假设主函数调用函数A，函数，函数A又调用函数又调用函数B，显然，显然，在函数在函数B运行期间主函数和函数运行期间主函数和函数A占用的存储

32、都不能被覆占用的存储都不能被覆盖，反之，当函数盖，反之，当函数B运行结束，它所占用的存储区便可释运行结束，它所占用的存储区便可释放，同时因为程序控制转移到函数放，同时因为程序控制转移到函数A，当前程序访问的数，当前程序访问的数据自然就是函数据自然就是函数A占用的存储区了占用的存储区了35数据结构递归程序的执行例：例：1voidditui(intn)2if(n1)3printf(n);4ditui(n-1);5/if6/ditui1234561234Ditui(4)Ditui(5)1234Ditui(3)1234Ditui(2)1256Ditui(1)565656输出2输出3输出4输出536数据

33、结构1 void ditui2(int n)2 if(n1)3 ditui2(n-1);4 printf(n);5 /if6 /ditui21234561234Ditui(4)Ditui(5)1234Ditui(3)1234Ditui(2)1256Ditui(1)565656输出2输出3输出4输出537数据结构递归函数的实现递归函数的实现 一个递归函数的运行过程类似于多个函数的嵌套调用，一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于差别仅在于调用函数和被调用函数是同一个函数调用函数和被调用函数是同一个函数。为了。为了保证保证每一层的递归调用每一层的递归调用都是对都是对本层本层的数据

34、进行操作，的数据进行操作，在执行递归函数的过程中需要一个在执行递归函数的过程中需要一个递归工作栈递归工作栈。它的。它的作作用用是是:1、将递归调用时的实在参数和函数返回地址传递给下一层将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数执行的递归函数；2、保存本层的参数和局部变量，以便从下一层返回时重新保存本层的参数和局部变量，以便从下一层返回时重新使用它们。使用它们。递归执行过程中所占用的数据区，称之为递归执行过程中所占用的数据区，称之为递归工作栈递归工作栈。每一层的递归参数等数据合成一个记录，称之为每一层的递归参数等数据合成一个记录，称之为递归工作记录递归工作记录。栈顶记录指示当

35、前层的执行情况，称之为栈顶记录指示当前层的执行情况，称之为当前活动记录当前活动记录。递归工作栈的栈顶指针，称之为递归工作栈的栈顶指针，称之为当前环境指针当前环境指针。38数据结构在此，称调用递归函数的主函数为在此，称调用递归函数的主函数为第第0层层，则从主函数，则从主函数调用递归函数被称为进入递归函数的调用递归函数被称为进入递归函数的第第1层层，从递归函数，从递归函数的的第第i层层递归调用本函数被称为进入递归函数的递归调用本函数被称为进入递归函数的第第i+1层层。显然，当递归函数执行到第显然，当递归函数执行到第i层时，从第层时，从第1层到第层到第i-1层的数层的数据都必须被保存下来，以便一层一

36、层退回时继续使用。递归据都必须被保存下来，以便一层一层退回时继续使用。递归函数执行过程中每一层所占用的内存数据区合起来就是一个函数执行过程中每一层所占用的内存数据区合起来就是一个递归工作栈递归工作栈。下面用汉诺塔问题来说明递归程序和堆栈的使用下面用汉诺塔问题来说明递归程序和堆栈的使用设主程序中有如下的调用语句：设主程序中有如下的调用语句：inti;.10hanoi(3,a,b,c);voidhanoi(intn,charx,chary,charz);39数据结构void hanoi(int n,char x,char y,char z)/将塔座将塔座x上按直径由小到大且至上而下编号为上按直径由

37、小到大且至上而下编号为1至至n/的的n个圆盘按规则搬到塔座个圆盘按规则搬到塔座z上，上，y可用作辅助塔座。可用作辅助塔座。1 2if(n=1)3 move(x,1,z);/将编号为1的圆盘从 x 移到 z 4else5hanoi(n-1,x,z,y);/将 x 上编号为1至 n-1 的圆盘移到 y,z 作辅助塔6move(x,n,z);/将编号为 n 的圆盘从 x 移到 z7 hanoi(n-1,y,x,z);/将 y 上编号为1至 n-1 的圆盘移到 z,x 作辅助塔 40数据结构(3,a,b,c)(2,a,c,b)(1,a,b,c)ab(1,c,a,b)a c(1,b,c,a)(2,b,a

38、,c)bc(1,a,b,c)41数据结构队列的定义队列的定义：一种运算受限的线性表。它只允许在表的一端：一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为进行插入，而在另一端进行删除。允许删除的一端称为队头队头(front)，允许插入的一端称为，允许插入的一端称为队尾队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作员总是先离开队列。因此队列亦称作先进先出先进先出(First In First Out)的线性表，简称的线性表，简称FIFO表。表。当队列中

39、没有元素时称为空队列。在空队列中依次加入元素当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，之后，a1是队头元素，是队头元素，an是队尾元素。显然退出队是队尾元素。显然退出队列的次序也只能是列的次序也只能是a1,a2,an，也就是说队列的修改是依先进，也就是说队列的修改是依先进先出的原则进行的。先出的原则进行的。3.4 队列队列3.4.1抽象数据类型队列的定义抽象数据类型队列的定义出队出队入队入队队头队头队尾队尾a1,a2,an42数据结构队列的抽象数据类型定义：队列的抽象数据类型定义：ADT Queue 数据对象：数据对象：D=ai|aiElemSet,I=1,2,

40、.n,n=0 数据关系：数据关系：R1=|a i-1,ai D,I=2,n 基本操作：基本操作：InitQueue(&Q);DestoryQueue(&Q);ClearQueue(&Q);QueueEmpty(Q);QueueLength(Q);GetHead(Q,&e);EnQueue(&Q,e);DeQueue(&Q,&e);QueueTraverse(Q,visit()43数据结构双端队列是限定插入和删除操作在表的两双端队列是限定插入和删除操作在表的两端进行的线性表。端进行的线性表。在实际应用中，可有输出受限的双端队列在实际应用中，可有输出受限的双端队列和输入受限的双端队列。和输入受限的

41、双端队列。如果限定双端队列从某个端点插入的元素如果限定双端队列从某个端点插入的元素只能从该端点删除，则就蜕化成两个栈底只能从该端点删除，则就蜕化成两个栈底相邻接的栈相邻接的栈44数据结构 用链表表示的队列简称为链队列，它是限制仅在表头删除和用链表表示的队列简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针是，一个链队列由一个头指针q.frontq.front和一

42、个尾指针和一个尾指针q.rear共同确共同确定。定。datadata二、链队列队列的链式存储结构q.frontq.rear队头队头队尾队尾链队列示意图链队列示意图空队列空队列45数据结构链式队列链式队列 typedef struct Qnode QElemType data;struct Qnode*next;Qnode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;46数据结构/基本操作接口（函数声明）基本操作接口（函数声明）voidInitQueue(Queue&Q);/构造一个空队列构造一个空队列Qvoid

43、DestroyQueue(Queue&Q);/销毁队列销毁队列Q，Q不再存在不再存在voidClearQueue(Queue&Q);/将将Q置为空队列置为空队列boolQueueEmpty(QueueQ);/若队列若队列Q为空队列，则返回为空队列，则返回TRUE，否则返回，否则返回FALSEintQueueLength(QueueQ);/返回队列返回队列Q中元素个数，即队列的长度中元素个数，即队列的长度boolGetHead(QueueQ,ElemType&e);/若队列不空，则用若队列不空，则用e返回返回Q的队列头元素，并返回的队列头元素，并返回TRUE；否则返回；否则返回FALSEvoid

44、EnQueue(Queue&Q,ElemType&e);/在当前队列的尾元素之后插入元素在当前队列的尾元素之后插入元素e为新的队列尾元素为新的队列尾元素boolDeQueue(Queue&Q,ElemType&e);/若队列不空，则删除当前队列若队列不空，则删除当前队列Q中的头元素，用中的头元素，用e返回其值，并返回返回其值，并返回TRUE；/否则返回否则返回FALSEvoidQueueTraverse(QueueQ,void(*visit(ElemType)/依次对依次对Q的每个元素调用函数的每个元素调用函数visit()，一旦，一旦visit()失败，则操作失败。失败，则操作失败。47数据

45、结构Status InitQueue(LinkQueue&Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;48数据结构Status DestroyQueue(LinkQueue&Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;49数据结构 Status EnQueue(LinkQueue&Q,QElemType x)p=(QueuePtr

46、)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);P-data=x;P-next=NULL;Q.rear-next=p;Q.rear=p;50数据结构出队：出队：Status DeQueue(LinkQueue&Q,QElemType&e)当删除的是队列中的最后一个元素时当删除的是队列中的最后一个元素时:要修改队尾指针要修改队尾指针Q.frontpa1a2anQ.rearQ.frontpanQ.rear51数据结构由于一般情况下，出队列的操作只涉及队头元素，因此不需由于一般情况下，出队列的操作只涉及队头元素，因此不需要修改队尾指针，但当链队列中只有一个数据元

47、素时，队头要修改队尾指针，但当链队列中只有一个数据元素时，队头元素恰好也是队尾元素，当它被删除之后，队尾指针就元素恰好也是队尾元素，当它被删除之后，队尾指针就悬空悬空了，待下次再做入队操作时，就要产生指针的了，待下次再做入队操作时，就要产生指针的悬空访问悬空访问的的错误，因此在这种情况下必须同时修改尾指针。错误，因此在这种情况下必须同时修改尾指针。52数据结构思考QueueEmpy(LinkQueue Q)应如何实现？应如何实现？GetHead(LinkQueue Q,QElemType&e)应应如何实现？如何实现？53数据结构Status QuequeEmpty(LinkQueue Q)If

48、(qfront=NULL&qrear=NULL)return TRUE;return FALSE;54数据结构和顺序栈相类似，在利用顺序分配存储结构实现队列时，和顺序栈相类似，在利用顺序分配存储结构实现队列时，除了用一维数组描述队列中数据元素的存储区域之外，除了用一维数组描述队列中数据元素的存储区域之外，尚需设立两个指针尚需设立两个指针 front 和和 rear 分别指示分别指示“队头队头”和和“队队尾尾”的位置。为了叙述方便，在此约定：的位置。为了叙述方便，在此约定：初始化建空队初始化建空队列时，令列时，令 front=rear=0，每当插入一个新的队尾元素，每当插入一个新的队尾元素后，尾

49、指针后，尾指针 rear 增增1；每当删除一个队头元素之后，；每当删除一个队头元素之后，头指针增头指针增1。因此，在非空队列中，头指针始终指向队因此，在非空队列中，头指针始终指向队头元素，而尾指针指向队尾元素的头元素，而尾指针指向队尾元素的下一个下一个位置。如位置。如下图所示。下图所示。循环队列循环队列 55数据结构#define MAXQSIZE 100 typedef struct QElemType*base;int front;int rear;SqQueue;其中其中base为连续空间首地址，为连续空间首地址，front为队首，为队首，rear为队尾。为队尾。注意和顺序栈的定义的区别

50、与联系注意和顺序栈的定义的区别与联系队列的顺序表示与实现队列的顺序表示与实现56数据结构非循环队列：非循环队列：如何判断空队如何判断空队?如何判断满队如何判断满队?由于队首的移动特征，实际采用循环队列。由于队首的移动特征，实际采用循环队列。rearfront空队空队front非空非非空非满队满队1rearABCC满队满队DECfront非空非非空非满队满队2Drearrearfront非循环队列：非循环队列：57数据结构循环队列：Maxsize-1 01frontrear这种循环意义下的加这种循环意义下的加1 1操作可以描述为：操作可以描述为：if(i+1=MAXSIZE)if(i+1=MAX