第4章 數(shù)組和廣義表

本章主要介紹下列內(nèi)容：
　　1.數(shù)組的定義、基本運(yùn)算和存儲結(jié)構(gòu)
　　2.特殊矩陣的壓縮存儲
　　3.廣義表的定義、術(shù)語、存儲結(jié)構(gòu)、運(yùn)算
　　4.遞歸算法設(shè)計(jì)
課時(shí)分配：
1兩個(gè)學(xué)時(shí)，2兩個(gè)學(xué)時(shí)，3兩個(gè)學(xué)時(shí), 4兩個(gè)學(xué)時(shí)
重點(diǎn)、難點(diǎn)：
特殊矩陣的壓縮存儲、廣義表的存儲結(jié)構(gòu)、遞歸算法設(shè)計(jì)

第一節(jié) 數(shù)組

1．?dāng)?shù)組的定義和基本運(yùn)算
數(shù)組的特點(diǎn)是每個(gè)數(shù)據(jù)元素可以又是一個(gè)線性表結(jié)構(gòu)。因此，數(shù)組結(jié)構(gòu)可以簡單地定義為：若線性表中的數(shù)據(jù)元素為非結(jié)構(gòu)的簡單元素，則稱為一維數(shù)組，即為向量；若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則稱為二維數(shù)組；依次類推，若二維數(shù)組中的元素又是一個(gè)一維數(shù)組結(jié)構(gòu)，則稱作三維數(shù)組。
結(jié)論：線性表結(jié)構(gòu)是數(shù)組結(jié)構(gòu)的一個(gè)特例，而數(shù)組結(jié)構(gòu)又是線性表結(jié)構(gòu)的擴(kuò)展。舉例：

其中，A是數(shù)組結(jié)構(gòu)的名稱，整個(gè)數(shù)組元素可以看成是由m個(gè)行向量和n個(gè)列向量組成，其元素總數(shù)為m×n。 在C語言中，二維數(shù)組中的數(shù)據(jù)元素可以表示成a[表達(dá)式1][表達(dá)式2]，表達(dá)式1和表達(dá)式2被稱為下標(biāo)表達(dá)式，比如，a[i][j]。 數(shù)組結(jié)構(gòu)在創(chuàng)建時(shí)就確定了組成該結(jié)構(gòu)的行向量數(shù)目和列向量數(shù)目，因此，在數(shù)組結(jié)構(gòu)中不存在插入、刪除元素的操作。
二維數(shù)組結(jié)構(gòu)的基本操作：
（1）給定一組下標(biāo)，修改該位置元素的內(nèi)容 Assign(A,elem,index1,index2)
（2）給定一組下標(biāo)，返回該位置的元素內(nèi)容 Value(A,elem,index1,index2)
2．?dāng)?shù)組的存儲結(jié)構(gòu)
從理論上講，數(shù)組結(jié)構(gòu)也可以使用兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。然而，由于數(shù)組結(jié)構(gòu)沒有插入、刪除元素的操作，所以使用順序存儲結(jié)構(gòu)更為適宜。換句話說，一般的數(shù)組結(jié)構(gòu)不使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 組成數(shù)組結(jié)構(gòu)的元素可以是多維的，但存儲數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問題。舉例： LOC(i,j)=LOC(0,0)+(n*i+j)*L
數(shù)組結(jié)構(gòu)的定義：
#define MAX_ROW_INDEX 10
#define MAX_COL_INDEX 10
typedef struct{Elemtype elem[MAX_ROW_INDEX][MAX_COL_INDEX] } ARRAY;
基本操作算法舉例：
（1）給數(shù)組元素賦值
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）返回給定位置的元素內(nèi)容
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．矩陣的壓縮存儲
矩陣是在很多科學(xué)與工程計(jì)算中遇到的數(shù)學(xué)模型。在數(shù)學(xué)上，矩陣是這樣定義的：它是一個(gè)由s×n個(gè)元素排成的s行（橫向）n列（縱向）的表。下面就是一個(gè)矩陣

3．1特殊矩陣

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

k是對稱矩陣位于（i，j）位置的元素在一維數(shù)組中的存放位置。 操作算法的實(shí)現(xiàn)：
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號單元開始存放。 舉例：

操作算法的實(shí)現(xiàn)：
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）對角矩陣
我們以三階對角矩陣為例討論一下它的壓縮存儲方法。對于對角矩陣，壓縮存儲的主要思路是只存儲非零元素。這些非零元素按以行為主序的順序，從下標(biāo)為1 的位置開始依次存放在一維數(shù)組中，而0位置存放數(shù)值0。

操作算法的實(shí)現(xiàn)：
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 最大的非零元素個(gè)數(shù)
typedef struct{
int i,j; //行序號、列序號
Elemtype value; //非零元素值
}Three_Elem;
typedef struct {
Three_Elem Elem[MAXSIZE]; //存儲非零元素的一維數(shù)組
int rows,cols,tu; //稀疏矩陣的總行數(shù)、列數(shù)及非零元素個(gè)數(shù)
}Matrix;
操作算法的實(shí)現(xiàn)：
（1）返回元素內(nèi)容
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("\n");
}
}

第二節(jié) 廣義表

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

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