數(shù)據(jù)結構 5數(shù)組和廣義表A

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

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

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

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

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

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

ac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

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

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

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

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

個字節(jié)。288例3：〖00年計算機系考研題〗設數(shù)組a[1..60,1..70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

。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答：請注意審題！利用列優(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ù)組，其中任一元素的地址該如何計算？其中Cn=L,Ci-1=bi×Ci，1<i≤n一個元素長度數(shù)組基址前面若干元素占用的地址字節(jié)總數(shù)第i維長度與所存元素個數(shù)有關的系數(shù)，可用遞推法求出教材已給出低維優(yōu)先的地址計算公式，見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ù)為8

typedef

struct{

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

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

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

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

}Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說明（有5個）（請閱讀教材P93-95）N維數(shù)組的順序存儲表示（見教材P93）以銷毀數(shù)組函數(shù)為例91StatusInitArray(Array&A,intdim,…){2//若維數(shù)dim和各維長度合法，則構造相應的數(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個）（見教材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指示的各下標值合法，則求出該元素在A中，相對地址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個下標值，若各下標不超界，則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個下標值，若各下標不超界，則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條件表達式、遞歸函數(shù)、廣義表、程序即數(shù)據(jù)（本身也同所有其他數(shù)據(jù)一樣用表結構形式表示）、垃圾回收McCarthy-“人工智能之父”。1971年圖靈獎–Lisp,AI,分時概念等麥卡錫是一個天賦很高的人，還在上初中時，他就弄了一份加州理工大學的課程目錄，按目錄自學了大學低年級的高等數(shù)學教材，做了教材上的所有練習題。這使他1944年進入加州理工學院以后可以免修頭兩年的數(shù)學，并使他雖因戰(zhàn)時環(huán)境(第二次世界大戰(zhàn)當時正在進行之中，美國也在珍珠港事件后宣布參戰(zhàn))要在軍隊中充任一個小職員，占去了部分時間，仍得以·在1948年按時完成學業(yè)。然后到普林斯頓大學研究生院深造，于1951年取得數(shù)學博士學位。165.4廣義表的定義廣義表是線性表的推廣，也稱為列表（lists）記為：LS=(a1,a2,……，an)廣義表名表頭(Head）表尾(Tail)1、定義：①第一個元素是表頭，而其余元素組成的表稱為表尾；②用小寫字母表示原子類型，用大寫字母表示列表。n是表長在廣義表中約定：討論：廣義表與線性表的區(qū)別和聯(lián)系？廣義表中元素既可以是原子類型，也可以是列表；當每個元素都為原子且類型相同時，就是線性表。172、特點：有次序性有長度有深度可遞歸可共享一個直接前驅和一個直接后繼＝表中元素個數(shù)＝表中括號的重數(shù)(遞歸的情況除外)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。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，因為A是空表n=1，表中元素e是原子n=2，a為原子，(b,c,d)為子表n=3，3個元素都是子表n=2，a為原子，E為子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表19ABDCeabcd②A=(a,(b,A))例2：試用圖形表示下列廣義表.（設代表原子，代表子表）

e①D=(A,B,C)=((),(e),(a,(b,c,d)))Aab①的長度為3，深度為3②的長度為2，深度為∞深度＝括號的重數(shù)＝結點的層數(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))】】＝

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

;6.GetHead【(())】＝

.7.GetTail【(())】＝

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

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

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

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