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

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

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

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

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

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

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

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

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

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

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

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

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

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

1、按矩陣M的列序進(jìn)行轉(zhuǎn)置【算法思想】對矩陣M中每一列col（0≤col≤n-1），通過從頭至尾掃描三元組表a.data，找出所有列號等于col的那些三元組，將它們的行號、列號互換后依次放入b.data，即可得到N的按行優(yōu)先的壓縮存儲表示。具體實現(xiàn)如下：第16頁，共27頁，2023年，2月20日，星期五0002800000009100000000-60000003110-150220015A=j==3時j==1時ijv13456782ijv111514221665191632813456782j==2時方法1：按照原矩陣的列號的順序?qū)θM掃描111515910000060222800030000011009100015B=22113233628j==4時4122第17頁，共27頁，2023年，2月20日，星期五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頁，共27頁，2023年，2月20日，星期五2、快速轉(zhuǎn)置【算法思想】建立兩個輔助向量分別記錄矩陣轉(zhuǎn)置后各行非零元素個數(shù)和各行元素在轉(zhuǎn)置三元組表中的開始存放位置；掃描三元組表，根據(jù)某項的列號，確定它轉(zhuǎn)置后的行號，查第二個輔助向量表，按查到的位置直接將該項存入轉(zhuǎn)置三元組表中。第19頁，共27頁，2023年，2月20日，星期五方法2（對號入座）ijv13456782ijv1115142216651916328134567821115關(guān)鍵：確定原矩陣的三元組表中每個三元組在新表中的位置41226161591第20頁，共27頁，2023年，2月20日，星期五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列的第一個非零元在TB中的位置=(A中第i-1列的第一個非零元在TB的位置)+(A中第i-1列的非零元的個數(shù))第21頁，共27頁，2023年，2月20日，星期五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的每一列含非零元素個數(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);}算法實現(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頁，共27頁，2023年，2月20日，星期五5.4廣義表5.4.1廣義表的定義和性質(zhì)

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

廣義表中的元素區(qū)分為區(qū)別原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。若廣義表LS非空（n>=1)，則a1是LS的表頭，其余元素組成的表(a2,…an)稱為LS的表尾。廣義表所含括號的重數(shù)即為廣義表的深度。第23頁，共27頁，2023年，2月20日，星期五5.4廣義表5.4.1廣義表的定義和性質(zhì)一、廣義表的定義1、定義也稱列表（lists），n0個元素的集合。一般記為：LS=(a1,a2,…an)其中：元素允許為單元素或子表。習(xí)慣上：單元素用小寫字母子表用大寫字母2、廣義表的例子如下：（1）A=（）——A是一個空表，其長度為零。（2）B=（