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