（一）教學目的：
掌握陣列的定義及順序表示與實現；
掌握矩陣的壓縮儲存；
廣義表的定義及儲存結構。
（二）教學重點：
1、陣列的定義及其儲存
2、特殊矩陣的壓縮儲存
3、稀疏矩陣邏輯結構和儲存結構
4、廣義表的邏輯結構和儲存結構
5、陣列和廣義表的操作應用舉例
（三）教學難點：
1、矩陣的壓縮儲存
2、廣義表的儲存結構
一、陣列的抽象型別定義：
資料物件：d= |n(>0)稱為陣列的維數，bi是陣列第i維的長度，ji是陣列元素的第i維下標，∈elemset}
資料關係：r= ri=>
0≤jk≤bk-1，1≤k≤n且k≠i，
0≤ji≤bi-2，∈d，i=2,…,n}
二、陣列基本操作：
1、initarray(&a,n,bound1,…,boundn)
操作結果：若維數n和各維長度合法，則構造相應的陣列a，並返回ok。
2、destroyarray（&a）
操作結果：銷毀陣列a。
3、value(a,&e,indeex1,…,indexn)
初始條件：a是n維陣列，e為元素變數，隨後是n個下標值。
操作結果：若各下標不超界，則e賦值為所指定的a的元素值，並返回ok。
4、assign(&a,e,index1,…,indexn)
初始條件：a是n維陣列，e為元素變數，隨後是n個下標值。
操作結果：若下標不超界，則將e的值賦給所指定的a的元素，並返回ok。
三、陣列與線性表的關係：
1、二維陣列與線性表的關係：
以把二維陣列看成是這樣一具定長線性表：它的每個資料元素也是乙個定長線性表。
a=(a0,a1,…,ap) (p=m-1或n-1)
其中每個資料元素aj是乙個列向量形式的線性表
aj=(a0j,aij,…,am-1j) 0≤j≤n-1
ai=(ai0,ai1,…,ai,n-1) 0≤i≤m-1
在c語言中，乙個二維陣列型別可以定義為其分量型別為一維陣列型別的一維陣列型別，也就是說，
typedef elemtype array2[m][n];
等價於 typedef elemtype array1[n];
typedef array1 array2[m];
(ab)
c )圖5·1二維數**例
（a）矩陣形式表示；（b）列向量的一維陣列；（c）行向量的一維陣列
2、n維陣列與線性表的關係：
同理，乙個n維陣列型別可以定義為其資料元素為n-1維陣列型別的一維陣列型別。
四、陣列的基本操作
陣列一旦被定義，它的維數和維界就不再改變。因此，除了結構的初始化和銷毀之外，陣列只有訪問元素和修改元素值的操作。
一、二維陣列的順序儲存：
則用一組連續儲存單元存放陣列的資料元素就有個次序約定問題。對二維陣列可有兩種儲存方式：在擴充套件basic、pl/1、cobol、pascal和c語言中，用的都是以行序為主序的儲存結構，而在fortran語言中，用的是以列序為主序的儲存結構。
（a） 以列序為主序 （b）以行序為主序
圖5.2 二維陣列的兩種儲存結構
二、陣列的位址計算：
1、二維陣列的位址計算：
假設每個資料元素佔l個儲存單元，則二維陣列a中任一元素aij的儲存位置可由下式確定
loc（i,j）=loc（0，0）+（b2×i+j）l (5——1)
式中，loc（i,j）是aij的儲存位置；loc（0，0）是a00的儲存位置，即二維陣列a的起始儲存位置，也稱為基位址或基址。
2、n維陣列位址計算：
loc(j1,j2,…,jn)=loc(0,0,…,0)＋(b2×…bn×j1＋b3×…bn×j2＋…＋bn×jn-1＋jn)l
=loc(0,0,…,0)＋()l
或縮寫成
loc（j1,j2,…,jn）=loc(0,0,…,05—2)
其中cn=l,ci-1=bi×ci, 11、壓縮儲存：為多個值相同的元只分配乙個儲存空間；對零元不分配空間。
2、特殊矩陣：假若值相同的元素或者零元素的矩陣中的分布有一定規律，則我們稱此類矩陣為特殊矩陣。
3、稀疏矩陣：非零元分布沒有任何規律，但是數量很少，這樣的矩陣我們稱為稀疏矩陣。
5．3．1特殊矩陣
一、對稱矩陣：
1、對稱矩陣定義：
若n階矩陣a中的元滿足下述性質aij=aji 1≤i,j≤n，則稱為n階對稱矩陣。
2、對稱矩陣的壓縮儲存：
對於對稱矩陣，我們可以為每一對對稱元分配乙個儲存空間，則可將n2個元壓縮儲存到n(n+1 )/2個元的空間中。
3、壓縮儲存元素與儲存位址之間的對應關係：
假設以一維陣列sa[n(n+1)/2]作為n階對稱矩陣a的儲存結構，則sa[k]和矩陣元aij之間存在著一一對應的關係：
5—3）
k= 0 1 2 3
圖5.3 對稱矩陣的壓縮儲存
二、三角矩陣：
所謂下（上）三角矩陣是指矩陣的上（下）三角（不包括對角線）中的元均為常數c或零的n階矩陣。則除了和對稱矩陣一樣只儲存其下（上）三角中的元之外，再加乙個儲存常數c的儲存空間即可。
三、對角矩陣：
所謂對角矩陣是指所有的非零元都集中在以主對角線為中心的帶狀區域中。即除了主對角線上和直接在對角線上、下方若干條對角線上的元之外，所有其他的元皆為零。如圖5.
4所示。對這種矩陣，我們也可按某個原則（或以行為主，或以對角線的順序）將其壓縮儲存到一維陣列上。
圖5.4 三對角矩陣
5.3.2 稀疏矩陣
假設在m×n的矩陣中，有t個元素不為零。令為矩陣的衡疏因子。通常認為時稱為稀疏矩陣。
圖5.5 稀疏矩陣m和t
一．三元組順序表
1、三元組順序表的定義：
假設以順序儲存結構來表示三元組表，則可得稀疏矩陣的一種壓縮儲存方式——我們稱之為三元組順序表。
#define maxsie 12500 //假設非零元個數的最大值為12500
typedef structtriple;
typedef structtsmatrix;
在此，data域中表示非零元的三元組是以行序為主序順序排列的。
2、矩陣的轉置運算。
從a轉置為b的主要過程：
（1）將矩陣的行列值相互交換；
（2）將每個三元組中的i和j要互調換；
（3）重排三元組之間的次序便可實現矩陣的轉置。
可以把兩種處理方法：
（1）按照中三元組的次序依次在中找到相應的三元組進行轉置。換句話說，按照矩陣m的列序來進行轉置。為了找到m的每一列中所有的非零元素，需要對其三元組表從第一行起整個掃瞄一遍，由於是以m的行序為主序來存放每個非零元的，由此得到的恰是應有的順序。
其具體演算法描述如演算法5.1所示。
status transposesmatrix(tsmatrix m, tsmatrix &t)
}return ok;
}//transposesmatrix
演算法 5.1
（2）按照中三元組的次序進行轉置，並將轉置後的三元組置入b中恰當的位置。如果能預先確定矩陣m中每一列（即t中每一行）的第乙個非零元在中應有的位置，那麼在對的三元組依次作轉置時，便可直接放到中恰當的位置上去。為了確定這些位置，在轉置前，應先求得m的每一列中非零元的個數，進而求得每一列的第乙個非零元在中應有的位置。
在此，需要附設num和cpot兩個向量。num[col]表示矩陣m中第col列中非零元的個數，cpot[col]指示m中第col列的第乙個非零元在中的恰當位置。顯然有
（5-4）
例如，對圖5.5的矩陣和cpot的值如表5.1所示。
表5.1 矩陣m的向量cpot的值
這種轉置方法稱為快速轉置，其演算法如演算法5.2所示。
status fastransposesmatrix(tsmatrix m, tsmatri×&t){
if(for(col=1; col＜ ++col） num[col]=0;
for(t=1;t＜ ++t） ++num[求m中每一列含非零元個數cpot[1]=1；
《資料結構》第5章陣列和廣義表
第 5 章陣列和廣義表 一 選擇題 1.設有乙個10階的對稱矩陣a，採用壓縮儲存方式，以行序為主儲存，a11為第一元素，其儲存位址為1，每個元素佔乙個位址空間，則a85的位址為 燕山大學 2001 一 2 2分 a.13b.33c.18d.40 2.有乙個二維陣列a 1 6，0 7 每個陣列元素用相...
《資料結構》習題集 第5章陣列與廣義表
第5章陣列與廣義表 一 選擇題 1.在以下講述中，正確的是 b a 線性表的線性儲存結構優於鍊錶儲存結構 b 二維陣列是其資料元素為線性表的線性表 c 棧的操作方式是先進先出 d 佇列的操作方式是先進後出 2.若採用三元組壓縮技術儲存稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉...
《資料結構題集》答案第5章陣列和廣義表
第五章陣列和廣義表 5.18 void rsh int a n int k 把陣列a的元素迴圈右移k位,只用乙個輔助儲存空間 print poly descend void get all int a,int m,int i,int seq 遞迴求出所有和為i的m個自然數 print nomial ...