數(shù)據(jù)結(jié)構(gòu) 課件 第6章 數(shù)組

第6章數(shù)組1總體要求：熟悉數(shù)組的定義及存儲(chǔ)熟悉特殊矩陣的定義及存儲(chǔ)熟悉數(shù)組的抽象數(shù)據(jù)類型描述中各種操作的含義熟練掌握數(shù)組在各種存儲(chǔ)結(jié)構(gòu)下算法的實(shí)現(xiàn)核心技能點(diǎn)：數(shù)組應(yīng)用于實(shí)際問題的能力；特殊矩陣應(yīng)用于實(shí)際問題的能力熟練掌握數(shù)組在各種存儲(chǔ)結(jié)構(gòu)下算法的實(shí)現(xiàn)的能力第6章數(shù)組2擴(kuò)展技能點(diǎn)：C語言環(huán)境下各種算法的實(shí)現(xiàn)相關(guān)知識(shí)點(diǎn)：C語言數(shù)組的知識(shí)線性代數(shù)的知識(shí)C語言指針的知識(shí)C語言函數(shù)的知識(shí)學(xué)習(xí)重點(diǎn)：熟悉數(shù)組的定義及存儲(chǔ)熟悉特殊矩陣的定義及存儲(chǔ)熟悉數(shù)組的抽象數(shù)據(jù)類型描述中各種操作的含義掌握數(shù)組在各種存儲(chǔ)結(jié)構(gòu)下算法的實(shí)現(xiàn)第6章數(shù)組36.1二維數(shù)組應(yīng)用實(shí)例及概念數(shù)組是我們很熟悉的一種數(shù)據(jù)類型，很多高級(jí)語言都支持這種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看作一般線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個(gè)線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。如果說一維數(shù)組在邏輯上可看成一個(gè)向量，那么二維數(shù)組在邏輯上可看成由若干行、列組成的表格或矩陣。如表6.1學(xué)生成績(jī)表就對(duì)應(yīng)了一個(gè)二維數(shù)組。第6章數(shù)組

表6.1學(xué)生成績(jī)表4

表中每一行表示了某個(gè)學(xué)生的各門課程的成績(jī)。可定義二維數(shù)組A存放以上學(xué)生成績(jī)intA[4][5]；對(duì)線性表A=（A0,A1,A2,…Am-1），如果其中的任意元素Ai（0≤i≤m-1）是簡(jiǎn)單類型，則A是一個(gè)一維數(shù)組，如果Ai本身也是一個(gè)線性表，即Ai=（ai0，ai1，…，ain-1），則A是一個(gè)二維數(shù)組。如圖6.1所示。第6章數(shù)組5圖6.1由線性表推廣得到的二維數(shù)組第6章數(shù)組6

同理，三維數(shù)組可以看成是這樣的一個(gè)線性表，其中每個(gè)數(shù)據(jù)元素均是一個(gè)二維數(shù)組。依次類推，可以得到多維數(shù)組。從數(shù)組的特殊結(jié)構(gòu)，我們可以看出，數(shù)組中的每一個(gè)元素由一個(gè)值和一組下標(biāo)來描述。“值”代表數(shù)組中元素的數(shù)據(jù)信息，一組下標(biāo)用來描述該元素在數(shù)組中的相對(duì)位置信息。數(shù)組的維數(shù)不同，描述其對(duì)應(yīng)位置的下標(biāo)的個(gè)數(shù)也不同。例如，在二維數(shù)組中，元素a[i][j]由兩個(gè)下標(biāo)值i，j來描述，其中i表示該元素所在的行號(hào)，j表示該元素所在的列號(hào)。同樣，我們可以將這個(gè)特性推廣到多維數(shù)組，對(duì)于n維數(shù)組而言，其元素由n個(gè)下標(biāo)值來描述其在n維數(shù)組中的相對(duì)位置。第6章數(shù)組76.2數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn)6.2.1數(shù)組的順序存儲(chǔ)對(duì)于數(shù)組A，一旦給定其維數(shù)n及各維長(zhǎng)度b，則該數(shù)組中元素的個(gè)數(shù)是固定的，不能對(duì)數(shù)組做插入和刪除操作，不涉及移動(dòng)數(shù)據(jù)元素操作，因此對(duì)于數(shù)組而言，采用順序存儲(chǔ)方式比較合適。我們知道，計(jì)算機(jī)內(nèi)存器的結(jié)構(gòu)是一維的，因此對(duì)于一維數(shù)組按下標(biāo)順序分配即可，而對(duì)多維數(shù)組，就必須按照某種次序，將數(shù)據(jù)元素排成一個(gè)線性序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。第6章數(shù)組8

數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種：一是以行為主序（或先行后列）的順序存放，如BASIC、PASCAL、COBOL、C等程序設(shè)計(jì)語言中用的是以行為主的順序分配，即一行分配完了接著分配下一行。另一種是以列為主序（先列后行）的順序存放，如FORTRAN語言中，用的是以列為主序的分配順序，即一列一列地分配。例如，二維數(shù)組a[m][n]以行為主序的存儲(chǔ)序列為：A[0][0]，a[0][1]，…，a[0][n-1]，a[1][0]，a[1][1]，…，a[1][n-1]，…a[m-1][0]，a[m-1][1]，…a[m-1][n-1]。第6章數(shù)組96.2.2數(shù)組的實(shí)現(xiàn)數(shù)組是各種高級(jí)語言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。在高級(jí)語言的應(yīng)用層上，一般不會(huì)涉及到數(shù)據(jù)元素的存儲(chǔ)地址的計(jì)算，這一計(jì)算內(nèi)存地址的任務(wù)是由高級(jí)語言的編譯系統(tǒng)完成的。當(dāng)我們使用數(shù)組進(jìn)行程序設(shè)計(jì)時(shí)，只需給出數(shù)組的下標(biāo)范圍，編譯系統(tǒng)將根據(jù)用戶提供的必要參數(shù)進(jìn)行地址分配，存取數(shù)據(jù)元素時(shí)，也只要給出下標(biāo)，而不必考慮其內(nèi)存情況。例如：定義數(shù)組inta[3][4]；引用數(shù)組元素printf(“%d”,a[2][3])；這些在學(xué)習(xí)C語言時(shí)都已掌握。用這種方法定義的數(shù)組，①必須預(yù)先定義，②一經(jīng)定義不能再改變大小，存在缺陷。下面介紹動(dòng)態(tài)定義數(shù)組。第6章數(shù)組10

C語言動(dòng)態(tài)存儲(chǔ)管理一章介紹過四個(gè)函數(shù)①void*calloc(intn,intsize)分配n塊size大小的空間。②void*malloc(intsize)分配size大小的空間。③void*realloc(*p,intsize)改變p所指存儲(chǔ)空間大小為size。④free(p)釋放p所指存儲(chǔ)空間。有了這四個(gè)函數(shù)，我們就可以動(dòng)態(tài)地創(chuàng)建數(shù)組了。第6章數(shù)組11下面DataType*Make1DArray(intn)實(shí)現(xiàn)創(chuàng)建了n個(gè)元素的一維數(shù)組。Destroy1DArray(DataType*p)實(shí)現(xiàn)銷毀。main()實(shí)現(xiàn)測(cè)試。#defineDataTypeint#include<stdio.h>#include<stdlib.h>/*定義了n個(gè)元素的一維數(shù)組。*/DataType*Make1DArray(intn){DataType*a;/*動(dòng)態(tài)申請(qǐng)n個(gè)DataType類型的內(nèi)存空間，內(nèi)存不足時(shí)退出*/if((a=(DataType*)malloc(n*sizeof(DataType)))==NULL){printf("內(nèi)存空間不夠！");exit(0);}returna;}第6章數(shù)組12/*銷毀數(shù)組*/Destroy1DArray(DataType*p){free(p);}/*測(cè)試數(shù)組主函數(shù)*/voidmain(void){inti,n=10;DataType*a;a=Make1DArray(n);for(i=0;i<n;i++)a[i]=i;for(i=0;i<n;i++)printf("%4d",a[i]);Destroy1DArray(a);}第6章數(shù)組132.二維數(shù)組的動(dòng)態(tài)創(chuàng)建和銷毀二維數(shù)組的創(chuàng)建要比一維復(fù)雜一些，下面int**Make2DArray(introw,intcol)實(shí)現(xiàn)創(chuàng)建了row行，col列的二維數(shù)組。Destroy2DArray(int**a,introw)實(shí)現(xiàn)銷毀。main()實(shí)現(xiàn)測(cè)試。第6章數(shù)組14#include<stdio.h>#include<stdlib.h>#defineDataTypeintDataType**Make2DArray(introw,intcol){DataType**a;inti;/*動(dòng)態(tài)申請(qǐng)row行個(gè)DataType指針類型的內(nèi)存空間，內(nèi)存不足時(shí)退出*/if((a=(DataType**)malloc(row*sizeof(DataType*)))==NULL){printf("內(nèi)存空間不夠！");exit(0);}for(i=0;i<row;i++)if((a[i]=(DataType*)malloc(col*sizeof(DataType)))==NULL){printf("內(nèi)存空間不夠！");exit(0);}returna;}第6章數(shù)組15/*銷毀動(dòng)態(tài)二維數(shù)組存儲(chǔ)空間*/Destroy2DArray(DataType**a,introw){inti;for(i=0;i<row;i++)free(a[i]);free(a);}第6章數(shù)組16voidmain(void){inti,j,c;introw=5,col=8;DataType**a;a=Make2DArray(row,col);c=1;for(i=0;i<row;i++){for(j=0;j<col;j++){a[i][j]=c;c++;}}for(i=0;i<row;i++){for(j=0;j<col;j++)printf("%4d",a[i][j]);printf("\n");}Destroy2DArray(a,row);}

從以上實(shí)例可以看出，用動(dòng)態(tài)的方式定義數(shù)組后，可以像靜態(tài)數(shù)組一樣使用。第6章數(shù)組176.3特殊矩陣的壓縮存儲(chǔ)矩陣是科學(xué)計(jì)算、工程數(shù)學(xué)中大量研究的對(duì)象。對(duì)于一個(gè)矩陣結(jié)構(gòu)顯然用一個(gè)二維數(shù)組來表示是非常恰當(dāng)?shù)?。但在有些情況下，例如有些高階矩陣中，階次很高，數(shù)據(jù)量很大，而非零元素非常少（遠(yuǎn)小于m×n），若仍采用二維數(shù)組存放，就會(huì)有很多存儲(chǔ)單元都存放的是0，這不僅造成存儲(chǔ)空間的浪費(fèi)，而且給運(yùn)算帶來了很大的不便，這時(shí)，就很希望能夠只存儲(chǔ)部分有效元素。另外，還有一些矩陣的數(shù)據(jù)元素分布有一定規(guī)律，如三角矩陣、對(duì)稱矩陣、帶狀矩陣等，那么就可以利用這些規(guī)律，只存儲(chǔ)部分元素，從而提高存儲(chǔ)空間的利用率。這些問題都需要對(duì)矩陣進(jìn)行壓縮存儲(chǔ)，一般的壓縮原則是：對(duì)有規(guī)律的元素和值相同的元素只分配一個(gè)存儲(chǔ)空間，對(duì)零元素不分配空間。在這一節(jié)討論幾種特殊矩陣及對(duì)它們進(jìn)行壓縮存儲(chǔ)的方式。第6章數(shù)組186.3.1三角矩陣三角矩陣可以分為三類：下三角矩陣、上三角矩陣、對(duì)稱矩陣。對(duì)于一個(gè)n階矩陣A來說，若當(dāng)i<j時(shí)，有aij=0或aij=c（c為常數(shù)），則稱此矩陣為下三角矩陣；若當(dāng)i>j時(shí)，有aij=0或aij=c（c為常數(shù)），則稱此矩陣為上三角矩陣；若矩陣中的所有元素均滿足aij=aji，則稱此矩陣為對(duì)稱矩陣。例如，圖6.2就是一個(gè)n×n的下三角矩陣，我們以此為例來討論三角矩陣的壓縮存儲(chǔ)。第6章數(shù)組19圖6.2n×n的下三角矩陣A第6章數(shù)組20

對(duì)于下三角矩陣，只需存儲(chǔ)下三角的非零元素，對(duì)于零元素則不存儲(chǔ)。若以“行序?yàn)橹餍颉边M(jìn)行存儲(chǔ)，得到的序列是：a00

，a10

，a11

，a20

，…，an-1,0

，an-1,1

，…，an-1,n-1由于下三角矩陣的元素個(gè)數(shù)為n(n+1)/2，即第0行：1個(gè)第1行：2個(gè)第2行：3個(gè)…

…

…第n-1行：n個(gè)共有1+2+3+…+n=n(n+1)/2個(gè)所以可將三角矩陣壓縮到一個(gè)大小為n(n+1)/2的一維數(shù)組C中，如圖6.3所示。第6章數(shù)組21圖6.3三角矩陣的壓縮存儲(chǔ)第6章數(shù)組22

假設(shè)每個(gè)數(shù)據(jù)元素占size個(gè)存儲(chǔ)單元，下三角矩陣中任意元素aij在一維數(shù)組C中的存儲(chǔ)位置可通過下式計(jì)算：Loc(aij)=Loc(a00)+（i*（i+1）/2+j）×size（i≥j）也就是說，如果A中數(shù)據(jù)元素aij存于C[k]，則下標(biāo)k與下三角矩陣中數(shù)據(jù)元素aij的下標(biāo)i、j之間的關(guān)系為：

k=（i*（i+1）/2+j）若上三角部分為一常數(shù)c，則數(shù)組的大小可設(shè)為C[n(n+1)/2+1]，其中C[n(n+1)/2]存放常數(shù)c。第6章數(shù)組23

同理，對(duì)上三角矩陣，只需存儲(chǔ)上三角的非零元素，對(duì)于零元素則不存儲(chǔ)，同樣可以將其壓縮存儲(chǔ)到一個(gè)大小為n(n+1)/2的一維數(shù)組中。若以“行序?yàn)橹餍颉边M(jìn)行存儲(chǔ)，得到的序列是：a00，a01，a02，…，a0,n-1，a1,1a1,n-1，…，an-1,n-1其中元素aij（i≤j）在數(shù)組C中的存儲(chǔ)位置為：k=i*（2n-i+1）/2+j-i（i≤j）請(qǐng)大家試著自己推導(dǎo)這一結(jié)果。第6章數(shù)組246.3.2稀疏矩陣設(shè)Mm×n矩陣中有t個(gè)非零元素，且t<<m×n，這樣的矩陣稱為稀疏矩陣。很多科學(xué)管理及工程計(jì)算中，常會(huì)遇到階數(shù)很高的大型稀疏矩陣。如果按常規(guī)分配方法，順序分配在計(jì)算機(jī)內(nèi)，那將是相當(dāng)浪費(fèi)內(nèi)存的，并且也給計(jì)算帶來不便。如圖6.5所示的矩陣M中，非零元素個(gè)數(shù)為7個(gè)，矩陣元素為42個(gè)，顯然是一個(gè)稀疏矩陣。圖6.5稀疏矩陣第6章數(shù)組251.稀疏矩陣的三元組表存儲(chǔ)對(duì)于稀疏矩陣，我們?cè)O(shè)想另外一種存儲(chǔ)方法，即僅僅存放非零元素。但這類矩陣中零元素的分布通常沒有規(guī)律，為了能找到相應(yīng)的元素，所以僅存儲(chǔ)非零元素的值是不夠的，還要記下它所在的行和列。于是采取如下方法：將非零元素所在的行、列以及它的值構(gòu)成一個(gè)三元組（row，col，value），然后再按某種規(guī)律存儲(chǔ)這些三元組，這就是稀疏矩陣的三元組表示法。每個(gè)非零元素在一維數(shù)組中的三元組的結(jié)構(gòu)如圖6.6所示。圖6.6三元組的結(jié)構(gòu)第6章數(shù)組26

將三元組按行優(yōu)先的順序，同一行中列號(hào)從小到大的規(guī)律排列成一個(gè)線性表，稱為三元組表，采用順序存儲(chǔ)方法存儲(chǔ)該表。圖6.5所示稀疏矩陣對(duì)應(yīng)的三元組表如圖6.7。圖6.7稀疏矩陣的三元組表表示第6章數(shù)組27

顯然，要惟一地表示一個(gè)稀疏矩陣，在存儲(chǔ)三元組表的同時(shí)還需要存儲(chǔ)該矩陣的總行數(shù)、總列數(shù)，為了運(yùn)算方便，矩陣的非零元素的個(gè)數(shù)也同時(shí)存儲(chǔ)。三元組表的類型說明如下：defineMAX100/*一個(gè)足夠大的數(shù)*/typedefstruct{introw,col;/*非零元素的行、列*/DataTypev;/*非零元素值*/}Triple;/*三元組類型*/typedefstruct{intmu,nu,tu;/*矩陣的行、列及非零元素的個(gè)數(shù)*/Tripledata[MAX+1];/*三元組表，data[0]未用*/}TSMatrix;/*三元組表的存儲(chǔ)類型*/第6章數(shù)組282．用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置矩陣的三元組存儲(chǔ)方法確實(shí)節(jié)約了存儲(chǔ)空間，但矩陣的運(yùn)算從算法上可能變的復(fù)雜些。下面以稀疏矩陣的轉(zhuǎn)置運(yùn)算為例介紹其實(shí)現(xiàn)方法。所謂的矩陣轉(zhuǎn)置，是指把位于（row，col）位置上的元素轉(zhuǎn)換到（col，row）位置上，也就是說，把元素的行列互換。如圖6.5所示的6×7矩陣M，它的轉(zhuǎn)置矩陣就是7×6的矩陣N，如圖6.8所示，M[row][col]=N[col][row]。第6章數(shù)組29圖6.8矩陣M的轉(zhuǎn)置矩陣N第6章數(shù)組30

顯然，稀疏矩陣的轉(zhuǎn)置矩陣仍為稀疏矩陣，所以可以采用三元組表實(shí)現(xiàn)矩陣的轉(zhuǎn)置。設(shè)TSMatrixA；表示一個(gè)m×n的稀疏矩陣，其轉(zhuǎn)置B則是一個(gè)n×m的稀疏矩陣，因此也有TSMatrixB；由A求B需要：⑴A的行、列轉(zhuǎn)化成B的列、行；⑵將A.data中每一三元組的行列交換后存放到B.data中；并且保證B.data中的數(shù)據(jù)也是以“行序?yàn)橹餍颉边M(jìn)行存放（B.data中的行號(hào)即為A.data中的列號(hào)）。要保證B.data中的數(shù)據(jù)也是以“行序?yàn)橹餍颉边M(jìn)行存放，可以有兩種方法，下面分別介紹。第6章數(shù)組31方法一：這種方法的思路是按照A.data中的列序進(jìn)行轉(zhuǎn)置，并依次送入B.data中，即在A.data中依次找第一列的、第二列的、直到最后一列，并將找到的每個(gè)三元組的行、列交換后順序存儲(chǔ)到B.data中即可。轉(zhuǎn)置過程如圖6.9所示圖6.9矩陣的轉(zhuǎn)置第6章數(shù)組32

附設(shè)一個(gè)位置計(jì)數(shù)器j，用于指向當(dāng)前轉(zhuǎn)置后元素應(yīng)放入三元組表B.data中的位置。處理完一個(gè)元素后，j加1，j的初值為1。具體轉(zhuǎn)置算法如下：voidTransTSMatrix1(TSMatrixA,TSMatrix*B){inti,j,k;B->mu=A.nu;B->nu=A.mu;B->tu=A.tu;if(B->tu>0)/*有非零元素則轉(zhuǎn)換*/{j=1;for(k=1;k<=A.nu;k++)/*按A的列序轉(zhuǎn)換*/for(i=1;i<=A.tu;i++)/*掃描整個(gè)三元組表*/if(A.data[i].col==k){B->data[j].row=A.data[i].col;B->data[j].col=A.data[i].row;B->data[j].v=A.data[i].v;j++;}}}第6章數(shù)組33

分析該算法，其時(shí)間主要耗費(fèi)在k和i的二重循環(huán)上，所以時(shí)間復(fù)雜性為O(n×t)，(設(shè)m、n是原矩陣的行、列，t是稀疏矩陣的非零元素個(gè)數(shù))，顯然當(dāng)非零元素的個(gè)數(shù)t和m×n同數(shù)量級(jí)時(shí)，算法的時(shí)間復(fù)雜度為O(m×n2)，和通常存儲(chǔ)方式下矩陣轉(zhuǎn)置算法相比，可能節(jié)約了一定量的存儲(chǔ)空間，但算法的時(shí)間性能更差一些。第6章數(shù)組34方法二：方法一的效率低的原因是算法要從A的三元組表中尋找第一列、第二列、……直到最后一列的非零元素時(shí)，要反復(fù)搜索A表，若能直接確定A中每一三元組在B中的位置，則對(duì)A的三元組表掃描一次即可。這是可以做到的，因?yàn)锳中第一列的第一個(gè)非零元素一定存儲(chǔ)在B.data[1]，如果還知道第一列的非零元素的個(gè)數(shù)，那么第二列的第一個(gè)非零元素在B.data中的位置便等于第一列的第一個(gè)非零元素在B.data中的位置加上第一列的非零元素的個(gè)數(shù)，依次類推，因?yàn)锳中三元組的存放順序是先行后列，對(duì)同一行來說，必定先遇到列號(hào)小的元素，這樣只需掃描一遍A.data即可。第6章數(shù)組35

根據(jù)這個(gè)想法，需引入兩個(gè)輔助數(shù)組來實(shí)現(xiàn)：num[n+1]和pos[n+1]，num[col]表示矩陣A中第col列的非零元素的個(gè)數(shù)（為了方便均從1單元用起），pos[col]初始值表示矩陣A中的第col列的第一個(gè)非零元素在B.data中的位置。于是pos的初始值為：

pos[1]=1；

pos[col]=pos[col-1]+num[col-1]；2≤col≤n

例如對(duì)于矩陣圖6.9矩陣A的num和pos的值如圖6.10所示。圖6-10矩陣A的num與pos值第6章數(shù)組36

依次掃描A.data，當(dāng)掃描到一個(gè)col列元素時(shí)，直接將其存放在B.data的pos[col]位置上，pos[col]加１，pos[col]中始終是下一個(gè)col列元素在B.data中的位置。下面按以上思路改進(jìn)轉(zhuǎn)置算法如下：/*稀疏矩陣的快速轉(zhuǎn)置*/#defineN100voidTransTSMatrix2(TSMatrixA,TSMatrix*B){inti,j,k,col;intnum[N+1],pos[N+1];B->mu=A.nu;B->nu=A.mu;B->tu=A.tu;/*稀疏矩陣的行、列、元素個(gè)數(shù)*/if(B->tu)/*有非零元素則轉(zhuǎn)換*/第6章數(shù)組37{for(col=1;col<=A.nu;col++)num[col]=0;for(k=1;k<=A.tu;k++)/*求矩陣A中每一列非零元素的個(gè)數(shù)*/num[A.data[k].col]++;pos[1]=1;/*求矩陣A中每一列第一個(gè)非零元素在B.data中的位置*/for(col=2;col<=A.nu;col++)pos[col]=pos[col-1]+num[col-1];for(i=1;i<=A.tu;i++)/*掃描三元組表*/{col=A.data[i].col;/*當(dāng)前三元組的列號(hào)*/j=pos[col];/*當(dāng)前三元組在B.data中的位置*/B->data[j].col=A.data[i].row;B->data[j].row=A.data[i].col;B->data[j].v=A.data[i].v;pos[col]++;}}}第6章數(shù)組38

分析這個(gè)算法的時(shí)間復(fù)雜度：這個(gè)算法中有四個(gè)循環(huán)，分別執(zhí)行n，t，n-1，t次，在每個(gè)循環(huán)中，每次迭代的時(shí)間是一常量，因此總的計(jì)算量是O（n+t）。當(dāng)然它所需要的存儲(chǔ)空間比前一個(gè)算法多了兩個(gè)輔助數(shù)組。第6章數(shù)組393.疏矩陣的十字鏈表存儲(chǔ)三元組表可以看作稀疏矩陣順序存儲(chǔ)，但是在做一些操作（如加法、乘法）時(shí)，非零項(xiàng)數(shù)目及非零元素的位置會(huì)發(fā)生變化，這時(shí)這種表示就十分不便。下面我們介紹稀疏矩陣的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——十字鏈表，它同樣具備鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)，因此，在某些情況下，采用十字鏈表表示稀疏矩陣是很方便的。用十字鏈表表示稀疏矩陣的基本思想是：對(duì)每個(gè)非零元素存儲(chǔ)為一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)由5個(gè)域組成，其結(jié)構(gòu)如圖6.11表示。⑴row：存儲(chǔ)非零元素的行號(hào)；⑵col：存儲(chǔ)非零元素的列號(hào)；⑶value：域存儲(chǔ)本元素的值；⑷right：鏈接同一行的下一個(gè)非零元素；⑸down：鏈接同一列的下一個(gè)非零元素。第6章數(shù)組40圖6.11十字鏈表中的結(jié)點(diǎn)結(jié)構(gòu)

稀疏矩陣中每一行的非零元素結(jié)點(diǎn)按其列號(hào)從小到大順序由right域鏈成一個(gè)帶表頭結(jié)點(diǎn)的單向行鏈表，同樣每一列中的非零元素按其行號(hào)從小到大順序由down域也鏈成一個(gè)帶表頭結(jié)點(diǎn)的單向列鏈表。即每個(gè)非零元素aij既是第i行鏈表中的一個(gè)結(jié)點(diǎn)，又是第j列鏈表中的一個(gè)結(jié)點(diǎn)。這好像是處在一個(gè)十字交叉路上，所以稱其為十字鏈表。同時(shí)再附設(shè)一個(gè)存放所有行鏈表的頭指針的一維數(shù)組和一個(gè)存放所有列鏈表的頭指針的一維數(shù)組。如圖6.12是一個(gè)稀疏矩陣和其對(duì)應(yīng)的十字鏈表。第6章數(shù)組41圖6.12稀疏矩陣和對(duì)應(yīng)的十字鏈表第6章數(shù)組42十字鏈表的結(jié)構(gòu)類型說明如下：typedefstructOLNode{introw,col;/*非零元素的行和列下標(biāo)*/DataTypevalue;structOLNode*down,*right;/*非零元素所在的行表、列表的后繼鏈域*/}OLNode;*Olink;typedefstruct{Olink*rowHead;*colHead;/*行、列鏈表的頭指針*/intmu,nu,tu;/*稀疏矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/}CrossLink;第6章數(shù)組436.4數(shù)組應(yīng)用實(shí)例迷宮問題是一個(gè)經(jīng)典問題，這一節(jié)，我們利用數(shù)組來求解這一問題。我們可以用一個(gè)二維數(shù)maze[m+2][n+2]表示迷宮，其中元素0表示走得通，1表示走不通。為了敘述上的方便，設(shè)定由maze[1][1]進(jìn)入迷宮，由maze[m][n]走出迷宮。迷宮中任意一點(diǎn)的位置可由maze[row][col]來表示。在maze[row][col]的周圍有八個(gè)方向可走，為了避免檢測(cè)邊界狀態(tài)，二維數(shù)組maze[m+2][n+2]的零行、零列及m+1行、n+1列的值均為1。另外，為了簡(jiǎn)化計(jì)算，設(shè)一個(gè)二維數(shù)組move[8][2]={0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1}記錄可走的八個(gè)方向坐標(biāo)增量。move[k][0]表示第k個(gè)方向上row的增量，move[k][1]表示第k個(gè)方向上col的增量（第一個(gè)方向?yàn)檎龞|，第二方向?yàn)闁|南）。第6章數(shù)組44

例如，從maze[row][col]出發(fā)，沿東南的方向達(dá)到下一個(gè)位置maze[i][j]為：

i=row+move[1][0]=row+1j=row+move[1][1]=col+1

為了避免走重復(fù)路徑，我們用mark[m+2][n+2]來記走過的路徑。它的初值為0，一旦達(dá)到某個(gè)位置maze[row][col]，就把mark[row][col]置為1。

我們規(guī)定計(jì)算機(jī)走迷宮時(shí)，每次都從正東的方向起順時(shí)針檢測(cè)，當(dāng)檢測(cè)到某個(gè)方向下一個(gè)位置的值為零，并且沒有走過這一位置時(shí)，就沿此方向走一步。這樣依次重復(fù)檢測(cè)，當(dāng)某一步七個(gè)可前進(jìn)方向都為1時(shí)，則退回一步，重新檢測(cè)下一個(gè)方向。因此，我們必須讓計(jì)算機(jī)記下所走過的路徑和方向，以便退到剛走過的方位，并繼續(xù)檢測(cè)下一個(gè)方位。我們可以設(shè)置一個(gè)棧stack來記每一步的坐標(biāo)row、col。第6章數(shù)組45下面是一個(gè)7×10的迷宮實(shí)例。#include<stdio.h>main(){intmaze[9][12]={1,1,1,1,1,1,1,1,1,1,1,1,

1,0,1,0,0,0,1,1,0,1,1,1,

1,1,0,1,1,0,0,0,1,1,0,1,

1,1,0,1,1,0,1,1,0,0,1,1,

1,1,1,1,1,0,0,1,1,1,1,1,

1,0,0,1,1,1,1,0,1,1,0,1,

1,0,1,1,0,0,0,1,1,0,1,1,

1,1,0,1,1,0,1,0,0,1,0,1,

1,1,1,1,1,1,1,1,1,1,1,1};第6章數(shù)組46intmove[8][2]={0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1};/*move為下一步行走方向，值為坐標(biāo)增量*/intstack[64][2],mark[9][12]={0};/*stack為棧，記錄路徑；mark為標(biāo)記，記錄已走過的點(diǎn)*/inttop=1,row=1,col=1,k=0;/*k標(biāo)記方向，從正東開始*/inti,j;mark[row][col]=1;/*第一步*/stack[top][0]=row;stack[top][1]=col;while(!(row==7&&col==10)&&!top==0){i=row+move[k][0];j=col+move[k][1];/*下一步*/if(maze[i][j]==0&&mark[i][j]==0)mark[row][col]=1;}第6章數(shù)組47{top=top+1;k=0;row=i;col=j;/*可行走*/stack[top][0]=row;stack[top][1]=col;mark[row][col]=1;}else{k++;/*不可行走,看下一個(gè)方向*/if(k==8){k=0;top--;row=stack[top][0];col=stack[top][1];}/*八個(gè)方向全部不通*/}}第6章數(shù)組48if(top==0)printf("NOPATH!!!\n");else{printf("ALLPATH:");for(i=1;i<top+1;i++)printf("%d,%d\n",stack[i][0],stack[i][1]);for(i=1;i<top+1;i++)maze[stack[i][0]][stack[i][1]]=2;/*有通路標(biāo)記為2*/for(i=1;i<8;i++){for(j=1;j<11;j++)printf("%d",maze[i][j]);printf("\n");}}}第6章數(shù)組49本章小結(jié)

本章討論數(shù)組的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)、特殊矩陣以及矩陣的壓縮存儲(chǔ)等，并介紹了壓縮存儲(chǔ)下的算法實(shí)現(xiàn)。是以后解決工程問題的基礎(chǔ)。其主要內(nèi)容包括：1.基本概念和術(shù)語