數(shù)據(jù)結構 數(shù)組和廣義表

數(shù)據(jù)結構數(shù)組和廣義表1第一頁，共五十三頁，編輯于2023年，星期三5.1數(shù)組的定義

數(shù)組：由一組名字相同、下標不同的變量構成注意：本章所討論的數(shù)組與高級語言中的數(shù)組有所區(qū)別：高級語言中的數(shù)組是順序結構；而本章的數(shù)組既可以是順序的，也可以是鏈式結構，用戶可根據(jù)需要選擇。答：對的。因為：①數(shù)組中各元素具有統(tǒng)一的類型；②數(shù)組元素的下標一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡單，除了結構的初始化和銷毀之外，只有存取元素和修改元素值的操作。討論：“數(shù)組的處理比其它復雜的結構要簡單”，對嗎？2第二頁，共五十三頁，編輯于2023年，星期三二維數(shù)組的特點：一維數(shù)組的特點：1個下標，ai是ai+1的直接前驅(qū)2個下標，每個元素ai,j受到兩個關系（行關系和列關系）的約束：一個m×n的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。N維數(shù)組的特點：n個下標，每個元素受到n個關系約束一個n維數(shù)組可以看成是由若干個n－1維數(shù)組組成的線性表。a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=3第三頁，共五十三頁，編輯于2023年，星期三N維數(shù)組的數(shù)據(jù)類型定義n_ARRAY=(D,R)其中：Ri={<aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

>|

aj1,j2,…ji…jn,aj1,j2,…ji+1…jn

D}數(shù)據(jù)關系：R={R1,R2，….Rn}數(shù)據(jù)對象：D={aj1,j2…jn|ji為數(shù)組元素的第i維下標，aj1,j2…jn

Elemset}數(shù)組的抽象數(shù)據(jù)類型定義略，參見教材P90構造數(shù)組、銷毀數(shù)組、讀數(shù)組元素、寫數(shù)組元素基本操作：4第四頁，共五十三頁，編輯于2023年，星期三5.2數(shù)組的順序存儲表示和實現(xiàn)問題：計算機的存儲結構是一維的，而數(shù)組一般是多維的，怎樣存放？解決辦法：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存入存儲器中。例如：在二維數(shù)組中，我們既可以規(guī)定按行存儲，也可以規(guī)定按列存儲。注意：若規(guī)定好了次序，則數(shù)組中任意一個元素的存放地址便有規(guī)律可尋，可形成地址計算公式；約定的次序不同，則計算元素地址的公式也有所不同；C和PASCAL中一般采用行優(yōu)先順序；FORTRAN采用列優(yōu)先。5第五頁，共五十三頁，編輯于2023年，星期三補充：計算二維數(shù)組元素地址的通式

設一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時求出任一元素的地址（這樣數(shù)組中的任一元素便可以隨機存?。。憾S數(shù)組列優(yōu)先存儲的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=單個元素長度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長度aij本行前面的元素個數(shù)①開始結點的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲時的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L6第六頁，共五十三頁，編輯于2023年，星期三例2：已知二維數(shù)組Am,m按行存儲的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存儲的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（盡管是方陣，但公式仍不同）例1〖軟考題〗：一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是

個字節(jié)。288例3：〖00年計算機系考研題〗設數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：請注意審題！利用列優(yōu)先通式：答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2887第七頁，共五十三頁，編輯于2023年，星期三Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是N維數(shù)組，其中任一元素的地址該如何計算？其中Cn=L,Ci-1=bi×Ci，1<i≤n一個元素長度數(shù)組基址前面若干元素占用的地址字節(jié)總數(shù)第i維長度與所存元素個數(shù)有關的系數(shù)，可用遞推法求出教材已給出低維優(yōu)先的地址計算公式，見P93（5-2）式該式稱為n維數(shù)組的映像函數(shù)：8第八頁，共五十三頁，編輯于2023年，星期三#defineMAX_ARRAY_DIM8//假設最大維數(shù)為8typedefstruct{ELemType*base;//數(shù)組元素基址intdim;//數(shù)組維數(shù)int*bound;//數(shù)組各維長度信息保存區(qū)基址int*constants;//數(shù)組映像函數(shù)常量的基址}Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說明（有5個）（請閱讀教材P93-95）N維數(shù)組的順序存儲表示（見教材P93）9第九頁，共五十三頁，編輯于2023年，星期三StatusInitArray(Array&A,intdim,…){//若維數(shù)dim和各維長度合法，則構造相應的數(shù)組A并返回OKif(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!a.bounds)exit(OVERFLOW);

//若各維長度合法，則存入A.bounds,并求出A的元素總數(shù)elemtotalelemtotal=1;va_start(ap.dim);//ap為va_list類型，是存放變長參數(shù)表信息的類型數(shù)組的基本操作函數(shù)說明（5個）（見教材P93-95）10第十頁，共五十三頁，編輯于2023年，星期三for(i=0;i<dim;++i){A.bounds[i]=va_arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;

elemtotal*=A.bounds[i];}va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);A.constants=(int*)malloc(dim*sizeof(int));if(!A.constans)exit(OVERFLOW);A.constans[dim-1]=1;for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}11第十一頁，共五十三頁，編輯于2023年，星期三數(shù)組基址指針各維長度保存區(qū)指針映像函數(shù)Ci保存區(qū)指針StatusDestroyArray(Array&A){//銷毀數(shù)組Aif(!A.base)returnERROR;

free(A.base);A.base=NULL;if(!A.bounds)returnERROR;

free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;

free(A.constants);A.constants=NULL;returnOK;}12第十二頁，共五十三頁，編輯于2023年，星期三StatusLocate(ArrayA,va_listap,int&off){

//若ap指示的各下標值合法，則求出該元素在A中，相對地址offoff=0;for(i=0;i<A.dim;++i){ind=va_arg(ap,int);if(ind<0||ind>A.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}13第十三頁，共五十三頁，編輯于2023年，星期三StatusValue(ArrayA,ElemType&e,…){

//A是n維數(shù)組，e為元素變量，隨后是n個下標值，若各下標不超界，則e賦值為所指定的A的元素值，即將指定元素值讀到e變量中。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;e=*(A.base+off);returnOK;}14第十四頁，共五十三頁，編輯于2023年，星期三StatusAssign(Array&A,ElemTypee,…){

//A是n維數(shù)組，e為元素變量，隨后是n個下標值，若各下標不超界，則e的值賦為所指定的A的元素值，即：將e值寫入指定數(shù)組單元。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}15第十五頁，共五十三頁，編輯于2023年，星期三順序存儲方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。^……行指針向量a11a12…^a1nam1am2…^amn補充：

鏈式存儲方式：用帶行指針向量的單鏈表來表示。注：數(shù)組的運算參見下一節(jié)實例（稀疏矩陣的轉(zhuǎn)置）（難點是多維數(shù)組與一維數(shù)組的地址映射關系）16第十六頁，共五十三頁，編輯于2023年，星期三5.3矩陣的壓縮存儲討論：1.什么是壓縮存儲？若多個數(shù)據(jù)元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。2.所有二維數(shù)組（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。3.什么樣的矩陣具備以上壓縮條件？

一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。4.什么叫稀疏矩陣？矩陣中非零元素的個數(shù)較少（一般小于5%）重點介紹稀疏矩陣的壓縮和相應的操作。17第十七頁，共五十三頁，編輯于2023年，星期三例：對稱矩陣的壓縮存儲設有一個nn的對稱矩陣A。在矩陣中，aij

=aji18第十八頁，共五十三頁，編輯于2023年，星期三為節(jié)約存儲，只存對角線及對角線以上的元素，或者只存對角線及對角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。下三角矩陣19第十九頁，共五十三頁，編輯于2023年，星期三上三角矩陣把它們按行存放于一個一維數(shù)組B中，稱之為對稱矩陣A的壓縮存儲方式。數(shù)組B共有n+(n-1)++1=

n*(n+1)/2個元素。20第二十頁，共五十三頁，編輯于2023年，星期三下三角矩陣Ba11a21a22a31a32a33a41a42a43……

ann

012345678n(n+1)/2-1若

i

j,數(shù)組元素A[i][j]在數(shù)組B中的存放位置為1+2++(i-1)+(j-1)=(i-1)*i/2+j-1前i行元素總數(shù)第i行第j個元素前元素個數(shù)21第二十一頁，共五十三頁，編輯于2023年，星期三若i<j，數(shù)組元素A[i][j]在矩陣的上三角部分,在數(shù)組B中沒有存放，可以找它的對稱元素A[j][i]

一維數(shù)組B中的數(shù)據(jù)元素和方陣A中的元素之間存在著下列一一對應的關系

22第二十二頁，共五十三頁，編輯于2023年，星期三上三角矩陣Ba11a12a13a14a22a23a24a33a34

a44

0123456789若i

j，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為 n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素總數(shù)第i行第j個元素前元素個數(shù)n=423第二十三頁，共五十三頁，編輯于2023年，星期三

若i

j，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為

n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==(2*n-i-1)*i/2+j若i>j，數(shù)組元素A[i][j]在矩陣的下三角部分，在數(shù)組B中沒有存放。因此，找它的對稱元素A[j][i]。A[j][i]在數(shù)組B的第(2*n-j-1)*j/2+i的位置中找到。24第二十四頁，共五十三頁，編輯于2023年，星期三5.3.2稀疏矩陣問題：如果只存儲稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？解決思路：對每個非零元素增開若干存儲單元，例如存放其所在的行號和列號，便可準確反映該元素所在位置。實現(xiàn)方法：將每個非零元素用一個三元組（i，j，aij）來表示，則每個稀疏矩陣可用一個三元組表來表示。問題：稀疏矩陣的存儲和操作？25第二十五頁，共五十三頁，編輯于2023年，星期三例1：三元素組表中的每個結點對應于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的

、

和

。行下標列下標元素值例2：寫出右圖所示稀疏矩陣的壓縮存儲形式。0

1290000

00000-30001400

0240000

18000015

00-700((1,2,12)

，(1,3,9)，(3,1,-3)，(3,5,14)，(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7))法1：用線性表表示：0

1290000

00000-30001400

024

0000

18000015

00-700(6,6)26第二十六頁，共五十三頁，編輯于2023年，星期三法2：用三元組順序表表示：P.980

1290000

00000-30001400

024

0000

18000015

00-700121213931-3351443245218611564-7注意：為更可靠描述，通常再加一行“總體”信息：即總行數(shù)、總列數(shù)、非零元素總個數(shù)668ijvalue稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能:-(01234567827第二十七頁，共五十三頁，編輯于2023年，星期三#defineMAXSIZE125000//設非零元素最大個數(shù)125000typedefstruct{inti;//元素行號intj;//元素列號ElemTypee;//元素值}Triple;typedefstruct{

Tripledata[MAXSIZE+1];//三元組表，以行為主序存入一維向量data[]中intmu;//矩陣總行數(shù)intnu;//矩陣總列數(shù)inttu;//矩陣中非零元素總個數(shù)}TsMatrix;三元組表的順序存儲表示（見教材P98）：//一個結點的結構定義//整個三元組表的定義28第二十八頁，共五十三頁，編輯于2023年，星期三法三：用帶輔助向量的三元組表示。方法：增加1個輔助向量：記錄稀疏矩陣中每行第一個非0元素在三元組中的行號，用POS（i）表示。76531211202NUM(i)6543POS(

i)21i0

1290000

00000-30001400

024

0000

18000015

00-700-7461516182524341453-3139311221866vji0123456783用途：通過三元組高效訪問稀疏矩陣中任一非零元素。規(guī)律：POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)注：書上稱為行邏輯鏈接的三元組順序表。教材P10029第二十九頁，共五十三頁，編輯于2023年，星期三行邏輯鏈接的三元組順序表的結構定義typedefstruct{Tripledata[MAXSIZE+1];/*非零元三元組表,data[0]未用*/intrpos[MAXRC+1];/*各行第一個非零元素的位置表*/intmu,nu,tu;/*矩陣的行數(shù)、列數(shù)和非零元個數(shù)*/}RLSMatrix;30第三十頁，共五十三頁，編輯于2023年，星期三法四：用十字鏈表表示教材P100用途：方便稀疏矩陣的加減運算；方法：每個非0元素占用5個域。rightdownvji同一列中下一非零元素的指針同一行中下一非零元素的指針十字鏈表的特點：①每行非零元素鏈接成帶表頭結點的循環(huán)鏈表；②每列非零元素也鏈接成帶表頭結點的循環(huán)鏈表。則每個非零元素既是行循環(huán)鏈表中的一個結點；又是列循環(huán)鏈表中的一個結點，即呈十字鏈狀。31第三十一頁，共五十三頁，編輯于2023年，星期三稀疏矩陣的十字鏈表存儲表示typedefstructOLNode{inti,j;/*該非零元的行和列下標*/ElemTypee;/*非零元素值*/structOLNode*right,*down;/*該非零元所在行表和列表的后繼鏈域*/}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;/*行和列鏈表頭指針向量基址,由CreatSMatrix_OL()分配*/intmu,nu,tu;/*稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)*/}CrossList;32第三十二頁，共五十三頁，編輯于2023年，星期三十字鏈表表示稀疏矩陣實例33第三十三頁，共五十三頁，編輯于2023年，星期三二、稀疏矩陣的操作

0

12

90000

00000-30001400

0240000

18000015

00-7000

0–3001512

000180

90024000

0000-70

0140000

00000(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)三元組表a.data三元組表b.data轉(zhuǎn)置后MT（以轉(zhuǎn)置運算為例）目的：34第三十四頁，共五十三頁，編輯于2023年，星期三答：肯定不正確！除了：（1）每個元素的行下標和列下標互換（即三元組中的i和j互換）；還應該：（2）T的總行數(shù)mu和總列數(shù)nu與M值不同（互換）；（3）重排三元組內(nèi)元素順序，使轉(zhuǎn)置后的三元組也按行（或列）為主序有規(guī)律的排列。上述（1）和（2）容易實現(xiàn)，難點在（3）。若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種說法正確嗎？有兩種實現(xiàn)方法壓縮轉(zhuǎn)置(壓縮)快速轉(zhuǎn)置提問：35第三十五頁，共五十三頁，編輯于2023年，星期三方法1：壓縮轉(zhuǎn)置思路：反復掃描a.data中的列序，從小到大依次進行轉(zhuǎn)置。三元組表a.data三元組表b.data①(1,3,-3)②(1,6,15)③(2,1,12)④(2,5,18)⑤(3,1,9)⑥(3,4,24)⑦(4,6,-7)⑧(5,3,14)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)1122colq1234p123436第三十六頁，共五十三頁，編輯于2023年，星期三StatusTransPoseSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){

q=1;for(col=1;col<=M.nu;col++){for(p=1;p<=M.tu;p++){if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].value=M.data[p].value;q++;}}}

}returnOK;}//TranposeSMatrix;壓縮轉(zhuǎn)置算法描述：（見教材P99）//用三元組表存放稀疏矩陣M，求M的轉(zhuǎn)置矩陣T//q是轉(zhuǎn)置矩陣T的結點編號//col是掃描M三元表列序的變量//p是M三元表中結點編號37第三十七頁，共五十三頁，編輯于2023年，星期三1、主要時間消耗在查找M.data[p].j=col的元素，由兩重循環(huán)完成:for(col=1;col<=M.nu;col++)循環(huán)次數(shù)＝nu

{for(p=1;p<=M.tu;p++)循環(huán)次數(shù)＝tu所以該算法的時間復雜度為O(nu*tu)----即M的列數(shù)與M中非零元素的個數(shù)之積最惡劣情況：M中全是非零元素，此時tu=mu*nu，時間復雜度為O(nu2*mu)注：若M中基本上是非零元素時，即使用非壓縮傳統(tǒng)轉(zhuǎn)置算法的時間復雜度也不過是O(nu*mu)（程序見教材P99）結論：壓縮轉(zhuǎn)置算法不能濫用。前提：僅適用于非零元素個數(shù)很少（即tu<<mu*nu）的情況。壓縮轉(zhuǎn)置算法的效率分析：38第三十八頁，共五十三頁，編輯于2023年，星期三方法2

快速轉(zhuǎn)置三元組表a.data三元組表b.data③(1,3,-3)①(2,1,12)⑥(2,5,18)②(3,1,9)⑧(4,6,-7)④(5,3,14)⑦(1,6,15)⑤(3,4,24)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)思路：依次把a.data中的元素直接送入b.data的恰當位置上（即M三元組的p指針不回溯）。關鍵：怎樣尋找b.data的“恰當”位置？p1234q3539第三十九頁，共五十三頁，編輯于2023年，星期三如果能預知M矩陣每一列(即T的每一行)的非零元素個數(shù)，又能預知第一個非零元素在b.data中的位置,則掃描a.data時便可以將每個元素準確定位（因為已知若干參考點）。技巧：利用帶輔助向量的三元組表，它正好攜帶每行（或列）的非零元素個數(shù)NUM(i)以及每行（或列）的第一個非零元素在三元組表中的位置POS(i)等信息。設計思路：i123456NUM(i)202112POS(i)133567不過我們需要的是按列生成的M矩陣的輔助向量。規(guī)律：POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)請回憶：請注意a.data特征：每列首個非零元素必定先被掃描到。40第四十頁，共五十三頁，編輯于2023年，星期三令：M中的列變量用col表示；

num[col]：存放M中第col列中非0元素個數(shù)，

cpot[col]：存放M中第col列的第一個非0元素的位置，

（即b.data中待計算的“恰當”位置所需參考點）討論：按列優(yōu)先的輔助向量求出后，下一步該如何操作？由a.data中每個元素的列信息，即可直接查出b.data中的重要參考點之位置，進而可確定當前元素之位置！col123456num[col]222110cpot[col]1規(guī)律：cpot(1)＝1cpot[col]＝

cpot[col-1]+num[col-1]0

12

90000

00000-30001400

0240000

18000015

00-700M35788col12345641第四十一頁，共五十三頁，編輯于2023年，星期三StatusFastTransposeSMatrix（TSMatirxM,TSMatirx&T）{T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;col++)num[col]=0;for(i=1;i<=M.tu;i++){col=M.data[i].j;++num[col];}

cpos[1]=1;for(col=2;col<=M.nu;col++)cpos[col]=cpos[col-1]+num[col-1];for(p=1;p<=M.tu;p++)

{

col=M.data[p].j;q=cpos[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].value=M.data[p].value;

++cpos[col];}

//for}//ifreturnOK;}//FastTranposeSMatrix;快速轉(zhuǎn)置算法描述：//M用順序存儲表示，求M的轉(zhuǎn)置矩陣T//先統(tǒng)計每列非零元素個數(shù)//再生成每列首元位置輔助向量表//p指向a.data，循環(huán)次數(shù)為非0元素總個數(shù)tu//查輔助向量表得q，即T中位置//重要語句！修改向量表中列坐標值，供同一列下一非零元素定位之用！42第四十二頁，共五十三頁，編輯于2023年，星期三1.與常規(guī)算法相比，附加了生成輔助向量表的工作。增開了2個長度為列長的數(shù)組(num[]和cpos[]）。傳統(tǒng)轉(zhuǎn)置：O(mu*nu)壓縮轉(zhuǎn)置：O(mu*tu)壓縮快速轉(zhuǎn)置：O(nu+tu)——犧牲空間效率換時間效率。快速轉(zhuǎn)置算法的效率分析：2.從時間上，此算法用了4個并列的單循環(huán)，而且其中前3個單循環(huán)都是用來產(chǎn)生輔助向量表的。for(col=1;col<=M.nu;col++)循環(huán)次數(shù)＝nu;

for(i=1;i<=M.tu;i++)循環(huán)次數(shù)＝tu;

for(col=2;col<=M.nu;col++)循環(huán)次數(shù)＝nu;for(p=1;p<=M.tu;p++)循環(huán)次數(shù)＝tu;

該算法的時間復雜度＝(nu*2)+(tu*2)=O(nu+tu）討論：最惡劣情況是tu=nu*mu(即矩陣中全部是非零元素），而此時的時間復雜度也只是O(mu*nu)，并未超過傳統(tǒng)轉(zhuǎn)置算法的時間復雜度。小結：稀疏矩陣相乘的算法見教材P101-10343第四十三頁，共五十三頁，編輯于2023年，星期三5.4廣義表的定義廣義表是線性表的推廣，也稱為列表（lists）記為：LS=(a1,a2,……，an)廣義表名表頭(Head）表尾(Tail)1、定義：①第一個元素是表頭，而其余元素組成的表稱為表尾；②用小寫字母表示原子類型，用大寫字母表示列表。n是表長在廣義表中約定：討論：廣義表與線性表的區(qū)別和聯(lián)系？廣義表中元素既可以是原子類型，也可以是列表；當每個元素都為原子且類型相同時，就是線性表。44第四十四頁，共五十三頁，編輯于2023年，星期三2、特點：有次序性有長度有深度可遞歸可共享一個直接前驅(qū)和一個直接后繼＝表中元素個數(shù)＝表中括號的重數(shù)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。45第四十五頁，共五十三頁，編輯于2023年，星期三E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))，E為遞歸表1）A=()2）B=(e)