数据结构导论知识点

1、数据结构导论知识点第一章概论数据结构：是相互之间存在一种或多种关系的数据元素的集合。和该集合中数据元素之间的关系组成。数据结构包括数据的逻辑结构、数据的存储结构和数据的基本运算。简单地说，数据结构是计算机组织数据和存储数据的方式。更进一步地说，数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的操作。合理的数据结构可降低程序设计的复杂性，提高程序执行的效率。1.1引言计算机解决一个具体问题时，一般需要经过以下几个步骤：从具体的问题抽象出一个适当的数学模型；设计一个求解该数学模型的算法；用某种计算机语言编写实现该算法的程序，调试和运行程

2、序直至最终得到问题的解答。数据的逻辑结构：数据和数据的组织方式称为数据的逻辑结构。为了能用计算机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。1976 年瑞士计算机科学家尼克劳斯· 维尔特提出公式：算法+数据结构 =程序。该公式简洁的描述了数据结构和程序之间关系。1.2基本概念和术语数据、数据元素和数据项数据：所有被计算机存储、处理的对象。数据元素：简称元素（又称为结点） ，数据的基本单位，在程序中作为一个整体而加以考虑和处理。数据元素是运算的基本单位，通常具有完整确定的实际意义。数据元素由数据项组成。数据项：在数据库中数据项又称为字段或域，是数据的不可分割的最小标识单位，

3、组成数据元素。关系：数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据元素组成，而数据元素又可由若干个数据项组成。表格（逻辑结构） ，行 =记录 =数据元素，列 =数据项。数据的逻辑结构数据的逻辑结构：是指数据元素之间的逻辑关系。逻辑关系：是指数据元素之间的关联方式或邻接关系。逻辑结构示意图中的小圆圈称为结点，一个结点代表一个数据元素（记录）。根据数据元素之间关系的不同特性，通常有集合、线性结构、树形结构和图结构四类基本逻辑结构，反映了四类基本的数据组织形式。四类基本逻辑结构：集合：集合中任何两个结点之间都没有邻接关系，组织形式松散。线性结构：线性结构中结点按逻辑关系依次

4、排列形成一条“ 链 ”，结点之间一个一个依次相邻接。树形结构：树形结构具有分支、层次特性，其形态有点像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。图结构：图结构最复杂，任何两个结点都可以邻接。数据的逻辑结构与存储无关，独立与计算机。数据的存储结构数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）一个存储结构包括两个部分：存储数据元素。数据元素之间的关联方式。表示数据元素之间的关联方式主要有：顺序存储方式：是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。（使用数组，内存地址连续）链式存储方

5、式：是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。索引存储方式。散列存储方式。一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储现象。运算运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。在每个逻辑结构上，都定义了一组基本运算，包括：建立、查找、读取、插入和删除等。线性表、栈和队列中的元素具有相同的逻辑结构（即线性结构） ，但有不同的运算集，是不同的数据结构。1.3算法及描述运算的实现是指该运算的算法。算法是计算机科学的一个基本概念，也是程序设

6、计的一个基本概念。一个算法规定了求解给定问题所需的处理步骤及其执行顺序，使给定问题在有限的时间内被求解。算法可以用某种语言描述。1.4算法分析评价算法好坏的因素包括：正确性：能正确的实现预定的功能，满足具体问题的需要。易读性：易于阅读、理解和交流，便于调试、修改和扩充。健壮性：即使输入非法数据，算法也能适当的做出反应或进行处理，不会产生预料不到的运行结果。时空性：一个算法的时空性是指该算法的时间性能（或时间效率）和空间性能（或时间效率），前者是算法包含的计算量，后者是算法需要的存储量。时间复杂度估算算法的计算量，可将基本操作次数作为该算法的时间度量。（执行次数最多的语句的执行次数。）假如问题的

7、输入规模为n，一般情况下，一个算法的计算量是问题规模n 的函数，一个算法的时间复杂度是算法输入规模的函数。常见算法时间复杂度的阶数有常数O(1) （最优的时间复杂度，与输入规模n 无关）、对数阶 O(log 2n) 、线性阶O(n) 、多项式阶 ( 平方阶 )O(n C) 、和指数阶O(Cn ) ， C 为大于 1 的正整数。通常认为，时间复杂度具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效的。O(1) O(log 2n) O(n) O(n C) O(Cn) 。最坏时间复杂度：对相同输入数据量的不同输入数据，算法时间用量的最大值。平均时间复杂度：对所有相同输入数据量的各种不同输

8、入数据，算法事件用量的平均值。空间复杂度一个算法的空间复杂度定义为该算法所耗费的存储空间。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在执行期间所需要的存储空间量包括：程序代码所占用的空间。输入数据所占用的空间。辅助变量所占用的空间。在估算法算法空间复杂度时，一般只需要分析辅助变量所占用的空间。第二章线性表2.1线性表的基本概念线性表（ Linear List）是一种线性结构，是由n（n0）个数据元素组成的有穷数列，数据元素又称为结点。结点个数n 称为表长。 a1 称为起始结点，an 称为终端结点，ai 称为ai+1 的直接前驱， ai+1 称为 ai 的直接后继。线

9、性表的基本特征：线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱，除终端结点没有直接后继，其他每个结点有且仅有一个直接前驱，一个直接后继。线性表的基本运算及功能描述：初始化 Initiate(L)：建立一个空表L=() ， L 不含数据元素。求表长 Length(L)：返回线性表L 的长度。读表元素Get(L,i)：返回线性表第i 个数据元素，当i 不满足 1i Length(L)返回一特殊值。定位 Locate(L,x)：查找线性表中数据元素值等于x 的结点序号，若有多个数据元素值与 x 相等，运算结果为这些结点中序号的最小值，若找不到该结点，则运算结果为0。时，插入

10、 Insert(L,x,i)：在线性表L 的第 i 个数据元素之前插入一个值为x 的新数据元素，参数i 的取值范围是1i n+1。插入后线性表L 表长度加1。删除 Delete(L,i)：删除线性表L 的第 i 个数据元素ai ， i 的有效取值范围是1i n。删除后线性表L 表长度减 1。2.2线性表的顺序存储顺序表是最简单的一个存储方式。线性表顺序存储的类型定义线性表顺序存储的方法是：将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表。一般使用数组来表示

11、顺序表。假定线性表的数据结构的类型是 DataType ，顺序表的结构定义，学生档案信息表的顺序存储实现：const int Maxsize=7;/预先定义一个足够大的常量，作为数组的最大长度typedef struct/定义一个结构体类型int num;/学号char name8;/姓名char sex2;/性别int age;/年龄int score;/入学成绩DataType;/定义结点类型typedef structDataType dataMaxsize;/存放数据的数组int length;/顺序表的实际长度SeqList;/顺序表类型名为 SeqListSeqList stude

12、nt;/定义 student为一个顺序表线性表的基本运算在顺序表上的实现（插入、删除、定位的最优、最坏、平均时间复杂度都是 O(n) ）1. 插入顺序表的插入运算InsertSeqlist(SeqList L, DataType x, int i)第 i （1i n+1）个元素之前，插入一个新元素x。使长度为表。是指在顺序表的n 的线性表变为n+1 的线性插入算法的具体步骤：首先将结点ai an 依次向后移动一个元素的位置，空出第数据元素的位置，然后将x 置入该该空位，表长加1。插入算法描述：i 个void InserSeqlist(SeqList L, DataType x, int i)/

13、将元素 x 插入到顺序表L 的第 i 个数据元素之前if (L.length=Maxsize) exit(“表已满 ”);if (i<1|i>L.length+1) exit(“位置错 ”); /检查插入位置是否合法for(j=L.length;j>=i;j-)/初始 i=L.lengthL.dataj=L.dataj-1;/依次后移L.datai-1=x;/元素 x 置入到下标为L.length+;/表长度加 1i-1的位置顺序表中结点的物理顺序和线性表中结点的逻辑顺序保持一致。顺序表插入算法的元素比较和移动的次数是（ n-i+1 ）次，平均移动次数是 n/2 ，时间复杂度

14、为 O(n) 。2. 删除删除运算 DeleteSeqlist(SeqList L, int i)是指将线性表的第i （1i n）个数据元素删去，使长度为n 的线性表变为n-1 的线性表。当i=n删除算法的基本步骤是：结点 ai an 依次向左移动一个元素位置，覆盖掉被删结点表长度减1，不考虑溢出，只判断参数i 是否合法。删除算法描述：时，直接将表长度减ai 。1 即可。void DeleteSeqlist(SeqList L, int i)/删除顺序表L 中的第i 个数据结点if (i<1|i>L.length+1) exit( for(j=i;j<L.length;j+)

15、 L.dataj-1=L.dataj; L.length-;/“非法位置 ”);/检查插入位置是否合法第 i 个元素的下标为依次左移表长度减1i-1顺序表删除算法的元素比较和移动的次数是（n-i ）次，最坏情况下元素移动次数为（n-1 ），元素平均移动次数约为（n-1 ） /2 ，时间复杂度为O(n) 。3. 定位定位运算 LocateSeqlist(SeqList L, DataType x)的功能是查找出线性表中值等于的结点序列号的最小值，当找不到值为x 的结点时，返回结果0。下列算法从左往右扫描顺序表中的元素，考察元素的值是否等于x。定位算法描述：xint LocateSeqlist(S

16、eqList L, DataType x)int i=0;while (i>L.length+1) (L.datai!=x);/i+;if(j<L.length) return i+1;/else return 0;/在顺序表中查找值为x 的结点若找到值为x 的元素，返回元素的序号未查找到值为x 的元素，返回0顺序表定位算法以参数顺序表的求表长操作x 与表中结点值得比较为操作标准，平均时间复杂度为Length(L)，直接输出L.length。O(n) 。顺序表实现算法的分析从算法的实现中可以看出，在线性表的基础操作中，最频繁的是数据元素的比较和移动。在分析线性表的顺序表实现算法时，

17、一个重要的指标就是数据元素的比较和移动次数。设表的长度length=n ，再插入算法中，元素的移动次数不仅与顺序表的长度n 有关，还与插入的位置i 有关。顺序表插入算法中，元素比较和移动的次数是（n-i+1 ）次，平均移动次数是n/2 ，时间复杂度为O(n) 。顺序表删除算法中，元素比较和移动的次数是（n-i ）次，最坏情况下元素移动次数为（n-1 ），元素平均移动次数约为（n-1 ） /2 ，时间复杂度为O(n) 。顺序表定位算法，需要扫描顺序表中的元素，以参数x 与表中结点值的比较为标准操作，平均时间复杂度为O(n) 。求表长和读表元素算法的时间复杂度为O(1) ，阶数最低。顺序表的插入、

18、删除算法在时间性能方面是不理想的。2.3线性表的链式存储线性表常见的链式存储结构有：单链表：是最简单的。循环链表。双向循环链表。单链表的类型定义链表的结点结构：|data|next|data 部分成为数据域，用于存储线性表的一个数据元素。 next 部分成为指针域或链域，用于存放一个指针，指针指向本结点所含数据元素的直接后继。所有结点通过指针链接形成链表(LinkList) ， head 成为头指针变量，可以用头指针变量命名单链表。学生档案信息链表的类型描述：typedef struct/定义一个结构体类型int num;/学号char name8;/姓名char sex2;/性别int ag

19、e;/年龄int score;/入学成绩DataType;/定义结点类型typedef struct nodeDataType data;/数据域struct node *next; /指针域node, *LinkList;/Node是链表结点的类型LinkList head;为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结点，称为头结点，其他结点称为表结点。表结点中的第一个和最后一个结点分别是首结点和尾结点。线性表的基本运算在单链表上的实现初始化单链表的初始化描述： InitiateLinkList 的功能是建立一个空表，空表由一个头指针和一个头结点组成。LinkList I

20、nitiateLinkList() /建立一个空的单链表LinkList head;/head=malloc(sizeof(Node); /头指针动态构建头结点head->next=NULL;return head;在算法中 , 变量 head 是链表的头指针，指向新创建的结点，即头结点。一个空单链表仅有一个头指针，它的指针域为NULL。求表长在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外的结点的个数。单链表的求表长描述：通过结点的指针域来从头至尾访问每一个结点。int LengthLinklist(LinkList head) /求单链表表 head

21、的长度Node *p=head;/p是工作指针，初始时p 指向头结点int cnt = 0;/计数器置初值while(p->next!=NULL)p=p->next;/指针移动到下一个结点cnt+;return cnt;/返回表长读表元素给定一个序列号i ，查找线性表的第i 个元素。单链表的读表元素描述：从头指针出发，一直往后移动，直到第i 个结点。Node *GetLinklist(LinkList head, int i)/ 在单链表 head 中查找第 i 个元素结点。找到返回指向该结点的指针，否则返回NULLNode *p;/p是工作指针p=head->next;/初

22、始时， p 指向首结点int c=1;while(c<i) (p!=NULL) /当未到第 i 结点且未到结尾结点时继续后移p=p->next; c+;if(i=c) return p;/找到第 i 个结点else return NULL;/i<1或 i>n ， i 值不合法，查找失败注意： p!=NULL 在这里作为判断是否以遍历整个链表的条件，不可遗漏。定位定位运算又称为安值查找。线性表的定位运算，是对给定表元素的值，找出这个元素的值。在单链表实现中，则是给定一个结点的值，找出这个结点是单链表的第几个结点。单链表的定位运算描述：从头至尾访问链表，直至找到需要的结点，

23、返回其序列号；若未找到，返回 0。int LocateLinklist(LinkList head,DataType x)/ 求单链表表head 中第一个值等于x 的结点的序号，若不存在这种结点，返回结果0Node *p=head;p=p->next;int i = 0;while(p!=NULL/p/i p->data!=x)/是工作指针初始时 p 指向头结点代表结点的序号，这里置初值为访问链表0i+;p=p->next;if(p!=NULL) return i+1;else return 0;插入单链表的插入运算是将值为x 的元素插入到链表 head 的第 i 个结点之前

24、。单链表的插入运算描述：先找到链表的第i-1 个结点 q，生成一个值为x 的新结点p， p 的指针域指向q 的直接后继结点， q 的指针域指向 p。void InserLinklist(LinkList head,DataType x,int i)/ 在单链表 head 的第 i 个数据元素结点之前插入一个值为x 的新结点Node *p,*q;if (i=1) q=head;else q=GetLinklist(head,i-1);/找第 i-1个数据元素结点if (q=NULL)/第 i-1 的结点不存在exit( “ 找不到插入的位置 ”);elsep=malloc(sizeof(Node

25、);p->data=x; /生成新结点p->next=q->next;/新结点链域指向 *q 的后继结点q->next=p;/修改 *q 的链域单链表的插入运算操作p->next=q->next和q->next=p语句执行顺序不能颠倒。删除单链表的删除运算是给定一个值i ，将链表中第i 个结点从链表中移除，并修改相关结点的指针域，以维持剩余结点的链接关系。单链表的删除运算描述：将ai 结点移除后，需要修改该结点的直接前驱结点ai-1针域，使其指向移除结点ai 的直接后继结点ai+1 。的指void DeleteLinklist(LinkList hea

26、d,int i)/ 在单链表head 中删除第i 个数据结点Node *q;if (i=1) q=head;else q=GetLinklist(head,i-1); /先找待删除结点的直接前驱if (q!=NULL q->next!=NULL) /若直接前驱存在且待删除结点存在p=q->next;/p指向待删除结点q->next=p->next;/移出待删除结点free(p);/释放以移出结点p 的空间else exit(“ 找不到要删除的结点”); /结点不存在free(p)是必不可少的，当一个结点从链表中移出后，若不释放它的空间，它将变成一个无用的结点，并一直占用

27、着系统内存空间，其他程序将无法使用这块空间。2.4其他运算在单链表上的实现建表根据线性表元素的邻接关系，建立该线性表的单链表。建立含头结点的单链表：首先建立带头节点的空表。其次建立一个新结点，然后将新结点链接到头结点之后，这个结点为尾结点（首结点）。最后重复建立新结点和将新结点链接到表尾这两个步骤，直到线性表中所有元素链接到单链表中。1. 建立单链表方法一： 通过已实现的初始化和插入算法来实现，依次增大插入位置i ，使新的结点链入到链表中。每次插入都从表头开始查找，比较浪费时间。算法 InserLinklist主要部分是找到第 i 个位置，然后将新结点插入，计算量约等于i 。线性表有 n 个元

28、素，插入位从1 到 n，方法一算法的计算量约为n(n+1)/2，时间复杂度为 O(n2) 。LinkList CreatLinkList1()/ 通过调用初始化和插入算法实现建表算法。假定0 是输入结束标志LinkList head;int x,i;head=InitiateLinkList(); /建立空表i=1;/置插入位置初值scanf( “%d”, x);/读入第一个数据元素， x 为整型while(x!=0)/输入的不是结束标志时继续插入InserLinklist(head,x,i); /将输入插入到head 表尾i+;/修改插入位置scanf( “%d”, x);/读下一个元素re

29、turn head;2. 建立单链表方法二：每次把新结点链接到链尾，用一个指针指向尾结点，为下一个新结点指明了插入位置。时间与元素个数成正比，时间复杂度为O(n) 。用方法二建立的链表，数据顺序与输入顺序相同。LinkList CreatLinkList2()/q是一个 LinkList类型的变量，用来指示链入的位置LinkList head;Node *q,*t;int x;head=malloc(sizeof(Node);/生成头结点q=head;/尾指针置初值scanf( “%d”, x);/读入第一个数据元素，x 为整型while(x!=0)/输入的不是结束标志时继续链入t=mallo

30、c(sizeof(Node);t->data=x; /生成一个新结点q->next=t;/新结点链入q=t;/修改尾指针q，指向新结点scanf( “%d”, x);/读下一个元素q->next=NULL;return head;3. 建立单链表方法三： 将新增加的结点插入到头结点之后，第一个数据结点之前，称为前插操作。时间复杂度为 O(n) 。用方法三建立的链表，数据顺序与输入顺序相反。LinkList CreatLinkList3()LinkList head;Node *p;int x;head = malloc(sizeof(Node); /生成头结点head->

31、;next = NULL;scanf( “%d”, x);while(x)/x=0时结束输入p = malloc(sizeof(Node);p->data = x;p->next = head->next;/前插：插入到链表的第一个结点处head->next = p;scanf( “%d”, x);return head;删除重复节点设计算法删除重复结点，只保留结点序号最小的那个结点。用链表作为存储结构，算法描述：void PurgeLinkList(LinkList head)/删除表 head 中多余的重复结点Node *p,*q,*r;q = head->n

32、ext;/q指示当前检查结点的位置，置其初值指向首结点while(q!=NULL)/当前检查结点*q 不是尾结点时，寻找并删除他的重复结点p = q;/工作指针p 指向 *qwhile(p->next!=NULL)/当*p 的后继结点存在时，将其数据域与if(p->next->data=q->data) /*q 数据域比较若*(p->next)是 *q的重复结点r=p->next;/rp->next=r->next;/移出结点free(r);elsep=p->next;/q=q->next;/指向待删结点*(p->next),p

33、->next指向原来 *(p->next)否则，让p 指向下一个结点更新检查结点的后继结点为了便于删除操作，P 指针始终指向 “ 当前比较结点 ” 的前驱结点。2.5其他链表2.5.1循环链表在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表中，从任一结点出发能够扫描整个链表。常见的循环链表：带头结点的非空循环链表；带头结点的空循环链表；设立尾指针的非空循环链表；设立尾指针的空循环链表。（头指针 head；尾指针 rear ，首结点表示为： rear->next->next）2.5.2双向循环链表双向循环链表与单链表类似，用类C 语言描述如

34、下：struct dbnodeDatatype data;struct dbnode *prior,*next;typedef struct dbnode *dbpointer;typedef dbpointer DLinkList;在单链表的每个结点中在设置一个指向其直接前驱结点的指针域prior ，这样每个结点有两个指针，结点结构： |prior|data|next|。头结点的 prior指向最后一个结点，最后一个结点的next 指向头结点，由这种结点构成的链表称为双向循环链表。单链表找直接后继结点的时间复杂度是O(1) ，双向循环链表是一种对称结构，找前驱结点和后继结点的时间复杂度均为O

35、(1) 。双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。双向循环链表的对称性可以用下列等式表示：p=p->prior->next=p->next->prior结点 p 的前驱结点的1. 删除next和后继结点的prior都指向结点p。在双向循环链表中删除结点时，设 p 指向待删结点，删除 p->prior->next=p->next; /p 前驱结点的后链指向 p->next->prior=p->prior; /p 后继结点的前链指向 free(p); / 释放 *p 的空间*p 可以通过下述语句完成：p 的后继结点p 的

36、前驱结点其中、这两个语句的执行顺序可以颠倒。2. 插入在双向循环链表中，在p 所指结点的后面插入一个新结点*t ，需要修改四个指针： t->prior=p; t->next=p->next; p->next->prior=t; p->next=t;2.6顺序实现与链接实现的比较顺序表优点：随机存储数据元素；缺点：需要预先分配存储空间。链表优点：插入、删除方便，不需要预先分配空间；缺点：需要分配存储指针空间。第三章栈、队列和数组3.1栈栈的基本概念栈是运算受限的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶，另一端称

37、为栈底。不含任何数据元素的栈称为空栈。处于栈顶位置的数据元素称为栈顶元素。栈的修改原则是后进先出 (Last In First Out) ，栈又称为后进先出线性表，简称后进先出表。栈的插入和删除运算分别称为进栈和出栈。栈的基本运算：初始化 InitStack(S)：构造一个空栈S；判栈空 EmptyStack(S) ：若栈 S为空栈，则结果为1，否则结果为0；进栈 Push(S,x) ：将元素x 插入栈 S 中，使 x 成为栈 S 的栈顶元素；出栈 Pop(S) ：删除栈顶元素。取栈顶 GetTop(S) ：返回栈顶元素。栈的顺序实现栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个元素

38、，并用始端作为栈底。栈的顺序实现称为顺序栈。通常用一个一维数组和一个记录栈顶元素位置的变量来实现栈的顺序存储。在出栈前判断栈是否为空，如果空栈作出栈运算，会产生在进栈前判断是否栈满，如果栈满作进栈运算，会产生顺序栈用类C 语言定义如下：“下溢 ”。“上溢 ”。const int maxsize=6;/顺序栈的容量typedef struct seqstackDataType datamaxsize;/存储栈中数据元素的数组int top; /标志栈顶位置的变量SeqStk;上述定义存放到Seqstack.h中。下面列出栈的基本运算在顺序栈上的实现算法：初始化int InitStack(SeqS

39、tk *stk)stk->top=0;return 1;判栈空 EmptyStack(S)int EmptyStack(SeqStk *stk)/if(stk->top=0);return 1;elsereturn 0;若栈为空，则返回值1，否则返回值0进栈int Push(SeqStk *stk, DataType x)/ 若栈未满，元素x 进栈 stk中，否则提示出错信息if (stk->top=maxsize-1);/ error (“ 栈已满 ”); return 0;else stk->top+;/stk->datastk->top=x; /ret

40、urn 1;判断栈是否满栈未满， top元素 x 进栈值加1出栈int Pop(SeqStk *stk)if (EmptyStack(stk);/判断是否下溢（栈空） error (“ 下溢 ”); return 0;else/未下溢，栈顶元素出栈stk->top-;/top值减1return 1;取栈顶元素DataType GetTop(SeqStk *stk)/ 取栈顶数据元素，栈顶数据元素通过参数返回if (EmptyStack(stk) return NULLData;/栈空，返回NULLDataelsereturn stk->datastk->top;/返回栈顶数据

41、元素在某些应用中，为了节省空间，让两个数据元素类型一致的栈共享一维数组空间 datamax ，成为双栈，两个栈的栈底分别设在数组两端，让两个栈彼此迎面增长，两个栈的栈顶变量分别为 top1 、 top2 ，仅当两个栈的栈顶位置在中间相遇时 (top1+1=top2) 才发生“ 上溢 ”。双栈的数据结构定义为：const int max=40;/栈容量typedef struct DbstackDataType datamax;int top1,top2;DbStk;双栈中判断上溢语句为top1+1=top2栈， top2=max-1 时栈 2 为空栈。，判栈空时，两个栈不同，当top1=0时栈

42、1 为空栈的链接实现栈的链接实现称为链栈，链栈可以用带头结点的单链表实现。LS 指向链表的头结点，首结点是栈顶元素， LS->next 指向栈顶结点，尾结点为栈底结点。各结点通过链域的链接组成栈，由于每个结点空间都是动态分配产生，链栈不用预先考虑容量的大小。链栈用类 C 语言定义如下：typedef struct nodeDataType data;struct node *next;LkStk;将上述定义存放到Lkstack.h中。栈的基本运算在链栈上的实现算法如下：初始化void InitStack(LkStk *LS)LS=(LkStk *)malloc(sizeof(LkStk)

43、;LS->next=NULL;/建立一个空栈判栈空int EmptyStack(LkStk *LS)/若栈为空，则返回值1，否则返回值0if(LS->next=NULL);return 1;elsereturn 0;进栈（在进栈操作算法中采用前插操作，新增结点始终插入到头结点之后）void Push(LkStk *LS, DataType x)LkStk *temp;temp=(LkStk *)malloc(sizeof(LkStk);/temptemp->data=x;/temp->next=LS->next;/tempLS->next=temp;/指向申

44、请的新结点新结点的data 域赋值为x的 next 域指向原来的栈顶结点指向新的栈顶结点出栈（出栈操作始终是栈顶结点出栈，即删除头结点之后的结点）int Pop(LkStk *LS)/ 栈顶数据元素通过参数返回，它的直接后继成为新的栈顶LkStk *temp;if (!EmptyStack(LS)/判断是否为空temp=LS->next;/temp指向栈顶结点LS->next=temp->next;/原栈顶的下一个结点成为新的栈顶free(temp);/释放原栈顶结点空间return 1;elsereturn 0;取栈顶元素DataType GetTop(LkStk *LS)

45、/if (!EmptyStack(LS)return LS->next->data;/else return NULLData;/取栈顶元素若栈非空，返回栈顶数据元素否则返回空元素例子：借助栈将带头结点的单链表逆置。将链表逆置，其实是将链表结点中数据元素倒置，由于不知道链表的长度，可以用链栈来实现。扫描链表，将链表中数据元素依次进栈，然后，再一次扫描链表，同时依次进行出栈操作，将出栈的元素依次填到链表中去。算法描述如下：void ReverseList(LkStk *head)LkStk *S;DataType x;InitStack(S);/p=head->next;while(p!=NULL)/Push(S,p->data);/p=p->next;p=head