徐士良《计算机软件技术基础》（第4版）笔记和课后习题详解

目录内容简介目录第1章预备知识复习笔记课后习题详解第2章基本数据结构及其运算复习笔记课后习题详解第3章查找与排序技术复习笔记课后习题详解第4章资源管理技术4.1复习笔记42课后习题详解第5章数据库设计技术复习笔记课后习题详解第6章编译技术概述复习笔记课后习题详解第7章应用软件设计与开发技术复习笔记课后习题详解第1章预备知识1.I复习笔记ー、集合基本概念集合是指若干个或无穷多个具有相同属性的元(元素)的集体。通常,ー个集合名称用大写字母表示,而集合中的某个元素用小写字母表示。如果集合M由n(n>0)个元素a“&，…，a”组成,则称集合M为有限集。如果ー个集合中有无穷多个元素,则称此集合为无限集。不包括任何元素的集合称为空集。空集通常用①表示。如果M是ー个集合,a是集合M中的一个元素,则记作aGM,称元素a属于集合M;如果a不是集合M中的元素,则记作a£M,称元素a不属于集合M。(1)列举法用列举法表示一个集合是将此集合中的元素全部列出来，或者列出若干项但能根据规律可知其所有的元素。例如:大于1而小于100的所有整数的集合A可以表示为A={2,3,4,...,99}(2)性质叙述法用性质叙述法表示一个集合是将集合中的元素所具有的属性描述出来。例如:大于1而小于100的所有整数的集合A可以表示为A={a|l<a<10()的所有整数}设M与N为两个集合,若M中的每个元素也为N的元素，则称M为N的子集,记作MUN,若MUN且N中至少有一个元素a£M,则称M为N的真子集，记作MuN。基本运算(1)两个集合的并设有两个集合M和N,它们的并集记作MUN,定义如下：MUN={a|aCM或a£N}(2)两个集合的交设有两个集合M和N,它们的交集记作MAN,定义如下:MDN={a|aWM且aGN}两个集合M和N的并、交均满足交换律,即MUN=NUMMnN=NDM(3)两个集合的差设有两个集合M和N,它们的差集记作M-N,定义如下:M-N={a|aCNHlla£N}两个集合的差不满足交换律,即M-N声N-M对于集合的并、交、差有以下几点基本性质:①结合律(acib)nc=An(Bnc)

(AUB)UC=AU(BUC)

②分配律

AD(BUC)=(ACIB)U(AClC)

AU(Bnc)=(AUB)n(AUC)(A-B)U<B-A)=(AUB)-(AnB)BCKA-B)=0(AAB)U(A-B)=A③其他(4)映射映射的相关概念如下:①设A、B是两个非空集，如果根据一定的法则f,对于每ー个xGA,在B中都有唯一确定的y与之对应，则称f为定义在A上而在B中取值的映射,记作f：A—B,并将x与y的关系记作y=f(x),x称为自变元,y称为在f作用下x的像;②设给定映射f：A-B,且B=f(A),若对于每个yCB仅有唯一的xWA使f(x)=y,则称隋逆映射「;③若A、B两个集合有ーー映射帝在,使f(A)=B,则称A与B成——对应,A与B对等,记作A〜B。集合的对等具有以下性质:自反性:A〜A；对称性:若A〜B,则B〜A；传递性：若A〜B且B〜C,则A〜C。自然数集与数学归纳法由所有自然数组成的集合{1,2,3,…}称为自然数集。自然数集是一个无限集。由自然数组成的集合均是自然数集的子集。自然数集的子集可以是有限集,也可以是无限集。它们具有如下性质:(1)在自然数集的任一非空子集M中,必定有一个最小数;(2)设M是由自然数形成的集合,如果它含有1,2,...,k,并且当它含有数n-1,n-2,...,n-k(n>k)时,那么它含有所有的自然数，即M是自然数集。笛卡儿积0!xD2X•••XD„={(ム,ム,…,ム)Id,eD,U=1,2,…,”}设有n个集合D“D2,...,D„,此n个集合的笛卡儿积定义为其中(4, d„)称为n元组,d称为n元组的第i个分量。由笛卡儿积的定义可以看出,n个集合的笛卡儿积是以n元组为元素的集合,而每ー个n元组中的第i个分量取自于第i个集合D,。•二元关系(1)笛卡儿积设M和N是两个集合,则其笛卡儿积MxN={(x,y)|xGN^yGN)其中每ー个子集称为在MxN上的ー个二元关系。如果M=N,则其笛卡儿积MxM={(x,y)Ix,y£M}其中每ー个子集称为在集合M上的ー个二元关系,简称为在集合M上的一个关系。(2)前后件、自反、对称与传递设R是集合M上的一个关系：①如果(a,b)GR1则称a是b的关于R的前件,b是a的关于R的后件;②如果对于每ー个aCM,都有(a,a)CR,则称关系R是自反的:如果对于任何a^M,(a,a)GR均不成立,则称关系R是非自反的；③如果（a,b）CR时必有（b,a）GR,则称关系R是对称的;④如果当（a,b）WR且（b,c）eR时必有（a,c）eR,则称关系R是传递的。（3）基与传递体设R是M上的ー个传递关系,且TUR,若对于任何（x,y）GR,在M中有元素x。,x.,x2,x„（n>l）满足:Xo=X;xn=y；③（x»Xi）GT（i=l,2,n）则称关系T是关系R的基,又称关系R是关系T的传递体。基本概念算法是指解题方案准确而完整的描述。算法具有如下基本特征:（1）能行性算法的能行性包括以下两个方面:①算法中的每ー个步骤必须能够实现;②算法执行的结果要能够达到预期的目的。（2）确定性算法的确定性,是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释,也不允许有多义性。（3）有穷性算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。算法的有穷性还应包括合理的执行时间的含义。（4）拥有足够的情报ー个算法是否有效,还取决于为算法所提供的情报是否足够。综上所述，算法是ー组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数内终止。基本方法（1）列举法列举法的基本思想是:根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会很大,因此需要对算法进行优化。(2)归纳法归纳法的基本思想是,通过列举少量的特殊情况,经过分析，最后找出一般的关系。(3)递推法递推法是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。(4)递归法递归法的基本思想是在解决了逐层分解到最后的那些最简单的问题后,再沿着原来分解的逆过程逐步进行综合。递归分为直接递归与间接递归两种。如果ー个算法P显式地调用自己则称为直接递归。如果算法P调用另ー个算法Q,而算法Q又调用算法P,则称为间接递归调用。(5)分治法(减半递推技术)分治法,即对问题分而治之。工程上常用的分治法是减半递推技术。"减半’’是指将问题的规模减半,而问题的性质不变。"递推''是指重复"减半''的过程。(6)回溯法通过对问题的分析,找出ー个解决问题的线索，然后沿着这个线索逐步试探。对于每ー步试探,若试探成功,就得到问题的解;若试探失败,就逐步回退，换别的路线再进行试探。复杂度分析算法的复杂度主要包括时间复杂度和空间复杂度。(1)时间复杂度①定义算法的时间复杂度是指执行算法所需要的计算工作量。客观地反应算法的效率可以用算法在执行过程中所需基本运算的执行次数来度量算法的エ作量。而算法所执行的基本运算次数是问题规模的函数,即算法的工作量f(n)。其中n是问题的规模。②方法在同一问题规模下,如果算法执行所需的基本运算次数取决于某ー特定输入时,可以用以下两种方法来分析算法的工作量。a.平均性态平均性态分析是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。设X是所有可能输入中的某个特定输入，P(X)是X出现的概率，t(X)是算法在输入为X时所执行的基本运算次数,则算法的平均性态定义为A(n)=/pェwd”b.最坏情况复杂性W(打)=max{^(x)}了《カ最坏情况分析是指在规模为n时,算法所执行的基本运算的最大次数。它定义为:(2)空间复杂度ー个算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数,则称该算法是原地工作的。1.2课后习题详解集合M={d”d2>d3»ム,ds,4}上的一个关系R如下:R={(di,d2),(d2,d&),(d5,d4),(di,d5),(di,th),(di,d6),(di,d3),(d3,d6)}试验证Ti={(d,,d2),(d2,0(),(di,d3),(&,&),(d5,&),(di,d5)}是R的具有6个元素的基,而T2={(d2,d4),(di,d3),(di,d2),(ds,ds)}不是R的基。答:对于T”显然满足T£R,且对于关系R中的每一个二元组(x,y),在M中存在元素RX0，よ］，よ2（ム,ム）d\,dz(di,dz)£Ti(dz, )dz9d4（ム,ム）6%（ds,ム）d$9d4（む,ム）6。(dltd5)di0,4)£Ti(dt,d.)d\9dz,d\(.d\ydz)»Cdz,d&)WT]（ム,ム）（ム,む），（ム,ム）er（ム,&）d\!6?3（4，4）GT】（4，ム）4（ム,ム）Xo,Xi,X2,...,X„,满足基的三个条件。验证过程如下：由上可知,「是R的具有6个元素的基。对于T”由于（do,ds）0R,因此,T2不是R的基。设给定三个整数a,b,c,试写出寻找其中数的ー个算法（用C/C++描述）,并分析在平均情况与最坏情况下,算法分别要进行多少次比较?答:算法的C++描述如下:/'chl.qjp^includeciostrean^usingnamespacestd;intmid(inta,intb,intc)(intm;m=a; ,吁页设a为中数if(m>=b)(if(m>=c)(if(b>=c)m=b;//b为中数elsem=c;〃c为中数))else(if(m<=c)(if(b>-c)m=ci〃c为中数elsem=b;//b为中数))return(m);j返回中数}假设a,b,c中的每一个数为中数的概率相等(均为1/3)。由于当a为中数时需要比较2次2X(l/3)+3X(l/3)+3X(l/3)=8/3,b或c为中数时均需要比较3次,因此,在平均情况下上述算法所需要的比较次数为即在平均情况下，上述算法需要比较(8/3)次。在最坏情况下,上述算法需要比较3次(当b或c为中数时)。主函数例如下:intmain()(inta,b,c;cout«"input丄b,c="；cin»a»b»c;cout«"m="«mid(a,b,c)«endl;return0;}运行结果如下(带有下划线的为键盘输入)：inputa,b,c=483m=4利用减半递推技术,写出求长度为n的数组中最大元素的递归算法(用C/C++描述)。设n=2k,其中kNl。答:利用减半递推技术,求数组中最大元素的递归过程如下:如果数组中只有一个元素,则该元素即是数组中最大的元素。否则将数组对分为前半部分和后半部分：用同样的方法求数组前半部分的最大值maxi。用同样的方法求数组后半部分的最大值max2〇若maxl>max2,则maxi为数组中的最大值;否则max2为数组中的最大值。算法的C++描述如下：〃chl_2.cpp??mclude<iostream>usingnamespacestd;intmaxa(inta[],intm,intn)(intd5dl,d2;if(m=n)return(a[m-l]);else(d1=maxa(a1ms(m-n)2);d2=maxa(a,(m*n),,2+lsn);if(dl>d2)d=dl;elsed=d2;return(d);}}主函数例如下：intmain()(mta(16卜{15,6,4“521,7378「51.40コ6,43,49,6327};cout«"max-"maxa(i,1,16)«ajdl,return0;)运行结果如下:max=78编写二分法求方程实根的减半递推算法(用C/C++描述)。//chl_3.cpp^include<iostream>^mclude<cmath>usingnamespacestd;doubleroot(doublea,doubleb}doubleeps,double(*f)(double))(doublewhile(fabs(a-b)>=eps)(c=(a*b)2;n«(*fXc)；if(fl+1.0—1.0)答:算法的C++描述如下:retum(c);if(f0*fl>0)a=c;取区间后半部分elseb=c;。取区间前半部分)c=(a*b)2;retum(c);)主函数例如下:intmain。(doublea=0.0,b=3.0;doublef(double);cout«root(丄b,0.0000IQvvendl;return0;)doublef(doublex)(return(x*x*x-x*x-1.0);)运行结果如下:1.46557编写用回溯法求解皇后问题的算法（用C/C++描述）。答:算法的C++描述如下:〃chl_4cpp#include<iostream>2?include<iomanip>#include<cmath>usingnamespacestd;voidqueen(intn)(inti,j,k,jt,*q;q=nexvint[n];for(i=0;i<n;i-Hh)q[i]=0；i-0;jt=l；cout«n«?,queenproblem?,«endl;while(jt=l)({k-0;while((k<i)&&((q[k]-q[i])*(febs(q[k]-q[i]>fabs(k-i)))!M))kfif(k<i)砒else{i-i+1;(for(j=0j<nj++)cout«setw(5)«q[j]+l;cout«endl;q[n-l]=q[n-l]+l;i-n-1;))}else(q[«]-o；"-1;(cout«endl;deleteq;return;)q[i]-qW+l；}}1主函数例如下:intmain(){intn;cout«T,mputnr；cin»n;queen(n);return0;)运行结果如下:(带有下划线的为键盘愉入)inputn:44queenproblem24133142设有12个小球。其中11个小球的重量相同,称为好球;有一个小球的重量与11个好球的重量不同(或轻或重),称这个小球为坏球。试编写ー个算法(用C/C++描述),用ー个无祛码的天平称3次找出这个坏球,并确定其比好球轻还是重。答:用ー个长度为12的整型数组A(1：12)模拟表示编号分别为1〜12的12个小球,其中的元素值分别是各小球的重量。即在这个整型数组中,11个元素值是相同的,称为好元素!只有一个元素的值与11个好元素值不同(其值或大或小),称为坏元素。下面通过对数组中元素值的比较来找出这个坏元素。具体比较过程如下。首先将12个元素分成以下三组:第一组为A(1),A(2),A(3),A(4)四个元素;第二组为A(5),A(6),A(7),A(8)四个元素;第三组为A(9),A(10),A(11),A(12)四个元素。3次比较过程如表1-1所示。表1-1比较过程

第一次比较第二次比較第三次比較若A⑴+A(2)+A(3)+A(4)=A(5)+A(6)+A(7)+A(8)则A(9),A(10),A(11),A(12)中有坏若A(l)+A(9)=A(10)+A(11),则A(12)坏若A(l)>A(12),则A(12)坏且轻若A(l)<A(12),则A(12)坏且重若A(l)+A(9)>A(10)+A(11),则A(9)坏目重或A(10)与A(11)中有坏且轻若A(10)=A(11),则A(9)坏目重若A(10)>A(11),则A(11)坏且轻若A(10)<A(11),则A(10)坏且轻若A(l)+A(9)<A(10)+A(11),则A(9)坏且轻或A(10)与A(11)中有坏且重若A(10)=A(11),则A(9)坏且轻若A(10)>A(11),则A(11)坏且重若A(10)<A(11),则A(10)坏且重若A(l)+A(2)+A(3)+A(4)>A(5)+A(6)+A⑺+A(8)则A⑴，A⑵，A(3),A(4)中有坏且重或A(5),A(6),A(7),A(8)中有坏且轻若A(1)+A(2)+A(6)=A(3)+A(4)+A(5),贝リA(7),A(8)中有坏且轻若A(l)=A(7),则A(8)坏且轻若A(1)卢A(7),则A(7)坏且轻若A⑴+A(2)+A(6)>A(3)+A(4)+A(5),则A(1),A⑵中有坏且重,或A(5)坏且轻若A(l)=A(2),则A(5)坏且轻若A(l)>A(2),则A(1)坏且重若A(l)<A(2),则A(2)坏且重若A(1)+A(2)+A(6)<A(3)+A(4)+A(5),则A(3),A(4)中有坏且重,或A(6)坏且轻若A(3)=A(4),则A(6)坏且轻若A(3)>A(4),则A(3)坏目重若A(3)<A(4),则A(4)坏且重若A(l)+A(2)+A(3)+A(4)<A(5)+A(6)+A(7)+A(8)则A(1),A(2),A(3),A(4)中有坏且轻,或A(5),A(6),A(7),A(8)中有坏且重若A(1)+A(2)+A(6)=A(3)+A(4)+A(5),则A(7),A(8)中有坏且重若A(l)=A(7),则A(8)坏目重若A⑴チA(7),则A(7)坏且重若A(1)+A(2)+A(6)>A(3)+A(4)+A(5),则A(3),A(4)中有坏且轻,或A(6)坏且重若A(3)=A(4),则A(6)坏且重若A(3)>A(4),则A(4)坏且轻若A(3)<A(4),则A(3)坏且轻若A(1)+A(2)+A(6)<A(3)+A(4)+A(5),则A⑴,A(2)中有坏且轻,或A(5)坏且重若A(l)=A(2),则A(5)坏且重若A(l)>A(2),则A(2)坏且轻若A⑴<A(2),则A(1)坏且轻根据表1-1所示的比较过程,可以写出算法的C++描述如下:,chl_5-cpp?rinclude<iostream>usmgnamespacestd;intal2(intafl)(if(a[l]+a[2]亠a[3]-a[4]=a[5卜a[6]-a[7卜a[8])，a[9],a[10],a[ll],a[12]中有坏if(a[lha[9]=a[10]-a[ll])间12]坏if(a[l]>a[12])retum(-12);>a[l2]坏且轻elseretum(12);ノ间12]坏且重elseif(a[l]-a[9]>a[10]-a[ll]) a[9]坏且重,或a[10]与a[U]中有坏且轻if(a[10]=a[ll])retuni(9); a[9]坏且重&sei<a[10]>a[llDretum(-ll); a[11]坏且轻elseretum(-10); 坏目轻else，司9]坏且轻,或a[10]与屮1]中有坏且重if(a[10]=a[H])retum(-9); a[9]坏且轻elseif(a[10]>a[ll])retum(lO); a[10]坏且重elseretum(ll); a[11]坏目重&seif(a[l]+a[2]+a[3]+a[4]>a[习+a[6]+a[7]+a[8D//a[l],a[2],a[3レa[4]中有坏且重,或a[5],旳切,a[8]中有坏且轻if(a[l]-a[2]+a[6]=43]-1[4卜a[5]) ，a[7],a[8]中有坏且轻if(a[l]=a[7])retum(-8); a[8]坏且轻elseretum(-7);旬T]坏且轻elseif(a[l]^a(2]-a[6]>43]-a[4]-a[5D a[lレa[2]中有坏且重,或-5]坏且轻if(a[l]=a[2])retam(-5);〃a[5]坏且轻elseif(a[l]>a[2])retum(l); a[l]坏且重elseretum(2);，a[2]坏目重else/闻3],a[4冲有坏且重,或a[6]坏且轻if(a[3]=a[4])retuni(-6);间6]坏且轻elseif(a[3]>a[4])retum(3);ha[3]坏且重elseretum(4); a[4]坏且重else/a(l],a[2],a[3レ皿中有坏且轻,或キレa[6ル明,晒中有坏且重国aロ]-a[2]-a[6]=a[3]-a[4卜a[习)Za[7],a[8]中有坏且重if(a[l]-a[7])retum(8);/a[8]坏且重elsereturn⑺;厶a[7]坏且重elseif(a[l]-a[2]+a⑹>a[3]-a[4]+a[习)/闻3レa[4]中有坏且轻,或a[6]坏且重if(a[3]=a[4])retuni(6);/a(习坏且重elseif(a(3]>a[4])retum(-4); a[4]坏且轻elseretum(-3)iパa[3]坏且轻else间1],a[2]中有坏且轻,或a»]坏且重if(a[l]=a[2])retuni(5); a[5]坏且重elseif(a[l]>a[2])retum(-2); a[2]坏且轻elseretum(-l);询1]坏且轻)在上述Cー程序中,为了直观起见,定义的数组长度为13,其中数组元素a[0]在程序中不用。主函数例如下:intmainO(ima口3]={0,5,5,5,555545555};cout«f,k=<*«al2(a)«endl:return0;)运行结果如下:k=-8 表示数组中第S个元素为坏元素,即编号为8的小球为坏球,且比好球轻。第2章基本数据结构及其运算2.I复习笔记ー、基本概念数据结构的定义数据结构是指相互有关联的数据元素的集合。(1)数据的逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。①数据的逻辑结构包含的信息:a.表示数据元素的信息;b,表示各数据元素之间的前后件关系。②数据的逻辑结构要素:a.数据元素的集合,通常用D来表示;b.D上的关系,它反映了D中各数据元素之间的前后件关系,通常记为R。即数据结构可以表示成B={D,R}其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元表示。(2)数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。常用的存储结构有顺序、链接、索引等存储结构。数据结构的图形表示(1)将数据集合D中的每ー个数据元素用中间标有元素值的方框表示，称为数据结点，简称结点；为了进ー步表示各数据元素之间的前后件关系,将关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点。(2)在数据结构中,没有前件的结点称为根结点;没有后件的结点称为终端结点(也称为叶子结点)。数据结构的类型根据数据结构中各数据元素之间前后件关系的复杂程度,可将数据结构分为线性结构与非线性结构。线性结构又称线性表,与其相关的几个性质如下:(1)若一个线性结构非空，则其有且只有一个根结点,且每ー个结点最多有一个前件,最多有一个后件;(2)在ー个线性结构中插入或删除任何ー个结点后还应是线性结构:(3)如果一个数据结构满足上述两个条件,但当在此数据结构中插入或删除任何ー个结点后就不满足这两个条件了,则该数据结构不能称为线性结构。线性结构与非线性结构都可以是空的数据结构。ー个空的数据结构究竟是属于线性结构还是属于非线性结构,这要根据具体情况来确定。二、线性表及其顺序存储结构线性表及其运算(1)定义线性表是由n(n>0)个数据元素4,a”…，a”组成的ー个有限序列。矩阵也是ー个线性表,在矩阵中,既可以把每一行看成是一个数据元素，也可以把每一列看成是一个数据元素。其中,每ー个数据元素实际上又是ー个简单的线性表。非空线性表有如下ー些结构特征:①有且只有一个根结点a”它无前件;②有且只有一个终端结点あ,它无后件;③除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。(2)顺序存储结构线性表的顺序存储结构具有以下两个基本特点:①线性表中所有元素所占的存储空间是连续的;②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在程序设计语言中,通常定义ー个ー维数组来表示线性表的顺序存储空间。在用ー维数组存放线性表时,该ー维数组的长度通常要定义得比线性表的实际长度略大,以便对线性表进行各种运算,特别是插入运算。建立一个容量为m的空线性表的顺序存储空间的C++描述如下:templatecnpenameT> 模板声明,T为类型参数voidinit_sq_LList(T*v,intmsmt*n)ヽnewT[m];动态申请存储空间*n=0i ユ线性表长度置为〇return;）在上述描述中,T为线性表中元素的虚拟数据类型。要释放线性表的顺序存储空间时,可以用“delete[]v；（3）顺序存储下的插入运算假设线性表的存储空间为V（1：m）,线性表的长度为n（n<m）,插入的位置为i（i表示在第i个元素之前插入）。要插入新元素b,则插入的过程如下:①首先处理以下三种异常情况。a.当存储空间已满（即n=m）时为“上溢”错误，不能进行插入，算法结束;b.当i>n时，认为在最后ー个元素之后插入;c,当i<l时,认为在第1个元素之前插入;②从最后ー个元素开始,直到第i个元素,其中每ー个元素均往后移动ー个位置;③最后将新元素b插入到第i个位置,并且将线性表的长度增加1。线性表在顺序存储结构下插入算法的C++描述如下:Iinclude<iostr¢am>usingnamespacestd;template<typen^meT> 〃模板声明,T为类型参数voidins_sq_LLi8t(T*v,intm,int*n,inti,Tb)iintk;if(*n«-m) 〃存储空间已満,上溢错误{cout«Moverflow!\nw; return;}if(i>*n)i-»n+1; 〃默认为在最后ー个元素之后插入ifリC)，7,・ 〃蒙认为在第一个元章之前揄入for(k*•n;k>-l；k--)v[k]«vlk-i]; 〃从最后ー个元米开始,直到第i个元索均往后移动ー个位臂v(i-lj-b; 〃插入新元素*n-»n*l; 〃线性或长度增加]1return;（4）顺序存储下的删除运算假设线性表的存储空间为V（1：m）,线性表的长度为n（n<m）,删除的位置为i,则删除的过程如下:①首先处理以下两种异常情况。a.当线性表为空时为“下溢”错误,不能进行删除,算法结束;b,当i<l或i>n时,认为在最后ー个元素之后删除。②从第i+1个元素开始,直到最后ー个元素，其中每ー个元素均依次往前移动ー个位置;③最后将线性表的长度减1。（5）顺序表类下面的描述是将顺序表的数据和基本操作（初始化、输出、插入与删除操作）封装成一个sq丄List类:////模板声明,数据元索虚拟类型为T〃顺序表类〃数据成员〃存储空间容依〃顺序表长度〃顺序表存储空间首地址〃成员函数return;)〃建立空顺序表,申请存储空间〃順序输出順序表中的元素与顺序表长度〃检测顺序表的状态//在表的指定元索前插入新元素//sq_LList.h#include<iostream>usingnamespacestd;template<classT>classsq_LList{private:intmm;intnn;T*v;public:sq_LList(){mm=O;nn»O;sq_LList(int);voidprt_sq_LList();intflag_sq_LList();voidinssq_LList(int,T);voiddel-Sq>List(int); 〃在表中B(除指定元素〃建立空顺序表〃存储空间〃存储空间容置〃动态申请存储空间〃顺序衰长度为。,即建立空顺序表v«newTfmmJ;nn・0;recurn;〃顺序输出廡序表中的元素与顺序表长度tempiate<classT>voidsq_LList<T>：:prt_sq_LLlst(){inti;cout«nnn-"«nn«endl；for(t・0;i<nn；i++)cout«v(1]«end1;return;〃检测顺序表的状态template<classT>〃存储空间已満,返回一】〃〃存储空间已満,返回一】〃顺序表为空，返回0〃正常返回1(if(nn・•mn)return(-1)；if(nn-«0)return(0);return⑴;〃在表的指定元素前插入新元素template<classT>voidsq_LList<T>::ins_sqtList(inti,Tb)(intk;if(nn*«iwn)(cout«"overfLowHif(nn*«iwn)(cout«"overfLowH«endl;ifぐいnZ 1;if<i<l)i-1;for(K-nn;k>*i;k--)vjk)*vjk-l);vimわ;nn-nn*l;〃存储空间已需，上溢槍误return；）〃跃认为在敷后ー个元素之后捕人〃默认为在第一个元素之前插入〃从最后ー个元家直到第i个元素均后移ー个位置〃摘入新元素〃顺序表长度加1return；return；ノノ在翔洋表中髭除指定元素template<classT>voidsq^LList<T>•:del_sg_LList(inti)Iintk;if(nn•if(nn•・0)〃顺用表为空，下溢幡谈Icout«"underflow!"«endl;return;}if 〃顺序表中没有这个元案(coutくく"Notthiselementinthelist!M«endl;return;)for(k»i;k<nn;k++)v[k-l)-v[k]; 〃从第i个元素直到最后ー个元素均前移ー个位置nn»nn-l; 〃顺序表氏度减!return;利用顺序表类中的成员函数flag_sq_LList()可以解决上溢错误信息没有返回给调用程序，调用程序无法处理的情况。成员函数flag.sq.LList()的功能是检测顺序表的当前状态〇若顺序表满,则返回函数值ー1；若顺序表空,则返回函数值〇;正常情况则返回函数值1。栈及(1)定义栈实际上也是线性表,只不过是ー种特殊的线性表。其插入和删除运算都只在线性表的ー端进行。在栈中,将允许插入与删除的一端称为栈顶,将不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素,也是最先被删除的元素;栈底元素总是最先被插入的元素,也是最后オ被删除的元素。即栈是按照“先进后出‘‘(FirstlnLastOut,FILO)或“后进先出''(LastInFirstOut,LIFO)的原则组织数据的,通常用指针top来指向栈顶的位置,用指针bottom指向栈底。往栈中插入ー个元素称为入栈运算,从栈中删除ー个元素称为退栈运算。栈顶指针t。p动态反映了栈中元素的变化情况。图2-1是栈的示意图。入栈退栈栈顶top入栈退栈栈顶top栈底bottom图2-1栈的示意图（2）顺序存储及运算①概念在程序设计语言中,用ー维数组S（1：m）作为栈的顺序存储空间,其中m为栈的最大容量。通常,栈底指针指向栈空间的低地址一端。S（bottom）通常为栈底元素（在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空;top=m表示栈满。template<t>penameT>模板声明,T为类型参数voidimt_Stack（Tnimt叩）（$-newT（m],动态申调容量为m的存償空间•top-O； UJ页指针晟为0»即栈空return;}建立一个空栈的顺序存储空间（即初始化栈的顺序存储空间）的C++描述如下:当要释放栈的顺序存储空间时,可以用“delete[]S；"。②入栈运算入栈运算是指在栈顶位置插入一个新元素。设栈顺序存储空间为S（1：m）,栈顶指针为top,入栈的元素为x。则入栈运算的操作过程如下:a,首先判断栈顶指针是否已经指向存储空间的最后ー个位置。如果是，则说明栈空间已满，不可能再进行入栈操作,即为栈“上溢’’错误。算法结束；b.将栈顶指针进ー（即top加1）；C.最后将新元素X插入到栈顶指针指向的位置。^include<iostream>usingnamespacestd;template<t>penameT>voidpush（T*s,intm;int*top,Tx）（if（*top=m）{cout«"Stack-overflownM;retum;}*top=*top-l;s[*top-l]=x;return;）在顺序存储结构下入栈算法的C++描述如下:③退栈运算退栈运算是指取出栈顶元素并赋给ー个指定的变量。设栈顺序存储空间为S（1：m）,栈顶指针为top。则退栈运算的操作过程如下:a.首先判断栈顶指针是否为0,如果是,则说明栈空,不可能进行退栈操作,即为栈“下溢”错误,算法结束;b.将栈顶元素赋给ー个指定的变量;c,最后将栈顶指针退ー（即top减1）。④读栈顶元素读栈顶元素是指将栈顶元素赋给ー个指定的变量。设栈顺序存储空间为S（1：m）,栈顶指针为top。则读栈顶元素的操作过程如下:a.首先判断栈顶指针是否为0,如果是，则说明栈空，读不到栈顶元素,算法结束;b.将栈顶元素赋给指定的变量y。必须注意，这个运算不删除栈顶元素,只是将它的值赋给ー个变量。因此，在这个运算中栈顶指针不会改变。在顺序存储结构下读栈顶元素算法的C++描述如下:^include<iostream>usingnamespacestd;template<t>penameT>Ttop(T*s,intm,int*top)(T%if(*top=0){cout«HStackemptynn;retum;}y*s[*top-l]retum(y);)(3)表达式的计算①概念计算机系统在具体处理表达式前,首先设置以下两个栈:ー是运算符栈,用于在表达式处理过程中存放运算符。在开始时,运算符栈中先压入一个表达式结束符“；”。二是操作数栈,用于在表达式处理过程中存放操作数。然后从左到右依次读出表达式中的各个符号(运算符或操作数)。②原则每读出一个符号按以下原则进行处理:a.若读出的是操作数,则将该操作数压入操作数栈，并依次读下一个符号:b.若读出的是运算符，则作进ー步判断:第一,若读出运算符的优先级大于运算符栈栈顶运算符的优先级,则将读出的运算符压入运算符栈,并依次读下ー个符号。第二,若读出的是表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束,最后的计算结果在操作数栈的栈顶位置。第三，若读出运算符的优先级不大于运算符栈栈顶运算符的优先级,则从操作数栈连续退出两个操作数,并从运算符栈退出ー个运算符,然后作相应的运算(运算符为刚从运算符栈退出的运算符,运算对象为刚从操作数栈退出的两个操作数),并将运算结果压入操作数栈。在这种情况下,当前读出的运算符下次将重新考虑(即不再读下ー个符号)。(4)递归的实现在递归函数的执行过程中,需要用栈来记忆各层调用中的参数，以便在逐层返回时恢复这些参数继续进行处理。在递归函数开始执行时,栈为空,随着递归调用,逐步将各层中的输入参数进栈,在逐层返回时，又依次从栈中取出这些参数打印输出。队列(1)定义队列(equeue)是指允许在一端进行插入,而在另一端进行删除的线性表。允许插入的ー端称为队尾,通常用ー个称为尾指针(rear)的指针指向队尾元素;允许删除的一端称为排头或队头,通常也用一个排头指针(front)指向排头元素的前ー个位置。队列称为“先进先出''(FirstInFirstOut,FIFO)或“后进后出’’(LastInLastOut,LILO)的线性表,它体现了“先来先服务''的原则。在队列中,队尾指针rear与排头退队ABCDEF入队指针front共同反映了队列中元素动态变化的情况。图2-2是具有6个元素的队列示意图。图2-2具有6个元素的队列示意图往队列的队尾插入ー个元素称为入队运算,从队列的排头删除ー个元素称为退队运算。图2-3是在队列中进行插入与删除的示意图。由图2-3可以看出，在队列的末尾插入ー个元素只涉及队尾指针rear的变化，而要删除队列中的排头元素只涉及排头指针front的变化。图2・3队列不意图（2）循环队列及其运算①概念循环队列是将队列存储空间的最后ー个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前ー个位置,从排头指针指向的后ー个位置直到队尾指针指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空,即rear=front=m。循环队列主要有两种基本运算:入队运算与退队运算。每进行一次入队运算,队尾指针就进ー。当队尾指针rea尸m+1时，则置reak1。每进行ー次退队运算,排头指针就进ー。当排头指针front=m+l时,则置front=l。tempiate<typenameT> 〃模板声明»T为类型参数voidinit_Queue（T**front»int*rear»int*s）（q=newT[m];*front=mj*rear=m；*s=0»return；}建立一个循环队列顺序存储空间算法的C++描述如下:当要释放循环队列的顺序存储空间时,可以用“deleteq；"。②入队运算入队运算是指在循环队列的队尾加入一个新元素。设循环队列顺序存储空间为Q（I：m）,队尾指针为rear;排头指针为front;标志s入队的元素为x。则入队运算的操作过程如下:a.首先判断循环队列是否满,当循环队列非空（s=l）且队尾指针等于排头指针时,说明循环队列已满,不能进行入队运算，即为“上溢”,此时算法结束；b,将队尾指针进ー（即rear=rear+l）,并当reakm+1时置rear=l；c.最后将新元素x插入到队尾指针指向的位置,并且置循环队列非空标志。循环队列入队运算的C++描述如下:#include<iostrea(n>usingnamespacestd;template<typenameT> 〃模板声明,T为类型参数voidaddcq(T*qfintint*rear,int*front,int*s,Tx){i£((*s==l)&&(*rear==*front)){cout«MQueue-OVERFLOW\nw;return;}*rear-*rear+1;if(*rear««m+1) *rear=1;q(»rear-l]»x;*s=l;return;③退队运算退队运算是指在循环队列的排头位置退出ー个元素并赋给指定的变量。设循环队列顺序存储空间为Q(l：m),队尾指针为rear,排头指针为front,标志为s,则退队运算的操作过程如下:a.首先判断循环队列是否为空,当循环队列为空(s=0)时,不能进行退队运算,即为“下溢”,此时算法结束;b.将排头指针进ー(即(front=front+l),并当front=m+l时置front=l；c.再将排头指针指向的元素赋给指定的变量;d.最后判断退队后循环队列是否为空,当front=rear时,置循环队列空标志(即s=0)。循环队列退队运算的C++描述如下:#include<iostream)usingnamespacestd;template<typenameT> 〃模板声明,T为类型参数Tdelcq(T*q,intint*rear/int*frontsint*s)(Ty;if(*s==0) {cout«MQueue~UNDERFLOW\nw;return;}*front=«front+1;if(*front==m+1) *front=l;*y=q(*front-1);if(♦front==*rear)*s=0;return;④循环队列类下面的描述是将循环队列的数据和基本操作（初始化、入队、退队、输出排头与队尾指针以及循环队列中的元素）封装成一个循环队列类sq-Queue：//模板声明,//模板声明,数据元素虚拟类型为T〃数据成员〃存储空间容址//排头指针〃队尾指针〃标志//循环队列存储空间首地址〃成员函数〃构造函数,建立空桶环队列//输出排头与队尾指针以及队中元素//检测徳环队列的状态〃人队//退队〃存储空间容量//动态申请存储空间return;)//sq_Queue.h#include<iostream>usingnamespacestd;〃定义循环队列类template<classT>classsq_Queue(private:intmm;intfront;intrear;ints;T•q;public:sq_Queue(int);voidprt_sq_Queue();intflagsq_Queue();voidinssq-Queue(T);Tdel_sq_Queue();J；〃建立容最为mm的空循环队列template<classT>sq_Queue<T>::sq_Queue(intm)(mm»m;q«newT(mm];front=mm;rear=mm;s»0;return;)〃输出排头与队尾指针以及队中元素template<classT>voidsq_Queue<T>::prt_sq_Queue()(inti;cout«"front，w«front«endl;cout«"rear，"«rear«endl;if(s,・0){coutく<”队列空!**<<endl;i=front;do{i«i+1；if(i==mm+l)is1;cout«q[i-l]«endl;}while(i!-rear);return;//检测循环队列的状态template<classT>intsqQueue<T>::flag_sq_Queue(){if(1)is(rear»«front))return(-1);if(s-=0)return(0);return(1);〃存储空间已満,返回一1〃循环队列为空,返回O〃正常返回1//人队template<classT>voidsq_Queue<T>::ins_sq_Queue(Tx){if((s-«l)&&(rear®-front))//存储空间已满,上溢错误(cout«MQueue_overflow!M«endl;return;}rear=rear+l;〃队尾指针进ーif(rear=«mm>1)rear-1;q(rear-l]=x;s»l;〃新元素人队〃人队后队列非空return;〃退队template<classT>Tsq_Queue<T>::del_sq_Queue(){Ty;if(s«=0)(cout«MQueue_underflow!H«endl;front«front+1;〃队列为空,下溢错误return(0);)〃排头指针进ーif(front--mm+1)front-1;y=q[front-1J;if(front=arear)s=0;〃将退队元索赋给变盘return(y);〃返冋退队的元素三、线性链表基本概念（1）定义在线性链表中,用ー个专门的指针HEAD指向线性链表中第一个数据元素的结点。线性表中最后ー个元素没有后件,因此,线性链表中最后一个结点的指针域为空（用NULL或。HEAD一数据]丄 数据2丄 ►...—数据n]NULL表示），表示链表终止。线性链表的逻辑结构如图2-4所示。图2-4线性链表的逻辑结构一般情况下,各结点存储序号是不连续的,并且各结点的位置关系与逻辑关系也不一致,而数据元素之间的前后件关系是由各结点的指针域来指示。指向线性表中第一个结点的指针HEAD称为头指针。当HEAD=NULL（或〇）时,称为空表。如下C++程序段定义了一种结点类型node;并定义了该类型的指针变量p（用于指向该种结点类型的存储空间的首地址）;最后申请分配该结点类型的ー个存储空间,其首地址存structnode{intd;〃定义结点类型〃数据域node*next;)；intmain(){node*p;〃指针域//定义该类型的指针变量Pp=newnode;〃申请分配结点存储空间deletep;//释放结点存储空间return0;放在指针变量P中。单链表中,只能向后寻找后件结点,无法向前寻找前件结点,因此会带来极大不便。为了弥补线性单链表的这个缺点,对线性链表中的每个结点设置两个指针。其中,一个称为左指针(Llink),用以指向其前件结点:另一个称为右指针(Rlink),用以指向其后件结HEADHEAD点。这样的线性链表称为双向链表，其逻辑状态如图2-5所示。图2-5双向链表示意图(2)优缺点线性表的顺序存储结构具有简单、运算方便等优点,特别是对于小线性表或长度固定的线性表,采用顺序存储结构的优越性更为突出。但是,线性表的顺序存储结构存在以下几方面的缺点:①插入与删除运算的效率都很低;②在顺序存储结构下,线性表的存储空间不便于扩充;③线性表的顺序存储结构不便于对存储空间进行动态分配。线性链表的插入与删除(1)插入假设可利用栈与线性链表如图2-6(a)所示。现在要在线性链表中包含元素x的结点之前插入一个新元素b。(a)原来的可利用栈与线性链表(b)从可利用桟取得结点p.在线性链表中找到包含元素x的前ー个结点g(c)p插入到g之后图2-6线性链表的插入其插入过程如下:①从可利用栈取得一个结点,设该结点号为P;并置结点P的数据域为插入的元素值b,即V(p)=b。经过这ー步后,可利用栈的状态如图2-6(b)所示。②在线性链表中寻找包含元素x的前一个结点,设该结点的存储序号为q。线性链表如图2-6(b)所示。③最后将结点p插入到结点q之后。为了实现这ー步,只要改变以下两个结点的指针域内容:a.使结点p指向包含元素x的结点(即结点q的后件结点),即NEXT(p)=NEXT(q)；b.使结点q的指针域内容改为指向结点p,即NEXT(q尸p。这ー步的结果如图2-6(c)所示。此时插入就完成了。(2)删除假设可利用栈与线性链表如图2-7(a)所示。现在要在线性链表中删除包含元素x的结点。其删除过程如下:①在线性链表中寻找包含元素x的前一个结点,设该结点序号为q,则包含元素x的结点序号p=NEXT(q)；②将结点q后的结点P从线性链表中删除,即让结点q的指针指向包含元素x的结点p的指针指向的结点,即NEXT(q)=NEXT(p)。经过上述两步后,线性链表如图2-7(b)所示。③将包含元素x的结点p送回可利用栈。经过这ー步后,可利用栈的状态如图2-(c)将被删除的结点ハ送回可利用栈后7(c)所示。此时,线性链表的删除运算完成。图2-7线性链表的删除带链的栈与队列(1)带链的栈栈也是线性表,也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为可利用栈。计算机中的所有可利用空间都可以以结点为单位链接在可利用栈中。随着其他线性链表中结点的插入与删除,可利用栈处于动态变化之中,即可利用栈经常要进行退栈与入栈操作。¢2)带链的队列与顺序队列ー样,带链队列的基本操作有以下几个:①队列的初始化,即建立一个空队列的顺序存储空间;

②入队运算,指在循环队列的队尾加入ー个新元素;③退队运算,指在循环队列的排头位置退出ー个元素并赋给指定的变量。循环链表通过循环链表(CircularLinkedList)的结构可以解决空表与非空表运算不统一的问题。图2-8是循环链表的示意图。其中图2-8(a)是ー个非空的循环链表,图2-表头结点HEAD表头结点HEAD(a)非空循环鮭表HEAD表头结点(b)空循环性表8(b)是ー个空的循环链表。在此,空表与非空表是针对线性表中的元素而言。图2-8循环链表的逻辑状态在实际应用中,循环链表与线性单链表相比主要有以下两个方面的优点:(1)在循环链表中,只要指出表中任何ー个结点的位置,就可以从它出发访问到表中其他所有的结点,而线性单链表做不到这一点；(2)由于在循环链表中设置了一个表头结点,因此,在任何情况下,循环链表中至少有ー个结点存在,从而使空表与非空表运算的统ー。以下描述的是循环链表类。//linked_Clist.h#include<iostream>usingnamespacestd;〃定义结点类型template<classT>structnode{Td;node*next;}；〃定义循环锌表类template<classT>classlinkedCList{private:node<T>*head;public:linked_CList();voidprt_linked_CList();voidins_linked_CList(TrT);intdel_linked_CList(T);)；〃建立空循环链表template<classT>linked_CList<T>::linked_CList(){node<T>*p;p-newnode<T>;p->d=0;p->next»p;head=p;〃数据元素虚拟类型为T//模板声明,数据元素虚拟类型为T〃数据成员//循环链表头指针〃成员函数〃构造函数,建立空循环链表〃扫描输出循环能表中的元素〃在包含元素x的结点前插入新元素b〃删除包含元素X的结点〃申请一个表头结点return;//扫描输出循环链表中的元素template<classT>voidlinked_CList<T>::prt_linked_CList()(node<T>*p;p»head->next;if(p・・head){cout<<”空循环链表!”<<endl;return;)do{cout«p->d«endl;p-p->next;)while(p!-head);return;}〃在包含元素x的结点前插入新元素btemplate<classT>voidlinked_CList<T>::ins_linked_CList(Tx,Tb){node<T>•p,»q;p-newnode<T>; 〃申请ー个新结点p->d-b; 〃置新结点的数据域q«head;while((q->next!-head)&&(((q->next)->d)!-x))q-q->next; 〃寻找包含元素x的前ー个结点qp->next-q->next;q->next-p; 〃新结点p插入到结点q之后return;)//删除包含元素X的结点元卖template<classT>intlinked_CList<T>::del_linked_CList(Tx){node<T>*pr*q;q=head;while((q->next!»head)&&(((q->next)->d)!=x))q=q->next; 〃寻找包含元素x的前ー个结点qif(q->next=«head)return(0); 〃循环链表中无删除的元素p-q*>next;q*>next-p->next; //删除q的下ー个结点pdeletep; 〃糅放结点p的存储空间return(1);多项式的表示与运算(1)表示Prt(x)=anxn+an-\Xn~x+…+ゐよ+。0设多项式为这种表达式中,即使某次项的系数为0时也必须存储,浪费了存储空间。可以采用链表形式来表示,即忽略系数为0的项,仅对非0项用结点表示。多项式中非零系数项所构成的结点如图2-9所示。其中数据域有两项:EXP(i)表示该项的指数值,COEF(i)表示该项的系数。EXP⑴COEF(i)NEXT(i)指针域NEXT(i)表示下一个非零系数项的结点序号。图2-9多项式非零系数项的结点结构在用循环链表表示时，其表头结点中的指数域为ー1,系数域为任意。由于多项式中的指数不可能为负数,因此很容易将表头结点与其他结点区分开。(2)多项式链表的生成生成一个多项式链表可以有以下两种方法:①从键盘输入多项式链表;②由数组复制多项式链表。(3)多项式链表的释放从表头结点开始,逐步释放链表中的各结点。但必须注意,多项式链表的释放只是删除了多项式链表中的元素结点,而不删除表头结点。即经过这个操作后,多项式变成一个空的循环链表。(4)多项式的输出从表头结点后的第一个结点开始，以数偶形式顺链输出各结点中的指数域与系数域的内容。(5)多项式的相加多项式相加的运算只要从两个多项式链表的第一个元素结点开始检测,对每一次的检测结果做如下运算:①若两个多项式中对应结点的指数值相等,则将它们的系数值相加;如果相加结果不为零,则形成一个新结点后链入头指针为CH的链表末尾;然后再检测两个链表中的下ー个结点。②若两个多项式中对应结点的指数值不相等，则复抄指数值大的那个结点中的指数值与系数值,形成一个新结点后链入头指针为CH的链表末尾;然后再检测指数值小的链表中的当前结点与指数值大的链表中的下一个结点。重复以上过程直到两个链表中的所有结点均检测完为止。(6)多项式的相乘多项式相乘的基本方法如下:C(x)=とXクル产"，’夕对于多项式Am(X)中每ー项与多项式&(X)相乘,且将结果逐步累加,即四、线性表的索引存储结构概念索引存储的基本思想是:将具有n个结点的线性表按性质划分成m个子表，然后分别存储此m个子表。另外再设立一个具有m个结点的索引表,其每ー个结点存储ー个子表性质的有关信息以及子表中第一个结点的存储地址。对于同一个索引表中的各结点结构应相同。(1)线性表的划分将线性表L划分成m个子表し,し,…,し、的基本方法是:对线性表L中的每个结点元素&的关键字k,计算其索引函数值,将所有索引函数值为i的结点元素均归并到第j个子表し中。经过划分后,m个子表し,し,…,し、、中的结点结合在ー起正好是线性表L中的全部结点。处理具有性质P的结点,不必查遍原线性表L中的全部结点,而只需要直接对具有性质P的子表进行处理就行了,提高查找效率。（2）索引存储的方式索引存储包括索引表的存储与各个子表的存储。如果采用顺序分配与链式分配的存储结构,则共有4种索引存储的方式:“顺序一索引ー顺序’’存储方式；“顺序一索弓I-链接''存储方式;“链接一索弓、顺序''存储方式;“链接-索引ー链接''存储方式。“A-索引-B”存储方式是指用存储结构A方式存储索引表,用存储结构B方式存储各子表。①“顺序一索引ー顺序”存储方式在“顺序一索引ー顺序''存储方式中,索引表与各子表均用顺序分配的方式来表示,有下面两个结构特点;a.索引表中的每ー个结点均设有若干个数据项,用以表示相应子表的有关信息;b.每个结点中还设有一个指针项,用以指示相应子表的第一个结点的存储序号。其在应用中常具备如下3个特点:a.在这种存储方式中，每ー个子表都是顺序分配的,但各个子表在存储空间中的前后位置无关紧要,并且各子表之间的存储地址也不一定是连续的；b.对于顺序存储的线性表来说,除了需要指出第一个结点的存储序号外,它的长度有时是必不可少的,特别是对于查找操作尤为突出;c.这种存储方式只有在线性表为固定的情况下オ比较合适。②“顺序一索引ー链接”存储方式“顺序一索引ー链接''存储方式是指用顺序分配的方法存储索引表,而用链式分配的方法存储各子表。在这种存储方式中,各子表均为线性链表,而每ー个线性链表的头指针是索引表中对应结点的指针项。图2-10为这种存储结构的示意图。数据表指针表图2-10"顺序一索引ー链接’‘存储结构示意图(3)多重索引存储结构如果索引表本身又是索引存储结构,则称为二重索引存储结构。索引存储结构嵌套多层形成多重索引结构,适当的嵌套使用索引结构可以有效地提髙查找效率。五、数组顺序存储结构(1)以行为主的顺序存储二维数组以行为主的顺序存储是指将数组中的元素一行接一行地顺序存储在计算机的连续存储空间中。在二维数组的以行为主顺序存储中，假设数组中第一个元素(即a”)在计算机中的存储地址为ADR(a,1),且每ー个元素占L个字节,则数组中的元素a"在计算机中的存储地址为ADR(a«)=ADR(a,1)+[(i-1)n+j-l]Lo其中iWigm,10Wn。(2)以列为主的顺序存储二维数组以列为主的顺序存储是指将数组中的元素一列接一列地顺序存储在计算机的连续存储空间中。在二维数组的以列为主顺序存储中，假设数组中第一个元素(即a”)在计算机中的存储地址为ADR(a,1),且每ー个元素占L个字节,则数组中的元素a"在计算机中的存储地址为ADR(aij)=ADR(a,,)+[(j-1)m+i-l]L。其中Igigm,l<j<rio规则矩阵的压缩规则矩阵是指矩阵中非零元素的分布是有规律的。压缩存储是指在存储ー个规则矩阵时,只需存储非零元素即可,而对于大部分的零元素或者重复的非零元素不必存储。(1)下三角矩阵的压缩存储设n阶下三角矩阵为开辟ー个长度为n(n+l)/2的ー维数组B,然后一行接一行地依次存放A中下三角部分的元素。经压缩后,存放在ー维数组B中的形式如图2-11(a)所示。

alla12alla12ー笫1行的元素a21a22a23-第2行的元素a32a33a34-第3行的元素***an-lji-2an-lji-l317Mー第n-l行的元素へ.n・laiuiー第n行的元索(a)以行为主alla21ー笫1列的元素a12a22a32ー第2列的元素a23a33a43ー第3列的元索***—第n-l列的元素annー第n列的元素(b)以列为主图2-11用ー维数组压缩存放ド三角矩阵显然,下三角矩阵A用ー维数组B表示后,可以按如下原则访问A中的第i行、第j列的元素［寅一1)/2+，］［O j>i下三角矩阵A也可以用以列为主的方式压缩存储在ー维数组B中,其存储形式如图2-11(b)所示。在以列为主压缩存储下三角矩阵A的情况下,访问下三角矩阵A中第i行、第j列元素为的公式为0,=Io i>i对下三角矩阵采用以行为主的压缩方法更为方便,但如果要对上三角矩阵进行压缩存储,则采用以列为主比较方便。在以列为主压缩存储上三角矩阵A的情况下,访问上三角矩阵■[0 j<iへ・(ぬ。ーD/2+口j>iA中第i行、第j列元素aM的公式为(2)对称矩阵的压缩存储即=レ[内-1)/2+门y>i在以行为主压缩存储对称矩阵A的情况下,访问对称矩阵A中第i行、第j列元素为的公式为(3)三对角矩阵的压缩存储n阶三对角矩阵的形式为对于n阶三对角矩阵,用ー个长度为3n-2的ー维数组存放三条对角线上的元素,其存储形式如图2-12所示。lO jVi-1或ノ）i+1在用ー维数组B以行为主存放三对角矩阵A中的元素a.时,其访问公式为

10 j<i〜1或>>i+l在用一维数组B以列为主存放三对角矩阵A中的元素衡时,其访问公式为allaalla12a21a22a23a32a33a34***^n-1^n-13nl,n-2,n-l,naihn-1ー第1行的元索C一第2行的元索-第3行的元素alla21ー第1列的元索ー笫2列的元素a12a22a32a23a33a43-第3列的元索—第n-1行的元索-第n行的元素an-2,n-lan-lji-lan,u-l一第n-1列的元素ー第!!列的元索分1】•1爾(a)以行为主 (b)以列为主图2-12用ー维数组压缩存放三对角矩阵一般稀疏矩阵的表示如果ー个矩阵中绝大多数的元素值为零,只有很少的元素值非零,则称该矩阵为稀疏矩阵。(1)三列二维数组表示在压缩存储形式中,每ー个非零元素应包括其所在的行号i、列号j和值V。即每ー个非零元素可以用下列三元组表示:(i,j,V)为了表示的唯一性,除了每ー个非零元素用ー个三元组表示外,在所有表示非零元素的三元组之前再添加一组信息:(I,J,t)其中I表示稀疏矩阵的总行数,J表示稀疏矩阵的总列数，t表示稀疏矩阵中非零元素的个数。通常将这些三元组组织成三列二维表格的形式,一般又表示成三列二维数组的形式，并简1231788"718388'3121333181143193\95457B=45765765767642642866366335_97357(a)稀疏矩阵的三列二维表格(b)稀疏矩阵的三列二维数组称为三列二维数组。图2-13为稀疏矩阵A的三列二维表示。图2-13稀疏矩阵的表示例(2)线性链表表示及运算表示稀疏矩阵中各非零元素信息的三元组可以组织成线性链表的形式。当产生新的非零元素时,可以直接申请ー个存放三元组的结点，然后顺序链接到线性链表中。如果通过运算,原来的非零元素变成了零元素,则可以从线性链表中删除这个结点。(3)十字链表①基本概念用十字链表结构表示稀疏矩阵时,矩阵中的每ー个非零元素对应ー个结点,每个结点有五个域：行域、列域、值域、向下域与向右域,如图2-

14所示。其中:行域与列域分别存放非零元素所在的行号与列号,值域存放非零元素的值,向下域指示同一列中下ー个非零元素的存储结点序号,向右域指示同一行中下ー个非零row col val行域列域值域向下域向右域down riglit元素的存储结点序号。图2-14十字链表的结点结构②特点用十字链表表示稀疏矩阵的结构特点如下:a.稀疏矩阵的每一行与每一列均用带表头结点的循环链表表示；b.表头结点中的行域与列域的值均置为-1(即row=-l,col=-l)；c.行、列链表的表头结点合用，且这些表头结点存放在ー个顺序存储空间中。③C++描述〃非零元素所在的行号〃非零元素所在的列号〃非零元素所在的行号〃非零元素所在的列号〃非零元索值〃向下指针域〃向右指针域