第5章-數(shù)組和廣義表

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

可表示為：（a1,a2,……,an）線性結(jié)構(gòu)北京林業(yè)大學(xué)信息學(xué)院第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)容北京林業(yè)大學(xué)信息學(xué)院1.

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

教學(xué)目標(biāo)北京林業(yè)大學(xué)信息學(xué)院①元素的值并非原子類型，可以再分解，表中元素也是一個(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ù)需要選擇。北京林業(yè)大學(xué)信息學(xué)院5.1數(shù)組的定義數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:ADTArray{北京林業(yè)大學(xué)信息學(xué)院基本操作:

(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北京林業(yè)大學(xué)信息學(xué)院一維數(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北京林業(yè)大學(xué)信息學(xué)院二維數(shù)組北京林業(yè)大學(xué)信息學(xué)院以行序?yàn)橹餍駽,PASCAL5.2數(shù)組的順序表示和實(shí)現(xiàn)北京林業(yè)大學(xué)信息學(xué)院以列序?yàn)橹餍騀ORTRAN北京林業(yè)大學(xué)信息學(xué)院

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

LOC(j,k)=a+j*m+k二維數(shù)組的行序優(yōu)先表示北京林業(yè)大學(xué)信息學(xué)院①②③三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先的順序存儲(chǔ)

北京林業(yè)大學(xué)信息學(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ù)組北京林業(yè)大學(xué)信息學(xué)院

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

m1,m2,m3,…,mn

下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲(chǔ)位置：

n維數(shù)組北京林業(yè)大學(xué)信息學(xué)院n維數(shù)組北京林業(yè)大學(xué)信息學(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í)北京林業(yè)大學(xué)信息學(xué)院設(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北京林業(yè)大學(xué)信息學(xué)院5.3矩陣的壓縮存儲(chǔ)1.什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2.什么樣的矩陣能夠壓縮？

一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。3.什么叫稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）北京林業(yè)大學(xué)信息學(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)和元素值稀疏矩陣北京林業(yè)大學(xué)信息學(xué)院

#defineMAXSIZE125000//設(shè)非零元素最大個(gè)數(shù)125000

typedef

struct{

inti;//元素行號(hào)

intj;//元素列號(hào)

ElemTypee;//元素值}Triple;typedef

struct{

Tripledata[MAXSIZE+1];//三元組表

int

mu;//矩陣總行數(shù)

int

nu;//矩陣總列數(shù)

int

tu;//矩陣中非零元素總個(gè)數(shù)}TsMatrix;//一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)定義三元組表的順序存儲(chǔ)表示北京林業(yè)大學(xué)信息學(xué)院typedef

struct{Tripledata[MAXSIZE+1];//非零三元組表

intrpos[MAXRC+1];//各行第一個(gè)非零元素的位置表

int

mu,nu,tu;//矩陣的行數(shù)，列數(shù)和非零元素個(gè)數(shù)}RLSMatrix;行邏輯鏈接的順序存儲(chǔ)表示北京林業(yè)大學(xué)信息學(xué)院rowcolvaldownright113418225234^^^^^^^鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（十字鏈表）同一列中下一非零元素的指針同一行中下一非零元素的指針北京林業(yè)大學(xué)信息學(xué)院十字鏈表的特點(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北京林業(yè)大學(xué)信息學(xué)院5.4廣義表的定義廣義表（列表）：n(0)個(gè)表元素組成的有限序列，記作LS=(a0,a1,a2,…,an-1)

LS是表名，ai

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

n為表的長(zhǎng)度。n=0的廣義表為空表。北京林業(yè)大學(xué)信息學(xué)院線性表的成分都是結(jié)構(gòu)上不可分的單元素廣義表的成分可以是單元素，也可以是有結(jié)構(gòu)的表線性表是一種特殊的廣義表廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)廣義表與線性表的區(qū)別？北京林業(yè)大學(xué)信息學(xué)院廣義表的抽象數(shù)據(jù)類型定義（教材P107-108）（1）求表頭GetHead(L)：非空廣義表的第一個(gè)元素，表頭可以是一個(gè)單元素，也可以是一個(gè)子表（2）求表尾GetTail(L)：非空廣義表除去表頭元素以外其它元素所構(gòu)成的表。表尾一定是一個(gè)表北京林業(yè)大學(xué)信息學(xué)院練習(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北京林業(yè)大學(xué)信息學(xué)院1.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í)北京林業(yè)大學(xué)信息學(xué)院有次序性有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼＝表中元素個(gè)數(shù)＝表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享廣義表的特點(diǎn)北京林業(yè)大學(xué)信息學(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)度北京林業(yè)大學(xué)信息學(xué)院ABDCeabcd