新書推薦：
《
甲骨文丛书·剑桥世界暴力史（第一卷）：史前和古代世界（套装全2册）
》
售價：HK$
210.6
《
甲骨文丛书·中华早期帝国：秦汉史的重估
》
售價：HK$
300.2
《
欲望与家庭小说
》
售價：HK$
98.6
《
惜华年（全两册）
》
售價：HK$
70.3
《
甲骨文丛书·古代中国的军事文化
》
售價：HK$
99.7
《
中国王朝内争实录（套装全4册）：从未见过的王朝内争编著史
》
售價：HK$
244.2
《
半导体纳米器件：物理、技术和应用
》
售價：HK$
177.0
《
创客精选项目设计与制作 第2版 刘笑笑 颜志勇 严国陶
》
售價：HK$
61.6
|
| 編輯推薦： |
|
既注重原理，又强调实践，配有大量的图表和习题，概念讲解清楚，逻辑性强，可读性好
|
| 內容簡介： |
本书以提高学生的程序设计能力为主旨，全面地介绍程序设计的基础知识、各种常用的数据结构以及排序、查找的各种算法及其应用。为了方便教学，各数据结构类型和基本运算首先用类C代码加以描述，并做了详细的注解。全书既注重原理，又强调实践，配有大量的图表和习题，概念讲解清楚，逻辑性强，可读性好。此外，本书的特点还有： 首次尝试采用任务驱动方式来设计教学内容； 书中有大量以思考形式出现的问题，能在恰当的时机激发思考，启发思维，方便应用于翻转课堂教学模式； 使用脚注介绍计算科学发展史知识和其他相关知识，可拓展学生的知识范围。
本书可作为技术应用型本科院校计算机专业教材，也可为参加全国计算机软件水平程序员级别考试提供参考，还可供广大从事计算机应用的科技人员参考。
|
| 目錄：
|
目录
第1章绪论
1.1数据结构的基本概念
1.1.1数据结构的实例
1.1.2数据结构的概念
1.1.3学习数据结构的理由
1.2算法分析的基本概念
1.2.1算法
1.2.2算法效率的分析
1.2.3算法效率的评价
1.3程序设计基础
1.3.1软件工程的基本概念
1.3.2软件设计基础
1.3.3编码基础
1.3.4计算机体系结构基础
习题1
第2章线性表
2.1线性表的基本概念
2.1.1线性表的基本运算
2.1.2一个有趣的问题
2.2线性表的顺序表示
2.2.1顺序表
2.2.2顺序表的基本运算
2.2.3顺序表的算法分析
2.3线性表的链式表示
2.3.1线性链表
2.3.2线性链表的基本运算
2.3.3顺序表和链式表的比较
2.4双链表和循环链表
2.4.1双链表
2.4.2循环链表
2.5线性表的应用
习题2
第3章栈和队列
3.1栈的概念及运算
3.1.1栈的概念
3.1.2栈的基本运算
3.1.3一个有趣的问题
3.2栈的存储和实现
3.2.1栈的顺序表示
3.2.2栈的链式表示
3.3栈的应用
3.3.1数制转换
3.3.2表达式求值
3.3.3栈与递归
3.3.4回溯法
3.4队列的概念及基本运算
3.4.1队列的概念
3.4.2队列的基本运算
3.4.3一个有趣的问题
3.5队列的存储结构及运算
3.5.1队列的顺序表示
3.5.2循环队列
3.5.3队列的链式表示
3.6队列的应用
习题3
第4章串、广义表及数组
4.1串的定义和基本运算
4.1.1串的定义
4.1.2串的基本运算
4.1.3一个有趣的问题
4.1.4串的定长顺序存储
4.1.5模式匹配
4.1.6串的链式存储结构
4.1.7串的应用
4.2广义表
4.2.1广义表的定义
4.2.2广义表的存储
4.3数组
4.3.1数组的定义和存储
4.3.2特殊矩阵的压缩存储
习题4
第5章树
5.1树的概念及基本运算
5.1.1树的概念
5.1.2树的基本术语
5.1.3树的基本运算
5.1.4一个有趣的问题
5.1.5树的存储
5.2二叉树的概念与性质
5.2.1二叉树的概念及基本运算
5.2.2二叉树的性质
5.2.3二叉树的存储
5.3二叉树的遍历
5.4二叉树遍历算法的应用
5.5线索二叉树
5.6树和二叉树
5.6.1树与二叉树的转换
5.6.2二叉树与森林的转换
5.7哈夫曼树及其应用
5.8树的应用
习题5
第6章图
6.1图的概念及运算
6.1.1图的概念
6.1.2图的基本运算
6.1.3一个有趣的问题
6.2图的存储
6.2.1数组表示
6.2.2邻接表表示
6.3图的遍历
6.3.1深度优先搜索遍历
6.3.2广度优先搜索遍历
6.4图的连通性问题
6.4.1无向图的连通性
6.4.2最小生成树
6.4.3Prim算法
6.4.4Kruskal算法
6.5最短路径
6.5.1单源点最短路径
6.5.2任意一对顶点之间的最短路径
6.6有向无环图的应用
6.6.1AOV网
6.6.2拓扑排序
6.6.3AOE网
6.6.4关键路径
6.7图的应用
习题6
第7章排序
7.1排序的基本概念
7.2一个有趣的问题
7.3插入排序
7.3.1直接插入排序
7.3.2折半插入排序
7.3.3希尔排序
7.4交换排序
7.4.1冒泡排序
7.4.2快速排序
7.5选择排序
7.5.1直接选择排序
7.5.2树形选择排序
7.5.3堆排序
7.6归并排序
7.7排序的应用
7.8各种排序方法的综合比较
习题7
第8章查找
8.1查找的基本概念
8.2一个有趣的问题
8.3静态查找表
8.3.1顺序查找法
8.3.2折半查找法
8.3.3分块查找法
8.4动态查找表
8.5B-树
8.6哈希表
8.6.1哈希法与哈希表
8.6.2冲突处理的方法
8.6.3哈希函数的构造方法
8.6.4哈希表的查找
8.7查找的应用
习题8
参考文献
|
| 內容試閱：
|
前言
大数据时代已经到来，数据与算法是数据科学与工程的重要内容，而数据结构是计算机算法设计的重要理论和方法基础，它不仅是计算机类专业的核心课程，而且已成为其他专业的重要教学内容。数据结构与算法的教学目的是： 让学生学会分析需要计算机处理的数据对象的特性，以选择适当的数据结构、存储结构从而选择相应的算法； 初步掌握算法性能分析的方法； 初步掌握将实际问题求解转化为算法，进而转化为计算机程序的能力； 通过本课程的学习，使学生获得更进一步的程序设计技能训练，提高编程能力，进而提高计算机软件工程能力。长久以来由于数据结构课程自身的抽象和严密，以及数据结构开设的时间通常在大一的第二学期，教师感觉数据结构难教，学生普遍反映数据结构难学，学生很难独立完成算法的实现。基于上述问题我们在编写本教材时充分考虑了学生的知识结构和教师的教学方法。本教材的编写遵循的原则是： 既注重原理又注重实践； 既注重抽象思维又注重形象思维； 既方便自学又方便教学。本书的编写有以下特色。1 采用任务驱动方式来设计教学内容。除第1章外，在每一章，必要的基础知识介绍后都安排了一个问题作为学习完本章后要解决的任务。该问题具有两个特征： ①有一定的趣味性，能较好地激发学生的学习兴趣和解决问题的动力； ②综合性较强，问题的解决需要使用到本章中的知识。2 利用教材中的思考标志，提出问题拓展学生思维。思考不同于习题，习题的作用代替不了思考，因为习题在每个章节之后，一般要等到讲完一个章节才会遇到，因此习题对于课堂教学是滞后的。采用提示思考的方式可以在教学中恰到好处地启发学生的思维。教材使用思考标志通常有3种情况： 一是提醒学生注意； 二是启发学生基于当前知识基础进一步思考； 三是提示本教材没有讲授的内容以引导学有余力的学生拓展自身知识面。另外，这些标志为思考的问题，可方便地应用于翻转课堂教学模式。3 在计算机专业的核心基础课程中增加计算机科学文化的知识，使学生在学习本教材的过程中，不但能学到专业知识，还能了解计算机科学发展历史的相关知识和数据结构课程与其他课程的联系； 对提高学生学习本课程的兴趣，拓宽学生的知识面大有好处。
全书共分8章： 第1章介绍数据结构和算法分析的基本概念及程序设计基础； 第2~4章介绍线性结构及一部分与线性结构密切相关的非线性结构； 第5章和第6章分别介绍树形结构和图结构； 第7章和第8章分别介绍排序和查找。本书可作为技术应用型本科院校计算机专业教材，也可为参加全国计算机软件水平程序员级别考试提供参考，还可供广大从事计算机应用的科技人员参考。本书讲授60课时左右，除第1章外每章可安排2课时上机实习。本书是由文益民、张瑞霞、李健三位在多年从事计算机专业数据结构课程教学的经验基础上，经过多次反复磋商和共同讨论而定稿。全书由桂林电子科技大学文益民整体构思、统稿、修改，易新河、文博奚等为本书的编辑、排版做了很多工作。由于编著者水平有限，书中难免存在不足和疏漏之处，殷切期望广大读者批评指正。文益民2017年1月于桂林电子科技大学
第3章栈和队列栈Stack是一种最常用和最重要的数据结构，它在计算机科学中应用非常广泛，例如，编译器对表达式的计算和表达式括号的匹配、计算机系统处理函数调用时参数的传递和函数值的返回等。栈是一种特殊的线性表，其特殊性在于它的插入、删除等操作都是在线性表的一端进行，特点是按后进先出的规则进行操作，是一种运算受限制的线性表，因此，可称为限定性的数据结构。栈在程序设计中非常重要，程序的调试和运行都需要系统栈的支撑。队列Queue是一种运算受限制的线性表。与栈不同的是： 队列是限制在表的两端进行操作的线性表。队列只允许在表的一端插入数据元素而在另一端删除数据元素。队列是软件设计中常用的一种数据结构。队列在操作系统中有重要的应用在操作系统中进程控制块PCB的组织就采用队列，称为PCB表。PCB表示操作系统中最关键、最常用的数据，它的物理结构直接影响到系统的效率。。队列的逻辑结构和线性表相同，其特点是按先进先出的规则进行操作。本章首先介绍栈的概念、栈的存储结构、有关栈的基本运算和栈的应用，然后介绍顺序队列其中重要介绍循环队列和链队列的概念及运算。
3.1栈的概念及运算
3.1.1栈的概念1. 定义
图3.1栈的示意图
栈是限定仅在表尾进行插入或删除操作的线性表，表尾称为栈顶top，表头称为栈底bottom。例如，设有n个元素的栈S=a1，a2，，an，则称a1为栈底元素，an为栈顶元素，如图3.1所示。2. 特点栈的最主要特点就是先进后出First In Last Out，FILO,或后进先出Last In First Out，LIFO。在日常生活中有很多栈的例子。例如，往箱子里放书，最先放进去的书压在最底下，只能最后拿出来，而最后放进去的书在最上面，可以最先拿出来。又如食堂里洗碗，最先洗好的碗放在最下面，而最先被使用的碗是最后洗好的碗。另外，铁路调度站也采用栈的原理来调度铁路机车。3.1.2栈的基本运算栈的基本运算主要有以下几种。1 建立一个空栈： InitStackS。初始条件： 栈S不存在。运算结果： 构造一个空栈S。2 进栈： PushS,x。初始条件： 栈S存在且非满。运算结果： 在栈顶插入一个值为x的元素，栈中增加一个元素。3 出栈： PopS,&x。初始条件： 栈S存在且非空。运算结果： 将栈顶元素的值赋给x，删除栈顶元素，栈中减少了一个元素。4 读栈顶元素： ReadTopS。初始条件： 栈S存在且非空。运算结果： 返回栈顶元素的值，栈中元素保持不变。5 判栈空： IsEmptyS。初始条件： 栈S已经存在。运算结果： 若栈空则返回1，否则返回0。6 判栈满： IsFullS。初始条件： 栈S已经存在。运算结果： 若栈满则返回1，否则返回0。7 显示栈中元素： ShowStackS。初始条件： 栈S已经存在且非空。运算结果： 显示栈中所有元素。3.1.3一个有趣的问题有一张由12个区域组成的地图如图3.2所示，试用最少的颜色对该地图进行着色每块区域只涂一种颜色，且要求相邻的颜色互不相同，请打印出所有可能的着色方案。
图3.2着色问题
根据四色定理世界近代三大数学难题之一。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯格思里Francis Guthrie来到一家科研单位做地图着色工作时，发现了一种有趣的现象： 每幅地图都可以用4种颜色着色，使得有共同边界的国家着上不同的颜色。这个结论能不能从数学上加以严格证明？世界上许多一流的数学家都纷纷参加了四色猜想的大会战，直到1976年，美国数学家阿佩尔Kenneth Appel与哈肯Wolfgang Haken在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，做了100亿个判断，终于完成了四色定理的证明。四色定理是第一个主要由计算机证明的理论。可以知道： 任何多么复杂的地图只需要使用4种颜色就可以将相邻的区域或国家分开。将4种颜色分别用1、2、3、4表示时，一种符合条件的着色方案可以如下所示：
1： 12： 23： 34： 25： 36： 47： 18： 49： 110： 411： 212： 3
由于要寻找所有可能的着色方案，需要使用回溯法，而利用栈可以方便地实现回溯法。栈和递归是紧密联系的，因而着色问题也可以使用递归算法实现。
3.2栈的存储和实现
3.2.1栈的顺序表示用顺序存储方式实现的栈称为顺序栈，顺序栈对应于顺序表。1. 顺序栈的实现设栈中数据元素的类型是整型，用一个足够长的一维数组s来存放元素，数组的最大容量为STACK_INTSIZE。同时假设栈顶指针top。注意： 在以下的程序中，top不是指向当前的栈顶元素，而是指向下一次将要进栈的元素的存储位置。顺序栈可以用C语言描述如下：
#defineSTACK_INTSIZE50*分配栈的最大存储空间*
DataTypes［STACK_INTSIZE］;*用来存放栈中数据元素的内存空间*
inttop;*定义栈顶指针*
可以用结构体数组来实现顺序栈：
#defineSTACK_INTSIZE50
#definecharDataType*定义栈中数据元素的类型*
typedefstruct
{DataTypes［STACK_INTSIZE］;
inttop;
}Stack;
Stack *st；*指针st用来引用一个顺序栈*
如果栈顶指针top指向当前的栈顶元素，则下面顺序栈的基本运算算法如何修改?2. 顺序栈的操作设有一个一维数组s［6］用来存放顺序栈，它的一些基本操作如图3.3所示，栈顶指针动态地反映了栈中元素的变化情况。top=0时，表示空栈，如图3.3 a所示。top=1时，表示已经有一个元素进栈，如图3.3 b中元素E已进栈；进栈时，栈顶指针top上移，top加1。top=6时，也即top=STACK_INTSIZE，表示栈满，图3.3 c是6个元素进栈后的状况，栈已满；出栈时，栈顶指针top下移，top减1，图3.3d是元素F出栈后的状况。
图3.3顺序栈操作示意图
3. 顺序栈基本操作的算法1 建立一个空栈【算法3.1】顺序栈的建栈算法。
Stack * InitStack
1{
2 Stack*s;
3 s=mallocsizeofStack;
4 s-top=0;
5 returns;
6}
1 算法3.1中设置s-top=0，表示什么含义？能否设置为s-top=-1?2 返回值s是什么类型？3 根据本章的定义，算法中申请了多大的空间？2 进栈【算法3.2】顺序栈的进栈算法。
void PushStack* st, DataType x
1{if st-top=STACK_INTSIZE
2printf"＼t＼t栈已满，不能入栈!＼n";*若栈满则不能进栈，输出出错信息*
3else
4{st-s［st-top］=x;*元素x进栈*
5st-top;*栈顶指针top加1*
6}
7}
1 在入栈时如果不判断栈是否满，会出现什么情况？2 如果st-top指向栈顶元素，那么如何判断栈满？3 如果在算法3.1中设置st-top=-1，则算法3.2如何描述入栈操作？3 出栈【算法3.3】顺序栈的出栈算法。
void PopStack* st, DataType x
1{ifst-top==0
2printf"＼t＼t栈空，不能出栈!＼n";*若栈空则不能出栈，且输出栈空的信息*
3else
4{ st-top--; x=st-s［st-top］; }*栈非空则top减1，元素出栈*
5}
1 为什么只要将栈顶指针下移一个单元，就表示一个元素出栈了？2 原来栈顶中的元素是否还存在，为什么？3 如果st-top指向栈顶元素，那么如何判断栈空？4 如果希望出栈算法能够返回栈顶元素，怎么修改上述算法？4 读栈顶元素【算法3.4】顺序栈的读栈顶元素算法。
DataType ReadTopStack* st
1{DataType x;
2ifst-top==0
3{printf"＼t＼t栈中无元素";return0; }*若栈空则返回0*
4else
5{st-top--;*修改栈顶指针*
6x=st-s［st-top］; *取栈顶元素*
7 returnx;*返回x即栈顶元素的值*
8 }
9}
注意： 此算法中元素并未出栈。
1 该算法执行后栈顶元素是否在数组中？2 如何用算法3.3和算法3.4实现显示栈中的所有元素ShowStackStack *s？3 两个栈合用一个存储空间比一个栈单用一个存储空间有什么样的优势？3.2.2栈的链式表示若是栈中元素的数目变化范围较大或不清楚栈中元素的数目，就应该考虑使用链式存储结构。将用链式存储结构表示的栈称为链栈，链栈对应于链表。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在栈顶进行，而对于单链表来说，在首端插入和删除结点要比尾端相对地容易一些，因此将单链表的首端作为栈顶，即将单链表的头指针作为栈顶指针。1. 链栈的实现可以采用链表作为栈的存储结构，其结点类型与单链表的结点类型相同。链栈可以用C语言描述如下：
typedef struct node
{ DataType data;
structnode*link;
}Node;
Node *top;*定义top指针指向链栈的栈顶结点*
2. 链栈操作的示意图链栈操作示意图如图3.4~图3.6所示。
图3.4链栈示意图
图3.5链栈的入栈操作
图3.6链栈的出栈操作
链栈为什么不像线性链表那样需要一个人为的头结点？3. 链栈操作的算法1 进栈【算法3.5】链栈的进栈算法。
void PushNode *top,DataType x
1{Node *p;
2 p=Node *mallocsizeofNode;*申请一个新的结点，并让指针p指向该结点*
3 p-data=x; *新结点的数据域被赋值为x*
4 p-link=top;*新结点的指针域赋值*
5 top=p; *修改栈顶指针变量*
6}
1 新插入结点和原来栈顶结点的逻辑关系是怎样的？通过哪个语句体现的？2 为什么要修改栈顶指针变量top=p？2 出栈【算法3.6】链栈的出栈算法。
voidPop Node * top
1{Node *q;
2 DataTypex;
3 iftop!=NULL
4 { q=top; *q指针指向原栈顶位置*
5 x=q -data; *x用来保存原栈顶元素*
6 top=top-link; *修改栈顶指针的位置*
7 freeq; *回收结点q*
8 }
9}
1 如果出栈时需要读出栈顶元素，如何修改算法？2 如果出栈算法需要返回值为栈顶元素，如何修改算法？
3 读栈顶元素。【算法3.7】读链栈栈顶元素的算法。
DataType ReadTopNode * top
1{DataTypex;
2 iftop!=NULL
3 {x=top-data;*x用来保存原栈顶元素*
4return x;
5 }
6 else
7 {printf"空栈＼n";
8exit-1;
9}
}
1 栈顶指针是否发生了变化？2 如何用算法3.7实现算法3.6中的第一个思考问题?3 用算法3.6和算法3.7如何实现显示栈中的所有元素算法ShowStackStack *s？
3.3栈的应用
3.3.1数制转换数值进位制的换算是计算机实现计算和处理的基本问题。例如，将十进制数N转换为j进制的数，其解决的方法很多，其中一个常用的算法是除j取余法见图3.7。将十进制数每次除以j，所得的余数依次进栈，然后按后进先出的次序便得到转换的结果。除j取余法的原理可以从下式看出：
anan-1a1j=anjn-1an-2jn-2 a1j031
其中j表示进位制的大小。从式31可知有下式成立：
N=Nj*j N%j32
其中，为整除，%为求余。
图3.7除j取余法
1. 算法思想1 若N!=0，则将N%j取得的余数压入栈s中，执行步骤2；若N=0，将栈s的内容依次出栈，算法结束。2 用Nj代替N。3 当N0，则重复步骤1、2。2. 算法的实现【算法3.8】十进制数转换算法用顺序栈实现，进制转换中栈的变化情况如图3.8所示。
voidConversion *将十进制数转换为八进制数*
1{int x;
2 Stack *Dstack;
3 Dstack=InitStack;
4 scanf"%d",&x;
5 whilex!=0
6{PushDstack,x%8;*进栈次序是个位、十位*
7x=x8;
8 }
9 while!IsEmptyDstack
10{PopDstack,x; *先出栈的是高位,最后是个位*
11printf"%d",x;
12}
13}
图3.8进制转换中栈的变化情况
1 如何用链栈实现十进制数转换算法？2 算法中使用了栈的哪些基本操作，这样做的好处是什么？【例3.1】把十进制数159转换成八进制数即N=159, j=8。
1 试写出十进制转换为十六进制的算法。2 使用链栈如何实现算法3.8？3.3.2表达式求值表达式是由运算对象、运算符、括号等组成的有意义的式子。表达式求值是程序设计语言编译中的一个基本问题。它的实现是栈应用的一个典型例子。1. 中缀表达式一般所用的表达式是将运算符号放在两运算对象的中间，如a b、cd等，把这样的式子称为中缀表达式。中缀表达式在运算中存在运算符号的优先权与结合性等问题，还存在括号优先处理的问题。首先，要了解算术四则运算的规则：1 先乘除，后加减；2 从左到右进行计算；3 先括号内，后括号外，多层括号，由内向外进行运算。例如，要对表达式2 43-102求值，则计算顺序应为：
2 43-102=2 12-102=2 12-5=14-5=9
任何一个表达式都是由操作数operand、运算符operator和界限符delimiter组成的，把运算符和界限符统称为算符。根据上述三条运算规则，在运算的每一步中，任意两个先后相继出现的算符1和2之间的优先关系有以下3种情况。
121的优先权高于2
表3.1定义了算符之间的这种优先关系。
表3.1算符间的优先关系
21 -*#
-*#2，则1出栈与OPND栈中连续出栈的两个操作数进行运算，将运算得到的结果入OPND栈。然后将2与OPTR栈顶的运算符再进行优先级比较，而进行相应的运算，直至整个表达式求值完毕。【算法3.9】运算符比较算法。
CharPrecedechar c1, char c2
1{charoptr1, optr2;
2switch c1
3 {case ''*''：
4 case ''''： optr1=4;break;
5 case '' ''：
6 case ''-''： optr1=2;break;
7 case ''''： optr1=0;break;
8 case ''''： optr1=5;break;
9 case ''#''： optr1=-1;
10 }
11switch c2
12 {case ''*''：
13 case ''''： optr1=3;break;
14 case '' ''：
15 case ''-''： optr1=1;break;
16 case ''''： optr1=5;break;
17 case ''''： optr1=0;break;
18 case ''#''： optr1=-1;
19 }
20ifoptr1optr2 return'''';
23}
【算法3.10】表达式求值算法。
intExpress
1{ char theta,c;*用来表示运算符*
2StackOPTR; Push &OPTR,''#'';*运算符栈*
3StackOPND;*运算数栈*
4c=getchar ;
5whilec!=''#''|| ReadTop &OPTR!=''#''
6*''#''是表达式结束的标记，也是运算符栈为空的标记*
7{ if!Inc,op
8 { Push&OPND,c; c=getchar ;}*不是运算符则进操作数栈*
9 else*判断运算符栈顶元素和新输入运算符的优先权*
10 switchPrecedeReadTop&OPTR,c
11 {case ''''：
18*将操作数栈顶两个元素和运算符栈顶的一个元素退栈，并结合进行运算，然后将结果入操作数栈*
19 Pop&OPTR,θ
20 Pop&OPND,&b;Pop&OPND,&a;
21 Push&OPND,Operatea,theta,b;
22 break;
23 }
24 }
25 return ReadTop&OPND;
26}
【例3.2】计算23 94-5。栈的变化过程如表3.2所示。
表3.2中缀表达式求值中栈的变化情况
步骤OPTR栈OPND栈输 入 字 符主 要 操 作
1#2*3 94-5#Push&OPTR，''#''2#2*3 94-5#Push&OPND，''2''3#2*3 94-5#Push&OPTR，''*''4# *23 94-5#Push&OPTR，''''5# * 23 94-5#Push&OPND，''3''6# * 23 94-5#Push&OPTR，'' ''7# * 2394-5#Push&OPND，''9''8# * 2394-5#Operate3,'' '',99# * 2124-5#Pop&OPTR,theta{删除一对括号}10# *2124-5#Operate2,''*'',1211#244-5#Push&OPTR，''''12# 244-5#Push&OPND，''4''13# 24 4-5#Operate24,'''',414#65#Push&OPTR，''-''15# -65#Push&OPND，''5''16# -65#Operate6,''-'',517#1return ReadTop&OPND
2. 中缀表达式转换成后缀表达式将中缀表达式转换成为后缀表达式的过程也是一个栈应用的典型例子，将中缀表达式转换成后缀表达式，可以简化求值过程。从中缀表达式2*3 94-5和其后缀表达式239 *45-可以看出，在这两种表达形式中，操作数的次序是相同的。因此，顺序扫描中缀表达式，将它转换成后缀表达式的过程中，只要遇到操作数就可以直接输出，若是运算符表中的2，则和OPTR栈的栈顶运算符表中的1比较优先权。如果12，则输出1出栈。然后将2与OPTR栈顶的运算符再进行优先级比较，而进行相应的运算，直至整个表达式求值完毕。【例3.3】将中缀表达式2*3 94-5转换成后缀表达式239 *45-的过程如表3.3表示。
表3.3中缀表达式转换成后缀表达式过程中栈的变化情况
步骤OPTR栈输 入 字 符主 要 操 作
1#2*3 94-5#Push&OPTR，''#''2#2*3 94-5#输出''2''3#*3 94-5#Push&OPTR，''*''4# *3 94-5#Push&OPTR，''''5# * 3 94-5#输出''3''6# * 94-5#Push&OPTR，'' ''7# * 94-5#输出''9''8# * 4-5#输出'' ''9# * 4-5#Pop&OPTR,&theta{删除一对括号}10# *4-5#输出''*''11#4-5#Push&OPTR，''''12# 4-5#输出''4''13# -5#输出''''14#5#Push&OPTR，''-''15# -5#输出''5''16# -#输出''-''17#3. 后缀表达式后缀表达式求值的运算只用一个栈便可实现，这是因为后缀表达式中既无括号又无优先级的约束。后缀表达式求值的步骤如下。1 读入表达式一个字符。2 若是操作数，压入栈，转向步骤4。3 若是运算符，从栈中弹出两个数，结合进行运算，并将运算结果再压入栈。4 若表达式输入完毕，栈顶即表达式的值； 若表达式未输入完，则转向步骤1。【例3.4】计算23 94-5。先转化为后缀表达式，其后缀表达式为： 239 *45-。后缀表达式求值过程中栈的变化过程如表3.4所示。
表3.4后缀表达式求值中栈的变化情况
步骤OPND栈输 入 字 符主 要 操 作
1239 *45-Push&OPND，''2''2239 *45-Push&OPND，''3''3239 *45-Push&OPND，''9''4239 *45-Operate3,'' '',95212*45-Operate2,''*'',1262445-Push&OPND，''4''72445-Operate24,'''',4865-Push&OPND，''5''965-Operate6,''-'',5101return ReadTop&OPND
表3.3和表3.4有何异同？3.3.3栈与递归1. 函数的嵌套调用
在高级语言编制的程序中，调用子程序和被调用子程序之间的链接和信息交换需要通过一种特殊的栈来进行，这个栈就是系统栈。通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成三件工作： ①将所有的实参、返回地址等信息传递给被调用函数保存； ②为被调用函数的局部变量分配存储区； ③将控制转移到被调用函数的入口。而从被调用函数返回调用函数之前，系统也应完成三件工作： ①保存被调函数的计算结果； ②释放被调函数的数据区； ③依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照最后调用最先返回的原则，系统运行期间所需要的数据依次存放在系统栈中。当调用一个子程序时，就创建一个新的活动记录或栈帧结构，并通过入栈将其压入栈顶； 每当从一个函数退出时，就通过出栈删除栈顶活动记录。【例3.5】函数的嵌套调用。
main
{
R ;
}
R
{
S ;
return;
}
S
{
K ;
return;
}
K
{
return;
}
程序中栈的变化情况如图3.9所示。
图3.9函数嵌套调用过程中栈的变化情况
2. 递归调用函数直接或间接调用自身称为递归调用。实现过程类似函数的嵌套调用，建立一个递归工作栈。【例3.6】函数的递归调用。
voidwriteintw
1{inti;
2if w!=0
3{writew-1;
4 fori=1;i0
12{m=i;
13whilee［m］=i
33 pope,&x;
34i--;
35}
36输出G
3.4队列的概念及基本运算
3.4.1队列的概念队列是线性表的一种，是一种先进先出First In First Out，FIFO的线性表。队列限制在表的一端可进行插入而只能在另一端进行删除操作。跟排队购票一样，能够插入元素的一端称为队尾rear，允许删除元素的一端称为队首front。设有n个元素的队列Q=a1，a2，a3，，an，则称a1为队首元素，an为队尾元素。队列中的元素按a1，a2，a3，a4，，an-1，an的次序进队，按a1，a2，a3，，an-1，an次序出队，即队列的操作是按照先进先出原则进行的，简称FIFO表，如图3.11所示。与线性表相类似，队列也有顺序存储和链式存储两种存储结构。
图3.11队列示意图
队列的实例如下。1 在计算机处理文件打印时，为了解决高速的CPU与低速的打印机之间的矛盾，将多个打印请求存储在缓存中，按照它们提出请求的时间而顺序执行各个打印任务，即按照先进先出的原则形成打印队列。2 现代制造业中的传送带上的产品也构成队列。3 现代银行服务采用计算机同时处理多个窗口的多个队列详见严蔚敏、吴伟民编著的《数据结构》Ｃ语言版，清华大学出版社。，以方便顾客和提高银行工作效率。3.4.2队列的基本运算在队列上进行的运算如下。1 队列初始化： InitQueQ。初始条件： 队列Q不存在。运算结果： 创建一个空队列。2 入队操作： InsertQueQ，x。初始条件： 队列Q存在，但未满。运算结果： 插入一个元素x到队尾，长度加1。3 出队操作： ExitQueQ。初始条件： 队列Q存在，且非空。运算结果： 删除队首元素，长度减1，需要时可获取队头元素。4 判队空操作： EmptyQueQ。初始条件： 队列Q存在。运算结果： 若队列空则返回为1，否则返回为0。5 求队列长度： LenQueQ。初始条件： 队列Q存在。运算结果： 返回队列的长度。3.4.3一个有趣的问题队列在模拟排队一类的问题中用途非常广泛，无冲突分组问题就是其中的一个。例如，设有一个旅游团由n个人组成，这n个人中有的互有嫌隙。为了在旅游中彼此不发生冲突，应将人员分组。试问应如何才能使组数最少且任何互有嫌隙的人不被分在同一组中？这个问题的另外一种描述为： 一个美食家急于吃遍某大饭店的n道菜，但这n道菜中却有不适于在同一餐中吃的，否则可能降低菜的营养价值。那么该人应如何点菜，才能尽快吃遍这n道菜又不降低菜的营养价值？这个问题的抽象表示是： 已知集合S={s1, s2, s3,，sn}和定义在S上的关系R={si,sj|si, sjS,1i,jn且ij}，si,sjR表示si与sj有冲突。现在要求将S划分成若干个不相交的子集，使得子集数量最少且任何一个子集中的任何两个元素互不冲突。例如，设S={s1, s2, s3, s4, s5, s6, s7, s8, s9}，R={s2,s8，s2,s9，s2,s6，s2,s5，s2,s1，s3,s6，s3,s7，s4,s5，s4,s9，s5,s6，s5,s7，s5,s9，s6,s7}，则问题的一个解为{S1, S3, S4, S8}，{S2,S7}，{S5}，{S6, S9}。
3.5队列的存储结构及运算
3.5.1队列的顺序表示顺序队列是按照队列中的数据元素的顺序将数据元素存放在一组连续的内存中，可以用一维数组Q［MAXLEN］作为队列的顺序存储空间，其中MAXLEN为队列的容量，队列元素从Q［1］单元开始存放，直到Q［MAXLEN］单元。因为队头和队尾都是活动的，因此，除了队列的数据以外，一般还要有两个整型变量标记队首front和队尾rear两个数据元素的位序，这两个整型变量被称为队列的头指针和尾指针。为了方便，通常规定头指针front总是指向队列当前的队首元素的前一个位置这个位置的地址编号更小，尾指针rear总是指向队列当前的队尾元素。顺序队列用C语言定义如下：
typedefstruct
{DataType*Q； *存储队列元素的存储块的首地址*
intfront=-1, rear=-1； *指示队头、队尾元素的位置，并置队列为空*
}SeqQue；
SeqQue*sp； *定义一个指向顺序队列的指针变量*
sp=Seque* mallocMAXLEN *sizeofSeqQue； *申请一个顺序队列的存储空间*
1. 入队操作在无溢出的情况下，入队时队尾指针加1，元素入队。操作如下：
sp-rear； *先将队尾指针加1*
sp-Q［sp-rear］=x； *x入队*
2. 出队操作在队非空的情况下，出队时队头指针加1，队头元素即可出队。操作如下：
sp-front；
x=sp-Q［sp-front］； *队头元素送x*
求队列的长度：队中元素的个数： m=sp-rear-sp-front。队满时： m=MAXLEN。队空时： m=0。设队列长度MAXLEN=5，则其示意图如图3.12所示。
图3.12队列操作示意图
1 为什么队列的长度不是sp-rear-sp-front 1？2 从图3.12d中可以看出，以上定义的这种队列有什么缺点？从图3.12可以看到，随着入队、出队操作的不断进行，整个队列会整体向后移动，这样就出现了图3.12d中的现象： 队尾指针已经移到了最后，而队列却未真满的假溢出现象，使得队列的空间没有得到有效的利用。解决的方法，可以将所有的数据往前移动，让空间留在队尾，这样新的数据就可以入队了。3 食堂的排队是队列，为什么没有假溢出现象？3.5.2循环队列
图3.13循环队列示意图
为了解决上述队列的假溢出现象，要做移动操作，当移动数据较多时将会影响队列的操作速度。一个更有效的方法是将队列的数据区Q［1： MAXLEN］假想成是首尾相连的环，即将Q［1］与Q［MAXLEN］假想成相邻的两个数组元素，形成一个环形表，这就成了循环队列，如图3.13所示。在循环队列中，仍旧规定头指针front总是指向队列当前的队首元素的前一个位置。循环队列初始化时，定义sp-rear=sp-front=1。因为是头尾相接的循环结构，入队操作修改为：
sp-rear=sp-rear 1 % MAXLEN； *先将队尾指针加1*
sp-Q［sp-rear］=x； *x送队头元素中*
出队操作修改为：
p-front=p-front 1 % MAXLEN；
x=sp-Q［sp-front］； *队头元素送x*
循环队列的入队和出队操作如图3.14所示。
图3.14循环队列操作示意图
从图3.14可以看出，循环队列的确可以解决假溢出问题，并且不需要移动数据元素。但是，循环队列还需要以空出一个存储空间的代价用于判断队列是否是满。如果不付出这样的一个存储空间，就无法判断队列是满还是空，这可以从对图3.15进行分析得到。
图3.15全部空间都用于存储数据元素时，循环队列操作示意图
从图3.15所示的循环队列可以看出： sp-front==sp-rear可以判别队列空间是否是空，而sp-rear 1% MAXLEN==sp-front可以判别队列空间是否是满。从图3.15可以知道： 当sp-rear追上sp-front时循环队列满，而当sp-front追上sp-rear时循环队列空。但是当sp-front==sp-rear时，无法判断队列是空还是满。要描述sp-rear与sp-front之间的这种追赶关系，那就必须要用一个变量来表述，因此为了便于判断循环队列是空还是满必须付出一个存储空间的代价。循环队列类型定义如下：
typedefstruct
{DataType* Q； *数据的存储区*
intfront，rear； *队头、队尾指针*
}CycQue； *循环队列*
循环队列的基本运算如下。1. 置空队【算法3.11】置空队示例如下：
voidInitCycQueCycQue* sp
1{sp-Q=DataType*mallocMAXLEN *sizeofDataType；
2sp-front=sp-rear=1；
3}
1 算法3.11中的第1行为什么要强制转换？2 算法3.11中的第2行sp-front=sp-rear=0是否可以，对后面的算法有什么影响？2. 入队算法【算法3.12】入队算法示例如下：
intInsertCycQueCycQue* sp，DataType x
1{if sp-rear 1%MAXLEN==sp-front
2 {printf "队满"；
3 return -1；*队满不能入队*
4 }
5 else
6 {sp-rear=sp-rear 1 % MAXLEN；
7sp-Q［sp-rear］=x；
8return 1； *入队完成*
9 }
10 }
解释第2行判断循环队列满的含义。3. 出队算法【算法3.13】出队算法示例如下：
intExitCycQueCycQue* sp, DataType*x
1{if sp-front==sp-rear
2{printf "队空"；
3 return -1； *队空不能出队*
4}
5 else
6{sp-front=sp-front 1 % MAXLEN；
7 *x=sp-Q［sp-front］； *读出队头元素*
8 return 1； *出队完成*
9}
10}
1 算法3.13中的首行和第7行中的*号代表什么含义，含义是否相同？2 在算法3.13中的首行和第7行中，如果不加*号是否可以？4. 求队列长度【算法3.14】求队列长度算法如下：
intLenCycQueCycQue* sp
{return sp-rear-sp-front MAXLEN%MAXLEN;}
若用户无法估计所用队列的最大长度，该怎么办？3.5.3队列的链式表示队列的链式存储称为链队列或链队。和链栈类似，链队列也可以用单链表来实现。根据先进先出原则，为了便于在队头删除和队尾插入，要分别为队列设置一个头指针和尾指针，队尾指针指向队列的最后一个元素。同样为了方便，给队列增加了一个头结点，队头指针就指向头结点，如图3.16和图3.17所示。
图3.16链队列示意图
图3.17链队列
在链队列与顺序队列中，头指针和尾指针的定义有何不同？根据以上链队列的示意图，可以定义关于链队列结点和链队列的定义。
链队列结点的定义：
typedefstructnode
{ DataTypedata；*存储数据元素*
structnodenext； *指向直接后继结点的指针*
} Quenode；
链队列的定义：
typedefstruct
{ Quenode *front，*rear； *定义队列的头指针和尾指针*
}LinkQue; *将头尾指针封装在一起的链队*
LinkQue*lp； *定义一个指向链队的指针lp*
队列为空时头指针和尾指针都指向头结点。链队列的基本运算如下。1 队列初始化，创建一个带头结点的空队列。【算法3.15】创建空队列算法。
void InitLQue LinkQue* Lp
1{
2 Quenode*Q；
3 Q=Quenode*mallocsizeofQuenode *申请链队头结点*
4 lp-front=Q； *头指针指向头结点*
5 lp-front-next=NULL; *置头结点指针域为空*
6 lp-rear=lp-front； *尾指针指向头结点*
7}
如果没有头结点，如何修改算法？2 入队操作。【算法3.16】入队算法。
void InsertLQue LinkQue *Lq ,DataType x
1{Quenode *p;
2p=Quenode*malloc sizeofQuenode;*申请新结点*
3p-data=x; p-next=NULL;
4lq-rear-next=p;
5lq-rear=p;
6}
如果没有头结点，如何修改入队算法，需要哪些特殊处理？3 判断队空操作。【算法3.17】判断队空算法。
intEmptyLQue LinkQue *Lq
1{if lq-front==Lq-rear return 0；
2elsereturn 1；
3}
哪些情况需要判断队空操作？4 出队操作。【算法3.18】出队算法。
int ExitLQue LinkQue* Lq ,DataType*x
1{Quenode*q;
2 if EmptyQue Lq
3 {printf "队空"； return 0；
4 }*队空，出队失败*
5 else
6 {q=lq-front-next;
7lq-front-next=lq-front-next-next；
8*x=q-data; *队头元素放x中*
9freeq； *释放资源*
10 return 1；
11}
12 }
1 队列只有一个结点时，出队算法如何增加特殊处理？2 如果需要给出链队列的长度，怎样修改数据结构定义和各个算法？3 链队列有没有假溢出现象？
3.6队列的应用
【例3.9】将二项式a bn展开，其系数构成杨辉杨辉是中国南宋时期杰出的数学家和数学教育家。在13世纪中叶活动于苏杭一带，其著作甚多。他著名的数学书共五种二十一卷，著有《详解九章算法》十二卷1261年、《日用算法》二卷1262年、《乘除通变本末》三卷1274年、《田亩比类乘除算法》二卷1275年、《续古摘奇算法》二卷1275年。三角形，如图3.18所示。要求按行输出展开式系数的前n行。
图3.18杨辉三角形
图3.19第i行元素与第i 1行元素的关系
从杨辉三角形的性质可以知道，除第1行以外，在打印第i行时，必须用到第i-1行的数据。例如，在i=2、3、4时，每行的两侧各加上一个0，如图3.19所示。设s是第i行第j-1个元素，t是第i行第j个元素，则s t是第i 1行的第j个元素。设在数组q中已有第i行数据，且s=0，则在第i行数据的后面再添加一个0。这样，第i 1行的数据可以通过第i行数据计算得到，而按照先算出先进入数组q的顺序将第i 1行的数据依次入队进入数组q，如图3.20所示，然后第i行的数据就依次出队。
图3.20从第2行数据计算第3行数据
【算法3.19】 杨辉三角形的算法如下：
void YangHuiint n
1{int s, int t;
2SeqQue*q;
3InitQueq;
4InsertQueq,0; *在第1行的左侧添加0*
5InsertQueq,1, printf"1＼t";
6InsertQueq,1 , printf"1＼t";
7InsertQueq,0;*在第1行的右侧添加0*
8for int i=2; iprior
10{ 利用关系矩阵检测j号元素与当前分组中的元素是否有冲突；
11如果无冲突，则将j号元素归入当前分组；
12否则重新入队；
13}
14else
15{ 新建另一空的分组；
16将j号元素归入该分组；
17}
18}
19输出： 各元素的分组情况；
20算法结束
习题3
一、 填空题1. 向栈中压入元素的操作是先，后。2. 设一个链栈的栈顶指针是ls，栈中结点类型为Node，则栈空的条件是。如果栈不为空，则退栈操作为p=ls； ； freep。3. 栈是限制在表的一端进行插入和删除的线性表，插入、删除的这端称为，另一端称为。4. 栈通常有和两种存储结构。5. 在栈中存取数据遵循的原则是。6. 在顺序栈S中，出栈操作时要执行的语句序列中有S-top； 进栈操作时要执行的语句序列中有S-top。7. 链栈中第一个结点代表栈的元素，最后一个结点代表栈的元素。8. 在顺序栈中，假设栈所分配的最大空间为MAXLEN，top=0表示，此时再出栈会发生现象； top=MAXLEN表示，此时再入栈就会发生现象。9. 在高级语言编制的程序中，调用子程序和被调用子程序之间的链接和信息交换需要通过来进行。10. 函数直接或间接调用自身称为。11. 当有多个函数构成嵌套调用时，遵守的原则。12. 2 43 94-5的后缀表达式为。13. 在队列中存取数据应遵从的原则是。14. FIFO的含义是。15. 在队列中，允许插入的一端称为，允许删除的一端称为。16. 设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为和； 若只设尾指针，则入队和出队操作的时间复杂度分别为和。17. 在非空队列中，头指针指向，而尾指针指向。18. 设采用顺序存储结构的循环队列头指针front指向队头元素，队尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为Queuelen。1 在循环队列中，队空标志为，队满标志为。2 当rear=front时，队列长度为； 当reartop!=0B. ST-top==0C. ST-top!=mD. ST-top==m3. a*b c-d的后缀表达式是。A. abcdd -B. abc *d-C. abc* d-D. - *abcd4. 有一栈，元素a、b、c、d只能依次进栈,则出栈序列中不可能得到的是。A. d、c、b、aB. c、b、a、dC. a、b、c、dD. d、c、a、b5. 如果以链表作为栈的存储结构，则出栈操作时。A. 必须判别栈是否满B. 必须判别栈是否为空C. 必须判别栈元素类型D. 可不做任何判断6. 如果以链表作为栈的存储结构，则入栈操作时。A. 必须判别栈是否满B. 必须判别栈是否为空C. 必须判别栈元素类型D. 可不做任何判断7. 插入和删除只能在一端进行线性表，称为。A. 队列B. 循环队列C. 栈D. 循环栈8. 一个顺序栈一旦说明，其占用空间的大小。A. 已固定B. 可以变动C. 不能固定D. 动态变化9. 向一个栈顶指针为H的链栈中插入一个s所指向的结点时，需执行。A. H-link=sB. s-link=H-link; H-link=s;C. s-link=H;H=s;D. s-link=H; H=H-link;10. 向一个栈顶指针为H的链栈中执行出栈运算时，需执行。
A. p=H;H=H-link;freep;B. H=H-link;freeH;C. p=H;H-link=H-link-link;freep;D. p=H;H=H-link;11. 在队列中存取数据的原则是。A. 先进先出B. 后进先出C. 先进后出D. 随意进出12. 栈和队列的共同点是。A. 都是先进先出B. 都是后进先出C. 只允许在端点处插入和删除元素D. 没有共同点13. 一个队列的入队序列是a、b、c、d,则出队序列是。A. a,b,c,dB. a, c, b,dC. d, c,b,aD. a, c, b,d14. 一个顺序队列的队头元素为。A. Q［sp-front］B. Q［sp-front 1］C. Q［sp-front-1］D. Q［sp-rear］15. 队列是限定在进行操作的线性表。A. 中间B. 队头C. 队尾D. 端点16. 判断一个顺序存储的队列sp为空的条件是。A. sp-front=sp-rearB. sp-front=sp-rear 1C. sp-front=sp-rear-1D. sp-front=NULL17. 在一个有头结点的链队列中，假设f和r分别为队首和队尾指针，则插入s所指的结点的运算是。A. f-next=s; f=s;B. r-next=s; r=s;C. s-next=r; r=s;D. s-next=f; f=s;18. 在一个有头结点的链队列中，假设f和r分别为队首和队尾指针，则队头出队的运算是。A. q=f-next; f-next=f-next-next; freeq;B. q=f; f-next=f-next-next; freeq;C. f-next=f-next-next; q=f-next;freeq;D. q=f-next-next; f=f-next; freeq;19. 判断一个循环队列cq最多元素为m为满的条件是。A. cq-rearcqfront=m;B. cq-rear 1%m=cq-front;C. cq-front=cq-rear;D. cq-rear=m-1;20. 判断一个循环队列cq最多元素为m为空的条件是。A. cq-rearcqfront=m;B. cq-rear 1%m=cq-front;C. cq-front=cq-rear;D. cq-rear=m-1;21. 循环队列用数组A［0,m-1］存放其元素值，已知头尾指针分别是front和rear，则当前队列中元素的数量是。A. rear-front m%mB. rear-front 1C. rear-front-1D. rear-front三、 运算题1. 设将整数1、2、3、4依次进栈，请回答下述问题。1 若入、出栈秩序为Push1、Pop、Push2、Push3、Pop、Pop 、Push4、Pop ,则出栈的数字序列是什么这里Pushi表示i进栈，Pop 表示出栈?2 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。2. 假设Q［1,7］是一个顺序队列，初始状态为front=rear=0，求完成下列各运算后队列的头尾指针的值，若不能入队，请指出其元素，并解释理由，画出上述各运算过程。1 a、b、c入队;2 a、b出队;3 d、e、f入队;4 c出队;5 g、h入队。3. 如果第2题中的Q［1,7］是循环队列，初始状态front=rear=0，求完成与前题同样的操作，并画出运算过程。四、 程序设计题1. 设计算法判断一个算术表达式的圆括号是否正确配对。提示： 对表达式进行扫描，凡遇到就进栈，遇就退掉栈顶的，表达式被扫描完毕，栈应为空。2. 设计算法，要求用栈来判断输入的字符串以#号结束是否为回文。回文即字符串顺读与逆读一样不含空格，如字符串madam即为回文。3. 设计算法，要求用栈和队列进行回文判断。4. 设计算法，要求用循环链表实现队列，设置一个指针指向队尾元素注意不设置头指针，该队列至少具有创建空队列、入队和出队算法，并编写主函数对各个函数进行测试。5. 编写一个函数从一给定的顺序表L中删除元素值在x到yxy之间的所有元素，要求以较高的效率来实现。要求： 与队列基本运算的实现程序结合在一起，实现队列基本运算的扩充，上机调试通过。6. 假设以数组sequ［m］存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和队列中内含元素的个数。试给出判别此循环队列的队满条件，并写出相应的入队和出队算法。五、 实训题1. 用递归算法求解聪明的学生问题。2. 实现例3.7和例3.9中的算法。
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
