版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第五章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)
5.3.1特殊矩陣
5.3.2稀疏矩陣5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)數(shù)組和廣義表可看成是一種特殊的線性表,其特殊在于,表中的所有元素本身也是一種線性表。數(shù)組是我們最熟悉的數(shù)據(jù)類型,在早期的高級(jí)語(yǔ)言中,數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型,并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界,因此,數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。多維數(shù)組是向量的推廣。例如,二維數(shù)組:5.1數(shù)組的定義二維數(shù)組可以看成是由行向量組成的向量,也可以看成是列向量組成的向量。同樣,可把三維數(shù)組看成是一個(gè)線性表,表中每一個(gè)數(shù)組元素為一個(gè)二維數(shù)組。依次類推,可把n維數(shù)組看成是一個(gè)線性表,表中每一個(gè)數(shù)據(jù)元素是一個(gè)n-1維數(shù)組。數(shù)組的運(yùn)算:數(shù)組一旦被定義,它的維數(shù)和維界就不再改變。因此,除了結(jié)構(gòu)的初始化和銷毀之外,數(shù)組只有存取元素和修改元素值的操作。即給定一組下標(biāo),存取或修改相應(yīng)的數(shù)組元素。5.1數(shù)組的定義1、順序存儲(chǔ)結(jié)構(gòu)5.2數(shù)組的順序表示和實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu):用一組地址連續(xù)的存儲(chǔ)單元依次存放數(shù)據(jù)元素,稱為數(shù)組的順序存儲(chǔ)結(jié)構(gòu)。由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的,因此用一維內(nèi)存來(lái)表示多維數(shù)組,就必須按某種次序?qū)?shù)組元素排成一列序列,然后將這個(gè)線性序列存放在存儲(chǔ)器中。由于對(duì)數(shù)組一般不做插入和刪除操作,也就是說(shuō),數(shù)組一旦建立,結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此,一般都是采用順序存儲(chǔ)的方法來(lái)表示數(shù)組。
通常有兩種順序存儲(chǔ)方式:2、順序存儲(chǔ)方式⑴行優(yōu)先順序——將數(shù)組元素按行排列,第i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維數(shù)組為例,按行優(yōu)先順序存儲(chǔ)的線性序列為:a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn
在PASCAL、C語(yǔ)言中,數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。⑵列優(yōu)先順序——將數(shù)組元素按列向量排列,第j+1個(gè)列向量緊接在第j個(gè)列向量之后,A的m*n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為:a11,a21,…,am1,a12,a22,…am2,……,a1n,a2n,…,amn在FORTRAN語(yǔ)言中,數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。
a11a12……..a1n
a21a22……..a2n
am1am2……..amn
….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l
按行序?yàn)橹餍虼娣?/p>
amn
……..
am2am1……….a2n
……..
a22a21a1n
…….a12
a1101n-1m*n-1n
按列序?yàn)橹餍虼娣?1m-1m*n-1m
amn
……..
a2n
a1n……….
am2
……..
a22
a12
am1
…….
a21
a11
a11
a12
……..
a1n
a21
a22……..
a2n
am1
am2
……..
amn
….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
以上規(guī)則推廣到多維數(shù)組的情況:行優(yōu)先順序可規(guī)定為先排最右的下標(biāo),從右到左,最后排最左下標(biāo);3、n維數(shù)組按上述兩種方式順序存儲(chǔ)的數(shù)組,只要知道開(kāi)始結(jié)點(diǎn)的存放地址(即基地址)、維數(shù)和每維的上、下界,以及每個(gè)數(shù)組元素所占用的單元數(shù),就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此,數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取,即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。列優(yōu)先順序與此相反,先排最左下標(biāo),從左向右,最后排最右下標(biāo)。例如,二維數(shù)組Amn按“行優(yōu)先順序”存儲(chǔ)在內(nèi)存中,假設(shè)每個(gè)元素占用d個(gè)存儲(chǔ)單元。4、地址公式元素aij的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。因?yàn)閍ij位于第i行、第j列,前面i-1行一共有(i-1)×n個(gè)元素,第i行上aij前面又有j-1個(gè)元素,故它前面一共有(i-1)×n+j-1個(gè)元素,因此,aij的地址計(jì)算函數(shù)為:LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d同樣,三維數(shù)組Aijk按“行優(yōu)先順序”存儲(chǔ),其地址計(jì)算函數(shù)為:
LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d上述討論均是假設(shè)數(shù)組各維的下界是1,更一般的二維數(shù)組是A[c1..d1,c2..d2],這里c1,c2不一定是1。aij前一共有i-c1行,二維數(shù)組一共有d2-c2+1列,故這i-c1行共有(i-c1)*(d2-c2+1)個(gè)元素,第i行上aij前一共有j-c2個(gè)元素,因此,aij的地址計(jì)算函數(shù)為:
4、地址公式LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d例如,在C語(yǔ)言中,數(shù)組各維下標(biāo)的下界是0,因此在C語(yǔ)言中,二維數(shù)組的地址計(jì)算公式為:LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d在科學(xué)與工程計(jì)算問(wèn)題中,矩陣是一種常用的數(shù)學(xué)對(duì)象,在高級(jí)語(yǔ)言編制程序時(shí),簡(jiǎn)單而又自然的方法,就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下,看起來(lái)存儲(chǔ)密度仍為1,但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素,這對(duì)高階矩陣會(huì)造成極大的浪費(fèi),為了節(jié)省存儲(chǔ)空間,我們可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。5.3矩陣的壓縮存儲(chǔ)壓縮存儲(chǔ):為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間;對(duì)零元素不分配空間。假若值相同的元素或零元素在矩陣中的分布有一定規(guī)律,則我們稱此類矩陣為特殊矩陣;反之,稱為稀疏矩陣。1、對(duì)稱矩陣5.3.1特殊矩陣在一個(gè)n階方陣A中,若元素滿足下述性質(zhì):aij=aji0≦i,j≦n-1則稱A為對(duì)稱矩陣。如圖5.1便是一個(gè)5階對(duì)稱矩陣。對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱,故只要存儲(chǔ)矩陣中上三角或下三角中的元素,讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間,這樣,能節(jié)約近一半的存儲(chǔ)空間。不失一般性,我們按“行優(yōu)先順序”存儲(chǔ)主對(duì)角線(包括對(duì)角線)以下的元素,其存儲(chǔ)形式如圖所示:
a00a01
….
……..a0n-1
a10
a11
……..…….a1n-1
an-10
an-11
……..an-1n-1
….a00a10a11a20a21a23………………..an-10an-11an-12…an-1n-1
a00a01
….
……..a0n-1
a10
a11
……..…….a1n-1
an-10
an-11
……..an-1n-1
….在這個(gè)下三角矩陣中,第i行恰有i+1個(gè)元素,元素總數(shù)為:(i+1)=n(n+1)/2。這樣可將n2個(gè)壓縮到n(n+1)/2個(gè)元的空間中。因此,我們可以按圖中箭頭所指的次序?qū)⑦@些元素存放在一個(gè)向量sa[0..n(n+1)/2-1]中。為了便于訪問(wèn)對(duì)稱矩陣A中的元素,我們必須在aij和sa[k]之間找一個(gè)對(duì)應(yīng)關(guān)系。1、對(duì)稱矩陣i≧j,則aij在下三角形中。aij之前的i行(從第0行到第i-1行)一共有1+2+…+i=i(i+1)/2個(gè)元素,在第i行上,aij之前恰有j個(gè)元素(即ai0,ai1,ai2,…,aij-1),因此有:1、對(duì)稱矩陣k=i*(i+1)/2+j0≦k<n(n+1)/2若i<j,則aij是在上三角矩陣中。因?yàn)閍ij=aji,所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到:k=j*(j+1)/2+i0≦k<n(n+1)/2令I(lǐng)=max(i,j),J=min(i,j),則k和i,j的對(duì)應(yīng)關(guān)系可統(tǒng)一為:
k=I*(I+1)/2+J0≦k<n(n+1)/2aij的地址可用下列式計(jì)算:
LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d)a00a10a11a20……an-10……an-1,n-1根據(jù)下標(biāo)交換關(guān)系,對(duì)于任意給定一組下標(biāo)(i,j),均可在sa[k]中找到矩陣元素aij,反之,對(duì)所有的k=0,1,2,…n(n-1)/2-1,都能確定sa[k]中的元素在矩陣中的位置(i,j)。由此,稱sa[n(n+1)/2]為階對(duì)稱矩陣A的壓縮存儲(chǔ),見(jiàn)下圖:k=0123n(n-1)/2n(n-1)/2-1例如a21和a12均存儲(chǔ)在sa[4]中
k=I*(I+1)/2+J=2*(2+1)/2+1=4以主對(duì)角線劃分,三角矩陣有上三角和下三角兩種。2、三角矩陣a00a01…a0n-1ca11…a1n-1……………..cc…an-1n-1(a)上三角矩陣a00c…ca10a11…c……………..an-10an-11…an-1
n-1
(b)下三角矩陣上三角矩陣如圖所示,它的下三角(不包括主對(duì)角線)中的元素均為常數(shù)。下三角矩陣正好相反,它的主對(duì)角線上方均為常數(shù),如圖所示。在大多數(shù)情況下,三角矩陣常數(shù)為零。帶狀矩陣:在帶狀矩陣中,所有的非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域中,即除了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外,其余元素皆為零。這個(gè)帶狀區(qū)域若包含主對(duì)角線下面及上面各d條對(duì)角線上的元素,那么,方陣稱為半帶寬為d的帶狀矩陣。設(shè)n階方陣A是半帶寬為d的帶狀矩陣,則當(dāng)|i-j|>d時(shí),aij=0,2d+1稱為帶狀矩陣的帶寬。3、帶狀矩陣
a11a120
…………….
0
a21
a22a23
0
……………0
0
0
…an-1,n-2an-1,n-1
an-1,n
0
0
……an,n-1
ann.
0
a32
a33a34
0
………0
……………非零元素僅出現(xiàn)在主對(duì)角上,緊鄰主對(duì)角線上面的d條對(duì)角線上和緊鄰主對(duì)角線下面的d條對(duì)角線上。顯然,當(dāng)∣i-j∣>d時(shí),元素aij=0。對(duì)帶狀矩陣可按行優(yōu)先順序或?qū)蔷€的順序,將其壓縮存儲(chǔ)到一個(gè)向量中,并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。對(duì)于n階半帶寬為d的帶狀矩陣,只需存放帶狀區(qū)域之內(nèi)的n(2d+1)-d(d+1)個(gè)非零元素。為了計(jì)算非零元素存放位置方便,除第1行和第n行外,每行都當(dāng)做有
2d+1個(gè)元素,若少于2d+1個(gè),則添零補(bǔ)足。將帶狀矩陣存儲(chǔ)在[(2d+1)n-2d)]s個(gè)存儲(chǔ)單元中,元素aij的地址公式為:LOC[i,j]=Loc[1,1]+[(i-1)(2d+1)+(j-i)]s(1in,1jn,|i-j|d)上述的各種特殊矩陣,其非零元素的分布都是有規(guī)律的,因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中,并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系,通過(guò)這個(gè)關(guān)系,仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。5.3.2稀疏矩陣什么是稀疏矩陣?精確點(diǎn),設(shè)在的矩陣A中,有s個(gè)非零元素。令e=s/(m*n),稱e為矩陣的稀疏因子。通常認(rèn)為e≦0.05時(shí)稱之為稀疏矩陣。簡(jiǎn)單說(shuō),設(shè)矩陣A中有s個(gè)非零元素,若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)(即s≦m×n),則稱A為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí),為了節(jié)省存儲(chǔ)單元,很自然地想到使用壓縮存儲(chǔ)方法。但由于非零元素的分布一般是沒(méi)有規(guī)律的,因此在存儲(chǔ)非零元素的同時(shí),還必須同時(shí)記下它所在的行和列的位置(i,
j)。1、三元順序表
反之,一個(gè)三元組(i,j,aij)唯一確定了矩陣A的一個(gè)非零元。因此,稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。例如,下列三元組表((1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6,7)這一對(duì)行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。1、三元順序表#defineM20typedef
structnode{inti,j;
intv;}JD;JDma[M];三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)678
121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)行列下標(biāo)非零元值2、稀疏矩陣的壓縮存儲(chǔ)方法3、求轉(zhuǎn)置矩陣問(wèn)題描述:已知一個(gè)稀疏矩陣的三元組表,求該矩陣轉(zhuǎn)置矩陣的三元組表。解決思路:(1)將矩陣行、列維數(shù)互換(2)將每個(gè)三元組中的i和j相互調(diào)換(3)重排三元組次序,使mb中元素以T的行(M的列)為主序67
8
121213931-3361443245218611564-7ijv012345678maijv76
8
13-3161521122518319342446-76314012345678mb?一個(gè)m×n的矩陣A,它的轉(zhuǎn)置B是一個(gè)n×m的矩陣,且a[i][j]=b[j][i],0≦i≦m,0≦j≦n,即A的行是B的列,A的列是B的行。方法一將A轉(zhuǎn)置為B,就是將A的三元組表a.data置換為表B的三元組表b.data,如果只是簡(jiǎn)單地交換a.data中i和j的內(nèi)容,那么得到的b.data將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B。要得到按行優(yōu)先順序存儲(chǔ)的b.data,就必須重新排列三元組的順序。
由于A的列是B的行,因此,按a.data的列序轉(zhuǎn)置,所得到的轉(zhuǎn)置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。按這種方法設(shè)計(jì)的算法,其基本思想是:對(duì)A中的每一列col(0≦col≦n-1),通過(guò)從頭至尾掃描三元表a.data,找出所有列號(hào)等于col的那些三元組,將它們的行號(hào)和列號(hào)互換后依次放入b.data中,即可得到B的按行優(yōu)先的壓縮存儲(chǔ)表示。方法一StatusTransmatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;col++)
for(p=1;p<=M.tu;p++)
if(M.data[p].j==col){
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;q++;}returnOK;}//TransposeSMatrix6
7
8
121213931-3361443245218611564-7ijv012345678ma7
6
8
13-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2方法一分析這個(gè)算法,主要的工作是在p和col的兩個(gè)循環(huán)中完成的,故算法的時(shí)間復(fù)雜度為O(n*t),即矩陣的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為:
for(col=1;col<=nu;++col)
for(row=1;row<=mu;++row)
t[col][row]=m[row][col];時(shí)間復(fù)雜度為O(n*m)。當(dāng)非零元素的個(gè)數(shù)t和m*n同數(shù)量級(jí)時(shí),算法transmatrix的時(shí)間復(fù)雜度為O(m*n2)。三元組順序表雖然節(jié)省了存儲(chǔ)空間,但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜,同時(shí)還有可能增加算法的難度。因此,此算法僅適用于t<=m*n的情況。方法一按照a.data中三元組的次序進(jìn)行轉(zhuǎn)置,并將轉(zhuǎn)置后的三元組置入b中的恰當(dāng)位置。方法2:快速轉(zhuǎn)置算法如果能預(yù)先確定矩陣M中每一列(即T中每一行)的第一個(gè)非零元素在b.data中應(yīng)有的位置,那么在對(duì)a.data中的三元組一次作轉(zhuǎn)置時(shí),便可直接放到b.data中恰當(dāng)位置上去。為了確定這些位置,在轉(zhuǎn)置前,應(yīng)先求得M的每一列中非零元的個(gè)數(shù),進(jìn)而求得每一列的第一個(gè)非零元在b.data中應(yīng)有的位置??焖俎D(zhuǎn)置算法的思想:對(duì)A掃描一次,按A第二列提供的列號(hào)一次確定裝入B的一個(gè)三元組的位置。具體實(shí)施如下:一遍掃描先確定三元組的位置關(guān)系,二次掃描由位置關(guān)系裝入三元組??梢?jiàn),位置關(guān)系是此種算法的關(guān)鍵。
實(shí)現(xiàn):需要附設(shè)num和cpot兩個(gè)數(shù)組。num[col]:表示矩陣M中第col列中非零元個(gè)數(shù);cpot[col]:指示M中第col列第一個(gè)非零元在mb中位置顯然有:cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2cola.nu)1357889colnum[col]cpot[col]12223241506170方法2:快速轉(zhuǎn)置算法快速轉(zhuǎn)置算法StatusFastTransmatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中每一列含非零元個(gè)數(shù)cpot[1]=1;//求第col列中第1個(gè)非零元素在b.data中的序號(hào)??焖俎D(zhuǎn)置算法for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;p++){col=M.data[p].j;q=cpot[col];}//ifreturnOK;}//FastTransposeSMatrix
T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;++cpot[col];}//for這個(gè)算法僅比前一個(gè)算法多用了兩個(gè)輔助數(shù)組??焖俎D(zhuǎn)置算法分析從時(shí)間上看,算法中有四個(gè)并列的單循環(huán),循環(huán)次數(shù)分別為nu和tu,因而總的時(shí)間復(fù)雜度為O(nu+tu)。在M的非零元素個(gè)數(shù)tu和mu×nu等數(shù)量級(jí)時(shí),其時(shí)間復(fù)雜度為O(mu×nu),和經(jīng)典算法的時(shí)間復(fù)雜度相同。67
8
121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907
6
8
13-3161521122518319342446-76314pppppppp4629753tpedef
struct
OLNode{inti,j;ElemTypee;struct
OLNode*down,*right;}OLNode;*OLink;ijedownright在鏈表中,每個(gè)非零元素可用一個(gè)含5個(gè)域的結(jié)點(diǎn)表示,right域用以鏈接同一行中下一個(gè)非零元素,down域用以鏈接同一列中下一個(gè)非零元素。4、十字鏈表同一行的非零元素通過(guò)right域鏈接成一個(gè)線性表,同一列的非零元素通過(guò)down域鏈接成一個(gè)線性表,每個(gè)非零元素既是某行鏈表中的一個(gè)結(jié)點(diǎn),又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn),整個(gè)矩陣構(gòu)成了一個(gè)十字交叉的鏈表,故稱這樣的存儲(chǔ)結(jié)構(gòu)為十字鏈表,可用兩個(gè)分別存儲(chǔ)行鏈表的頭指針和列鏈表的頭指針的一維數(shù)組表示。113418225234^^^^^^^4、十字鏈表例題:兩個(gè)矩陣相加假設(shè)兩個(gè)矩陣相加后的結(jié)果為A’,則和矩陣A’中的非零元aij’只可能有三種情況:aij+bij
當(dāng)將B加到A上去時(shí),A矩陣的十字鏈表:改變接點(diǎn)的e值(aij+bij0)aij(bij=0)bij(aij=0)不變(bij=0)插入一個(gè)新結(jié)點(diǎn)(aij=0)另一種情況:和A矩陣中的某個(gè)非零元相對(duì)應(yīng),和矩陣A’中是零元,即對(duì)A的操作是刪除一個(gè)接點(diǎn)(aij+bij=0)。整個(gè)運(yùn)算過(guò)程可從矩陣的第一行起逐行進(jìn)行。對(duì)每一行都從表頭出發(fā)分別找到A和B在該行中的第一個(gè)非零元結(jié)點(diǎn)后,開(kāi)始比較,然后按上述四種不同情況分別處理。例題:兩個(gè)矩陣相加廣義表(Lists,又稱列表)是線性表的推廣。在第2章中,我們把線性表定義為n0個(gè)元素a1,a2,a3,…,an的有限序列。線性表的元素僅限于原子項(xiàng),原子是作為結(jié)構(gòu)上不可分割的成分,它可以是一個(gè)數(shù)或一個(gè)結(jié)構(gòu),若放松對(duì)表元素的這種限制,容許它們具有其自身結(jié)構(gòu),這樣就產(chǎn)生了廣義表的概念。5.4廣義表的定義廣義表是n(n0)個(gè)元素a1,a2,a3,…,an的有限序列,其中ai或者是原子項(xiàng),或者是一個(gè)廣義表。通常記作LS=(a1,a2,a3,…,an)。LS是廣義表的名字,n為它的長(zhǎng)度。若ai是廣義表,則稱它為L(zhǎng)S的子表。通常用圓括號(hào)將廣義表括起來(lái),用逗號(hào)分隔其中的元素。為了區(qū)別原子和廣義表,書(shū)寫(xiě)時(shí)用大寫(xiě)字母表示廣義表,用小寫(xiě)字母表示原子。若廣義表LS(n>=1)非空,則a1是LS的表頭,其余元素組成的表(a1,a2,…an)稱為L(zhǎng)S的表尾。5.4廣義表的定義顯然廣義表是遞歸定義的,這是因?yàn)樵诙x廣義表時(shí)又用到了廣義表的概念。廣義表的例子如下:(1)A=()——A是一個(gè)空表,其長(zhǎng)度為零。(2)B=(e)——表B只有一個(gè)原子e,B的長(zhǎng)度為1。(3)C=(a,(b,c,d))——表C的長(zhǎng)度為2,兩個(gè)元素分別為原子a和子表(b,c,d)。(4)D=(A,B,C)——表D的長(zhǎng)度為
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 滬科版八年級(jí)數(shù)學(xué)上冊(cè)專項(xiàng)素養(yǎng)綜合練(五)與三角形有關(guān)的四大模型課件
- 飲品店員工培訓(xùn)合同
- 內(nèi)蒙古鄂爾多斯市康巴什新區(qū)達(dá)標(biāo)名校2024年中考數(shù)學(xué)四模試卷含解析
- 青島版小學(xué)科學(xué)(五四制)一年級(jí)科學(xué)下冊(cè)全冊(cè)教案
- 青島版三年級(jí)科學(xué)下冊(cè)備課教案設(shè)計(jì)
- 初三第一次家長(zhǎng)會(huì)課件
- 2024年二建建筑-案例必背100問(wèn)
- 智能應(yīng)急協(xié)同解決方案
- 訂貨經(jīng)濟(jì)合同模板
- 相機(jī)支架租賃合同模板
- 運(yùn)輸方式和交通布局與區(qū)域發(fā)展的關(guān)系課件
- 第四單元達(dá)標(biāo)測(cè)試卷(單元測(cè)試)-2024-2025學(xué)年統(tǒng)編版語(yǔ)文四年級(jí)上冊(cè)
- 2024年社區(qū)工作者面試題庫(kù)與答案
- 中國(guó)人壽保險(xiǎn)股份有限公司招聘考試試卷2022
- 省級(jí)賽課大賽一等獎(jiǎng)人音版二年級(jí)上冊(cè)音樂(lè)《四小天鵝舞曲》課件(內(nèi)嵌音視頻)
- 人工智能技術(shù)應(yīng)用專業(yè)調(diào)研報(bào)告
- 2024發(fā)展對(duì)象培訓(xùn)班考試試題與答案
- GB/T 15967-20241∶500 1∶1 000 1∶2 000地形圖數(shù)字航空攝影測(cè)量測(cè)圖規(guī)范
- (正式版)HGT 22820-2024 化工安全儀表系統(tǒng)工程設(shè)計(jì)規(guī)范
- 《中華民族共同體概論》考試復(fù)習(xí)題庫(kù)(含答案)
- NB-T 47013.15-2021 承壓設(shè)備無(wú)損檢測(cè) 第15部分:相控陣超聲檢測(cè)
評(píng)論
0/150
提交評(píng)論