Java版数据结构(程序员必须看)

数据结构,计算机科学与技术学院张宏,第一章绪论,1.1什么是数据结构1.2有关概念和术语1.3算法和算法分析1.3.1算法1.3.2算法设计的要求1.3.3算法效率的度量1.3.4算法的存储空间的需求,第一章绪论,计算机学科一直处于高速发展中,而且这种发展速度还会持续。,计算机科学已经难以完全覆盖学科新的发展，因此扩展后的学科称为计算学科。,包括：计算机科学、计算机工程、软件工程、信息系统,关键问题：利用计算机进行信息表示和处理的涉及：信息的表示信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,1.1什么是数据结构众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。什么是数据结构呢？例子：例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)(an，bn)其中(ai，bi)(i=1，2n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。,数据结构含义：就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。,所有能被输入到计算机中，且能被计算机处理的符号的集合。,数据:,是计算机操作的对象的总称。,是计算机处理的信息的某种特定的符号表示形式。,1.2有关概念和术语,是数据（集合）中的一个“个体”,数据元素:,是数据结构中讨论的基本单位,数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。,一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。,数据在计算机中的表示称为数据的物理结构，又称为存储结构。,数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C+语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是-3，-2，-1，0，1，2，3，英文字符类型的数据对象是A，B，C，D，E，F，,1.3算法和算法分析1.3.1算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,1.3.2算法设计的要求,设计算法时，通常应考虑达到以下目标：,1、正确性2、可读性3、健壮性4、高效率与低存储量需求,1正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“正确”的理解可以有以下四个层次：,a程序中不含语法错误；,b程序对于几组输入数据能够得出满足要求的结果；,c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第c层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,2.可读性,算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。,3健壮性,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,4高效率与低存储量需求,通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。,1.3.3算法效率的度量,通常有两种衡量算法效率的方法:,事后统计法,事前分析估算法,缺点：1必须执行程序2其它因素掩盖算法本质,和算法执行时间相关的因素：,1算法选用的策略,2问题的规模,3编写程序的语言,4编译程序产生的机器代码的质量,5计算机执行指令的速度,一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。,假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：,T(n)=O(f(n),称T(n)为算法的(渐近)时间复杂度。,如何估算算法的时间复杂度？,算法=控制结构+原操作（固有数据类型的操作）,算法的执行时间=原操作(i)的执行次数原操作(i)的执行时间,算法的执行时间与原操作执行次数之和成正比,从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。,voidmult(inta,intb,intc)for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;/for/mult,基本操作:乘法操作,时间复杂度:O(n3),例1,例+x;s=0;将x自增看成是基本操作，则语句频度为1，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为(1)，即常量阶。例for(i=1;i=n;+i)+x;s+=x;语句频度为：n其时间复杂度为：O(n)即时间复杂度为线性阶。,i=0:赋值次,i=1:赋值2次,i=2:赋值3次,i=n-1:赋值n次,.,1+2+3+n=(1+n)n/2=n2/2+n/2,例for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;语句频度为：n2其时间复杂度为：O(n2)即时间复杂度为平方阶。例for(i=0;ixn，所以：,|an|*|xn|+|an-1|*|xn-1|+|a1|*|x1|+|a0|*|x0|an|*|xn|+|an-1|*|xn|+|a1|*|xn|+|a0|*|xn|,=(|an|+|an-1|+|a1|+|a0|)|xn|=c|xn|其中：n0=1,c=|an|+|an-1|+|a1|+|a0|,g(n)=xn,一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。,以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：O(2n)=i-1;j-)/第i个元素（下标为i-1)开始L.dataj+1=L.dataj;/顺序后移L.datai-1=x;L.length+;,memcpy(目的地址,源地址，字节数）memset(目的地址,字符，字节数）,inta5050,b5050;,a清0for(i=0;i50;i+)for(j=0;j50;j+)aij=0;,拷贝：for(i=0;i最坏情况，,a1，ai-1，ai，an,算法的平均移动由于插入可能在表中任何位置上进行，在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。Pi代表在第i个位置插入概率，则Eis(n)=p1n+p2(n-1)+.+pn1+pn+10若表中任何位置(1in+1)上插入结点的概率是均等的，则p1=p2=p3=pn+1=1/(n+1)因此，在等概率插入的情况下：Eis(n)=1/(n+1)n+(n-1)+1+0=n/2,a1，ai-1，ai，an,结论：在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。2、删除线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表：(a1，ai-1，ai，ai+1，an)变成长度为n-1的线性表(a1，ai-1，ai+1，an),voiddeleteList(L,i)/表L中删除第i个元素if(iL.length)cout“删除序号错”ch;while(ch!=$)p=newLNode;pdata=ch;pnext=h;h=p;cinch;returnh;,#includestructLNodechardata;LNode*next;LNode*CreateList()charch;LNode*h,*p;h=NULL;cinch;while(ch!=$)p=newLNode;pdata=ch;pnext=h;h=p;cinch;returnh;voidCreateList1(LNode*,cinch;while(ch!=$)p=newLNode;pdata=ch;pnext=h;h=p;cinch;voidprint(LNode*h)LNode*p=h;while(p!=NULL)coutdatanext;coutch;while(ch!=$)p=newLNode;pdata=ch;if(head=NULL)head=p;,elser-next=p;r=p;cinch;if(r!=NULL)r-next=NULL;returnhead;,头结点（哨兵结点）引入：增加一个表头结点，数据域可根据需要使用或不用。,特点：a、表中第一个结点和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点。因此空表和非空表的处理统一。,head,有头结点的空表,LNode*creat()LNode*r,*h;charch;h=newLNode;r=h;cinch;,while(ch!=$)r-next=newLNode;r=r-next;r-data=ch;cinch;r-next=NULL;returnh;,上述算法里动态申请新结点空间时未加错误处理，在实际使用时间，可作下列判定与处理：p=newLNode;if(p=NULL)错误处理；,二、查找运算1、按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0个结点，其算法如下：,LNode*getnode(head，i)/i1/在链表head中取第i个数据，链表有头结点p=head;j=0;/计数用while(pnext,2、按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：,LNode*locatenode(head，key)p=headnext;while(p,该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找。,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,p-next=q;,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,p-next=q;,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q-next=p-next;,p-next=q;,定位ai-1并将指针p指向它；,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q=newLNode;q-data=x;q-next=p-next;p-next=q;,定位ai-1并将指针p指向它；,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,q=newLNode;q-data=x;q-next=p-next;p-next=q;,p=getnode(head，i-1);,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化,三、插入运算,voidinsertnode(head，x，i)LNode*p，*q;p=getnode(head，i-1);if(p=NULL)coutdata=x;qnext=pnext;pnext=q;,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,问题：链表的逻辑结构已正确了，但结点ai空间丢了。,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,r=p-next;p-next=r-next;deleter;,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,r=p-next;p-next=r-next;deleter;,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,r=p-next;p-next=r-next;deleter;,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,p=getnode(head，i-1);r=p-next;p-next=r-next;deleter;,四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,四、删除运算,voiddeletelist(head，i)LNode*p，*r;p=getnode(head，i-1);if(p=NULL|pnext=NULL)returnERROR;r=pnext;pnext=rnext;deleter;,从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。,作业：（1）链表是有序的，现在插入数据x，要求插入后仍然有序（2）链表是有序的，现在删除数据x，若x不存在，输出一段提示信息。要求：按链表有头结点和无头结点两种情况分别写出并上机调试通过。（3）链表逆转（没有头结点）,五、静态链,1、静态链表的概念用一维数组来实现线性链表，这种用一维数组表示的线性链表，称为静态链表。静态：体现在表的容量是一定的。（数组的大小）链表：插入与删除同前面所述的动态链表方法相同2、静态链表的类型定义,#defineMAXSIZE1000/链表的最大长度structComponentElemTypedata;intcur;ComponentVListMAXSIZE;,SLinkList类型的数组变量是结构数组，每一数组分量包括两个域：data：用于存储线性表元素；cur：用于存储直接后继元素在数组中的位置,静态链表图示,0,h=5,数组下标,线性链表图示,地址,1,2,3,4,5,6,7,8,9,10,h=1020,例：静态链表的操作设插入和删除只在表的头上进行（栈）,h=7（5，7，2，3）,（8，5，7，2，3）,h=0,表中加入x,01234,7,9,3,-1,5,1,2,3,5678910,2.(1)VListi.data=x;,1.在VList中找空位置i(比如0),(2)VListi.cur=h;,x,7,(3)h=i;,空位置的标识：将所有空位置构成链表，用av表示链首,av=0,删除：,if(h!=-1)x=VListh.data;i=h;h=VListi.cur;VListi.cur=av;av=i;,h=7,空表初始化：,开始，表是空的，所以：for(i=0;inextnext和rear，显然，查找时间都是O(1)。因此，实际中也常采用尾指针表示单循环链表.。,由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。,2.3.3双向链表双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：structDuLNodedatatypedata;DuLNode*prior，*next;,结点,存储前趋结点的地址,存储数据元素,存储后继结点的地址,双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：ppriornext=p=pnextprior,双向链表结点p前的插如数据x的操作：,p,x,q=newDuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;,双向链表结点p前的插如数据x的操作：,p,x,q=newDuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;,双向链表结点p前的插如数据x的操作：,p,x,q=newDuLNode;q-data=x;q-prior=p-prior;q-next=p;p-prior-next=q;p-prior=q;,ppriornext=pnext;pnextprior=pprior;deletep;,p,删除p指针所指的结点：,ppriornext=pnext;pnextprior=pprior;deletep;,p,删除p指针所指的结点：,ppriornext=pnext;pnextprior=pprior;deletep;,p,删除p指针所指的结点：,双向链表的插入、删除灵活；链表维护的工作量大，所需的存储空间较大。,24一元多项式的表示及相加,Pn(x)=pnxn+pn-1xn-1+p1x+p0Qm(x)=qmxm+qm-1xm-1+q1x+q0,一、一元多项式的表示多项式的操作是表处理的典型用例。数学上,一元多项式可按降幂写成：（指数为正整数的情况）,其中：pn、qm不为0,存储结构：用线性链表表示。增加头结点，每个结点有coef:系数exp指数next：指针其中，头结点的exp为-1。,多项式A(x)=5x17+9x8+3x+7,例：求两多项式的和多项式A(x)=5x17+9x8+3x+7B(x)=9x8+22x7+8x,二、一元多项式的相加算法,一元多项式相加运算规则：指数相同的项系数相加,A(x)B(x)相加的和多项式为C(x)=A(x)+B(x)=5x17+22x7+11x+7,设多项式A(x)，B(x)分别用带表头结点的线性链表ha,hb表示,完成:ha=ha+hb,一元多项式加法算法主要步骤分别对两个链表ha、hb进行扫描，设工作指针pa、pb分别指向两个多项式当前进行比较的结点，q指针指向pa的前驱，初始：q=ha;pa=ha-next;pb=hb-next;若pa,pb都不为空：则比较两者指数：pa-exppb-exp：q,pa后移；pa-exp=pb-exp：将pb所指结点的系数“加”到pa所指结点的系数上；若和为0，则pa所指结点删除。q,pa,pb调整pa-expexp：从表hb中复制pb所指结点的coef,exp，并将其插入到ha表pa所指结点之前；,若pb不空：hb表中从pb开始的结点插入到ha表尾上,intcomp(inta,intb)if(ab)return-1;if(a=b)return0;elsereturn1;PloyAdd(ha,hb)q=ha;pa=ha-next;pb=hb-next;while(pa!=NULL,r-coef=pb-coef;r-exp=pb-exp;q-next=r;r-next=pa;q=r;pb=pb-next;break;while(pb!=NULL)r=newNode;r-coef=pb-coef;r-exp=pb-exp;q-next=r;r-next=pa;q=r;pb=pb-next;,while改成：while(pb!=hb),在改成循环链后，此while可省去。,1、线性表v的数据递增有序，试将x插入表中并保持有序性（1）表顺序表示（2）链表表示（3）带有头结点的链表2、写一个线性表的转置算法（顺序和链表表示两种情况）（a1,a2,.,an)变为（an,an-1,.,a1),3、写一个类（用模板）实现顺序表示的线性表。templateclassLiT*p;intlen;intmax;public:.,实习题目：hc=ha*hb要求：（1）输入形式：以系数指数的递减序输入，最后以00结束（2）输出，见格式例：5x9-7x2+6x-5输入为：输出为：,9-721000,5X9-7X2+6X-5,已知一个带有表头结点的单链表，结点结构为,假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为整数）。若查找成功，算法输出该结点的data域的之，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C+或JAVA语言实现），关键之处请给出简要注释。（2009年研究生入学试题，15分）,find(p,data,k)/p-链表头指针，k-倒数的值,d-返回值count=0;q=p-next;p1=p;while(q)if(+countk)p1=p1-next;q=q-next;if(p1=p)return0;d=p1-data;return1;,设将n(n1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p(0pn)个位置，即将R中的数据由（x0,x1,xn-1）变换为（xp,xp+1,xn-1,x0,x1,xp-1）。要求：（1）给出算法的基本思想。（2）根据设计的思想，采用C或C+或JAVA语言描述算法，关键之处给出注释。（3)说明你所设计算法的时间复杂度和空间复杂度.(2010年研究生入学考试，13分),算法思想将x0,x1,xn-1原地转置，形成xn-1,xp,xp-1,x0，时间显然是O(n),后面将前n-p个和后p个元素转置，形成xp,xp-1,xn-1,x0,x1,xp-1。这部分时间显然也是O(n),所以总时间是O(n)。实现时可以写一个转置函数re(r,l,h),其中，r为数组，l,h为范围（ln;while(n)push(s,n%8);n=n/8;while(!Stackempty(s)pop(s,e);coute;,3.2.2括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,3.2.3行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。,出口,3.2.4迷宫求解入口,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,3.2.4迷宫求解,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径，继续前进;,若当前位置“不可通”，则后退，换方向继续探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,设定初值为入口位置,以正东为起始方向；doif(当前位置可通)则将当前位置插入栈顶；if(该位置是出口位置)exit(0)；else按顺时针下一方向为新的当前位置；else.while(栈不空）；,求迷宫中一条从入口到出口的路径的算法：,若栈空，则表明迷宫没有通路。,if(栈不空,2）运算符的相对次序不同;,例如:exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+,结论:,3）中缀式丢失了括弧信息，致使运算的次序不确定;,例如:exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+,结论:,4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;,例如:exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+,结论:,5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。,如何从后缀式求值？,先找运算符，再找操作数,例如：abcde/f+,ab,d/e,c-d/e,(c-d/e)f,ab-(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。,分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f,从原表达式求得后缀式的规律为：,1)设立运算符栈,2)设表达式的结束符为“#”，预设运算符栈的栈底为“#”,3)若当前字符是操作数，则直接发送给后缀式,4)若当前运算符的优先数高于栈顶运算符，则进栈,5)否则，退出栈顶运算符发送给后缀式；,7)遇表达式结束“#”，连续将栈中运算符退到后缀式。,6)“(”对它之前后的运算符起隔离作用，可理解为优先级最低的运算符号，进栈；“)”可视为自相应左括弧开始的表达式的结束符。一直退到栈顶是“(”（符号送后缀式），最后“（”退栈。,ab+(cd/e)f#,#,栈,后缀表达式：,ab+(cd/e)f#,#,栈,后缀表达式：,ab+(cd/e)f#,#,a,后缀表达式：,栈,ab+(cd/e)f#,#,a,后缀表达式：,栈,ab+(cd/e)f#,#,a,后缀表达式：,栈,ab+(cd/e)f#,#,a,b,后缀表达式：,栈,ab+(cd/e)f#,#,a,b,后缀表达式：,栈,ab+(cd/e)f#,#,a,b,后缀表达式：,栈,ab+(cd/e)f#,#,a,b,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,后缀表达式：,栈,ab+(cd/e)f#,#,栈,a,+,b,（,后缀表达式：,ab+(cd/e)f#,#,栈,a,+,b,（,后缀表达式：,ab+(cd/e)f#,#,栈,a,+,b,（,c,后缀表达式：,ab+(cd/e)f#,#,a,+,b,（,c,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,/,e,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,/,e,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,e,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,e,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,（,c,d,e,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,c,d,e,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,c,d,e,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,c,d,e,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,c,d,e,/,后缀表达式：,栈,ab+(cd/e)f#,#,a,+,b,c,d,e,/,f,后缀表达式：,栈,ab+(cd/e)f#,#,栈,a,+,b,c,d,e,/,f,后缀表达式：,ab+(cd/e)f#,#,栈,a,+,b,c,d,e,/,f,后缀表达式：,ab+(cd/e)f#,#,栈,a,b,c,d,e,/,f,+,后缀表达式：,ab+(cd/e)f#,栈,a,b,c,d,e,/,f,+,后缀表达式：,第二种实现:用两个栈运算符栈操作数栈,3.2.6、实现递归,将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回！,例如：voidmain()voida()voidb()a();b();/main/a/b,main的数据区,函数a的数据区,函数b的数据区,3.3队列3.3.1队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an，也就是说队列的修改是依先进先出的原则进行的。,出队,入队,队头,队尾,