數(shù)據(jù)結(jié)構(gòu)與算法分析第一頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.1數(shù)組定義

數(shù)組是數(shù)據(jù)結(jié)構(gòu)的基本結(jié)構(gòu)形式，它是一種順序式的結(jié)構(gòu)，數(shù)組是存儲(chǔ)同一類型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，使用數(shù)組時(shí)需要定義數(shù)組的大小和存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)類型，數(shù)組分為一維數(shù)組和多維數(shù)組。數(shù)組的維數(shù)是由數(shù)組的下標(biāo)的個(gè)數(shù)確定的，一個(gè)下標(biāo)稱為一維數(shù)組，一個(gè)下標(biāo)以上的數(shù)組稱為多維數(shù)組。從這個(gè)意義上講，確定了對(duì)于數(shù)組的一個(gè)下標(biāo)總有一個(gè)相應(yīng)的數(shù)值與之對(duì)應(yīng)的關(guān)系；或者說(shuō)數(shù)組是有限個(gè)同類型數(shù)據(jù)元素組成的序列。數(shù)組的基本操作包括：initarray（&A）；//初始化數(shù)組destroyarray（&A）；//銷毀數(shù)組assign（&A，e）；//數(shù)組賦值value（A，&e）；//取數(shù)組的某個(gè)元素copyarray（M，&T）；//復(fù)制一個(gè)數(shù)組printarray（M）；//打印數(shù)組的元素第二頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.1數(shù)組定義一維數(shù)組一維數(shù)組是指下標(biāo)的個(gè)數(shù)只有一個(gè)的數(shù)組，有時(shí)稱為向量，是最基本的數(shù)據(jù)類型，在java中需要事先聲名，程序才能夠在編譯過程中預(yù)留內(nèi)存空間。聲明的格式一般是：<數(shù)據(jù)類型><變量名稱>[]=new<數(shù)據(jù)類型>[<數(shù)組大小>]；

第三頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.1數(shù)組定義多維數(shù)組多維數(shù)組是指下標(biāo)的個(gè)數(shù)有兩個(gè)以上，我們比較常用的是二維數(shù)組（因?yàn)槿S以上的數(shù)組存儲(chǔ)可以簡(jiǎn)化為二維數(shù)組的存儲(chǔ)）。下面以二維數(shù)組為例說(shuō)明多維數(shù)組。二維數(shù)組的聲明同一維數(shù)組。格式為：<數(shù)據(jù)類型><數(shù)組名稱>[][]=new<數(shù)據(jù)類型>[size1][size2];第四頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.2數(shù)組的存儲(chǔ)一維數(shù)組的存儲(chǔ)一維數(shù)組的數(shù)據(jù)存儲(chǔ)按照順序存儲(chǔ)，邏輯地址和物理地址都是連續(xù)的。如果已知第一個(gè)數(shù)據(jù)元素的地址loc(a1)，則第i個(gè)元素的地址loc(ai)為：loc(ai)=loc(a1)+（i-1）*c假設(shè)數(shù)組的下標(biāo)從1開始，只要求出第i個(gè)元素之前存放了多少個(gè)數(shù)據(jù)元素即可（實(shí)際上有i-1個(gè)元素），每個(gè)元素占有c個(gè)存儲(chǔ)單元，再乘以c，就是第i個(gè)元素的起始地址。如果下標(biāo)從0開始，則第i個(gè)元素之前就有i個(gè)元素，此時(shí)上面的公式就變?yōu)椋簂oc(ai)=loc(a1)+i*c由此可見，求數(shù)組中數(shù)據(jù)元素的地址，已知條件必須是知道第一個(gè)元素的地址，然后主要是找出該元素之前已經(jīng)存儲(chǔ)了多少個(gè)數(shù)據(jù)元素。在一維數(shù)組中，只要知道任何一個(gè)元素的地址即可求出其它元素的地址，但在多維數(shù)組中，已知條件必須是第一個(gè)數(shù)據(jù)元素地址。第五頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.2數(shù)組的存儲(chǔ)多維數(shù)組以二維數(shù)組的順序存儲(chǔ)為例說(shuō)明，二維數(shù)組在順序存儲(chǔ)時(shí)一般有兩種：行優(yōu)先順序：存儲(chǔ)時(shí)先按行從小到大的順序存儲(chǔ)，在每一行中按列號(hào)從小到大存儲(chǔ)。列優(yōu)先順序：存儲(chǔ)時(shí)先按列從小到大的順序存儲(chǔ)，在每一列中按行號(hào)從小到大存儲(chǔ)。以上的兩種存儲(chǔ)順序中，第一個(gè)被存放的元素總是第一行第一列的數(shù)據(jù)元素，所以該元素的地址是我們的已知條件。同樣在二維數(shù)組中比較典型的是計(jì)算數(shù)據(jù)的存儲(chǔ)位置。第六頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.2數(shù)組的存儲(chǔ)多維數(shù)組假設(shè)二維數(shù)組是m*n的二維數(shù)組（共有m行，每行有n列）。第一個(gè)數(shù)據(jù)元素的地址是loc(a11)，則第i行第j列的數(shù)據(jù)元素的地址的計(jì)算公式應(yīng)為（按照行優(yōu)先順序存儲(chǔ)）：loc(aij)=loc(a11)+[（i-1）*n+j-1]*c假設(shè)下標(biāo)從1開始，我們需要計(jì)算出i行前面已經(jīng)存儲(chǔ)了i-1行元素，每行有n個(gè)元素，共有（i-1）*n個(gè)數(shù)據(jù)元素，在第i行元素中，j列之前有j-1個(gè)數(shù)據(jù)元素，共有（i-1）*n+j-1個(gè)元素，每個(gè)元素占有c個(gè)存儲(chǔ)單元，只要乘以c就可以了。其中l(wèi)oc(aij)表示第i行第j列數(shù)據(jù)元素的內(nèi)存的起始位置，loc(a11)表示第一個(gè)數(shù)據(jù)元素的內(nèi)存位置，c表示每個(gè)數(shù)據(jù)元素所占有的內(nèi)存空間的大小，如果下標(biāo)從0開始，只要不用減1即可。第七頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.2數(shù)組的存儲(chǔ)多維數(shù)組如果按列優(yōu)先順序存儲(chǔ)，則地址的計(jì)算為：loc(aij)=loc(a11)+[（j-1）*m+i-1]*c假設(shè)下標(biāo)從1開始，其中l(wèi)oc(aij)表示第i行第j列的數(shù)據(jù)元素的內(nèi)存起始位置，loc(a11)表示第一個(gè)數(shù)據(jù)元素的內(nèi)存位置，c表示每個(gè)數(shù)據(jù)元素所占有的內(nèi)存空間的大小；主要還是計(jì)算第i行j列元素之前有多少個(gè)數(shù)據(jù)元素。如果下標(biāo)從0開始，只要不用減1即可。按此公式可以推廣到多維數(shù)組的數(shù)據(jù)元素的地址計(jì)算（假設(shè)按照行優(yōu)先順序存儲(chǔ)）：m行n列縱標(biāo)為k的三維數(shù)組，假設(shè)第一個(gè)元素的地址是loc(a111)，如果按行優(yōu)先順序存儲(chǔ)，i行j列縱標(biāo)為p的數(shù)據(jù)元素的地址為（可以將它分解為二維數(shù)組）：loc(aijp)=loc(a111)+[(i-1)*n*k+(j-1)*k+p-1]*c;如果下標(biāo)從0開始，只要不用減1即可。讀者可以從以上的地址公式中可以找出一定的地址計(jì)算規(guī)律：多維數(shù)組中按行優(yōu)先計(jì)算公式用一個(gè)下標(biāo)乘以后面的最大值。第八頁(yè)，共二十三頁(yè)，2022年，8月28日4.1多維數(shù)組4.1.3顯示二維數(shù)組的內(nèi)容一般情況下，只要定義了數(shù)組的存儲(chǔ)順序，數(shù)組的存儲(chǔ)順序就不會(huì)改變了，所以對(duì)數(shù)組的各種操作后，應(yīng)按照數(shù)組的已定義的存儲(chǔ)順序存儲(chǔ)；也就是說(shuō)，如果是按行優(yōu)先順序存儲(chǔ)，在對(duì)數(shù)組操作后，即使改變了存儲(chǔ)順序，應(yīng)加以改變?nèi)匀话凑招袃?yōu)先順序存儲(chǔ)。

第九頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)所謂矩陣的壓縮存儲(chǔ)，也就是在存儲(chǔ)數(shù)組時(shí)，盡量減少存儲(chǔ)空間，但是數(shù)組中的每個(gè)元素必須存儲(chǔ)，所以在矩陣存儲(chǔ)中，如果有規(guī)律可尋，只要存儲(chǔ)其中一部分，而另一部分的存儲(chǔ)地址可以通過相應(yīng)的算法將它計(jì)算出來(lái)，從而占有比較少的存儲(chǔ)空間達(dá)到存儲(chǔ)整個(gè)矩陣的目的，稱為矩陣的壓縮存儲(chǔ)。矩陣的壓縮存儲(chǔ)僅是針對(duì)特殊矩陣的；而對(duì)于沒有規(guī)律可循的二維數(shù)組則不能夠使用壓縮存儲(chǔ)。二維數(shù)組（矩陣）的壓縮存儲(chǔ)一般有三種，它們分別是對(duì)稱矩陣、稀疏矩陣和三角矩陣。三種矩陣中以稀疏矩陣比較常見。

第十頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)特殊矩陣若n階矩陣A中的元素滿足以下條件：aij=ajii≥1，j≥1則稱為n階對(duì)稱矩陣。對(duì)于對(duì)稱矩陣，如果不采用壓縮存儲(chǔ)，占有的存儲(chǔ)單元有n2個(gè)，因?yàn)槭菍?duì)稱矩陣，所以只要存儲(chǔ)對(duì)角的數(shù)據(jù)元素和一半的數(shù)據(jù)元素即可，占有的存儲(chǔ)單元有n（n-1）/2個(gè)存儲(chǔ)單元中。如果我們以行序?yàn)橹餍虼鎯?chǔ)其下三角（包括對(duì)角線）的元素，其上三角的元素可以推算出來(lái)。第十一頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)特殊矩陣如果用一維數(shù)組存儲(chǔ)一個(gè)對(duì)稱矩陣，只要將對(duì)稱矩陣存儲(chǔ)在一個(gè)最大下標(biāo)為n（n-1）/2的一維數(shù)組S中即可。此時(shí)按照行優(yōu)先順序存儲(chǔ)，數(shù)據(jù)元素aij與數(shù)組S的下標(biāo)k的對(duì)應(yīng)關(guān)系為：i(i-1)/2+j-1當(dāng)i≥j時(shí)k=j(j-1)/2+i-1當(dāng)i＜j時(shí)第十二頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)特殊矩陣對(duì)于任意給定的一組下標(biāo)（i，j），均可在S中找到元素aij，反之，對(duì)所有元素都能夠確定在S中位置，當(dāng)i＜j時(shí)，根據(jù)對(duì)稱矩陣的性質(zhì)推算即可。由此可以看出對(duì)稱矩陣的存儲(chǔ)可以使用一維數(shù)組S存儲(chǔ)，占用的空間不再是n2，而是n（n-1）/2空間減少了接近一半，實(shí)現(xiàn)了二維數(shù)組的壓縮存儲(chǔ)。所謂對(duì)角矩陣是指，矩陣的所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線上和直接在主對(duì)角線上、下方若干條對(duì)角線上的元素之外，其余元素皆為零。

第十三頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)特殊矩陣也可以按照某個(gè)原則（或者以行序?yàn)橹餍?，或者以列序?yàn)橹餍?，或者按?duì)角線的順序）將對(duì)角矩陣B的所有非零元素壓縮存儲(chǔ)到一個(gè)一維數(shù)組LTB[1…3n-2]中。這里不妨仍然以行序?yàn)橹餍虻脑瓌t對(duì)B進(jìn)行壓縮存儲(chǔ)，當(dāng)B中任一非零元素bij與LTB[k]之間存在著如下一一對(duì)應(yīng)關(guān)系：k=2*i+j-2時(shí)，則有bij=LTB[k]。稱LTB[1…3n-2]為對(duì)角矩陣B的壓縮存儲(chǔ)。上面討論的幾種特殊矩陣中，非零元素的分布都具有明顯的規(guī)律，因而都可以被壓縮存儲(chǔ)到一個(gè)一維數(shù)組中，并能夠確定這些矩陣的每個(gè)非零元素在一維數(shù)組中的存儲(chǔ)位置。但是，對(duì)于那些非零元素在矩陣中的分布沒有規(guī)律的特殊矩陣(如稀疏矩陣)，則需要尋求其他方法來(lái)解決壓縮存儲(chǔ)問題。

第十四頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)稀疏矩陣對(duì)稀疏矩陣很難下一個(gè)確切的定義，它只是一個(gè)憑人們的直覺來(lái)理解的概念。一般認(rèn)為，一個(gè)較大的矩陣中，零元素的個(gè)數(shù)相對(duì)于整個(gè)矩陣元素的總個(gè)數(shù)所占比例較大時(shí)，該矩陣就是一個(gè)稀疏矩陣。例如，有一個(gè)6×6階的矩陣A，其36個(gè)元素中只有8個(gè)非零元素，那么，可以稱矩陣A為稀疏矩陣。稀疏矩陣一般是指矩陣中的大部分元素為零，僅有少量元素非零的矩陣稱為稀疏矩陣；或者說(shuō)矩陣A（m×n）中有S個(gè)非零元素，如果S遠(yuǎn)遠(yuǎn)小于矩陣的元素總數(shù)，稱A為稀疏矩陣。稀疏矩陣的存儲(chǔ)一般只要保存非零元素即可，對(duì)于零元素可以不與保存，這樣可以實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)。

第十五頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)稀疏矩陣稀疏矩陣的壓縮存儲(chǔ)采用三元組的方法實(shí)現(xiàn)。其存儲(chǔ)規(guī)則如下：每一個(gè)非零元素占有一行，每行中包含非零元素所在的行號(hào)、列號(hào)、非零元素的數(shù)值。為完整描述稀疏矩陣，一般在第一行描述矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)。其邏輯描述為：（rowcolvalue）其中row表示行號(hào)，col表示列號(hào)，value表示非零元素的值。如果每個(gè)非零元素按照此種方法存儲(chǔ)，雖然能夠完整地描述非零元素，但如果矩陣中有整行（或整列）中沒有非零元素，此時(shí)可能不能夠還原成原來(lái)的矩陣，所以為了完整地描述稀疏矩陣，在以上描述的情況下，如果增加一行的內(nèi)容，該行包括矩陣的總的行數(shù)、矩陣的總的列數(shù)，矩陣中非零元素的個(gè)數(shù)，就可以還原為原來(lái)的矩陣描述了。

第十六頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.1矩陣的壓縮存儲(chǔ)稀疏矩陣歸納起來(lái)，若一個(gè)稀疏矩陣有t個(gè)非零元素，則需要用t+1行的三元組來(lái)表示稀疏矩陣。到底矩陣何時(shí)使用三元組存儲(chǔ)呢？一般對(duì)m×n的矩陣來(lái)說(shuō)，只要滿足（t+1）*3≤m*n這個(gè)條件，使用三元組存儲(chǔ)可以節(jié)省空間，否則更加浪費(fèi)空間，也就沒有必要使用三元組存儲(chǔ)，所以稀疏矩陣中的非零元素的個(gè)數(shù)t是能否使用三元組存儲(chǔ)的關(guān)鍵。

第十七頁(yè)，共二十三頁(yè)，2022年，8月28日4.2矩陣的壓縮存儲(chǔ)4.2.2稀疏矩陣轉(zhuǎn)換為三元組存儲(chǔ)

首先應(yīng)該將稀疏矩陣轉(zhuǎn)換為三元組存儲(chǔ)，然后才利用三元組的存儲(chǔ)，實(shí)現(xiàn)對(duì)矩陣的各種運(yùn)算。對(duì)于矩陣的運(yùn)算一般有矩陣的轉(zhuǎn)置，在轉(zhuǎn)置時(shí)值得注意的是：在矩陣的存儲(chǔ)規(guī)則已經(jīng)確定的情況下（如按行優(yōu)先存儲(chǔ)），實(shí)現(xiàn)矩陣的運(yùn)算（如轉(zhuǎn)置）時(shí)，應(yīng)仍然保留原來(lái)的存儲(chǔ)規(guī)則。改進(jìn)的轉(zhuǎn)置方法可以利用對(duì)原始的三元組的元素的掃描，直接確定該元素在轉(zhuǎn)置后的三元組中的行，這樣可以將原始三元組中的元素直接放在轉(zhuǎn)置后的三元組中即可。這種方法需要增加兩個(gè)一維數(shù)組的結(jié)構(gòu)開銷，稱為快速轉(zhuǎn)置。第十八頁(yè)，共二十三頁(yè)，2022年，8月28日4.3廣義表4.3.1廣義表的定義廣義表是線性表的擴(kuò)展，具體定義為n（n≥0）個(gè)元素的有限集合。其中元素有以下兩種類型：1）一個(gè)原子元素（指不可再分的元素）；2）一個(gè)可以再分的元素（或稱為一個(gè)子表）。如果所有元素都是原子元素，則稱為線性表，如果含有子表則是廣義表。第十九頁(yè)，共二十三頁(yè)，2022年，8月28日4.3廣義表4.3.1廣義表的定義廣義表的基本操作：initGlist(&L)//創(chuàng)建空的廣義表creatGlist(&L,S)//由S創(chuàng)建廣義表LdestroyGlist(&L)//銷毀廣義表LGlistlength（L）//求廣義表的長(zhǎng)度Glistdepth（L）//求廣義表的深度Gethead(L)//求廣義表L的頭Gettail(L)//求廣義表的表尾Insertfirst_Glist(&L,e)//插入元素e作為廣義表L的第一個(gè)元素Deletefirst_Glist(&L,&e)//刪除廣義表L的第一個(gè)元素，并用e返回其值第二十頁(yè)，共二十三頁(yè)，2022年，8月28日4.3廣義表4.3.1廣義表的定義廣義表一般記作：LS=（a1，a2，…，an