本次課程內容

第四章 數組、廣義表和串

第一節 數組及廣義表

數組的基本操作

數組是高級程序設計語言中的重要語法成分，很多語言都定義了數組類型。例如，在C語言中，定義了一維數組。數組元素還可以是數組，由此得到數組的數組，

即多維數組。

一般將n(n>2)維數組看作n-1維數組的數組。

從數據結構的角度來理解，一維數組可以作為線性表的存儲結構，數組中保存的各元素可以組成一個線性表。多維數組在系統內部都對應一個隱含的一維數組，所

以多維數組也是一種線性表。例如，二維數組就是以一維數組為元素的線性表。

數組的每個元素都是形如(index，value)的二元對，index是數組下標，也稱為索引，value是對應于該下標的數值。任何兩個元素的index值都不相同。

從數組的操作可知，它沒有一般線性表常用的插入和刪除操作，更多的是根據下標index訪問元素。

數組的順序存儲方式-借用矩陣行列式概念

一維數組天然地采用順序存儲方式，

多維數組的順序存儲又是什么樣的呢?

數組的順序存儲有兩種形式。以二維數組為例，它的元素可以按行排列，也可以按列排列。

這里的“行”和“列”借用數學上矩陣或行列式中的概念。

所謂按行排列，就是先排數組的第一行，緊隨其后排第二行，依此類推。

所謂按列排列，就是先排數組的第一列，緊隨其后排第二列，依此類推。

最終都是將數組中的全部元素排列成一個序列。

在C語言中，可以定義多維數組，它的下標采取如下的形式表示:

二維數組C語言對應的函數-通常行主序方式

通常int類型占4字節，數組D2Array中含有18個元素，共占用18x4=72字節。如果保存的起始地址是1000，則數組將占用從1000到1071的內存空間。注意，這里

提到的字節編號并不是內存中真實的編號。將圖4-1所示的下標表格按行自上而下、同一行中自左至右的次序進行連續編號，從0開始，

即可得到圖4-2a所示的編號結果，

這種按行優先把二維數組中的下標映射到0~n-1之間的某個整數的方式稱為按行優先方式，也稱為行主序方式。

包括C語言在內的大多數程序設計語言均采用行主序的實現模式。

也有一些程序設計語言采用另一種實現模式，稱為按列優先方式，也稱為列主序方式。

在列主序方式中，按列優先，對于下標表格，從第一列開始，從上到下進行連續編號，直到最后一列。這個結果如圖4-2b所示。

矩陣的壓縮存儲

數學中的矩陣可以使用二維數組保存。對于n行m列的矩陣，數組元素至少需要分配n x m個。

有些矩陣因其特殊性，可以不必保存其中的所有元素，因而可以減少為數組分配的空間。

對稱矩陣和三角矩陣

如果不考慮矩陣的特殊性，按照一般二維數組的順序存儲方式來存儲特殊矩陣，也是完全可行的。

但是，從節省存儲空間的角度考慮，對稱矩陣和上(下)三角矩陣都可以只保存矩陣中約一半的元素，從而可以節省差不多一半的存儲空間。

這樣的存儲形式稱為壓縮存儲。

• 具體來說，對干對稱矩陣，因為對角線以上及以下的元素對稱相等，所以只需要保存其中的一半及對角線上的元素。

• 對于上三角矩陣或下三角矩陣，僅保存上三角部分或下三角部分的元素，另外一半的0元素不再保存。

若矩陣有n行n列，則這三種形式下需要保存的元素個數為nx(n+1)/2。

在采用壓縮存儲以后，需要尋找與普通二維數組不同的映射函數。

壓縮存儲后，采用不同的映射函數

稀疏矩陣-可以構成三元組線性表

在實際的應用中，矩陣中可能會出現大量的0元素，而非0元素數量很少，這就是所謂的稀疏矩陣。至于非0元素少到什么程度才能稱為稀疏矩陣，并沒有很嚴格的定義。通常認為，矩陣中非0元素的個數與矩陣的階數相當，即可將其看作稀疏矩陣。

• 如何理解？

為了節省空間，一般只存儲稀疏矩陣中的非0元素。但在稀疏矩陣中，非0元素的出現是沒有規律的，

所以在存儲非0元素時必須將它所在的行號和列號一起存儲起來。這些信息組成一個三元組(i，j，v)的形式

其中v表示非0元素的值，i表示v所在的行號，i表示v所在的列號。

一個稀疏矩陣的所有元素用一個三元組表來表示，也就是可以構成一個三元組的線性表。

為了方便后續其他操作的實現，三元組表應該是一個有序序列，通常按行主序的次序排列，即先按行的大小排列，同一行的三元組再按列的大小排列。

三元組表的初始值從鍵盤輸入，輸入時，各三元組可以按行主序排列，也可以按任意的次序排列，但最終都應該按行主序的次序插入到一維數組的合適位置。

當然，在有特殊需求的應用中，也可以按列主序方式保存。

三元組在C語言中的實現

三元組表的轉置

轉置是矩陣中常用的一種操作。下面實現采用三元組表表示的稀疏矩陣的轉置算法。矩陣轉置即行、列互換，i行的元素放置到i列，這也意味著，j列的元素放置在j行。如果矩陣是nxm則轉置后得到的矩陣是mxn的。
很容易想到，將三元組表中的每個三元組項的i與i互換，即可得到轉置后矩陣的三元組表。但是，這樣轉換后得到的三元組表不再按行主序排列，不便于后續操作的實現。所以，要實現矩陣轉置程序，必須先得到一個按行主序排列的三元組表。

可以像readSparseMatrix函數那樣處理，讀入原矩陣的一個三元組，插入到目標矩陣的三元組表中。在插入過程中，需要調整部分三元組在三元組表中的次序，也就是需要進行元素的移動。從順序表實現的時間復雜度分析中知道，這樣的移動會導致轉置操作的效率很低。
可以使用一個臨時計數數組，記錄原矩陣的每個三元組在目標矩陣的三元組表中的插入位置，以輔助完成轉置操作，由此避免了三元組的移動，可高效率地實現轉置操作。
不失一般性，設原矩陣A的行數是rows，列數是cols，則轉置后矩陣B的行數是cols，列數是rows。元組的個數沒有改變。

三元組轉置的算法實現

數組的應用-解決迷宮問題

多維數組，特別是二維數組，在計算機科學中有廣泛的應用。

下面以一個有趣的“迷宮”問題為例,介紹數組的應用。

“老鼠走迷宮”是實驗心理學中的一個經典問題，也是一種智力游戲。

在計算機模擬實現中，可以用-個較大的二維數組表示迷宮，其中元素0表示走得通，元素1表示走不通(受阻)，行走路徑只考慮水平和垂直方向上的4個方向(上、下、左、右)。圖4-9是一個迷宮示意圖。

• 適合解決復雜迷宮問題，簡單的用算法不至于

廣義表

廣義表是線性表的推廣，也稱為列表。

它是由n(n≥0)個表元素組成的有限序列，記為:

廣義表示例

廣義表操作示例