數(shù)組和廣義表

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

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

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

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

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

)存儲：數(shù)組元素aij的存儲位置由下式決定：

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

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

)存儲：數(shù)組元素aij的存儲位置由下式決定：

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

第6頁，講稿共30頁，2023年5月2日，星期三5.2數(shù)組的順序存貯結構練習：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é)，行下標從0到4，列下標從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頁，講稿共30頁，2023年5月2日，星期三5.3矩陣的壓縮存儲特殊矩陣:值相同的元素或零元素在矩陣中的分布有一定的規(guī)律。稀疏矩陣:矩陣中只有少量的非零值元，并且這些非零值元在矩陣中的分布沒有一定規(guī)律。壓縮存儲原理：為相等的多個非零元只分配一個存儲空間，零元不分配空間。第8頁，講稿共30頁，2023年5月2日，星期三5.3.1特殊矩陣的壓縮存儲特殊矩陣常見的特殊矩陣有對稱矩陣、下（上）三角矩陣、對角矩陣等等。1.對稱矩陣若一個n階矩陣A中的元素滿足aij=aji（1≤i，j≤n），則稱為n階對稱矩陣。壓縮存儲原理：為每一對對稱元素分配一個存儲空間，則可將原本需要n×n個元素空間壓縮為n(n+1)/2個元素空間中。第9頁，講稿共30頁，2023年5月2日，星期三

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

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

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

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

{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表示的稀疏矩陣轉置為三元組表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廣義表的定義和性質

廣義表是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頁，講稿共30頁，2023年5月2日，星期三5.4廣義表5.4.1廣義表的定義和性質一、廣義表的定義1、定義也稱列表（lists），n0個元素的集合。一般記為：LS=(a1,a2,…an)其中：元素允許為單元素或子表。習慣上：單元素用小寫字母子表用大寫字母2、廣義表的例子如下：（1）A=（）——A是一個空表，其長度為零。（2）B=（e）——表B只有一個原子e，B的長度為1。（3）C=（a,(b,c,d))——表C的長度為2，兩個元素分別為原子a和子表(b,c,d)。第24頁，講稿共30頁，2023年5月2日，星期三5.4廣義表（4）D=（A，B，C）——表D的長度為3，三個元素都是廣義表。顯然，將子表的值代入后，則有D=((),(e),(a,(b,c,d)))。（5）E=（E）——這是一個遞歸的表，它的長度為2，E相當于一個無限的廣義表E=(a,(a,(a,(a,…))))。（6）F=（（））——長度為1的非空表，該表中唯一的一個元素是空表。3、廣義表的三個重要結論：（1）多層次的結構。（2）共享性。（3）遞歸性。第25頁，講稿共30頁，2023年5月2日，星期三5.4廣義表

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

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

頭尾表示法實現(xiàn)廣義表的鏈式存儲結構。第27頁，講稿共30頁，2023年5月2日，星期三5.5數(shù)組應用舉例

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