NOIP高中信息技术竞赛资料数据结构.docx

第1章 绪论程序设计就是运用计算机解决现实世界中的实际问题。对于给定的一个实际问题，在进展程序设计时，首先要把实际问题中用到的信息抽象为可以用计算机表示的数据；第二要把抽象出来的这些数据建立一个数据模型，这个数据模型也称为逻辑构造，即建立数据的逻辑构造；第三要把逻辑构造中的数据及数据之间的关系存放到计算机中，即建立数据的存储构造；最终在所建立的存储构造上实现对数据元素的各种操作，即算法的实现。本章就是要使大家理解计算机中的数据表示，理解数据元素、逻辑构造、存储构造和算法的有关概念；驾驭根本逻辑构造和常用的存储方法，可以选择适宜的数据的逻辑构造和存储构造；驾驭算法及算法的五个重要特性，可以对算法进展时间困难度分析，从而选择一个好的算法，为后面的学习打下良好的根底。1.1根本概念和术语1.数据(data)：是对客观事物的符号的表示,是全部能输入到计算机中并被计算机程序处理的符号的总称。2.数据元素(data element):是数据的根本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项（data item）组成，数据项是数据不行分割的最小单位。3.数据构造(data structure):是互相之间存在一种或多种特定关系的数据元素的集合。数据构造是一个二元组，记为:data_structure=(D,S).其中D为数据元素的集合，S是D上关系的集合。数据元素互相之间的关系称为构造（structure）。依据数据元素之间关系的不同特性，通常由下列四类根本构造：（1）集合:数据元素间的关系是同属一个集合。（图1）（2）线性构造:数据元素间存在一对一的关系。（图2）（3）树形构造：构造中的元素间的关系是一对多的关系。（图3）（4）图（网）状构造：构造中的元素间的关系是多对多的关系。（图4） 图1 图2 图3 图41.2 数据的逻辑构造和物理构造1.逻辑构造：数据元素之间存在的关系（逻辑关系）叫数据的逻辑构造。即上面给出的四种构造。2.物理构造：数据构造在计算机中的表示（映象）叫数据的物理构造，又称存储构造。一种逻辑构造可映象成不同的存储构造：依次存储构造和非依次存储构造（链式存储构造和散列构造）。1.3算法及算法分析1. 算法：是对特定问题求解步骤的一种描绘，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。 2. 算法的重要特性 输入：一个算法应当有零个或多个输入。 有穷性：一个算法必需在执行有穷步骤后正常完毕，而不能形成无穷循环。 确定性：算法中的每一条指令必需有准确的含义，不能产生多义性。 可行性：算法中的每一条指令必需是实在可执行的，即原则上可以通过已经实现的根本运算执行有限次来实现。 输出：一个算法应当有一个或多个输出，这些输出是同输入有某个特定关系的量。 3. 算法的时间困难度定义：设问题的规模为n，把一个算法的时间消耗T(n)称为该算法的时间困难度，它是问题规模为n的函数。算法的渐进时间困难度设T(n)为一个算法的时间困难度，假如当n趋向无穷大时T(n)与函数f(n)的比值的极限是一个非零常数M，即记作T(n)=O(f(n)，则称O(f(n)为算法的渐进时间困难度，简称时间困难度，也称T(n)与f(n)的数量级一样，通常，f(n)应当是算法中频度最大的语句的频度。常用的算法的时间困难度的依次O(1)<O(lgn)<O(n)<O(n·lgn)<O(n2)<O(n3)<<O(2n)算法的时间困难度不仅仅依靠于问题的规模，还与输入实例的初始状态有关。例如：在数组A0.n-1中查找给定值K的算法如下：(1)i=n-1;(2)while(i>=0&&(Ai!=k)(3) i-;(4)return i;此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关：若A中没有与K相等的元素，则语句(3)的频度f(n)=n；若A的最终一个元素等于K，则语句(3)的频度f(n)是常数0。 最坏时间困难度和平均时间困难度最坏状况下的时间困难度称为最坏时间困难度。一般不特殊说明，探讨的时间困难度均是最坏状况下的时间困难度。这样做的缘由是：最坏状况下的时间困难度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何状况下更长。平均时间困难度是指全部可能的输入实例均以等概率出现的状况下，算法的期望运行时间。 例1 求下列交换两个变量i和j的值的算法的时间困难度。(1) i=10;(2) j=20;(3) t=i;(4) i=j;(5) j=t;解：各行语句的执行次数均为1，所以该算法的时间消耗T(n)= 1+1+1+1+1=5，该算法的时间消耗T(n)与问题的规模n无关，因此，该算法的时间困难度T(n)=O(1)。例2 求两个n阶方阵的乘积C=A×B，其算法如下，计算该时间困难度。程序段：(1) for(i=0; i<n; i+)(2) for(j=0; j<n; j+)(3) cij=0;(4) for(k=0; k<n; k+)(5) cij+=aik*bkj; 解：解法1计算程序段中的每一行的执行次数。第(1)行for(i=0; i<n; i+)中只考虑循环条件表达式i<n的执行次数（忽视初始化表达式i=0和修正表达式i+的执行次数，下同），表达式i<n共执行n+1次（i为0到n-1时该表达式非零，共n次，i为n时该表达式为零，共1次，合计执行n+1次），所以，第(1)行共执行n+1次；第(2)行for(j=0; j<n; j+)，在第(1)行for(i=0; i<n; i+)中的表达式i<n非零时（共n次）都要执行一遍，而每一遍同样要执行n+1次，所以，第(2)行共执行n（n+1）次；第(3)行cij=0;在表达式i<n和j<n均非零时执行，共执行n2次；第(4)行for(k=0; k<n; k+)在表达式i<n和j<n均非零时执行一遍，而每一遍同样要执行n+1次，所以，第(4)行共执行n2（n+1）次；第(5)行cij+=aik*bkj; 在表达式i<n、j<n和k<n均非零时执行，共执行n3次；因此，各行执行次数分别为：n+1，n（n+1），n2，n2（n+1），n3。假如用T(n)表示该算法的时间消耗，则 T(n)= n+1+n（n+1）+n2+n2（n+1）+n3=2n3+3n2+2n+1由此可知，该算法的时间消耗T(n)是矩阵阶数n的函数，T(n)=O(n3)。解法2只计算执行频度最高的行。明显，在该程序段中，执行频度最高的行为cij+=aik*bkj; 在表达式i<n、j<n和k<n均非零时执行，而表达式i<n、j<n和k<n均有n次非零，所以，该行共执行n3次。因此，该算法的时间消耗T(n)是矩阵阶数n的函数，T(n)=O(n3)。【课堂理论】分析并计算下面程序段执行的时间困难度。i=1; k=0; while(i<=n-1) k+=10*i;i+;第2章 线性表线性表是最常用且最简洁的一种数据构造，一个线性表是n个数据元素的有序系列，每个数据元素可以是一个数或一个符号，也可以使一页书，甚至其他更困难的信息。如26个字母的字母表：（A,B,C,D.,Z）在困难的线性表中，一个数据元素可以由若干个数据项组成，在这种状况下，常把数据元素称为一个记录，含有大量记录的线性表又称文件。如图综合上述例子，可以将线性表描绘为：线性表是由n个数据元素的有限序列(a1,a2,an)组成的，其中每一个数据元素ai的详细含义可以按不同的状况和要求定义详细的内容，它可以是一个数、一个符号、一串文字，甚至是其他更困难的信息。线性表中数据元素的个数n称为线性表的长度。2.1 线性表的逻辑构造及根本运算1.线性表简洁的定义n个数据元素的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。线性表中的数据元素不仅可以进展访问，还可进展插入和删除。若n=0，则表示一个空表，即没有任何数据元素的线性表；若n>0，则除a1和an外，有且仅有一个干脆前驱和一个干脆后继，即ai(其中1< i<n)是线性表中第i个数据元素，在ai之前仅有一个数据元素ai-1，而在ai之后也仅有一个数据元素ai+1。称a1称为起始结点，an称为终端结点，i称为ai在线性表中的序号或位置。线性表中结点的之间的关系就是上述的邻接关系，由于该关系是线性的，我们称线性表是一种线性构造。2.线性表的根本运算（1）线性表初始化格式：InitList(L)初始条件：线性表L不存在。操作结果：构造一个空的线性表L。（2）求线性表的长度格式：LengthList(L)初始条件：线性表L存在。操作结果：返回线性表L中全部元素的个数。（3）取表元格式：GetList(L，i)初始条件：线性表L存在，且1iLengthList(L)。操作结果：返回线性表L的第i个元素(ai)的值。（4）按值查找格式：LocateList(L，x)初始条件：线性表L存在，x有确定的值。操作结果：在线性表L中查找值为x的数据元素，并返回该元素在L中的位置。若L中有多个元素的值与x一样，则返回首次找到的元素的位置；若L中没有值为x的数据元素，返回一个特殊值（通常为-1）表示查找失败。（5）插入操作格式：InsertList(L，i，x)初始条件：线性表L存在，i为插入位置（1in+1，n为插入前的表长）。操作结果：在线性表L的第i个元素(ai)位置上插入值为x的新元素，原序号为i,i+1, ,n的数据元素的序号插入后变为i+1,i+2, ,n+1，插入后表长=原表长+1。（6）删除操作格式：DeleteList(L，i)初始条件：线性表L存在，i（1in）为给定的待删除元素的位置值。操作结果：在线性表L中删除序号为i的数据元素(ai)，删除后，原序号为i+1,i+2, ,n的数据元素的序号变为i,i+1, ,n-1，删除后表长=原表长-1。注：以上给出的是线性表的根本运算，并不是全部运算，其它运算可用这些根本运算来实现，这些运算都是定义在逻辑构造层次上的运算，只有确定了存储构造之后，才能详细实现这些运算。例1 假设两个线性表LA,LB分别代表两个集合A和B:求A=A U Bvoid union(List &La ,List &Lb)/将全部在线性表Lb中，但不在La中的数插入到La中La.len=ListLength(La);Lb.len=ListLength(Lb); /求两表的长度for(i=1;i<=Lb.len;i+) GetElem(Lb,i,e);/取Lb中第i个的元素复制给eIf(!LocateElem(La,e,equal)ListInsert(La,+La.len,e);/若其中不存在一样的，则插入/union例2 已知线性表la，lb中的数据元素按值非递减有序排列，现要求将la，lb归并为一个新的线性表lc且lc按值非递减。例如 la=（3,5,8,11）, Lb=(2,6,8,9,11,15,20)则lc=(2,3,5,6,8,8,9,11,11,15,20)分析：由于两表都是依据肯定依次进展排列，全部设置2个指针，分别指向a、b表，先分别比拟比拟最初指向的两数据，比拟一下大小，谁小就放入到c表中，然后数小的指针向下挪动，再进展比拟。直到2表有一表完毕,再将剩余的表存放到c中。Void MergeList(List La, List Lb,List &Lc)/已知线性表la和lb中的数据元素InitList(Lc);/初始化表cInt i=j=1;k=0;La.len=ListLength(La);Lb.len= ListLength(Lb);While(i<= La.len)&&( (j<= Lb.len)GetElem（La,i,ai）;GetElem（Lb,j,bj）;/获得数值If(ai<=bj)ListInsert(Lc,+k,ai);i+;elseListInsert(Lc,+k,bj);j+;/if完毕/whie完毕,其中一表完毕；While(i<=La.len)/表B数据全访问完，表a未到最终GetElem（La,i+,ai）;ListInsert(Lc,+k,ai);While(j<=Lb.len)/表a数据全访问完，表b未到最终GetElem（Lb,j+,bj）;ListInsert(Lc,+k,bj);/程序完毕分析：上述2个算法的时间困难度（根本操作的执行时间），例1为O(ListLength(La)*ListLength(Lb),例2的时间困难度为O(ListLength(La)+ListLength(Lb)。2.2 线性表的依次存储构造线性表的依次存储即用一组地址连续的存储单元依次存储线性表中的元素。设线性表中每个元素需占用r个存储单元则 loc（ai+1 ）=loc（ai）+r loc（ai）=loc（a1）+（i-1）*r线性表的这种机内表示称做线性表的依次存储构造或依次映像，通常，称这种存储构造的线性表为依次表。只要确定了存储线性表的起始位置，线性表中任一数据元素可随机存储，所以线性表的依次构造是一种随机存储的存储构造。/=线性表的动态依次存储构造#define LIST_INIT_SIZE 100 / 初始安排量#define LISTINCREMENT 10 /安排增量Typedef structElemtype *elem; /存储空间基址Int length; /当前长度Int listsize; /当前安排的存储容量SqList;Elem表示基地址，length指示线性表的当前长度。上述的含义是为依次表安排一个预定义大小的数据空间，并将当前的长度设为0；Status InitList_sq(SqList &L)/=创立一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);/ ElemType指数据类型，malloc新安排空间If(!L.elem) exit(OVERFLOW);/存储安排失败L.length=0;/空表长度为0L.listsize= LIST_INIT_SIZE;/初始存储容量Return ok；/InitList_sq在这种存储方式下，简洁实现对表的遍历。要在表的尾部插入一个新元素，也很简洁。但是要在表的中间位置插入一个新元素，就必需先将其后面的全部元素都后移一个单元，才能腾出新元素所需的位置。Status ListInsert_sq(SqList &L,int I,ElemType e)/在依次表中插入一个新元素 eIf(i<1|i>L.length+1) return Error;If(L.length>= L.listsize)/当前存储空间已满，增加安排Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType);/ ElemType指数据类型，realloc再次安排，L.elem存储基地址/ifq=&(L.elemi-1);/q为插入位置for(p=&(L.elemL.length-1);p>=q;-p)*(p+1)=*q;/for*q=e;/插入e+ L.length；Return ok；执行删除运算的情形类似。假如被删除的元素不是表中最终一个元素，则必需将它后面的全部元素前移一个位置，以填补由于删除所造成的空缺。这两种运算的时间困难度均为O(n)n为表的长度。Status ListDelete_sq(SqList &L,int I,ElemType &e)/在依次表中插入一个新元素 eIf(i<1|i>L.length+1) return Error;p=&(L.elemi-1);/p为删除位置e=*p;q=L.elem+L.length-1;for(+p;p<=q;+p)*(p-1)=*p;/for- L.length；Return ok；2.3 线性表的链式存储构造 线性表依次构造的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存储表中的任一元素，但是在插入删除时须挪动大量元素。而线性表的链式存储由于其不要求逻辑上相邻，因此它没有依次存储构造的弱点，但同时也失去了依次表可随机存取的优点。1.单链表线性链表的特点是用一组随意的存储单元存储线性表的元素，用指针将存储表元素的那些单元依次串联在一起。这种方法避开了在数组中用连续的单元存储元素的缺点，因此在执行插入或删除运算时，不再须要挪动元素来腾出空间或填补空缺。然而我们为此付出的代价是，须要在每个单元中设置指针来表示表中元素之间的逻辑关系，因此增加了额外的存储空间的开销。为了将存储表元素的全部单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域如图所示：其中，存储单元由两局部构成，即数据域存储数据元素，指针域存储下一个元素所在的单元假如表是a1,a2,an ，那么含有元素ai的那个单元中的指针应指向含有元素ai+1的单元(i=1,2,n-1)。含有an的那个单元中的指针是空指针null。此外，通常我们还为每一个表设置一个表头单元header，其中的指针指向开场元素中所在的单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更简洁处理。这一点我们在后面可以看到。假如我们情愿单独地处理诸如在表的第一个位置上进展插人与删除操作等边界状况，也可以简洁地用一个指向表的第一个单元的指针来代替表头单元。上述这种用指针来表示表的构造通常称为单链接表，或简称为单链表或链表。单链表的逻辑构造如图1所示。表示空表的单链表只有一个单元，即表头单元header，其中的指针是空指针null。 图1 单链表示意图为了便于实现表的各种运算，在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置i是一个指针，它所指向的单元是元素ai-1所在的单元，而不是元素ai所在的单元(i=2,3,n)。位置1是指向表头单元header的指针。位置End(L)是指向单链表L中最终一个单元的指针。这样做的目的是为了避开在修改单链表指针时须要找一个元素的前驱元素的费事，因为在单链表中只设置指向后继元素的指针，而没有设置指向前驱元素的指针。单链表存储构造Typedef struct LnodeElemType data;Struct Lnode *next;/指向后继节点的指针Lnode, *LinkList;/线性链表的本质就是指针根本运算(1)ListInsert.L(L,i,e)功能:在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,an，那么在执行Insert(x,p)后，表L变为a1,a2,ap-1,x,ap,an 。若p为End(L)，那么表L变为a1,a2,an,x 。若表L中没有位置p，则该运算无定义。实现P为指向a节点的指针，s为指向X节点的指针:s->next=p->next; p->next=s;上述算法中，链表指针的修改状况见图2图2(a)是执行Insert运算之前的状况。我们要在指针p所指的单元之后插入一个新元素x。图2(b)是执行Insert运算以后的结果，其中的虚线表示新的指针。在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前断定。往一个单链表中插入新元素通常在表头或表尾进展，因此p的合法性简洁断定。Insert运算所需的时间明显为O(1)。(2)Delete(p)功能:从表L中删除位置p的下一元素。例如，当L为a1,a2,an时，执行Delete(p)后，L变为a1,a2,ap-1,ap+1,an 。当L中没有位置p或p=End(L)时，该运算无定义。实现:p.next=p.next.next;这个过程很简洁，其指针的修改如图3所示。若要从一个表中删除一个元素x，但不知道它在表中的位置，则应先用Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元素。Delete过程所需的时间明显也为O(1)。2.静态链表静态链表：用游标指示数组单元地址的下标值，它属整数类型数组元素是记录类型，记录中包含一个表元素和一个作为游标的整数；详细说明如下:type jid=record data:datatype; next:integer; end;var alist=array0.maxsize of jid游标即我们可以用游标来模拟指针, 对于一个表L，我们用一个整型变量Lhead(如Lhead=0)作为L的表头游标。这样，我们就可以用游标来模拟指针，实现单链表中的各种运算。当i>1时，表示第i个位置的位置变量pi的值是数组alist中存储表L的第i-1个元素next值,用p:=alist(p).next后移。照此，我们虽然是用数组来存储表中的元素，但在作表的插人和删除运算时，不须要挪动元素，只要修改游标，从而保持了用指针实现表的优点。因此，有时也将这种用游标实现的表称为静态链表。3.循环链表循环链表是另一种链式存储构造，特点是表中最终一个结点的指针域指向头结点，整个链表形成一个环。因此，可由表中任一结点动身均可找到表中其他结点。如图6所示的是一个单链的循环链表或简称为单循环链表。(a)非空表(b)空表图6单循环链表在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p.next指向表头单元；后者是p或p.next指向空(nil)。在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在O(1)时间内找到表L中的第一个元素。然而要找到表L中最终一个元素就要花O(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指针表示一个表L。但是，假如我们用指向表尾的指针表示一个表L时，我们就可以在O(1)时间内找到表上中最终一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在O(1)时间内找到表L中的第一个元素。在很多状况下，用这种表示方法可以简化一些关于表的运算。4.双链表单循环链表中，只有一个指示干脆后继的指针域，虽然从任一单元动身，可以找到其前驱单元，但须要O(n)时间。假如我们盼望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。图8 双链表由于在双链表中可以干脆确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。双链表的单元类型定义如下。 和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的next指针指向表头单元，构成如图9所示的双向循环链表。图9 双向循环链表下面仅以双向循环链表为例给出三种根本运算的实现。(1)在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。 上述算法对链表指针的修改状况见图10。图10 在双向循环链表中插入一个元素算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置p的合法性。由于插入通常是在表的头尾两端进展的，所以简洁检查位置p的合法性。(2)从双向循环链表L中删除位置p处的元素可实现如下:上述算法对链表指针的修改状况见图11。图11 从双向循环链表中删除一个元素5.链表的应用例1：求 (A-B)U(B-A)其中A,B代表两个集合（用静态链表）例2 求p1(x)+p2(x) (两个多项式的和）练习题：1.约瑟夫问题:有M个猴子围成一圈，每个有一个编号，编号从1到M。准备从中选出一个大王。经过协商，确定选大王的规则如下：从第一个开场，每隔N个，数到的猴子出圈，最终剩下来的就是大王。要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。(程序）2.求多项式的减与乘法.(程序）第3章 栈栈是一种特殊的线性表，它的逻辑构造与线性表一样，只是其运算规则较线性表有更多的限制，故又称它为运算受限的线性表。3.1 栈的概念及运算栈（Stack）是限制仅在表的一端进展插入和删除运算的线性表。向栈中插入元素称为进（入）栈，从栈中删除元素称为退（出）栈。通常插入、删除的这一端称为栈顶，由于元素的进栈和退栈，使得栈顶的位置常常是变动的，因此须要用一个整型量Top指示栈顶的位置，通常称Top 为栈顶指针；另一端称为栈底。当表中没有元素时称为空栈，即Top=-1。栈的修改是按后进先出的原则进展。每次删除的总是当前栈中“最新”的元素，即最终插入的元素，而最先插入的是被放在栈的底部，要到最终才能删除。假设一个栈S中的元素为an,an-1,.,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a1 ,a2,.,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进展的，如图1所示。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以运用栈。 图1栈的运算：为一种抽象数据类型，常用的栈运算有:运算含义inistack(S)使S成为一个空栈。getTop(S)这是一个函数，函数值为S中的栈顶元素。Pop(S)从栈S中删除栈顶元素，简称为抛栈。Push(S,x)在S的栈顶插入元素x，简称为将元素x入栈。Empty(S)这是一个函数。当S为空栈时，函数值为true，否则函数值为false。3.2 栈的存储与实现1.依次栈及根本操作的实现由于栈是运算受限线性表，因此线性表的存储构造对栈也适用，而线性表有依次存储和链式存储两种，所以，栈也有依次存储和链式存储两种。（1）依次栈：栈的依次存储构造简称为依次栈，它是运算受限的依次表。（2）依次栈的描绘#define StackSize 100 /假定栈空间最多为100个元素typedef char DataType;/假定栈元素的类型为字符类型typedef structDataType dataStackSize;/栈元素定义int top;/栈指针定义SeqStack; SeqStack *S;/ 定义栈S设S是SeqStack类型的指针变量，则栈顶指针可表示为S-> top；若栈底位置在向量的低端，则S->data0是栈底元素，栈顶元素可表示为S->dataS-> top。留意：有元素x进栈时，须要先将S->top加1，然后再将元素进栈，即依次完成下列操作：+S->top;S->dataS-> top=x;。当栈顶元素做退栈操作后，须要将S->top减1，即完成操作：S->top-;。条件S->top=StackSize-1表示栈满；S->top=-1表示栈空。当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出错状态，应设法避开。当栈空时，做退栈运算所产生的溢出现象称为下溢。3、依次栈上根本运算的算法置栈空void InitStack（SeqStack *S）/将依次栈置空     S->top=-1;判栈空假如栈S为空，则S->top=-1，此时应当返回1，而关系表达式S->top=-1的值为1；假如栈S为非空，则S->top!=-1，此时应当返回0，而关系表达式S->top=-1的值为0，因此，无论怎样只需返回S->top=-1的值。int StackEmpty（SeqStack *S）return S->top=-1;判栈满与判栈空的道理一样，只需返回S->top=StackSize-1。int StackFull（SeqStack *S）return S->top=StackSize-1;进栈进栈操作须要将栈和进栈元素的值作为函数参数，由于运用栈指针作为函数参数，对栈进展操作，所以进栈函数不须要有返回值；进栈操作时，须要推断是否栈满，当栈不满时，先将栈顶指针加1，再进栈。int Push（SeqStack *S，DataType x）if (StackFull(S)puts("栈满"); return 0; S->data+S->top=x;/栈顶指针加1后将x入栈return 1;退栈退栈操作须要将栈指针作为函数参数，并返回栈顶元素的值，所以函数返回值的类型为DataType；退栈操作时，须要推断是否栈空，当栈不空时，先退栈，再将栈顶指针减1，可以先将栈顶元素的值记录下来，然后栈顶指针减1，最终返回记录下来的值，也可以像给出的退栈函数那样来操作。DataType Pop（SeqStack * S）if(StackEmpty(S)puts("栈空"); return 0;return S->dataS->top-;/返回栈顶元素并将栈顶指针减1取栈顶元素取栈顶元素与退栈的区分在于，退栈须要变更栈的状态，而取栈顶元素不须要变更栈的状态。DataType StackTop（SeqStack *S）if(StackEmpty(S)puts("栈空"); return 0;return S->dataS->top;由于栈的插入和删除操作具有它的特殊性，所以用依次存储构造表示的栈并不存在插入删除数据元素时须要挪动的问题，但栈容量难以扩大的弱点仍就没有摆脱。例 元素a1，a2，a3，a4依次进入依次栈，则下列不行能的出栈序列是Aa4, a3, a2, a1 Ba3, a2, a4, a1Ca3, a4, a2, a1 Da3, a1, a4, a2分析：对于A，由于元素a1，a2，a3，a4依次进栈，而a4先出栈，说明a1，a2，a3已经入栈，所以出栈依次只能是a4，a3，a2，a1，因此A是正确的出栈序列；对于B，C，D，由于都是a3先出栈，说明a1，a2已经入栈，所以a1，a2的相对位置肯定是不变的，这就是a2肯定在a1之前出栈，比拟上述三个答案，只有D中的a1出如今a2的前面，这明显是错误的。因此，答案为D。2.链栈及根本操作的实现若栈中元素的数目变更范围较大或不清晰栈元素的数目，就应当考虑运用链式存储构造。用链式存储构造表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在一端进展，而对于单链表来说，在首端插入删除结点要比尾端相对地简洁一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。链栈如图3.2。图3.2 链栈top栈顶栈底（1）链栈：栈的链式存储构造称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进展，栈顶指针就是链表的头指针。（2）链栈的描绘typedef char DataType;/假定栈元素的类型为字符类型typedef struct stacknode/结点的描绘DataType data;struct stacknode *next;StackNode;typedef struct/栈的描绘StackNode  *top;  /栈顶指针LinkStack; LinkStack *S; /定义指向链栈的指针S设S是LinkStack类型的指针变量，则S是指向链栈的指针，链栈栈顶指针可表示为S-> top；链栈栈顶元素可表示为S-> top ->data。设p是StackNode类型的指针变量，则p是指向链栈某结点的指针，该结点的数据域可表示为p ->data，该结点的指针域可表示为p -> next。留意：LinkStack构造类型的定义是为了便利在函数体中修改top指针本身。若要记录栈中元素个数，可将元素个数属性作为LinkStack类型中的成员定义。 条件S->top= NULL表示空栈，链栈没有栈满的状况。3、链栈上根本运算的算法置栈空 void InitStack（LinkStack *S）/将链栈置空S->top=NULL;判栈空int StackEmpty（LinkStack *S） return S->top=NULL;进栈void Push（LinkStack *S，DataType x ）/将元素x插入链栈头部StackNode *p=(StackNode *)malloc(sizeof(StackNode);p->data=x;p->next=S->top;/将新结点*p插入链栈头部S-