第5章數(shù)組和廣義表1．教學(xué)目的：掌握數(shù)組和廣義表的定義、特點(diǎn)及典型算法。2．教學(xué)要求：①掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。②掌握矩陣實(shí)現(xiàn)壓縮存儲(chǔ)時(shí)的下標(biāo)變換。③理解稀疏矩陣的兩種存儲(chǔ)方式的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行運(yùn)算采用的處理方法。④掌握廣義表的定義及其存儲(chǔ)結(jié)構(gòu)，學(xué)會(huì)將廣義表分解為表頭，表尾的方法。3．教學(xué)重點(diǎn)：①掌握特殊矩陣的壓縮存儲(chǔ)。②掌握稀疏矩陣采用三元組存儲(chǔ)時(shí)典型算法的實(shí)現(xiàn)。③廣義表的定義、運(yùn)算。4．教學(xué)難點(diǎn)：數(shù)組的十字鏈表存儲(chǔ)結(jié)構(gòu)。5.1數(shù)組5.1.1數(shù)組的邏輯結(jié)構(gòu)特點(diǎn)：元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。數(shù)組是非常有用的數(shù)據(jù)結(jié)構(gòu)，幾乎所有的高級(jí)程序設(shè)計(jì)語(yǔ)言都提供了數(shù)組類型。比如：一維數(shù)組可以看作一個(gè)線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，依此類推。如圖是一個(gè)m行n列的二維數(shù)組矩陣Am×n看成n個(gè)列向量的線性表，推廣：

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

α

2…α

j

…α

n)通過(guò)以上分析可總結(jié)出數(shù)組具有以下性質(zhì)：⑴數(shù)組中數(shù)據(jù)元素?cái)?shù)目固定。⑵數(shù)組中數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。⑶數(shù)組中每一個(gè)數(shù)據(jù)元素由唯一的一組下標(biāo)來(lái)標(biāo)識(shí)。⑷數(shù)組是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級(jí)語(yǔ)言中，數(shù)組一旦被定義，每一維的大小及上下界都不能改變。⑴取值操作：給定一組下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。⑵賦值操作：給定一組下標(biāo)，存儲(chǔ)或修改其相對(duì)應(yīng)的數(shù)據(jù)元素。兩種操作：

二維數(shù)組形式化表示為：

A=(D,R)D={a0,0,a0,1,……a0,m,……,am-1,n-1}R={Row,Col}Row={<a0,0,a0,1>,<a0,1,a0,2>……,……<a0,n-2,a0,n-1>,<a1,0,a1,1>……}Col={<a0,0,a1,0>,<a1,0,a2,0>……,……<an-2,0,an-1,0>,<a0,1,a1,1>……｝其中Row是行關(guān)系，Col是列關(guān)系5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種：1.按行序存儲(chǔ)。如：BASIC、COBOL和PASCAL語(yǔ)言。2.按列序存儲(chǔ)。如：FORTRAN語(yǔ)言。a23a22a21a13a12a11a23a22a21a13a12a11a23a13a22a12a21a11(a)2×3數(shù)組的邏輯狀態(tài)(b)以行為主序(c)以列為主序圖5.2

2×3數(shù)組的物理狀態(tài)設(shè)數(shù)組的基址為L(zhǎng)OC(a11)，每個(gè)數(shù)組元素占據(jù)k個(gè)地址單元，那么aij的物理地址計(jì)算：設(shè)有二維數(shù)組Amn，按元素的下標(biāo)求其地址的計(jì)算：2以“以列為主序”的分配比例：

LOC(aij)=LOC(a11)+((j-1)*m+(i-1))*k

1以“以行為主序”的分配為例：

LOC(aij)=LOC(a11)+((i-1)*n+j-1)*k3在C語(yǔ)言中，數(shù)組中每一維的下界定義為0，則：

LOC(aij)=LOC(a00)+(i*n+j)*k對(duì)于三維數(shù)組Amnp，即m?×?n?×?p數(shù)組，對(duì)于數(shù)組元素aijk，其物理地址為：

Loc(aijk)=Loc(a111)+((i-1)×n×p+(j-1)×p+k-1)×L推廣到一般的三維數(shù)組：A[c1..d1][c2..d2][c3..d3]，則aijk的物理地址為L(zhǎng)oc(aijk)=Loc(ac1c2c3)+((i-c1)×(d2-c2+1)×(d3-c3+1)??+(j-c2)×(d3-c3+1)+(k-c3))×L對(duì)于n維數(shù)組A(c1..d1,c2..d2,…,cn..dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲(chǔ)地址的計(jì)算公式：容易看出，數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機(jī)存取。我們稱具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。5.2特殊矩陣的壓縮存儲(chǔ)矩陣：是一個(gè)二維數(shù)組，是科學(xué)和工程計(jì)算問(wèn)題中常用到的數(shù)據(jù)模型。特殊矩陣：矩陣中的元素分布呈現(xiàn)某種規(guī)律。為了節(jié)省存儲(chǔ)空間，特別是在高階矩陣的情況下，可以利用特殊矩陣的分布規(guī)律對(duì)他們進(jìn)行壓縮存儲(chǔ)。壓縮存儲(chǔ)：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，值為零的元素不分配空間。壓縮存儲(chǔ)時(shí)，節(jié)約了存儲(chǔ)單元，但在壓縮后還需解決如何找到某元素的方法，因此，還必須給出壓縮前下標(biāo)和壓縮后下標(biāo)之間的變換公式，使壓縮存儲(chǔ)變得有意義。注意：特點(diǎn)：在一個(gè)n階方陣中，有aij=aji

，其中1≤i、j≤n。如圖所示是一個(gè)5階對(duì)稱矩陣

5.2.1對(duì)稱矩陣對(duì)于對(duì)稱矩陣，因其元素滿足aij=aji，只需存儲(chǔ)其下三角（或上三角）,即可實(shí)現(xiàn)壓縮存儲(chǔ)。對(duì)于下三角元素aij，前面共有i行,這i行共有?

個(gè)元素,當(dāng)前行中aij前亦有?

個(gè)元素。所以aij前共有?

個(gè)元素，對(duì)于上三角元素aij，由于aij=aji,則訪問(wèn)和它對(duì)應(yīng)的下三角中的aji即可。綜合起來(lái)，對(duì)于對(duì)稱矩陣中的任意元素aij得到轉(zhuǎn)換公式：對(duì)于n階對(duì)稱方陣，將？個(gè)元素壓縮到？個(gè)空間中。n×nn(n+1)/2對(duì)下三角部分以行為主序順序存儲(chǔ)到一個(gè)向量中去，在下三角中共有n×(n+1)/2個(gè)元素，因此，不失一般性，設(shè)存儲(chǔ)到向量SA[n(n+1)/2]中。設(shè)矩陣元素aij存儲(chǔ)在A數(shù)組的A[k]中，則關(guān)鍵問(wèn)題是要找i、j與k的關(guān)系。根據(jù)存儲(chǔ)原則：K=I*(I+1)/2+J(其中I=max(i,j),J=min(i,j);)(i+1)*i/2j(i+1)*i/2+j12345…n(n+1)/2a11a21a22a31a32a33…an1an2…ani≥j且1≤i≤n若i?<?j對(duì)于對(duì)稱矩陣中的任意數(shù)組元素aij，若令I(lǐng)?=?max(i,j)，J?=?min(i,j)，則將上面兩個(gè)式子綜合起來(lái)得到：k?=?I?×?(I-1)/2?+?J。如圖為一個(gè)三角矩陣，其中c為某個(gè)常數(shù)。其中：(a)為下三角矩陣：主對(duì)角線以上均為同一個(gè)常數(shù)；(b)為上三角矩陣，主對(duì)角線以下均為同一個(gè)常數(shù)；5.2.2三角矩陣下面討論它們的壓縮存儲(chǔ)方法，可以借用對(duì)稱矩陣的壓縮存儲(chǔ)方法

3

cccc62

ccc481

cc

7460

c8295734810c

2946cc

157

ccc

08cccc

7(a)下三角矩陣(b)上三角矩陣1

下三角矩陣中元素aij(i>j)在一維數(shù)組A中，A數(shù)組的大小為？k=i*(i-1)/2+j-1當(dāng)i≥jn*(n+1)/2當(dāng)i<j2上三角矩陣，也可以將其壓縮存儲(chǔ)到一個(gè)大小為n(n+1)/2的一維數(shù)組A中。其中元素aij(i<j)在數(shù)組A中的存儲(chǔ)位置為：k=j*(j-1)/2+i-1當(dāng)i≤jn*(n+1)/2當(dāng)i>jn*(n+1)/2+1其中元素aij(i<j)在數(shù)組A中的存儲(chǔ)位置為：主對(duì)角線上下方各有b條次對(duì)角線。b為矩陣的半帶寬，2b+1為矩陣的帶寬，常見的有三對(duì)角、五對(duì)角、七對(duì)角矩陣。5.2.3帶狀矩陣若矩陣中所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱此矩陣為對(duì)角矩陣。如圖所示為三對(duì)角矩陣：對(duì)角矩陣具有如下特點(diǎn)：Am×n=a11a12

a21a22a23a32a33a34a43a44a45……………

1.確定存儲(chǔ)該矩陣所需的一維向量空間的大小假設(shè)每個(gè)非零元素所占空間的大小為1個(gè)單元。所需一維向量空間的大小為2+2+3(n-2)=3n-2以三對(duì)角矩陣為例討論對(duì)角矩陣的壓縮存儲(chǔ)Loc[i,j]=Loc[0,0]+前i行非零元個(gè)數(shù)+第i行中aij前非零元個(gè)數(shù);前i行元素個(gè)數(shù)為：3×(i-1)+2(因?yàn)榈?行只有2個(gè)非零元素);第i行中aij前非零元素個(gè)數(shù)=j-i+1，其中2.確定非零元素在一維數(shù)組空間中的位置-1(j<i)0(j=i)1(j>i)j-i=由此得到:Loc[i,j]=Loc[0,0]+3(i-1)+2+j-i+1=Loc[0,0]+2i+j5.3稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣：設(shè)m×n矩陣中有t個(gè)非零元素，且t<<m×n，這樣的矩陣稱為稀疏矩陣。5.3.1稀疏矩陣的三元組表示在很多科學(xué)管理及工程計(jì)算中，常會(huì)遇到階數(shù)很高的大型稀疏矩陣。若按常規(guī)的存儲(chǔ)方法，將會(huì)浪費(fèi)很多內(nèi)存。提出另外的存儲(chǔ)方法：僅存放非零元素。由于這類矩陣，通常零元素分布沒(méi)有規(guī)律，所以：將非零元素所在的行號(hào)、列號(hào)、及值構(gòu)成一個(gè)三元組，然后再按某種規(guī)律存儲(chǔ)這些三元組，便可以節(jié)約存儲(chǔ)空間。

defineSMAX1024 /*一個(gè)足夠大的數(shù)*/typedefstruct{inti,j; /*非零元素的行、列*/datatypev; /*非零元素值*/}SPNode; /*三元組類型*/typedefstruct{intmu,nu,tu; /*矩陣的行、列及非零元素的個(gè)數(shù)*/SPNodedata[SMAX]; /*三元組表*/}SPMatrix; /*三元組表的存儲(chǔ)類型*/三元組表的類型說(shuō)明如下：

所謂矩陣轉(zhuǎn)置，是指變換元素的位置，把位于(row，col)位置上的元素?fù)Q到(col，row)位置上，也就是說(shuō)，把元素的行、列互換。采用矩陣的正常存儲(chǔ)方式時(shí)，實(shí)現(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}

顯然，時(shí)間復(fù)雜度為O(m?×?n)。1稀疏矩陣的轉(zhuǎn)置在A的三元組存儲(chǔ)基礎(chǔ)上得到B的三元組表存儲(chǔ)算法思路：①由A的行數(shù)、列數(shù)、非零元數(shù)目轉(zhuǎn)化成B的列數(shù)、行數(shù)、非零元數(shù)目。②按A的列(B的行)進(jìn)行循環(huán)處理：對(duì)A的每一列掃描三元組，找出相應(yīng)的元素，若找到，則交換其行號(hào)與列號(hào)，并存儲(chǔ)到B的三元組中。1SPMatrix*TransM1(SPMatrix*A)2{SPMatrix*B;3intp,q,col;4B=(SPMatrix*)malloc(sizeof(SPMatrix));/*申請(qǐng)存儲(chǔ)空間*/5B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;/*稀疏矩陣的行、列、元素個(gè)數(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++)/*掃描整個(gè)三元組表*/10if(A->data[p].j==col)11{B->data[q].i=A->data[p].j;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*/時(shí)間復(fù)雜度為O(A.n×A.len),最壞情況當(dāng)A.len=A.m×A.n時(shí)，時(shí)間復(fù)雜度為O(A.m×A.n2)。依次按三元組表A的次序進(jìn)行轉(zhuǎn)置，轉(zhuǎn)置后直接放到三元組表B的正確位置上。這種轉(zhuǎn)置算法稱為快速轉(zhuǎn)置算法。

為了能將待轉(zhuǎn)置三元組表A中元素一次定位到三元組表B的正確位置上，需要預(yù)先計(jì)算以下數(shù)據(jù)：待轉(zhuǎn)置矩陣每一列中非零元素的個(gè)數(shù)。(2)待轉(zhuǎn)置矩陣每一列中第一個(gè)非零元素在三元組表B中的正確位置?？焖俎D(zhuǎn)置方法：為此，需要設(shè)兩個(gè)數(shù)組num[col]————用來(lái)存放A中第col列非零元素個(gè)數(shù)cpot[col]————用來(lái)存放A中第col列中第一個(gè)非零元素在三元組表B中的正確位置。舉例：col90781687531Position[col]01222num[col]54321-746815167182562434514634-3133931212211ecolrow14368-7647244369135185241212315612-3311ecolrow(a)三元組表A(b)三元組表B其中：(1)num[col]的計(jì)算方法：將三元組表A掃描一遍，對(duì)于其中列號(hào)為k的元素，給相應(yīng)的num[k]加1。(2)position[col]的計(jì)算方法：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;intnum[MAXSIZE],cpot[MAXSIZE];B->tu=A->tu;B->nu=A->mu;B->mu=A->nu;if(B->tu){for(col=1;col<=A->nu;col++)num[col]=0;for(t=1;t<=A->tu;t++)num[A->data[t].col]++;

將矩陣A轉(zhuǎn)置為B所指的矩陣計(jì)算每一列的非零元素的個(gè)數(shù)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列第一個(gè)非零元素在B.data[]的位置快速轉(zhuǎn)置算法時(shí)間耗費(fèi)在四個(gè)并列的單循環(huán)上，這四個(gè)并列的單循環(huán)分別執(zhí)行了A.nu，A.tu，A.nu，A.tu次；因而總的時(shí)間復(fù)雜度為O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。當(dāng)待轉(zhuǎn)置矩陣M中非零元素個(gè)數(shù)接近于A.mu×A.nu時(shí)，其時(shí)間復(fù)雜度接近于經(jīng)典算法的時(shí)間復(fù)雜度O(A.mu×A.nu)?？臻g耗費(fèi)上除了三元組表所占用的空間外，還需要兩個(gè)輔助向量空間，即num[1..A->nu]，cpot[1..A->nu]?？梢?，算法在時(shí)間上的節(jié)省，是以更多的存儲(chǔ)空間為代價(jià)的。

2)用三元組表實(shí)現(xiàn)稀疏矩陣的乘法運(yùn)算兩個(gè)矩陣相乘也是矩陣的一種常用的運(yùn)算。設(shè)矩陣M是m1×n1矩陣，N是m2×n2矩陣；若可以相乘，則必須滿足矩陣M的列數(shù)n1與矩陣N的行數(shù)m2相等，才能得到結(jié)果矩陣Q=M×N（一個(gè)m1×n2的矩陣）因?yàn)槿M表只對(duì)矩陣的非零元素做存儲(chǔ)。所以可以采用固定三元組表a中的元素(i,k,D1)（1≤i≤m1,1≤k≤n1），在三元組表b中找所有行號(hào)為k的對(duì)應(yīng)元素(k,j,D2)（1≤k≤m2,1≤j≤n2）進(jìn)行相乘、累加，從而得到Q[i][j]，即以三元組表a中的元素為基準(zhǔn)，依次求出其與三元組表b的有效乘積。算法中附設(shè)兩個(gè)向量num[]、first[]，其中num[row]表示三元組表b中第row行非零元素個(gè)數(shù)（1≤row≤m2），first[row]表示三元組表b中第row行第一個(gè)非零元素所在的位置。顯然，first[row+1]-1指向三元組表b中第row行最后一個(gè)非零元素的位置。與用二維數(shù)組存儲(chǔ)稀疏矩陣比較，用三元組表表示的稀疏矩陣不僅節(jié)約了空間，而且使得矩陣某些運(yùn)算的運(yùn)算時(shí)間比經(jīng)典算法還少。但是在進(jìn)行矩陣加法、減法和乘法等運(yùn)算時(shí)，有時(shí)矩陣中的非零元素的位置和個(gè)數(shù)會(huì)發(fā)生很大的變化。如A=A+B，將矩陣B加到矩陣A上，此時(shí)若還用三元組表表示法，勢(shì)必會(huì)為了保持三元組表“以行序?yàn)橹餍颉倍罅恳苿?dòng)元素。5.3.2稀疏矩陣的十字鏈表存儲(chǔ)**在十字鏈表中，矩陣的每一個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示，該結(jié)點(diǎn)除了（row，col，value）以外，還要有以下兩個(gè)鏈域：right：用于鏈接同一行中的下一個(gè)非零元素；down：用于鏈接同一列中的下一個(gè)非零元素。再附設(shè)一個(gè)存放所有行鏈表的頭指針的一維數(shù)組和一個(gè)存放所有列鏈表的頭指針的一維數(shù)組。圖5.15(b)給出了稀疏矩陣圖5.15(a)的十字鏈表。downrightvaluecolrow圖5.14十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)A＝300504003000(a)稀疏矩陣∧311422∧541∧313∧∧(b)十字鏈表圖5.15一個(gè)稀疏矩陣的十字鏈表十字鏈表的結(jié)構(gòu)類型說(shuō)明如下：typedefstructOLNode{introw,col;datatypevalue;structOLNode*right,*down;}OLNode;*OLink;非零元素的行和列下標(biāo)非零元所在行、列表的后繼鏈域typedefstruct{OLink*row_head,*col_head;intm,n,len;}CrossList;

行、列鏈表的頭指針向量稀疏矩陣的行數(shù)、列數(shù)、非零元素的個(gè)數(shù)

CreateCrossList(CrossList*M){if(M!=NULL)free(M);scanf(&m,&n,&t);

M->m=m;M->n=n;M->len=t;if(!(M->row_head=(OLink*)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW);if(!(M->col-head=(OLink*)malloc((n+1)*sizeof(OLink))))exit(OVERFLOW);M->row_head[]=M->col_head[]=NULL;

for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;if(M->row-head［i］==NULL)M->row-head［i］=p;采用十字鏈表存儲(chǔ)結(jié)構(gòu)，創(chuàng)建稀疏矩陣M輸入M的行數(shù),列數(shù)和非零元素的個(gè)數(shù)初始化行、列頭指針向量，各行、列鏈表為空的鏈表生成結(jié)點(diǎn)建立稀疏矩陣的十字鏈表的算法：else{for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right)p->right=q->right;q->right=p;}if(M->col_head[j]==NULL)M->col_head[j]=p;else{for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down)p->down=q->down;q->down=p;}}}建十字鏈表的算法的時(shí)間復(fù)雜度為O(t×s)，s=MAX(m,n)。尋找行表中的插入位置完成插入尋找列表中的插入位置完成插入5.4廣義表是n個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an的有序序列。一般記為：ls=（a1，a2，a3，…，an）廣義表廣泛地應(yīng)用于人工智能等領(lǐng)域的表處理語(yǔ)言LISP語(yǔ)言中。用二元組表示：List(D,R)D={ai|ai∈Atomset或ai∈Lists}R={<ai,ai+1>|ai,ai+1∈D;1<=i<=n-1}其中

（1）ai是單個(gè)元素或是一個(gè)廣義表，稱為ls的原子或子表（2）長(zhǎng)度：n是廣義表的長(zhǎng)度。（3）表頭：a1是廣義表ls的表頭（4）表尾：其余元素組成的表是表尾。（5）廣義表示一個(gè)遞歸定義的表。⒈廣義表的定義D=()空表；其長(zhǎng)度為零。A=(a,(b,c))

表長(zhǎng)度為2的廣義表，其中第一個(gè)元素是單個(gè)數(shù)據(jù)a，第二個(gè)元素是一個(gè)子表(b，c)。

B=(A,A,D)長(zhǎng)度為3的廣義表，其前兩個(gè)元素為表A，第三個(gè)元素為空表D。C=(a,C)長(zhǎng)度為2遞歸定義的廣義表，C相當(dāng)于無(wú)窮表(a，(a,(a，(…))))。下面給出一些廣義表的例子，以加深對(duì)廣義表概念的理解。下面以廣義表A為例，說(shuō)明求表頭、表尾的操作：head(A)=a

表A的表頭是a。tail(A)=((b,c))

表A的表尾是((b,c))。廣義表的表尾一定是一個(gè)表。⑴廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，…。⑵廣義表可以是遞歸的表。例如表C就是一個(gè)遞歸的表。⑶廣義表可以為其它表所共享。如廣義表B就共享表A。在表B中不必列出表A的內(nèi)容，只要通過(guò)子表的名稱就可以引用該表。⒉廣義表的性質(zhì)從上述廣義表的定義和例子可以得到廣義表的重要性質(zhì)：⒊廣義表基本運(yùn)算基本操作，取頭操作（Head）和取尾操作（Tail）。根據(jù)廣義表的表頭、表尾的定義可知，對(duì)于任意一個(gè)非空的廣義表，其表頭可能是單元素也可能是廣義表，而表尾必為廣義表。A＝()B＝(e)C＝(a,(b,c,d))D＝(A,B,C)E＝(a,E)F＝(())例如：head(B)＝etail(B)=()head(C)＝atail(C)=(b,c,d)head(D)=Atail(D)=(B,C)head(E)=atail(E)=(E)Head(F)=()tail(F)=()那么：例如：L=(a，