数据结构需要掌握的算法

为了便于比较同一问题的不同算法,通常从算法中选取一种对于所研究的问题来说是基本运算的原操作(以下将基本运算的原操作简称为基本运算)。算法执行时间大致为基本运算所需的时间与其运算次数(也称为频度)的乘积。被视为算法基本运算的一般是最深层循环内的语句。在一个算法中,进行基本运算的次数越少,其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多。所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作：T(n)=O(f(n))记号“O”读作“大O”,它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。也就是只求出T(n)的最高阶,忽略其低阶项和常系数,这样既可简化T(n)的计算,又能比较客观地反映出当n很大时,算法的时间性能。例如,T(n)=3n2-5n+10000=O(n2)一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1),也称作常数阶一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。各种不同数量级对应的值存在着如下关系：O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)本质上讲，是一种最高数量级的比较例1.8求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。#defineMAX20/*定义最大的方阶*/voidmatrixadd(intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]){inti,j;for(i=0;in;i++)for(j=0;jn;j++)C[i][j]=A[i][j]+B[i][j];}该算法中的基本运算是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j],分析它的频度,即：T(n)==O(n2)102101010*11ninininjnnnnn例分析以下算法的时间复杂度。intfun(intn){inti,j,k,s;s=0;for(i=0;i=n;i++)for(j=0;j=i;j++)for(k=0;k=j;k++)s++;return(s);}基本语句或基本操作该算法的基本操作是语句s++,其频度：T(n)==O(n3)则该算法的时间复杂度为O(n3)。niijjk0001习题1.5（3）分析以下算法的时间复杂度voidfunc(intn){inti=0,s=0;while(sn){i++;s=s+i;}}基本语句解：对于while循环语句，设执行的次数为m，i从0开始递增1，直到m为止，有：s=0+1+2+…+m-1=m(m-1)/2，因s=m(m-1)/2n，则有m＜T(n)=O()例1.10有如下算法：voidfun(inta[],intn,intk)/*数组a共有n个元素*/{inti;if(k==n-1)for(i=0;in;i++)printf(%d\n,a[i]);else{for(i=k;in;i++)a[i]=a[i]+i*i;fun(a,n,k+1);}}调用上述算法的语句为fun(a,n,0)，求其时间复杂度。解：设fun(a,n,0)的时间复杂度为T(n),则fun(a,n,k)的执行时间为T1(n,k)，由fun()算法可知：T1(n,k)=n当k=n-1时T1(n,k)=(n-k)+T1(n,k+1)其他情况则T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=…=n+(n-1)+…+2+T1(n,n-1)=n+(n-1)+…+2+n=O(n2)所以调用fun(a,n,0)的时间复杂度为O(n2)。1.建立单链表先考虑如何建立单链表。假设我们通过一个含有n个数据的数组来建立单链表。建立单链表的常用方法有如下两种:(1)头插法建表从一个空表开始读取字符数组a中的字符,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止adcbi=0i=1i=2i=3∧head采用头插法建立单链表的过程heada∧headda∧headcda∧headbcda∧第1步:建头结点第2步:i＝0,新建a结点,插入到头结点之后第3步:i＝1,新建d结点,插入到头结点之后第4步:i＝2,新建c结点,插入到头结点之后第5步:i＝3,新建b结点,插入到头结点之后(2)尾插法建表头插法建立链表虽然算法简单,但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致,可采用尾插法建立。该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下:bcdai=0i=1i=2i=3head头结点adcb∧b采用尾插法建立单链表的过程插入结点示意图………p…∧∧s(a)插入前…p…∧s(b)s-next=p-next…p∧s(c)p-next-prior=s…p…s(d)s-prior=p…ps(e)p-next=s…p…s(f)插入后双链表中插入结点示意图归纳起来,在双链表中p所指的结点之后插入一个*s结点。其操作语句描述为:s-next=p-next;/*将*s插入到*p之后*/p-next-prior=s;s-prior=p;p-next=s;删除结点示意图在双链表中删除一个结点的过程如右图所示:归纳起来,删除双链表L中*p结点的后续结点。其操作语句描述为:p-next=q-next;q-next-prior=p;另外一种思路：p-next-next-prior=p;p-next=p-next-next;此算法必须使用两个指针。例3.1设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。答:所有可能的出栈次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba例3.2设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是。(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。例3.3已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。(A)i(B)n-i(C)n-i+1(D)不确定答:当p1=n时,输出序列必是n,n-1,…,3,2,1,则有:p2=n-1,p3=n-2,…,pn=1推断出pi=n-i+1,所以本题答案为C。例3.4设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值。(A)一定是2(B)一定是1(C)不可能是1(D)以上都不对答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,…,n,但一定不能是1。所以本题答案为C。3.1.4栈的应用例子:表达式求值这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如：1+2*3就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算xopy之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组str中,其后缀表达式存放在字符型数组exp中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组op作为栈。将算术表达式转换成后缀表示的方法如下:while(从exp读取字符ch,ch!='\0'){若ch为数字,将后续的所有数字均依次存放到postexp中,并以字符“#”标志数值串结束。若ch为左括号“(”,则将此括号进栈到运算符栈op中。若ch为右括号“)”,则将运算符栈op中左括号“(”以前的运算符依次出栈并存放到postexp中,然后将左括号“(”删除。若ch运算符优先级小于或等于op栈顶运算符的优先级(除栈顶运算符为“(”外)的优先级,则依次出栈并存入到postexp中,然后将ch进栈。}若字符串exp扫描完毕,则将运算栈op中的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。中缀表达式后缀表达式对于表达式“(56-20)/(4+2)”,其转换成后缀表达式的过程如下：exp操作过程oppostexp(56-20)/(4+2)遇到ch为“(”,将此括号进栈op。(56-20)/(4+2)遇到ch为数字,将56存入postexp中,并插入一个字符“#”。(56#-20)/(4+2)遇到ch为“-”,由于op中“(”以前没有字符,则直接将ch进栈op中。(-56#20)/(4+2)遇到ch为数字,将20#存入数组exp中。(-56#20#exp操作过程oppostexp)/(4+2)遇到ch为“)”,则将栈op中“(”以前的字符依次出栈并存入postexp中,然后将“(”删除。56#20#-/(4+2)遇到ch为“/”,将将ch进栈op中。/56#20#-(4+2)遇到ch为“(”,将此括号进栈op中。/(56#20#-4+2)遇到ch为数字,将4#存入数组postexp中。/(56#20#-4#exp操作过程oppostexp+2)遇到ch为“+”,由于op栈顶运算符为“(”,则直接将ch进栈op中。/(+56#20#-4#2)遇到ch为数字,将2#存入postexp中。/(+56#20#-4#2#)遇到ch为“)”,则将栈op中“(”以前的字符依次出栈并存放到postexp中,然后将“(”出栈。/56#20#-4#2#+str扫描完毕,则将栈op中的所有运算符依次弹出并存放到postexp中,得到后缀表达式。56#20#-4#2#+/注:操作栏中,在以下选项中选择填入A:进栈;B:存入后缀表达式中,并插入字符#;C:将栈中“(”后面的字符依次出栈并存入后缀表达式中,将“(”删除;D:将栈中的所有字符依次出栈并存入后缀表达式中处理字符操作运算栈后缀表达式处理字符操作运算栈后缀表达式下面对后缀表达式求值。在后缀表达式求值算法中要用到一个数值栈st,该算法实现过程如下:后缀表达式存放在字符型数组exp中,从头开始依次扫描这个后缀表达式,当遇到运算数时,就把它插入到数值栈st中；当遇到运算符时,就执行两次退栈,并根据该运算符对退栈的数值进行相应的运算,再把结果入栈st。重复上述过程,直至后缀表达式exp扫描完毕,此时数值栈st中栈顶的数值即为表达式的值。while(从postexp读取字符ch,ch!='\0'){若ch为数字,将后续的所有数字构成一个整数存放到数值栈st中。若ch为“+”,则从数