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

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

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

a11a12…a1n

a21a22…a2n

…………

am1am2…amn

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

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

ac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

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

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

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

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

個字節。288例3：〖00年計算機系考研題〗設數組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答：請注意審題！利用列優先通式：答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2887Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是N維數組，其中任一元素的地址該如何計算？其中Cn=L,Ci-1=bi×Ci，1<i≤n一個元素長度數組基址前面若干元素占用的地址字節總數第i維長度與所存元素個數有關的系數，可用遞推法求出教材已給出低維優先的地址計算公式，見P93（5-2）式該式稱為n維數組的映像函數：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//假設最大維數為8

typedef

struct{

ELemType*base;//數組元素基址

intdim;//數組維數

int*bound;//數組各維長度信息保存區基址

int*constants;//數組映像函數常量的基址

}Array;即Ci信息保存區數組的基本操作函數說明（有5個）（請閱讀教材P93-95）N維數組的順序存儲表示（見教材P93）以銷毀數組函數為例91StatusInitArray(Array&A,intdim,…){2//若維數dim和各維長度合法，則構造相應的數組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的元素總數elemtotal8elemtotal=1;9va_start(ap,dim);//ap為va_list類型，是存放變長參數表信息的類型數組的基本操作函數說明（5個）（見教材P93-95）10//P93代碼1-9行用于檢查維數和各維長度是否合法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{//銷毀數組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}數組基址指針各維長度保存區指針映像函數Ci保存區指針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維數組，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維數組，e為元素變量，隨后是n個下標值，若各下標不超界，則e的值賦為所指定的A的元素值，即：將e值寫入指定數組單元。3va_start(ap,e);4if((result=Locate(A,ap,off))<=0)returnresult;5*(A.base+off)=e;6return

OK;7}15LispandJohnMaCarthyLisp–LIStProcessor條件表達式、遞歸函數、廣義表、程序即數據（本身也同所有其他數據一樣用表結構形式表示）、垃圾回收McCarthy-“人工智能之父”。1971年圖靈獎–Lisp,AI,分時概念等麥卡錫是一個天賦很高的人，還在上初中時，他就弄了一份加州理工大學的課程目錄，按目錄自學了大學低年級的高等數學教材，做了教材上的所有練習題。這使他1944年進入加州理工學院以后可以免修頭兩年的數學，并使他雖因戰時環境(第二次世界大戰當時正在進行之中，美國也在珍珠港事件后宣布參戰)要在軍隊中充任一個小職員，占去了部分時間，仍得以·在1948年按時完成學業。然后到普林斯頓大學研究生院深造，于1951年取得數學博士學位。165.4廣義表的定義廣義表是線性表的推廣，也稱為列表（lists）記為：LS=(a1,a2,……，an)廣義表名表頭(Head）表尾(Tail)1、定義：①第一個元素是表頭，而其余元素組成的表稱為表尾；②用小寫字母表示原子類型，用大寫字母表示列表。n是表長在廣義表中約定：討論：廣義表與線性表的區別和聯系？廣義表中元素既可以是原子類型，也可以是列表；當每個元素都為原子且類型相同時，就是線性表。172、特點：有次序性有長度有深度可遞歸可共享一個直接前驅和一個直接后繼＝表中元素個數＝表中括號的重數(遞歸的情況除外)自己可以作為自己的子表可以為其他廣義表所共享特別提示：任何一個非空表，表頭可能是原子，也可能是列表；但表尾一定是列表。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，深度為∞深度＝括號的重數＝結點的層數20介紹兩種特殊的基本操作：GetHead(L)——取表頭(可能是原子或列表);GetTail(L)——取表尾(一定是列表)

。廣義表的抽象數據類型定義見教材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標志域數值域注意：列表的“元素”還可以是列表，所以結點可能有兩種形式tpatomtag=０標志域值域

表尾指針法2：標志域、值域、表尾指針指向下一結點法1：標志域，數值域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一、稀疏矩陣的壓縮存儲問題：如果只存儲稀疏矩陣中的非零元素，那這些元素的位置信息該如何表示？解決思路：對每個非零元素增開若干存儲單元，例如存放其所在的行號和列號，便可準確反映該元素所在位置。實現方法：將每個非零元素用一個三元組（i，j，aij）來表示，則每個稀疏矩陣可用一個三元組表來表示。二、稀疏矩