第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表

可表示為：（a1,a2,……,an）線性結(jié)構(gòu)國(guó)際教育學(xué)院第2章線性表可表示為：（a1,a2,……,第5章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)教學(xué)內(nèi)容國(guó)際教育學(xué)院第5章數(shù)組和廣義表5.1數(shù)組的定義教學(xué)內(nèi)容國(guó)際教育學(xué)院1.

掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法2.了解稀疏矩陣的壓縮存儲(chǔ)表示方法的特點(diǎn)3.掌握廣義表的定義、性質(zhì)、表示及其GetHead和GetTail的操作

教學(xué)目標(biāo)國(guó)際教育學(xué)院1.掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法教學(xué)目標(biāo)國(guó)①元素的值并非原子類型，可以再分解，表中元素也是一個(gè)線性表（即廣義的線性表）。②所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型。數(shù)組和廣義表的特點(diǎn)：一種特殊的線性表注意：本章所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。國(guó)際教育學(xué)院①元素的值并非原子類型，可以再分解，表中元素也是一個(gè)線性表5.1數(shù)組的定義

數(shù)組：由一組名字相同、下標(biāo)不同的變量構(gòu)成注意：本章所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組有所區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。答：對(duì)的。因?yàn)椋孩贁?shù)組中各元素具有統(tǒng)一的類型；②數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。討論：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單”，對(duì)嗎？國(guó)際教育學(xué)院5.1數(shù)組的定義數(shù)組：由一組名字相同、下標(biāo)不同的變二維數(shù)66組的特點(diǎn)：一維數(shù)組的特點(diǎn)：1個(gè)下標(biāo)，ai是ai+1的直接前驅(qū)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=國(guó)際教育學(xué)院二維數(shù)66組的特點(diǎn)：一維數(shù)組的特點(diǎn)：1個(gè)下標(biāo)，ai是ai+5.1數(shù)組的定義數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:ADTArray{國(guó)際教育學(xué)院5.1數(shù)組的定義數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:AD基本操作:

(1)InitArray(&A,n,bound1,boundn)//構(gòu)造數(shù)組A(2)DestroyArray(&A)//銷毀數(shù)組A(3)Value(A,&e,index1,…,indexn)//取數(shù)組元素值(4)Assign(A,&e,index1,…,indexn)//給數(shù)組元素賦值}ADTArray國(guó)際教育學(xué)院基本操作:(1)InitArray(&A,n,b5.2數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)問(wè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)先。國(guó)際教育學(xué)院5.2數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)問(wèn)題：計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一維一維數(shù)組352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la國(guó)際教育學(xué)院一維數(shù)組3527491860二維數(shù)組國(guó)際教育學(xué)院二維數(shù)組國(guó)際教育學(xué)院以行序?yàn)橹餍駽,PASCAL5.2數(shù)組的順序表示和實(shí)現(xiàn)國(guó)際教育學(xué)院以行序?yàn)橹餍駽,PASCAL5.2數(shù)組的順序表示和實(shí)現(xiàn)國(guó)以列序?yàn)橹餍騀ORTRAN國(guó)際教育學(xué)院以列序?yàn)橹餍騀ORTRAN國(guó)際教育學(xué)院

a[n][m]設(shè)數(shù)組開(kāi)始存放位置LOC(0,0)=a

LOC(j,k)=a+j*m+k二維數(shù)組的行序優(yōu)先表示國(guó)際教育學(xué)院

a[n][m]設(shè)數(shù)組開(kāi)始存放位置LOC(0,0)①②③三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先的順序存儲(chǔ)

國(guó)際教育學(xué)院①②③三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先的順序存儲(chǔ)國(guó)際教育學(xué)a[m1][m2][m3]

各維元素個(gè)數(shù)為

m1,m2,m3下標(biāo)為i1,i2,i3的數(shù)組元素的存儲(chǔ)位置：

LOC(i1,i2,i3)=a+i1*m2*m3+i2*m3+i3前i1頁(yè)總元素個(gè)數(shù)第i1頁(yè)的前i2行總元素個(gè)數(shù)第i2行前i3列元素個(gè)數(shù)三維數(shù)組國(guó)際教育學(xué)院a[m1][m2][m3]各維元素個(gè)數(shù)為m1,m2

各維元素個(gè)數(shù)為

m1,m2,m3,…,mn下標(biāo)為i1,i2,i3,…,in的數(shù)組元素的存儲(chǔ)位置：

n維數(shù)組國(guó)際教育學(xué)院各維元素個(gè)數(shù)為m1,m2,m3,…,mnn維數(shù)n維數(shù)組國(guó)際教育學(xué)院n維數(shù)組國(guó)際教育學(xué)院設(shè)有一個(gè)二維數(shù)組A[m][n]按行優(yōu)先順序存儲(chǔ)，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。設(shè)數(shù)組元素A[i][j]存放在起始地址為L(zhǎng)oc(i,j)的存儲(chǔ)單元中∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.練習(xí)國(guó)際教育學(xué)院設(shè)有一個(gè)二維數(shù)組A[m][n]按行優(yōu)先順序存儲(chǔ)，假設(shè)A[0]設(shè)有二維數(shù)組A[10,20]，其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按行優(yōu)先順序存儲(chǔ)，則元素A[6,6]的存儲(chǔ)地址為

，按列優(yōu)先順序存儲(chǔ)，元素A[6,6]的存儲(chǔ)地址為

。練習(xí)352232(6*20+6)*2+100=352(6*10+6)*2+100=232國(guó)際教育學(xué)院設(shè)有二維數(shù)組A[10,20]，其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

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

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（盡管是方陣，但公式仍不同）例1〖軟考題〗：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是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=288國(guó)際教育學(xué)院例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

Lo#defineMAX_ARRAY_DIM8//假設(shè)最大維數(shù)為8typedefstruct{ELemType*base;//數(shù)組元素基址intdim;//數(shù)組維數(shù)int*bound;//數(shù)組各維長(zhǎng)度信息保存區(qū)基址int*constants;//數(shù)組映像函數(shù)常量的基址}Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說(shuō)明（有5個(gè)）（請(qǐng)閱讀教材P93-95）N維數(shù)組的順序存儲(chǔ)表示（見(jiàn)教材P93）以銷毀數(shù)組函數(shù)為例國(guó)際教育學(xué)院#defineMAX_ARRAY_DIM8//Status

InitArray(Array&A,intdim,…){//若維數(shù)dim和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A并返回OKif(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!a.bounds)exit(OVERFLOW);

//若各維長(zhǎng)度合法，則存入A.bounds,并求出A的元素總數(shù)elemtotalelemtotal=1;va_start(ap.dim);//ap為va_list類型，是存放變長(zhǎng)參數(shù)表信息的類型數(shù)組的基本操作函數(shù)說(shuō)明（5個(gè)）（見(jiàn)教材P93-95）國(guó)際教育學(xué)院StatusInitArray(Array&A,intfor(i=0;i<dim;++i){A.bounds[i]=va_arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;elemtotal*=A.bounds[i];}va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);A.constants=(int*)malloc(dim*sizeof(int));if(!A.constans)exit(OVERFLOW);A.constans[dim-1]=1;for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}國(guó)際教育學(xué)院for(i=0;i<dim;++i){國(guó)際教育學(xué)院數(shù)組基址指針各維長(zhǎng)度保存區(qū)指針映像函數(shù)Ci保存區(qū)指針StatusDestroyArray(Array&A){//銷毀數(shù)組Aif(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;returnOK;}國(guó)際教育學(xué)院數(shù)組基址指針各維長(zhǎng)度保存區(qū)指針映像函數(shù)Ci保存區(qū)指針StatStatusLocate(ArrayA,va_listap,int&off){

//若ap指示的各下標(biāo)值合法，則求出該元素在A中，相對(duì)地址offoff=0;for(i=0;i<A.dim;++i){ind=va_arg(ap,int);if(ind<0||ind>A.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}國(guó)際教育學(xué)院StatusLocate(ArrayA,va_listStatusValue(ArrayA,ElemType&e,…){

//A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值，若各下標(biāo)不超界，則e賦值為所指定的A的元素值，即將指定元素值讀到e變量中。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;e=*(A.base+off);returnOK;}國(guó)際教育學(xué)院StatusValue(ArrayA,ElemTypeStatusAssign(Array&A,ElemTypee,…){

//A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值，若各下標(biāo)不超界，則e的值賦為所指定的A的元素值，即：將e值寫(xiě)入指定數(shù)組單元。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}國(guó)際教育學(xué)院StatusAssign(Array&A,ElemTyp順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。^……行指針向量a11a12…^a1nam1am2…^amn補(bǔ)充：

鏈?zhǔn)酱鎯?chǔ)方式：用帶行指針向量的單鏈表來(lái)表示。注：數(shù)組的運(yùn)算參見(jiàn)下一節(jié)實(shí)例（稀疏矩陣的轉(zhuǎn)置）（難點(diǎn)是多維數(shù)組與一維數(shù)組的地址映射關(guān)系）國(guó)際教育學(xué)院順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。5.3矩陣的壓縮存儲(chǔ)1.什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2.什么樣的矩陣能夠壓縮？

一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。3.什么叫稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）國(guó)際教育學(xué)院5.3矩陣的壓縮存儲(chǔ)1.什么是壓縮存儲(chǔ)？國(guó)際教育學(xué)院三元組表:（(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)）壓縮存儲(chǔ)原則：每個(gè)非零元的行下標(biāo)、列下標(biāo)和元素值稀疏矩陣國(guó)際教育學(xué)院壓縮存儲(chǔ)原則：每個(gè)非零元的行下標(biāo)、列下標(biāo)和元素值稀疏矩陣國(guó)際#defineMAXSIZE125000//設(shè)非零元素最大個(gè)數(shù)125000typedefstruct{inti;//元素行號(hào)intj;//元素列號(hào)ElemTypee;//元素值}Triple;typedefstruct{

Tripledata[MAXSIZE+1];//三元組表intmu;//矩陣總行數(shù)intnu;//矩陣總列數(shù)inttu;//矩陣中非零元素總個(gè)數(shù)}TsMatrix;//一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義三元組表的順序存儲(chǔ)表示國(guó)際教育學(xué)院#defineMAXSIZE125000//設(shè)非零typedefstruct{Tripledata[MAXSIZE+1];//非零三元組表

intrpos[MAXRC+1];//各行第一個(gè)非零元素的位置表intmu,nu,tu;//矩陣的行數(shù)，列數(shù)和非零元素個(gè)數(shù)}RLSMatrix;行邏輯鏈接的順序存儲(chǔ)表示國(guó)際教育學(xué)院typedefstruct{行邏輯鏈接的順序存儲(chǔ)表示國(guó)際教rowcolvaldownright113418225234^^^^^^^鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十字鏈表）同一列中下一非零元素的指針同一行中下一非零元素的指針國(guó)際教育學(xué)院rowcolvaldownright113418225234十字鏈表的特點(diǎn)：①每行非零元素通過(guò)right域鏈接成一個(gè)線性鏈表②每列非零元素通過(guò)down域鏈接成一個(gè)線性鏈表則每個(gè)非零元素既是行鏈表中的一個(gè)結(jié)點(diǎn)；又是列鏈表中的一個(gè)結(jié)點(diǎn)，即呈十字鏈狀。方法：每個(gè)非0元素占用5個(gè)域用途：方便稀疏矩陣的加減運(yùn)算鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十字鏈表）rowcolvaldownright國(guó)際教育學(xué)院十字鏈表的特點(diǎn)：方法：每個(gè)非0元素占用5個(gè)域鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十5.4廣義表的定義廣義表（列表）：n(0)個(gè)表元素組成的有限序列，記作LS=(a0,a1,a2,…,an-1)

LS是表名，ai是表元素，它可以是表(稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。

n為表的長(zhǎng)度。n=0的廣義表為空表。國(guó)際教育學(xué)院5.4廣義表的定義國(guó)際教育學(xué)院線性表的成分都是結(jié)構(gòu)上不可分的單元素廣義表的成分可以是單元素，也可以是有結(jié)構(gòu)的表線性表是一種特殊的廣義表廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)廣義表與線性表的區(qū)別？國(guó)際教育學(xué)院線性表的成分都是結(jié)構(gòu)上不可分的單元素廣義表與線性表的區(qū)別？國(guó)廣義表的抽象數(shù)據(jù)類型定義（教材P107-108）（1）求表頭GetHead(L)：非空廣義表的第一個(gè)元素，表頭可以是一個(gè)單元素，也可以是一個(gè)子表（2）求表尾GetTail(L)：非空廣義表除去表頭元素以外其它元素所構(gòu)成的表。表尾一定是一個(gè)表國(guó)際教育學(xué)院廣義表的抽象數(shù)據(jù)類型定義（教材P107-108）（1）求表練習(xí)A=()GetHead和GetTail均無(wú)定義A=(a,b)

GetHead(A)=aGetTail(A)=(b)

A=(a)

GetHead(A)=aGetTail(A)=()

A=((a))

GetHead(A)=(a)GetTail(A)=()

GetHead(GetTail(GetHead(GetTail(GetTail(A)))))

A=(a,b,(c,d),(e,(f,g)))

d國(guó)際教育學(xué)院練習(xí)A=()GetHead和GetTail1.GetTail【(b,k,p,h)】＝

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

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

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

;(k,p,h)（b）(a,b)5.GetTail【（e）】＝

;6.GetHead【(())】＝

.7.GetTail【(())】＝

.()(a,b)()()((c,d))練習(xí)國(guó)際教育學(xué)院1.GetTail【(b,k,p,h)】＝有次序性有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享廣義表的特點(diǎn)國(guó)際教育學(xué)院有次序性一個(gè)直接前驅(qū)和一個(gè)直接后繼廣義表的特點(diǎn)國(guó)際教育學(xué)院E=(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)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)))，共享表練習(xí)：求下列廣義表的長(zhǎng)度國(guó)際教育學(xué)院E=(a,E)=(a,(a,E))=(a,(a,(a,……ABDCeabcd②A=(a,(b,A))練習(xí)：試用圖形表示下列廣義表（設(shè)代表原子，代表子表）

e①D=(A,B,C)=((),(e),(a,(b,c,d)))Aab①的長(zhǎng)度為3，深度為3②的長(zhǎng)度為2，深度為∞深度＝括號(hào)的重?cái)?shù)＝結(jié)點(diǎn)的層數(shù)國(guó)際教育學(xué)院ABDCeabcd②A=(a,(b,A))練習(xí)1.掌握：數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中地址計(jì)算方法2.了解：稀疏矩陣的壓縮存儲(chǔ)表示方法的特點(diǎn)3.掌握：廣義表的定義、性質(zhì)、表示及其GetHead和GetTail的操作小結(jié)國(guó)際教育學(xué)院1.掌握：數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中地址計(jì)算方法小結(jié)國(guó)際教第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表

可表示為：（a1,a2,……,an）線性結(jié)構(gòu)國(guó)際教育學(xué)院第2章線性表可表示為：（a1,a2,……,第5章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義5.5廣義表的存儲(chǔ)結(jié)構(gòu)教學(xué)內(nèi)容國(guó)際教育學(xué)院第5章數(shù)組和廣義表5.1數(shù)組的定義教學(xué)內(nèi)容國(guó)際教育學(xué)院1.

掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法2.了解稀疏矩陣的壓縮存儲(chǔ)表示方法的特點(diǎn)3.掌握廣義表的定義、性質(zhì)、表示及其GetHead和GetTail的操作

教學(xué)目標(biāo)國(guó)際教育學(xué)院1.掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法教學(xué)目標(biāo)國(guó)①元素的值并非原子類型，可以再分解，表中元素也是一個(gè)線性表（即廣義的線性表）。②所有數(shù)據(jù)元素仍屬同一數(shù)據(jù)類型。數(shù)組和廣義表的特點(diǎn)：一種特殊的線性表注意：本章所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。國(guó)際教育學(xué)院①元素的值并非原子類型，可以再分解，表中元素也是一個(gè)線性表5.1數(shù)組的定義

數(shù)組：由一組名字相同、下標(biāo)不同的變量構(gòu)成注意：本章所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組有所區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。答：對(duì)的。因?yàn)椋孩贁?shù)組中各元素具有統(tǒng)一的類型；②數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。討論：“數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單”，對(duì)嗎？國(guó)際教育學(xué)院5.1數(shù)組的定義數(shù)組：由一組名字相同、下標(biāo)不同的變二維數(shù)5050組的特點(diǎn)：一維數(shù)組的特點(diǎn)：1個(gè)下標(biāo)，ai是ai+1的直接前驅(qū)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=國(guó)際教育學(xué)院二維數(shù)66組的特點(diǎn)：一維數(shù)組的特點(diǎn)：1個(gè)下標(biāo)，ai是ai+5.1數(shù)組的定義數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:ADTArray{國(guó)際教育學(xué)院5.1數(shù)組的定義數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:AD基本操作:

(1)InitArray(&A,n,bound1,boundn)//構(gòu)造數(shù)組A(2)DestroyArray(&A)//銷毀數(shù)組A(3)Value(A,&e,index1,…,indexn)//取數(shù)組元素值(4)Assign(A,&e,index1,…,indexn)//給數(shù)組元素賦值}ADTArray國(guó)際教育學(xué)院基本操作:(1)InitArray(&A,n,b5.2數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)問(wè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)先。國(guó)際教育學(xué)院5.2數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)問(wèn)題：計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一維一維數(shù)組352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la國(guó)際教育學(xué)院一維數(shù)組3527491860二維數(shù)組國(guó)際教育學(xué)院二維數(shù)組國(guó)際教育學(xué)院以行序?yàn)橹餍駽,PASCAL5.2數(shù)組的順序表示和實(shí)現(xiàn)國(guó)際教育學(xué)院以行序?yàn)橹餍駽,PASCAL5.2數(shù)組的順序表示和實(shí)現(xiàn)國(guó)以列序?yàn)橹餍騀ORTRAN國(guó)際教育學(xué)院以列序?yàn)橹餍騀ORTRAN國(guó)際教育學(xué)院

a[n][m]設(shè)數(shù)組開(kāi)始存放位置LOC(0,0)=a

LOC(j,k)=a+j*m+k二維數(shù)組的行序優(yōu)先表示國(guó)際教育學(xué)院

a[n][m]設(shè)數(shù)組開(kāi)始存放位置LOC(0,0)①②③三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先的順序存儲(chǔ)

國(guó)際教育學(xué)院①②③三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先的順序存儲(chǔ)國(guó)際教育學(xué)a[m1][m2][m3]

各維元素個(gè)數(shù)為

m1,m2,m3下標(biāo)為i1,i2,i3的數(shù)組元素的存儲(chǔ)位置：

LOC(i1,i2,i3)=a+i1*m2*m3+i2*m3+i3前i1頁(yè)總元素個(gè)數(shù)第i1頁(yè)的前i2行總元素個(gè)數(shù)第i2行前i3列元素個(gè)數(shù)三維數(shù)組國(guó)際教育學(xué)院a[m1][m2][m3]各維元素個(gè)數(shù)為m1,m2

各維元素個(gè)數(shù)為

m1,m2,m3,…,mn下標(biāo)為i1,i2,i3,…,in的數(shù)組元素的存儲(chǔ)位置：

n維數(shù)組國(guó)際教育學(xué)院各維元素個(gè)數(shù)為m1,m2,m3,…,mnn維數(shù)n維數(shù)組國(guó)際教育學(xué)院n維數(shù)組國(guó)際教育學(xué)院設(shè)有一個(gè)二維數(shù)組A[m][n]按行優(yōu)先順序存儲(chǔ)，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。設(shè)數(shù)組元素A[i][j]存放在起始地址為L(zhǎng)oc(i,j)的存儲(chǔ)單元中∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.練習(xí)國(guó)際教育學(xué)院設(shè)有一個(gè)二維數(shù)組A[m][n]按行優(yōu)先順序存儲(chǔ)，假設(shè)A[0]設(shè)有二維數(shù)組A[10,20]，其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按行優(yōu)先順序存儲(chǔ)，則元素A[6,6]的存儲(chǔ)地址為

，按列優(yōu)先順序存儲(chǔ)，元素A[6,6]的存儲(chǔ)地址為

。練習(xí)352232(6*20+6)*2+100=352(6*10+6)*2+100=232國(guó)際教育學(xué)院設(shè)有二維數(shù)組A[10,20]，其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

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

Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（盡管是方陣，但公式仍不同）例1〖軟考題〗：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是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=288國(guó)際教育學(xué)院例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

Lo#defineMAX_ARRAY_DIM8//假設(shè)最大維數(shù)為8typedefstruct{ELemType*base;//數(shù)組元素基址intdim;//數(shù)組維數(shù)int*bound;//數(shù)組各維長(zhǎng)度信息保存區(qū)基址int*constants;//數(shù)組映像函數(shù)常量的基址}Array;即Ci信息保存區(qū)數(shù)組的基本操作函數(shù)說(shuō)明（有5個(gè)）（請(qǐng)閱讀教材P93-95）N維數(shù)組的順序存儲(chǔ)表示（見(jiàn)教材P93）以銷毀數(shù)組函數(shù)為例國(guó)際教育學(xué)院#defineMAX_ARRAY_DIM8//Status

InitArray(Array&A,intdim,…){//若維數(shù)dim和各維長(zhǎng)度合法，則構(gòu)造相應(yīng)的數(shù)組A并返回OKif(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!a.bounds)exit(OVERFLOW);

//若各維長(zhǎng)度合法，則存入A.bounds,并求出A的元素總數(shù)elemtotalelemtotal=1;va_start(ap.dim);//ap為va_list類型，是存放變長(zhǎng)參數(shù)表信息的類型數(shù)組的基本操作函數(shù)說(shuō)明（5個(gè)）（見(jiàn)教材P93-95）國(guó)際教育學(xué)院StatusInitArray(Array&A,intfor(i=0;i<dim;++i){A.bounds[i]=va_arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;elemtotal*=A.bounds[i];}va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);A.constants=(int*)malloc(dim*sizeof(int));if(!A.constans)exit(OVERFLOW);A.constans[dim-1]=1;for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}國(guó)際教育學(xué)院for(i=0;i<dim;++i){國(guó)際教育學(xué)院數(shù)組基址指針各維長(zhǎng)度保存區(qū)指針映像函數(shù)Ci保存區(qū)指針StatusDestroyArray(Array&A){//銷毀數(shù)組Aif(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;returnOK;}國(guó)際教育學(xué)院數(shù)組基址指針各維長(zhǎng)度保存區(qū)指針映像函數(shù)Ci保存區(qū)指針StatStatusLocate(ArrayA,va_listap,int&off){

//若ap指示的各下標(biāo)值合法，則求出該元素在A中，相對(duì)地址offoff=0;for(i=0;i<A.dim;++i){ind=va_arg(ap,int);if(ind<0||ind>A.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}國(guó)際教育學(xué)院StatusLocate(ArrayA,va_listStatusValue(ArrayA,ElemType&e,…){

//A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值，若各下標(biāo)不超界，則e賦值為所指定的A的元素值，即將指定元素值讀到e變量中。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;e=*(A.base+off);returnOK;}國(guó)際教育學(xué)院StatusValue(ArrayA,ElemTypeStatusAssign(Array&A,ElemTypee,…){

//A是n維數(shù)組，e為元素變量，隨后是n個(gè)下標(biāo)值，若各下標(biāo)不超界，則e的值賦為所指定的A的元素值，即：將e值寫(xiě)入指定數(shù)組單元。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}國(guó)際教育學(xué)院StatusAssign(Array&A,ElemTyp順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。^……行指針向量a11a12…^a1nam1am2…^amn補(bǔ)充：

鏈?zhǔn)酱鎯?chǔ)方式：用帶行指針向量的單鏈表來(lái)表示。注：數(shù)組的運(yùn)算參見(jiàn)下一節(jié)實(shí)例（稀疏矩陣的轉(zhuǎn)置）（難點(diǎn)是多維數(shù)組與一維數(shù)組的地址映射關(guān)系）國(guó)際教育學(xué)院順序存儲(chǔ)方式：按低地址優(yōu)先（或高地址優(yōu)先）順序存入一維數(shù)組。5.3矩陣的壓縮存儲(chǔ)1.什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2.什么樣的矩陣能夠壓縮？

一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。3.什么叫稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）國(guó)際教育學(xué)院5.3矩陣的壓縮存儲(chǔ)1.什么是壓縮存儲(chǔ)？國(guó)際教育學(xué)院三元組表:（(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)）壓縮存儲(chǔ)原則：每個(gè)非零元的行下標(biāo)、列下標(biāo)和元素值稀疏矩陣國(guó)際教育學(xué)院壓縮存儲(chǔ)原則：每個(gè)非零元的行下標(biāo)、列下標(biāo)和元素值稀疏矩陣國(guó)際#defineMAXSIZE125000//設(shè)非零元素最大個(gè)數(shù)125000typedefstruct{inti;//元素行號(hào)intj;//元素列號(hào)ElemTypee;//元素值}Triple;typedefstruct{

Tripledata[MAXSIZE+1];//三元組表intmu;//矩陣總行數(shù)intnu;//矩陣總列數(shù)inttu;//矩陣中非零元素總個(gè)數(shù)}TsMatrix;//一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義三元組表的順序存儲(chǔ)表示國(guó)際教育學(xué)院#defineMAXSIZE125000//設(shè)非零typedefstruct{Tripledata[MAXSIZE+1];//非零三元組表

intrpos[MAXRC+1];//各行第一個(gè)非零元素的位置表intmu,nu,tu;//矩陣的行數(shù)，列數(shù)和非零元素個(gè)數(shù)}RLSMatrix;行邏輯鏈接的順序存儲(chǔ)表示國(guó)際教育學(xué)院typedefstruct{行邏輯鏈接的順序存儲(chǔ)表示國(guó)際教rowcolvaldownright113418225234^^^^^^^鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十字鏈表）同一列中下一非零元素的指針同一行中下一非零元素的指針國(guó)際教育學(xué)院rowcolvaldownright113418225234十字鏈表的特點(diǎn)：①每行非零元素通過(guò)right域鏈接成一個(gè)線性鏈表②每列非零元素通過(guò)down域鏈接成一個(gè)線性鏈表則每個(gè)非零元素既是行鏈表中的一個(gè)結(jié)點(diǎn)；又是列鏈表中的一個(gè)結(jié)點(diǎn)，即呈十字鏈狀。方法：每個(gè)非0元素占用5個(gè)域用途：方便稀疏矩陣的加減運(yùn)算鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十字鏈表）rowcolvaldownright國(guó)際教育學(xué)院十字鏈表的特點(diǎn)：方法：每個(gè)非0元素占用5個(gè)域鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十5.4廣義表的定義廣義表（列表）：n(0)個(gè)表元