數(shù)據(jù)結(jié)構(gòu) 5數(shù)組和廣義表A

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1第5章數(shù)組和廣義表（Arrays&Lists）①元素的值并非原子類型，可以再分解，表中元素也是一個(gè)線性表（即廣義的線性表）。②所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型。5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)數(shù)組和廣義表的特點(diǎn)：一種特殊的線性表25.1數(shù)組的定義

數(shù)組：由一組名字相同、下標(biāo)不同的變量構(gòu)成答：對(duì)的。因?yàn)椋孩贁?shù)組中各元素具有統(tǒng)一的類型；②數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。討論：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單”，對(duì)嗎？一維數(shù)組的特點(diǎn)：1個(gè)下標(biāo)，ai

是ai+1的直接前驅(qū)3二維數(shù)組的特點(diǎn)：2個(gè)下標(biāo)，每個(gè)元素ai,j受到兩個(gè)關(guān)系（行關(guān)系和列關(guān)系）的約束：一個(gè)m×n的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n維數(shù)組可以看成是由若干個(gè)n－1維數(shù)組組成的線性表。

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=45.2數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)問題：計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一維的，而數(shù)組一般是多維的，怎樣存放？解決辦法：事先約定按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存入存儲(chǔ)器中。例如：在二維數(shù)組中，我們既可以規(guī)定按行存儲(chǔ)，也可以規(guī)定按列存儲(chǔ)。注意：若規(guī)定好了次序，則數(shù)組中任意一個(gè)元素的存放地址便有規(guī)律可尋，可形成地址計(jì)算公式；約定的次序不同，則計(jì)算元素地址的公式也有所不同；C和PASCAL中一般采用行優(yōu)先順序；FORTRAN采用列優(yōu)先。5補(bǔ)充：計(jì)算二維數(shù)組元素地址的通式

設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時(shí)求出任一元素的地址（這樣數(shù)組中的任一元素便可以隨機(jī)存?。。憾S數(shù)組列優(yōu)先存儲(chǔ)的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L

ac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=單個(gè)元素長度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長度aij本行前面的元素個(gè)數(shù)①開始結(jié)點(diǎn)的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個(gè)數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L6例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*L,按列存儲(chǔ)的公式是？

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*L（盡管是方陣，但公式仍不同）例1〖軟考題〗：一個(gè)二維數(shù)組A[1..6,0..7]，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是

個(gè)字節(jié)。288例3：〖00年計(jì)算機(jī)系考研題〗設(shè)數(shù)組a[1..60,1..70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為

。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：請(qǐng)注意審題！利用列優(yōu)先通式：答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2887Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是N維數(shù)組，其中任一元素的地址該如何計(jì)算？其中Cn=L,Ci-1=bi×Ci，1<i≤n一個(gè)元素長度數(shù)組基址前面若干元素占用的地址字節(jié)總數(shù)第i維長度與所存元素個(gè)數(shù)有關(guān)的系數(shù)，可用遞推法求出教材已給出低維優(yōu)先的地址計(jì)算公式，見P93（5-2）式該式稱為n維數(shù)組的映像函數(shù)：LOC(j1,j2,…,jn)=LOC(c1,c2,…,cn)+[(b2…bn)(j1-c1)+(b3…bn)(j2-c2)+…+bn(jn-1-cn-1)+(jn-cn)]L8#defineMAX_ARRAY_DIM8//假設(shè)最大維數(shù)為8

typedef

struct{

ELemType*base;//數(shù)組元素基址

intdim;//數(shù)組維數(shù)

int*bound;//數(shù)組各維長度信息保存區(qū)基址

int*constants;//數(shù)組映像函數(shù)常量的基址

}Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說明（有5個(gè)）（請(qǐng)閱讀教材P93-95）N維數(shù)組的順序存儲(chǔ)表示（見教材P93）以銷毀數(shù)組函數(shù)為例91StatusInitArray(Array&A,intdim,…){2//若維數(shù)dim和各維長度合法，則構(gòu)造相應(yīng)的數(shù)組A并返回OK3if(dim<1||dim>MAX_ARRAY_DIM)return

ERROR;4A.dim=dim;5A.bounds=(int*)malloc(dim*sizeof(int));6if(!A.bounds)exit(OVERFLOW);

7//若各維長度合法，則存入A.bounds,并求出A的元素總數(shù)elemtotal8elemtotal=1;9va_start(ap,dim);//ap為va_list類型，是存放變長參數(shù)表信息的類型數(shù)組的基本操作函數(shù)說明（5個(gè)）（見教材P93-95）10//P93代碼1-9行用于檢查維數(shù)和各維長度是否合法10for(i=0;i<dim;++i){11A.bounds[i]=va_arg(ap,int);12if(A.bounds[i]<0)return

UNDERFLOW;13elemtotal*=A.bounds[i];}14va_end(ap);15A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));16if(!A.base)exit(OVERFLOW);17A.constants=(int*)malloc(dim*sizeof(int));18if(!A.constants)exit(OVERFLOW);19A.constants[dim-1]=1;20for(i=dim-2;i>=0;--i)21A.constants[i]=A.bounds[i+1]*A.constants[i+1];22return

OK;23}111StatusDestroyArray(Array&A)2{//銷毀數(shù)組A3if(!A.base)return

ERROR;4free(A.base);5A.base=NULL;6if(!A.bounds)return

ERROR;7free(A.bounds);8A.bounds=NULL;9if(!A.constants)return

ERROR;10free(A.constants);11A.constants=NULL;12return

OK;13}數(shù)組基址指針各維長度保存區(qū)指針映像函數(shù)Ci保存區(qū)指針121StatusLocate(ArrayA,va_list

ap,int&off)2{3//若ap指示的各下標(biāo)值合法，則求出該元素在A中，相對(duì)地址off4off=0;5for(i=0;i<A.dim;++i)6{7ind=va_arg(ap,int);8if(ind<0||ind>A.bounds[i])return

OVERFLOW;9off+=A.constants[i]*ind;10}11return

OK;12}131StatusValue(ArrayA,ElemType&e,…){2//A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值，若各下標(biāo)不超界，則e賦值為所指定的A的元素值，即將指定元素值讀到e變量中。3va_start(ap,e);4if((result=Locate(A,ap,off))<=0)returnresult;5e=*(A.base+off);6return

OK;7}141StatusAssign(Array&A,ElemTypee,…){2//A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值，若各下標(biāo)不超界，則e的值賦為所指定的A的元素值，即：將e值寫入指定數(shù)組單元。3va_start(ap,e);4if((result=Locate(A,ap,off))<=0)returnresult;5*(A.base+off)=e;6return

OK;7}15LispandJohnMaCarthyLisp–LIStProcessor條件表達(dá)式、遞歸函數(shù)、廣義表、程序即數(shù)據(jù)（本身也同所有其他數(shù)據(jù)一樣用表結(jié)構(gòu)形式表示）、垃圾回收McCarthy-“人工智能之父”。1971年圖靈獎(jiǎng)–Lisp,AI,分時(shí)概念等麥卡錫是一個(gè)天賦很高的人，還在上初中時(shí)，他就弄了一份加州理工大學(xué)的課程目錄，按目錄自學(xué)了大學(xué)低年級(jí)的高等數(shù)學(xué)教材，做了教材上的所有練習(xí)題。這使他1944年進(jìn)入加州理工學(xué)院以后可以免修頭兩年的數(shù)學(xué)，并使他雖因戰(zhàn)時(shí)環(huán)境(第二次世界大戰(zhàn)當(dāng)時(shí)正在進(jìn)行之中，美國也在珍珠港事件后宣布參戰(zhàn))要在軍隊(duì)中充任一個(gè)小職員，占去了部分時(shí)間，仍得以·在1948年按時(shí)完成學(xué)業(yè)。然后到普林斯頓大學(xué)研究生院深造，于1951年取得數(shù)學(xué)博士學(xué)位。165.4廣義表的定義廣義表是線性表的推廣，也稱為列表（lists）記為：LS=(a1,a2,……，an)廣義表名表頭(Head）表尾(Tail)1、定義：①第一個(gè)元素是表頭，而其余元素組成的表稱為表尾；②用小寫字母表示原子類型，用大寫字母表示列表。n是表長在廣義表中約定：討論：廣義表與線性表的區(qū)別和聯(lián)系？廣義表中元素既可以是原子類型，也可以是列表；當(dāng)每個(gè)元素都為原子且類型相同時(shí)，就是線性表。172、特點(diǎn)：有次序性有長度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號(hào)的重?cái)?shù)(遞歸的情況除外)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個(gè)非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。18E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))，E為遞歸表1）A=()2）B=(e)3）C=(a,(b,c,d))4）D=(A,B,C)5）E=(a,E)例1：求下列廣義表的長度。n=0，因?yàn)锳是空表n=1，表中元素e是原子n=2，a為原子，(b,c,d)為子表n=3，3個(gè)元素都是子表n=2，a為原子，E為子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表19ABDCeabcd②A=(a,(b,A))例2：試用圖形表示下列廣義表.（設(shè)代表原子，代表子表）

e①D=(A,B,C)=((),(e),(a,(b,c,d)))Aab①的長度為3，深度為3②的長度為2，深度為∞深度＝括號(hào)的重?cái)?shù)＝結(jié)點(diǎn)的層數(shù)20介紹兩種特殊的基本操作：GetHead(L)——取表頭(可能是原子或列表);GetTail(L)——取表尾(一定是列表)

。廣義表的抽象數(shù)據(jù)類型定義見教材P107-108211.GetTail【(b,k,p,h)】＝

;2.GetHead【((a,b),(c,d))】＝

;3.GetTail【((a,b),(c,d))】＝

;4.GetTail【GetHead【((a,b),(c,d))】】＝

;例：求下列廣義表操作的結(jié)果（嚴(yán)題集5.10②）(k,p,h)（b）(a,b)5.GetTail【（e）】＝

;6.GetHead【(())】＝

.7.GetTail【(())】＝

.()(a,b)()()((c,d))225.5廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素可以是不同結(jié)構(gòu)（原子或列表），難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常用鏈?zhǔn)浇Y(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示。1.原子結(jié)點(diǎn)：表示原子，可設(shè)2個(gè)域或3個(gè)域，依習(xí)慣而選。valuetag=0標(biāo)志域數(shù)值域注意：列表的“元素”還可以是列表，所以結(jié)點(diǎn)可能有兩種形式tpatomtag=０標(biāo)志域值域

表尾指針法2：標(biāo)志域、值域、表尾指針指向下一結(jié)點(diǎn)法1：標(biāo)志域，數(shù)值域23tphptag=1標(biāo)志域表頭指針表尾指針2.表結(jié)點(diǎn)：表示列表，若表不空，則可分解為表頭和表尾，用3個(gè)域表示：標(biāo)志域，表頭指針，表尾指針。①A=()

^10e③C=(a,(b,c,d))1^110a0b0d0c1^1例：②B=(e)A=NULL指向子表指向下一結(jié)點(diǎn)^^124⑤E=(a,E)④D=(A,B,C)＝((),(e),(a,(b,c,d)))

0a^11^10e1^11^110a0b0d0c1^1^1本章結(jié)束（參見教材P109圖）25一、稀疏矩陣的壓縮存儲(chǔ)問題：如果只存儲(chǔ)稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？解決思路：對(duì)每個(gè)非零元素增開若干存儲(chǔ)單元，例如存放其所在的行號(hào)和列號(hào)，便可準(zhǔn)確反映該元素所在位置。實(shí)現(xiàn)方法：將每個(gè)非零元素用一個(gè)三元組（i，j，aij）來表示，則每個(gè)稀疏矩陣可用一個(gè)三元組表來表示。二、稀疏矩