软件开发技术基础2教学课件全书电子讲义.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,软件开发技术基础,21,世纪大学计算机基础规划教材,第一章 工程软件的基础元素,1.1,工程软件概述,科学计算、信息处理、过程控制是计算机的三大应用领域。计算机最早应用于科学计算，,20,世纪,70,年代，计算机的应用范围扩大到数据信息处理，数据信息处理是当今计算机应用的重要领域。由于计算机具有逻辑运算的能力，从,20,世纪,60,年代起计算机被广泛应用于工业生产过程的实时监测和控制，这是工程软件大量出现的开始。伴随着网络技术的飞速发展，计算机应用的网络化已引起了生产方式的深刻变革。,工程软件所面向的应用领域主要有如下 几个方面：,1,、工程辅助系统,2,、工程事务处理,3,、现代工程通信及信息交流,工程软件的三个基本要素是数据、数据结构和算法，,1.2,数据结构概述,1.2.1,数据结构及数据运算的概念,数据结构是计算机科学的重要基础，近年来已发展成为一个专门学科。根据各种实际问题的需求，人们提出了许多组织数据的方法，从而构造了不同的数据结构，而且随着处理实际问题的需要，新的更加复杂的数据结构还在不断地被提出。,数据,是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。,数据元素,数据元素是数据的基本单位，是数据集合中的个体，是对事物属性中基本方面的测量。,数据项,具有独立意义的最小数据单位，是对数据元素属性的描述。,数据类型,是指某种程序设计语言所允许使用的变量种类。,有关数据结构的概念：,数据对象,是性质相同的数据元素的集合，是数据的一个子集。,数据结构,是带有结构的元素的集合，它是指数据之间的相互关系，即数据的组织形式。,数据的逻辑结构是数据间关系的描述，它只抽象地反映数据元素间的逻辑关系，而不涉及其在计算机中的存在方式。,数据的存储结构是逻辑结构在计算机存储器中的实际表示，它不仅要存储数据元素的内容，还要把数据元素间的关联体现出来，它是逻辑结构用计算机所能理解的方式的具体实现。,算法是为解决特定问题而采取的有限操作步骤，是对解题方案的准确而完整的描述。,在计算机科学中，数据结构与算法是密不可分，缺一不可的。,程序,=,数据结构,+,算法,强调了数据结构和算法之间的天然联系。,有关算法的概念：,有关运算的概念：,数据结构往往是与施加于其上的运算密切相关的。数据的运算是定义在数据的逻辑结构上的，运算的具体实现要在存储结构上进行。,最常用的运算有：,1,、插入在数据结构中增加新的结点,2,、删除把指定的结点从数据结构中去除,3,、更新改变指定结点的值或改变指定的某些结点之间的关系,4,、查找在数据结构中查找满足一定条件的结点,5,、排序对数据结构中各个结点按指定数据项的值，以升序或降序等重新排列,复杂的运算过程可以是以上各种基本操作的组合。,1.2.2,数据结构的分类,依据数据元素间关系的特点，数据结构可分为两大类：线性结构和非线性结构。,如果一个非空的数据结构满足下列两个条件：,1,、有且有一个根结点；,2,、每一个结点最多有一个前驱，最多有一个后继。,则称该数据结构为线性结构。,根据对线性结构中数据元素的存取方式的不同，又可将其分为直接存取结构、顺序存取结构和广义索引结构。,对于直接存取结构，可以直接存取某一特定数据元素而不需先访问其前驱。,对于顺序存取结构，只能从数据序列中的第一个数据元素开始，按顺序依次查找，直到指定的元素。,广义索引是通过关键码进行索引的。通过设定数据记录中某一数据项或某一组全数据项为关键码，通过关键码来索引记录。,在非线性结构中各个数据元素不必保持在一个线性序列中，每个数据元素可能多个其它数据元素发生关联。在非线性结构中。各数据元素之间的前驱与后继的关系要比线性结构复杂，因此，对非线性结构的存储与处理比线性结构要复杂得多。,典型的非线性结构（树结构）实例。,典型的非线性结构（图结构）实例。,1.2.3,数据结构的表示,1,、数据的逻辑结构,对数据间关系的描述即是数据的逻辑结构，形式上可以用一个二元组来表示，即：,B=(K,，,R),其中,K,为结点的有穷集合，即,K,是由有限个结点所构成的集合；,R,是,K,上的的有穷集合，即,R,是由有限关系所构成的集合，其中的每个关系都是从,K,到,K,的关系。,2,、数据的存储结构,有,4,种基本的物理存储映像方法：顺序的方法、链接的方法、索引的方法和散列的方法。,一个数据结构的存储映像都是以上,4,种基本映像之一或是它们的组合。一个逻辑结构可以有不同的映像方法。,1.2.4,数据类型及数据抽象,数据类型则最早出现在高级算法语言中，用以刻画数据操作对象的特性。,数据类型可分为简单型和结构类型两种。简单类型中的每个数据都是无法再分割的整体。结构类型由简单类型按照一定的规则构造而成，其数据结构就是相应元素的集合和元素之间所含关系的集合，并且结构类型中可以包含结构类型。,所谓数据抽象就是提取反映问题本质的数据结构。抽象数据类型的概念其实质和高级算法语言中的数据类型概念相同。,抽象数据类型,(Abstract Data Type,ADT),是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示及实现无关。,一个线性表的抽象数据类型可描述如下：,ADT Linear_list,其中,数据元素：所有,a,i,属于同一数据对象，,i=1,2,n,；,逻辑结构：所有数据元素,a,i,(i=1,2,，,n-1),存在次序关系,，,a,1,无前驱，,a,n,无后继；,操作：设,L,为,Linear_list,类型的线性表,Initial(L),为线性表初始化操作；,Length(L),为求线性表表长操作；,Get(L,i),为取线性表的第,i,个元素；,Insert(L,i,b),在线性表,L,的第,i,个位置插入元素,b,；,Delete(L,，,i),删除线性表的第,i,个元素。,1.3,算法概述,1.3.1,算法的概念,算法,(Algorithm),是为解决一个问题采取的方法和步骤，也就是说，算法是为实现某种计算过程而规定的基本动作的执行序列。算法分两大类：数值计算方法和非数值计算方法。,算法有如下的特点：,1.,算法有有限的操作步骤，即算法的有穷性（,finiteness,）,2.,算法的每一步骤都应为确定的，即算法的确定性,(definiteness),3.,执行算法时可从外界输入信息，即算法需要足够的输入信息,(information),4.,算法的目的是为了求解，因此算法要有输出，即算法的输出,(output),5.,算法的每一步都应有效地执行，即算法的有效性,(effectiveness),1.3.2,算法的描述,算法的描述方法很多，根据描述算法语言的不同，可将算法分为以下常用的四种：,1,、框图描述法。,2,、非形式描述法。,3,、类高级算法语言描述法。,4,、高级算法语言描述法。,1.3.3,算法分析,判断一个算法的优劣主要有以下几个标准：,1,、正确性,2,、可使用性,3,、健壮性,4,、效率,时间代价是常用的评价指标，往往用时间复杂度来衡量。当一个算法转换成程序并在计算机上执行时，其运行所需要的时间取总是取决于下列因素：,1,、硬件的速度,2,、所选用的程序设计语言,3,、编译程序所生成目标代码的质量,4,、问题的规模,时间复杂度（,Time complexity,）又称计算复杂度，它是一个算法运行时间的相对度量。一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。,定义：如果存在两个正常数,c,和,n,0,，使得对所有的,n,，,n,n,0,，有,f(n),cg(n),，则记为,T(n)=O(g(n),。,使用,O,记号表示的算法的时间复杂度称为算法的渐进时间复杂度,(Asymptotic Complexity),。通常用,O(1),表示常数计算时间。常见的渐进时间复杂度有：,O,（,1,）,O,（,log,2,n,）,O(n),O(n log,2,n),O(n,2,),O(n,3,),O(2,n,),一个程序的空间复杂度（,Space Complexity,）是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分：,1.,固定部分,2.,可变部分,类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义算法空间复杂度为,S(n)=O(g(n),表示随问题规模,n,的增大，算法运行所需存储量的增长率与,g(n),的增长率相同。,工程软件技术基础,第二章,常用数据结构,及其在工程中的应用,本章主要内容,主要介绍：,基本数据结构,数据结构的应用,各种数据结构的插入与删除运算,课时：5-6学时对于数据结构的另外两种基本运算即查找与排序，将放在第三章中讨论,数据结构的内容,线性数据结构,非线性数据结构,线性表,顺序表,顺序队列,队列,链栈,链队列,串,广义表,数组,树与二叉树,图,线性链表,图2-1 常用数据结构的组成,栈,顺序栈,单链表,双向链表,2.1,线性数据结构,2.1.1,顺序表,2.1.2,线性链表,2.1.3,索引存储,2.1.4,栈,2.1.5,队列,2.1.6,串,线性表的基本概念,线性表（,Linear List):,由,n(n,0,),个数据元素,a1,a2,.an,组成的一个有限序列，线性表中的每个数据元素，除了第一个和最后一个外，有且仅有一个前件，也有且仅有一个后件。,ai,也称为线性表中的一个,结点。,n,个元素的线性表:,（,a,1,a,2,a,i,a,i+1,a,n,）,第一个元素,(没有前驱),第,i,个元素,(有唯一的前驱,和唯一的后继),最后一个元素,(没有后继),线性表的特征,非空线性表的结构特征,：,有且只有一个根结点,a,1,，,它无前件；,有且只有一个终结点,a,n,，,它无后件；,除根结点和终结点外，其它所有结点有且只有一个前件和一个后件。,线性表中结点的个数,n,称为,线性表的长度,。当,n,0,时，称为空表。,线性表的基本操作,InitList(,构造一个空的线性表,L。,DestroyList(,初始条件:线性表,L已经存在。,操作结果:销毁线性表,L。,ListInsert(,ListDelete(,线性表的扩展操作,Length（L）,求表长。,Get（L，i）,取表中元素。,Prior（L，i）,取元素,a,i,的直接前趋。,Succ（L，i）,取元素,a,i,的直接后继。,Locate（L，x）,定位函数。,2.1.1,顺序表,线性表的顺序存储结构:,用一组,连续,的存储单元依次存储线性表中的各数据元素。(最简单，最常用),将顺序存储结构的线性表称为,顺序表,。,顺序表的存储（一）,第,i,个数据元素的存储地址：,假设线性表中的每个数据元素需占用,k,个存储单元，且第一个数据元素的存储地址为,ADR,（,a1,），,则对于顺序表，第,i,个数据元素的存储地址为：,ADR,（,ai,）,ADR,（,a1,）,十（,i,1,）*,k,顺序表中每一个数据元素在计算机内的存储地址与第一个数据元素的存储地址之差与数据元素的序号成正比。,在顺序表中存取一个数据元素，只需要通过元素序号计算出它的存储地址。,顺序表的存储（二）,存储地址,内存状态,元素符号,b,a1,1,b+k,a2,2,。,。,。,b+(i-1)*k,ai,i,。,。,。,b+(n-1)*k,an,n,b-,为,a1,数据元素的存储地址,k-,为,每个数据元素所需的存储空间,typedef struct,ElemType *elem;,int length;,int listsize;,SqList;,内存分配示意图：,顺序表的运算,初始化,插入新元素,删除数据元素,顺序表的初始化算法实现,void InitList_Sq(SqList&L),L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);,if(!L.elem)return(OVERFLOW);,L.length=0;,L.listsize=LIST_INIT_SIZE;,return OK;,顺序表插入分析,插入算法,：,为在第,i,个元素之前插入新元素，则从最后一个 （即第,n,个）元素开始，直到第,i,个元素共,ni1,个元素依次向后移动一个位置，最后将新元素放到第,i,位置。,ListInsert(&L,i,e),初始条件:线性表,L,已经存在，1=,i=ListLength(L)+1,操作结果:在,L,的第,i,个位置之前插入新的数据元素,b,L,的长度加1。,插入前（长度为,n）:,（a,1,a,2,a,i-1,a,i,a,n,）,插入后（长度为,n+1）:,（a,1,a,2,a,i-1,b,a,i,a,n,）,void ListInsert_Sq(SqList&L,int i,ElemType d),int j;,if(L.length=L.listsize)return;/表已满,if(iL.length)i=L.ength+1;/,按在表尾插入处理,for(j=L.length;j=i;j-)*(L.elem+j)=*(L.elem+j-1);,*(L.elem+i-1)=d;,L.length+;,顺序表的插入算法实现,顺序表插入算法的时间复杂度,用,Pj,表示在第,j,个元素之前插入元素的概率，则在长度为,n,的线性表中插入一个元素（也包括在线性表的末尾插入一个新元素）时，所需移动元素的平均次数（即期望值,）,Eis,如果在线性表的任何位置插入的概率被认为是相等的，即,Pj,则有,由此可见，对顺序存储的线性表作一次插入运算，平均起来大约需移动表中一半的元素,顺序表的删除,ListDelete(&L,i,&e),初始条件:线性表,L,已经存在，1=,ilength)return;/i,值不合法,p=(L-elem+i-1);/p,为被删除元素的位置,*,e=*p;/,被删除元素的值赋给,e,for(j=i;jlength;j+),*(L-elem+j-1)=*(L-elem+j);,L-length-;,顺序表的删除算法实现,顺序表删除算法的时间复杂度,若用,q,j,表示删除线性表中第,j,个元素的概率，则在长度为,n,的线性表中删除一个元素时需要移动的平均次数（期望值）为,若删除线性表中每一个元素的概率是相等的，即,则有:,由此可见，对顺序存储的线性表作一次删除，平均诓秦玉臣需要移动表中一半的元素。,顺序表小结,线性表的顺序存储结构有以下特点,:,结构比较简单,便于随机访问表中的任一元素,对线性表进行插入和删除运算时，其运算效率比较低，(特别当线性表很大时，插入与删除运算很不方便),顺序存储结构往往多用于比较小的线性表或元素不常变动（指很少进行插入与删除运算）的线性表。对于大的线性表或元素经常变动的线性表可以采用链式存储结构,2.1.2,线性链表,1 线性链表的概念,2 线性链表的插入与删除,3 循环链表,4 单链表和循环链表,线性链表的概念,概念：,线性链表（,Linked List,）,是线性表的链式存储结构。,数据元素的表示由两部分信息组成：一是数据元素的值，二是数据元素在线性表中的逻辑位置。这两部分信息构成线性链表中的一个,结点,。,线性链表是由若干个结点组成，每个结点有两个域：一个是,数据域,，用以存放数据元素的值；另一个是,指针域,，用以存放后件的存储地址，即后件结点的存储序号。,Typedef struct List_Node,DataType data;,struct List_Node *next;,Node，*Linklist,data,next,a1,a2,a3,L,ai,an,线性链表的结点结构,Node*p;,或,Linklist p;,线性链表举例,（赵，钱，孙，李，周，伍，张，王）,的链式表示,1,13,19,25,31,37,43,7,头指针：,31(赵的地址),存储地址:,钱,孙,李,周,赵,伍,张,王,H,头指针,HEAD,结点序号,i,数据域,V,(i),指针域,NEXT(i),31,7,a3,25,13,a6,37,19,a2,7,25,a4,43,31,a1,19,37,a7,0,43,a5,13,线性链表的物理状态,a1 a2 a3 a4 a5 a6 a7,线性链表的逻辑状态,HEAD,31,19,7,25,43,13,37,a1,a2,a3,a4,a5,a6,a7,0,若,NEXT(i)0（,或,NULL，）,表示最后一个结点,，,链表终止。,头指针,HEAD,存放第一个结点的存储地址，指向链表中的第一个结点；是一组连续存储单元的首地址。,线性链表的插入,s-next=p-next;p-next=s;,a1,a2,a3,a1,a3,a2,p,p,s,s,p-next=s,插入前：,插入后：,指针,p,所指的结点后插入,指针,s,所指的结点,线性链表插入结点算法,void ListInsert_L(LinkList&L,int i,ElemType d),LinkList s,p;,int j;,p=L;j=0;,/,找到指向插入点,i,的指针,p,while(p!=NULL+j,if(!p|ji-1)return ERROR;,/,为插入的元素分配一个结点,s,s=(Node*)malloc(sizeof(Node);,if(!s)return OVERFLOW;,s-data=d;,s-next=p-next;p-next=s;,return();,在第,i,个结点后面插入结点,线性链表的删除,a,1,a,3,a,2,p,删除前：,删除后：,a,1,a,3,a,2,p,s,s=p-next,释放结点后：,a,1,a,3,p,free(s),p-next=p-next-next,;,或,s=p-next；p-next=s-next;,线性链表删除结点算法,Status ListDlete_L(LinkList L,int i,ElemType&d),LinkList s,p;,int j;,p=L;j=1;,/,找到删除点之前的结点,p,while(p-next,!=NULL+j,if(!(p-next)|（ji-1）)return ERROR;,s=p-next;,p-next=s-next;,d=s-data;,free(s);,return OK;,删除第,i,个元素，并由,d,返回其值,输入：,HEAD，b,输出：,q,Node*LOOKLIST(Node*HEAD,Datatype b),Node*q,qHEAD；,While(q-next!=NULL&q-data!=b),q=q-next;,return q,线性链表查找,在头指针为,HEAD,的非空链表中寻找指定元素,b,的前一个结点,q,循环链表,单链表在插入和删除时，对空表和第一个结点地插入和删除都需要单独考虑，使得对空表和非空表的处理不一样，循环链表避免了这个问题。,最后一个结点的指针域指向头结点,整个链表形成一个环。,单链表：,每个结点只有一个指针域。要找到某个结点的前件，必须从头指针开始，沿着指针方向扫描。,双向链表：,每个结点有两个指针域，一个称为左指针，指向其前件结点；另一个称为右指针，指向其后件。从表的任意结点出发可以通过正向环（或反向环）找到表中其它结点。,0,HEAD,0,单链表和双向链表,双向链表的结点定义,prior,data,next,结点：,typedef struct DuLnode,DataType data;,Struct DuLnode*prior;,Struct DuLnode*next;,DuLnode,*DuLinklist;,双向链表的插入,a1,a3,a2,p,s,插入前：,p,s,插入后：,a1,a2,a3,指针,p,所指的结点前插入,指针,s,所指的结点,s-prior=p-prior;p-prior-next=s;,s-next=p;p-prior=s;,双向链表的删除,a1,a2,p,删除前：,删除后：,p-prior-next=p-next,a3,a1,a2,p,a3,p-next-proir=p-prior,释放结点：,free(p);,删除指针,p,所指的结点,2.1.3,索引存储结构,1 索引存储的概念,2 “顺序一索引一顺序”存储方式,3 “顺序一索引一链接”存储方式,索引存储的概念,索引存储的基本思想,：,将具有,n,个结点线性表，划分成,m,个子表,（长度可以不等）然后分别存储此,m,个子表，并且另外设立一个索引表。,索引表,具有,m,个结点，每一个结点存储一个子表性质的有关信息以及子表中第一个结点的存储地址，在需要时，还可存储子表的其它有关信息。,索引表中的结点结构（数据项个数）可以根据实际应用的需要来设置，但对于同一索引表中的各结点结构应相同,索引存储的目的：,提高查找效率,索引函数,设线性表中每个结点元素,a,i,的关键字为,k,i,，,取函数：,jg（k,i,）,，i1，2,n,，,j=1,2,m,，,使线性表,L,中,j,值相等的结点元素归并到子表,L,j,中，这样就把具有,n,个结点的线性表划分为了,m,个子表。函数,g（k,i,）,称为索引函数。,线性表划分,有一个学生成绩表如右表所示。以成绩（即总分为关键字）对学生成绩表进行划分，取索引函数为：,g,（,k,）,INT,（,k,10,）,23，,即,以分数段,240,249,、,250,259,、,260,269,、,270,279,、,280,289,、,290,299,、,300,将此线性表划分成,7,个子表,L1,，,L2,，,L3,，,L4,，,L5,，,L6,，,L7,，,经过划分后，除,L5,，,L6,，,L7,，,为空表外，其余,4,个子表如表,2,3,所示。,学号,S,姓名,N$,总分,K,02,03,04,05,09,11,12,13,LIN,ZHANG,ZHAO,MA,ZHEN,WANG,LI,XU,276,261,246,273,255,243,258,249,划分为子表,学号,S,姓名,N$,总分,K,04,11,13,ZHAO,WANG,XU,246,243,249,学号,S,姓名,N$,总分,K,09,12,ZHEN,LI,255,258,子表,L,2,子表,L,1,K240,249，j1,K250,259，j2,学号,S,姓名,N$,总分,K,03,ZHANG,261,学号,S,姓名,N$,总分,K,02,05,LIN,MA,276,273,子表,L,3,子表,L,4,K260,269，j3,K270,279，j4,g,（,k,）,INT,（,k,10,）,23,索引函数：,由于索引存储将具有某个性质,P,的结点都集中在一个子表中，因此，处理（如查找）具有性质,P,的结点，不必查遍原线性表,L,中的全部结点，而直接对具有性质,P,的子表进行处理就行了。,例如，如何查找成绩为,240,249,的学生？,采用索引存储以后，有利于对线性表的处理，提高查找效率。,索引存储结构的优势,查找效率高！,索引存储的方式,索引存储包括,索引表的存储,以及,各子表的存储,。如果采用顺序分配与链式分配的存储结构，则共有四种索引存储的方式：,“顺序索引顺序”存储方式；,“顺序一索引一链接”存储方式；,“链接一索引顺序”存储方式；,“链接一索引一链接”存储方式。,“,顺序一索引一顺序,”,存储方式,索引表以及各子表：均用顺序存储方式；,索引表中每一个结点：,均设有若干个数据项，用以表示相应子表的有关信息；,还设有一个指针项（索引指针），用以指示相应子表的第一个结点的存储地址。,每个子表的内部都是顺序分配的，但各子表的存储顺序可以随意，且子表之间也不一定是连续的。,索引表中每个结点有三个数据项。第一个数据项表示子表的性质（一个分数段），例如，,250,表示,250,259,这个分数段；第二个数据项表示子表的长度；第三项为索引指针。,索引表和子表,“,顺序一索引一顺序,”,存储方式小结,实际应用中，,索引表中的每一个结点设置一个子表长度的数据项是很有用的,。因为各子表是顺序存储的，而对于顺序存储的线性表来说，除了需要指出第一个结点的存储序号外，它的长度有时是必不可少的，特别是对于查找操作尤为突出。,在,“,顺序一索引一顺序,”,存储方式中，虽然可根据子表的性质，在某个子表范围内进行处理，但由于各子表采用顺序分配，,就子表而言，存在顺序分配的缺点,，这种存储方式在线性表较固定的情况下才比较有用。,“,顺序一索引一链接,”,存储方式,索引表：用顺序存储方法,各子表：用链式存储方法,在这种存储结构中,各子表均为线性链表,而每一个线性链表的头指针是索引表中对应结点的指针项。,“,顺序一索引一链接,”,存储方式举例,设索引表空间用二列二维数组,P（1：7，1：2）,表示，其中第一列用以存放各分数段的关键字，第二列为指针顶。,设各子表存储空间中每一个结点有四个域：学号,S，,姓名,N，,总分,k，,链接指针,NEXT。,它们分别取自一维数组,S，N，K,及,NEXT。,然后依次输入各组数据：学号,num、,姓名,name,及总分,t1、计算索引函数值,iINT（t10）,一23。,2、取得一新结点,q，,其数据域分别为,S(q)num，N(q)name，K(q)t,3、,将新结点,q,链入以,P（i，2）,为头指针的线性链表链头。,建立学生成绩表存储结构,数据存储逻辑,状态,数据存储物理状态,2,.1.4,栈,1 栈的基本概念,2 栈的顺序存储结构,3 栈的基本运算,4 栈的应用举例,栈的基本概念,栈,:插入和删除只允许在一端进行的线性表称为栈。,栈顶,:在栈中，允许插入和删除的一端称为栈顶。,栈底,:不允许插入和删除的另一端称为栈底。,栈的,:按,“,后进先出,”,（,LIFO,Last In First Out修改,或,“,先进后出,”,（,FILO,First In Last Out）,的原则进行，所以栈又被称为,LIFO,或,FILO,表。,入栈,:元素的插入称为压人（,push）,或入栈。,退栈,:元素的删除称为弹出（,POP）,或退栈。,a,1,a,n,a,2,。,入栈,退栈,栈顶,栈底,栈的示意图,栈的顺序存储结构（顺序栈）,栈是特殊的线性表，栈的顺序存储结构也占有一片连续的存储空间。随着入栈与退栈操作的进行，栈顶的位置是浮动变化的。,为了反映栈顶位置的变化过程，通常要设一个,栈顶指针,top,，,以指向当前栈顶元素的存储位置。用,栈底指针,bot,，,指向栈底元素的存储位置。,顺序栈栈结构的定义,typedef struct,SElemType*bot;,/*,在栈构造之前和销毁之后，,bot,的值为,NULL*/,SElemType*top;/*,栈顶指针 */,int stacksize;/*,当前已分配的存储空间*/,SqStack;,#define STACK_INIT_SIZE 100,#define STACKINCREMENT 10,#define OK 1,#define OVERFLOW-1,#define ERROR 0,栈的基本操作（一）,InitStack(&S),操作结果:构造一个空的栈,S。,DestroyStack(&S),初始条件:栈,S,已经存在。,操作结果:销毁栈,S。,ClearStack(&S),初始条件:栈,S,已经存在。,操作结果:将栈,S,重置为空栈。,栈的基本操作（二）,StackEmpty(S),初始条件:栈,S,已经存在。,操作结果:若栈,S,为空栈返回,TURE;,否则返回,FALSE。,StackLength(S),初始条件:栈,S,已经存在。,操作结果:返回栈,S,中的数据元素个数。,GetTop(S,&e),初始条件:栈,S,已经存在且非空。,操作结果:用,e,返回栈,S,中栈顶元素的值。,栈的基本操作（三）,Push(&S,e),初始条件:栈,S,已经存在。,操作结果:插入元素,e,为新的栈顶元素。Pop(&S,&e),初始条件:栈,S,已经存在且非空。,操作结果:删除,S,的栈顶元素并用,e,返回其值。,StackTraverse(S,visit(),初始条件:栈,S,已经存在且非空。,操作结果:从栈底到栈顶依次对,S,的每个元素调用函数,visit()。,一旦,visit(),失败，则操作失败。,顺序栈示意图,*,bot,*,top,stacksize,.,a,1,.,a,i,a,n,*,bot,*,top,stacksize,初始,空,栈,*,top=*bot;,stacksize=STACK_INIT_SIZE,顺序栈,顺序栈的操作实现（一）,Status InitStack(SqStack*s),s-bot=(SElemType*)malloc,(STACK_INIT_SIZE*sizeof(SElemType);,if(!s-bot)return(OVERFLOW);,s-top=s-bot;,s-stacksize=STACK_INIT_SIZE;,return OK;,/*InitStack*/,InitStack,构造一个空的栈,S,顺序栈的操作实现（二）,*,bot,*,top,stacksize,.,a,1,.,a,i,a,n,s,e,*,e=*(s.top-1);,Status GetTop(SqStack s,SElemType*e),if(s.top=s.bot)return ERROR;,*e=*(s.top-1);,return OK;,/*GetTop */,GetTop,栈,s,非空,则用,e,返回栈,s,中栈顶元素的值，,并返回,OK；,否则返回,ERROR。,顺序栈的操作实现（三）,Status Push(SqStack*s,SElemType e),if(s-top,s-bot=s-stacksize),l_temp=(SElemType*)realloc,(s-bot,(s-stacksize+STACKINCREMENT)*sizeof(SElemType);,if(!l_temp)return(OVERFLOW);s-bot=l_temp;,s-top=s-bot+s-stacksize;,s-stacksize+=STACKINCREMENT;,/*,栈满，追加存储空间*/,s-top+;*(s-top)=e;,return OK;,/*Push*/,Push,插入元素,e,为新的栈顶元素,入栈示意图,e,*,bot,*,top,stacksize,.,a,1,.,a,i,a,n,s,*,bot,*,top,stacksize,.,a,1,.,a,i,a,n,s,栈满时，追加存储空间,*(,s-top+)=e;,出栈操作,*,base,*,top,stacksize,.,a,1,.,a,i,a,n,s,e,*,e=*(-s-top);,Status Pop(SqStack*s,SElemType*e),if(s-top=s-bot)return ERROR;,*e=*(s-top);s-top-;,return OK;,/*Pop */,P,op,栈,S,非空,则删除,S,的栈顶元素,用,e,返回栈,S,中栈顶元素的值，,并返回,OK,否,则返回,ERROR。,栈的溢出,下溢,当对一个空栈进行删除时，便发生“,下溢,”(,under,fl,ow,)。,一般情况下，“下溢”是有意义的，可以被用来控制程序的转移。,例如，用栈存放各层子程序的返回地址，实现子程序的嵌套调用。栈的“下溢”说明子程序嵌套有错（返回语句多于调用语句）,上溢,当对一个已满的栈作人栈操作时，便要发生,“,上溢,”,（,overflow,）。,“,上溢,”,是一种出错状态。,在顺序存储结构中，避免,“,上溢,”,的办法是事先给栈分配一个足够大的空间。但这种做法太浪费空间,最好的方法是采用链式存储结构。,栈的应用举例,程序的嵌套调用,表达式的计算,递归过程的实现,数值转换,迷宫问题,栈的应用举例表达式的计算,计算机是如何处理表达式呢？,对于编译系统来说，要根据表达式的运算顺序将它翻译成求值的机器指令序列；,而对于解释系统来说，要根据表达式的运算顺序对它边解释边求值。,处理一个表达式，首先必须确定其,运算顺序,。对于优先级大的运算符应优先进行处理。,运算符以及对应的优先数,算术运算符：,*,*,（,）,；,优先数：,4 3322 11 0,建立两个栈：,操作数栈,OVS,和,运算符栈,OPS,。,操作数栈用于存放表达式中的操作数，其栈顶指针为,topv,，,初始时为空，即,topv,0,；,运算符栈用于存放表达式中的运算符（包括左、右括号及表达式结束符），其栈顶指针为,topp,，,初始时，运算符栈中有一个表达式结束符，即,topp,1,，,且,OPS,（,l,）“；”。,扫描表达式（一）,自左至右扫描待处理的表达式，假设当前扫描到的符号为,W,，,根据不同的符号,W,作如下处理：,1,若,W,为操作数则将,W,压入操作数栈,OVS,，,且继续扫描下一个字符。,2,若,W,为运算符，则根据运算符的性质作以下处理：,（,1,）若运算符,W,为左括号“（”或者运算符,W,的优先数大于运算符栈栈顶的运算符（即,OPS,（,topp,），,则将运算符,W,压人运算符栈,OPS,，,并继续扫描下一个符号；,扫描表达式（二）,（,2,）若运算符,W,为表达式结束符“；”且运算符栈栈顶的运算符也为表达式结束符（即,OPS,（,topp,）“；”），,则处理过程结束，此时，操作数栈栈顶元素（即,OVS,（,topv,）,即为表达式值；,（,3,）若运算符,W,为右括号“）”且运算符栈栈顶的运算符为左括号（即,OPS,（,topp,）“（”），,则将左括号从运算符栈弹出，继续扫描下一个符号；,（,4,）若运算符,W,的优先数不大于运算符栈栈顶的运算符(即,OPS,(,topp,)，,则从操作数栈,OVS,中弹出两个操作数，设先后弹出的操作数为,x,、,z,，,再从运算符栈,OPS,中弹出一个运算符，设为,。,作运算,zx,，,并将运算结果压人操作数栈,OVS,。,本次的运算符下次将重新考虑。,例:计算表达式,A*,（,B,十,C,D,）,一,E*F*G;,（,l,）,建立操作数栈,OVS,与运算符栈,OPS,OVS,OPS,topv,topp,;,步骤2,A*,（,B,十,C,D,）,一,E*FG;,（,2,）操作数,A,进,OVS,栈，运算符“,*,”进,OPS,栈，左括号“（”进,OPS,栈，操作数,B,进,OVS,栈，运算符“”进,OPS,栈，操作数,C,进,OVS,栈，运算符“,/,”进,OPS,栈，操作数,D,进,OVS,栈。,OVS,OPS,topv,topp,/,D,+,C,(,B,*,A,;,步骤3,A*,（,B,十,C,D,）,一,E*F*G;,（,3,）因右括号“）”的优先数1不大于运算符“”的优先数3，从,OVS,栈弹出,D,和,C,，,从,OPS,栈弹出运算符“”，作运算,C,D,T1,，,T1,进,OVS,栈。,OVS,OPS,topv,+,topv,T1