资源描述
单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数 据 结 构,计算机系,第一章 绪 论,1.1 什么是数据结构,1.2 基本概念和术语,1.3 抽象数据类型的表示与实现,1.4 算法和算法分,1.4.1 算法,1.4.2 算法设计的要求,1.4.3 算法效率的度量,1.4.4 算法的存储空间的需求,第一章 绪 论,计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：,信息的表示,信息的处理,而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题,。,1.1什么是数据结构,众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。,例1、电话号码查询系统,设有一个电话号码薄，它记录了,N,个人的名字和其相应的电话号码，假定按如下形式安排：,(,a,1,，b,1,)(a,2,，b,2,)(a,n,，,b,n,),其中,a,i,，b,i,(i=1，2n),分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。,算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。,数据的结构，直接影响算法的选择和效率。,上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。,假定名字和其电话号码逻辑上已安排成,N,元向量的形式，它的每个元素是一个数对(,a,i,，b,i,)， 1in,数据结构还要提供每种结构类型所定义的各种运算的算法。,例2、图书馆的书目检索系统自动化问题,例3、教师资料档案管理系统,例4、多叉路口交通灯的管理问题,P3,通过以上几例可以直接地认为：数据结构,就是研究数据的逻辑结构和物理结构以及它们,之间相互关系，并对这种结构定义相应的运算，,而且确保经过这些运算后所得到的新结构仍然,是原来的结构类型。,1.2 基本概念和术语,数据(,Data,):,是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。,数据元素(,Data Element,):,是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。,一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。,数据对象(,Data Object),：,是性质相同的数据元素的集合。是数据的一个子集。,数据结构(,Data Structure),：,是相互之间存在一种或多种特定关系的数据元素的集合。,数据结构主要指逻辑结构和物理结构,数据之间的相互关系称为逻辑结构。通常分为四类基本结构：,一、,集合,结构中的数据元素除了同属于一种类型外，别无其它关系。,二、,线性结构,结构中的数据元素之间存在一对一的关系。,三、,树型结构,结构中的数据元素之间存在一对多的关系。,四、,图状结构或网状结构,结构中的数据元素之间存在多对多的关系。,数据结构的形式定义为：数据结构是一个二元组：,Data-Structure=(D，S),其中：,D,是数据元素的有限集，,S,是,D,上关系的有限集。,例 复数的数据结构定义如下：,Complex=(C，R),其中：,C,是含两个实数的集合,C1，C2，,分别表示复数的实部和虚部。,R=P，P,是定义在集合上的一种关系,C1，C2。,数据结构在计算机中的表示称为数据的,物理结构,，又称为,存储结构,。,数据对象可以是有限的，也可以是无限的。,数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,抽象数据类型：一个数学模型以及定义在该模型上的一组操作。,抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。,用三元组描述如下：,（，）,数据结构在计算机中有两种不同的表示方法：,顺序表示和非顺序表示,由此得出两种不同的存储结构：,顺序存储结构和链式存储结构,顺序存储结构:,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系,。,链式存储结构：,在每一个数据元素中增加一个存放地址的指针（ ），用此指针来表示数据元素之间的逻辑关系。,数据类型,：在一种程序设计语言中，变量所具有的数据种类。,例1、 在,FORTRAN,语言中，变量的数据类型有整型、实型、和复数型,例2、在,C,语言中,数据类型：基本类型和构造类型,基本类型：整型、浮点型、字符型,构造类型：数组、结构、联合、指针、枚举型、自定义,数据对象,：某种数据类型元素的集合。,例3、整数的数据对象是-3，-2，-1，0，1，2，3，,英文字符类型的数据对象是,A，B，C，D，E，F，,1.3 抽象数据类型的表示和实现,P11,1.4 算法和算法分析,算法,：是对特定问题求解步骤的一种描述,算法是指令的有限序列，其中每一条指令表示一个或多个操作。,算法具有以下五个特性：,（1）,有穷性,一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。,（2）,确定性,算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。,（3）,可行性,一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。,4）,输入,一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。,5）,输出,一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,1.4.2 算法设计的要求,评价一个好的算法有以下几个标准:,(1),正确性(,Correctness ),算法应满足具体问题的需求。,(2),可读性(,Readability),算法应该好读。以有利于阅读者对程序的理解。,(3),健状性(,Robustness),算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。,(,4),效率与存储量需求,效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。,1.4.3,算法效率的度量,对一个算法要作出全面的分析可分成两用人才个阶段进行，即,事先分析,和,事后测试,事先分析,求出该算法的一个时间界限函数,事后测试,收集此算法的执行时间和实际占用空间的统计资料。,定义：如果存在两个正常数,c,和,n,0,，,对于所有的,nn,0,，,有,f(n) cg(n) ,则记作,f(n)=O(g(n),一般情况下，算法中基本操作重复执行的次数是问题规模,n,的某个函数，算法的时间量度记作,T(n)=O(f(n),称作算法的渐近时间复杂度。,例、,for(I=1，I=n;+I),for(j=1;j=n;+j),cIj=0;,for(k=1;k=n;+k),cIj+=aIk*bkj;,由于是一个三重循环，每个循环从1到,n，,则总次数为:,nnn=n,3,时间复杂度为,T(n)=O(n,3,),频度,：是指该语句重复执行的次数,例 +,x;s=0;,将,x,自增看成是基本操作，则语句频度为，即时间复杂度为(1),如果将,s=0,也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。,例、,for(I=1;I=n;+I),+x;s+=x;,语句频度为：2,n,其时间复杂度为：,O(n),即时间复杂度为线性阶。,例、,for(I=1;I=n;+I),for(j=1;j=n;+j),+x;s+=x;,语句频度为：2,n,2,其时间复杂度为：,O(n,2,),即时间复杂度为平方阶。,定理：若,A(n)=a,m,n,m,+a,m-1,n,m-1,+a,1,n+a,0,是一个,m,次多项式，则,A(n)=O(n,m,),证略。,例,for(i=2;i=n;+I),for(j=2;j=i-1;+j),+x;ai，j=x;,语句频度为：,1+2+3+,n-2=(1+n-2) (n-2)/2,=(n-1)(n-2)/2,=n,2,-3n+2,时间复杂度为,O(n,2,),即此算法的时间复杂度为平方阶.,一个算法时间为,O(1),的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为,O(n,2,),的算法则由一个二次多项式来限界。,以下六种计算算法时间的多项式是最常用的。其关系为：,O(1)O(,logn,)O(n)O(,nlogn,),O(n,2,)O(n,3,),指数时间的关系为：,O(2,n,)O(n!)1 -I),change=false;,for(j=0;jaj+1) ,aj aj+1;,change=TURE,最好情况：0次,最坏情况：1+2+3+,n-1,=n(n-1)/2,平均时间复杂度为:,O(n,2,),1.4.4,算法的存储空间需求,空间复杂度:算法所需存储空间的度量，记作:,S(n)=O(f(n),其中,n,为问题的规模(或大小),第二章 线性表,2.1 线性表的类型定义,2.2 线性表的顺序表示和实现,2.3 线性表的链式表示和实现,2.3.1 线性链表,2.3.2 循环链表,2.3.3 双向链表,2.4 一元多项式的表示及相加,2.1 线性表的逻辑结构,线性表(,Linear List) ：,由,n(n),个数据元素(结点),a,1,，a,2,， a,n,组成的有限序列。其中数据元素的个数,n,定义为表的长度。当,n=0,时称为空表，常常将非空的线性表(,n0),记作：,(,a,1,，a,2,，a,n,),这里的数据元素,a,i,(1in),只是一个抽象的符号，其具体含义在不同的情况下可以不同。,例1、26个英文字母组成的字母表,（,A，B，C、Z）,例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。,（,6，17，28，50，92，188,）,例3、学生健康情况登记表如下：,姓 名,学 号,性 别,年龄,健康情况,王小林,790631,男,18,健康,陈 红,790632,女,20,一般,刘建平,790633,男,21,健康,张立立,790634,男,17,神经衰弱,.,.,.,.,.,例4、一副扑克的点数,（2，3，4，,J，Q，K，A）,从以上例子可看出线性表的逻辑特征是：,在非空的线性表，有且仅有一个开始结点,a,1,，,它没有直接前趋，而仅有一个直接后继,a,2,；,有且仅有一个终端结点,a,n,，,它没有直接后继，而仅有一个直接前趋,a,n-1,；,其余的内部结点,a,i,(2in-1),都有且仅有一个直接前趋,a,i-1,和一个直接后继,a,i+1,。,线性表是一种典型的线性结构。,数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,抽象数据类型的定义为：,P,19,算法2.1,例,2-1 利用两个线性表,LA,和,LB,分别表示两个集合,A,和,B，,现要求一个新的集合,A=AB。,void union(List &La，List Lb) ,La-,len,=,listlength,(La);,Lb-,len,=,listlength,(Lb);,for(I=1;I=lb-,len,;I+) ,getelem,(lb，I，e);,if(!,locateelem,(la，e，equal),listinsert,(la，+la-en，e),算法2.2,例2-2 巳知线性表,LA,和线性表,LB,中的数据元素按值非递减有序排列，现要求将,LA,和,LB,归并为一个新的线性表,LC，,且,LC,中的元素仍按值非递减有序排列。,此问题的算法如下：,void,mergelist,(list la，list lb，list &,lc,),initlist,(,lc,);,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;,else,listinsert,(,lc,，+k，,bj,);+j;,while(I=la-,len,),getelem,(la，I+，,ai,);,listinsert,(,lc,，+k，,ai,);,while(j=,ListSize,),printf,(“overflow”);,exit(overflow);,for(j=l.length-1;j=I-1;j-),l.dataj+1=l.dataj;,l.dataI-1=x;,l.length+;,现在分析算法的复杂度。,这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。,当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度,O（1）；,当=1时，结点后移语句将循环执行,n,次，需移动表中所有结点，这是最坏情况，,其,时间复杂度为,O（n）。,由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度,在长度为,n,的线性表中第,i,个位置上插入一个结点，令,E,is,(n),表示移动结点的期望值（即移动的平均次数），则在第,i,个位置上插入一个结点的移动次数为,n-I+1。,故,E,is,(n)= p,i,(n-I+1),不失,一般性，假设在表中任何位置(1,in+1),上插入结点的机会是均等的，则,p,1,=p,2,=p,3,=p,n+1,=1/(n+1),因此，在等概率插入的情况下，,E,is,(n)= (n-I+1)/(n+1)=n/2,也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长,n,较大时，算法的效率相当低。虽然,E,is,(n),中,n,的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为,O(n)。,2、,删除,线性表的删除运算是指将表的第,i(1in),结点删除，使长度为,n,的线性表： (,a,1,，a,i-1,，,a,i,，a,i+1,，a,n,),变成长度为,n-1,的线性表,(,a,1,，a,i-1,，a,i+1,，a,n,),Void,deleteList,(,Sqlist,*L，,int,I),int,j;,if(Il.length),printf,(“Position error”);,return ERROR,for(j=i;jdata=,ch,;,pnext=head;,head=p;,ch,=,getchar,( );,return (head);,listlink createlist,(,int,n),int,data;,linklist,head;,listnode,*p,head=null;,for(i=n;i0;-i),p=(,listnode,*),malloc,(,sizeof,(,listnode,);,scanf,(%d，,pnext=head;,head=p;,return(head);,2、,尾插法建表,头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针,r，,使其始终指向当前链表的尾结点。例：,linklist,creater,( ),char,ch,;,linklist,head;,listnode,*p，*r; /(， *head;),head=NULL;r=NULL;,while(,ch,=,getchar,( )!=n),p=(,listnode,*),malloc,(,sizeof,(,listnode,);,pdata=,ch,;,if(head=NULL),head=p;,else,rnext=p;,r=p;,if (r!=NULL),rnext=NULL;,return(head);,说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，,而其余结点的位置是在其前趋结点的指针域中。算法中的第一个,if,语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个,if,语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表,head,是空表，尾指针,r,亦为空，结点*,r,不存在；否则链表,head,非空，最后一个尾结点*,r,是终端结点，应将其指针域置空。,如果我们在链表的开始结点之前附加一个结点，并称它为,头结点,，那么会带来以下两个优点：,a、,由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就,和在表的其它位置上的操作一致，无需进行特殊处理；,b、,无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。,其算法如下：,linklist,createlistr1( ),char,ch,;,linklist,head=(,linklist,),malloc,(,sizeof,(,listnode,);,listnode,*p，*r,r=head;,while(,ch,=,getchar,( )!=n,p=(,listnode,*),malloc,(,sizeof,(,listnode,);,pdata=,ch,;,pnext=p;,r=p;,rnext=NULL;,return(head);,上述算法里动态申请新结点空间时未加错误处理，可作下列处理：,p=(,listnode,*),malloc,(,sizeof,(,listnode,),if(p=NULL),error(No space for node can be obtained);,return ERROR;,以上算法的时间复杂度均为,O(n)。,二、查找运算,1、按序号查找,在链表中，即使知道被访问结点的序号,i，,也不能象顺序表中那样直接按序号,i,访问结点，而只能从链表的头指针出发，顺链域,next,逐个结点往下搜索，直到搜索到第,i,个结点为止。因此，链表不是随机存取结构。,设单链表的长度为,n，,要查找表中第,i,个结点，仅当1,in,时，,i,的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下：,Listnode,*,getnode,(,linklist,head ，,int,i),int,j;,listnode,* p;,p=head;j=0;,while(pnext & jnext;,j+;,if (i=j),return p;,else,return NULL;,2、,按值查找,按值查找是在链表中，查找是否有结点值等于给定值,key,的结点，若有的话，则返回首次找到的其值为,key,的结点的存储位置；否则返回,NULL。,查找过程从开始结点出发，顺着链表逐个将结点的值和给定值,key,作比较。其算法如下：,Listnode,*,locatenode,(,linklist,head，,int,key),listnode,* p=headnext;,while( p & pdata!=key),p=pnext;,return p;,该算法的执行时间亦与输入实例中的的取值,key,有关，其平均时间复杂度的分析类似于按序号查找，也为,O(n)。,三、插入运算,插入运算是将值为,x,的新结点插入到表的第,i,个结点的位置上，即插入到,a,i,-1,与,a,i,之间。因此，我们必须首先找到,a,i,-1,的存储位置,p，,然后生成一个数据域为,x,的新结点*,p，,并令结点*,p,的指针域指向新结点，新结点的指针域指向结点,a,i,。,从而实现三个结点,a,i,-1,，x,和,a,i,之间的逻辑关系的变化，插入过程如：,具体算法如下：,void,insertnode,(,linklist,head，,datetype,x，,int,i),listnode,* p，*q;,p=,getnode,(head，i-1);,if(p=NULL),error(position error);,q=(,listnode,*),malloc,(,sizeof,(,listnode,);,qdata=x;,qnext=pnext;,pnext=q;,设链表的,长度为,n，,合法的插入位置是1,in+1。,注意当,i=1,时，,getnode,找到的是头结点，当,i=n+1,时，,getnode,找到的是结点,a,n,。,因此，用,i-1,做实参调用,getnode,时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作,getnode,上，故时间复杂度亦为,O(n)。,四、删除运算,删除运算是将表的第,i,个结点删去。因为在单链表中结点,a,i,的存储地址是在其直接前趋结点,a a,i-1,的指针域,next,中，所以我们必须首先找到,a,i-1,的存储位置,p。,然后令,pnext,指向,a,i,的直接后继结点，即把,a,i,从链上摘下。最后释放结点,a,i,的空间，将其归还给“存储池”。此过程为：,具体算法如下,：,void,deletelist,(,linklist,head，,int,i),listnode,* p， *r;,p=,getnode,(head，i-1);,if(p= =NULL | pnext= =NULL),return ERROR;,r=pnext;,pnext=rnext;,free( r ) ;,设,单链表的,长度为,n，,则删去第,i,个结点仅当1,in,时是合法的。注意，当,i=n+1,时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*,p,存在并不意味着被删结点就一定存在，仅当*,p,存在（即,p!=NULL）,且*,p,不是终端结点,（即,pnext!=NULL）,时，才能确定被删结点存在。,显然此算法的时间复杂度也是,O(n)。,从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。,2.3.2 循环链表,循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活,。,单循环链表：,在单链表中，将终端结点的指针域,NULL,改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。,为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：,a1,a,n,.,head, 非空表, 空表,在用头,指针表示的单链表中，找开始结点,a,1,的,时间是,O(1)，,然而要找到终端结点,a,n,，,则需从头指针开始遍历整个链表，其时间是,O(n),在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针,rear,来表示单循环链表，则查找开始结点,a,1,和终端结点,a,n,都很方便，它们的存储位置分别是(,rearnext) next,和,rear，,显然，查找时间都是,O(1)。,因此，实际中多采用尾指针表示单循环链表。,由于循环链表中没有,NULL,指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断,p,或,pnext,是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。,例、在链表上实现将两个线性表(,a,1,，a,2,，a,3,，a,n,),和(,b,1,，b,2,，b3，,b,n,),链接成一个线性表的运算。,linklist,connect(,linklist heada,，,linklist headb,),linklist,p=,heada,next;,heada,next=(,headb,next)next,free(,headb,next);,headb,next=p;,return(,headb,);,2.3.3双链表,双向链表(,Double linked list):,在单链表的每个结点里再增加一个指向其直接前趋的指针域,prior。,这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：,typedef struct dlistnode,datatype,data;,struc dlistnode,*prior，*next;,dlistnode,;,typedef dlistnode,*,dlinklist,;,dlinklist,head;,和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。,设指针,p,指向某一结点，则双向链表结构的对称性可用下式描述：,(,pprior)next=p=(pnext)prior,即结点*,p,的存储位置既存放在其前趋结点*(,pprior),的直接后继指针域中，也存放 在它的后继结点*(,pnext),的直接前趋指针域中。,双向链表的前插,操作算法如下：,void,dinsertbefor,(,dlistnode,*p，,datatype,x),dlistnode,*q=,malloc,(,sizeof,(,dlistnode,);,qdata=x;,qprior=pprior;,qnext=p;,ppriornext=q;,pprior=q;,void,ddeletenode,(,dlistnode,*p),ppriornext=pnext;,pnextprior=pprior;,free(p);,注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为,O(1)。,第三章 栈和队列,3.1 栈,3.1.1 抽象数据类型栈的定义,3.1.2 栈的表示和实现,3.2 栈的应用举例,3.2.1 数制转换,3.2.2 括号匹配的检验,3.2.4 行编辑程序,3.2.5 迷宫求解,3.2.5 表达式求值,3.1.1 栈,3.1.1 栈的定义及基本运算,栈(,Stack),是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(,Top)，,另一端为栈底(,Bottom)。,当表中没有元素时称为空栈。,假设栈,S=(a,1,，a,2,，a,3,，a,n,)，,则,a,1,称为栈底元素，,a,n,为栈顶元素。栈中元素按,a,1,，a,2,，a,3,，a,n,的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（,LIFO）。,3.1.2,顺序栈,由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。,栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量,top,例、一叠书或一叠盘子。,栈的抽象数据类型的定义如下：,P,44,a,n,a,n-1,a,2,a,1,栈顶,栈,底,top,7,6 5 4 3 2 1,-1,来指示当前栈顶的位置，通常称,top,为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为,top,即可。顺序栈的类型定义如下：,#,define,StackSize,100,typedef,char,datatype,;,typedef struct,datatype,data,stacksize,;,int,top;,seqstack,;,设,S,是,SeqStack,类型的指针变量。若栈底位置在向量的低端，即,sdata0,是栈底元素，那么栈顶指针,stop,是正向增加的，即进栈时需将,s,top,加1，退栈时需将,stop,减1。因此，,stoptop =,stacksize,-1,表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。,3、判断栈满,int stackfull,(,seqstack,*s),return(stop=,stacksize,-1);,4、,进栈,void push(,seqstack,*s，,datatype,x),if (,stackfull,(s),error(“stack overflow”);,sdata+stop=x;,1、置空栈,void,initstack,(,seqstack,*s),stop=-1;,2、,判断栈空,int stackempty,(,seqstack,*s),return(stop=-1);,5、退栈,datatype,pop(,seqstack,*s),if(,stackempty,(s),error(“stack underflow”);,x=sdatatop;,stop-;,return(x),/return(sdatastop-);,6、,取栈顶元素,Datatype stacktop,(,seqstack,*s),if(,stackempty,(s),error(“stack is,enpty,”);,return sdatastop;,3.1.3,链栈,栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。,链栈的类型说明如下：,typedef,struct,stacknode,datatype,data,struct stacknode,*next,stacknode,;,Void,initstack,(,seqstack,*p),ptop=null;,int stackempty,(,linkstack,*p),return ptop=null;,Void push(,linkstack,*p,datatype,x),stacknode,*q q=(,stacknode,*),malloc,(,sizeof,(,stacknode,);,qdata=x;,qnext=ptop;,ptop=p;,Datatype,pop(,linkstack,*p),datatype,x;,stacknode,*q=ptop;,if(,stackempty,(p),error(“stack underflow.”);,x=qdata;,ptop=qnext;,free(q);,return x;,datatype,stack top(,linkstack,*p),if(,stackempty,(p),error(“stack is empty.”);,return ptopdata;,3.2 栈的应用举例,由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。,3.2.1 数制转换,十进制,N,和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:,N=(n div d)*d+n mod d,(,其中:,div,为整除运算,mod,为求余运算),例如 (,1348),10,=(2504),8,，,其运算过程如下：,n n div 8 n mod 8,1348 168 4,168 21 0,21 2 5,2 0 2,void conversion( ) ,initstack,(s);,scanf,(“%”,n);,while(n),push(s,n%8);,n=n/8;,while(!,Stackempty,(s),pop(s,e);,printf,(“%d”,e);,3.2.2 括号匹配的检验,假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：,（）（） （）,3.2.3 行编辑程序,在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。,行编辑程序算法如下:,void,lineedit,( ),initstack,(s);,ch,=,gether,( );,while(,ch,!=,eof,),while(,ch,!=,eof,&,ch,!=n),switch(,ch,),case # : pop(s,c);,case :,clearstack,(s);,default : push(s,ch,);,ch,=,getchar,( );,clearstack,(s);,if(,ch,!=,eof,),ch,=,gethar,( );,destroystack,(s);,3.2.4 迷宫求解,入口,出口,3.4 队列,3.4.1 抽象数据类型队列的定义,队列(,Queue),也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(,front)，,允许插入的一端称为队尾(,rear)。,例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(,First In First Out),的线性表，简称,FIFO,表。,当队列中没有元素时称为空队列。在空队列中依次加入元素,a,1,a,2,a,n,之后，,a,1,是队头元素，,a,n,是队尾元素。显然退出队列的次序也只能是,a,1,a,2,a,n,，,也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：,a,1,a,2,a,n,出队,入队,队头,队尾,队列的抽象数据定义见书,59,3.4.2 循环队列队列的顺序表示和实现,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队,列,中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。, 0 1 2 3,Front,rear,a,b,c,Front
展开阅读全文