第4章 數組和廣義表

第4章 數組和廣義表

本章主要介紹下列內容：　　1.數組的定義、基本運算和存儲結構　　2.特殊矩陣的壓縮存儲　　3.廣義表的定義、術語、存儲結構、運算　　4.遞歸演算法設計課時分配：1兩個學時，2兩個學時，3兩個學時, 4兩個學時重點、難點：特殊矩陣的壓縮存儲、廣義表的存儲結構、遞歸演算法設計

第一節 數組

1．數組的定義和基本運算數組的特點是每個數據元素可以又是一個線性表結構。因此，數組結構可以簡單地定義為：若線性表中的數據元素為非結構的簡單元素，則稱為一維數組，即為向量；若一維數組中的數據元素又是一維數組結構，則稱為二維數組；依次類推，若二維數組中的元素又是一個一維數組結構，則稱作三維數組。結論：線性表結構是數組結構的一個特例，而數組結構又是線性表結構的擴展。舉例：

其中，A是數組結構的名稱，整個數組元素可以看成是由m個行向量和n個列向量組成，其元素總數為m×n。 在C語言中，二維數組中的數據元素可以表示成a[表達式1][表達式2]，表達式1和表達式2被稱為下標表達式，比如，a[i][j]。 數組結構在創建時就確定了組成該結構的行向量數目和列向量數目，因此，在數組結構中不存在插入、刪除元素的操作。二維數組結構的基本操作：（1）給定一組下標，修改該位置元素的內容 Assign(A,elem,index1,index2) （2）給定一組下標，返回該位置的元素內容 Value(A,elem,index1,index2) 2．數組的存儲結構從理論上講，數組結構也可以使用兩種存儲結構，即順序存儲結構和鏈式存儲結構。然而，由於數組結構沒有插入、刪除元素的操作，所以使用順序存儲結構更為適宜。換句話說，一般的數組結構不使用鏈式存儲結構。 組成數組結構的元素可以是多維的，但存儲數據元素的內存單元地址是一維的，因此，在存儲數組結構之前，需要解決將多維關係映射到一維關係的問題。舉例：

LOC(i,j)=LOC(0,0)+(n*i+j)*L 數組結構的定義： #define MAX_ROW_INDEX 10 #define MAX_COL_INDEX 10 typedef struct{Elemtype elem[MAX_ROW_INDEX][MAX_COL_INDEX] } ARRAY; 基本操作演算法舉例： （1）給數組元素賦值 void Assign(ARRAY *A,Elemtype elem,int index1,int index2) { if (index1<0||index1>=MAX_ROW_INDEX||index2<0||index2>=MAX_COL_INDEX) exit(ERROR); else A->elem[index1][index2]=elem; } （2）返回給定位置的元素內容int Value(ARRAY A,Elemtype *elem,int index1,int index2) { if (index1<0||index1>=MAX_ROW_INDEX|| index2<0||index2>=MAX_COL_INDEX) return FALSE; else { *elem= A.elem[index1][index2]; return OK; 3．矩陣的壓縮存儲 矩陣是在很多科學與工程計算中遇到的數學模型。在數學上，矩陣是這樣定義的：它是一個由s×n個元素排成的s行（橫向）n列（縱向）的表。下面就是一個矩陣

3．1特殊矩陣

對於這些特殊矩陣，應該充分利用元素值的分布規律，將其進行壓縮存儲。選擇壓縮存儲的方法應遵循兩條原則：一是儘可能地壓縮數據量，二是壓縮後仍然可以比較容易地進行各項基本操作。三種特殊矩陣的壓縮方法：（1）對稱矩陣 對稱矩陣的特點是aij=aji。一個n×n的方陣，共有n²個元素，而實際上在對稱矩陣中有n(n-1)/2個元素可以通過其他元素獲得。壓縮的方法是首先將二維關係映射成一維關係，並只存儲其中必要的n(n+1)/2個（主對角線和下三角）元素內容，這些元素的存儲順序以行為主序。舉例： 假設定義一個數組型變數：int A[10];

k是對稱矩陣位於（i，j）位置的元素在一維數組中的存放位置。 操作演算法的實現： int Value(int A[],Elemtype *elem,int i,int j) { if(i<1||i>MAX_ROW_INDEX|| j<1||j>MAX_COL_INDEX) return FALSE; else { if (i>=j) k=i*(i-1)/2+j-1;else k=j*(j-1)/2+i-1; *elem=A[k]; return TRUE; }} （2）下（上）三角矩陣 下三角矩陣的壓縮存儲與上面講述的對稱矩陣的壓縮存儲一樣，只是將上三角部分的常量值存儲在0單元，下三角和主對角上的元素從1號單元開始存放。 舉例：

操作演算法的實現：int Value(int A[],Elemtype *elem,int i,int j){ if(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDEX) return FALSE;else { if (i>=j) k=i*(i-1)/2+j; else k=0; *elem=A[k]; return TRUE;}}（3）對角矩陣我們以三階對角矩陣為例討論一下它的壓縮存儲方法。對於對角矩陣，壓縮存儲的主要思路是只存儲非零元素。這些非零元素按以行為主序的順序，從下標為1 的位置開始依次存放在一維數組中，而0位置存放數值0。

操作演算法的實現：int Value(int A[ ],Elemtype *elem,int i,int j){if(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDEX) return FALSE;else { if (j>=(i-1)&&j<=(i+1)) k=3*(i-1)+j-i+1; else k=0;*elem=A[k]; return TRUE;}}3．2 稀疏矩陣的壓縮存儲

類型定義：#define MAX_SIZE 100 最大的非零元素個數typedef struct{int i,j; //行序號、列序號Elemtype value; //非零元素值}Three_Elem;typedef struct {Three_Elem Elem[MAXSIZE]; //存儲非零元素的一維數組int rows,cols,tu; //稀疏矩陣的總行數、列數及非零元素個數}Matrix;操作演算法的實現：（1）返回元素內容 int Value(Matrix M,Elemtype *elem,int i,int j)if (i<1||i>rows||j<1||j>cols) exit(ERROR);else { for (p=0;p<M.tu;p++)if(M.elem[p].i==i&&M.elem[p].j==j) { *elem=M.elem[p].value; return OK; }else if (M.elem[p].i>i||M.elem[p].i==i&&M.Elem[p].j>j) break;*elem=0;return OK;}}（2）輸出三元組表示的稀疏矩陣 void Print(Matrix M){for (p=0,i=1;i<=M.rows;i++) {for (j=1;j<=M.cols;j++)if(p<M.tu&&M.elem[p].i==i&&M.elem[p].j==j) printf("%4d",M.elem[p++].value;);else printf("%4d",0);printf("
");}}

第二節 廣義表

1. 廣義表的定義廣義表（Lists，又稱列表）是線性表的推廣。在第2章中，我們把線性表定義為n>=0個元素a1,a2,a3,…,an的有限序列。線性表的元素僅限於原子項，原子是作為結構上不可分割的成分，它可以是一個數或一個結構，若放鬆對錶元素的這種限制，容許它們具有其自身結構，這樣就產生了廣義表的概念。廣義表是n(n>=0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。通常記作LS=（a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS的子表。通常用圓括弧將廣義表括起來，用逗號分隔其中的元素。為了區別原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。若廣義表LS（n>=1)非空，則a1是LS的表頭，其餘元素組成的表(a1,a2,…an)稱為LS的表尾。顯然廣義表是遞歸定義的，這是因為在定義廣義表時又用到了廣義表的概念。廣義表的例子如下：（1）A=（）--A是一個空表，其長度為零。（2）B=（e）--表B只有一個原子e，B的長度為1。（3）C=（a,(b,c,d))--表C的長度為2，兩個元素分別為原子a和子表(b,c,d)。（4）D=（A，B，C）--表D的長度為3，三個元素都是廣義表。顯然，將子表的值代入後，則有D=(( ),(e),(a,(b,c,d)))。（5）E=（E）--這是一個遞歸的表，它的長度為2，E相當於一個無限的廣義表E=(a,(a,(a,(a,…)))).從上述定義和例子可推出廣義表的三個重要結論：（1）廣義表的元素可以是子表，而子表的元素還可以是子表。由此，廣義表是一個多層次的結構，可以用圖形象地表示。（2）廣義表可為其它表所共享。例如在上述例（4）中，廣義表A，B，C為D的子表，則在D中可以不必列出子表的值，而是通過子表的名稱來引用。（3）廣義表的遞歸性。綜上所述，廣義表不僅是線性表的推廣，也是樹的推廣。2. 廣義表的存儲結構由於廣義表(a1,a2,a3,…an)中的數據元素可以具有不同的結構，（或是原子，或是廣義表），因此，難以用順序存儲結構表示，通常採用鏈式存儲結構，每個數據元素可用一個結點表示。由於廣義表中有兩種數據元素，原子或廣義表，因此，需要兩種結構的結點：一種是表結點，一種是原子結點。 下面介紹兩種廣義表的鏈式存儲結構。表結點由三個域組成：標誌域、指示表頭的指針域和指示表尾的指針域；而原子域只需兩個域：標誌域和值域。

其類型定義如下：typedef enum{ATOM,LIST}elemtag;typedef struct glnode{elemtag tag;union{atomtype atom;struct { struct glnode *hp,*tp;}ptr;};} *glist;例見書。3. 分析求廣義表深度和長度的遞歸演算法（見教材）這部分內容比較難，用1個課時講解，用1個課時答疑

推薦閱讀：