數(shù)組和廣義表

關(guān)于數(shù)組和廣義表第1頁，講稿共30頁，2023年5月2日，星期三本章學(xué)習(xí)要求1.了解數(shù)組的邏輯結(jié)構(gòu)和基本運(yùn)算；2.熟練掌握數(shù)組的兩種存儲(chǔ)表示方式，并掌握數(shù)組在以行為主存儲(chǔ)的地址計(jì)算方法；3.掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；4.掌握特殊矩陣和稀疏矩陣的定義及其壓縮存儲(chǔ)原理、特點(diǎn)、適用范圍，了解以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算的方法；5．掌握廣義表的結(jié)構(gòu)特點(diǎn)及存儲(chǔ)表示方法。第2頁，講稿共30頁，2023年5月2日，星期三5.1數(shù)組的定義數(shù)組由一組名字相同、下標(biāo)不同的同類型的元素組成，它有兩個(gè)特點(diǎn)：（1）表長(zhǎng)固定（2）數(shù)據(jù)元素類型統(tǒng)一

數(shù)組的分類：（1）一維數(shù)組，即向量；（2）二維數(shù)組；（3）多維數(shù)組。第3頁，講稿共30頁，2023年5月2日，星期三5.1數(shù)組的定義

數(shù)組結(jié)構(gòu)不存在插入、刪除運(yùn)算。常見的操作：

值檢索：給定一組下標(biāo)，查取相應(yīng)的數(shù)組元素的值。

值存儲(chǔ)：給定一組下標(biāo)和值，存入或修改相應(yīng)數(shù)組元素的值。第4頁，講稿共30頁，2023年5月2日，星期三5.2數(shù)組的順序存貯結(jié)構(gòu)理論上，數(shù)組可以用兩種存儲(chǔ)結(jié)構(gòu)，即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。實(shí)際：順序存儲(chǔ)結(jié)構(gòu)更為適宜。m行n列的二維數(shù)組按行優(yōu)先順序(以行為主序

)存儲(chǔ)：數(shù)組元素aij的存儲(chǔ)位置由下式?jīng)Q定：

LOC（A[i,j]）=LOC（A[0,0]）+（i*n+j）*L每個(gè)元素占L個(gè)存貯單元

第5頁，講稿共30頁，2023年5月2日，星期三5.2數(shù)組的順序存貯結(jié)構(gòu)m行n列的二維數(shù)組按列優(yōu)先順序(以列為主序

)存儲(chǔ)：數(shù)組元素aij的存儲(chǔ)位置由下式?jīng)Q定：

LOC（A[i,j]）=LOC（A[0,0]）+（j*m+i）*L每個(gè)元素占L個(gè)存貯單元

第6頁，講稿共30頁，2023年5月2日，星期三5.2數(shù)組的順序存貯結(jié)構(gòu)練習(xí)：1、二維數(shù)組A[20][10]采用行序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，且A[10][5]的存儲(chǔ)地址是1000，則A[18][9]的存儲(chǔ)地址是＿＿＿＿。A．1208B．1212C．1368 D．13362、二維數(shù)組A中，每個(gè)數(shù)據(jù)元素占4個(gè)字節(jié)，行下標(biāo)從0到4，列下標(biāo)從0到5，按行優(yōu)先存儲(chǔ)時(shí)元素A[3][5]的地址域同按列優(yōu)先存儲(chǔ)時(shí)元素＿＿＿＿的地址相同。A．A[2][4]B．A[3][4]C．A[3][5]D．A[4][4]第7頁，講稿共30頁，2023年5月2日，星期三5.3矩陣的壓縮存儲(chǔ)特殊矩陣:值相同的元素或零元素在矩陣中的分布有一定的規(guī)律。稀疏矩陣:矩陣中只有少量的非零值元，并且這些非零值元在矩陣中的分布沒有一定規(guī)律。壓縮存儲(chǔ)原理：為相等的多個(gè)非零元只分配一個(gè)存儲(chǔ)空間，零元不分配空間。第8頁，講稿共30頁，2023年5月2日，星期三5.3.1特殊矩陣的壓縮存儲(chǔ)特殊矩陣常見的特殊矩陣有對(duì)稱矩陣、下（上）三角矩陣、對(duì)角矩陣等等。1.對(duì)稱矩陣若一個(gè)n階矩陣A中的元素滿足aij=aji（1≤i，j≤n），則稱為n階對(duì)稱矩陣。壓縮存儲(chǔ)原理：為每一對(duì)對(duì)稱元素分配一個(gè)存儲(chǔ)空間，則可將原本需要n×n個(gè)元素空間壓縮為n(n+1)/2個(gè)元素空間中。第9頁，講稿共30頁，2023年5月2日，星期三

假設(shè)以一維數(shù)組s[1：n(n+1)/2]作為n階對(duì)稱矩陣A的存儲(chǔ)結(jié)構(gòu)，則s[k]和矩陣元素aij之間存在一一對(duì)應(yīng)關(guān)系，矩陣下標(biāo)(i,j)與k的關(guān)系如下：第10頁，講稿共30頁，2023年5月2日，星期三2.三角矩陣下（上）三角矩陣的特點(diǎn)是以主對(duì)角線為界的上（下）半部分所有元素的值都相同，而下（上）半部分的元素值則沒有任何規(guī)律。將上半部分的常量值存儲(chǔ)在0單元，下半部分和主對(duì)角上的元素從1號(hào)單元開始存放對(duì)于任意的（i,j），在一維數(shù)組中的存放位置可利用下列公式求得：第11頁，講稿共30頁，2023年5月2日，星期三3.對(duì)角矩陣若n階方陣中的非零值元都集中在以主對(duì)角線為中心的(由k條對(duì)角線組成的)帶狀區(qū)域中，則稱為k階對(duì)角矩陣。非零元素以行為主序，從下標(biāo)為1的位置開始依次存放在一維數(shù)組中，而位置1存放數(shù)值0

對(duì)于任意的（i,j），可按以下公式求得矩陣元素在一維數(shù)組中的存儲(chǔ)位置k：第12頁，講稿共30頁，2023年5月2日，星期三假設(shè)在m×n的矩陣中，有t個(gè)元素不為零。令δ=t/m×n,稱δ為矩陣的稀疏因子。通常認(rèn)為δ≤0.05的矩陣為稀疏矩陣。三元組順序表將三元組按行優(yōu)先順序排列，同一行中按列號(hào)從小到大的順序排列，組成一個(gè)線性表，稱為三元組表，再采用順序存儲(chǔ)方法存儲(chǔ)該表，稱為三元組順序表。5.3.2稀疏矩陣第13頁，講稿共30頁，2023年5月2日，星期三三元組順序表的結(jié)構(gòu)定義如下：DefineSMAX1024typedefstruct{inti,j;/*非零元素的行下標(biāo)、列下標(biāo)*/datatypev;/*非零元素值*/}triple;/*三元組類型*/typedefstruct{intmu,nu,tu;/*矩陣的行數(shù)、列數(shù)及非零元素的個(gè)數(shù)*/tripledata[SMAX];//三元組表}TSMatrix;/*三元組表的存儲(chǔ)類型*/第14頁，講稿共30頁，2023年5月2日，星期三矩陣轉(zhuǎn)置運(yùn)算的實(shí)現(xiàn)：對(duì)于一個(gè)m×n的矩陣M，它的轉(zhuǎn)置矩陣N是一個(gè)n×m的矩陣，且N（i,j）=M（j,i），0≤i≤n，0≤j≤m。

假設(shè)a和b都是TSMatrix型變量，分別表示矩陣M、N。從a得到b轉(zhuǎn)置的實(shí)現(xiàn)步驟：①將矩陣的行列值互換；②將每個(gè)三元組中的i和j相互調(diào)換；③重排三元組之間的次序。第15頁，講稿共30頁，2023年5月2日，星期三

1、按矩陣M的列序進(jìn)行轉(zhuǎn)置【算法思想】對(duì)矩陣M中每一列col（0≤col≤n-1），通過從頭至尾掃描三元組表a.data，找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)、列號(hào)互換后依次放入b.data，即可得到N的按行優(yōu)先的壓縮存儲(chǔ)表示。具體實(shí)現(xiàn)如下：第16頁，講稿共30頁，2023年5月2日，星期三0002800000009100000000-60000003110-150220015A=j==3時(shí)j==1時(shí)ijv13456782ijv111514221665191632813456782j==2時(shí)方法1：按照原矩陣的列號(hào)的順序?qū)θM掃描111515910000060222800030000011009100015B=22113233628j==4時(shí)4122第17頁，講稿共30頁，2023年5月2日，星期三Statustransmatrix(TSMatrixa,TSMatrix&b){intp,q,col;b.mu=a.nu;b.nu=a.mu;b.tu=a.tuif(b.tu){q=0;for(col=0;col<a.nu;col++)for(p=0;p<a.tu;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++;}}return(ok);}第18頁，講稿共30頁，2023年5月2日，星期三2、快速轉(zhuǎn)置【算法思想】建立兩個(gè)輔助向量分別記錄矩陣轉(zhuǎn)置后各行非零元素個(gè)數(shù)和各行元素在轉(zhuǎn)置三元組表中的開始存放位置；掃描三元組表，根據(jù)某項(xiàng)的列號(hào)，確定它轉(zhuǎn)置后的行號(hào)，查第二個(gè)輔助向量表，按查到的位置直接將該項(xiàng)存入轉(zhuǎn)置三元組表中。第19頁，講稿共30頁，2023年5月2日，星期三方法2（對(duì)號(hào)入座）ijv13456782ijv1115142216651916328134567821115關(guān)鍵：確定原矩陣的三元組表中每個(gè)三元組在新表中的位置41226161591第20頁，講稿共30頁，2023年5月2日，星期三512346？15loc(1,1)0002800000009100000000-60000003110-150220015A=0000060222800030000011009100015B=11loc(2,1)=loc(1,1)+2loc(3,1)=loc(2,1)+13loc(4,1)=loc(3,1)+2

22尋址公式：A中第i列的第一個(gè)非零元在TB中的位置=(A中第i-1列的第一個(gè)非零元在TB的位置)+(A中第i-1列的非零元的個(gè)數(shù))第21頁，講稿共30頁，2023年5月2日，星期三if(b.tu){for(col=0;col<a.nu;++col)num[col]=0;/*初始化*/for(k=0;k<a.tu;++k)++num[a.data[k].j];/*求M的每一列含非零元素個(gè)數(shù)*/cpot[0]=0;for(col=1;col<a.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=0;p<a.tu;++p)//轉(zhuǎn)置

{col=a.data[p].j;q=cpot[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;++cpot[col];}}return(ok);}算法實(shí)現(xiàn)如下：Statusfast_transpos(TSMatrixa,TSMatrix&b)/*將三元組表a表示的稀疏矩陣轉(zhuǎn)置為三元組表b表示的稀疏矩陣*/{intp,q,col,k;intnum[0..a.nu],cpot[0..a.nu];b.mu=a.nu;

b.nu=a.mu;

b.tu=a.tu;第22頁，講稿共30頁，2023年5月2日，星期三5.4廣義表5.4.1廣義表的定義和性質(zhì)

廣義表是n(n>=0)個(gè)元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項(xiàng)，或者是一個(gè)廣義表。通常記作LS=（a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長(zhǎng)度。若ai是廣義表，則稱它為L(zhǎng)S的子表。

廣義表中的元素區(qū)分為區(qū)別原子和廣義表，書寫時(shí)用大寫字母表示廣義表，用小寫字母表示原子。若廣義表LS非空（n>=1)，則a1是LS的表頭，其余元素組成的表(a2,…an)稱為L(zhǎng)S的表尾。廣義表所含括號(hào)的重?cái)?shù)即為廣義表的深度。第23頁，講稿共30頁，2023年5月2日，星期三5.4廣義表5.4.1廣義表的定義和性質(zhì)一、廣義表的定義1、定義也稱列表（lists），n0個(gè)元素的集合。一般記為：LS=(a1,a2,…an)其中：元素允許為單元素或子表。習(xí)慣上：?jiǎn)卧赜眯懽帜缸颖碛么髮懽帜?、廣義表的例子如下：（1）A=（）——A是一個(gè)空表，其長(zhǎng)度為零。（2）B=（e）——表B只有一個(gè)原子e，B的長(zhǎng)度為1。（3）C=（a,(b,c,d))——表C的長(zhǎng)度為2，兩個(gè)元素分別為原子a和子表(b,c,d)。第24頁，講稿共30頁，2023年5月2日，星期三5.4廣義表（4）D=（A，B，C）——表D的長(zhǎng)度為3，三個(gè)元素都是廣義表。顯然，將子表的值代入后，則有D=((),(e),(a,(b,c,d)))。（5）E=（E）——這是一個(gè)遞歸的表，它的長(zhǎng)度為2，E相當(dāng)于一個(gè)無限的廣義表E=(a,(a,(a,(a,…))))。（6）F=（（））——長(zhǎng)度為1的非空表，該表中唯一的一個(gè)元素是空表。3、廣義表的三個(gè)重要結(jié)論：（1）多層次的結(jié)構(gòu)。（2）共享性。（3）遞歸性。第25頁，講稿共30頁，2023年5月2日，星期三5.4廣義表

二、廣義表有兩個(gè)特殊的基本運(yùn)算：取表頭head(LS)：取表中的第一個(gè)數(shù)據(jù)元素，不能對(duì)空表操作。取表尾tail(LS)；取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對(duì)空表操作。第26頁，講稿共30頁，2023年5月2日，星期三5.4廣義表5.4.2廣義表的存儲(chǔ)結(jié)構(gòu)

由于廣義表中有兩種數(shù)據(jù)元素，原子或廣義表，因此，需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：一種是表結(jié)點(diǎn)，一種是原子結(jié)點(diǎn)。對(duì)于廣義表：F=（e,C,（）），其中C=（a,（b,c,（d））），采用頭尾表示法的存儲(chǔ)結(jié)構(gòu)如圖

頭尾表示法實(shí)現(xiàn)廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第27頁，講稿共30頁，2023年5月2日，星期三5.5數(shù)組應(yīng)用舉例

例5-1已知一個(gè)函數(shù)聲明為“intFINDMAX(inta[][],intm,intn);”，編寫出此函數(shù)定義，求出并返回矩陣An×m