第十二章文件
12.1 有关文件的基本概念
一、文件即为记录的集合，和“查找表”的差别在于，“文件”指的是存储在外存储器中的记录的集合。记录是文件中可以存取的数据的基本单位。
二、文件可按其中记录的类型不同而分成两类：
其一为操作系统的文件，文件中的记录仅是一个字符组。由于操作系统中的文件仅是一维的连续字符序列，为了用户存取和加工的方便，将文件中的信息划分为若干组，其中每一组信息称作一个记录；
其二为数据库文件，文件中的记录带有结构，是数据项的集合。记录是文件中可以存取的数据基本单位，数据项是文件中可以使用的数据最小单位。
三、记录中能识别不同记录的数据项被称为关键字，若该数据项能唯一识别一个记录，则称为主关键字，若能识别多个记录则称为次关键字。
四、文件的逻辑结构指的是呈现在用户面前的文件中记录之间的逻辑关系；文件的物理结构指的是文件中的逻辑记录在存储器中的组织方式。
五、文件的操作：
1．检索：
顺序存取：存取“当前记录的”下一个记录；直接存取：存取第i个记录；
按关键字存取：存取其关键字等于给定值的记录。
2．修改：
往文件中插入一个或一批记录；
从文件中删除一个或一批记录；
更新文件中某个记录的属性。
3．排序
文件的操作方式可以实时处理或批量处理
本章讨论文件的几种常见的物理结构。
12.2 顺序文件
结构特点：
记录在文件中的排列顺序是由记录进入存储介质的次序决定的，即文件物理结构中记录的排列顺序和文件的逻辑结构中记录的排列顺序一致。
顺序文件的具体组织形式有两种：
连续文件：次序相继的两个物理记录其存储位臵相邻；
串联文件：物理记录之间的顺序由指针相链。操作特点：
1．便于进行顺序存取；
2．不便于进行直接存取，为取第i个记录，必须先读出前i-1个记录，对于磁盘上的等长记录的连续文件可以进行折半查找；
3．插入新的记录只能加在文件的末尾；
4．删除记录时，只作标记；
5．更新记录必须生成新的文件。
顺序文件的插入、删除和更新操作在多数情况下都采用批处理方式。此时，为处理方便，通常将顺序文件作成有序文件，称作“主文件”，同时将所有的操作作成一个“事务文件”（经过排序也成为有序文件），所谓“批处理”，就是将这两个文件“合”为一个新的主文件。具体操作相当于“归并两个有序表”，但有两点不同：（1）对于事务文件中的每个操作首先要判别其“合法性”；（2）事务文件中可能存在多个操作是对主文件中同一个记录进行的。
批处理的时间分析：
假设主文件中含有n个记录，事务文件中含有m个记录，则对事务文件进行排序的时间复杂度为O(m log m）；内部归并的时间复杂度为O(m+n），则总的内部处理的时间为O(m log m+n）；
假设对外存进行一次读/取为s个记录，则整个批处理过程中读/写外存的次数为
2?（?m/s?+?(m+n)/s?）
12.3 索引文件
一、结构特点：
1．索引文件由“主文件”和多级“索引”组成。
２．索引中的每个记录(索引项)由“关键字”和“指针”组成。
３．通常，索引文件中的主文件是无序文件，索引是(按关键字有序)的有序文件。
４．“索引”是在输入数据建立文件时自动生成。初建时的“索引”为无序文件，经过排序后成为有序文件。
二、操作的特点：
１．检索方式为：直接存取和按关键字存取。“检索”将分两步进行：先查索引，然后根据索引中指针所指索取记录。
２．插入记录时，“记录”插入在主文件的末尾，而相应的“索引项”必须插入在索引的合适位臵上。因此，最好在建索引表时留有一定“空位”。
３．删除记录时，仅需删除索引表中相应的索引项即可。
４．更新记录时，应将更新后的记录插入在主文件的末尾，同时修改相应的索引项。
三、“索引”的结构
１．多级静态索引
此时的索引文件结构：
对主文件中每个记录建立一个索引项：
主关键字记录在主文件中的存储位臵
称作稠密索引，由这些索引项构成索引表；
从索引表建立的索引称查找表，其中每个索引项为：
最大关键字其所在数据块的存储位臵
称这类索引为非稠密索引。类似地，由查找表建立的索引为第二查找表;由第二查找表建立的索引为第三查找表。
按关键字进行检索时，从第三查找表开始，至多访问外存五次。
２．动态索引
索引表采用查找树表或哈希表。优点：
（１）不需要建立多级索引;
（２）初建索引不需要进行排序;
（３）插入或删除记录时，修改索引方便;
用查找树表作索引时，查找索引所需访问外存次数的最大值恰为查找树的深度。可以作索引的树表有：二叉排序树、B-树和键树
稠密索引的优点是，可以实现“预查找”
缺点是，索引表占用的存储空间大。
12.4 索引顺序文件
结构特点：
主文件按主关键字有序，对一组记录建立一个索引项(建立非稠密索引)。
有两种典型的索引顺序文件
一、ISAM文件
ISAM(I ndex S equential A ccess M ethod)(索引顺序存取方法)是一种专为磁盘存取设计的文件组织方法。
１．文件的组织方式：
主文件按柱面集中存放，同时建立三级索引：磁道索引、柱面索引和主索引。
磁道索引结构
关键字指针关键字指针
基本索引项溢出索引项
２．操作的特点：
检索：可有两种方式：
顺序存取—依关键字最小至大顺序存取
按关键字存取—从主索引开始，到柱面索引，到磁道索引，最后取得记录，先后访问四次外存。
插入:
将记录插入在某个磁道的合适位臵上;
将该磁道上关键字最大的记录移出到本柱面的溢出区中;
修改本磁道的索引项(包括基本索引项和溢出索引项)。
删除:
在被删记录当前存储位臵上作“删除标记”。
３．文件重组
在经过多次的插入和删除操作之后，大量的记录进入文件的“溢出区”，而“基本存储区”中出现很多已被删去的记录空间，此时的文件结构很不合理。因此，对ISAM文件，需要周期地进行重整。
４．柱面索引的位臵
ISAM文件占有多个柱面，其柱面索引应设在数据文件的中间位臵上，以使“磁头”的平均移动距离最小。
二、VSAM文件
VSAM(V istual S torage A ccess M ethod)文件是利用操作系统中提供的虚拟存储器的功能组
织的文件，免除了用户为读/写记录时直接对外存进行的操作，对用户而言，文件只有控制区间和控制区域等逻辑存储单位。
１．文件的结构
由索引集、顺序集和数据集三部分组成。
数据集内含若干控制区域，而控制区域内含若干控制区间，每个控制区间内含一个或多个记录，当含多个记录时，同一控制区间内的记录按关键字自小至大有序排列，且文件中第一个控制区间中记录的关键字最小;
顺序集内存放的是数据集的索引，每个控制区间有一个索引项，它由两部分信息组成：该控制区间中记录的最大关键字和指向该控制区间的指针。若干相邻控制区间的索引项形成顺序集中的一个结点，结点之间用指针相链;
索引集是顺序集的索引，即文件的高层索引项，也由最大关键字和指针两部分信息组成。
从索引文件的角度看，数据集即为主文件，而顺序集和索引集构成“索引”。
２．控制区间是用户进行一次存取的逻辑
单位，可看成是一个逻辑磁道。但它的实际大小和物理磁道无关。
控制区域由若干控制区间和它们的索引项组成，可看成是一个逻辑柱面。
VSAM文件初建时，每个控制区间内的记录数不足额定数，并且有的控制区间内的记录数为零。
３．顺序集本身是一个单链表，它包含文件的全部索引项，同时，顺序集中的每个结点即为B+树的叶子结点，索引集中的结点即为B+树的非叶结点。
４．文件的操作
检索：可进行顺序存取和按关键字存取;
插入：按关键字大小插入在某个适当的控制区间中，当控制区间中的记录数超过文件
规定的大小时，要“分裂”控制区间，
必要时，还需要“分裂”控制区域;
删除：必须“真实地”删除记录，因此要在控制区间内“移动”记录;
５．VSAM文件通常被作为大型索引顺序文件的标准组织方式。
其优点是：动态地分配和释放空间，不需要重组文件；能较快地实现对“后插入”的记录的检索;
其缺点是：占有较多的存储空间，一般只能保持约75%的存储空间利用率。(因此，一般情况下，极少产生需要分裂控制区域的情况)
12.5 直接存取文件
１．和前几节讨论的文件组织方法不同，直接存取文件的特点是，由记录的关键字“直接”得到记录在外存上的映象地址。
类似于哈希表的构造方法，根据文件中关键字的特点设计一种“哈希函数”和“处理冲突的方法”将记录散列到外存储设备上，又称“散列文件”。
２．散列文件的结构
由于记录在外存上是成组存放的，因此允许多个记录映象到同一个地址上。在此，称外存储器中存放多个记录的“数据块”为“桶”。因此由哈希函数得到的映象地址为“桶地址”。例如：有一组关键字如下所列
{589，063，269，505，764，182，166，330} 假设哈希函数为key MOD 7，每个桶可以容纳3个记录（称桶的容量为3），则可得散列文件如下所示：
1
2
3
4
5
6
在哈希文件中，“冲突”和“溢出”是不同的概念。一般情况下，假设桶的大小为m，则允许哈希地址产生m-1次的冲突，当发生第m次冲突时，才需要进行“冲突处理”，对散列文件而
言，通常采用链地址法出路冲突。为区别起见，称直接“散列”的数据块为“基桶”，而因“溢出”存放的数据块为“溢出桶”。
３．文件的操作
检索：只能进行按关键字的查找，不能进行顺序查找。检索时，先在基桶内进行查找，
若不存在，则再到溢出桶中进行查找。
插入：当查找不成功时，将记录插入在相应的基桶或溢出桶内。
删除：对被删记录作特殊标记。
４．优点：记录随机存放，不需要进行排序；插入、删除方便，存取速度快；节省存储空间，不需要索引区。
缺点：不能进行顺序存取；在经过多次插入和删除操作之后，需进行“重组文件”的操作。
12.6 多关键字文件
一、多关键字文件的特点
除需要对主关键字建立“主索引”外，尚需对各个次关键字建立“次索引”。
次索引项：次关键字（指向记录的）指针
二、次索引的组织方法
1．多重链表文件
特点：将所有具有相同次关键字的记录链接在同一链表中，该链表的头指针即为次索引项中“指针域”的值。
2．倒排文件
特点：将所有具有相同次关键字的记录构成一个次索引顺序表，此时的次索引顺序表中仅存放记录的“主关键字”或记录的“物理记录号”。次索引项中的“指针”指向相应的次索引顺序表。
3．次关键字索引表本身的结构可以是顺序表，也可以是树表或哈希表，视具体的次关键字的特性而定。
第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据
类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
数据结构复习题集 一、判断题 1.线性表的长度是线性表所占用的存储空间的大小。( F ) 2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。( F ) 3.在对链队列做出队操作时，不会改变front指针的值。( F ) 4.如果两个串含有相同的字符，则说它们相等。( F ) 5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。(T ) 6.已知一棵树的先序序列和后序序列，一定能构造出该树。( F ) 7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。(T ) 8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。( F ) 9.对一个堆按层次遍历，不一定能得到一个有序序列。(T ) 10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。(T ) 11. 线性表的逻辑顺序与物理顺序总是一致的。( F ) 12. 线性表的顺序存储表示优于链式存储表示。( F ) 13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。(T ) 14. 二维数组是其数组元素为线性表的线性表。( F )
15. 每种数据结构都应具备三种基本运算：插入、删除和搜 索。(T ) 16.（101，88，46，70，34，39，45，58，66，10）是堆；(T ) 17.将一棵树转换成二叉树后，根结点没有左子树；( F ) 18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；(F) 19.哈夫曼树是带权外部路径长度最短的树，路径上权值较大的结点离根较近( T ) 20.用一组地址连续的存储单元存放的元素一定构成线性表。(F) 21.堆栈、队列和数组的逻辑结构都是线性表结构。( T ) 22.给定一组权值，可以唯一构造出一棵哈夫曼树。( F) 23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。索引表可以常驻内存。( T) 24.在平均情况下，快速排序法最快，堆积排序法最节省空间。( T) 25.快速排序法是一种稳定性排序法。( F ) 二.选择题: 1.一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。 A.23415 B.54132 C.31245 D.1425 3 2．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。 A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n 3．二叉树在线索化后，仍不能有效求解的问题是（D）。
第一章 1. 怎样理解“算法+数据结构=程序”这个公式？举例说明。 算法是语句序列解决特定问题的固有程序片段。数据结构是确定数据间的关系。从具体问题抽象出一个合适的数学模型、然后设计一个解决此数学模型的算法，最后编写出程序。寻求数学模型的是指就是数据结构要完成的工作。参看书p1前两段的描述。 2. 数据结构的概念，它包含哪三方面的内容？ 数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科。参看书p3 包含三方面的内容:1、数据之间的逻辑关系2、数据在计算机中的存储方式3、在数据上定义的运算的集合。 3. 数据、数据元素、数据项的基本概念。举例说明数据元素和数据项的联系与区别。 数据：描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑或处理。 数据项：数据项是具有独立含义的最小标识单位，是数据元的一个具体值，是数据记录中最基本的、不可分的有名数据单位。 例1：class A { int c[123]; int i; }; class B { A a; } B b; b.a是数据项，B是数据元素 例2：一本书的数目信息为一个数据元素，而数目信息中每一项（如书名、作者名等）为一个数据项 4. 从逻辑结构来看，数据结构有哪四种基本结构，各自的特点是什么？ 1、集合（数据元素之间同属于一个集合，再无其他关系） 2、线性结构（数据元素之间存在一对一的关系） 3、树形结构（数据元素之间一对多的关系） 4、图状结构或网状结构（数据元素之间多对多的关系） 5. 从物理结构来看，数据结构有哪两种基本结构，各自的特点是什么？ 1、顺序存储结构 特点：借助元素在存储器中的相应位置来表示数据元素之间的逻辑关系。 2、链式存储结构 特定：借助元素在存储地址的指针表示数据元素之间的逻辑关系。 6. 算法的5个特征，4个评价标准是什么？ 特征:有穷性、确定性、可行性、输入、输出。 评价标准：正确性、可读性、健壮性、效率与低存储量需求。 7. 描述时间复杂度。
? 4.2 基本体的表面取点 ? 4.3 平面与立体表面的交线 结束放映 ? 4.1 基本体的三视图 ? 4.4 立体与立体表面的交线 ? 4.5 基本体三维造型
4.1 基本体的三视图 常见的基本几何体 平面基本体曲面基本体
一、画基本体三视图的方法步骤 1 .确定三个视图的位置。选择立体上的一个点或立体的对 称中心线、主要棱线、平面等作为画图参考基准；先画 出它们的三个视图（布图），注意要做到横平竖直。 2.画出反映立体主要形状特征（实形）的视图。 3 .再根据立体的长、宽、高尺寸（相对坐标），依照“长 对正、高平齐、宽相等”的规律，完成另外两个视图。 4 .视图完成后，应擦去作图辅助线。 ?立体是具有三维坐标的实心体，研究的立体投影是研究立体表面的投影。 ?立体是有具体形状和尺寸大小的形体。画三视图时，主要用长、宽、高方向的相对坐标，与投影轴无关，从这里开始不再画出投影轴。
开始画三视图！ 在图示位置时,五棱柱的上 下两底面为水平面,在俯视图中反映实形（五边形）.后侧棱面是正平面,其余四个侧棱面是铅垂面,它们的水平投影都积聚成直线,与五边形的边重合。 ⑵ 五棱柱的三视图 ⑴ 棱柱的组成 由上下两个底面和若干侧棱面组成。侧棱面与侧棱面的交线叫侧棱线，侧棱线相互平行。 1.棱柱 二、平面基本体 ● a 0 ● a 0" ● a 0' ● (１)布图:选点ＡＯ画图参考基准，画出其三个投影图。 ２) 画出反映立体主要形状特征的俯视图。 (３) 由“长对正”和立体的高度画出主视图。 ４利用“宽相等”和"高平齐”画出左（二求三）。 三视图概念
#include
void ClearList_L(Linklist L)/*将L重置为空表*/ { Linklist p; if(!L) printf("ERROR\n"); else { while(L->next) { p=L->next; L->next=p->next; free(p); } printf("OK\n"); } } void ListEmpty_L(Linklist L)/*L为空表返回TRUE，否则返回FALSE*/ { if(!L) printf("ERROR\n"); else { if(!L->next) printf("TRUE\n"); else printf("FLASE\n"); } } int ListLength_L(Linklist L)/*返回L中数据元素个数*/ { int i=0; Linklist p=L; if(!L) return 0; else { while(p) { i++; p=p->next; } return i; } }
1.复杂性分析 对各种操作的时间复杂性的分析。 主要是链表，树，排序等简单一些的分析。 分析的时候，从简单的入手，学会方法。 后续的各种豆可能让你分析时间复杂度。 线性链表（顺序表和单链表） 链表循环链表 双向链表 2.线性结构队列（循环队列） 栈 链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。栈：查找，插入（位置固定），删除（位置固定） 队列：查找，插入（位置固定），删除（位置固定） 顺序表（可以视为一个数组） 单链表： （删除）
（插入）
倒置： （查找）
循环链表 双向链表 栈： （插入删除查找）
队列 （插入删除查找） 循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。 3.二叉树 基本概念 二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。 二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。 二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别： 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态： (1)空二叉树——如图(a)； (2)只有一个根结点的二叉树——如图(b)； (3)只有左子树——如图(c)； (4)只有右子树——如图(d)； (5)完全二叉树——如图(e) 注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形 性质 (1) 在非空二叉树中，第i层的结点总数不超过, i>=1； (2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点； (3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1； (4) 具有n个结点的完全二叉树的深度为 (5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： 若I为结点编号则如果I>1，则其父结点的编号为I/2； 如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子； 如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。 (6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。 （7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i 存储结构
第03章栈和队列 3.1栈的基本概念 （一）栈顶top位置的说明： 1.在空栈中，top和base都指向整个栈的起始地址（也就是即将分配的第一个元素的地址）； 2.在非空栈中，top始终是指向栈顶元素的下一个元素的地址。 （二）入栈操作（先压后加）：Stack[top++]=e （三）出栈操作（先减后弹）：e = Stack[--top] （四）栈不存在的判断条件：base==NULL （五）栈空的判断条件：base==top （六）栈满的判断条件：top – base = MaxSize 三、顺序栈的C语言实现 typedef struct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int StackSize; //顺序栈的初始容量（初始分配的能够容纳的元素个数） }SqStack; 四、顺序栈的操作 1.初始化栈——构造一个空栈 Status InitStack(SqStack &S) { S.base = (SElemType*)malloc(Stack_Init_Size*sizeof(SElemType)); if(S.base==NULL) exit(OverFlow); //存储空间分配失败 S.top = S.base; S.StackSize = Stack_Init_Size; } 2.获取栈顶元素——若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR Status GetTop(SqStack S,SElemType &e) { if(S.top==S.base) return ERROR; //栈空 e = *(top – 1); return OK; } 3.入栈——插入元素e作为新的栈顶元素 Status Push(SqStack &S,SElemType e) { if(S.top – S.base >= S.StackSize) //栈已满，需要追加存储空间 { S.base = (SElemType*)realloc(S.base,(S.StackSize+StackIncrement)*sizeof(SElemType)); if(!S.base) exit(OverFlow); //存储空间分配失败 S.top = S.base + S.StackSize; S.StackSize += StackIncrement; } *S.top++ = e; //*指针运算符和++自加运算符优先级相同，但是其结合方向是自右向左 Return OK; }