线性数据结构4动态建立单链表的算法

,第二级,第三级,第四级,第五级,第,2,章,线性数据结构,在此幻灯片插入公司的徽标,从“插入”菜单,选择图片,找到徽标文件,单击“确定”,重新设置徽标大小,单击徽标内任意位置。徽标外部出现的方框是“调整控点”,使用这些重新设置对象大小,如果在使用尺寸调整控点前按下,shift,键，则对象改变大小但维持原比例。,DATA,10,65,865,姓名 学号 成绩 班级,李红 9761059 95 机97.6,A,B,C,D,E,F,G,数据结构,第2章 线性数据结构,2.1 基本概念,2.1.1 数据和数据结构,2.1.2 算法的描述和评价,2.2 线性表,2.2.1 线性表的定义及操作,2.2.2 线性表的 顺序存储结构,2.2.3 线性表的链式存储结构,2.2.4 循环链表和双向链表,2.3 栈和队列,2.3.1 栈,2.3.2 队列,2.4 串和数组,2.4.1 串,2.4.2 数组,习题,2.1 基 本 概 念,2.1.1 数据和数据结构,现代数字计算机原是作为能快速地进行复杂、耗时计算的工具而发明的。随着计算机的发展，在计算机的绝大多数应用中，能够存取、处理大量信息的能力却被认为是计算机的首要特征，而它的计算能力在许多情况下已经几乎被人们忽略了。有位美国学者曾批评说：“,计算机,”这个词只告诉我们以前能做的事，却未道出它的潜能。有鉴于此，人们常常把计算机称作,数据处理机,。,什么是数据？,数据,就是,是信息的载体,它可以用计算机表示并加工,。可以看出，数据这个概念本身是随着计算机的发展而不断扩展的概念。在计算机发展的初期，由于计算机主要用于数值计算，数据指的就是,数值,。计算机硬件和软件技术的不断发展，扩大了计算机的应用领域，诸如,字符、文字、表格、图形、图像、声音等,也属于数据的范畴。,数据元素,是,数据集合中的一个个体，它是数据的,基本单位,。,例如：全部学生的学籍登记卡组成学生的学籍数据，每个学生的学籍登记卡就是学籍数据的一个数据元素。,数据元素可以是一个数或字符串，也可以由若干,数据项,组成(,数据的,最小单位,)。在这种情况下，通常把,数据元素,称为,记录,。如表2-1所示的学生学籍登记表，在这个表中每一个学生的学籍登记卡作为一个数据元素，每一个元素由学号、姓名、性别、民族、籍贯、专业六个数据项组成。,表2-1 学生学籍登记表,学 号,姓 名,性 别,民 族,籍 贯,专 业,1,王 安,男,汉,北京,计算机通信,2,李 华,男,回,河北,软 件,3,张 莉,女,汉,山西,计算机应用,4,张 平,女,汉,广东,软 件,什么是数据结构？在任何问题中，构成数据的数据元素并不是孤立存在的，它们之间存在着一定的关系以表达不同的事物及事物之间的联系。所以简单地说，,数据结构,就是,研究数据及数据元素之间关系的一门学科,。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它,包括三个方面的内容：,数据的逻辑结构。,数据的存储结构。,数据的运算。,1. 数据的逻辑结构,2. 数据的存储结构,3. 数据的运算： 检索、排序、插入、删除、修改等。,A . 线性结构,B . 非线性结构,A . 顺序存储,B . 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,反映数据元素之间的逻辑关系,数据元素在计算机内部的组织方式,C . 散列结构（散列表）,D . 索引结构（索引表）,1. 数据的逻辑结构,数据的逻辑结构,就是,数据元素之间的逻辑关系,。可以用一个二元组，给出其形式定义为,Data,Structure =(D，R),其中，,D,是组成数据的数据元素的有限集合，,R,是数据元素之间的关系集合。,根据数据元素之间关系的不同特性，数据结构又可,分为两大类,：,线性数据结构,和,非线性数据结构,。按照这种划分原则，本书介绍的所有数据结构如图2-1所示。,图2-1 数据结构分类,2数据的存储结构,数据的逻辑结构,是,从逻辑上来描述数据元素之间的关系的，是独立于计算机的,。然而讨论数据结构的目的是为了在计算机中实现对它的处理。因此还需要研究,数据元素和数据元素之间的关系如何在计算机中表示,，这就是,数据的存储结构,。,计算机的存储器是由很多存储单元组成的，每个存储单元有惟一的地址。,数据的存储结构,要讨论的就是,数据结构在计算机存储器上的存储映像方法。,实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。一般来说，数据在存储器中的存储有,四种基本的映像方法,。,(1),顺序存储结构,。这种存储方式主要用于线性数据结构，就是,把数据元素按某种顺序放在一块连续的存储单元中,。其,特点,是,逻辑上相邻的数据元素存储在物理上相邻的存储单元中,，元素之间的关系由存储单元的邻接关系来体现。,某些非线性数据结构也可以采用顺序方式存储，例如完全二叉树、多维数组等，具体方法将在后面介绍。,(2),链式存储结构,。链式存储结构,可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中,。即,可用一组任意的存储单元来存储数据元素，这些存储单元可以是连续的，也可以是不连续的,。另外对于非线性数据结构，还可以在线性编址的计算机存储器中表示结点之间的非线性关系。,链式存储结构的,特点,就是,将存放每个数据元素的结点分为两部分,：一部分存放数据元素(称为,数据域,)：另一部分存放指示存储地址的指针(称为,指针域,)，借助指针表示数据元素之间的关系。,(3),索引存储结构,。在线性表中，数据元素可以排成一个序列：R,1,、R,2,、R,3,、R,n,，每个数据元素R,i,在序列里都有对应的位置数据i，这就是元素的,索引,。索引存储结构就是,通过数据元素的索引号i来确定数据元素R,i,的存储地址,。一般索引存储结构的实现方法是建立附加的,索引表,，,索引表里,第i项的值就是第i个元素的存储地址,。,(4),散列存储结构,。这种存储方法就是,在数据元素与其在存储器上的存储位置之间建立一个映像关系F,。根据这个映像关系F，已知某数据元素就可以得到它的存储地址。即,D=F(E),，这里,E,是要存放的,数据元素,，,D,是该数据元素的,存储位置,。可见，这种存储结构的,关键,是,设计这个函数F,。但函数F不可能解决数据存储中的所有问题，还应有一套,意外事件的处理方法,，它们共同实现数据的散列存储结构。本书第4章中介绍的哈希表，就是散列存储结构的一个实例。,3. 数据的运算,数据的运算,是,定义在数据逻辑结构上的操作,，每种数据结构都有一个运算的集合。,常用的运算,有,检索、插入、删除、更新、排序等,。,运算的具体实现,要在,存储结构,上进行,。,数据的运算是数据结构的一个重要方面。讨论任何一种数据结构时都离不开对该结构上的数据运算及实现算法的讨论。,2.1.2 算法的描述和评价,算法,是,对特定问题求解步骤的一种描述，它是指令的有限序列,，其中每一条指令表示一个或多个操作。有时，把运算的实现称之为算法。,运算是定义,在,逻辑结构,上的操作，是独立于计算机的,，而,运算的具体实现,则,是在计算机上进行的，因此算法要依赖于数据的,存储结构,。,作为算法应具有下述的,五个重要特性,：,(1),有穷性,。一个算法必须在执行有穷步后结束，且每一步都能在有限的时间内完成。,(2),确定性,。算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得到相同的输出。,(3),可行性,。一个算法必须是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。,(4),输入,。一个算法应该有零个或多个输入。,(5),输出,。一个算法应该有一个或多个输出。,1. 算法的描述,算法需要用一种工具来描述，同时，算法可有各种描述方法以满足不同的需求。,常用的描述方法,有,自然语言描述、伪码描述、流程图描述、类PASCAL语言描述、C语言描述等,。本书中使用C语言作为描述算法的工具。,2. 算法的评价,在算法是“,正确性,”（,+,易读性 + 健壮性,）的前提下，评价算法主要有,两个指标,：,(1),时间复杂度（性）,：依据算法编制成程序后，在计算机上运行时所消耗的时间。,(2),空间复杂度（性）,：依据算法编制成程序后，在计算机执行过程中所需要的最大存储空间。,要确定实现算法在运行时,所花的时间,和,所占用的存储空间,，最直接的方法就是,测试,，即将依据算法编制的程序在计算机上运行，所得到的结果就是算法运行时所花的时间。这种方法有时也称为,事后统计的方法,。同一算法在不同档次的计算机上运行所花的时间肯定不同，这取决于计算机系统的速度。,另外一种方法就是,事前分析估算的方法,，这是人们常常采用的一种方法，下面将详细讨论之。,(1),时间复杂度,。假定知道算法中每一条语句执行一次所花的平均时间，则有：,算法运行所花的时间= 语句执行一次所花的时间, 语句执行次数,其中语句执行一次所花的平均时间取决于计算机系统中硬件、软件等环境因素，而一个算法中语句的执行次数一般来说是确定的。因此，对于事前分析估算方法，我们讨论的目标集中在确定语句的执行频度上，即把算法的,语句执行频度,作为衡量一个算法时间复杂度的依据。,在实际分析中，关注的是,频度的数量级,，即按重复执行次数最多的语句确定算法的时间复杂度。引入符号“O”来表示这种数量级，算法的时间复杂度记作：,T (n) = O (f ( n ) ),它表示随,问题规模,n,的增大，算法执行时间的增长率和函数,f (n),的增长率相同，称作算法的,渐近时间复杂度,，简称,时间复杂度,。,按数量级递增次序排列，,常见的几种时间复杂度,有：O(1)，O(logn)，O(n)，O(nlogn)，O(n,2,)，O(n,3,)，O(2,n,)，这里，,n表示问题的规模,。,例如，在下列三个程序段中：,(1) +x；s = 0；,T(n)= O(1),(2) for ( i = 1；i=n；+i ) (,常量阶,), +x；s += x；,T(n)= O(n),(3) for ( j = 1；j=n； +j ) (,线性阶,),for ( k = 1；k=n；+k ),T(n)= O(n,2,), +x；s +=x； (,平方阶,),含基本操作“x增1”的语句的频度分别为1，n和n,2,，则这三个程序段的时间复杂度分别为O(1)，O(n)和O(n,2,)，它们分别称为常量阶、线性阶和平方阶。,需要指出的是，有些算法的基本操作的,频度,不仅仅,依赖于问题的规模n,，还,取决于它所处理的输入数据集的状态i，即,T(n,i),。对于这一类算法，一般按每种情况发生的概率求出其数学期望值作为算法的,平均时间复杂度,，或者按最坏情况下基本操作的执行频度得出算法,最坏情况下的时间复杂度,，以此作为该算法的时间复杂度。,(2),空间复杂度,。一个算法的实现所占用的存储空间大致有这样,三个方面,：,其一,是,指令、常数、变量所占用的存储空间,；,其二,是,输入数据所占用的存储空间,；,其三,是,算法执行时必需的,辅助空间,。前两种空间是计算机运行时所必须的。因此，把算法在执行时所需的,辅助空间的大小,作为分析算法空间复杂度的依据,。,与算法时间复杂度的表示一致，也用辅助空间大小的,数量级,来表示算法的空间复杂度，仍然记为：,S(n)=O(f(n),。常见的几种空间复杂度有：O(1)，O(n)，O(n,2,)，O(n,3,)等。,事实上，一个问题的算法实现，,时间复杂度,和,空间复杂度,往往是,相互矛盾,的,，要降低算法的执行时间就要以使用更多的空间为代价，要节省空间就可能要以增加算法的执行时间作为代价，两者很难兼顾。因此，只能根据具体情况有所侧重。,2.2 线 性 表,2.2.1 线性表的定义及操作,定义2-1,线性表,(Linear-list),是n(n0)个数据元素的有限序列,。记为：,(a,1,，a,2, ., a,n,),其中，数据元素个数,n,称为,表,的,长,度，n = 0时，称此线性表为,空表,。,线性表的结构,仅涉及诸元素的,线性,相对位置,，即第i个元素a,i,处在第i-1个元素a,i-1,的后面和第i+1个元素a,i+1,的前面，这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。,线性表中每个,数据元素,a,i,的具体含义,，在不同情况下各不相同，它可以是一个数，或是一个符号，也可以是一页书，甚至是其它更复杂的信息。但在,同一个线性表中的数据元素必须具有相同的特性,(或者说,具有相同的类型,)。,线性表的逻辑结构,：,若线性表是非空表，则第一个元素a,1,无前趋，最后一个元素a,n,无后继，其它元素a,i,(1i=maxlen-1),printf( 线性表已满！n );,else, for( k =,v.,last; k = i; k- ),v.,elemk+1 =,v.,elemk;,v.,elemi = x;,v.,last+;,演示,算法2-2,线性表的,删除,算法。,已知线性表的当前状态是(a,1,，a,2,，a,i-1,，,a,i,，a,i+1,，a,n,)，若要删除第i个元素a,i,，则线性表成为(a,1,，a,2,，a,i-1,，a,i+1,，a,n,)。,具体,实施步骤,为：,(1),若i值合法，则将第i+1至第n个位置上的元素依次向,前移,动一个存储单位；,(2),将线性表的长度,减,1,。,.,a,2,a,1,a,n,.,a,i+1,a,i,0,1,i-1,i,n-1,删除线性表的第i个元素，后面所有元素前移。,a,i-1,.,a,2,a,1,a,last,a,i+1,a,i,a,i-1,.,a,2,a,1,a,i,a,i+1,a,last,删除,结点a,i,a,i+1,a,last,#define maxlen 100,struct sqlisttp,int elemmaxlen;,int last;,;,sqlisttp,v,;,void,delete(,sqlisttp,v, int,i), int k;,if (i,v.,last),printf( 删除位置不合适！n );,演示,else,for( k = i+1; k next;,while ( p!=NULL) & (counter next;,counter+;,if ( p!= NULL) & (counter = i ) /* 找到,1=in或inext = p-next,；,p-next = s,。,插入结点s后单链表的逻辑状态如图2-7所示。,图2-7 在单链表中插入结点S,算法2-4,void,insert,(NODE *head, int i, int x),NODE *p, *s;,int j=0;,p = head;,while ( p!=NULL) & (j next;,j+;,if (p = NULL) | (j i-1),printf( i值不合法 n); /* 找不到,in或i data = x; /*,*/,s - next = p - next; /*,*/,p - next = s; /*,*/,如果事先告之p指针所指的位置，则这种在p指针,后插,入,一个元素算,法,的时间复杂度,T(n)=O(1),，否则平均时间复杂度,T(n)=O(n),。,3) 单链表的删除,删除操作和插入操作一样，,(1),首先,要搜索单链表以,找到,指定,删除结点的,前趋结点,(假设为p)；,(2),然后,改变,链接,，即只要将待删除结点的指针域内容赋予p结点的指针域即可。,设有线性表(a,1,，a,2,，.，a,i-1,，,a,i,，a,i+1,，.，a,n,)，用带头结点的单链表存储，删除前的逻辑状态如图2-8所示。,删除元素a,i,所在的结点之后，单链表的逻辑状态如图2-9所示。,图2-8 带头结点的单链表,图2-9 在单链表中删除一个结点,算法2-5,void,delete,(NODE *head, int i),NODE *p, *s;,int j=0;,p = head;,while ( p-next != NULL) & (j next;,j+;,if (p-next = NULL) | (j i-1),printf(“i值不合法 n”); /* 找不到,in或i next;,p - next = s - next;,free(s);,如果事先告之p指针所指的位置，则这种在p指针,后删,除,一个元素算,法,的时间复杂度,T(n)=O(1),，否则平均时间复杂度,T(n)=O(n),。,4) 动态建立单链表的算法,要对单链表进行操作，首先要掌握怎样,建立,单链表,。链表是一种动态存储结构，所需的存储空间只有在程序执行,malloc,之后，才可能申请到一个可用结点空间；,free(p),的作用是系统回收一个结点，回收后的空间可以备作再次生成结点时用。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统应需求即时生成。因此，,建立线性表的链式存储结构的过程,就是一个动态生成链表的过程。即,从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表,。,动态建立线性表的链式存储结构有,两种,基本方法，分别适用于不同的场合。可根据所建链表结点的顺序要求选择采用一种方法。,单链表建立方法一：,反向,建立链表（头插法）,。,思想,：若线性表的元素已顺序存放在一维数组AN中，建表方法是从线性表的最后一个元素开始，,从后向前,依次插入到当前链表的第一个结点之前。,算法2-6,#define N m /* m为链表中数据元素的个数,如m=10 */,int AN;,NODE *,creatlink1,( ),NODE *head, *s;,int i;,head = (NODE *)malloc(sizeof(NODE); /*生成头结点*/,head - next = NULL; /* 置空表 */,for(i=N-1; i=0; i-) /* 插入10个数据 */,s = (NODE *)malloc(sizeof(NODE); /*生成新结点*/,s - data = Ai; /*将输入数据放入新结点数据域*/,s - next = head - next; /*新结点与原首结点链接*/,head - next = s; /* 将新结点插入到表头 */,return head; /* 返回单链表头指针 */,算,法,的时间复杂度为：,T(n)=O(n),单链表建立方法二：正向建立单链表（尾插法）。,思想,：依次读入线性表的元素，,从前往后,依次将元素插入到当前链表的最后一个结点之后。,图B 新结点,*,s插入到单链表head的尾上,算法2-7,NODE *,creatlink2,( ),NODE *head, *p, *s;,int num;,head = (NODE *)malloc(sizeof(NODE); /*生成头结点*/,scanf(“%d”, /* 读入第一个结点值*/,p = head; /* 头指针=尾指针 */,while (num!=0) /* 输入为0为输入结束符*/,s = (NODE *)malloc(sizeof(NODE);/*生成新结点*/,s - data = num; /* 新结点上填入输入值 */,p - next = s; /* 新结点*s插入到尾结点*p之后 */,p = s; /* 尾指针p指向新的表尾 */,scanf(“%d”, /* 读入下一个结点值 */,p - next = NULL; /* 将尾结点的指针置空 */,return head; /* 返回单链表头指针 */,算,法,的时间复杂度：,T(n)=O(n),3. 线性链表算法示例,例2-5,求,不带头结点,的头指针为head的单链表中的,结点数目,。,解： int length(NODE *head),NODE *p;,int j;,p = head;,j = 0;,while ( p != NULL ),p = p - next;,j+;,return j;,算,法,的平均时间复杂度：,T(n)=O(n),例2-6,设计算法：将一个,带头结点,的单链表A,分解,为两个带头结点的单链表A和B，使得A表中含有原表中序号为,奇数,的元素，B表中含有原表中序号为,偶数,的元素，且保持其相对顺序。,解：,void,disA,(NODE *A, NODE *B),NODE *r, *p, *q;,B = (NODE *)malloc(sizeof(NODE);,/*建立单链表B的头结点*/,r = B;,p = A-next;,while (p!=NULL) & (p-next!=NULL),q = p-next;,p-next = q-next;,r-next = q;,r = q;,p = p-next;,r-next = NULL;,p-next = NULL;,例2-7,已知两个,不带头结点,的单链表A、B分别表示两个集合，其,元素递增有序,。试设计算法求出A与B的,交集,C。要求C另外开辟存储空间，并同样以,元素值递增,的,带头结点,的单链表形式存储。,解：,void,intersectionset,(NODE *A, NODE *B, NODE *C),NODE *r, *p, *q, *s;,C = (NODE *)malloc(sizeof(NODE);,r = C;,p = A;,q = B;,while (p!=NULL) & (q!=NULL),if (p-data data),p = p-next;,else if (p-data q-data),q = q-next;,else if (p-data = q-data),s = (NODE *)malloc(sizeof(NODE);,s-data = p-data;,r-next = s;,r = s;,p = p-next;,q = q-next;,r-next = NULL;,2.2.4 循环链表和双向链表,1. 循环链表,如果链表最后一个结点的指针域指向头结点，整个链表形成一个环,，这样的链表称为,循环链表,。,这样，从表中任一结点出发均可找到表中其它结点，其逻辑状态图如图2-10。,图2-10 循环单链表,循环链表一般,设表头结点,，这样链表将永不为空，这将,使空表和非空表的逻辑状态及运算统一起来,。,循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是,p或p-next是否为空,，而是它们是否等于头指针。,与单链表比较，,循环链表,有以下,特点,：,(1),在循环单链表中，从表中任何一个结点出发都能访问到其它所有的结点；而单链表一般把头指针作为入口点，从某一结点出发，只能访问到其所有后继结点。,(2),循环单链表的,空表判定条件,是：,head-next=head,。,2双向链表,前面讨论的链式存储结构中,只有,一个,指示直接后继的指针域,，所以从某结点出发,只能顺指针,往后,查找,其它结点。,若要查找结点的直接前趋，则应从头指针出发(或在循环单链表中从p结点出发)一直往后找，直到结点q满足q-next=p，那么q是p的前趋结点,。为克服链表这种单向性的缺点，为有更大的灵活性来操作线性链表，可采用,双向,链表存储结构,。,在每个结点上,增加,另一个,指向线性表中每个元素的前趋结点的指针域prior,，就得到,双向链表,。其结点的结构如图2-11所示。,其中，,prior,是指向前趋结点的指针域；,data,是数据域；,next,是指向后继结点的指针域。,图2-11 双向链表结点结构,图2-12 带头结点的空双向链表,和循环单链表类似，也可将双向链表的头结点和尾结点链接起来组成双向循环链表。,双向链表的几种不同状态如图2-12，图2-13，图2-14和图2-15所示。,图2-13 带头结点的非空双向链表,图2-14 空的双向循环链表,图2-15 非空双向循环链表,在,非空双向循环链表,中，设p是指向链表中任一结点的指针，则有：,p-next-prior = p-prior-next = p,这个等式反映了这种链表的本质，在此链表上进行插入或删除操作是十分方便的。双向链表虽然多花了存储空间，但却换得了操作上的更大灵活性。,双向链表的运算,如,LENGTH,(Head)，,GET,(Head, i)，,LOCATE,(Head, x)等操作，仅涉及一个方向的指针，操作类似单链表。但插入,INSERT,、删除,DELETE,时要同时修改两个方向的指针。,(1) 插入,。在链表中第i个结点前插入元素x。,步骤：,首先,搜索插入位置，找到第i个结点用指p指示，,然后,申请新结点并改变链接,。插入结点时指针变化状况如图2-16所示。,图2-16 在双向链表中插入结点,插入时相关操作序列为：, s-prior = p-prior;, (p-prior)-next = s;, s-next = p;, p-prior = s。,(2) 删除,。在链表中删除第i个结点。,步骤：首先,找到删除位置P，,然后,改变链接，,最后,释放被删结点P。,删除结点时指针变化状况如图2-17所示。,图2-17 在双向链表中删除结点,删除时相关操作序列为：, (p-prior)-next = p-next;, (p-next)-prior = p-prior;,例2-8,设计算法：,判断,带头结点的循环双向链表head按元素值是否,对称,(所谓对称，就是在线性表中a,1,=a,n,，a,2,=a,n-1,，.)。,int,symmetry,(DNODE *head),DNODE *p, *q;,p = head-next; /* p指向首元素 */,q = head-prior; /* q指向尾元素 */,while (p-data = q-data),if (p = q) | (p-next = q) /* 0个或1个元素*/,return 1;,else,p = p-next; /* p向左扫描 */,q = q-prior; /* q向右扫描 */,return 0;,2.3 栈 和 队 列,栈,(stack),和,队列,(queue),是经常遇到的两种数据结构，它们都是,特殊,情况下的,线性表,。前面介绍的线性表的向量及链表存储，进行插入、删除时是比较麻烦的。向量导致数据元素的大量移动，而链表中则要顺链寻找指定位置。如果能够,把插入、删除操作都限制在线性表的,端部,进行,，则运算效率可以大大提高。本节要讨论的就是这种限制存取位置的线性表栈和队列。,2.3.1 栈（,也称,堆栈,）,1栈的定义,栈,（stack）,是,限定只能在表的同一端进行插入和删除操作的线性表,。,其中,允许进行插入和删除操作的一端,称为,栈顶(top),，而表中,固定的一端,称为,栈底(bottom),。,栈中元素个数为零时,称为,空栈,。,由于栈中元素的插入和删除只能在栈顶进行，所以总是后进栈的元素先出来，即栈具有,后进先出,(L,ast,I,n,F,irst,O,ut,，缩写为,LIFO,),的特性，故栈又称为,“,后进先出表,”,(,LIFO,表)。,在日常生活中,，有不少类似栈的例子。例如,食堂中盘子的叠放,，如果限定一次叠放一只，那么每次都是叠放到原来一叠盘子的顶上，这相当于,入栈,操作,；而当取用一只盘子时，也是从这一叠盘子的顶上取用，这相当于,出栈,操作,。,栈的五种,基本运算,：,(1) Inistack(S),。,初始化,栈S为空栈。,(2) Empty(S),。,判,定S是否为,空,栈。若S是空栈则返回值为真(Ture)，否则返回值为假(False)。,(3) Push(S，x),。,进栈,操作。在栈S的栈顶插入数据元素x。,(4) Pop(S),。,出栈,操作。若栈S不是空栈，则删除栈顶元素。,(5) Gettop(S),。,取栈,顶元素。它只读取栈顶元素，不改变栈中的内容。,图2-18 三个元素可能的出栈序列,例2-9,有三个元素的进栈序列是,1，2，3,，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列如图2-18所示(假设以,I,和,O,表示进栈和出栈操作)。,2栈的表示和实现,因为栈是线性表的一种特例，所以线性表的存储结构对它都适用。一般称,采用顺序存储结构的栈,为,顺序栈,；,采用链式存储结构的栈,为,链栈,。,1) 栈的顺序存储结构,顺序栈,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设,指针top,指示栈顶元素的当前位置。,空栈的栈顶指针值为-1。设用数组,StackMAXSIZE,表示栈，则对非空栈，Stack0为最早进入栈的元素，,Stacktop,为最迟进入栈的元素，即,栈顶元素,。,当,top= MAXSIZE-1,时意为,栈满,，此时若有元素入栈则将产生“数组越界”的错误，称为栈的“,上溢,”,(overflow),；,反之，,top= -1,意为,栈空,，若此时再作退栈操作，则发生“,下溢,”,(underflow),。,图2-19展示了顺序栈中数据元素和栈顶指针之间的对应关系，设,MAXSIZE =m,。,图2-19 栈顶指针和栈中元素之间的关系,顺序栈的,C语言描述,如下：,typedef int datatype；,#define MAXSIZE m,#define maxsiz