您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 经营企划 > 考研数据结构,各种算法的经解分析
第一章◆数据:指能够被计算机识别、存储和加工处理的信息载体。◆数据元素:就是数据的基本单位,在某些情况下,数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。◆数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。在高级语言程序中又分为:非结构的原子类型和结构类型◆抽象数据类型(ADT):是指一个数学模型以及定义在该模型上的一组操作。一个抽象的数据类型的软件模块通常包含定义和表示和实现用三元组(D,S,P):数据对象、数据关系、基本操作◆数据结构:指的是数据之间的相互关系,即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。◆逻辑结构:指各数据元素之间的逻辑关系。◆存储结构:就是数据的逻辑结构用计算机语言的实现。◆线性结构:数据逻辑结构中的一类,它的特征是若结构为非空集,则该结构有且只有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。◆非线性结构:数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个直接前趋和直接后继。常用的存储表示方法有四种:◆顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。◆链接存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。◆索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。◆散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。渐近时间复杂度的表示法T(n)=O(f(n)),这里的O是数学符号,它的严格定义是若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常数C和n0,使得当n≥n0时都满足0≤T(n)≤C·f(n)。用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时,两者的比值是一个不等于0的常数。这么一来,就好计算了吧。求某一算法的时间复杂度是关于N的统计,下面的例子很有反面意义x=91;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;◆T(n)=O(1)◇这个程序看起来有点吓人,总共循环运行了1000次,但是我们看到n没有?没。◇这段程序的运行是和n无关的,就算它再循环一万年,我们也不管他,只是一个常数阶的函数。算法的时间复杂度仅与问题的规模相关吗?◆No,事实上,算法的时间复杂度不仅与问题的规模相关,还与输入实例中的元素取值等相关,但在最坏的情况下,其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时,一般就是以最坏情况下的时间复杂度为准的。增长率由小至大的顺序排列下列各函数:2^100,(2/3)^n,(3/2)^n,n^n,,n!,2^n,lgn,n^lgn,n^(3/2)◇分析如下:2^100是常数阶;(2/3)^n和(3/2)^n是指数阶,其中前者是随n的增大而减小的;n^n是指数方阶;√n是方根阶,n!就是n(n-1)(n-2)...就相当于n次方阶;2^n是指数阶,lgn是对数阶,n^lgn是对数方阶,n^(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下:◆(2/3)^n2^100lgn√nn^(3/2)n^lgn(3/2)^n2^nn!n^n算法:是对特定的问题求解步骤地一种描述,是指令的有限序列。有五个基本的特性有穷性、确定性、可行性、输入、输出确定性:每条指令不能有二义性,对于同样的输入有同样的输出可行性:算法中所用到的操作都是已经实现的基本运算或通过有限次能实现的输入:有0个或多个输入输出:有一个或多个输出设计算法的要求(追求的目标)正确性、可读性、健壮性、效率与低存储量需求算法原地工作:当空间复杂度为O(1)时,称算法为就地工作(原地工作)。多型数据类型:是指其值的成分不确定的数据类型。从抽象数据类型的角度看,具有相同的数学抽象特性,故称之为多型数据类型。数据结构是一门研究什么内容的学科?研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等学科对于一个数据结构,一般包括哪三个方面的讨论?数据的逻辑结构、存储结构和数据的运算。逻辑结构有线形结构(1),树型结构(2),(3)网状结构,集合(4)_四种。平方和公式:n2222....321=n*(n+1)*(2n+1)/6斐波那契数列计算的时间复杂度是O(n)第二章循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点),形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1),不用遍历整个链表了。判别链表终止的条件也不同于单链表,它是以指针是否等于某一指定指针如头指针或尾指针来确定。何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答:在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几方面的考虑:1.基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;反之,若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。第三章例如:Exp=a*b+(c-d/e)*f若Exp=a*b+(c-d/e)*f则它的前缀式为:+*ab*-c/def中缀式为:a*b+c-d/e*f后缀式为:ab*cde/-fx+综合比较它们之间的关系可得下列结论:1.三式中的“操作数之间的相对次序相同”;(二叉树的三种访问次序中,叶子的相对访问次序是相同的)2.三式中的“运算符之间的的相对次序不同”;3.中缀式丢失了括弧信息,致使运算的次序不确定;(而前缀和后缀运算只需要一个存储操作数的栈,而中缀求值需要两个栈,符号栈和操作数栈)4.前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5.后缀式的运算规则为:·运算符在式中出现的顺序恰为表达式的运算顺序;·每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;6.中缀求值的运算规则:如果是操作数直接入栈。如果是运算符。这与当前栈顶比较。个如果比当前栈顶高,则入栈,如果低则说明当前栈顶是最高的必须把他先运算完了。用编译原理的话就是说当前栈顶已经是最左素短语了)其实中缀表达式直接求值和把中缀表达式转化成后缀表达式在求值的过程惊人的相似,只不过是直接求值是求出来,而转化成后缀是输出来。中缀表达式直接求值算法:OPNDTypeEvalueExpression(){//OPTR和OPND分别为运算符栈和操作数栈InitStack(OPTR);Push(OPTR,’#’);InitStack(OPND);c=getchar();While(c!=’#’||GetTop(OPTR)!=’#’){If(!IN(c,OP))//如果是操作数,直接入操作数栈{push(OPND,c);c=getchar();}Else//如果是运算符,则与当前的栈顶比较{Switch(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}//else}//whildReturnGetTop(OPND);//操作数栈中最后剩下的就是整个表达式的结果了。}中缀表达式转化成后缀表达式算法voidtrans-post(charE[n],charB[n])//中、后缀表达式转换//{//E[n]是中缀表达式、B[n]是后缀表达式存储的空间inti=0,j=0;charx;stypeS;Clearstack(S);Push(S,‘#’);//‘#’入栈//do{x=E[i++];//扫描当前表达式分量//if(x=‘#’)//到了中缀表达式最后了while(!Emptystack(S))//全部退栈,#和#是优先级最低的,B[j++]==pop(S);//所以当前栈的所有运算都要规约//输出栈顶运算符,并退栈直到遇见栈底的开始放进去的那个#//elseif(isdigit(x))B[j++]=x;//操作数直接输出//elseif(x=‘)’)//遇到)那么就一定要找到({while(Getstop(S)!=‘(’)B[j++]=pop(S);//输出栈顶,并退栈//pop(S);//退掉‘(’//}else//x为运算符//{while(precede(Getstop(S),x))//栈顶(1)与x比较//B[j++]=pop(S);//1=x时,输出栈顶符并退栈//Push(S,x);//1x时x进栈//}}while(x!=’#’);B[j]=’#’;}//置表达式结束符//双端队列:两端都可以插入和删除,但实际应用中通常是输出受限的双端对列和输入受限的双端队列输入受限的双端队列指的是:一端可以输入输出另一端只能输出不能输入输出受限的双端队列指的是:一端可以输入输出另一端只能输入不能输出求从迷宫入口到出口的一条最短路径要用到队列,因为队列可以用在广度优先中,队列中的元素表示离中心点依次越来越远。所以第一次找到出口肯定是半径最短的。链式栈:链式队列:N个结点的不同二叉树有:CCCnnnnnnn212211等于不同的进出栈总数a0^a1top……Anfrontrearq头a0an-1^有n个数顺序(依次)进栈,出栈序列有Cn种,Cn=[1/(n+1)]*(2n)!/[(n!)*(n!)]。=尾递归和单向递归的消除不需要借用栈单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程。证明:若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着ijk,使PjPkPi。ij若PiPj说明小的先于大的数出栈,那么也就是Pi出栈在Pj入栈前面若PiPj说明大的数先于小的数出栈,那么在Pi出栈前Pj一定在栈中证明:1)jk且PjPk说明Pj出栈在Pk入栈的前面;2)ik且PiPk说明Pi出栈前,Pk在栈中3)ij且PiPj说明Pi出栈前Pj在栈中而Pi是最先出栈的那么在Pi为栈顶的时候,Pj和Pk一定都同时被压入栈中,那么就与1矛盾了,1要求Pj要在Pk入栈前出栈,而此时PkPj都在栈中所以假设不成立。用两个栈来模拟一个队列栈的特点是后进先出,队列的特点是先进先出。所以,用两个栈s1和s2模拟一个队列时,s1作输入栈,逐个元素压栈,以此模拟队列元素的入队。当需要出队时,将栈s1退栈并逐个压入栈s2中,s1中最先入栈的元素,在s2中处于栈顶。s2退栈,相当于队列的出队,实现了先进先出。显然,只有栈s2为空且s1也为空,才算是队列空。第四章KMP算
本文标题:考研数据结构,各种算法的经解分析
链接地址:https://www.777doc.com/doc-6314708 .html