數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計（第二版）課件 第5章數(shù)組

第五章數(shù)組數(shù)組—邏輯結(jié)構(gòu)數(shù)組是我們很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以把數(shù)組看做是線性表的推廣。數(shù)組的特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。一維數(shù)組二維數(shù)組三維數(shù)組數(shù)組—邏輯結(jié)構(gòu)從小事做起，學(xué)會“積累”，學(xué)習(xí)也是一個積累的過程。使學(xué)生明白“積少成多”，能力才能螺旋式上升。數(shù)組—邏輯結(jié)構(gòu)數(shù)組的特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，一維數(shù)組可以看做是一個線性表；（a1a2…aj…an）二維數(shù)組可以看做是“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組；三維數(shù)組可以看做是“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組。a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……………………m行n列的二維數(shù)組看成n個列向量的線性表推廣：

n維數(shù)組—每個數(shù)據(jù)元素受n個關(guān)系的約束，每一單個關(guān)系，仍是線性關(guān)系。也可看成m個行向量的線性表B=(βiβ2β1βm……a11a12…a1j…a1na21a22…a2j…a2nai1ai2…aij…ainam1am2…amj…amnAm×n=……………………A=(α1

α

2…α

j

…α

n)每一個數(shù)組元素aij在第i行，第j列，受到兩個線性關(guān)系的約束，就是行和列關(guān)系。數(shù)組—邏輯結(jié)構(gòu)一般來說，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種操作：(1)取值操作：給定一組下標(biāo)，讀其對應(yīng)的數(shù)據(jù)元素。(2)賦值操作：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。從數(shù)組的特殊結(jié)構(gòu)可看出，數(shù)組中的每個元素由一個值和一組下標(biāo)來描述。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..數(shù)組—邏輯結(jié)構(gòu)由于對數(shù)組一般不做插入、刪除操作；一旦建立了數(shù)組，數(shù)據(jù)元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動；

采用順序存儲結(jié)構(gòu)表示數(shù)組；由于存儲單元是一維的結(jié)構(gòu)，而數(shù)組是多維的結(jié)構(gòu)，則采用一組連續(xù)存儲單元存放數(shù)組元素就有個次序約定問題。一般有兩種存儲方式：一是以行為主序(即先行后列)的順序存放，一行存儲完了接著存儲下一行。二是以列為主序(即先列后行)的順序存放，一列存儲完了接著存儲下一列。數(shù)組—存儲結(jié)構(gòu)數(shù)組—存儲結(jié)構(gòu)第一行第二行第一列第二列第三列a11a12a13a21a22a232×3數(shù)組的邏輯狀態(tài)a11a12a23a21a22a23

以行為主序a11a21a12a22a13a23

以列為主序采用以行為主序的方法存放，則存放順序為：a111，a112，a121，a122，…，a331，a332，a341，…；采用以縱為主序的方法存放，則順序為：a111，a211，a311，a121，a221，a321，…，a132，a232，a332，a142，a242，a342。假設(shè)有一個3?×?4?×?2的三維數(shù)組，共有24個元素。三維數(shù)組元素的下標(biāo)由三個數(shù)字表示，即行、列、縱三個方向。A231表示第2行、第3列、第1縱的元素。數(shù)組—存儲結(jié)構(gòu)

數(shù)組的順序存儲是一種隨機存取的結(jié)構(gòu)。如果已知多維數(shù)組的維數(shù)，以及每維的上、下界，就可以方便地將多維數(shù)組按順序存儲結(jié)構(gòu)存放在計算機中了。同時，根據(jù)數(shù)組的下標(biāo)，可以計算出數(shù)組中某個數(shù)組元素在存儲器中的位置。設(shè)有m?×?n二維數(shù)組Amn，假設(shè)下標(biāo)從1開始，以“以行為主序”的分配為例。設(shè)數(shù)組中的a11存儲地址為Loc(a11)，每個數(shù)組元素占據(jù)L個地址單元，那么aij的物理地址可計算出來：Loc(aij)?=?Loc(a11)?+?((i?-?1)×n?+?j?-?1)?×?L

這是因為數(shù)組元素aij的前面有i-1行，每一行的元素個數(shù)為n，在第i行中它的前面還有j-1個數(shù)組元素。數(shù)組—存儲結(jié)構(gòu)

同理，可得到三維數(shù)組Amnp中任意元素aijk的存儲地址的計算公式：Loc(aijk)?=?Loc(a111)?+?((i?-?1)?×?n?×?p?+?(j?-?1)?×?p?+?k?-?1)?×?L

數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機存取。我們稱具有這一特點的存儲結(jié)構(gòu)為隨機存儲結(jié)構(gòu)。數(shù)組—存儲結(jié)構(gòu)推廣到一般的三維數(shù)組：A[c1..d1][c2..d2][c3..d3]，則aijk的物理地址為:Loc(aijk)=Loc(ac1c2c3)+((i-c1)×(d2-c2+1)×(d3-c3+1)??+(j-c2)×(d3-c3+1)+(k-c3))×L對于n維數(shù)組A(c1..d1,c2..d2,…,cn..dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲地址的計算公式：

容易看出，數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機存取。我們稱具有這一特點的存儲結(jié)構(gòu)為隨機存儲結(jié)構(gòu)。數(shù)組—存儲結(jié)構(gòu)矩陣是一個二維數(shù)組，它是很多科學(xué)與工程計算問題中研究的數(shù)學(xué)對象。矩陣可以用行優(yōu)先或列優(yōu)先方法順序存放到內(nèi)存中，但是，當(dāng)矩陣的階數(shù)很大時將會占較多存儲單元。而當(dāng)數(shù)組元素分布呈現(xiàn)某種規(guī)律時，這時，從節(jié)約存儲單元出發(fā)，可考慮若干數(shù)組元素共用一個存儲單元，即進行壓縮存儲。所謂壓縮存儲，是指為多個值相同的數(shù)組元素只分配一個存儲空間，值為零的數(shù)組元素不分配空間。特殊矩陣—壓縮存儲矩陣的壓縮存儲是為了節(jié)約空間，雖然現(xiàn)在計算機硬件發(fā)展很快，其處理量以指數(shù)級增長，必須考慮存儲空間的有效利用?！扒趦€節(jié)約”，杜絕浪費。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..在一個n階方陣中，有aij

=

aji，稱之為對稱矩陣；對稱矩陣的特點是：在一個n階方陣中，有aij

=

aji，其中1≤i,j≤n。對稱矩陣關(guān)于主對角線對稱，因此只需存儲上三角或下三角部分即可。特殊矩陣—壓縮存儲透過現(xiàn)象看本質(zhì)?。。τ趎*n矩陣A，只存儲A中的下三角中的數(shù)組元素aij，上三角中的數(shù)組元素aij，和對應(yīng)的aji相等，因此當(dāng)訪問的數(shù)組元素在上三角時，直接去訪問和它對應(yīng)的下三角數(shù)組元素即可，這樣，原來需要n2個存儲單元，現(xiàn)在只需要n(n+1)/2個存儲單元了，節(jié)約了n(n-1)/2個存儲單元，當(dāng)n較大時，這是可觀的一部分存儲資源。Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..特殊矩陣—壓縮存儲透過現(xiàn)象看本質(zhì)！??！第1行第2行第3行第n行對于下三角中的數(shù)組元素aij，其特點是：i≥j且1≤i≤n，存儲到SA中后，根據(jù)存儲原則，它前面有i-1行，共有1?+?2?+?…?+?i?-?1?=?i?×?(i?-?1)?/?2個元素。而aij又是它所在的行中的第j個，所以在上面的排列順序中，aij是第i?×?(i?-?1)?/?2?+?j個元素。因此它在SA中的下標(biāo)k與i、j的關(guān)系為Am×n=a11a12a1ja1n…..…..a21a22a2ja2n…..…..ai1ai2aijain…..…..an1an2anjann…..…..12345···n(n+1)/2a10a21a22a31a32a33···an1an2···ann特殊矩陣—壓縮存儲若i?<?j，則aij是上三角中的數(shù)組元素，因為aij?=?aji，這樣，訪問上三角中的數(shù)組元素aij時則去訪問和它對應(yīng)的下三角中的aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的數(shù)組元素在SA中的對應(yīng)關(guān)系：

綜上所述，對于對稱矩陣中的任意數(shù)組元素aij，若令I(lǐng)?=?max(i,j)，J?=?min(i,j)，則將上面兩個式子綜合起來得到：k?=?I?×?(I-1)/2?+?J。特殊矩陣—壓縮存儲下三角矩陣上三角矩陣三角矩陣與對稱矩陣類似，不同之處在于存完下三角中的數(shù)組元素之后，緊接著存儲對角線上方的常量，因為是同一個常數(shù)，所以存一個即可。這樣一共存儲了n?×?(n+1)/2+1個元素。下三角矩陣的壓縮存儲形式362481746082957c12345678910111213141516特殊矩陣—壓縮存儲若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。三對角帶狀矩陣特點：第一行、第n行只有兩個非零元素，中間n-2行每行有三個非零元素。12345678910111213a11a12a21a22a23a32a33a34a43a44a45a54a32特殊矩陣—壓縮存儲(1)確定存儲該矩陣所需的一維向量空間的大小。所需一維向量空間的大小為2?+?2?+?3(n?-?2)?=?3n?-?2(2)確定非零元素在一維數(shù)組空間中的位置：Loc[i,j]。前i-1行元素個數(shù)?=?3?×?(i-1)?-?1(因為第1行只有兩個非零元素)；第i行中aij前非零元素個數(shù)?=?j-i+1，其中j-i的絕對值小于等于1?，F(xiàn)在的任務(wù)是：將矩陣中的非零元素aij壓縮存儲。Loc[i,j]?=?Loc[1,1]?+?3(i?-?1)?-?1?+?j?-?i?+?1?=?Loc[1,1]?+?2(i?-?1)?+?j?-?1特殊矩陣—壓縮存儲總而言之，對特殊矩陣的壓縮存儲方法時可以總結(jié)為兩條：首先，確定壓縮存儲矩陣所需的空間的大小。第二：確定矩陣元素aij在壓縮存儲區(qū)域中的位置。特殊矩陣—壓縮存儲內(nèi)容回顧數(shù)組—邏輯結(jié)構(gòu)數(shù)組是我們很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以把數(shù)組看做是線性表的推廣。數(shù)組的特點是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。一維數(shù)組二維數(shù)組三維數(shù)組數(shù)組—邏輯結(jié)構(gòu)從小事做起，學(xué)會“積累”，學(xué)習(xí)也是一個積累的過程。使學(xué)生明白“積少成多”，能力才能螺旋式上升。對于n維數(shù)組A(c1..d1,c2..d2,…,cn..dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲地址的計算公式：

容易看出，數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機存取。我們稱具有這一特點的存儲結(jié)構(gòu)為隨機存儲結(jié)構(gòu)。數(shù)組—存儲結(jié)構(gòu)矩陣是一個二維數(shù)組，它是很多科學(xué)與工程計算問題中研究的數(shù)學(xué)對象。矩陣可以用行優(yōu)先或列優(yōu)先方法順序存放到內(nèi)存中，但是，當(dāng)矩陣的階數(shù)很大時將會占較多存儲單元。而當(dāng)數(shù)組元素分布呈現(xiàn)某種規(guī)律時，這時，從節(jié)約存儲單元出發(fā)，可考慮若干數(shù)組元素共用一個存儲單元，即進行壓縮存儲。所謂壓縮存儲，是指為多個值相同的數(shù)組元素只分配一個存儲空間，值為零的數(shù)組元素不分配空間。特殊矩陣—壓縮存儲矩陣的壓縮存儲是為了節(jié)約空間，雖然現(xiàn)在計算機硬件發(fā)展很快，其處理量以指數(shù)級增長，必須考慮存儲空間的有效利用。“勤儉節(jié)約”，杜絕浪費。設(shè)m?×?n矩陣中有t個非零元素且t?<<?m?×?n，稀疏矩陣—壓縮存儲δ=t/m?×?n，δ稱為稀疏因子,

δ≤0.05時為稀疏矩陣。如果按順序存儲結(jié)構(gòu)存儲，會造成空間的浪費。通常零元素分布沒有規(guī)律，存儲非零元素的值是不夠的，還要記下它所在的行和列。將非零元素所在的行、列以及它的值構(gòu)成一個三元組(i,j,v)，然后再按某種規(guī)律存儲這些三元組，這種方法可以節(jié)約存儲空間。透過現(xiàn)象看本質(zhì)?。。⑷M按行優(yōu)先的順序，同一行中列號從小到大的規(guī)律排列成一個線性表，稱為三元組表，采用順序存儲方法存儲該表。

ijv123456711122351462341

1522

-15113691顯然，要唯一地表示一個稀疏矩陣，可在存儲三元組表的同時存儲該矩陣的行、列，為了運算方便，矩陣的非零元素的個數(shù)也同時存儲。稀疏矩陣—壓縮存儲1defineSMAX10242typedefstruct3{4inti,j; 5datatypev; 6}SPNode; 7typedefstruct8{9intmu,nu,tu;10SPNodedata[SMAX]; 11}SPMatrix; /*一個足夠大的數(shù)*//*非零元素的行、列*//*非零元素值*//*三元組類型*//*矩陣的行、列及非零元素的個數(shù)*//*三元組表的存儲類型*//*三元組表*/稀疏矩陣—壓縮存儲稀疏矩陣的三元組表表示法雖然節(jié)約了存儲空間，但比起矩陣正常的存儲方式來講，其實現(xiàn)相同操作要耗費較多的時間，同時也增加了算法的難度，以耗費更多時間為代價來換取空間的節(jié)省。稀疏矩陣—壓縮存儲

所謂矩陣轉(zhuǎn)置，是指變換元素的位置，把位于(row，col)位置上的元素?fù)Q到(col，row)位置上，也就是說，把元素的行、列互換。采用矩陣的正常存儲方式時，實現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下：1voidTransMatrix(datatypesource[n][m],datatypedest[m][n])2{/*source和dest分別為被轉(zhuǎn)置的矩陣和轉(zhuǎn)置以后的矩陣*/3inti,j;4for(i=0;i<m;i++)5for(j=0;j<n;j++)6dest[i][j]=source[j][i];7}

顯然，時間復(fù)雜度為O(m?×?n)。1稀疏矩陣的轉(zhuǎn)置在A的三元組存儲基礎(chǔ)上得到B的三元組表存儲算法思路：①由A的行數(shù)、列數(shù)、非零元數(shù)目轉(zhuǎn)化成B的列數(shù)、行數(shù)、非零元數(shù)目。②按A的列(B的行)進行循環(huán)處理：對A的每一列掃描三元組，找出相應(yīng)的元素，若找到，則交換其行號與列號，并存儲到B的三元組中。-746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a)三元組表A(b)三元組表B

1稀疏矩陣的轉(zhuǎn)置1SPMatrix*TransM1(SPMatrix*A)2{SPMatrix*B;3intp,q,col;//p為A中下標(biāo)，q為B中下標(biāo)4B=(SPMatrix*)malloc(sizeof(SPMatrix));/*申請存儲空間*/5B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;/*稀疏矩陣的行、列、元素個數(shù)*/6if(B->tu>0)/*有非零元素則轉(zhuǎn)換*/7{q=1;8for(col=1;col<=(A->nu);col++)/*按A的列序轉(zhuǎn)換*/9for(p=1;p<=(A->tu);p++)/*掃描整個A的三元組表*/10if(A->data[p].j==col)//三元組中的元素在當(dāng)前列。11{B->data[q].i=A->data[p].j;//逐個復(fù)制當(dāng)前的A三元組元素到B三元組12B->data[q].j=A->data[p].i;13B->data[q].v=A->data[p].v;14q++;15}/*if*/16}/*if(B->tu>0)*/17returnB;/*返回的是轉(zhuǎn)置矩陣的指針*/18}/*TransM1*/時間復(fù)雜度為O(A.n×A.len),最壞情況當(dāng)A.len=A.m×A.n時，時間復(fù)雜度為O(A.m×A.n2)。1稀疏矩陣的轉(zhuǎn)置依次按三元組表A的次序進行轉(zhuǎn)置，轉(zhuǎn)置后直接放到三元組表B的正確位置上。這種轉(zhuǎn)置算法稱為快速轉(zhuǎn)置算法。

為了能將待轉(zhuǎn)置三元組表A中元素一次定位到三元組表B的正確位置上，需要預(yù)先計算以下數(shù)據(jù)：待轉(zhuǎn)置矩陣每一列中非零元素的個數(shù)。(2)待轉(zhuǎn)置矩陣每一列中第一個非零元素在三元組表B中的正確位置?？焖俎D(zhuǎn)置方法：為此，需要設(shè)兩個數(shù)組num[col]——用來存放A中第col列非零元素個數(shù)cpot[col]——用來存放A中第col列中第一個非零元素在三元組表B中的正確位置。col90781687531Position[col]01222num[col]54321-746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a)三元組表A(b)三元組表B(1)num[col]的計算方法：將三元組表A掃描一遍，對于其中列號為k的元素，給相應(yīng)的num[k]加1。(2)position[col]的計算方法：position[1]=1，position[col]=position[col-1]+num[col-1]，其中2≤col≤A.nu。

算法如下：SPMatrix*FastTM(TSMatrix*A){SPMatrix*B;intcol,t,p，q;//p為A下標(biāo)，q為B下標(biāo)

intnum[MAXSIZE],cpot[MAXSIZE];B->tu=A->tu;B->nu=A->mu;B->mu=A->nu;if(B->tu>0){for(col=1;col<=A->nu;col++)num[col]=0;//num初始化

for(t=1;t<=A->tu;t++)num[A->data[t].col]++;//計算num

cpot[1]=1;for(col=2;col<=A->nu;col++)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<A.tu；p++){col=A.data[p].col;q=cpot[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].ecpot[col]++;//下一個col行非零元素位置加1}//for}//if}快速轉(zhuǎn)置算法時間耗費在四個并列的單循環(huán)上，這四個并列的單循環(huán)分別執(zhí)行了A.nu，A.tu，A.nu，A.tu次；因而總的時間復(fù)雜度為O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。當(dāng)待轉(zhuǎn)置矩陣M中非零元素個數(shù)接近于A.mu×A.nu時，其時間復(fù)雜度接近于經(jīng)典算法的時間復(fù)雜度O(A.mu×A.nu)?？臻g耗費上除了三元組表所占用的空間外，還需要兩個輔助向量空間，即num[1..A->nu]，cpot[1..A->nu]。可見，算法在時間上的節(jié)省，是以更多的存儲空間為代價的。歲月靜好，是因為有人在替我們負(fù)重前行三元組表存儲的稀疏矩陣，在進行矩陣加法、減法和乘法等操作時，有時矩陣中的非零元素的位置和個數(shù)會發(fā)生很大的變化。如A?=?A?+?B，將矩陣B加到矩陣A上，此時若還用三元組表表示法，勢必會為了保持三元組表“以行序為主序”而大量移動元素。為此引入了鏈?zhǔn)酱鎯ο∈杈仃嚒＞仃囍?，每一個矩陣元素aij，受兩個線性關(guān)系的約束，行關(guān)系、列關(guān)系；每一個關(guān)系都是線性的，我們可以用線性鏈表來存儲行關(guān)系、列關(guān)系；這樣，aij就處于第i行的單鏈表中，也處于第j列的單鏈表中，就像處于十字路口一樣，所以我們將這種存儲結(jié)構(gòu)稱之為“十字鏈表”。稀疏矩陣—壓縮存儲在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了(row，col，value)以外，還要有以下兩個鏈域：

right：用于連接同一行中的下一個非零元素；

down：用于連接同一列中的下一個非零元素。同一行的非零元素通過right域連接成一個單鏈表，同一列中的非零元素通過down域連接成一個單鏈表。同時，再附設(shè)一個存放所有行鏈表的頭指針的一維數(shù)組和一個存放所有列鏈表的頭指針的一維數(shù)組。rowcolvaluedownright稀疏矩陣—壓縮存儲稀疏矩陣十字鏈表十字鏈表的結(jié)構(gòu)類型說明如下：1typedefstructOLNode2{3introw,col; 4datatypevalue;5structOLNode*right,*down;6}OLNode;*OLink;7typedefstruct8{9OLink*row_head,*col_head; 10intm,n,len; 11}CrossList;/*非零元素的行和列下標(biāo)*//*非零元素*//*非零元素所在行表、列表的后繼鏈域*//*行、列鏈表的頭指針向量*//*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個數(shù)*/稀疏矩陣—壓縮存儲十字鏈表的結(jié)構(gòu)類型說明如下：1typedefstructOLNode2{3introw,col; 4datatypevalue;5structOLNode*right,*down;6}OLNode;*OLink;7typedefstruct8{9OLink*row_head,*col_head; 10intm,n,len; 11}CrossList;/*非零元素的行和列下標(biāo)*//*非零元素所在行表、列表的后繼鏈域*//*行、列鏈表的頭指針向量*//*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個數(shù)*/稀疏矩陣—壓縮存儲廣義表是線性表的推廣，也有人稱其為列表。線性表是由n個數(shù)據(jù)元素組成的有限序列。(a1，a2，…，ai，…，an)其中每個組成元素被限定為單元素。廣義表將這種限制突破了，表中的元素可以是單元素，也可以是一個表。廣義表—邏輯結(jié)構(gòu)中國舉辦的某體育項目國際邀請賽，參賽隊清單可采用如下的表示形式：(俄羅斯，巴西，(國家，河北，四川)，古巴，美國，()，日本)韓國隊?wèi)?yīng)排在美國隊的后面，但由于某種原因未參加，成為空表。國家隊、河北隊、四川隊均作為東道主的參賽隊參加，構(gòu)成一個小的線性表，成為原線性表的一個數(shù)據(jù)項。這就是廣義表。廣義表是n(n≥0)個數(shù)據(jù)元素a1，a2，…，ai，…，an的有序序列，一般記作：ls?=?(a1，a2，…，ai，…，an)其中：ls是廣義表的名稱，n是它的長度。每個ai?(1≤i≤n)是ls的成員，它可以是單個元素，也可以是一個廣義表，分別稱為廣義表ls的單元素和子表。當(dāng)廣義表ls非空時，稱第一個元素a1為ls的表頭(head)；稱其余元素組成的表a2，…，ai，…，an)為ls的表尾(tail)。廣義表—邏輯結(jié)構(gòu)通常用大寫字母表示廣義表，用小寫字母表示單個數(shù)據(jù)元素，廣義表用括號括起來，括號內(nèi)的數(shù)據(jù)元素用逗號分隔開。廣義表的例子：D?=?(?) 空表，其長度為零A?=?(a，(b，c))表長度為2的廣義表 B?=?(A，A，D) 長度為3的廣義表C?=?(a，C)長度為2遞歸定義的廣義表C相當(dāng)于無窮表C?=?(a，(a，(a，(…))))

廣義表—邏輯結(jié)構(gòu)廣義表的重要性質(zhì)：(1)廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表。A?=?(a，(b，c))