第6章 數(shù)組和特殊矩陣

第6章數(shù)組和特殊矩陣本章講解數(shù)組和特殊矩陣。要求理解數(shù)組和特殊矩陣的概念；掌握數(shù)組的存儲結(jié)構(gòu)和基本操作算法；理解特殊矩陣的壓縮存儲算法；靈活應(yīng)用數(shù)組，了解特殊矩陣的應(yīng)用。喜歡老家的壩壩宴，接地氣而實惠，最主要的是能吃到小時候的味道。每回，好吃的作者在開席前都要跑到廚房去瞅瞅，豐富的菜品一排一列擺得整整齊齊真壯觀！真誘人！這是數(shù)組，這是矩陣??！提綱6.1數(shù)組基本概念6.2數(shù)組存儲結(jié)構(gòu)6.3數(shù)組基本操作6.4數(shù)組應(yīng)用6.5特殊矩陣基本概念6.6特殊矩陣壓縮存儲6.7特殊矩陣應(yīng)用6.8數(shù)組和特殊矩陣學(xué)習(xí)總結(jié)6.1數(shù)組基本概念

6.1數(shù)組基本概念數(shù)組分為1維數(shù)組、2維數(shù)組和多維數(shù)組。2維數(shù)組可以看作其元素是1維數(shù)組構(gòu)成的數(shù)組，3維數(shù)組可以看作其元素是2維數(shù)組構(gòu)成的數(shù)組，依此類推。6.2數(shù)組存儲結(jié)構(gòu)1維數(shù)組的存儲結(jié)構(gòu)1維數(shù)組所有元素依邏輯次序存放在一片連續(xù)的內(nèi)存單元中，其起始地址為第1個元素a0的地址記為LOC(a0)，假設(shè)每個元素占用k個存儲單元，則元素ai的存儲地址LOC(ai)可由以下公式求出：LOC(ai)=LOC(a0)+i×k（1≤i<n）由此可見，1維數(shù)組具有隨機存取特點。6.2數(shù)組存儲結(jié)構(gòu)2.2維數(shù)組的存儲結(jié)構(gòu)2維數(shù)組的存儲可以分為按行優(yōu)先存儲和按列優(yōu)先存儲。6.2數(shù)組存儲結(jié)構(gòu)（1）按行優(yōu)先存儲按行優(yōu)先存儲是指2維數(shù)組中的元素按照從左到右、從上到下的順序進(jìn)行存儲：a0,0a0,1...a0,n-1a1,0a1,1...a1,n-1...am-1,0am-1,1...am-1,n-1。元素ai,j的存儲地址LOC(ai,j)可由以下公式求出：LOC(ai,j)=LOC(a0,0)+(i×n+j)×k（ai,j元素前面有i行（0到i-1））n列，第i行中其前面有j（0到j(luò)-1）個元素）6.2數(shù)組存儲結(jié)構(gòu)（2）按列優(yōu)先存儲按列優(yōu)先存儲是指2維數(shù)組中的元素按照從上到下、從左到右的順序進(jìn)行存儲：a0,0a1,0...am-1,0a0,1a1,1...am-1,1...a0,n-1a1,n-1...am-1,n-1。元素ai,j的存儲地址LOC(ai,j)可由以下公式求出：LOC(ai,j)=LOC(a0,0)+(j×m+i)×k（ai,j元素前面有j列（0到j(luò)-1））m行，第j列中其上面有i（0到i-1）個元素）6.3數(shù)組基本操作數(shù)組的操作包含創(chuàng)建、初始化、插入、查找、更新、刪除、清空、判空等操作，同順序表的操作，詳見第2章2.2.2順序表類SeqList和算法2.1至2.4。6.4數(shù)組應(yīng)用【例6.1】求含有n個元素的1維整型數(shù)組a中任意2個元素差的絕對值的最小值。思路：（1）將數(shù)組a的所有元素遞增排序；（2）求兩兩元素差的絕對值；（3）比較這些絕對值，輸出最小的絕對值。代碼見應(yīng)用6.16.4數(shù)組應(yīng)用【進(jìn)一步思考】例6.1算法若不使用排序，其實現(xiàn)思路是什么。答：（1）求出所有差值的絕對值，當(dāng)計算出來是0時直接返回輸出，否則執(zhí)行（2）；（2）將這些絕對值放到另1個數(shù)組中；（3）求這個數(shù)組的最小元素并輸出之。6.4數(shù)組應(yīng)用【例6.2】將1個n階2維整型數(shù)組a的所有元素轉(zhuǎn)置。思路：以2維數(shù)組的主對角線為中心線，交換兩邊的對稱元素，即交換a[i][j]和a[j][i]。代碼見應(yīng)用6.26.4數(shù)組應(yīng)用

6.4數(shù)組應(yīng)用

6.4數(shù)組應(yīng)用

6.4數(shù)組應(yīng)用

6.4數(shù)組應(yīng)用【進(jìn)一步思考】例6.4算法改成求最小值，代碼如何修改？答：將Math類中的max函數(shù)換成min函數(shù)。6.5特殊矩陣基本概念

6.5特殊矩陣基本概念各種特殊矩陣舉例：6.6特殊矩陣壓縮存儲對于上述的特殊矩陣，在計算機中又是如何存儲的呢？這里先要搞清楚2個問題：第1，它們都是非線性結(jié)構(gòu)，如何存儲呢？第2，它們的特點是否決定了不必存儲所有的元素？對于第1個問題，我們可以將這些矩陣線性化，再進(jìn)行存儲；對于第2個問題，答案是肯定的，即我們可以通過壓縮算法對這些矩陣進(jìn)行壓縮存儲以節(jié)省空間。6.6.1對稱矩陣壓縮存儲對稱矩陣的壓縮存儲是指通過壓縮算法將1個對稱矩陣A存儲到1個1維數(shù)組B中，存儲的元素是上/下三角部分加主對角線上的元素。6.6.1對稱矩陣壓縮存儲

6.6.2三角矩陣壓縮存儲三角矩陣的壓縮存儲是指通過壓縮算法將1個三角矩陣A存儲到1個1維數(shù)組B中，存儲的元素是上/下三角部分加主對角線上的元素和常量C。6.6.2三角矩陣壓縮存儲

6.6.3對角矩陣壓縮存儲對角矩陣的壓縮存儲是指通過壓縮算法將1個對角矩陣A存儲到1個1維數(shù)組B中，存儲的元素是非0元素。6.6.3對角矩陣壓縮存儲

6.6.4稀疏矩陣壓縮存儲3元組稀疏矩陣的3元組存儲方式是將矩陣中的非0元素的行號、列號及元素值存入到1個3元組（i,j,ai,j）中。6.6.4稀疏矩陣壓縮存儲2.十字鏈表稀疏矩陣的十字鏈表存儲方式是稀疏矩陣的鏈?zhǔn)酱鎯Ψ绞?。?）十字鏈表中結(jié)點的相對位置同對應(yīng)的矩陣；（2）down和right指針，若向下和向右無非零元素，則回指向頭結(jié)點，否則指向所在列和行的元素；（3）行和列皆為循環(huán)單鏈表結(jié)構(gòu)。6.7特殊矩陣應(yīng)用【例6.6】求1個3元組表示為a的稀疏矩陣的轉(zhuǎn)置矩陣的3元組表示b。思路：（1）按列號順序遍歷a，構(gòu)造行/列號相反順序的3元組元素；（2）將該元素添加到b的3元組集合中；（3）