數(shù)據(jù)結(jié)構(gòu)課件習(xí)題五章數(shù)組廣義表

5.1數(shù)組的類型定義5.3矩陣的壓縮存儲(chǔ)5.2數(shù)組的順序存儲(chǔ)5.4廣義表的類型定義5.5廣義表的表示方法第五章數(shù)組和廣義表前幾章介紹的數(shù)據(jù)結(jié)構(gòu)都是線性結(jié)構(gòu)，數(shù)據(jù)元素都屬于原子類型，其值不分解使用。本章討論的多維數(shù)組和廣義表是線性結(jié)構(gòu)的推廣，從整體上看它們是多個(gè)元素組成的線性表，而從局部上看線性表中的數(shù)據(jù)元素不一定是原子類型，即數(shù)據(jù)元素又可以具有某種數(shù)據(jù)結(jié)構(gòu)。ADTArray{

數(shù)據(jù)對(duì)象：

D＝{aj1j2...jn|ji=0,...,bi-1,i=1,2,..,n}

數(shù)據(jù)關(guān)系：

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,i=2,...,n}

}ADTArray基本操作:n維數(shù)組5.1數(shù)組的類型定義數(shù)組是由類型相同的數(shù)據(jù)元素構(gòu)成的有序集合,每個(gè)元素受n（n>=1)個(gè)線性關(guān)系的約束，二維數(shù)組Am*n的定義:數(shù)據(jù)對(duì)象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}數(shù)據(jù)關(guān)系:

R={ROW,COL}

ROW={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}

COL={<ai,j,ai,j+1>|0≤i≤b1-1,0≤j≤b2-2}m-1n-1二維數(shù)組可以看成是由多個(gè)一維數(shù)組組成的。例如，二維數(shù)組Amn既可看成由m個(gè)行向量組成的線性表，也可看成是由n個(gè)列向量組成的線性表。數(shù)組具有以下性質(zhì)：(1)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定。一旦定義了一個(gè)數(shù)組,其數(shù)據(jù)元素?cái)?shù)目不再有增減變化。(2)數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。(3)數(shù)組中的每個(gè)數(shù)據(jù)元素都和一組惟一的下標(biāo)值對(duì)應(yīng)。(4)數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)?？呻S機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。(5)數(shù)組中的每個(gè)數(shù)據(jù)元素都受n個(gè)關(guān)系制約。(6)n個(gè)關(guān)系仍是線性關(guān)系?；静僮鳎篒nitArray(&A,n,bound1,...,boundn)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)

操作結(jié)果：若維數(shù)n和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回OK。Value(A,&e,index1,...,indexn)

初始條件：A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值。

操作結(jié)果：若各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OK。

Assign(&A,e,index1,...,indexn)

初始條件：A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值。

操作結(jié)果：若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。5.2數(shù)組的順序表示和實(shí)現(xiàn)

類型特點(diǎn):1)只有報(bào)告/觀察型操作，沒有結(jié)構(gòu)加工型操作；2)數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一個(gè)一維的結(jié)構(gòu)。

有兩種順序映象的方式:1)以行序?yàn)橹餍?低下標(biāo)優(yōu)先)；2)以列序?yàn)橹餍?高下標(biāo)優(yōu)先)。例如：

稱為基地址或基址。以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象二維數(shù)組A中任一元素ai,j的存儲(chǔ)位置LOC(ai,j)=LOC(a0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系稱為n維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。其中cn=L，ci-1=bi×ci,1<i

n。LOC(j1,j2,...,jn)=LOC(0,0,...,0)+∑ciji

i=1n數(shù)組存儲(chǔ)結(jié)構(gòu)具有隨機(jī)存儲(chǔ)結(jié)構(gòu)特點(diǎn)。假設(shè)m行n列的矩陣含t個(gè)非零元素，則稱為稀疏因子。通常認(rèn)為

0.05的矩陣為稀疏矩陣。5.3矩陣的壓縮存儲(chǔ)何謂稀疏矩陣？二維數(shù)組存儲(chǔ)出現(xiàn)的問(wèn)題？1)盡可能少存或不存零值元素；解決問(wèn)題的原則:2)盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；3)操作方便。即：能盡可能快地找到與下標(biāo)值(i，j)對(duì)應(yīng)的元素，能盡可能快地找到同一行或同一列的非零值元。1)特殊矩陣

非零元在矩陣中的分布有一定規(guī)則例如:三角矩陣對(duì)角矩陣2)隨機(jī)稀疏矩陣非零元在矩陣中隨機(jī)出現(xiàn)有兩類稀疏矩陣：1.下三角矩陣的壓縮存儲(chǔ)用長(zhǎng)度為n(n＋1)/2的一維數(shù)組B，一行接一行存放A中下三角部分的元素。用長(zhǎng)度為n(n＋1)/2的一維數(shù)組B，一列接一列存放A中下三角部分的元素。1)特殊矩陣2.對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣：a[i,j]=a[j,i]以行為主3.三對(duì)角矩陣的壓縮存儲(chǔ)用一個(gè)長(zhǎng)度為3n－2的一維數(shù)組B存放三條對(duì)角線上的元素隨機(jī)稀疏矩陣的壓縮存儲(chǔ)方法:一、三元組順序表二、十字鏈表2)隨機(jī)稀疏矩陣

#defineMAXSIZE12500

typedefstruct{

inti,j;//該非零元的行下標(biāo)和列下標(biāo)

ElemTypee;//該非零元的值

}Triple;//三元組類型一、三元組順序表typedef{

Tripledata[MAXSIZE+1];

//非零元三元組表，data[0]未用

intmu,nu,tu;//矩陣的行數(shù),列數(shù),非零元個(gè)數(shù)}TSMatrix;//稀疏矩陣類型typedefstructOLNode{inti；//*非零元的行下標(biāo)＊/ intj;//*非零元的列下標(biāo)*/ Elemtypee;//*非零元的數(shù)據(jù)元素值*/ structOLNode*right;//*非零元所在行表的后繼鏈域*/ structOLNode*down;//*非零元所在列表的后繼鏈域*/}OLNode;*

OLink;typedefstruct{

OLink*rhead;//*用于存放行表的頭指針*/

OLink*chead;//*用于存放列表的頭指針*/ intmu; //*表示矩陣的行數(shù)的個(gè)數(shù)*/ intnu; //*表示矩陣的列數(shù)*/ inttu; //*表示矩陣中非零元的個(gè)數(shù)*/}CrossList;三、十字鏈表三、十字鏈表30050-100200011314522-1312^^^^^^^5.4廣義表的類型定義ADTGlist{

數(shù)據(jù)對(duì)象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet為某個(gè)數(shù)據(jù)對(duì)象}

數(shù)據(jù)關(guān)系：LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist基本操作:廣義表被廣泛地應(yīng)用于人工智能等領(lǐng)域的表處理語(yǔ)言LISP語(yǔ)言中。廣義表是遞歸定義的多層次的線性結(jié)構(gòu)。

LS=(

1,

2,

,

n)其中：

i或?yàn)樵踊驗(yàn)閺V義表例如:A=（）

B=（a，b）C=（c，B）D=（B，C，d）E=（a，E）共享遞歸共享廣義表LS=(

1,

2,…,

n)的結(jié)構(gòu)特點(diǎn):1)廣義表中的數(shù)據(jù)元素有相對(duì)次序；2)廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；3)廣義表的深度定義為所含括弧的重?cái)?shù)；注意：“原子”的深度為0

“空表”的深度為14)廣義表可以共享；5)廣義表可以是一個(gè)遞歸的表。遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。6)任何一個(gè)非空廣義表LS=(

1,

2,…,

n)均可分解為

表頭Head(LS)=

1和

表尾Tail(LS)=(

2,…,

n)兩部分。例如:

D=(E,F)=((a,(b,c))，F(xiàn))Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()1.廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu)5.5廣義表的存儲(chǔ)結(jié)構(gòu)2.擴(kuò)展線性鏈表存儲(chǔ)結(jié)構(gòu)廣義表A、B、C、D的存儲(chǔ)結(jié)構(gòu)C=（a，C）B=（A，A，D）A=（a，（b，c））D=（）廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu)廣義表的另一種結(jié)點(diǎn)結(jié)構(gòu)Tag=1hptpTag=0atomtp表結(jié)點(diǎn)原子結(jié)點(diǎn)D=（）A=（a，（b，c））B=（A，A，D）C=（a，C）擴(kuò)展線性鏈表存儲(chǔ)結(jié)構(gòu)：1.了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。2.掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。3.了解稀疏