數(shù)據(jù)結(jié)構(gòu)數(shù)組廣義表

數(shù)據(jù)結(jié)構(gòu)數(shù)組廣義表第1頁，共31頁，2023年，2月20日，星期六數(shù)組描述二維數(shù)組可用形式化語言描述，即：

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

關(guān)系集Row和Col表明：除數(shù)組A(2)周邊元素外的其它任一個元素aij，有兩個直接前驅(qū)ai-1j，aij-1,和兩個直接后繼ai+1j，aij+1(周邊元素的前驅(qū)或后繼可不足兩個)。n維數(shù)組也可按上述方法類似定義。二維數(shù)組還可以用如下形式描述:

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]=第2頁，共31頁，2023年，2月20日，星期六2.數(shù)組的基本運算 多維數(shù)組是線性表的推廣，而線性表是多維數(shù)組的特例。 在算法語言中，數(shù)組一旦生成，其元素的存儲空間就固定下來，故數(shù)組的運算一般不包括插入和刪除這樣的操作。對數(shù)組運算有： (1)構(gòu)造一個n維數(shù)組：Setarray(A,n,d1d2,......dn)，即生成：

A[d1][d2].....[dn]（C語言中，1≤n≤8）。 (2)撤消一個數(shù)組：Dearray(A)，釋放數(shù)組A的存儲空間。 (3)取值：Aget(A,i1,...,in,x)，將A[i1][i2],...,[in]的值傳給變量x。 (4)賦值：Assign(A,i1,...,in,x)，將變量x的值傳給A[i1][i2].....[in]。

5.2數(shù)組的存儲映像由于計算機的存儲空間是一維的（或線性的），所以存儲數(shù)組時，要將多維數(shù)組中的元素按某種次序映象到一維存儲空間，即解決“降維”問題。在PASCAL和C等語言中，是按低維下標優(yōu)先變化（或按行優(yōu)先）的方式，存儲數(shù)組中的元素。如在C語言中，二維數(shù)組的映像如圖5.1所示。但在FORTRAN語言中，數(shù)組元素是按高維下標優(yōu)先變化或按列優(yōu)先方式，存儲數(shù)組中的元素。 第3頁，共31頁，2023年，2月20日，星期六數(shù)組的存儲映像

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.三維以上數(shù)組如何映像? 2.“按列優(yōu)先”如何映像?第4頁，共31頁，2023年，2月20日，星期六5.2.1數(shù)組元素的地址計算以C語言為例。設(shè)數(shù)組元素的起始地址為b,每個元素占用L個單元（元素所占單元量由元素的類型而定），元素a的地址用Loc(a)表示。1.一維數(shù)組： 即:Loc(a0)=b; Loc(a1)=b+L;

Loc(ai)=b+i×L;

規(guī)律：任一元素ai的地址:

a0a1

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

a0,

a1,……ai

,……an-1)

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

起址b:b+L:……b+i?L:L圖5.3第5頁，共31頁，2023年，2月20日，星期六數(shù)組元素的地址計算2.二維數(shù)組：a00…a0,n-1…ai0…aij……am-1,n-1映像

（存儲器）起址b:b+L:……b+[i×n]×L:…b+[i?n+j]?L:由圖5.4知：Loc(a00)=b Loc(ai0)=b+(ai0前元素個數(shù))?L=b+(i?n)?L

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

inj圖5.4a00a01

……a0j……

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

……aij….…

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

…am-1j…

am-1n-1A[m][n]=第6頁，共31頁，2023年，2月20日，星期六數(shù)組元素的地址計算3．三維數(shù)組：

由圖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)×L可以看出，i?n?p，i?n?p+j?p，i?n?p+j?p+k分別為ai00，aij0，aijk前的元素個數(shù)。a000ai00aij0aijk第7頁，共31頁，2023年，2月20日，星期六數(shù)組元素的地址計算4．n維數(shù)組從以上的地址公式推導中得出這樣一條規(guī)律：任意維數(shù)組中任一元素的地址=起址b+該元素前的個數(shù)×元素單元量L。故n維數(shù)組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 元素按“列優(yōu)先”方式存儲時，地址計算方法類似，不再贅述。 有了數(shù)組元素的地址計算公式，給出相應參數(shù)后，能夠很快求出任一元素的地址，然后按地址存取相應元素，故對數(shù)組的存取是隨機存?。ɑ虬垂酱嫒。?。5.2.2數(shù)組空間的動態(tài)生成（略）

第8頁，共31頁，2023年，2月20日，星期六5.3矩陣的壓縮存儲信息的壓縮存儲是一項專業(yè)技術(shù)，在當今的多媒體應用中顯得尤為重要。但本節(jié)只是討論矩陣（或二維數(shù)組）中元素的壓縮存儲。在矩陣中，往往會出現(xiàn)許多值相同的元素或０元素，為節(jié)省存儲空間，可以采用某些技術(shù)對這類矩陣進行壓縮存儲。壓縮存儲的原則是：對多個值相同的元素只存儲其中之一，對０元素甚至不分配存儲空間。5.3.1特殊矩陣的壓縮存儲特殊矩陣，指的是值相同的元素或０元素在矩陣中的分布遵循一定規(guī)律的矩陣。1.對稱矩陣：

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

aii…

ann

An×n=

aijaji第9頁，共31頁，2023年，2月20日，星期六特殊矩陣的壓縮

顯然，aij與aji對稱相等，二者只需分配一個存儲單元，即只存儲矩陣中包括主對角線的下三角(或上三角)元素。于是An×n所需的存儲單元數(shù)為n(n+1)/2，而不壓縮存儲需要n2個存儲單元。當n很大時，幾乎能壓縮原存儲空間的一半。具體做法是：設(shè)置一個一維數(shù)組S[n(n+1)/2+1]作為An.n的存儲空間，且按行的次序存放An×n中包括主對角線的下三角元素，如圖5.7所示。a11a21a22…aij…annS[n(n+1)/2+1]:123…..….….k………..n(n+1)/2 圖5.7

a11a22

…aii

annAn×n=

aij其中aij存入S[k]單元，下標（i,j）與k的關(guān)系為：

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時。第10頁，共31頁，2023年，2月20日，星期六特殊矩陣的壓縮２．三角矩陣：（下三角矩陣）(上三角矩陣）顯然，對于下三角矩陣，類似于對稱矩陣的壓縮存儲，即只存儲包括主對角線的下三角元素。而當i<j時，aij取C即可。對于上三角矩陣，壓縮方法如圖5.8所示。a11a22

…aii

annAn×n=

aijCa11a22

aii…

annCaijCa11a12…aij…annS[n(n+1)/2+1]:012…..….….k………..n(n+1)/2K=—+=(i-1)n–(i-1)(i-2)/2+(j-i+1)=(i-1)(2n-i)/2+j(i≤j)

而當(i>j)時，K=0.圖5.8

第11頁，共31頁，2023年，2月20日，星期六特殊矩陣的壓縮3．對角線矩陣（三對角線）：按行順序壓縮于S中，如圖5.9所示。

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

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

ann-1annAn×n=

CC圖5.9

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=第12頁，共31頁，2023年，2月20日，星期六5.3.2稀疏矩陣的壓縮存儲特殊矩陣中同值元素的分布有一定的規(guī)律可循，而有的矩陣，０元素很多（如同一個畫面上有幾個亮點，其余全是空白），但分布無規(guī)律，稱這類矩陣為稀疏矩陣。例5-2設(shè)一個6×7的矩陣如下：則A6×7可以視為一個稀疏矩陣。對于矩陣Am×n，設(shè)非0元素個數(shù)為t，若δ=t/(m×n)≤0.2，則可以將其視為稀疏矩陣。顯然，為節(jié)省存儲空間，須對這類矩陣壓縮存儲空間，原則是只存儲非0元素。一般有“三元組表”和“十字鏈表”的壓縮存儲方法。010200000000003000040005000006000007008000

A6×7

=

第13頁，共31頁，2023年，2月20日，星期六1．三元組表三元組：（i,j,v），其中i,j分別為非0元素的行、列號，v存放非0元的數(shù)值。以行優(yōu)先的順序?qū)⑾∈杈仃囍蟹?元以三元組形式存入一數(shù)組，即所謂的三元組表。三元組表的存儲結(jié)構(gòu)的描述：#definemaxsize64//最大非0元個數(shù)//typedefStruct//三元組類型//{inti,j;datatypev;}tritype;//三元組說明符//typedefStruct{tritypedata[maxsize+1];//三元組表//intmu,nu,tu;//原矩陣的行、列、非0元個數(shù)//}Tsmtype,*Tsmlink;//三元組表說明符//若說明：TsmlinkA;A=(Tsmlink)malloc(sizeof(Tsmtype));則指針變量A指向一個如圖5.10所示的三元組表。對例5-3中A6×7，設(shè)每個元素占16個字節(jié)，若不壓縮存儲，需6×7×16=672（字節(jié)），而壓縮成三元組表存儲時，i,j為整型，故共需：2×16+8×16=160（字節(jié)）。ijv121142313364435526617648A->data[1]……………A->data[tu]

圖5.10第14頁，共31頁，2023年，2月20日，星期六三元組表的轉(zhuǎn)置然而，稀疏矩陣的壓縮存儲會給矩陣運算帶來一些不便，算法要復雜些。這里的運算指求矩陣的轉(zhuǎn)置，兩矩陣相加和相乘等。我們只討論矩陣的轉(zhuǎn)置的算法。未壓縮前，求矩陣A的轉(zhuǎn)置矩陣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=

現(xiàn)在，要通過A的三元組表求其轉(zhuǎn)置矩陣B的三元組表。ijv126143212239328514第15頁，共31頁，2023年，2月20日，星期六三元組表的轉(zhuǎn)置算法思路：1)矩陣A的所有列轉(zhuǎn)化成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]的轉(zhuǎn)置：（1，2，6）=>B->data[1]，又A->data[6].j=1，所以A->data[6]的轉(zhuǎn)置：(1，4，3)=>B->data[2]，完成第一列的轉(zhuǎn)換，依此類推。算法描述：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++)

//掃描A的所有列//for(p=1;p<=A->tn;p++)//掃描所有非0元//

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++;}}}第16頁，共31頁，2023年，2月20日，星期六三元組表的轉(zhuǎn)置

ijv122154216238329413

p

12345602004608000900030000

A4×5=

12345colijv126

q

12345614321223932851406032090080000004000

B5×4=

（矩陣A的三元組表）

圖5.12

（轉(zhuǎn)置后的三元組表）算法的時間復雜度：O(t×n)n=列數(shù),t=非0元個數(shù)。改進算法的復雜度：O(t+n)（略）第17頁，共31頁，2023年，2月20日，星期六2.十字鏈表十字鏈表是以鏈表結(jié)構(gòu)形式存儲一個稀疏矩陣。矩陣中非0元設(shè)置成如下形式的結(jié)點：

其中i、j分別存放非0元的行列號，head/data或作為一非0元的值域（data）或作為頭結(jié)點的鏈指針(head)；down為指向相同列下一個非0元結(jié)點的指針，right為指向相同行下一非0元結(jié)點的指針。結(jié)點類型描述： typedefstructnode {inti,j; union{structnode*head; datatypedata; }vdata; structnode*down,*right; }nodetype,*tlink;ijhead/datadownright第18頁，共31頁，2023年，2月20日，星期六十字鏈表例5-4設(shè)稀疏矩陣：1004020030000005

A4×4=

111144222313445004400000000000000LA的十字鏈表如圖5.13：第19頁，共31頁，2023年，2月20日，星期六十字鏈表算法思路：先構(gòu)造空表，其中S取矩陣行列數(shù)的最大值，即S=max(m,n)。依次讀入每個非0元(i,j,v)，生成一個非0元的結(jié)點，對該結(jié)點賦讀入的值后，將其插入第i行鏈表和第j列鏈表的正確位置。算法描述：voidCreattenlink(tlinkL,intm,n,t)//L為頭指針，m,n,t分別為行列號和非0元個數(shù)//{tlinkp,q,H[maxsize];inti,j,k,s;datatypev;if(m>n)s=m;elses=n;//確定頭結(jié)點的個數(shù)//L=(tlink)malloc(sizeof(nodetype));//申請總的頭結(jié)點//L->i=m;L->j=n;//置行列數(shù)//H[0]=L;for(i=1;i<=s;i++)//建立頭結(jié)點鏈表//{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;//構(gòu)成循環(huán)鏈表//

第20頁，共31頁，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));//申請結(jié)點存放非0元//p->i=i;p->j=j;p->vdata.data=v;//賦值//q=H[i]； //取第i行鏈表頭結(jié)點指針//while((q->right!=H[i])&&(q->right->j<j)) q=q->right;//找當前非0元結(jié)點在行鏈表中的位置// p->right=q->right;q->right=p;//當前非0元結(jié)點插入q結(jié)點之后// q=H[j]； //取第j列鏈表頭結(jié)點指針// while((q->down!=H[j])&&(q->down->i<i)) q=q->down;//找當前非0元結(jié)點在列鏈表中的位置// p->down=q->down;q->down=p;//非0元結(jié)點結(jié)點插入q結(jié)點之后// }}第21頁，共31頁，2023年，2月20日，星期六5.4廣義表的定義 廣義表又稱列表(lists),是線型表的推廣。在線型表L=(a0……ai……an-1)中，ai是單元素或稱原子，即ai本身不再是一個數(shù)據(jù)結(jié)構(gòu)，而廣義表記為：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的子表（滿足遞歸定義)。當廣義表非空時，定義兩個函數(shù)：

head(LS)=d0；tail(LS)=(d1...dn-1)。 即head(LS)是LS的第一元素d0（當然d0可以為子表），而tail(LS)是LS中d1...dn-1的一個子表。對廣義表的其它運算（如查找，插入和刪除等）類似于線性表的運算。第22頁，共31頁，2023年，2月20日，星期六廣義表例5-5廣義表的例子。約定：大寫字母A～Z為表名，小寫字母a～z為單元素。 A=()或A()——空表，表長=0，無表頭，表尾； B=(a,b)或B(a,b)——線性表(廣義表特例),表長=2,head(B)=a,tail(B)=(b)；C=(e,B)或C(e,B)——表長=2，head(C)=e,tail(C)=(B)=((a,b)),表C可以表示為：C(e,(a,b))； D=(A,B,C)或D(A,B,C)——表長=3，head(D)=A=(), tail(D)=(B,C)=((a,b),(e,(a,b)))； E=(a,E)——表長=2，head(E)=a,tail(E)=(E),整個表E為(a,(a,(a,...)))，它為一個特殊的廣義表，稱為遞歸表，或無限表。從例5-5可以看出，廣義表有如下特點：（1）表可以嵌套——表中元素可以是一個表，稱為子表，而子表還可以有子表。如例5-5中表B和表C的結(jié)構(gòu)如圖5.15所示。圖5.15CeBababB第23頁，共31頁，2023年，2月20日，星期六廣義表（2）表可以共享——表可以是其它表的子表，或表中的元素可取自其他的表。如例5-5中表D包含表A、B、C，或A、B、C為D的子表,如圖5.16所示。（3）表可以遞歸——表中元素可以是表本身。如例5-5中表E。

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

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

例5-5中廣義表A、B、C、D、E的單鏈表如圖5.17所示。1^1^^AA=()圖5.170a0b^1^BB=(a，b)0e1^1^CC=(e，B)11^1^1^DD=(A，B，C)0a1^1^EE=(a，E)第26頁，共31頁，2023年，2月20日，星期六廣義表的存儲2．雙鏈表示法元素di的結(jié)點形式：其中：指向子表的指針當di為子表時；link1=^當di為原子時。

表名當di為子表時；data=link2：指向di+1所在的結(jié)點。原子值當di為原子時。例5-5中幾個廣義表的雙鏈表結(jié)構(gòu)如圖5.18：

datalink1link2BA^C^DE^a^EB^e^Cb^^a^A=^B第27頁，共31頁，2023年，2月20日，星期六廣義表的存儲例5-6設(shè)職工工資的表頭H：