徐士良《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》（第4版）筆記和課后習(xí)題詳解

目錄內(nèi)容簡介目錄第1章預(yù)備知識復(fù)習(xí)筆記課后習(xí)題詳解第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算復(fù)習(xí)筆記課后習(xí)題詳解第3章查找與排序技術(shù)復(fù)習(xí)筆記課后習(xí)題詳解第4章資源管理技術(shù)4.1復(fù)習(xí)筆記42課后習(xí)題詳解第5章數(shù)據(jù)庫設(shè)計(jì)技術(shù)復(fù)習(xí)筆記課后習(xí)題詳解第6章編譯技術(shù)概述復(fù)習(xí)筆記課后習(xí)題詳解第7章應(yīng)用軟件設(shè)計(jì)與開發(fā)技術(shù)復(fù)習(xí)筆記課后習(xí)題詳解第1章預(yù)備知識1.I復(fù)習(xí)筆記ー、集合基本概念集合是指若干個(gè)或無窮多個(gè)具有相同屬性的元(元素)的集體。通常,ー個(gè)集合名稱用大寫字母表示,而集合中的某個(gè)元素用小寫字母表示。如果集合M由n(n>0)個(gè)元素a“&，…，a”組成,則稱集合M為有限集。如果ー個(gè)集合中有無窮多個(gè)元素,則稱此集合為無限集。不包括任何元素的集合稱為空集?？占ǔＳ芒俦硎?。如果M是ー個(gè)集合,a是集合M中的一個(gè)元素,則記作aGM,稱元素a屬于集合M;如果a不是集合M中的元素,則記作a￡M,稱元素a不屬于集合M。(1)列舉法用列舉法表示一個(gè)集合是將此集合中的元素全部列出來，或者列出若干項(xiàng)但能根據(jù)規(guī)律可知其所有的元素。例如:大于1而小于100的所有整數(shù)的集合A可以表示為A={2,3,4,...,99}(2)性質(zhì)敘述法用性質(zhì)敘述法表示一個(gè)集合是將集合中的元素所具有的屬性描述出來。例如:大于1而小于100的所有整數(shù)的集合A可以表示為A={a|l<a<10()的所有整數(shù)}設(shè)M與N為兩個(gè)集合,若M中的每個(gè)元素也為N的元素，則稱M為N的子集,記作MUN,若MUN且N中至少有一個(gè)元素a￡M,則稱M為N的真子集，記作MuN。基本運(yùn)算(1)兩個(gè)集合的并設(shè)有兩個(gè)集合M和N,它們的并集記作MUN,定義如下：MUN={a|aCM或a￡N}(2)兩個(gè)集合的交設(shè)有兩個(gè)集合M和N,它們的交集記作MAN,定義如下:MDN={a|aWM且aGN}兩個(gè)集合M和N的并、交均滿足交換律,即MUN=NUMMnN=NDM(3)兩個(gè)集合的差設(shè)有兩個(gè)集合M和N,它們的差集記作M-N,定義如下:M-N={a|aCNHlla￡N}兩個(gè)集合的差不滿足交換律,即M-N聲N-M對于集合的并、交、差有以下幾點(diǎn)基本性質(zhì):①結(jié)合律(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)映射映射的相關(guān)概念如下:①設(shè)A、B是兩個(gè)非空集，如果根據(jù)一定的法則f,對于每ー個(gè)xGA,在B中都有唯一確定的y與之對應(yīng)，則稱f為定義在A上而在B中取值的映射,記作f：A—B,并將x與y的關(guān)系記作y=f(x),x稱為自變元,y稱為在f作用下x的像;②設(shè)給定映射f：A-B,且B=f(A),若對于每個(gè)yCB僅有唯一的xWA使f(x)=y,則稱隋逆映射「;③若A、B兩個(gè)集合有ーー映射帝在,使f(A)=B,則稱A與B成——對應(yīng),A與B對等,記作A?B。集合的對等具有以下性質(zhì):自反性:A?A；對稱性:若A?B,則B?A；傳遞性：若A?B且B?C,則A?C。自然數(shù)集與數(shù)學(xué)歸納法由所有自然數(shù)組成的集合{1,2,3,…}稱為自然數(shù)集。自然數(shù)集是一個(gè)無限集。由自然數(shù)組成的集合均是自然數(shù)集的子集。自然數(shù)集的子集可以是有限集,也可以是無限集。它們具有如下性質(zhì):(1)在自然數(shù)集的任一非空子集M中,必定有一個(gè)最小數(shù);(2)設(shè)M是由自然數(shù)形成的集合,如果它含有1,2,...,k,并且當(dāng)它含有數(shù)n-1,n-2,...,n-k(n>k)時(shí),那么它含有所有的自然數(shù)，即M是自然數(shù)集。笛卡兒積0!xD2X???XD?={(ム,ム,…,ム)Id,eD,U=1,2,…,”}設(shè)有n個(gè)集合D“D2,...,D?,此n個(gè)集合的笛卡兒積定義為其中(4, d?)稱為n元組,d稱為n元組的第i個(gè)分量。由笛卡兒積的定義可以看出,n個(gè)集合的笛卡兒積是以n元組為元素的集合,而每ー個(gè)n元組中的第i個(gè)分量取自于第i個(gè)集合D,。?二元關(guān)系(1)笛卡兒積設(shè)M和N是兩個(gè)集合,則其笛卡兒積MxN={(x,y)|xGN^yGN)其中每ー個(gè)子集稱為在MxN上的ー個(gè)二元關(guān)系。如果M=N,則其笛卡兒積MxM={(x,y)Ix,y￡M}其中每ー個(gè)子集稱為在集合M上的ー個(gè)二元關(guān)系,簡稱為在集合M上的一個(gè)關(guān)系。(2)前后件、自反、對稱與傳遞設(shè)R是集合M上的一個(gè)關(guān)系：①如果(a,b)GR1則稱a是b的關(guān)于R的前件,b是a的關(guān)于R的后件;②如果對于每ー個(gè)aCM,都有(a,a)CR,則稱關(guān)系R是自反的:如果對于任何a^M,(a,a)GR均不成立,則稱關(guān)系R是非自反的；③如果（a,b）CR時(shí)必有（b,a）GR,則稱關(guān)系R是對稱的;④如果當(dāng)（a,b）WR且（b,c）eR時(shí)必有（a,c）eR,則稱關(guān)系R是傳遞的。（3）基與傳遞體設(shè)R是M上的ー個(gè)傳遞關(guān)系,且TUR,若對于任何（x,y）GR,在M中有元素x。,x.,x2,x?（n>l）滿足:Xo=X;xn=y；③（x?Xi）GT（i=l,2,n）則稱關(guān)系T是關(guān)系R的基,又稱關(guān)系R是關(guān)系T的傳遞體?；靖拍钏惴ㄊ侵附忸}方案準(zhǔn)確而完整的描述。算法具有如下基本特征:（1）能行性算法的能行性包括以下兩個(gè)方面:①算法中的每ー個(gè)步驟必須能夠?qū)崿F(xiàn);②算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。（2）確定性算法的確定性,是指算法中的每一個(gè)步驟都必須有明確的定義，不允許有模棱兩可的解釋,也不允許有多義性。（3）有窮性算法的有窮性,是指算法必須能在有限的時(shí)間內(nèi)做完,即算法必須能在執(zhí)行有限個(gè)步驟之后終止。算法的有窮性還應(yīng)包括合理的執(zhí)行時(shí)間的含義。（4）擁有足夠的情報(bào)ー個(gè)算法是否有效,還取決于為算法所提供的情報(bào)是否足夠。綜上所述，算法是ー組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,并且每一個(gè)規(guī)則都是有效的,且是明確的,此順序?qū)⒃谟邢薜拇螖?shù)內(nèi)終止。基本方法（1）列舉法列舉法的基本思想是:根據(jù)提出的問題,列舉所有可能的情況,并用問題中給定的條件檢驗(yàn)?zāi)男┦切枰?哪些是不需要的。列舉法的特點(diǎn)是算法比較簡單。但當(dāng)列舉的可能情況較多時(shí),執(zhí)行列舉算法的工作量將會很大,因此需要對算法進(jìn)行優(yōu)化。(2)歸納法歸納法的基本思想是,通過列舉少量的特殊情況,經(jīng)過分析，最后找出一般的關(guān)系。(3)遞推法遞推法是指從已知的初始條件出發(fā),逐次推出所要求的各中間結(jié)果和最后結(jié)果。(4)遞歸法遞歸法的基本思想是在解決了逐層分解到最后的那些最簡單的問題后,再沿著原來分解的逆過程逐步進(jìn)行綜合。遞歸分為直接遞歸與間接遞歸兩種。如果ー個(gè)算法P顯式地調(diào)用自己則稱為直接遞歸。如果算法P調(diào)用另ー個(gè)算法Q,而算法Q又調(diào)用算法P,則稱為間接遞歸調(diào)用。(5)分治法(減半遞推技術(shù))分治法,即對問題分而治之。工程上常用的分治法是減半遞推技術(shù)。"減半’’是指將問題的規(guī)模減半,而問題的性質(zhì)不變。"遞推''是指重復(fù)"減半''的過程。(6)回溯法通過對問題的分析,找出ー個(gè)解決問題的線索，然后沿著這個(gè)線索逐步試探。對于每ー步試探,若試探成功,就得到問題的解;若試探失敗,就逐步回退，換別的路線再進(jìn)行試探。復(fù)雜度分析算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。(1)時(shí)間復(fù)雜度①定義算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量?？陀^地反應(yīng)算法的效率可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的エ作量。而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù),即算法的工作量f(n)。其中n是問題的規(guī)模。②方法在同一問題規(guī)模下,如果算法執(zhí)行所需的基本運(yùn)算次數(shù)取決于某ー特定輸入時(shí),可以用以下兩種方法來分析算法的工作量。a.平均性態(tài)平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的帶權(quán)平均值來度量算法的工作量。設(shè)X是所有可能輸入中的某個(gè)特定輸入，P(X)是X出現(xiàn)的概率，t(X)是算法在輸入為X時(shí)所執(zhí)行的基本運(yùn)算次數(shù),則算法的平均性態(tài)定義為A(n)=/pェwd”b.最壞情況復(fù)雜性W(打)=max{^(x)}了《カ最壞情況分析是指在規(guī)模為n時(shí),算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為:(2)空間復(fù)雜度ー個(gè)算法的空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。一個(gè)算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù),則稱該算法是原地工作的。1.2課后習(xí)題詳解集合M={d”d2>d3?ム,ds,4}上的一個(gè)關(guān)系R如下:R={(di,d2),(d2,d&),(d5,d4),(di,d5),(di,th),(di,d6),(di,d3),(d3,d6)}試驗(yàn)證Ti={(d,,d2),(d2,0(),(di,d3),(&,&),(d5,&),(di,d5)}是R的具有6個(gè)元素的基,而T2={(d2,d4),(di,d3),(di,d2),(ds,ds)}不是R的基。答:對于T”顯然滿足T￡R,且對于關(guān)系R中的每一個(gè)二元組(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?,滿足基的三個(gè)條件。驗(yàn)證過程如下：由上可知,「是R的具有6個(gè)元素的基。對于T”由于（do,ds）0R,因此,T2不是R的基。設(shè)給定三個(gè)整數(shù)a,b,c,試寫出尋找其中數(shù)的ー個(gè)算法（用C/C++描述）,并分析在平均情況與最壞情況下,算法分別要進(jìn)行多少次比較?答:算法的C++描述如下:/'chl.qjp^includeciostrean^usingnamespacestd;intmid(inta,intb,intc)(intm;m=a; ,吁頁設(shè)a為中數(shù)if(m>=b)(if(m>=c)(if(b>=c)m=b;//b為中數(shù)elsem=c;〃c為中數(shù)))else(if(m<=c)(if(b>-c)m=ci〃c為中數(shù)elsem=b;//b為中數(shù)))return(m);j返回中數(shù)}假設(shè)a,b,c中的每一個(gè)數(shù)為中數(shù)的概率相等(均為1/3)。由于當(dāng)a為中數(shù)時(shí)需要比較2次2X(l/3)+3X(l/3)+3X(l/3)=8/3,b或c為中數(shù)時(shí)均需要比較3次,因此,在平均情況下上述算法所需要的比較次數(shù)為即在平均情況下，上述算法需要比較(8/3)次。在最壞情況下,上述算法需要比較3次(當(dāng)b或c為中數(shù)時(shí))。主函數(shù)例如下:intmain()(inta,b,c;cout?"input丄b,c="；cin?a?b?c;cout?"m="?mid(a,b,c)?endl;return0;}運(yùn)行結(jié)果如下(帶有下劃線的為鍵盤輸入)：inputa,b,c=483m=4利用減半遞推技術(shù),寫出求長度為n的數(shù)組中最大元素的遞歸算法(用C/C++描述)。設(shè)n=2k,其中kNl。答:利用減半遞推技術(shù),求數(shù)組中最大元素的遞歸過程如下:如果數(shù)組中只有一個(gè)元素,則該元素即是數(shù)組中最大的元素。否則將數(shù)組對分為前半部分和后半部分：用同樣的方法求數(shù)組前半部分的最大值maxi。用同樣的方法求數(shù)組后半部分的最大值max2〇若maxl>max2,則maxi為數(shù)組中的最大值;否則max2為數(shù)組中的最大值。算法的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);}}主函數(shù)例如下：intmain()(mta(16卜{15,6,4“521,7378「51.40コ6,43,49,6327};cout?"max-"maxa(i,1,16)?ajdl,return0;)運(yùn)行結(jié)果如下:max=78編寫二分法求方程實(shí)根的減半遞推算法(用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;取區(qū)間后半部分elseb=c;。取區(qū)間前半部分)c=(a*b)2;retum(c);)主函數(shù)例如下: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);)運(yùn)行結(jié)果如下: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主函數(shù)例如下:intmain(){intn;cout?T,mputnr；cin?n;queen(n);return0;)運(yùn)行結(jié)果如下:(帶有下劃線的為鍵盤愉入)inputn:44queenproblem24133142設(shè)有12個(gè)小球。其中11個(gè)小球的重量相同,稱為好球;有一個(gè)小球的重量與11個(gè)好球的重量不同(或輕或重),稱這個(gè)小球?yàn)閴那颉Ｔ嚲帉懇`個(gè)算法(用C/C++描述),用ー個(gè)無祛碼的天平稱3次找出這個(gè)壞球,并確定其比好球輕還是重。答:用ー個(gè)長度為12的整型數(shù)組A(1：12)模擬表示編號分別為1?12的12個(gè)小球,其中的元素值分別是各小球的重量。即在這個(gè)整型數(shù)組中,11個(gè)元素值是相同的,稱為好元素!只有一個(gè)元素的值與11個(gè)好元素值不同(其值或大或小),稱為壞元素。下面通過對數(shù)組中元素值的比較來找出這個(gè)壞元素。具體比較過程如下。首先將12個(gè)元素分成以下三組:第一組為A(1),A(2),A(3),A(4)四個(gè)元素;第二組為A(5),A(6),A(7),A(8)四個(gè)元素;第三組為A(9),A(10),A(11),A(12)四個(gè)元素。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)壞且輕根據(jù)表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[習(xí)+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[習(xí))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[習(xí))/聞3レa[4]中有壞且輕,或a[6]壞且重if(a[3]=a[4])retuni(6);/a(習(xí)壞且重elseif(a(3]>a[4])retum(-4); a[4]壞且輕elseretum(-3)iパa(bǔ)[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ー程序中,為了直觀起見,定義的數(shù)組長度為13,其中數(shù)組元素a[0]在程序中不用。主函數(shù)例如下:intmainO(ima口3]={0,5,5,5,555545555};cout?f,k=<*?al2(a)?endl:return0;)運(yùn)行結(jié)果如下:k=-8 表示數(shù)組中第S個(gè)元素為壞元素,即編號為8的小球?yàn)閴那?且比好球輕。第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2.I復(fù)習(xí)筆記ー、基本概念數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。(1)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。①數(shù)據(jù)的邏輯結(jié)構(gòu)包含的信息:a.表示數(shù)據(jù)元素的信息;b,表示各數(shù)據(jù)元素之間的前后件關(guān)系。②數(shù)據(jù)的邏輯結(jié)構(gòu)要素:a.數(shù)據(jù)元素的集合,通常用D來表示;b.D上的關(guān)系,它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系,通常記為R。即數(shù)據(jù)結(jié)構(gòu)可以表示成B={D,R}其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系,一般用二元表示。(2)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)(也稱數(shù)據(jù)的物理結(jié)構(gòu))。在數(shù)據(jù)的存儲結(jié)構(gòu)中,不僅要存放各數(shù)據(jù)元素的信息,還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的圖形表示(1)將數(shù)據(jù)集合D中的每ー個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，稱為數(shù)據(jù)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)；為了進(jìn)ー步表示各數(shù)據(jù)元素之間的前后件關(guān)系,將關(guān)系R中的每一個(gè)二元組,用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。(2)在數(shù)據(jù)結(jié)構(gòu)中,沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn);沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)(也稱為葉子結(jié)點(diǎn))。數(shù)據(jù)結(jié)構(gòu)的類型根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度,可將數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)與非線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表,與其相關(guān)的幾個(gè)性質(zhì)如下:(1)若一個(gè)線性結(jié)構(gòu)非空，則其有且只有一個(gè)根結(jié)點(diǎn),且每ー個(gè)結(jié)點(diǎn)最多有一個(gè)前件,最多有一個(gè)后件;(2)在ー個(gè)線性結(jié)構(gòu)中插入或刪除任何ー個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu):(3)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)滿足上述兩個(gè)條件,但當(dāng)在此數(shù)據(jù)結(jié)構(gòu)中插入或刪除任何ー個(gè)結(jié)點(diǎn)后就不滿足這兩個(gè)條件了,則該數(shù)據(jù)結(jié)構(gòu)不能稱為線性結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。ー個(gè)空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu),這要根據(jù)具體情況來確定。二、線性表及其順序存儲結(jié)構(gòu)線性表及其運(yùn)算(1)定義線性表是由n(n>0)個(gè)數(shù)據(jù)元素4,a”…，a”組成的ー個(gè)有限序列。矩陣也是ー個(gè)線性表,在矩陣中,既可以把每一行看成是一個(gè)數(shù)據(jù)元素，也可以把每一列看成是一個(gè)數(shù)據(jù)元素。其中,每ー個(gè)數(shù)據(jù)元素實(shí)際上又是ー個(gè)簡單的線性表。非空線性表有如下ー些結(jié)構(gòu)特征:①有且只有一個(gè)根結(jié)點(diǎn)a”它無前件;②有且只有一個(gè)終端結(jié)點(diǎn)あ,它無后件;③除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外,其他所有結(jié)點(diǎn)有且只有一個(gè)前件,也有且只有一個(gè)后件。(2)順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn):①線性表中所有元素所占的存儲空間是連續(xù)的;②線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。在程序設(shè)計(jì)語言中,通常定義ー個(gè)ー維數(shù)組來表示線性表的順序存儲空間。在用ー維數(shù)組存放線性表時(shí),該ー維數(shù)組的長度通常要定義得比線性表的實(shí)際長度略大,以便對線性表進(jìn)行各種運(yùn)算,特別是插入運(yùn)算。建立一個(gè)容量為m的空線性表的順序存儲空間的C++描述如下:templatecnpenameT> 模板聲明,T為類型參數(shù)voidinit_sq_LList(T*v,intmsmt*n)ヽnewT[m];動態(tài)申請存儲空間*n=0i ユ線性表長度置為〇return;）在上述描述中,T為線性表中元素的虛擬數(shù)據(jù)類型。要釋放線性表的順序存儲空間時(shí),可以用“delete[]v；（3）順序存儲下的插入運(yùn)算假設(shè)線性表的存儲空間為V（1：m）,線性表的長度為n（n<m）,插入的位置為i（i表示在第i個(gè)元素之前插入）。要插入新元素b,則插入的過程如下:①首先處理以下三種異常情況。a.當(dāng)存儲空間已滿（即n=m）時(shí)為“上溢”錯(cuò)誤，不能進(jìn)行插入，算法結(jié)束;b.當(dāng)i>n時(shí)，認(rèn)為在最后ー個(gè)元素之后插入;c,當(dāng)i<l時(shí),認(rèn)為在第1個(gè)元素之前插入;②從最后ー個(gè)元素開始,直到第i個(gè)元素,其中每ー個(gè)元素均往后移動ー個(gè)位置;③最后將新元素b插入到第i個(gè)位置,并且將線性表的長度增加1。線性表在順序存儲結(jié)構(gòu)下插入算法的C++描述如下:Iinclude<iostr￠am>usingnamespacestd;template<typen^meT> 〃模板聲明,T為類型參數(shù)voidins_sq_LLi8t(T*v,intm,int*n,inti,Tb)iintk;if(*n?-m) 〃存儲空間已満,上溢錯(cuò)誤{cout?Moverflow!\nw; return;}if(i>*n)i-?n+1; 〃默認(rèn)為在最后ー個(gè)元素之后插入ifリC)，7,? 〃蒙認(rèn)為在第一個(gè)元章之前揄入for(k*?n;k>-l；k--)v[k]?vlk-i]; 〃從最后ー個(gè)元米開始,直到第i個(gè)元索均往后移動ー個(gè)位臂v(i-lj-b; 〃插入新元素*n-?n*l; 〃線性或長度增加]1return;（4）順序存儲下的刪除運(yùn)算假設(shè)線性表的存儲空間為V（1：m）,線性表的長度為n（n<m）,刪除的位置為i,則刪除的過程如下:①首先處理以下兩種異常情況。a.當(dāng)線性表為空時(shí)為“下溢”錯(cuò)誤,不能進(jìn)行刪除,算法結(jié)束;b,當(dāng)i<l或i>n時(shí),認(rèn)為在最后ー個(gè)元素之后刪除。②從第i+1個(gè)元素開始,直到最后ー個(gè)元素，其中每ー個(gè)元素均依次往前移動ー個(gè)位置;③最后將線性表的長度減1。（5）順序表類下面的描述是將順序表的數(shù)據(jù)和基本操作（初始化、輸出、插入與刪除操作）封裝成一個(gè)sq丄List類:////模板聲明,數(shù)據(jù)元索虛擬類型為T〃順序表類〃數(shù)據(jù)成員〃存儲空間容依〃順序表長度〃順序表存儲空間首地址〃成員函數(shù)return;)〃建立空順序表,申請存儲空間〃順序輸出順序表中的元素與順序表長度〃檢測順序表的狀態(tài)//在表的指定元索前插入新元素//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(除指定元素〃建立空順序表〃存儲空間〃存儲空間容置〃動態(tài)申請存儲空間〃順序衰長度為。,即建立空順序表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;〃檢測順序表的狀態(tài)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；）〃躍認(rèn)為在敷后ー個(gè)元素之后捕人〃默認(rèn)為在第一個(gè)元素之前插入〃從最后ー個(gè)元家直到第i個(gè)元素均后移ー個(gè)位置〃摘入新元素〃順序表長度加1return；return；ノノ在翔洋表中髭除指定元素template<classT>voidsq^LList<T>?:del_sg_LList(inti)Iintk;if(nn?if(nn??0)〃順用表為空，下溢幡談Icout?"underflow!"?endl;return;}if 〃順序表中沒有這個(gè)元案(coutくく"Notthiselementinthelist!M?endl;return;)for(k?i;k<nn;k++)v[k-l)-v[k]; 〃從第i個(gè)元素直到最后ー個(gè)元素均前移ー個(gè)位置nn?nn-l; 〃順序表氏度減!return;利用順序表類中的成員函數(shù)flag_sq_LList()可以解決上溢錯(cuò)誤信息沒有返回給調(diào)用程序，調(diào)用程序無法處理的情況。成員函數(shù)flag.sq.LList()的功能是檢測順序表的當(dāng)前狀態(tài)〇若順序表滿,則返回函數(shù)值ー1；若順序表空,則返回函數(shù)值〇;正常情況則返回函數(shù)值1。棧及(1)定義棧實(shí)際上也是線性表,只不過是ー種特殊的線性表。其插入和刪除運(yùn)算都只在線性表的ー端進(jìn)行。在棧中,將允許插入與刪除的一端稱為棧頂,將不允許插入與刪除的一端稱為棧底。棧頂元素總是最后被插入的元素,也是最先被刪除的元素;棧底元素總是最先被插入的元素,也是最后オ被刪除的元素。即棧是按照“先進(jìn)后出‘‘(FirstlnLastOut,FILO)或“后進(jìn)先出''(LastInFirstOut,LIFO)的原則組織數(shù)據(jù)的,通常用指針top來指向棧頂?shù)奈恢?用指針bottom指向棧底。往棧中插入ー個(gè)元素稱為入棧運(yùn)算,從棧中刪除ー個(gè)元素稱為退棧運(yùn)算。棧頂指針t。p動態(tài)反映了棧中元素的變化情況。圖2-1是棧的示意圖。入棧退棧棧頂top入棧退棧棧頂top棧底bottom圖2-1棧的示意圖（2）順序存儲及運(yùn)算①概念在程序設(shè)計(jì)語言中,用ー維數(shù)組S（1：m）作為棧的順序存儲空間,其中m為棧的最大容量。通常,棧底指針指向?？臻g的低地址一端。S（bottom）通常為棧底元素（在棧非空的情況下），S（top）為棧頂元素。top=0表示棧空;top=m表示棧滿。template<t>penameT>模板聲明,T為類型參數(shù)voidimt_Stack（Tnimt叩）（$-newT（m],動態(tài)申調(diào)容量為m的存償空間?top-O； UJ頁指針晟為0?即?？誶eturn;}建立一個(gè)空棧的順序存儲空間（即初始化棧的順序存儲空間）的C++描述如下:當(dāng)要釋放棧的順序存儲空間時(shí),可以用“delete[]S；"。②入棧運(yùn)算入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。設(shè)棧順序存儲空間為S（1：m）,棧頂指針為top,入棧的元素為x。則入棧運(yùn)算的操作過程如下:a,首先判斷棧頂指針是否已經(jīng)指向存儲空間的最后ー個(gè)位置。如果是，則說明?？臻g已滿，不可能再進(jìn)行入棧操作,即為棧“上溢’’錯(cuò)誤。算法結(jié)束；b.將棧頂指針進(jìn)ー（即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;）在順序存儲結(jié)構(gòu)下入棧算法的C++描述如下:③退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給ー個(gè)指定的變量。設(shè)棧順序存儲空間為S（1：m）,棧頂指針為top。則退棧運(yùn)算的操作過程如下:a.首先判斷棧頂指針是否為0,如果是,則說明?？?不可能進(jìn)行退棧操作,即為?！跋乱纭卞e(cuò)誤,算法結(jié)束;b.將棧頂元素賦給ー個(gè)指定的變量;c,最后將棧頂指針退ー（即top減1）。④讀棧頂元素讀棧頂元素是指將棧頂元素賦給ー個(gè)指定的變量。設(shè)棧順序存儲空間為S（1：m）,棧頂指針為top。則讀棧頂元素的操作過程如下:a.首先判斷棧頂指針是否為0,如果是，則說明?？眨x不到棧頂元素,算法結(jié)束;b.將棧頂元素賦給指定的變量y。必須注意，這個(gè)運(yùn)算不刪除棧頂元素,只是將它的值賦給ー個(gè)變量。因此，在這個(gè)運(yùn)算中棧頂指針不會改變。在順序存儲結(jié)構(gòu)下讀棧頂元素算法的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)表達(dá)式的計(jì)算①概念計(jì)算機(jī)系統(tǒng)在具體處理表達(dá)式前,首先設(shè)置以下兩個(gè)棧:ー是運(yùn)算符棧,用于在表達(dá)式處理過程中存放運(yùn)算符。在開始時(shí),運(yùn)算符棧中先壓入一個(gè)表達(dá)式結(jié)束符“；”。二是操作數(shù)棧,用于在表達(dá)式處理過程中存放操作數(shù)。然后從左到右依次讀出表達(dá)式中的各個(gè)符號(運(yùn)算符或操作數(shù))。②原則每讀出一個(gè)符號按以下原則進(jìn)行處理:a.若讀出的是操作數(shù),則將該操作數(shù)壓入操作數(shù)棧，并依次讀下一個(gè)符號:b.若讀出的是運(yùn)算符，則作進(jìn)ー步判斷:第一,若讀出運(yùn)算符的優(yōu)先級大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級,則將讀出的運(yùn)算符壓入運(yùn)算符棧,并依次讀下ー個(gè)符號。第二,若讀出的是表達(dá)式結(jié)束符“；”，且運(yùn)算符棧棧頂?shù)倪\(yùn)算符也是表達(dá)式結(jié)束符“；”，則表達(dá)式處理結(jié)束,最后的計(jì)算結(jié)果在操作數(shù)棧的棧頂位置。第三，若讀出運(yùn)算符的優(yōu)先級不大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級,則從操作數(shù)棧連續(xù)退出兩個(gè)操作數(shù),并從運(yùn)算符棧退出ー個(gè)運(yùn)算符,然后作相應(yīng)的運(yùn)算(運(yùn)算符為剛從運(yùn)算符棧退出的運(yùn)算符,運(yùn)算對象為剛從操作數(shù)棧退出的兩個(gè)操作數(shù)),并將運(yùn)算結(jié)果壓入操作數(shù)棧。在這種情況下,當(dāng)前讀出的運(yùn)算符下次將重新考慮(即不再讀下ー個(gè)符號)。(4)遞歸的實(shí)現(xiàn)在遞歸函數(shù)的執(zhí)行過程中,需要用棧來記憶各層調(diào)用中的參數(shù)，以便在逐層返回時(shí)恢復(fù)這些參數(shù)繼續(xù)進(jìn)行處理。在遞歸函數(shù)開始執(zhí)行時(shí),棧為空,隨著遞歸調(diào)用,逐步將各層中的輸入?yún)?shù)進(jìn)棧,在逐層返回時(shí)，又依次從棧中取出這些參數(shù)打印輸出。隊(duì)列(1)定義隊(duì)列(equeue)是指允許在一端進(jìn)行插入,而在另一端進(jìn)行刪除的線性表。允許插入的ー端稱為隊(duì)尾,通常用ー個(gè)稱為尾指針(rear)的指針指向隊(duì)尾元素;允許刪除的一端稱為排頭或隊(duì)頭,通常也用一個(gè)排頭指針(front)指向排頭元素的前ー個(gè)位置。隊(duì)列稱為“先進(jìn)先出''(FirstInFirstOut,FIFO)或“后進(jìn)后出’’(LastInLastOut,LILO)的線性表,它體現(xiàn)了“先來先服務(wù)''的原則。在隊(duì)列中,隊(duì)尾指針rear與排頭退隊(duì)ABCDEF入隊(duì)指針front共同反映了隊(duì)列中元素動態(tài)變化的情況。圖2-2是具有6個(gè)元素的隊(duì)列示意圖。圖2-2具有6個(gè)元素的隊(duì)列示意圖往隊(duì)列的隊(duì)尾插入ー個(gè)元素稱為入隊(duì)運(yùn)算,從隊(duì)列的排頭刪除ー個(gè)元素稱為退隊(duì)運(yùn)算。圖2-3是在隊(duì)列中進(jìn)行插入與刪除的示意圖。由圖2-3可以看出，在隊(duì)列的末尾插入ー個(gè)元素只涉及隊(duì)尾指針rear的變化，而要?jiǎng)h除隊(duì)列中的排頭元素只涉及排頭指針front的變化。圖2?3隊(duì)列不意圖（2）循環(huán)隊(duì)列及其運(yùn)算①概念循環(huán)隊(duì)列是將隊(duì)列存儲空間的最后ー個(gè)位置繞到第一個(gè)位置,形成邏輯上的環(huán)狀空間,供隊(duì)列循環(huán)使用。用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素,用排頭指針front指向排頭元素的前ー個(gè)位置,從排頭指針指向的后ー個(gè)位置直到隊(duì)尾指針指向的位置之間所有的元素均為隊(duì)列中的元素。循環(huán)隊(duì)列的初始狀態(tài)為空,即rear=front=m。循環(huán)隊(duì)列主要有兩種基本運(yùn)算:入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。每進(jìn)行一次入隊(duì)運(yùn)算,隊(duì)尾指針就進(jìn)ー。當(dāng)隊(duì)尾指針rea尸m+1時(shí)，則置reak1。每進(jìn)行ー次退隊(duì)運(yùn)算,排頭指針就進(jìn)ー。當(dāng)排頭指針front=m+l時(shí),則置front=l。tempiate<typenameT> 〃模板聲明?T為類型參數(shù)voidinit_Queue（T**front?int*rear?int*s）（q=newT[m];*front=mj*rear=m；*s=0?return；}建立一個(gè)循環(huán)隊(duì)列順序存儲空間算法的C++描述如下:當(dāng)要釋放循環(huán)隊(duì)列的順序存儲空間時(shí),可以用“deleteq；"。②入隊(duì)運(yùn)算入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。設(shè)循環(huán)隊(duì)列順序存儲空間為Q（I：m）,隊(duì)尾指針為rear;排頭指針為front;標(biāo)志s入隊(duì)的元素為x。則入隊(duì)運(yùn)算的操作過程如下:a.首先判斷循環(huán)隊(duì)列是否滿,當(dāng)循環(huán)隊(duì)列非空（s=l）且隊(duì)尾指針等于排頭指針時(shí),說明循環(huán)隊(duì)列已滿,不能進(jìn)行入隊(duì)運(yùn)算，即為“上溢”,此時(shí)算法結(jié)束；b,將隊(duì)尾指針進(jìn)ー（即rear=rear+l）,并當(dāng)reakm+1時(shí)置rear=l；c.最后將新元素x插入到隊(duì)尾指針指向的位置,并且置循環(huán)隊(duì)列非空標(biāo)志。循環(huán)隊(duì)列入隊(duì)運(yùn)算的C++描述如下:#include<iostrea(n>usingnamespacestd;template<typenameT> 〃模板聲明,T為類型參數(shù)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;③退隊(duì)運(yùn)算退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出ー個(gè)元素并賦給指定的變量。設(shè)循環(huán)隊(duì)列順序存儲空間為Q(l：m),隊(duì)尾指針為rear,排頭指針為front,標(biāo)志為s,則退隊(duì)運(yùn)算的操作過程如下:a.首先判斷循環(huán)隊(duì)列是否為空,當(dāng)循環(huán)隊(duì)列為空(s=0)時(shí),不能進(jìn)行退隊(duì)運(yùn)算,即為“下溢”,此時(shí)算法結(jié)束;b.將排頭指針進(jìn)ー(即(front=front+l),并當(dāng)front=m+l時(shí)置front=l；c.再將排頭指針指向的元素賦給指定的變量;d.最后判斷退隊(duì)后循環(huán)隊(duì)列是否為空,當(dāng)front=rear時(shí),置循環(huán)隊(duì)列空標(biāo)志(即s=0)。循環(huán)隊(duì)列退隊(duì)運(yùn)算的C++描述如下:#include<iostream)usingnamespacestd;template<typenameT> 〃模板聲明,T為類型參數(shù)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;④循環(huán)隊(duì)列類下面的描述是將循環(huán)隊(duì)列的數(shù)據(jù)和基本操作（初始化、入隊(duì)、退隊(duì)、輸出排頭與隊(duì)尾指針以及循環(huán)隊(duì)列中的元素）封裝成一個(gè)循環(huán)隊(duì)列類sq-Queue：//模板聲明,//模板聲明,數(shù)據(jù)元素虛擬類型為T〃數(shù)據(jù)成員〃存儲空間容址//排頭指針〃隊(duì)尾指針〃標(biāo)志//循環(huán)隊(duì)列存儲空間首地址〃成員函數(shù)〃構(gòu)造函數(shù),建立空桶環(huán)隊(duì)列//輸出排頭與隊(duì)尾指針以及隊(duì)中元素//檢測徳環(huán)隊(duì)列的狀態(tài)〃人隊(duì)//退隊(duì)〃存儲空間容量//動態(tài)申請存儲空間return;)//sq_Queue.h#include<iostream>usingnamespacestd;〃定義循環(huán)隊(duì)列類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的空循環(huán)隊(duì)列template<classT>sq_Queue<T>::sq_Queue(intm)(mm?m;q?newT(mm];front=mm;rear=mm;s?0;return;)〃輸出排頭與隊(duì)尾指針以及隊(duì)中元素template<classT>voidsq_Queue<T>::prt_sq_Queue()(inti;cout?"front，w?front?endl;cout?"rear，"?rear?endl;if(s,?0){coutく<”隊(duì)列空!**<<endl;i=front;do{i?i+1；if(i==mm+l)is1;cout?q[i-l]?endl;}while(i!-rear);return;//檢測循環(huán)隊(duì)列的狀態(tài)template<classT>intsqQueue<T>::flag_sq_Queue(){if(1)is(rear??front))return(-1);if(s-=0)return(0);return(1);〃存儲空間已満,返回一1〃循環(huán)隊(duì)列為空,返回O〃正常返回1//人隊(duì)template<classT>voidsq_Queue<T>::ins_sq_Queue(Tx){if((s-?l)&&(rear?-front))//存儲空間已滿,上溢錯(cuò)誤(cout?MQueue_overflow!M?endl;return;}rear=rear+l;〃隊(duì)尾指針進(jìn)ーif(rear=?mm>1)rear-1;q(rear-l]=x;s?l;〃新元素人隊(duì)〃人隊(duì)后隊(duì)列非空return;〃退隊(duì)template<classT>Tsq_Queue<T>::del_sq_Queue(){Ty;if(s?=0)(cout?MQueue_underflow!H?endl;front?front+1;〃隊(duì)列為空,下溢錯(cuò)誤return(0);)〃排頭指針進(jìn)ーif(front--mm+1)front-1;y=q[front-1J;if(front=arear)s=0;〃將退隊(duì)元索賦給變盤return(y);〃返冋退隊(duì)的元素三、線性鏈表基本概念（1）定義在線性鏈表中,用ー個(gè)專門的指針HEAD指向線性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。線性表中最后ー個(gè)元素沒有后件,因此,線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨ㄓ肗ULL或。HEAD一數(shù)據(jù)]丄 數(shù)據(jù)2丄 ?...—數(shù)據(jù)n]NULL表示），表示鏈表終止。線性鏈表的邏輯結(jié)構(gòu)如圖2-4所示。圖2-4線性鏈表的邏輯結(jié)構(gòu)一般情況下,各結(jié)點(diǎn)存儲序號是不連續(xù)的,并且各結(jié)點(diǎn)的位置關(guān)系與邏輯關(guān)系也不一致,而數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來指示。指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為頭指針。當(dāng)HEAD=NULL（或〇）時(shí),稱為空表。如下C++程序段定義了一種結(jié)點(diǎn)類型node;并定義了該類型的指針變量p（用于指向該種結(jié)點(diǎn)類型的存儲空間的首地址）;最后申請分配該結(jié)點(diǎn)類型的ー個(gè)存儲空間,其首地址存structnode{intd;〃定義結(jié)點(diǎn)類型〃數(shù)據(jù)域node*next;)；intmain(){node*p;〃指針域//定義該類型的指針變量Pp=newnode;〃申請分配結(jié)點(diǎn)存儲空間deletep;//釋放結(jié)點(diǎn)存儲空間return0;放在指針變量P中。單鏈表中,只能向后尋找后件結(jié)點(diǎn),無法向前尋找前件結(jié)點(diǎn),因此會帶來極大不便。為了彌補(bǔ)線性單鏈表的這個(gè)缺點(diǎn),對線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針。其中,一個(gè)稱為左指針(Llink),用以指向其前件結(jié)點(diǎn):另一個(gè)稱為右指針(Rlink),用以指向其后件結(jié)HEADHEAD點(diǎn)。這樣的線性鏈表稱為雙向鏈表，其邏輯狀態(tài)如圖2-5所示。圖2-5雙向鏈表示意圖(2)優(yōu)缺點(diǎn)線性表的順序存儲結(jié)構(gòu)具有簡單、運(yùn)算方便等優(yōu)點(diǎn),特別是對于小線性表或長度固定的線性表,采用順序存儲結(jié)構(gòu)的優(yōu)越性更為突出。但是,線性表的順序存儲結(jié)構(gòu)存在以下幾方面的缺點(diǎn):①插入與刪除運(yùn)算的效率都很低;②在順序存儲結(jié)構(gòu)下,線性表的存儲空間不便于擴(kuò)充;③線性表的順序存儲結(jié)構(gòu)不便于對存儲空間進(jìn)行動態(tài)分配。線性鏈表的插入與刪除(1)插入假設(shè)可利用棧與線性鏈表如圖2-6(a)所示?，F(xiàn)在要在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入一個(gè)新元素b。(a)原來的可利用棧與線性鏈表(b)從可利用桟取得結(jié)點(diǎn)p.在線性鏈表中找到包含元素x的前ー個(gè)結(jié)點(diǎn)g(c)p插入到g之后圖2-6線性鏈表的插入其插入過程如下:①從可利用棧取得一個(gè)結(jié)點(diǎn),設(shè)該結(jié)點(diǎn)號為P;并置結(jié)點(diǎn)P的數(shù)據(jù)域?yàn)椴迦氲脑刂礲,即V(p)=b。經(jīng)過這ー步后,可利用棧的狀態(tài)如圖2-6(b)所示。②在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn),設(shè)該結(jié)點(diǎn)的存儲序號為q。線性鏈表如圖2-6(b)所示。③最后將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。為了實(shí)現(xiàn)這ー步,只要改變以下兩個(gè)結(jié)點(diǎn)的指針域內(nèi)容:a.使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)(即結(jié)點(diǎn)q的后件結(jié)點(diǎn)),即NEXT(p)=NEXT(q)；b.使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p,即NEXT(q尸p。這ー步的結(jié)果如圖2-6(c)所示。此時(shí)插入就完成了。(2)刪除假設(shè)可利用棧與線性鏈表如圖2-7(a)所示?，F(xiàn)在要在線性鏈表中刪除包含元素x的結(jié)點(diǎn)。其刪除過程如下:①在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn),設(shè)該結(jié)點(diǎn)序號為q,則包含元素x的結(jié)點(diǎn)序號p=NEXT(q)；②將結(jié)點(diǎn)q后的結(jié)點(diǎn)P從線性鏈表中刪除,即讓結(jié)點(diǎn)q的指針指向包含元素x的結(jié)點(diǎn)p的指針指向的結(jié)點(diǎn),即NEXT(q)=NEXT(p)。經(jīng)過上述兩步后,線性鏈表如圖2-7(b)所示。③將包含元素x的結(jié)點(diǎn)p送回可利用棧。經(jīng)過這ー步后,可利用棧的狀態(tài)如圖2-(c)將被刪除的結(jié)點(diǎn)ハ送回可利用棧后7(c)所示。此時(shí),線性鏈表的刪除運(yùn)算完成。圖2-7線性鏈表的刪除帶鏈的棧與隊(duì)列(1)帶鏈的棧棧也是線性表,也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。帶鏈的?？梢杂脕硎占?jì)算機(jī)存儲空間中所有空閑的存儲結(jié)點(diǎn),這種帶鏈的棧稱為可利用棧。計(jì)算機(jī)中的所有可利用空間都可以以結(jié)點(diǎn)為單位鏈接在可利用棧中。隨著其他線性鏈表中結(jié)點(diǎn)的插入與刪除,可利用棧處于動態(tài)變化之中,即可利用棧經(jīng)常要進(jìn)行退棧與入棧操作。￠2)帶鏈的隊(duì)列與順序隊(duì)列ー樣,帶鏈隊(duì)列的基本操作有以下幾個(gè):①隊(duì)列的初始化,即建立一個(gè)空隊(duì)列的順序存儲空間;

②入隊(duì)運(yùn)算,指在循環(huán)隊(duì)列的隊(duì)尾加入ー個(gè)新元素;③退隊(duì)運(yùn)算,指在循環(huán)隊(duì)列的排頭位置退出ー個(gè)元素并賦給指定的變量。循環(huán)鏈表通過循環(huán)鏈表(CircularLinkedList)的結(jié)構(gòu)可以解決空表與非空表運(yùn)算不統(tǒng)一的問題。圖2-8是循環(huán)鏈表的示意圖。其中圖2-8(a)是ー個(gè)非空的循環(huán)鏈表,圖2-表頭結(jié)點(diǎn)HEAD表頭結(jié)點(diǎn)HEAD(a)非空循環(huán)鮭表HEAD表頭結(jié)點(diǎn)(b)空循環(huán)性表8(b)是ー個(gè)空的循環(huán)鏈表。在此,空表與非空表是針對線性表中的元素而言。圖2-8循環(huán)鏈表的邏輯狀態(tài)在實(shí)際應(yīng)用中,循環(huán)鏈表與線性單鏈表相比主要有以下兩個(gè)方面的優(yōu)點(diǎn):(1)在循環(huán)鏈表中,只要指出表中任何ー個(gè)結(jié)點(diǎn)的位置,就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn),而線性單鏈表做不到這一點(diǎn)；(2)由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn),因此,在任何情況下,循環(huán)鏈表中至少有ー個(gè)結(jié)點(diǎn)存在,從而使空表與非空表運(yùn)算的統(tǒng)ー。以下描述的是循環(huán)鏈表類。//linked_Clist.h#include<iostream>usingnamespacestd;〃定義結(jié)點(diǎn)類型template<classT>structnode{Td;node*next;}；〃定義循環(huán)鋅表類template<classT>classlinkedCList{private:node<T>*head;public:linked_CList();voidprt_linked_CList();voidins_linked_CList(TrT);intdel_linked_CList(T);)；〃建立空循環(huán)鏈表template<classT>linked_CList<T>::linked_CList(){node<T>*p;p-newnode<T>;p->d=0;p->next?p;head=p;〃數(shù)據(jù)元素虛擬類型為T//模板聲明,數(shù)據(jù)元素虛擬類型為T〃數(shù)據(jù)成員//循環(huán)鏈表頭指針〃成員函數(shù)〃構(gòu)造函數(shù),建立空循環(huán)鏈表〃掃描輸出循環(huán)能表中的元素〃在包含元素x的結(jié)點(diǎn)前插入新元素b〃刪除包含元素X的結(jié)點(diǎn)〃申請一個(gè)表頭結(jié)點(diǎn)return;//掃描輸出循環(huán)鏈表中的元素template<classT>voidlinked_CList<T>::prt_linked_CList()(node<T>*p;p?head->next;if(p??head){cout<<”空循環(huán)鏈表!”<<endl;return;)do{cout?p->d?endl;p-p->next;)while(p!-head);return;}〃在包含元素x的結(jié)點(diǎn)前插入新元素btemplate<classT>voidlinked_CList<T>::ins_linked_CList(Tx,Tb){node<T>?p,?q;p-newnode<T>; 〃申請ー個(gè)新結(jié)點(diǎn)p->d-b; 〃置新結(jié)點(diǎn)的數(shù)據(jù)域q?head;while((q->next!-head)&&(((q->next)->d)!-x))q-q->next; 〃尋找包含元素x的前ー個(gè)結(jié)點(diǎn)qp->next-q->next;q->next-p; 〃新結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后return;)//刪除包含元素X的結(jié)點(diǎn)元賣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的前ー個(gè)結(jié)點(diǎn)qif(q->next=?head)return(0); 〃循環(huán)鏈表中無刪除的元素p-q*>next;q*>next-p->next; //刪除q的下ー個(gè)結(jié)點(diǎn)pdeletep; 〃糅放結(jié)點(diǎn)p的存儲空間return(1);多項(xiàng)式的表示與運(yùn)算(1)表示Prt(x)=anxn+an-\Xn~x+…+ゐよ+。0設(shè)多項(xiàng)式為這種表達(dá)式中,即使某次項(xiàng)的系數(shù)為0時(shí)也必須存儲,浪費(fèi)了存儲空間。可以采用鏈表形式來表示,即忽略系數(shù)為0的項(xiàng),僅對非0項(xiàng)用結(jié)點(diǎn)表示。多項(xiàng)式中非零系數(shù)項(xiàng)所構(gòu)成的結(jié)點(diǎn)如圖2-9所示。其中數(shù)據(jù)域有兩項(xiàng):EXP(i)表示該項(xiàng)的指數(shù)值,COEF(i)表示該項(xiàng)的系數(shù)。EXP⑴COEF(i)NEXT(i)指針域NEXT(i)表示下一個(gè)非零系數(shù)項(xiàng)的結(jié)點(diǎn)序號。圖2-9多項(xiàng)式非零系數(shù)項(xiàng)的結(jié)點(diǎn)結(jié)構(gòu)在用循環(huán)鏈表表示時(shí)，其表頭結(jié)點(diǎn)中的指數(shù)域?yàn)椹`1,系數(shù)域?yàn)槿我?。由于多?xiàng)式中的指數(shù)不可能為負(fù)數(shù),因此很容易將表頭結(jié)點(diǎn)與其他結(jié)點(diǎn)區(qū)分開。(2)多項(xiàng)式鏈表的生成生成一個(gè)多項(xiàng)式鏈表可以有以下兩種方法:①從鍵盤輸入多項(xiàng)式鏈表;②由數(shù)組復(fù)制多項(xiàng)式鏈表。(3)多項(xiàng)式鏈表的釋放從表頭結(jié)點(diǎn)開始,逐步釋放鏈表中的各結(jié)點(diǎn)。但必須注意,多項(xiàng)式鏈表的釋放只是刪除了多項(xiàng)式鏈表中的元素結(jié)點(diǎn),而不刪除表頭結(jié)點(diǎn)。即經(jīng)過這個(gè)操作后,多項(xiàng)式變成一個(gè)空的循環(huán)鏈表。(4)多項(xiàng)式的輸出從表頭結(jié)點(diǎn)后的第一個(gè)結(jié)點(diǎn)開始，以數(shù)偶形式順鏈輸出各結(jié)點(diǎn)中的指數(shù)域與系數(shù)域的內(nèi)容。(5)多項(xiàng)式的相加多項(xiàng)式相加的運(yùn)算只要從兩個(gè)多項(xiàng)式鏈表的第一個(gè)元素結(jié)點(diǎn)開始檢測,對每一次的檢測結(jié)果做如下運(yùn)算:①若兩個(gè)多項(xiàng)式中對應(yīng)結(jié)點(diǎn)的指數(shù)值相等,則將它們的系數(shù)值相加;如果相加結(jié)果不為零,則形成一個(gè)新結(jié)點(diǎn)后鏈入頭指針為CH的鏈表末尾;然后再檢測兩個(gè)鏈表中的下ー個(gè)結(jié)點(diǎn)。②若兩個(gè)多項(xiàng)式中對應(yīng)結(jié)點(diǎn)的指數(shù)值不相等，則復(fù)抄指數(shù)值大的那個(gè)結(jié)點(diǎn)中的指數(shù)值與系數(shù)值,形成一個(gè)新結(jié)點(diǎn)后鏈入頭指針為CH的鏈表末尾;然后再檢測指數(shù)值小的鏈表中的當(dāng)前結(jié)點(diǎn)與指數(shù)值大的鏈表中的下一個(gè)結(jié)點(diǎn)。重復(fù)以上過程直到兩個(gè)鏈表中的所有結(jié)點(diǎn)均檢測完為止。(6)多項(xiàng)式的相乘多項(xiàng)式相乘的基本方法如下:C(x)=とXクル產(chǎn)"，’夕對于多項(xiàng)式Am(X)中每ー項(xiàng)與多項(xiàng)式&(X)相乘,且將結(jié)果逐步累加,即四、線性表的索引存儲結(jié)構(gòu)概念索引存儲的基本思想是:將具有n個(gè)結(jié)點(diǎn)的線性表按性質(zhì)劃分成m個(gè)子表，然后分別存儲此m個(gè)子表。另外再設(shè)立一個(gè)具有m個(gè)結(jié)點(diǎn)的索引表,其每ー個(gè)結(jié)點(diǎn)存儲ー個(gè)子表性質(zhì)的有關(guān)信息以及子表中第一個(gè)結(jié)點(diǎn)的存儲地址。對于同一個(gè)索引表中的各結(jié)點(diǎn)結(jié)構(gòu)應(yīng)相同。(1)線性表的劃分將線性表L劃分成m個(gè)子表し,し,…,し、的基本方法是:對線性表L中的每個(gè)結(jié)點(diǎn)元素&的關(guān)鍵字k,計(jì)算其索引函數(shù)值,將所有索引函數(shù)值為i的結(jié)點(diǎn)元素均歸并到第j個(gè)子表し中。經(jīng)過劃分后,m個(gè)子表し,し,…,し、、中的結(jié)點(diǎn)結(jié)合在ー起正好是線性表L中的全部結(jié)點(diǎn)。處理具有性質(zhì)P的結(jié)點(diǎn),不必查遍原線性表L中的全部結(jié)點(diǎn),而只需要直接對具有性質(zhì)P的子表進(jìn)行處理就行了,提高查找效率。（2）索引存儲的方式索引存儲包括索引表的存儲與各個(gè)子表的存儲。如果采用順序分配與鏈?zhǔn)椒峙涞拇鎯Y(jié)構(gòu),則共有4種索引存儲的方式:“順序一索引ー順序’’存儲方式；“順序一索弓I-鏈接''存儲方式;“鏈接一索弓、順序''存儲方式;“鏈接-索引ー鏈接''存儲方式?！癆-索引-B”存儲方式是指用存儲結(jié)構(gòu)A方式存儲索引表,用存儲結(jié)構(gòu)B方式存儲各子表。①“順序一索引ー順序”存儲方式在“順序一索引ー順序''存儲方式中,索引表與各子表均用順序分配的方式來表示,有下面兩個(gè)結(jié)構(gòu)特點(diǎn);a.索引表中的每ー個(gè)結(jié)點(diǎn)均設(shè)有若干個(gè)數(shù)據(jù)項(xiàng),用以表示相應(yīng)子表的有關(guān)信息;b.每個(gè)結(jié)點(diǎn)中還設(shè)有一個(gè)指針項(xiàng),用以指示相應(yīng)子表的第一個(gè)結(jié)點(diǎn)的存儲序號。其在應(yīng)用中常具備如下3個(gè)特點(diǎn):a.在這種存儲方式中，每ー個(gè)子表都是順序分配的,但各個(gè)子表在存儲空間中的前后位置無關(guān)緊要,并且各子表之間的存儲地址也不一定是連續(xù)的；b.對于順序存儲的線性表來說,除了需要指出第一個(gè)結(jié)點(diǎn)的存儲序號外,它的長度有時(shí)是必不可少的,特別是對于查找操作尤為突出;c.這種存儲方式只有在線性表為固定的情況下オ比較合適。②“順序一索引ー鏈接”存儲方式“順序一索引ー鏈接''存儲方式是指用順序分配的方法存儲索引表,而用鏈?zhǔn)椒峙涞姆椒ù鎯Ω髯颖怼Ｔ谶@種存儲方式中,各子表均為線性鏈表,而每ー個(gè)線性鏈表的頭指針是索引表中對應(yīng)結(jié)點(diǎn)的指針項(xiàng)。圖2-10為這種存儲結(jié)構(gòu)的示意圖。數(shù)據(jù)表指針表圖2-10"順序一索引ー鏈接’‘存儲結(jié)構(gòu)示意圖(3)多重索引存儲結(jié)構(gòu)如果索引表本身又是索引存儲結(jié)構(gòu),則稱為二重索引存儲結(jié)構(gòu)。索引存儲結(jié)構(gòu)嵌套多層形成多重索引結(jié)構(gòu),適當(dāng)?shù)那短资褂盟饕Y(jié)構(gòu)可以有效地提髙查找效率。五、數(shù)組順序存儲結(jié)構(gòu)(1)以行為主的順序存儲二維數(shù)組以行為主的順序存儲是指將數(shù)組中的元素一行接一行地順序存儲在計(jì)算機(jī)的連續(xù)存儲空間中。在二維數(shù)組的以行為主順序存儲中，假設(shè)數(shù)組中第一個(gè)元素(即a”)在計(jì)算機(jī)中的存儲地址為ADR(a,1),且每ー個(gè)元素占L個(gè)字節(jié),則數(shù)組中的元素a"在計(jì)算機(jī)中的存儲地址為ADR(a?)=ADR(a,1)+[(i-1)n+j-l]Lo其中iWigm,10Wn。(2)以列為主的順序存儲二維數(shù)組以列為主的順序存儲是指將數(shù)組中的元素一列接一列地順序存儲在計(jì)算機(jī)的連續(xù)存儲空間中。在二維數(shù)組的以列為主順序存儲中，假設(shè)數(shù)組中第一個(gè)元素(即a”)在計(jì)算機(jī)中的存儲地址為ADR(a,1),且每ー個(gè)元素占L個(gè)字節(jié),則數(shù)組中的元素a"在計(jì)算機(jī)中的存儲地址為ADR(aij)=ADR(a,,)+[(j-1)m+i-l]L。其中Igigm,l<j<rio規(guī)則矩陣的壓縮規(guī)則矩陣是指矩陣中非零元素的分布是有規(guī)律的。壓縮存儲是指在存儲ー個(gè)規(guī)則矩陣時(shí),只需存儲非零元素即可,而對于大部分的零元素或者重復(fù)的非零元素不必存儲。(1)下三角矩陣的壓縮存儲設(shè)n階下三角矩陣為開辟ー個(gè)長度為n(n+l)/2的ー維數(shù)組B,然后一行接一行地依次存放A中下三角部分的元素。經(jīng)壓縮后,存放在ー維數(shù)組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用ー維數(shù)組壓縮存放ド三角矩陣顯然,下三角矩陣A用ー維數(shù)組B表示后,可以按如下原則訪問A中的第i行、第j列的元素［寅一1)/2+，］［O j>i下三角矩陣A也可以用以列為主的方式壓縮存儲在ー維數(shù)組B中,其存儲形式如圖2-11(b)所示。在以列為主壓縮存儲下三角矩陣A的情況下,訪問下三角矩陣A中第i行、第j列元素為的公式為0,=Io i>i對下三角矩陣采用以行為主的壓縮方法更為方便,但如果要對上三角矩陣進(jìn)行壓縮存儲,則采用以列為主比較方便。在以列為主壓縮存儲上三角矩陣A的情況下,訪問上三角矩陣■[0 j<iへ?(ぬ。ーD/2+口j>iA中第i行、第j列元素aM的公式為(2)對稱矩陣的壓縮存儲即=レ[內(nèi)-1)/2+門y>i在以行為主壓縮存儲對稱矩陣A的情況下,訪問對稱矩陣A中第i行、第j列元素為的公式為(3)三對角矩陣的壓縮存儲n階三對角矩陣的形式為對于n階三對角矩陣,用ー個(gè)長度為3n-2的ー維數(shù)組存放三條對角線上的元素,其存儲形式如圖2-12所示。lO jVi-1或ノ）i+1在用ー維數(shù)組B以行為主存放三對角矩陣A中的元素a.時(shí),其訪問公式為

10 j<i?1或>>i+l在用一維數(shù)組B以列為主存放三對角矩陣A中的元素衡時(shí),其訪問公式為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用ー維數(shù)組壓縮存放三對角矩陣一般稀疏矩陣的表示如果ー個(gè)矩陣中絕大多數(shù)的元素值為零,只有很少的元素值非零,則稱該矩陣為稀疏矩陣。(1)三列二維數(shù)組表示在壓縮存儲形式中,每ー個(gè)非零元素應(yīng)包括其所在的行號i、列號j和值V。即每ー個(gè)非零元素可以用下列三元組表示:(i,j,V)為了表示的唯一性,除了每ー個(gè)非零元素用ー個(gè)三元組表示外,在所有表示非零元素的三元組之前再添加一組信息:(I,J,t)其中I表示稀疏矩陣的總行數(shù),J表示稀疏矩陣的總列數(shù)，t表示稀疏矩陣中非零元素的個(gè)數(shù)。通常將這些三元組組織成三列二維表格的形式,一般又表示成三列二維數(shù)組的形式，并簡1231788"718388'3121333181143193\95457B=45765765767642642866366335_97357(a)稀疏矩陣的三列二維表格(b)稀疏矩陣的三列二維數(shù)組稱為三列二維數(shù)組。圖2-13為稀疏矩陣A的三列二維表示。圖2-13稀疏矩陣的表示例(2)線性鏈表表示及運(yùn)算表示稀疏矩陣中各非零元素信息的三元組可以組織成線性鏈表的形式。當(dāng)產(chǎn)生新的非零元素時(shí),可以直接申請ー個(gè)存放三元組的結(jié)點(diǎn)，然后順序鏈接到線性鏈表中。如果通過運(yùn)算,原來的非零元素變成了零元素,則可以從線性鏈表中刪除這個(gè)結(jié)點(diǎn)。(3)十字鏈表①基本概念用十字鏈表結(jié)構(gòu)表示稀疏矩陣時(shí),矩陣中的每ー個(gè)非零元素對應(yīng)ー個(gè)結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)有五個(gè)域：行域、列域、值域、向下域與向右域,如圖2-

14所示。其中:行域與列域分別存放非零元素所在的行號與列號,值域存放非零元素的值,向下域指示同一列中下ー個(gè)非零元素的存儲結(jié)點(diǎn)序號,向右域指示同一行中下ー個(gè)非零row col val行域列域值域向下域向右域down riglit元素的存儲結(jié)點(diǎn)序號。圖2-14十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)②特點(diǎn)用十字鏈表表示稀疏矩陣的結(jié)構(gòu)特點(diǎn)如下:a.稀疏矩陣的每一行與每一列均用帶表頭結(jié)點(diǎn)的循環(huán)鏈表表示；b.表頭結(jié)點(diǎn)中的行域與列域的值均置為-1(即row=-l,col=-l)；c.行、列鏈表的表頭結(jié)點(diǎn)合用，且這些表頭結(jié)點(diǎn)存放在ー個(gè)順序存儲空間中。③C++描述〃非零元素所在的行號〃非零元素所在的列號〃非零元素所在的行號〃非零元素所在的列號〃非零元索值〃向下指針域〃向右指針域