5￥-five(天津科技大學)

第五章

數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲

5.3.1特殊矩陣

5.3.2稀疏矩陣

5.4廣義表的定義

5.5廣義表的存儲結構10/1/20241第五章數(shù)組和廣義表數(shù)組和廣義表簡單描述數(shù)組和廣義表可看成是一種特殊的線性表。表中的元素本身也是一種數(shù)據(jù)結構。數(shù)組的的數(shù)據(jù)元素是數(shù)組；廣義表的數(shù)據(jù)元素可以是原子類型，也可以是廣義表，分別稱為廣義表的原子項和子表10/1/20242第五章數(shù)組和廣義表

5.1數(shù)組的定義

數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級語言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標一般具有固定的上界和下界，因此，數(shù)組的處理比其它復雜的結構更為簡單。多維數(shù)組是向量的推廣。例如，二維數(shù)組：

a11a12…a1na21a22…a2n…………am1am2…amn

Amn=10/1/20243第五章數(shù)組和廣義表二維數(shù)組二維數(shù)組可以看成是由若干個行向量組成的向量，也可以看成是若干個列向量組成的向量。在C語言中，一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說，

typedef

elemtypearray2[m][n];

等價于：

typedef

elemtypearray1[n];

typedefarray1array2[m];10/1/20244第五章數(shù)組和廣義表多維數(shù)組一個n維數(shù)組類型可以定義為其數(shù)據(jù)元素為n-1維數(shù)組類型的一維數(shù)組類型。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。除了結構的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作（共四個操作）。多維數(shù)組抽象數(shù)據(jù)類型定義見P9010/1/20245第五章數(shù)組和廣義表5.2數(shù)組的順序表示和實現(xiàn)

由于計算機的內(nèi)存結構是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一個序列，然后將這個線性序列存放在存儲器中。由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結構中的元素個數(shù)和元素間的關系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。

10/1/20246第五章數(shù)組和廣義表兩種順序存儲方式：⑴行優(yōu)先順序——將數(shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

在PASCAL、C語言中，數(shù)組就是按行優(yōu)先順序存儲的。10/1/20247第五章數(shù)組和廣義表兩種順序存儲方式（續(xù)）⑵列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，A的m*n個元素按列優(yōu)先順序存儲的線性序列為：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN語言中，數(shù)組就是按列優(yōu)先順序存儲的。10/1/20248第五章數(shù)組和廣義表多維數(shù)組順序存儲方式以上規(guī)則可以推廣到多維數(shù)組的情況：優(yōu)先順序可規(guī)定為先排最右的下標，從右到左，最后排最左下標：列優(yōu)先順序與此相反，先排最左下標，從左向右，最后排最右下標。按上述兩種方式順序存儲的序組，只要知道開始結點的存放地址（即基地址），維數(shù)和每維的上、下界，以及每個數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時間內(nèi)存取，即順序存儲的數(shù)組是一個隨機存取結構。10/1/20249第五章數(shù)組和廣義表二維數(shù)組元素的存取二維數(shù)組Amn按“行優(yōu)先順序”存儲在內(nèi)存中，假設每個元素占用L個存儲單元。元素aij的存儲地址應是數(shù)組的基地址加上排在aij前面的元素所占用的單元數(shù)。因為aij位于第i行、第j列，前面i-1行一共有(i-1)×n個元素，第i行上aij前面又有j-1個元素，故它前面一共有(i-1)×n+j-1個元素，因此，aij的地址計算函數(shù)為：

LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*L10/1/202410第五章數(shù)組和廣義表二維數(shù)組A[c1..d1,c2..d2]分析：aij前一共有i-c1行，二維數(shù)組一共有d2-c2+1列，故這i-c1行共有(i-c1)*(d2-c2+1)個元素，第i行上aij前一共有j-c2個元素，因此，aij的地址計算函數(shù)為：

LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L在C語言中，數(shù)組各維下標的下界是0，因此二維數(shù)組Amn的地址計算公式為：

LOC(aij)=LOC(a00)+(i*n+j)*L數(shù)組的順序存儲表示和實現(xiàn)見P93

10/1/202411第五章數(shù)組和廣義表5.3矩陣的壓縮存儲在科學與工程計算問題中，矩陣是一種常用的數(shù)學對象，在高級語言編制程序時，簡單而又自然的方法，就是將一個矩陣描述為一個二維數(shù)組。矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲密度仍為1，但實際上占用了許多單元去存儲重復的非零元素或零元素，這對高階矩陣會造成極大的浪費.為了節(jié)省存儲空間，我們可以對這類矩陣進行壓縮存儲：即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。10/1/202412第五章數(shù)組和廣義表特殊矩陣

所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲。

1、對稱矩陣

2、三角矩陣

3、對角矩陣10/1/202413第五章數(shù)組和廣義表對稱矩陣在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≦i,j≦n-1

則稱A為對稱矩陣。如下圖是一個5階對稱矩陣。

15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1

10/1/202414第五章數(shù)組和廣義表對稱矩陣（續(xù)）對稱矩陣中的元素關于主對角線對稱，故只要存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節(jié)約近一半的存儲空間。不失一般性，我們按“行優(yōu)先順序”存儲主對角線（包括對角線）以下的元素，其存儲形式如上頁圖所示。10/1/202415第五章數(shù)組和廣義表對稱矩陣的存儲表示

在這個下三角矩陣中，第i行恰有i+1個元素，元素總數(shù)為：

(i+1)=n(n+1)/2因此，我們可以按行優(yōu)先的次序?qū)⑦@些元素存放在一個向量sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個對應關系。10/1/202416第五章數(shù)組和廣義表

對稱矩陣的存儲表示若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個元素，在第i行上，

aij之前恰有j個元素（即ai0,ai1,ai2,…,aij-1），因此有：

k=i*(i+1)/2+j0≦k<n(n+1)/2

若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應關系式中的i和j即可得到：

k=j*(j+1)/2+i0≦k<n(n+1)/210/1/202417第五章數(shù)組和廣義表對稱矩陣的存儲表示（續(xù)）aij的地址可用下列式子計算：

LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*L=LOC(sa[0]）+[I*(I+1)/2+J]*L有了上述的下標交換關系，對于任意給定一組下標(i，j)，均可在sa[k]中找到矩陣元素aij，反之，對所有的k=0,1,2,…，n(n-1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(i,j)。10/1/202418第五章數(shù)組和廣義表對稱矩陣的存儲表示（續(xù)）稱sa[n(n+1)/2]為對稱矩陣A的壓縮存儲，見下圖：k=0123n(n-1)/2n(n+1)/2-1例如a21和a12均存儲在sa[4]中，這是因為

k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20……an-10……an-1,n-110/1/202419第五章數(shù)組和廣義表三角矩陣以主對角線劃分，三角矩陣有上三角和下三角兩種。如圖所示，上三角矩陣的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)。在大多數(shù)情況下，三角矩陣常數(shù)為零。

a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩陣(b)下三角矩陣10/1/202420第五章數(shù)組和廣義表三角矩陣的存儲表示三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中。上三角矩陣中，主對角線之上的第p行(0≦p<n)恰有n-p個元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時，aij之前的i行一共有

(n-p)=i(2n-i+1)/2

個元素，在第i行上，aij前恰好有j-i個元素：aij,aij+1,…aij-1。10/1/202421第五章數(shù)組和廣義表三角矩陣的存儲表示（續(xù)）上三角矩陣中，sa[k]和aij的對應關系是：

i(2n-i+1)/2+j-i當i≦jn(n+1)/2當i>j下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關系是：

i(i+1)/2+ji≧jn(n+1)/2i<jk=k=10/1/202422第五章數(shù)組和廣義表對角矩陣對角矩陣中，所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣。

a00a01a10a11a12a21a22a23….…..….an-2n-3an-2n-2an-2n-1an-1n-2an-1n-110/1/202423第五章數(shù)組和廣義表對角矩陣的存儲表示非零元素僅出現(xiàn)在主對角(aii,0≦i≦n-1上，緊鄰主對角線上面的那條對角線上(aii+1,0≦i≦n-2)和緊鄰主對角線下面的那條對角線上(ai+1i,0≦i≦n-2)。顯然，當∣i-j∣>1時，元素aij=0。由此可知，一個k對角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應關系。10/1/202424第五章數(shù)組和廣義表對角矩陣的存儲表示（續(xù)）在三對角矩陣里附滿足條件i=0，j=0、1，或i=n-1j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。對這種矩陣，我們也可按行優(yōu)序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都是3個，因此，需存儲的元素個數(shù)為3n-2。10/1/202425第五章數(shù)組和廣義表對角矩陣的存儲表示（續(xù)）K=012345……3n-23n-1

數(shù)組sa中的元素sa[k]與三對角帶狀矩陣中的元素aij存在一一對應關系，在aij之前有i行,共有3*i-1個非零元素，在第i行，有j-i+1個非零元素.a00a01

a10a11a12a21

……an-1n-2an-1n-110/1/202426第五章數(shù)組和廣義表特殊矩陣存儲方法小結

上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一個向量中，并且一般都能找到矩陣中的元素與該向量的對應關系，通過這個關系，仍能對矩陣的元素進行隨機存取。10/1/202427第五章數(shù)組和廣義表

稀疏矩陣設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。設在的矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e≦0.05時稱之為稀疏矩陣。10/1/202428第五章數(shù)組和廣義表稀疏矩陣的存儲存儲稀疏矩陣時，為了節(jié)省存儲單元，應使用壓縮存儲方法。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。10/1/202429第五章數(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)這一對行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000M=T=10/1/202430第五章數(shù)組和廣義表

矩陣的壓縮存儲-稀疏矩陣設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數(shù)（即s<<m×n），則稱A為稀疏矩陣。設在的矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e≦0.05時稱之為稀疏矩陣。10/1/202431第五章數(shù)組和廣義表稀疏矩陣的存儲存儲稀疏矩陣時，為了節(jié)省存儲單元，應使用壓縮存儲方法。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。10/1/202432第五章數(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)這一對行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000M=T=10/1/202433第五章數(shù)組和廣義表稀疏矩陣的抽象數(shù)據(jù)類型定義數(shù)據(jù)對象：

D={aij}數(shù)據(jù)關系：

R={Row,Col}基本操作：CreateSMtrix,DestroySMtrix,PrintSMtrix,CopySMtrix,AddSMtrix,SubtSMtrix,MultSMtrix,TransposeSMtrix10/1/202434第五章數(shù)組和廣義表稀疏矩陣的三元組的表示#definemaxsize10000Typedef

struct{

inti,j;//非零元的行下標和列下標

ElemTypee;}Triple;10/1/202435第五章數(shù)組和廣義表稀疏矩陣的三元組表的順序表示typedef

struct{tripledata[maxsize];

intm,n,t;}tripletable;

其中m,n,t分別表示矩陣的行數(shù)，列數(shù)和非零元個數(shù)設A為tripletable型的結構變量，圖5.4中所示的稀疏矩陣的三元組的表示如右表

ijv121213931-3361443245218611564-710/1/202436第五章數(shù)組和廣義表矩陣轉置的有關概念一個m×n的矩陣A，它的轉置B是一個n×m的矩陣，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。一個稀疏矩陣的轉置矩陣還是稀疏矩陣若a和b是tripletable型的變量，分別表示M和T，如何由a得到b？將矩陣的行列值相互交換將每個三元組中i和j相互調(diào)換重排三元組之間的次序（關鍵點）10/1/202437第五章數(shù)組和廣義表矩陣轉置前后的三元組表ijv121213931-3361443245218611564-7

ijv13-3161521122518319342446-76314b.dataa.data10/1/202438第五章數(shù)組和廣義表矩陣的轉置操作的實現(xiàn)將A轉置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個按列優(yōu)先順序存儲的稀疏矩陣B，要得到按行優(yōu)先順序存儲的b.data，就必須重新排列三元組的順序。由于A的列是B的行，因此，按a.data的列序轉置，所得到的轉置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。10/1/202439第五章數(shù)組和廣義表矩陣的轉置操作（續(xù)）算法的基本思想是：對A中的每一列col(0≦col≦n-1)，通過從頭至尾掃描三元表a.data，找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放入b.data中，即可得到B的按行優(yōu)先的壓縮存儲表示。具體算法描述如下頁。10/1/202440第五章數(shù)組和廣義表Voidtransmatrix(tripletablea,tripletableb){

intp,q,col;b.m=a.n;b.n=a.m;b.t=a.t;if(b.t<=0)

printf(“A=0\n”);q=0;

10/1/202441第五章數(shù)組和廣義表

for(col=1;col<=a.n;col++)for(p=0;p<=a.t;p++)if(a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;q++;}}

10/1/202442第五章數(shù)組和廣義表矩陣的轉置操作算法分析主要的工作是在p和col的兩個循環(huán)中完成的，故算法的時間復雜度為O(n*t)，即矩陣的列數(shù)和非零元的個數(shù)的乘積成正比。矩陣的傳統(tǒng)轉置算法為：

for(col=0;col<=n-1;++col)for(row=0;row<=m;++row)

t[col][row]=m[row][col];

其時間復雜度為O(n*m)。當非零元素的個數(shù)t和m*n同數(shù)量級時，算法transmatrix的時間復雜度為O(m*n2)。10/1/202443第五章數(shù)組和廣義表算法分析（續(xù)）三元組順序表雖然節(jié)省了存儲空間，但時間復雜度比一般矩陣轉置的算法還要復雜，同時也增加了算法的難度。因此，此算法僅適用于t<<m*n的情況。10/1/202444第五章數(shù)組和廣義表快速轉置的算法簡介算法思想為：對A掃描一次，按A第二列提供的列號一次確定位置裝入B的一個三元組。具體實施如下：一遍掃描先確定三元組的位置關系，二次掃描由位置關系裝入三元組?？梢姡恢藐P系是此種算法的關鍵。為了預先確定矩陣M中的每一列的第一個非零元素在數(shù)組B中應有的位置，需要先求得矩陣M中的每一列中非零元素的個數(shù)。因為：矩陣M中第一列的第一個非零元素在數(shù)組B中應有的位置等于前一列第一個非零元素的位置加上前列非零元素的個數(shù)。10/1/202445第五章數(shù)組和廣義表其它存儲方法行邏輯鏈接的順序表—為了便于隨機存取任意一行的非零元，需知道每一行的第一個非零元在三元組表中的位置十字鏈表—當矩陣的非零元個數(shù)和位置在操作過程中變化較大時，應采用鏈式存儲結構表示三元組。類似于雙向鏈表。10/1/202446第五章數(shù)組和廣義表5.4廣義表的定義廣義表（Lists，又稱列表）是線性表的推廣。線性表為n>=0個元素a1,a2,a3,…,an的有限序列。線性表的元素僅限于原子項，原子是作為結構上不可分割的成分，它可以是一個數(shù)或一個結構，若放松對表元素的這種限制，容許它們具有其自身結構，這樣就產(chǎn)生了廣義表的概念。廣義表是n(n>=0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。通常記作LS=（a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS的子表。抽象數(shù)據(jù)類型廣義表的定義見教材P10710/1/202447第五章數(shù)組和廣義表廣義表的有關概念通常用圓括號將廣義表括起來，用逗號分隔其中的元素。為了區(qū)別原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。若廣義表LS（n>=1)非空，則a1是LS的表頭，其余元素組成的表(a1,a2,…an)稱為LS的表尾。廣義表的深度定義為廣義表中括弧的重數(shù)，是廣義表的一種量度。顯然廣義表是遞歸定義的，這是因為在定義廣義表時又用到了廣義表的概念。10/1/202448第五章數(shù)組和廣義表廣義表的例子（1）A=（）——A是一個空表，其長度為零。（2）B=（e）——表B只有一個原子e，B的長度為1。（3）C=（a,(b,c,d))——表C的長度為2，兩個元素分別為原子a和子表(b,c,d)。（4）D=（A，B，C）——表D的長度為3，三個元素都是廣義表。顯然，將子表的值代入后，則有D=((),(e),(a,(b,c,d)))。（5）E=（E）——這是一個遞歸的表，它的長度為2，

E相當于一個無限的廣義表E=(a,(a,(a,(a,…)))).10/1/202449第五章數(shù)組和廣義表廣義表的三個重要結論廣義表的元素可以是子表，而子表的元素還可以是子表，。由此，廣義表是一個多層次的結構，可以用圖形象地表示見P108廣義表可為其它表所共享。例如在上述例4中，廣義表A，B，C為D的子表，則在D中可以不必列出子表的值，而是通過子表的名稱來引用。廣義表的遞歸性。綜上所述，廣義表不僅是線性表的推廣，也是樹的推廣。10/1/202450第五章數(shù)組和廣義表廣義表的操作任何一個非空廣義表其表頭可能是原子，也可能是廣義表，而其表尾必定是廣義表。

gethead(B)=egettail(B)=()

gethead(D)=Agettail(D)=(B,C)

由于（B，C）為非空廣義表，則可繼續(xù)分解得到：

gethead(B,C)=Bgettail(B,C)=(C)

注意廣義表（）和(())不同。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而后者是長度為1的非空表（只不過該表中唯一的一個元素是空表）。對其可進行分解，得到表頭和表尾均為空表（）。10/1/202451第五章數(shù)組和廣義表5.5廣義表的存儲結構由于廣義表(a1,a2,a3,…an)中的數(shù)據(jù)元素可以具有不同的結構，（或是原子，或是廣義表），因此，難以用順序存儲結構表示，通常采用鏈式存儲結構，每個數(shù)據(jù)元素可用一個結點表示。由于廣義表中有兩種數(shù)據(jù)元素，原子或廣義表，因此，需要兩種結構的結點：一種是表結點，一種是原子結點。10/1/202452第五章數(shù)組和廣義表廣義表的鏈式存儲結構（一）

表結點由三個域組成：標志域、指示表頭的指針域和指示表尾的指針域；而原子域只需兩個域：標志域和值域。表結點原子結點tag=1hp

tptag=0atom10/1/202453第五章數(shù)組和廣義表類型定義t