數據結構數組和廣義表1第1頁，共33頁，2023年，2月20日，星期六數組描述設二維數組: 其中:m、n為行列數,aij為第i行、第j列的元素,0≤i≤m-1,0≤j≤n-1;元素個數為m×n。二維數組可用形式化語言描述，即：

A(2)=(D,R)其中：D={aij|aij∈datatype,0≤i≤m-1,0≤j≤n-1};R={Row,Col}行關系：Row={<aij,aij+1>|aij,aij+1∈D,0≤i≤m-1,0≤j≤n-2}列關系：Col={<aij,ai+1j>|aij,ai+1j∈D,0≤i≤m-2,0≤j≤n-1}

a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A(2)=A[m][n]=2第2頁，共33頁，2023年，2月20日，星期六數組描述 關系集Row和Col表明：除數組A(2)周邊元素外的其它任一個元素aij，有兩個直接前驅ai-1j，aij-1,和兩個直接后繼ai+1j，aij+1(周邊元素的前驅或后繼可不足兩個)。n維數組也可按上述方法類似定義。 二維數組可如下描述:

多維數組是線性表的推廣，而線性表是多維數組的特例。A[0]…A[i]

…A[m-1]=(A[0]………A[i]…….…A[m-1])-----線性表形式a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A(2)=A[m][n]=3第3頁，共33頁，2023年，2月20日，星期六5.1.1數組的抽象數據類型 在算法語言中，數組一旦生成，其元素的存儲空間就固定下來，故數組的運算一般不包括插入和刪除這樣的操作。ADTArray{D={aj1j2…jn|aj1j2…jn∈datatype，ji=0,…,bi-1其中i=1,2,…,n}n(n>0)為數組維數，bi是第i維長度，ji是數組元素第i維下標。 R={R1,R2,…,Rn} 其中：Ri={<aj1…ji…jn,aj1…ji+1…jn>|0≤jk≤bk-1，1≤k≤n且k≠i，0≤ji≤bi-2，aj1…ji…jn,aj1…ji+1…jn∈D，i=1,2,…,n} PArrayInit(&A,n,d1，d2,......dn) 操作結果：若維數n和各維長度合法，則生成一個n維數組A[d1][d2].....[dn]（C語言中，1≤n≤8）。ArrayDestroy(&A) 初始條件：數組A存在。操作結果：撤銷數組A。ArrayGet(A,i1,...,in,&e) 初始條件：數組A存在，e∈datatype。操作結果：若各下標合法，則將元素A[i1][i2],...,[in]的值傳給變量e。4第4頁，共33頁，2023年，2月20日，星期六數組的抽象數據類型ArrayAssign(&A,i1,...,in,e) 初始條件：數組A存在，e∈datatype。 操作結果：若各下標合法，則將變量e的值傳給數組元素A[i1][i2],...,[in]。}ADTArray；5.2數組的存儲結構由于計算機的存儲空間是一維的（或線性的），所以存儲數組時，要將多維數組中的元素按某種次序映象到一維存儲空間，即解決“降維”問題。5.2.1數組的靜態存儲方式1．數組的靜態存儲映像

在PASCAL和C等語言中，是按低維下標優先變化（或按行優先）的方式，存儲數組中的元素。如在C語言中，二維數組的映像如圖5.1所示。但在FORTRAN語言中，數組元素是按高維下標優先變化或按列優先方式，存儲數組中的元素。 5第5頁，共33頁，2023年，2月20日，星期六數組的存儲映像

a00…a0,n-1…ai0…ai,n-1……am-1,n-1映像

（存儲器）a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A[m][n]=圖5.1思考：1.三維以上數組如何映像? 2.“按列優先”如何映像?6第6頁，共33頁，2023年，2月20日，星期六2.靜態數組元素的地址計算以C語言為例。設數組元素的起始地址為b,每個元素占用L個單元（元素所占單元量由元素的類型而定），元素a的地址用Loc(a)表示。1）一維數組： 即:Loc(a0)=b; Loc(a1)=b+L;

Loc(ai)=b+i×L;

規律：任一元素ai的地址:

a0a1

…ai-1ai…an-1A[n]=(

a0,

a1,……ai

,……an-1)

起始地址b+(ai前的元素個數i)×L

起址b:b+L:……b+i?L:L圖5.27第7頁，共33頁，2023年，2月20日，星期六數組元素的地址計算2）二維數組：a00…a0,n-1…ai0…aij……am-1,n-1由圖5.3知：Loc(a00)=b Loc(ai0)=b+(ai0前元素個數)?L=b+(i?n)?L

Loc(aij)=b+(aij前元素個數)?L=b+[i×n+j]×L例5-1設二維數組A[7][8]，起始地址b=1000，每個元素所占單元量L=3，則Loc(a5,6)=1000+(5?8+6)3=1138。

inj映像

起址b:b+L:……b+[i×n]×L:…b+[i?n+j]?L:圖5.3a00a01

……a0j……

a0n-1………………….ai0ai1

……aij….…

ain-1………….am-10am-11

…am-1j…

am-1n-1A[m][n]=8第8頁，共33頁，2023年，2月20日，星期六數組元素的地址計算3）三維數組：

由圖5.5可知： Loc(a000)=b圖5.5 Loc(ai00)=b+(i?n?p)?L Loc(aij0)=b+(i?n?p+j?p)?L

Loc(aijk)=b+(i×n×p+j×p+k)×Laijk前的元素個數。a000ai00aij0aijk9第9頁，共33頁，2023年，2月20日，星期六數組元素的地址計算4）n維數組從以上的地址公式推導中得出這樣一條規律：數組中任一元素的地址=起址b+該元素前的個數×元素單元量L。故n維數組A[u1][u2]…..[un]中任一元素ai1....in的地址為：Loc(ai1i2……in)=b+(i1?u2?u3?

…

?un+i2?u3?u4?

…un+…+in-1?un+in)?L

=b+()×L 元素按“列優先”方式存儲時，地址計算方法類似，不再贅述。 有了數組元素的地址計算公式，給出相應參數后，能夠很快求出任一元素的地址，然后按地址存取相應元素，故對數組的存取是隨機存取（或按公式存取）。5.2.2數組的動態存儲方式（略）10第10頁，共33頁，2023年，2月20日，星期六5.2矩陣的壓縮存儲 信息的壓縮存儲是一項專業技術，在當今的多媒體應用中顯得尤為重要。但本節只是討論矩陣（或二維數組）中元素的壓縮存儲。 在矩陣中，往往會出現許多值相同的元素或０元素，為節省存儲空間，可以采用某些技術對這類矩陣進行壓縮存儲。壓縮存儲的原則是：對多個值相同的元素只存儲其中之一，對０元素甚至不分配存儲空間。5.3.1特殊矩陣的壓縮存儲特殊矩陣：值相同的元素或０元素在矩陣中的分布遵循一定規律。1.對稱矩陣：

滿足aij=aji，(1≤i,j≤n)a11a22

aii…

ann

An×n=

aijaji11第11頁，共33頁，2023年，2月20日，星期六特殊矩陣的壓縮 aij與aji對稱相等，二者只需分配一個存儲單元，即只存儲包括主對角線的下三角(或上三角)元素。于是An×n所需單元數為n(n+1)/2，而不壓縮存儲需要n2個單元。當n很大時，幾乎能壓縮原存儲空間的一半。 具體做法：設置數組S[n(n+1)/2+1]作為An.n的存儲空間，且按行的次序存放An×n中包括主對角線的下三角元素，如圖5.5所示。a11a21a22…aij…annS[n(n+1)/2+1]:123…..….….k………..n(n+1)/2 圖5.5其中aij存入S[k]單元，下標（i,j）與k的關系為：

i(i-1)/2+j當i≥j時；S[i(i-1)/2+j]當i≥j時；k=即：aij=

j(j-1)/2+i當i<j時。S[j(j-1)/2+i]當i<j時。a11a22

…aii

annAn×n=

aij12第12頁，共33頁，2023年，2月20日，星期六特殊矩陣的壓縮2．三角矩陣：

（下三角矩陣）（上三角矩陣）

a11a22

…aii

annAn×n=

aijCa11a22

aii…

annCaijCa11a12…aij…annS[n(n+1)/2+1]:012…..….….k………..n(n+1)/2

K=—+=(i-1)n–(i-1)(i-2)/2+(j-i+1)=(i-1)(2n-i)/2+j(i≤j)

圖5.6

而當(i>j)時，K=0.對于下三角矩陣，類似于對稱矩陣，即只存儲包括主對角線的下三角元素。而當i<j時，aij取C即可。對于上三角矩陣，壓縮方法如圖5.6所示。13第13頁，共33頁，2023年，2月20日，星期六特殊矩陣的壓縮3．對角線矩陣（三對角線）：按行順序壓縮于S中，如圖5.7所示。

Ca11a12…aij…annS[3n-1]:012…..….….k………..3n-2a11a12a21a22a23..…..…

aii-1aiiaii+1..…..…

ann-1annAn×n=

CC圖5.7

3(i-1)當i=j+1時；3i-2當i=j時；歸納為：k=2i+j-2當i=j+1,i=j,i+1=j時。3i-1當i+1=j時；如將i=1,j=2代入,k=20其他。k=14第14頁，共33頁，2023年，2月20日，星期六5.3.1稀疏矩陣的壓縮存儲 特殊矩陣中同值元素的分布有一定的規律可循，而有的矩陣，０元素很多（如同一個畫面上有幾個亮點，其余全是空白），但分布無規律，稱這類矩陣為稀疏矩陣。例5-2設一個6×7的矩陣如下： 則A6×7可以視為一個稀疏矩陣。對于矩陣Am×n，設非0元素個數為t，若δ=t/(m×n)≤0.2，則可以將其視為稀疏矩陣。顯然，為節省存儲空間，須對這類矩陣壓縮存儲空間，原則是只存儲非0元素。一般有“三元組表”和“十字鏈表”的壓縮存儲方法。010200000000003000040005000006000007008000

A6×7

=

15第15頁，共33頁，2023年，2月20日，星期六

1.三元組表 三元組：（i,j,v），其中i,j分別為非0元素的行、列號，v存放非0元的數值。以行優先的順序將矩陣中非0元以三元組形式存入一數組，即所謂的三元組表。三元組表的存儲結構的描述：#definemaxsize64//最大非0元個數typedefstruct//三元組類型{inti,j;datatypev;}tritype;//三元組說明符typedefstruct{tritypedata[maxsize+1];//三元組表intmu,nu,tu;//原矩陣的行、列、非0元個數}Tsmtype,*Tsmlink;//三元組表說明符若說明：TsmlinkA;A=(Tsmlink)malloc(sizeof(Tsmtype));則指針變量A指向一個如圖5.8所示的三元組表。 對例5-2中A6×7，設每個元素占16個字節，若不壓縮存儲，需6×7×16=672（字節），而壓縮成三元組表時，i,j為整型，故共需：2×16+8×16=160（字節）。ijv121142313364435526617648A->data[1]………………A->data[tu]

圖5.816第16頁，共33頁，2023年，2月20日，星期六三元組表的轉置 然而，稀疏矩陣的壓縮存儲會給矩陣運算帶來一些不便，算法要復雜些。這里的運算指求矩陣的轉置，兩矩陣相加和相乘等。我們只討論矩陣的轉置的算法。未壓縮前，求矩陣A的轉置矩陣B，算法很簡單：for(col=1;col<=nu;col++)for(row=1;row<=mu;row++)B[col][row]=A[row][col];例5-3：02004608000900030000

A4×5=

ijv12215421623832941306032090080000004000

B5×4=

現在，要通過A的三元組表求其轉置矩陣B的三元組表。ijv12614321223932851417第17頁，共33頁，2023年，2月20日，星期六三元組表的轉置算法思路：1)矩陣A的所有列轉化成B的所有行； 2)

對A中的每一列col(1～nu)，掃描所有非0元（1～tu），若有非0元的列號j=當前列col，則將該非0元行列互換，送到目標三元組表。 如例5-3中矩陣A，當前列col=1時，因A->data[3].j=1,故將A->data[3]轉置：(1，2，6)=>B->data[1]，又A->data[6].j=1，所以A->data[6]轉置：(1，4，3)=>B->data[2]，完成第一列的轉換，依此類推。算法描述：voidTransm(TsmtypeA,TsmtypeB){intp,q,col;B->mu=A->nu;B->nu=A->mu;B->tu=A->tu;if(A->tu!=0){q=1;//目標表的序號for(col=1;col<=A->nu;col++)for(p=1;p<=A->tn;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++;}}}18第18頁，共33頁，2023年，2月20日，星期六三元組表的轉置

ijv122154216238329413

p

12345602004608000900030000

A4×5=

12345colijv126

q

12345614321223932851406032090080000004000

B5×4=

（矩陣A的三元組表）

圖5.10

（轉置后的三元組表）算法的時間復雜度：O(t×n)n=列數,t=非0元個數。改進算法的復雜度：O(t+n)（略）19第19頁，共33頁，2023年，2月20日，星期六2.十字鏈表 十字鏈表是以鏈表結構形式存儲一個稀疏矩陣。矩陣中非0元設置成如下形式的節點：其中i、j分別存放非0元的行列號，head/data或作為一非0元的值域（data）或作為頭節點的鏈指針(head)；down為指向相同列下一個非0元節點的指針，right為指向相同行下一非0元節點的指針。節點類型描述： typedefstructnode {inti,j; union{structnode*head; datatypedata; }vdata; structnode*down,*right; }nodetype,*tlink;ijhead/datadownright20第20頁，共33頁，2023年，2月20日，星期六十字鏈表111144222313445004400000000000000L例5-4設稀疏矩陣：1004020030000005

A4×4=

A的十字鏈表如圖5.11：21第21頁，共33頁，2023年，2月20日，星期六建立十字鏈表算法思路：先構造空表，其中S取矩陣行列數的最大值，即S=max(m,n)。依次讀入每個非0元(i,j,v)，生成一個非0元的節點，對該節點賦讀入的值后，將其插入第i行鏈表和第j列鏈表的正確位置。算法描述：voidCreattenlink(tlinkL,intm,intn,intt) //L為頭指針，m,n,t分別為行列號和非0元個數{tlinkp,q,H[maxsize];inti,j,k,s;datatypev;if(m>n)s=m;elses=n;//確定頭節點的個數L=(tlink)malloc(sizeof(nodetype));//申請總的頭節點L->i=m;L->j=n;//置行列數H[0]=L;for(i=1;i<=s;i++)//建立頭節點鏈表{p=(tlink)malloc(sizeof(nodetype));p->i=p->j=0;p->down=p->right=p;H[i]=p;H[i-1]->vdata.head=p;}H[s]->vdata.head=L;//構成循環22第22頁，共33頁，2023年，2月20日，星期六建立十字鏈表for(k=1;k<=t;k++)//處理t個非0元{scanf(“%d%d%d”,&i,&j,&v);//讀入一個非0元（i,j,v）p=(tlink)malloc(sizeof(nodetype));//申請節點存放非0元p->i=i;p->j=j;p->vdata.data=v;//賦值q=H[i]； //取第i行鏈表頭節點指針while((q->right!=H[i])&&(q->right->j<j)) q=q->right;//找當前非0元節點在行鏈表中的位置 p->right=q->right;q->right=p;//當前非0元節點插入q節點之后 q=H[j]； //取第j列鏈表頭節點指針 while((q->down!=H[j])&&(q->down->i<i)) q=q->down;//找當前非0元節點在列鏈表中的位置 p->down=q->down;q->down=p;//非0元節點節點插入q節點之后 }}23第23頁，共33頁，2023年，2月20日，星期六5.4廣義表的定義及其操作5.4.1廣義表的定義

廣義表又稱列表(lists),是線型表的推廣。在線型表L=(a0……ai……an-1)中，ai是單元素或原子，即ai本身不再是一個DS，而廣義表記為： LS=(d0d1……di……dn－1) 其中di（0≤i≤n-1）既可以是一個原子，又可以是另一個表（稱為子表），即表中還可以套表。廣義表LS的形式化描述為：

LS=(D,R) 其中：D={di|di∈datatypeordi∈LS(遞歸定義)，i=0,1,.....n-1,n≥0}

R={<di,di+1>|di,di+1∈D,0≤i≤n-2} 式中n為表長（n=0時為空表），若di為原子，則稱di為LS的單元素，否則di稱為LS的子表（滿足遞歸定義)。對非空廣義表定義兩個函數：Gethead(LS)=d0； Gettail(LS)=(d1...dn-1)。 即Gethead(LS)是LS的第一元素d0（當然d0可以為子表），而Gettail(LS)是LS中d1...dn-1的一個子表。對廣義表的其它運算（如查找，插入和刪除等）類似于線性表的運算（見5.4.2）。24第24頁，共33頁，2023年，2月20日，星期六例5-5

廣義表的例子 約定：大寫字母A～Z為表名，小寫字母a～z為單元素。 A=()或A()——空表，表長=0，無表頭，表尾； B=(a,b)或B(a,b)——線性表特例,表長=2,Gethead(B)=a,Gettail(B)=(b)； C=(e,B)或C(e,B)——表長=2，Gethead(C)=e,Gettail(C)=(B)=((a,b)),表C可以表示為：C(e,(a,b))； D=(A,B,C)或D(A,B,C)——表長=3，Gethead(D)=A=(), Gettail(D)=(B,C)=((a,b),(e,(a,b)))； E=(a,E)——表長=2，Gethead(E)=a,Gettail(E)=(E),整個表E為(a,(a,(a,...)))，它為一個特殊的廣義表，稱為遞歸表，或無限表。從例5-5可以看出，廣義表有如下特點：（1）表可以嵌套——表中元素可以是一個表，稱為子表，而子表還可以有子表。如例5-5中表B和表C的結構如圖5.13所示。圖5.13CeBababB25第25頁，共33頁，2023年，2月20日，星期六廣義表的例子（2）表可以共享——表可以是其它表的子表,或表中的元素可取自其他表。如例5-5中表D包含表A、B、C，或A、B、C為D的子表,如圖5.16所示。（3）表可以遞歸——表中元素可以是表本身。如例5-5中表E。

EaDABCabe^圖5.16另外，表中任一單元素可由Gethead(Ls)和Gettail(Ls)函數導出，如取表A=(a,(b,d,e))中單元素d的運算為：

Gethead(Gettail(Gethead(Gettail(A))))

26第26頁，共33頁，2023年，2月20日，星期六5.5廣義表的存儲結構 對于廣義表LS=(d0…di…dn-1)，由于di可以是單元素或子表，故用順序存儲結構表示LS較為困難，一般采用鏈表存儲，稱為廣義鏈表。5.5.1廣義表的鏈式存儲1．單鏈表示法元素di的節點形式：其中：0當di為單元素時；data當atom=0時；atom=data/link=1當di為子表時。link當atom=1時。next意義同線性鏈表，指向di+1所在節點。節點描述：typedefstructnode {intatom; union{datatypedata;structnode*link; }dtype; structnode*next; }Lsnode;atomdata/linknext27第27頁，共33頁，2023年，2月20日，星期六廣義表的存儲 為操作方便，對每一廣義表引入頭節點，其形式同一般的表節點：

例5-5中廣義表A、B、C、D、E的單鏈表如圖5.15所示。1^1^^AA=()圖5.150a0b^1^BB=(a，b)0e1^1^CC=(e，B)11^1^1^DD=(A，B，C)0a1^1^EE=(a，E)28第28頁，共33頁，2023年，2月20日，星期六廣義表的存儲2．雙鏈表示法元素di的節點形式：其中：指向子表的指針當di為子表時；link1=^當di為原子時。表名當di為子表時；data=link2：指向di+1所在的節點。原子值當di為原子時。例5-5中幾個廣義表的雙鏈表結構如圖5.16：

datalink1link2BA^C^DE^a^EB^e^Cb^^a^A=^B29第29頁，共33頁，2023年，2月2