第3章-特殊线性表课件.ppt

1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第第3章章 特殊线性表特殊线性表栈、队列和串栈、队列和串本章的基本内容是：本章的基本内容是：三种特殊的线性表三种特殊的线性表栈、队列、串栈、队列、串从数据结构角度看，栈和队列是从数据结构角度看，栈和队列是操作受限操作受限的线的线性表，他们的逻辑结构相同。性表，他们的逻辑结构相同。串是重要的非数值处理对象，它是以串是重要的非数值处理对象，它是以字符字符作为作为数据元素的线性表。数据元素的线性表。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 特殊线性表特殊线性表栈栈栈的逻辑结构栈的逻辑结构空栈：空栈：不含任何数据元素的栈。不含

2、任何数据元素的栈。（a1,a2,an）栈：栈：限定仅在限定仅在表尾表尾进行插入和删除操作的进行插入和删除操作的线性表线性表。栈顶栈顶栈底栈底允许插入和删除的一端称为栈顶，另一端称为栈底。允许插入和删除的一端称为栈顶，另一端称为栈底。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶 特殊线性表特殊线性表栈栈插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶栈的示意图栈的示意图数据结构（数据结构（C版）版）清华大学出版社清华大学出版社栈的操作特性：栈的操作特性：后进先出后进先出a1a2a3入栈入栈出栈出

3、栈栈底栈底栈顶栈顶 特殊线性表特殊线性表栈栈插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈的示意图栈的示意图数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？特殊线性表特殊线性表栈栈栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶 情况情况1：栈的逻辑结构栈的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 特殊线性表特殊线性表栈栈栈底栈底栈顶栈顶ab栈顶栈顶c栈

4、顶栈顶出栈序列：出栈序列：c出栈序列：出栈序列：c、b出栈序列：出栈序列：c、b、a例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 情况情况1：数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 特殊线性表特殊线性表栈栈栈底栈底栈顶栈顶ab栈顶栈顶出栈序列：出栈序列：b 情况情况2：例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，

5、则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 特殊线性表特殊线性表栈栈栈底栈底a出栈序列：出栈序列：b出栈序列：出栈序列：b、c出栈序列：出栈序列：b、c、ac栈顶栈顶栈顶栈顶注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈

6、的逻辑结构 情况情况2：数据结构（数据结构（C版）版）清华大学出版社清华大学出版社栈的抽象数据类型定义栈的抽象数据类型定义 特殊线性表特殊线性表栈栈ADT StackData 栈中元素具有相同类型及后进先出特性，栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitStack 前置条件：栈不存在前置条件：栈不存在 输入：无输入：无 功能：栈的初始化功能：栈的初始化 输出：无输出：无 后置条件：构造一个空栈后置条件：构造一个空栈 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社DestroyStack 前置条件：栈已存在前置

7、条件：栈已存在 输入：无输入：无 功能：销毁栈功能：销毁栈 输出：无输出：无 后置条件：释放栈所占用的存储空间后置条件：释放栈所占用的存储空间Push 前置条件：栈已存在前置条件：栈已存在 输入：元素值输入：元素值x 功能：在栈顶插入一个元素功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素后置条件：如果插入成功，栈顶增加了一个元素栈的抽象数据类型定义栈的抽象数据类型定义 特殊线性表特殊线性表栈栈数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Pop 前置条件：栈已存在前置条件：栈已存在 输入：无输入：

8、无 功能：删除栈顶元素功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素后置条件：如果删除成功，栈减少了一个元素GetTop 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：读取当前的栈顶元素功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变后置条件：栈不变栈的抽象数据类型定义栈的抽象数据类型定义 特殊线性表特殊线性表栈栈数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Empty 前置条件：栈已

9、存在前置条件：栈已存在 输入：无输入：无 功能：判断栈是否为空功能：判断栈是否为空 输出：如果栈为空，返回输出：如果栈为空，返回1，否则，返回，否则，返回0 后置条件：栈不变后置条件：栈不变endADT栈的抽象数据类型定义栈的抽象数据类型定义 特殊线性表特殊线性表栈栈数据结构（数据结构（C版）版）清华大学出版社清华大学出版社栈的顺序存储结构及实现栈的顺序存储结构及实现 顺序栈顺序栈栈的顺序存储结构栈的顺序存储结构如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？0 1 2 3 4 5 6 7 8a1确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。特殊线性表特殊线性表栈栈附设指

10、针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。top数据结构（数据结构（C版）版）清华大学出版社清华大学出版社出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top=-1 0 1 2 3 4 5 6 7 8 特殊线性表特殊线性表栈栈a1topa2topa3top栈满：栈满：top=MAX_SIZE栈的顺序存储结构及实现栈的顺序存储结构及实现 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 顺序栈类的声明顺序栈类的声明const int MAX_SIZE=100;template class seqStack public:seqStack();

11、seqStack();void Push(T x);T Pop();T GetTop();bool Empty();private:T dataMAX_SIZE;int top;特殊线性表特殊线性表栈栈数据结构（数据结构（C版）版）清华大学出版社清华大学出版社顺序栈的实现顺序栈的实现入栈入栈template void seqStack:Push(T x)if(top=MAX_SIZE-1)throw “溢出溢出”;top+;datatop=x;特殊线性表特殊线性表栈栈操作接口：操作接口：void Push(T x);时间复杂度？时间复杂度？数据结构（数据结构（C版）版）清华大学出版社清华大学出

12、版社顺序栈的实现顺序栈的实现出栈出栈template T seqStack:Pop()if(top=-1)throw “溢出溢出”;x=datatop-;return x;特殊线性表特殊线性表栈栈操作接口：操作接口：T Pop();时间复杂度？时间复杂度？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社两栈共享空间两栈共享空间 解决方案解决方案1：直接解决：为每个栈开辟一个数组空间。直接解决：为每个栈开辟一个数组空间。解决方案解决方案2：顺序栈单向延伸顺序栈单向延伸使用一个数组来存储两个栈使用一个数组来存储两个栈 特殊线性表特殊线性表栈栈在一个程序中需要在一个程序中需要同时同时使用具

13、有使用具有相同相同数据类型的数据类型的两个栈两个栈，如何顺序存储这两个栈？如何顺序存储这两个栈？会出现什么问题？如何解决？会出现什么问题？如何解决？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社两栈共享空间：两栈共享空间：使用一个数组来存储两个栈，让一个使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸的末端，两个栈从各自的端点向中间延伸。特殊线性表特殊线性表栈栈两栈共享空间两栈共享空间 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社栈栈1的底固定在下标为的底固

14、定在下标为0的一端；的一端；栈栈2的底固定在下标为的底固定在下标为StackSize-1的一端。的一端。top1和和top2分别为栈分别为栈1和栈和栈2的栈顶指针；的栈顶指针；Stack_Size为整个数组空间的大小（图中用为整个数组空间的大小（图中用S表示）；表示）；a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间两栈共享空间两栈共享空间 top2bj b2 b1栈栈1底底栈栈2底底数据结构（数据结构（C版）版）清华大学出版社清华大学出版社两栈共享空间两栈共享空间top1=-1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空

15、间 top2bj b2 b1top1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社两栈共享空间两栈共享空间top1=-1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间 top2bj b2 b1什么时候栈什么时候栈2为空？为空？top2top2=Stack_Size数据结构（数据结构（C版）版）清华大学出版社清华大学出版社两栈共享空间两栈共享空间top1=-1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间 top2bj b2 b1什么时候栈什么时候栈2为空？为空？top2=St

16、ack_Size什么时候栈满？什么时候栈满？top2=top1+1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社const int Stack_Size=100;template class BothStack public:BothStack()();BothStack()();void Push(int i,T x);T Pop(int i);T GetTop(int i);bool Empty(int i);private:T dataStack_Size;int top1,top2;两栈共享空间类的声明两栈共享空间类的声明两栈共享空间两栈共享空间数据结构（数据结构（C版）版

17、）清华大学出版社清华大学出版社1.如果栈满，则抛出上溢异常；如果栈满，则抛出上溢异常；2.判断是插在栈判断是插在栈1还是栈还是栈2；2.1 若在栈若在栈1插入，则插入，则 2.1.1 top1加加1;2.1.2 在在top1处填入处填入x；2.2 若在栈若在栈2插入，则插入，则 2.2.1 top2减减1;2.2.2 在在top2处填入处填入x；两栈共享空间两栈共享空间两栈共享空间的实现两栈共享空间的实现插入插入 操作接口：操作接口：void Push(int i,T x);数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.若是在栈若是在栈1删除，则删除，则 1.1 若栈若栈1为空

18、栈，抛出下溢异常；为空栈，抛出下溢异常；1.2 删除并返回栈删除并返回栈1的栈顶元素；的栈顶元素；2.若是在栈若是在栈2删除，则删除，则 2.1 若栈若栈2为空栈，抛出下溢异常；为空栈，抛出下溢异常；2.2 删除并返回栈删除并返回栈2的栈顶元素；的栈顶元素；两栈共享空间两栈共享空间两栈共享空间的实现两栈共享空间的实现删除删除 操作接口：操作接口：T Pop(int i);数据结构（数据结构（C版）版）清华大学出版社清华大学出版社栈的链接存储结构及实现栈的链接存储结构及实现 链栈：链栈：栈的链接存储结构栈的链接存储结构 特殊线性表特殊线性表栈栈firsta1a2anai链栈需要加头结点吗？链栈需

19、要加头结点吗？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将哪一端作为栈顶？将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。链栈不需要附设头结点。链栈不需要附设头结点。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社栈的链接存储结构及实现栈的链接存储结构及实现 栈顶栈顶栈底栈底链栈：链栈：栈的链接存储结构栈的链接存储结构 特殊线性表特殊线性表栈栈topanan-1a1firsta1a2anai两种示意图在内存中两种示意图在内存中对应同一种状态对应同一种状态topa1an-1an栈顶栈顶栈底栈底数据结构（数据结构（C版）版）清华大学出版社清华大学出

20、版社链链栈栈的的类类声声明明template class LinkStack public:LinkStack()();LinkStack()();void Push(T x);T Pop()();T GetTop()();bool Empty()();private:Node*top;特殊线性表特殊线性表栈栈数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法描述：算法描述：template void LinkStack:Push(T x)s=new Node;s-data=x;s-next=top;top=s;特殊线性表特殊线性表栈栈topanan-1a1链栈的实现链栈的实现插入

21、插入 xstop操作接口：操作接口：void Push(T x);为为什什么么没没有有判判断断栈栈满满？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社算法描述：算法描述：template T LinkStack:Pop()()if(top=NULL)throw 下溢下溢;x=top-data;p=top;top=top-next;delete p;return x;特殊线性表特殊线性表栈栈链栈的实现链栈的实现插入插入操作接口：操作接口：T Pop();topanan-1a1topp top+可以吗？可以吗？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社顺序栈和链栈的比较

22、顺序栈和链栈的比较时间性能：时间性能：相同，都是常数时间相同，都是常数时间O(1)。空间性能：空间性能：顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。域，从而产生了结构性开销。特殊线性表特殊线性表栈栈总之，当栈的使用过程中元素总之，当栈的使用过程中元素个数变化个数变化较大时，用较大时，用链栈是适宜的，反之，应该采用顺序栈。链栈是适宜的，反之，应该采用顺序栈。数据

23、结构（数据结构（C版）版）清华大学出版社清华大学出版社栈的应用举例栈的应用举例递归递归1 递归的定义递归的定义子程序（或函数）直接调用自己或通过一系列调子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种用语句间接调用自己，是一种描述问题描述问题和和解决问解决问题题的基本方法。的基本方法。2 递归的基本思想递归的基本思想问题分解：问题分解：把一个不能或不好解决的大问题转化把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解成更小的小问题，直至每个小问题都可以直接解决。解决

24、。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社3 递归的要素递归的要素 递归边界条件：递归边界条件：确定递归到何时终止，确定递归到何时终止，也称也称为递归出口；为递归出口；递归模式：大问题是如何分解为小问题的，递归模式：大问题是如何分解为小问题的，也称为递归体。也称为递归体。栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例例1 1 阶乘函数阶乘函数递归算法递归算法int fact (int n)if(n=0)return 1;else return n*fact(n-1);-*=时时当当时时当当 )!1(1!n1n1nnn栈的应用举例栈

25、的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社求解阶乘求解阶乘 n!n!的过程的过程 fact(4)计算计算 4*fact(3)计算计算 3*fact(2)计算计算 2*fact(1)计算计算 fact(1)返回返回 24返回返回 6返回返回 2返回返回1栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社递归过程与递归工作栈递归过程与递归工作栈n递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。n层层向下递归，返回次序正好相反：层层向下递归，返回次序正好相反：递归调用递归调用 n!(n-1)!(n-2)

26、!1!=1 返回次序返回次序栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社递归的经典问题递归的经典问题汉诺塔问题汉诺塔问题 在世界刚被创建的时候有一座钻石宝塔（塔在世界刚被创建的时候有一座钻石宝塔（塔A），），其其上有上有64个金碟。所有碟子按从大到小的次序从塔底堆放至个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔和塔C）。）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔上的碟子移动到塔C上去，其间

27、借助于塔上去，其间借助于塔B的帮助。每次只的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。的碟子上面。当牧师们完成任务时，世界末日也就到了。栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社汉诺塔问题的递归求解汉诺塔问题的递归求解:如果如果 n=1，则将这一个盘子直接从则将这一个盘子直接从 塔塔A移到塔移到塔 C 上。否则，执行以下三步：上。否则，执行以下三步：将塔将塔A上的上的n-1个碟子借助塔个碟子借助塔C先移到塔先移到塔B上；上；把塔

28、把塔A上剩下的一个碟子移到塔上剩下的一个碟子移到塔C上；上；将将n-1个碟子从塔个碟子从塔B借助于塔借助于塔A移到塔移到塔C上。上。栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 void Hanoi(int n,char A,char B,char C)if(n=1)Move(A,C);else Hanoi(n-1,A,C,B);Move(A,C);Hanoi(n-1,B,A,C);栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社递归函数的内部执行过

29、程递归函数的内部执行过程n每一次递归调用时，需要为过程中使用的每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。参数、局部变量等另外分配存储空间。n每层递归调用需分配的空间形成递归工作每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。记录，按后进先出的栈组织。局部变量局部变量返回地址返回地址值值 参参活动活动记录记录框架框架递归递归工作记录工作记录 运行开始时，首先为递归调用建立一个工作栈，运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；其结构包括值参、局部变量和返回地址；每次执行递归调用之前，把递归函数的值参和局每次执行递归调用之

30、前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；部变量的当前值以及调用后的返回地址压栈；每次递归调用结束后，将栈顶元素出栈，使相应每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。回地址指定的位置继续执行。栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 写出函数当前调用层执行的各语句，并用有向弧写出函数当前调用层执行的各语句，并用有向弧表示语句的执行次序；表示语句的执行次序；对函数的每个递归调用，写出对应的函数调用，对函数的每个递

31、归调用，写出对应的函数调用，从调用处画一条有向弧指向被调用函数入口，表从调用处画一条有向弧指向被调用函数入口，表示调用路线，从被调用函数末尾处画一条有向弧示调用路线，从被调用函数末尾处画一条有向弧指向调用语句的下面，表示返回路线；指向调用语句的下面，表示返回路线；在返回路线上标出本层调用所得的函数值。在返回路线上标出本层调用所得的函数值。递归函数的运行轨迹递归函数的运行轨迹栈的应用举例栈的应用举例递归递归数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1

32、,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束结束数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列队列的逻辑结构队列的逻辑结构空队列：空队列：不含任何数据元素的队列。不含任何数据元素的队列。队列：队列：只允许在只允许在一端一端进行插入操作，而进行插

33、入操作，而另一端另一端进行进行删除操作的线性表。删除操作的线性表。允许插入（也称入队、进队）的一端称为队尾，允允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。许删除（也称出队）的一端称为队头。（a1,a2,an）队尾队尾队头队头数据结构（数据结构（C版）版）清华大学出版社清华大学出版社队列的操作特性：队列的操作特性：先进先出先进先出a1a2a3入队入队队尾队尾队头队头出队出队特殊线性表特殊线性表队列队列队头队头队列的逻辑结构队列的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue Da

34、ta 队列中元素具有相同类型及先进先出特性，队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitQueue 前置条件：队列不存在前置条件：队列不存在 输入：无输入：无 功能：初始化队列功能：初始化队列 输出：无输出：无 后置条件：创建一个空队列后置条件：创建一个空队列特殊线性表特殊线性表队列队列数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 DestroyQueue 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：销毁队列功能：销毁队列 输出：无输出：无 后置条件：释放队列所占用的存储空间后置条件：

35、释放队列所占用的存储空间 EnQueue 前置条件：队列已存在前置条件：队列已存在 输入：元素值输入：元素值x 功能：在队尾插入一个元素功能：在队尾插入一个元素 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 后置条件：如果插入成功，队尾增加了一个元素后置条件：如果插入成功，队尾增加了一个元素队列的抽象数据类型定义队列的抽象数据类型定义 特殊线性表特殊线性表队列队列数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 DeQueue 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：删除队头元素功能：删除队头元素 输出：如果删除成功，返回被删元素值输出：如果

36、删除成功，返回被删元素值 后置条件：如果删除成功，队头减少了一个元素后置条件：如果删除成功，队头减少了一个元素 GetQueue 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：读取队头元素功能：读取队头元素 输出：若队列不空，返回队头元素输出：若队列不空，返回队头元素 后置条件：队列不变后置条件：队列不变队列的抽象数据类型定义队列的抽象数据类型定义 特殊线性表特殊线性表队列队列数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Empty 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：判断队列是否为空功能：判断队列是否为空 输出：如果队列为空，返回

37、输出：如果队列为空，返回1，否则，返回，否则，返回0 后置条件：队列不变后置条件：队列不变endADT队列的抽象数据类型定义队列的抽象数据类型定义 特殊线性表特殊线性表队列队列数据结构（数据结构（C版）版）清华大学出版社清华大学出版社0 1 2 3 4 入队入队出队出队队列的顺序存储结构及实现队列的顺序存储结构及实现 顺序队列：顺序队列：队列的顺序存储结构队列的顺序存储结构特殊线性表特殊线性表队列队列如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操作时间性能为入队操作时间性能为O(

38、1)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a1a2a3a4rear数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a2a3a4rear数据结构（数据结

39、构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3a4rear出队操作时间性能为出队操作时间性能为O(n)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列队列的顺序存储结构及实现队列的顺序存储结构及实现 如何改进出队的时间性能？如何改进出队的时间性能？放宽队列的所有元素必须存储在数组的前放宽队列的所有元素必须存储在数组的前n个单元这一个单元这一条件条件，

40、只要求队列的元素存储在数组中连续的位置。，只要求队列的元素存储在数组中连续的位置。设置队头、队尾两个指针设置队头、队尾两个指针 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操作时间性能仍为入队操作时间性能仍为O(1)front rear数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例：例：a1a2依次出队依次出队特殊线性表特殊线性表队列队列队列的顺序存储结构及实

41、现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a1a2a3a4rearfront front front出队操作时间性能提高为出队操作时间性能提高为O(1)数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例：例：a1a2依次出队依次出队特殊线性表特殊线性表队列队列队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3a4rearfront队列的移动有什么特点？队列的移动有什么特点？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社例：例：a1a2依次出队依次出队特殊线性表特殊线性表队列队列队列的顺序存储结构及实现队列的顺序

42、存储结构及实现 0 1 2 3 4 入队入队出队出队a3a4rearfront整个队列向数组下标较大方向移动整个队列向数组下标较大方向移动单向移动性单向移动性数据结构（数据结构（C版）版）清华大学出版社清华大学出版社假溢出：假溢出：当元素被插入到数组中下标最大的位置上之当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。空闲空间，这种现象叫做假溢出。特殊线性表特殊线性表队列队列队列的顺序存储结构及实现队列的顺序存储结构及实现 继续入队会出现什么情况？继续入队会出现什么情况？0 1 2 3

43、 4 入队入队出队出队a3a4rearfronta5rear数据结构（数据结构（C版）版）清华大学出版社清华大学出版社循环队列：循环队列：将存储队列的数组头尾相接。将存储队列的数组头尾相接。特殊线性表特殊线性表队列队列队列的顺序存储结构及实现队列的顺序存储结构及实现 如何解决假溢出？如何解决假溢出？0 1 2 3 4 入队入队出队出队a3a4fronta5rearreara6数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊线性表特殊线性表队列队列不存在物理的循环结构，用软件方法实现。不存在物理的循环结构，用软件方法实现。求模求模：（：（41）mod 50队列的顺序存储结构及实现队

44、列的顺序存储结构及实现 如何实现循环队列？如何实现循环队列？0 1 2 3 4 入队入队出队出队a3a4frontreara6数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断循环队列队空？如何判断循环队列队空？特殊线性表特殊线性表队列队列队空的临界状态队空的临界状态队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3rearfront数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断循环队列队空？如何判断循环队列队空？特殊线性表特殊线性表队列队列执行出队操作执行出队操作队空：队空：front=rear队列的顺序存储结构及实

45、现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3front rearfront数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断循环队列队满？如何判断循环队列队满？队满的临界状态队满的临界状态队列的顺序存储结构及实现队列的顺序存储结构及实现 特殊线性表特殊线性表队列队列0 1 2 3 4 入队入队出队出队a3a4fronta5reara6数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断循环队列队满？如何判断循环队列队满？执行入队操作执行入队操作队满：队满：front=rear队列的顺序存储结构及实现队列的顺序存储结构及实现 特殊线性表特殊线

46、性表队列队列0 1 2 3 4 入队入队出队出队a3a4fronta5reara6reara7数据结构（数据结构（C版）版）清华大学出版社清华大学出版社方法一：方法一：附设一个存储队列中元素个数的变量附设一个存储队列中元素个数的变量num，当当num=0时队空，当时队空，当num=QueueSize时为队满；时为队满；方法二：方法二：修改队满条件，浪费一个元素空间，队满时修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元数组中只有一个空闲单元；方法三：方法三：设置标志设置标志flag，当当front=rear且且flag=0时为队时为队空，当空，当front=rear且且flag=1

47、时为队满。时为队满。如何确定不同的队空、队满的判定条件？如何确定不同的队空、队满的判定条件？为什么要将队空和队满的判定条件分开？为什么要将队空和队满的判定条件分开？特殊线性表特殊线性表队列队列队列的顺序存储结构及实现队列的顺序存储结构及实现 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社队满的条件：队满的条件：(rear+1)mod QueueSize=front队列的顺序存储结构及实现队列的顺序存储结构及实现 特殊线性表特殊线性表队列队列0 1 2 3 4 入队入队rearfronta3a4fronta5reara6出队出队数据结构（数据结构（C版）版）清华大学出版社清华大学出版

48、社循循环环队队列列类类的的声声明明const int QueueSize=100;template class CirQueue public:CirQueue()()；CirQueue()()；void EnQueue(T x);T DeQueue()();T GetQueue()();bool Empty()()；private:T dataQueueSize;int front,rear;特殊线性表特殊线性表队列队列数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template void CirQueue:EnQueue(T x)if(rear+1)%QueueSize=fr

49、ont)throw 上溢上溢;rear=(rear+1)%QueueSize;datarear=x;特殊线性表特殊线性表队列队列循环队列的实现循环队列的实现入队入队0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear数据结构（数据结构（C版）版）清华大学出版社清华大学出版社0 1 2 3 4 入队入队a4a5a6出队出队template T CirQueue:DeQueue()()if(rear=front)throw 下溢下溢;front=(front+1)%QueueSize;return datafront;特殊线性表特殊线性表队列队列循环队列的实现循环队列的实现出

50、队出队frontrearfronta3数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template T CirQueue:GetQueue()()if(rear=front)throw 下溢下溢;i=(front+1)%QueueSize;return datai;特殊线性表特殊线性表队列队列循环队列的实现循环队列的实现读队头元素读队头元素0 1 2 3 4 入队入队a4a5a6出队出队frontreara3 i数据结构（数据结构（C版）版）清华大学出版社清华大学出版社队列的链接存储结构及实现队列的链接存储结构及实现 链队列：链队列：队列的链接存储结构队列的链接存储结构 队头指针