数据结构与算法教案

数据结构与算法第一章绪论1.1数据结构讨论的范畴NiklausWirthAlgorithm+DataStructures=Programs程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型例如:数值计算的程序设计问题结构静力分析计算─━线性代数方程组全球天气预报─━环流模式方程非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:基本操作是“比较两个数的大小”模型：？例二：计算机对弈算法：对弈的规则和策略模型：？例三：足协的数据库管理算法：需要管理的项目？如何管理？用户界面？模型：？概括地说，数据结构描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中的表示和实现1.2基本概念一、数据与数据结构数据:所有能被输入到计算机中，且被计算机处理的符号的集合计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式数据元素:数据中的一个“个体”，数据结构中讨论的基本单位数据项：?/b>数据结构中讨论的最小单位数据元素是数据项的集合例如：运动员（数据元素）姓名俱乐部名称出生日期参加日期职务业绩其中出生日期年月日是组合项数据结构：带结构的数据元素的集合例如,一个含12位数的十进制数可以用三个4位的十进制数表示3214,6587,9345─a1(3214),a2(6587),a3(9345)在a1、a2和a3之间存在“次序”关系<a1,a2>、<a2,a3>3214，6587，9345≠6587，3214，9345a1a2a3a2a1a3又例，2行3列的二维数组{a1,a2,a3,a4,a5,a6}a1a2a3a4a5a6行的次序关系:row={,,,}

列的次序关系:col={,,}

再例，一维数组{a1,a2,a3,a4,a5,a6}中存在次序关系:{i,ai+1>|i=1,2,3,4,5}数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。严格地讲，以上定义仅是数据的逻辑结构的定义数据的存储结构─━逻辑结构在存储器中的映象数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示<x,y>的方法）顺序映象以存储位置的相邻表示后继关系y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置在不同的编程环境中，存储结构可有不同的描述方法，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型，定义长整数为:typedefintLong_int[3]二、数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。因为类型明显或隐含地规定了，在程序执行期间，变量或表达式所有可能取值的范围，以及在这些之上允许进行的操作。数据类型是一个值的集合和定义在此集合上的一组操作的总称。三、抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作ADT有两个重要特征:数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节例如抽象数据类型复数的定义：ADTComplex{数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{|e1是复数的实数部分,|e2是复数的虚数部分}基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex假设:z1和z2是上述定义的复数，则Add(z1,z2,z3)操作的结果将得到z3=z1+z2抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现1.3算法和算法衡量一、算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5．有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。二、算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d．程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。三、算法效率的衡量方法和准则通常有两种衡量算法效率的方法:事后统计法缺点：1。必须执行程序2．其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度如何估算算法的时间复杂度？算法=控制结构+原操作（固有数据类型的操作）算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间算法的执行时间与原操作执行次数之和成正比从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则例一for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];}基本操作:乘法操作时间复杂度:O(n3)例二voidselect_sort(inta[],intn){//将a中整数序列重新排列成自小至大有序的整数序列。for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}//select_sort基本操作:比较(数据元素)操作时间复杂度:O(n2)例三voidbubble_sort(inta[],intn){//将a中整数序列重新排列成自小至大//有序的整数序列。for(i=n-1,change=TRUE;i>1&&change;--i){change=FALSE;for(j=0;j<>if(a[j]>a[j+1]){a[j]←→a[j+1];change=TRUE}}}//bubble_sort基本操作:赋值操作时间复杂度:O(n2)四、算法的存储空间需求算法的空间复杂度S(n)=O(g(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1．输入数据所占空间;2．程序本身所占空间；3．辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。学习要点1.熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2.了解抽象数据类型的定义、表示和实现方法。3．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。4．掌握计算语句频度和估算算法时间复杂度的方法。

第二章线性表线性结构是一个数据元素的有序（次序）集线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。2.1线性表的类型定义抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{i-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：{结构初始化}InitList(&L)操作结果：构造一个空的线性表L。{销毁结构}DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。{引用型操作}ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。GetElem(L,cur_e,&next_e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。{加工型操作}ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList利用上述定义的线性表可以完成其它更复杂的操作例2-1假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A＝A∪B。上述问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．从线性表LB中依次取得每个数据元素;GetElem(LB,i)→e2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)voidunion(List&La,ListLb){//将所有在线性表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_len1,e);//La中不存在和e相同的数据元素，则插入之}}//union例2-2已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。voidpurge(List&La,ListLb){//已知线性表Lb中的数据元素依值非递减有序排列(Lb是有序表)，//构造线性表La，使其只包含Lb中所有值不相同的数据元素InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!equal(en,e)){ListInsert(La,++La_len,e);en=e;}//La中不存在和e相同的数据元素，则插入之}}//purge例2-3归并两个“其数据元素按值非递减有序排列的”线性表LA和LB，求得线性表LC也具有同样特性设La=(a1,…,ai,…,an)Lb=(b1,…,bj,…,bm)Lc=(c1,…,ck,…,cm+n)则Ck=k=1,2,…,m+n1．分别从LA和LB中取得当前元素ai和bj；2．若ai≤bj，则将ai插入到LC中，否则将bj插入到LC中。voidMergeList(ListLa,ListLb,List&Lc){//已知线性表La和Lb中的元素按值非递减排列。//归并La和Lb得到新的线性表Lc，//Lc的元素也按值非递减排列。InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空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<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//merge_list2.2线性表类型的实现¾顺序映象用一组地址连续的存储单元依次存放线性表中的数据元素线性表的起始地址，称作线性表的基地址以“存储位置相邻”表示有序对i-1，ai>即：所有数据元素的存储位置均取决于第一个数据元素的存储位置顺序映像的C语言描述//-----线性表的动态分配顺序存储结构-----#defineLIST_INIT_SIZE80//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;//俗称顺序表线性表的初始化在顺序映像中的实现StatusInitList_Sq(SqList&L){//构造一个空的线性表L。L.elem=(ElemType*)malloc(LISTINCREMENT*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//长度为0L.listsize=LISTINCREMENT;//初始存储容量returnOK;}//InitList_Sq线性表操作LocateElem(L,e,compare())的实现：intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()的元素的位序。//若找到，则返回其在L中的位序，否则返回0。i=1;//i的初值为第1元素的位序p=L.elem;//p的初值为第1元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq此算法的时间复杂度为:O(ListLength(L))线性表操作ListInsert(&L,i,e)的实现：问：插入元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)StatusListInsert_Sq(SqList&L,intpos,ElemTypee){//在顺序线性表L的第pos个元素之前插入新的元素e，//pos的合法值为1≤pos≤Listlength_Sq(L)+1if(pos<1||pos>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存储容量}q=&(L.elem[pos-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;}//ListInsert_Sq此算法的时间复杂度为:O(ListLength(L))线性表操作ListDelete(&L,i,&e)的实现：问：删除元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,ai+1,…,an)改变为(a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,intpos,ElemType&e){//在顺序线性表L中删除第pos个元素，并用e返回其值。//pos的合法值为1≤pos≤ListLength_Sq(L)if((pos<1)||(pos>L.length))returnERROR;//删除位置不合法p=&(L.elem[pos-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后的元素左移--L.length;//表长减1returnOK;}//ListDelete_Sq此算法的时间复杂度为:O(ListLength(L))2.3线性表类型的实现¾链式映象一、单链表用一组地址任意的存储单元存放线性表中的数据元素以元素(数据元素的映象)+指针(指示后继元素存储位置的)=结点(表示数据元素)以“结点的序列”表示线性表¾¾称作链表以线性表中第一个数据元素a1的存储地址作为线性表的地址，为线性表的头指针二、结点和单链表的C语言描述typedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;三、单链表操作的实现线性表的操作GetElem(L,i,&e)在链表中的实现:基本操作为:使指针p始终指向线性表中第j个数据元素StatusGetElem_L(LinkListL,intpos,ElemType&e){//L为带头结点的单链表的头指针。当线性表中存在第pos个元素//存在时，则将第pos个数据元素的值赋给e并返回OK，否则返//回ERRORp=L->next;j=1;//初始化，p指向第一个结点，j为计数器while(p&&j{//顺指针向后查找，直到p指向第pos个元素或p为空p=p->next;++j;}if(!p||j>pos)returnERROR;//第pos个元素不存在e=p->data;//取第pos个元素returnOK;}//GetElem_L算法的时间复杂度为:O(ListLength(L))线性表的操作ListInsert(&L,i,e)在链表中的实现:基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针有序对i-1,ai>改变为i-1,e>和i>

StatusListInsert_L(LinkListL,intpos,ElemTypee){//在带头结点的单链表L中第pos个数据元素之前插入数据元素ep=L;j=0;while(p&&j<pos-1){p=p->next;++j;}//寻找第pos-1个结点if(!p||j>pos-1)returnERROR;//pos小于1或者大于表长s=(LinkList)malloc(sizeof(LNode));//生成新结点s->data=e;s->next=p->next;//插入L中p->next=s;returnOK;}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))线性表的操作ListDelete(&L,i,&e)在链表中的实现:

基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针有序对i-1,ai>和i,ai+1>改变为i-1,ai+1>

StatusListDelete_L(LinkListL,intpos,ElemType&e){//在带头结点的单链表L中，删除第pos个元素，并由e返回其值p=L;j=0;while(p->next&&j<pos-1){//寻找第pos个结点，并令p指向其前趋p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点e=q->data;free(q);returnOK;}//ListDelete_L算法的时间复杂度为:O(ListLength(L))voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点scanf(&p->data);//输入元素值p->next=L->next;L->next=p;//插入到表头}}//CreateList_L算法的时间复杂度为:O(Listlength(L))例2-1算法的时间复杂度控制结构：for循环基本操作：LocateElem(La,e,equal())当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)×ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:O(ListLength(La)×ListLength(Lb))例2-2算法的时间复杂度控制结构：for循环基本操作：GetElem(Lb,i,e)当以顺序映像实现抽象数据类型线性表时为:O(ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:O(ListLength2(Lb))例2-3算法的时间复杂度控制结构：三个并列的while循环基本操作：ListInsert(Lc,++k,e)当以顺序映像实现抽象数据类型线性表时为:O(ListLength(La)+ListLength(Lb))当以链式映像实现抽象数据类型线性表时为:O((ListLength(La)+ListLength(Lb)2)用上述定义的单链表实现线性表的操作时，存在的问题：1．单链表的表长是一个隐含的值；2．在单链表的最后一个元素最后插入元素时，需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。改进链表的设置：1．增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2．将基本操作中的“位序i”改变为“指针p”四、一个带头结点的线性链表类型typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*Link,*Position;typedefstruct{//链表类型Linkhead,tail;//指向头结点和最后一个结点intlen;//指示链表长度Linkcurrent;//指向当前访问的结点的指针，//初始位置指向头结点}LinkList;StatusMakeNode(Link&p,ElemTypee);//分配由p指向的值为e的结点，并返回OK；//若分配失败，则返回ERRORvoidFreeNode(Link&p);//释放p所指结点链表的基本操作:{结构初始化和销毁结构}StatusInitList(LinkList&L);//构造一个空的线性链表L，//头指针、尾指针和当前指针均指向头结点，表长为零StatusDestroyList(LinkList&L);//销毁线性链表L，L不再存在{引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//求表长StatusPrior(LinkListL);//改变当前指针指向其前驱StatusNext(LinkListL);//改变当前指针指向其后继ElemTypeGetCurElem(LinkListL);//返回当前指针所指数据元素StatusLocatePos(LinkListL,inti);//改变当前指针指向第i个结点StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//若存在与e满足函数compare()判定关系的元素，则移动当前指针//指向第1个满足条件的元素，并返回OK;否则返回ERRORStatusListTraverse(LinkListL,Status(*visit)());//依次对L的每个元素调用函数visit(){加工型操作}StatusClearList(LinkList&L);//重置为空表StatusSetCurElem(LinkList&L,ElemTypee);//更新当前指针所指数据元素StatusAppend(LinkList&L,Links);//一串结点链接在最后一个结点之后StatusInsAfter(LinkList&L,ElemTypee);//将元素e插入在当前指针之后StatusDelAfter(LinkList&L,ElemType&e);//删除当前指针之后的结点{这里定义的大部分算法都将结点和指针的概念封装在算法中}StatusInsAfter(LinkList&L,ElemTypee){//若当前指针在链表中，则将数据元素e插入在线性链表L中//当前指针所指结点之后,并返回OK;否则返回ERROR。if(!L.current)returnERROR;if(!MakeNode(s,e))returnERROR;s->next=L.current->next;L.current->next=s;RreturnOK;}//InsAfterStatusDelAfter(LinkList&L,ElemType&e){//若当前指针及其后继在链表中，则删除线性链表L中当前//指针所指结点之后的结点，并返回OK;否则返回ERROR。if(!(L.current&&L.current->next))returnERROR;q=L.current->next;L.current->next=q->next;e=q->data;FreeNode(q);returnOK;}//DelAfter{利用上述定义的线性链表可以完成线性表的其它操作}例一:StatusListInsert_L(LinkListL,inti,ElemTypee){//在带头结点的单链线性表L的第i个元素之前插入元素eif(!LocatePos(L,i-1))returnERROR;//i值不合法if(InsAfter(L,e))returnOK;//插入在第i-1个结点之后elsereturnERROR;}//ListInsert_L例二:voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lcint(*compare)(ElemType,ElemType))){//已知单链线性表La和Lb的元素按值非递减排列，归并//La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列if(!InitList(Lc))returnERROR;//存储空间分配失败LocatePos(La,0);LocatePos(Lb,0);//当前指针指向头结点if(DelAfter(La,e))a=e;elsea=MAXC;//MAXC为常量最大值if(DelFirst(Lb,e))b=e;elseb=MAXC;//a和b为两表中当前比较元素while(!(a=MAXC&&b=MAXC)){//La或Lb非空if((*compare)(a,b)<=0){//a≤bInsAfter(Lc,a);if(DelAfter(La,e1)a=e1;elsea=MAXC;}else{//a＞bInsAfter(Lc,s);if(DelAfter(Lb,e)b=e1;elseb=MAXC;}}DestroyList(La);DestroyList(Lb);//销毁链表La和LbreturnOK;}//MergeList_L五、其它形式的链表1.双向链表//-----线性表的双向链表存储结构-----typedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior;//指向前驱的指针域structDuLNode*next;//指向后继的指针域}DuLNode,*DuLinkList;2.循环链表最后一个结点的指针域的指针又指回第一个结点的链表2.4一元多项式的表示一元多项式在计算机中，可以用一个线性表来表示:P=(p0,p1,…，pn)但是对于形如S(x)=1+3x10000–2x20000的多项式，上述表示也就不恰当了。一般情况下的一元多项式可写成Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指数为ei的项的非零系数，0≤e1<e2<┄<em=n它可以用其数据元素为(系数项，指数项)的线性表来表示（（p1,e1）,(p2,e2),┄,(pm,em)）例如：线性表（(7,3),(-2,12),(-8,999)）表示多项式P999(x)=7x3-2x12-8x999抽象数据类型一元多项式的定义如下：ADTPolynomial{数据对象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0}{TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1＝{i-1,ai>|ai-1,ai∈D,且ai-1中的指数值＜ai中的指数值，i=2,...,n}基本操作：CreatPolyn(&P,m)操作结果：输入m项的系数和指数，建立一元多项式P。DestroyPolyn(&P)初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。PrintPolyn(&P)初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa＋Pb，并销毁一元多项式Pb。SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa=Pa－Pb，并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相乘运算，即：Pa=Pa×Pb，并销毁一元多项式Pb。PolynLength(P)初始条件：一元多项式P已存在。操作结果：返回一元多项式P中的项数。}ADTPolynomial如此定义的多项式可以看成是一个有序表(对其数据元素中的指数项而言),则多项式定义中的各个操作均可利用有序表的操作来完成。学习要点1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i..j]的上、下界和长度之间的变换公式(L=j-i+1,i=j-L+1,j=i+L-1)，链表中指针p和结点*p的对应关系(结点*(p->next)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。3.熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4.熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。5.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。第三章栈和队列从数据结构的角度看:它们和线性表相同从数据类型的角度看:它们和线性表不同线性表栈队列Insert(L,i,x)(1<=i<=n+1)Insert(S,n+1,x)Insert(Q,n+1,x)Delete(L,i)(1<=i<=n)Delete(S,n)Delete(Q,1)3.1栈的类型定义ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{i-1,ai>|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack3.2栈的应用举例例一、数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算）例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。voidconversion(){//对于输入的任意一个非负十进制整数，打印输出//与其等值的八进制数InitStack(S);//构造空栈scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先一味地入栈，然后一味地出栈。也许，有的读者会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。例二、括号匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或(()])均为不正确的格式。检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。例如考虑下列括号序列：[([][])]12345678分析可能出现的不匹配的情况:到来的右括弧非是所“期待”的;到来的是“不速之客”;直到结束，也没有到来所“期待”的。statusmatching(string&exp){//检验表达式中所含括弧是否正确嵌套，若是，则返回//OK，否则返回ERRORintstate=1;while(i<=length(exp)&&state){swithofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case")":{if(NOTStackEmpty(S)&&GetTop(S)="("){Pop(S,e);i++;}else{state=0}break;}……}}if(state&&StackEmpty(S))returnOKelsereturnERROR;}例三、行编辑程序问题一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。每接受一个字符即存入用户数据区”不恰当。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，可用一个退格符“#”表示前一个字符无效；可用一个退行符“@”，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);voidLineEdit(){//利用字符栈S，从终端接收一行并传送至调用过程//的数据区。InitStack(S);//构造空栈Sch=getchar();//从终端接收第一个字符while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!=‘\n‘){switch(ch){case‘#‘:Pop(S,c);break;//仅当栈非空时退栈case‘@‘:ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;//有效字符进栈，未考虑栈满情形}ch=getchar();//从终端接收下一个字符}将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(S);//重置S为空栈if(ch!=EOF)ch=getchar();}DestroyStack(S);}例四、迷宫求解求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。假设迷宫如下图所示:假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置"可通"，则纳入"当前路径"，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。求迷宫中一条从入口到出口的路径的算法可简单描述如下：设定当前位置的初值为入口位置；do｛若当前位置可通，则｛将当前位置插入栈顶；//纳入路径若该位置是出口位置，则结束；//求得路径存放在栈中否则切换当前位置的东邻方块为新的当前位置；｝否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝｝while(栈不空）；在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。typedefstruct{intord;//通道块在路径上的“序号”PosTypeseat;//通道块在迷宫中的“坐标位置”intdi;//从此通道块走向下一通道块的“方向”}SElemType;//栈的元素类型StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend){//若迷宫maze中从入口start到出口end的通道，//则求得一条存放在栈中（从栈底到栈顶），并返回//TRUE；否则返回FALSEInitStack(S);curpos=start;//设定“当前位置”为“入口位置”curstep=1;//探索第一步do{if(Pass(curpos)){//当前位置可以通过，即是未曾走到过的通道块FootPrint(curpos);//留下足迹e=(curstep,curpos,1);Push(S,e);//加入路径if(curpos==end)return(TRUE);//到达终点（出口）curpos=NextPos(curpos,1);/下一位置是当前位置的东邻curstep++;//探索下一步}else{//当前位置不能通过if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){MarkPrint(e.seat);Pop(S,e);//留下不能通过的标记，并退回一步}//whileif(e.di<4){e.di++;Push(S,e);//换下一个方向探索curpos=NextPos(curpos,e.di);//设定当前位置是该新方向上的相邻块}//if}//if}//else}while(!StackEmpty(S));return(FALSE);}//MazePath例五、表达式求值限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数在计算机中，表达式可以有三种不同的标识方法设Exp=S1+OP+S2则称OP+S1+S2为表达式的前缀表示法称S1+OP+S2为表达式的中缀表示法称S1+S2+OP为表达式的后缀表示法可见，它以运算符所在不同位置命名的。结论:操作数之间的相对次序不变;运算符的相对次序不同;中缀式丢失了括弧信息，致使运算的次序不确定;前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;如何从后缀式求值？先找运算符，后找操作数如何从原表达式求得后缀式？分析“原表达式”和“后缀式”中的运算符:每个运算符的运算次序要由它之后的一个运算符来定，若当前运算符的优先数小，则暂不进行;否则立即进行。从原表达式求得后缀式的规律为：设立操作数栈;设表达式的结束符为“#”,予设运算符栈的栈底为“#”若当前字符是操作数，则直接发送给后缀式;若当前运算符的优先数高于栈顶运算符，则进栈;否则，退出栈顶运算符发送给后缀式;“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。算法描述如下：voidtransform(charsuffix[],charexp[]){//从合法的表达式字符串exp求得其相应的后缀式InitStack(S);Push(S,¢#¢);p=exp;ch=*p;while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);//直接发送给后缀式else{switch(ch){case¢(¢:Push(S,ch);break;case¢)¢:{Pop(S,c);while(c!=¢(¢){Pass(Suffix,c);Pop(S,c)}break;}defult:{while(!Gettop(S,c)&&(precede(c,ch))){Pass(Suffix,c);Pop(S,c);}if(ch!=¢#¢)Push(S,ch);break;}//defult}//switch}//elseif(ch!=¢#¢){p++;ch=*p;}}//while}//CrtExptree表达式求值的规则:设立运算符栈和操作数栈;设表达式的结束符为“#”,予设运算符栈的栈底为“#”若当前字符是操作数，则进操作数栈;若当前运算符的优先数高于栈顶运算符，则进栈;否则，退出栈顶运算符作相应运算;“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。算法描述如下:OperandTypeEvaluateExpression(){//算术表达式求值的算符优先算法。设OPTR和OPND//分别为运算符栈和运算数栈，OP为运算符集合。InitStack(OPTR);Push(OPTR,‘#‘);initStack(OPND);c=getchar();while(c!=‘#‘||GetTop(OPTR)!=‘#‘){if(!In(c,OP)){Push((OPND,c);c=getchar();}//不是运算符则进栈elseswitch(precede(GetTop(OPTR),c){case‘<‘://栈顶元素优先权低Push(OPTR,c);c=getchar();break;case‘=‘://脱括号并接收下一字符Pop(OPTR,x);c=getchar();break;case‘>‘#//退栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression例六、实现递归在高级语言编制的程序中，调用函数与被调用函数之间的链接和信息交换必须通过栈例进行。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事:将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。从被调用函数返回调用函数之前，应该完成:保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。多个函数嵌套调用的规则是:后调用先返回此时的内存管理实行“栈式管理”递归过程指向过程中占用的数据区，称之为递归工作栈每一层的递归参数合成一个记录，称之为递归工作记录栈顶记录指示当前层的执行情况，称之为当前活动记录栈顶指针，称之为当前环境指针例如:voidhanoi(intn,charx,chary,charz)//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1{2if(n==1)3move(x,1,z);//将编号为１的圆盘从x移到z4else{5hanoi(n-1,x,z,y);//将x上编号为１至n-1的圆//盘移到y,z作辅助塔6move(x,n,z);//将编号为n的圆盘从x移到z7hanoi(n-1,y,x,z);//将y上编号为１至n-1的圆盘//移到z,x作辅助塔8}9}3.3栈类型的实现顺序栈类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//base的初值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//-----基本操作的函数原型说明-----StatusInitStack(SqStack&S);//构造一个空栈SStatusDestroyStack(SqStack&S);//销毁栈S，S不再存在StatusClearStack(SqStack&S);//把S置为空栈StatusStackEmpty(SqStackS);//将栈S为空栈，则返回TRUE，否则返回FALSEintStackLength(SqStackS);//返回S的元素个数，即栈的长度StatusGetTop(SqStackS,SElemType&e);//若栈不空，则用e返回S的栈顶元素，并返回OK；//否则返回ERRORStatusPush(SqStack&S,SElemTypee);//插入元素e为新的栈顶元素StatusPop(SqStack&S,SElemType&e);//若栈不空，则删除S的栈顶元素，用e返回其值，//并返回OK；否则返回ERROR链栈利用链表实现栈，注意链表中指针的方向是从栈顶到栈底。3.4队列的类型定义ADTQueue{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{i-1,ai>|ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADTQueue3.5队列类型的实现链队列——链式映象typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;//-----基本操作的函数原型说明-----StatusInitQueue(LinkQueue&Q){//构造一个空队列QStatusDestroyQueue(LinkQueue&Q){//销毁队列Q，Q不再存在StatusClearQueue(LinkQueue&Q){//将Q清为空队列StatusQueueEmpty(LinkQueueQ){//若队列Q为空队列，则返回TRUE，否则返回FALSEintQueueLength(LinkQueueQ){//返回Q的元素个数，即为队列的长度StatusGetHead(LinkQueueQ,QElemType&e){//若队列不空，则用e返回Q的队头元素，并返回OK；//否则返回ERRORStatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，用e返回其值，//并返回OK；否则返回ERROR循环队列——顺序映象#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//动态分配存储空间intfront;//头指针，若队列不空，指向队列头元素intrear;//尾指针，若队列不空，指向队列尾元素//的下一个位置}SqQueue;3.6队列应用举例——排队问题的系统仿真一、需求分析和规格说明编制一个事件驱动仿真程序以模拟理发馆内一天的活动，要求输出在一天的营业时间内，到达的顾客人数、顾客在馆内的平均逗留时间和排队等候理发的平均人数以及在营业时间内空椅子的平均数。假设理发馆内设有N把理发椅，一天内连续营业T小时。在T小时内顾客到达的时间及顾客理发所需时间均随机生成，过了营业时间，不再有顾客进门，但仍需继续为已进入店内的顾客理发，直至最后一名顾客离开为止。二、概要设计1.主程序为:voidBarberShop_Simulation(intchairNum,intCloseTime){//理发店业务模拟，统计一天内顾客在店内逗留的平均时间//和顾客在等待理发时排队的平均长度以及空椅子的平均数OpenForDay;//初始化whileMoreEventdo{EventDrived(OccurTime,EventType);//事件驱动switch(EventType){case‘A‘:CustomerArrived;break;//处理到达事件case‘D‘:CustomerDeparture;break;//处理离开事件default:Invalid;}//switch}//whileCloseForDay;//计算平均逗留时间和排队的平均长度}//BarberShop_Simulation2.数据类型为:ADTEvent(事件){数据对象:D={事件的发生时刻，事件类型}数据关系:R={}基本操作:Initiate(&E,oT,eT);操作结果:产生一个发生时间为oT,事件类型为eT的事件E;GetOccurTime(ev);初始条件:事件ev已存在，操作结果:返回该事件的发生时间;GetEventType(ev);初始条件:事件ev已存在;操作结果:返回该事件的类型;}ADTcustomer(顾客){数据对象:D={进门时刻，理发所需时间};数据关系:R={}基本操作:Initiate(&P,aT,cT);操作结果:产生一个进门时刻为aT,理发时间为cT的顾客P;GetArrivalTime(Ps);初始条件:顾客Ps已存在，操作结果:返回该顾客的进门时刻;GetCutTime(Ps);初始条件:顾客Ps已存在;操作结果:返回该顾客的理发时间;}ADTOrderedList(有序表){数据对象:是上述定义的事件的集合数据关系:按事件的发生时刻自小至大有序基本操作:在线性表的操作的基础上添加一个有序表的插入Insert(&OL,x)初始条件:有序表OL已存在;操作结果:在有序表中插入x,并保持表的有序性;}ADT(数据元素为上述定义的顾客的)队列一．学习要点1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过程。二、思考题3.1若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意：两侧铁道均为单向行驶道)，则请回答：(1)如果进站的车厢序列为123，则可能得到的出站车厢序列是什么?(2)如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如