【正文】 第5章 數(shù)組和廣義表第5章 數(shù)組和廣義表本章學(xué)習(xí)要點(diǎn)◆掌握多維數(shù)組在行優(yōu)先順序存儲結(jié)構(gòu)中地址的計(jì)算方法◆了解特殊矩陣壓縮存儲時(shí)的下標(biāo)轉(zhuǎn)換方法◆掌握稀疏矩陣常用的兩種壓縮存儲表示方法（三元組表和十字鏈表表示法）的特點(diǎn)和存儲結(jié)構(gòu)◆掌握稀疏矩陣在三元組表表示下的基本運(yùn)算（矩陣加法、減法、轉(zhuǎn)置和乘法等）方法◆了解廣義表的有關(guān)概念、廣義表的各種表示方法和存儲結(jié)構(gòu)◆掌握廣義表的基本操作（求廣義表的表頭、表尾、表的深度以及廣義表的復(fù)制等）數(shù)組是最常用的數(shù)據(jù)結(jié)構(gòu)之一，幾乎所有的高級程序設(shè)計(jì)語言都把數(shù)組類型設(shè)定為內(nèi)部類型。在前面討論的線性結(jié)構(gòu)中，其數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型，元素的值是不可再分解的。本章所討論的數(shù)組可以看成是線性表的一種擴(kuò)展，即線性表中的每個(gè)數(shù)據(jù)元素本身也是一個(gè)線性表。稀疏矩陣是一種特殊的二維數(shù)組，因其在壓縮存儲方面的特點(diǎn)而被廣泛使用。廣義表是一種較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，它是線性結(jié)構(gòu)和樹型結(jié)構(gòu)的拓廣。廣義表被廣泛應(yīng)用于人工智能等領(lǐng)域。如果一個(gè)向量的所有元素又都是向量（或稱子向量），且這些子向量具有相同的上限和下限標(biāo)號，那么這種特殊形式的向量稱為數(shù)組。一維數(shù)組是一個(gè)向量，它的每一個(gè)元素都是該結(jié)構(gòu)中不可分割的最小單位。n(n1)維數(shù)組是一個(gè)向量，它的每個(gè)元素都是n1維數(shù)組，且具有相同的上限和下限。從邏輯結(jié)構(gòu)上看，n維數(shù)組Array中各元素的位置由該元素的下標(biāo)唯一確定，一旦給定一組下標(biāo)(j0,j1,j2,…,jn1)，都存在唯一的一個(gè)與其相對應(yīng)的元素值a稱為數(shù)組元素，記為a(j0,j1,j2,…,jn1)。其中，0=jibi，bi稱為第i維的長度(i=0,1,2,…,n1)。數(shù)組一旦被定義，它的元素類型（即數(shù)組類型）、維數(shù)、各維的界（長度）就不再改變。所以數(shù)組的基本操作主要有：（1）初始化InitArray(Array amp。A,int dim,int* bounds)：該操作根據(jù)數(shù)組元素類型、維數(shù)dim和長度bounds定義一個(gè)數(shù)組（初始化數(shù)組）A。（2）讀取操作Value(Array A,int* script,EType amp。e)：該操作根據(jù)下script標(biāo)讀取數(shù)組A中的元素到e中。（3）修改操作Assign(Arrayamp。 A,int* script,EType e)：該操作根據(jù)下標(biāo)script修改數(shù)組A中的元素為e的值。（4）銷毀操作：該操作回收一個(gè)數(shù)組所占的資源（銷毀數(shù)組）。由于數(shù)組不作插入和刪除操作，也就是說，一旦建立了數(shù)組，則該數(shù)組結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)。因此，采用順序存儲結(jié)構(gòu)表示數(shù)組是最合理的方式。但是，由于內(nèi)存地址是一維結(jié)構(gòu)，而數(shù)組可以是多維結(jié)構(gòu)，所以，必須有一個(gè)從多維下標(biāo)到一維地址的對應(yīng)關(guān)系。1．?dāng)?shù)組的兩種順序存儲方法（1）以行（左下標(biāo)）為主序的存儲結(jié)構(gòu)該存儲結(jié)構(gòu)以最左面的下標(biāo)為主序，右下標(biāo)優(yōu)先變化，即下標(biāo)變化順序是從右到左。以二維數(shù)組為例，（a）所示。對于三維數(shù)組：（有2頁、2行、3列），（b）所示。（2）以列（右下標(biāo)）為主序的存儲結(jié)構(gòu)該存儲結(jié)構(gòu)以最右面的下標(biāo)為主序，左下標(biāo)優(yōu)先變化，即下標(biāo)變化順序是從左到右。以二維數(shù)組：為例，（a）所示。對于三維數(shù)組：（有2頁、2行、3列），（b）所示。2．左下標(biāo)為主序存儲的n維數(shù)組中的元素a(j0,j1,...,jn1)的地址計(jì)算公式對于一個(gè)已經(jīng)被定義的二維數(shù)組Ab0b1=(a[i][j])b0b1，只要給出該數(shù)組存放的起始地址LOC(a[0][0])、數(shù)組元素的行下標(biāo)i和列下標(biāo)j，以及每個(gè)元素所占用的存儲單元（字節(jié)）數(shù)L，便可以求得元素a[i][j]在內(nèi)存中的首地址LOC(a[i][j])。地址計(jì)算公式為： 其中b1為數(shù)組第2維的長度（界）。對于以行為主序的n維數(shù)組，數(shù)組元素a(j0,j1,...,jn1)的地址計(jì)算公式為：其中為數(shù)組元素a[0][0]...[0]的地址，L為每個(gè)元素所占內(nèi)存的字節(jié)數(shù)，b0,b1,...,bn1為每一維的長度。如果記：,即可得到映像常數(shù)向量：，相應(yīng)的n維數(shù)組元素的地址計(jì)算公式可簡寫為：完全類似地，讀者可以自行給出以右下標(biāo)為主序的n維數(shù)組元素a(j0,j1,...,jn1)的地址計(jì)算公式。【】二維數(shù)組M56的元素是4個(gè)字符（每個(gè)字符占1個(gè)存儲單元）組成的串，那么M按行優(yōu)先（以左下標(biāo)為主序）存儲時(shí)元素M[3][5]的起始地址與M按列優(yōu)先（以右下標(biāo)為主序）存儲時(shí)的哪個(gè)元素的起始地址相同？解：按行優(yōu)先存儲時(shí)元素M[3][5]的起始地址為：LOC(M[3][5]) =LOC(M[0][0])+(i6+j)4=LOC(M[0][0])+(36+5)4=LOC(M[0][0])+234按列優(yōu)先存儲時(shí)元素M[i][j]的起始地址為：LOC(M[i][j])=LOC(M[0][0])+(j5+i)4=LOC(M[0][0])+234=LOC(M[0][0])+(45+3)4所以，要求的元素M[i][j]即為M[3][4]?！尽恳阎狝456為按左下標(biāo)為主序存儲的3維數(shù)組，每個(gè)元素占4個(gè)存儲單元，并且元素A[0][0][0]的首地址為1000，分別計(jì)算元素A[1][2][3]、A[3][2][0]和A[1][3][5]的首地址。解：按左下標(biāo)為主序的地址計(jì)算公式為：LOC(A[i][j][k])= LOC(A[0][0][0])+(ib1b2+jb2+k)L。所以：LOC(A[1][2][3])=1000+(156+26+3)4=1180LOC(A[3][2][0])=1000+(356+26+0)4=1408LOC(A[1][3][5])=1000+(156+36+5)4=1212【】已知A456為按右下標(biāo)為主序存儲的3維數(shù)組，每個(gè)元素占2個(gè)存儲單元，并且元素A[0][0][0]的首地址為100，分別計(jì)算元素A[1][2][3]、A[3][2][0]和A[1][3][5]的首地址。解：按右下標(biāo)為主序的地址計(jì)算公式為：LOC(A[i][j][k])= LOC(A[0][0][0])+(kb0b1+jb0+i)L。所以：LOC(A[1][2][3])=100+(354+24+1)2=238LOC(A[3][2][0])=100+(054+24+3)2=122LOC(A[1][3][5])=100+(554+34+1)2=3261．?dāng)?shù)組的順序存儲結(jié)構(gòu)表示在C++語言環(huán)境中，順序數(shù)組的存儲表示如下include //標(biāo)準(zhǔn)輸入輸出頭文件typedef int EType。 //便于上機(jī)操作定義數(shù)組類型為整型（int）struct Array{ EType *base。 //數(shù)組的基地址 int dim。 //數(shù)組的維數(shù) int *bounds。 //數(shù)組維界向量基地址 int *constent。 //數(shù)組元素的映像常數(shù)向量}。2．?dāng)?shù)組的初始化操作操作int InitArray(Array amp。A,int dim,int* bounds)的功能是，、。如果輸入維數(shù)dim合理返回1，表示操作成功，否則返回0表示操作失敗。int InitArray(Array amp。A,int dim,int* bounds){ int length=1,i。 if(dim1)return 0。 =new int[dim]。 //分配維界向量的存儲空間 =new int[dim]。 //分配映像向量的存儲空間 for(i=0。idim。i++) { length*=bounds[i]。 //計(jì)算數(shù)組元素的總數(shù) [i]=bounds[i]。 } =dim。 =new EType[length]。 //分配數(shù)組元素的存儲空間 [dim1]=1。 for(i=dim2。i=0。i) //計(jì)算數(shù)組元素的映像常數(shù)向量[i]=[i+1]*[i+1]。 return 1。}3．根據(jù)下標(biāo)(script)提取數(shù)組元素的操作操作int Value(Array A,int* script,EType amp。e)的功能是，根據(jù)下標(biāo)向量script提取數(shù)組A中相應(yīng)元素的值到e中。如果下標(biāo)合理返回1表示提取成功，否則返回0表示操作失敗。int Value(Array A,int* script,EType amp。e){ int i,off=0。 for(i=0。i。i++) { if(script[i]=[i]|| script[i]0) return 0。 off+= script[i]*[i]。 //計(jì)算對應(yīng)元素的偏移量off }e=[off]。 return 1。}簡化的提取數(shù)組元素操作函數(shù)EType Value(Array A,int* script)，該操作對下標(biāo)越界不做檢查。EType Value(Array A,int* script){ int i,off=0。 for(i=0。i。i++)off+= script[i]*[i]。 return [off]。}4．根據(jù)下標(biāo)(script)修改數(shù)組元素的操作操作int Assign(Arrayamp。 A,int* script,EType e)的作用是，根據(jù)下標(biāo)向量script修改數(shù)組A中相應(yīng)元素的值為e。如果下標(biāo)合理返回1表示修改成功，否則返回0表示操作失敗。int Assign(Arrayamp。 A,int* script,EType e){ int i,off=0。 for(i=0。i。i++) { if(script[i]=[i]|| script[i]0) return 0。 off+= script[i]*[i]。 //計(jì)算對應(yīng)元素的偏移量off } [off]=e。 return 1。}5．?dāng)?shù)組的按行序輸入操作操作void ArrayInput(Arrayamp。 A)的功能是，以左下標(biāo)為主序依次輸入多維數(shù)組A中各元素的值。void ArrayInput(Arrayamp。 A){ int length=1,i。 for(i=0。i。i++)length*=[i]。 cout以行為主序的順序輸入A。 for(i=0。i。i++) coutchar((i)?39。*39。:39。[39。)[i]。 cout]中的length個(gè)元素的值。\n。 for(i=0。ilength。i++)cin[i]。}6．?dāng)?shù)組的按行序輸出操作操作void Arrayoutput(Array A)的功能是，按左下標(biāo)為主序，輸出一維、二維、三維和多維數(shù)組A中的元素。 void Arrayoutput(Array A) { int s[3],i,len=1。 switch() { case 1: //按一維數(shù)組格式輸出 for(s[0]=0。s[0][0]。s[0]++) coutValue(A,s) 。 coutendl。 break。 case 2: //按二維數(shù)組格式輸出 for(s[0]=0。s[0][0]。s[0]++) { for(s[1]=0。s[1][1]。s[1]++) coutValue(A,s) 。 coutendl。 } break。 case 3: //按三維數(shù)組格式輸出 for(s[0]=0。s[0][0]。s[0]++) { cout第s[0]+1頁:\n。 for(s[1]=0。s[1][1]。s[1]++) { for(s[2]=0。s[2][2]。s[2]++) coutValue(A,s) 。 coutendl。 } } break。 default: //三維以上按左下標(biāo)優(yōu)先的一維數(shù)組格式輸出 cout維數(shù)為大于3\n按左下標(biāo)為主序輸出所有元素的值:\n。 for(i=0。i。i++)len*=[i]。 for(i=0。ilen。i++)cout[i] 。 coutendl。 } }7．矩陣的轉(zhuǎn)置操作操作int Trans(Array amp。 A,Array B)作用是，計(jì)算矩陣B的轉(zhuǎn)置矩陣A。如果B的維數(shù)不等于2返回0表示操作失敗，否則返回1表示操作成功。int Trans(Arrayamp。 A,Array B){ if(!=2)return 0。 int dim=2,s[2],s1[2]。 int bounds[]={[1],[0]}。 InitArray(A,dim,bounds)。 //初始化數(shù)組A for(s[0]=0。s[0][0]。s[0]++) for(s[1]=0。s[1][1]。s[1]++) { s1[0]=s[1],s1[1]=s[0]。