數(shù)據(jù)結(jié)構(gòu)答案-第6章-多維數(shù)組和廣義表學(xué)習(xí)指導(dǎo)

數(shù)據(jù)結(jié)構(gòu)答案-第6章-多維數(shù)組和廣義表學(xué)習(xí)指導(dǎo)數(shù)據(jù)結(jié)構(gòu)答案-第6章-多維數(shù)組和廣義表學(xué)習(xí)指導(dǎo)數(shù)據(jù)結(jié)構(gòu)答案-第6章-多維數(shù)組和廣義表學(xué)習(xí)指導(dǎo)數(shù)據(jù)結(jié)構(gòu)答案-第6章-多維數(shù)組和廣義表學(xué)習(xí)指導(dǎo)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:第6章多維數(shù)組和廣義表知識(shí)點(diǎn)分析1．多維數(shù)組概念多維數(shù)組是向量的推廣，對于二維數(shù)組Am×n既可以看成m行向量組成的向量，也可以看成n行向量組成的向量。多維數(shù)組在計(jì)算機(jī)中有兩種存儲(chǔ)形式：按行優(yōu)先順序存儲(chǔ)和按列優(yōu)先順序存儲(chǔ)。2．多維數(shù)組的存儲(chǔ)二維數(shù)組aij的地址為：LOC(aij)=LOC(a00)+(i×n+j)×d（0下標(biāo)起始的語言）三維數(shù)組aijk的地址為：LOC(aijk)=LOC(a000)+((i×n×p+j×p+k)×d（0下標(biāo)起始的語言）d為每個(gè)數(shù)據(jù)元素占有的字節(jié)數(shù)。3．特殊矩陣在矩陣中非零元素或零元素的分布有一定規(guī)律的矩陣稱為特殊矩陣，如三角矩陣、對稱矩陣、稀疏矩陣等。當(dāng)矩陣的階數(shù)很大時(shí)，用普通的二維數(shù)組存儲(chǔ)這些特殊矩陣將會(huì)占用很多的存儲(chǔ)單元。從節(jié)約存儲(chǔ)空間的角度考慮，以下特殊矩陣的存儲(chǔ)方法。（1）對稱矩陣對稱矩陣是一種特殊矩陣，n階方陣的元素滿足性質(zhì)：aij=aji（0≤i,j≤n-1）。對稱矩陣是關(guān)于主對角線的對稱，因此只需存儲(chǔ)上三角或下三角部分的數(shù)據(jù)即可。（2）三角矩陣三角矩陣的特殊性是以主對角線劃分矩陣。下三角矩陣，主對角線以上均為同一個(gè)常數(shù)；上三角矩陣，主對角線以下均為同一個(gè)常數(shù)，可以采用壓縮存儲(chǔ)。（3）稀疏矩陣在m*n的矩陣中有t個(gè)非零元素，且t遠(yuǎn)小于m×n，這樣的矩陣稱稀疏矩陣。為了節(jié)約存儲(chǔ)空間，稀疏矩陣中零元素?zé)o需存儲(chǔ)，只需存儲(chǔ)矩陣中的非零元素。稀疏矩陣常用的有：三元組表存儲(chǔ)、帶行指針的鏈表存儲(chǔ)、十字鏈表存儲(chǔ)等存儲(chǔ)方法。4．廣義表廣義表是n（n≥0）個(gè)數(shù)據(jù)元素的有序序列，廣義表的元素可以是單元素，也可以是一個(gè)廣義表。由于廣義表的元素有兩種形式，所以其結(jié)點(diǎn)的存儲(chǔ)形式也有兩種：（1）表結(jié)點(diǎn)由標(biāo)志域、表頭指針域、表尾指針域組成。（2）原子結(jié)點(diǎn)由標(biāo)志域和值域組成。5．廣義表與線性表的區(qū)別和聯(lián)系線性表是具有相同類型的n個(gè)數(shù)據(jù)元素的有限序列，記為a1、a2、a3、……、an。廣義表也是n個(gè)數(shù)據(jù)元素的有限序列，記為a1、a2、a3、……、an。線性表中的元素必須具有相同的類型，而廣義表中的成員，既可以是單個(gè)元素（原子），也可以是一個(gè)廣義表（子表）。當(dāng)廣義表中的每一個(gè)ai元素都是數(shù)據(jù)元素，且具有相同類型時(shí)，則它就是一個(gè)線性表，因此可以說廣義表是線性表的一種推廣，或者說線性表是廣義表的一個(gè)特例。典型習(xí)題分析【例1】設(shè)二維數(shù)組A5×6的每個(gè)元素占4個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址。已知A的起始地址為2000，計(jì)算：（1）數(shù)組的大?。?）A的終端結(jié)點(diǎn)a45的存儲(chǔ)地址（3）按行優(yōu)先順序存儲(chǔ)時(shí)，a25的存儲(chǔ)地址（4）按列優(yōu)先順序存儲(chǔ)時(shí)，a25的存儲(chǔ)地址答：（1）數(shù)組的大?。磾?shù)組A共占多少字節(jié)）：5×6×4=120B。（2）一個(gè)結(jié)點(diǎn)aij的存儲(chǔ)地址是該結(jié)點(diǎn)所占用的存儲(chǔ)空間的第1個(gè)字節(jié)的地址（即起始地址），它等于：基地址+排在aij之前的結(jié)點(diǎn)個(gè)數(shù)×每個(gè)結(jié)點(diǎn)所占用的字節(jié)數(shù)。a45的起始地址：LOC(a45)=2000+(4×6+5)×4=2116（3）在按行優(yōu)先順序存儲(chǔ)時(shí)，排在aij之前的結(jié)點(diǎn)的個(gè)數(shù)為：在前i行（即0~i-1行）上共有i×n個(gè)結(jié)點(diǎn)，在第i行上aij之前有j個(gè)結(jié)點(diǎn)（0~j-1列）。所以按行優(yōu)先存儲(chǔ)的地址計(jì)算公式為：LOC(aij)=LOC(a00)+(i×n+j)×dLOC(a25)=2000+(2×6+5)×4=2068（4）在按列優(yōu)先順序存儲(chǔ)時(shí)，排在aij之前的結(jié)點(diǎn)的個(gè)數(shù)為：在前j列（即0~j-1列）上共有j×m個(gè)結(jié)點(diǎn)，在第j列上aij之前有i個(gè)結(jié)點(diǎn)（0~i-1行）。所以按列優(yōu)先存儲(chǔ)的地址計(jì)算公式為：LOC(aij)=LOC(a00)+(j×m+i)×dLOC(a25)=2000+(5×5+2)×4=2108【例2】特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后會(huì)失去隨機(jī)存儲(chǔ)功能為什么答：對于像三角矩陣等特殊矩陣由于壓縮存儲(chǔ)時(shí)將其存儲(chǔ)在一個(gè)線性數(shù)組向量中，矩陣元素aij的下標(biāo)i，j與它在向量中的對應(yīng)元素bk下標(biāo)k有一對應(yīng)關(guān)系，故不會(huì)失去隨機(jī)存儲(chǔ)功能。而像稀疏矩陣，其壓縮存儲(chǔ)的方式是將其非零元素存儲(chǔ)在一個(gè)三元組中，以三元組數(shù)組a[k]形式存儲(chǔ)，矩陣元素aij下標(biāo)i，j與數(shù)組中對應(yīng)元素a[k]行下標(biāo)k無對應(yīng)關(guān)系，故失去隨機(jī)存儲(chǔ)功能?！纠?】求矩陣的轉(zhuǎn)置矩陣分析：對于一個(gè)m×n的矩陣Amn，其轉(zhuǎn)置矩陣是一個(gè)n×m的矩陣Bnm，且B[i][j]=A[j][i]，0≤in，0≤im。其函數(shù)如下：voidtrs(A,B)maxixA,B;{inti,j;for(i=0;i<m;i++)for(j=0;j<n;j++)B[j][i]=A[i][j];}【例4】求兩個(gè)矩陣的乘分析：設(shè)兩個(gè)矩陣相乘：C=A×B，其中A是一個(gè)m×n的矩陣，B是一個(gè)n×k的矩陣，則C為一個(gè)m×k的矩陣。其函數(shù)如下：voidmut(C,A,B)maxixA,B,C;{inti,j,k;for(i=0;i<m;i++)for(j=0;j<k;j++){C[i][j]=0;for(k=0;k<n;k++)C[i][j]=C[i][j]+A[i][k]*B[k][j];}}【例5】若矩陣Am×n中存在一個(gè)元素aij，滿足aij是第i行最小的元素，且是第j列最大的元素，則稱aij是矩陣A的鞍點(diǎn)，請編寫一個(gè)算法，找出矩陣A的所有鞍點(diǎn)。分析：找矩陣A的所有鞍點(diǎn)的基本思想是：先逐行找出本行值最小的元素，確定其所在的列，并在此列中選值最大的元素，若兩者值相等，即選中一個(gè)鞍點(diǎn)。voidSpoint(int*a,intm,intn){inti,j,k,c,max,min,r=0;for(i=0;i<m;i++){min=a[i][0];abdabdfegACLB圖6-2廣義表圖形表結(jié)點(diǎn)為：tag=1hptp元素結(jié)點(diǎn)為：tag=0data五．編程題答案（1）【程序代碼】#include""#defineERROR–99999typedefstruct{introw;intcol;intdata;}Triple;intMDSum(Triple*a){inti;intsum=0;if(a[0].row!=a[0].col)returnERROR;for(i=1;i<=a[0].data;i++){if(a[i].row==a[i].col)sum+=a[i].data;}returnsum;}（2）分析：設(shè)j為原子個(gè)數(shù)，則求廣義表中原子元素個(gè)數(shù)的算法可遞歸定義如下：j=0 LS為空j=表尾原子元素個(gè)數(shù)+1 LS非空且表頭為原子元素表頭子表原子元素個(gè)數(shù)+表尾原子元素個(gè)數(shù)+1 LS非空且表頭子表【程序代碼】intatomnum(Gnode*head){if(head==NULL)return0;if(head->tag==0)return(atomnum(head->next)+1);elsereturn(atomnum(head->next)+atomnum(head->);}（3）【程序代碼】intmaxele(Gnode*head){intm=0,a;while(head){if(he