數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表1第五章數(shù)組和廣義表5.1數(shù)組和線性表的關(guān)系以及數(shù)組的運(yùn)算5.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

5.3矩陣的壓縮存儲(chǔ)5.4廣義表的定義和表示方法5.5廣義表的存儲(chǔ)結(jié)構(gòu)5.6廣義表的遞歸算法本章學(xué)習(xí)要點(diǎn)、習(xí)題與上機(jī)作業(yè)

本質(zhì)上是非線性結(jié)構(gòu)。擴(kuò)展的線性表：表中的數(shù)據(jù)元素本身也是一個(gè)數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表25.1數(shù)組和線性表的關(guān)系以及數(shù)組的運(yùn)算任何數(shù)組A都可以看作一個(gè)線性表

A=(a1,a2,…,ai,…an)二維數(shù)組mn時(shí)，

ai是數(shù)組中第i行所有元素，0im-1，表中每一個(gè)元素是一個(gè)一維數(shù)組；三維數(shù)組時(shí)，表中每一個(gè)元素是一個(gè)二維數(shù)組；n維數(shù)組時(shí)，表中每一個(gè)元素是一個(gè)(n-1)維數(shù)組()()()()()()()()()=Amna00a01

…a0,n-1a10a11

…a1,n-1…………am-1,0am-1,1

…am-1,n-1數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表3數(shù)組與線性表之間的關(guān)系線性表的擴(kuò)展，其數(shù)據(jù)元素本身也是線性表數(shù)組的特點(diǎn)數(shù)組中各元素都具有統(tǒng)一的類型可以認(rèn)為，d維數(shù)組的非邊界元素具有d個(gè)直接前趨和d個(gè)直接后繼數(shù)組維數(shù)確定后，數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系不再發(fā)生改變，適合于順序存儲(chǔ)每組有定義的下標(biāo)都存在一個(gè)與其相對(duì)應(yīng)的值在數(shù)組上的基本操作給定一組下標(biāo)，取得相應(yīng)的數(shù)據(jù)元素值給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素值數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表4數(shù)組的基本操作定義(1)構(gòu)造n維數(shù)組InitArray(&A,n,bound1,…,boundn)(2)銷毀數(shù)組ADestroyArray(&A)(3)取得指定下標(biāo)的數(shù)組元素值

Value(A,&e,index1,…,indexn)(4)為指定下標(biāo)的數(shù)組元素重新賦值

Assign(&A,e,index1,…,indexn)數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表55.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)一維數(shù)組b基地址L個(gè)單元a0a1aiLOC[i]=LOC[0]+iL=b+i

L=c0+c1

ic1=Lc0=b=LOC[0]an-1ElemTypea[n]；數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表6二維數(shù)組

a00a01a02...a0,n-1a10a11a12...a1,n-1

::::

am-1,0am-1,1am-1,2...am-1,n-1a=mna00a0,,n-1a10aijam-1,n-1ba1LOC[i,j]=LOC[0,0]+(in+j)L=c0+c1i+c2jc2=Lc1=nc2=b2c2c0=b=LOC[0,0]注：Pascal、C語言以行序?yàn)橹餍?/p>

Fortran語言以列序?yàn)橹餍駿lemTypea[m][n];“行序?yàn)橹餍颉奔础暗拖聵?biāo)優(yōu)先”“列序?yàn)橹餍颉奔础案呦聵?biāo)優(yōu)先”aij數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表7n維數(shù)組

LOC[j1,j2,...,jn]=c0+c1j1+c2j2+...+cnjn=c0+ciji

cn=L;ci-1=cibi(1<in)c0=b=LOC[0,0,...,0]

數(shù)組是一種隨機(jī)存取結(jié)構(gòu):對(duì)任一元素定位時(shí)間相等.思考：

ElemTypeA[3..7,0..9,1..6,5..12]

設(shè)每數(shù)組元素占用8個(gè)存儲(chǔ)單元，起始地址為1000,求按低下標(biāo)優(yōu)先（類似行優(yōu)先）順序存儲(chǔ)時(shí)，

LOC[6,1,4,7]=？ElemTypea[b1][b2]...[bn];數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表8

參考解答

維數(shù):b1=5,b2=10,b3=6,b4=8[法1]LOC[6,1,4,7]=1000+[1068(6-3)+68(1-0)+8(4-1)+(7-5)]8=13112[法2]相當(dāng)于A[0..4,0..9,0..5,0..7],求LOC[3,1,3,2]LOC[3,1,3,2]=LOC[0,0,0,0]+c1j1+c2j2+c3j3+c4j4=1000+c1j1+c2j2+c3j3+82=1000+c1j1+c2j2+883

+82=1000+c1j1+6461

+883

+82=1000+384103+6461

+883

+82=13112數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表95.3矩陣的壓縮存儲(chǔ)

目的是節(jié)省空間。5.3.1對(duì)稱矩陣[特點(diǎn)]在nn的矩陣a中，滿足如下性質(zhì)：aij=aji(1i,jn)[存儲(chǔ)方法]只存儲(chǔ)下(或者上)三角(包括主對(duì)角線)的數(shù)據(jù)元素。共占用n(n+1)/2個(gè)元素空間:sa[0..n(n+1)/2-1]。k=i(i-1)/2+j-1當(dāng)ijj(j-1)/2+i-1當(dāng)i<ja11a21a22a31aij(aji)annk0123n(n+1)/2-1saaijaji數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表105.3.2三角矩陣[特點(diǎn)]

對(duì)角線以下(或者以上)的數(shù)據(jù)元素(不包括對(duì)角線)全部為常數(shù)c。[存儲(chǔ)方法]

重復(fù)元素c共享一個(gè)元素存儲(chǔ)空間，共占用n(n+1)/2+1個(gè)元素空間:sa[0..n(n+1)/2]。sa[0]=C

上三角矩陣下三角矩陣

k=(i-1)(2n-i+2)/2+j-i+1ijk=i(i-1)/2+jij0i>j

0i<jCk0n(n+1)/2CC上三角矩陣下三角矩陣ijij數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表115.3.3帶狀矩陣（對(duì)角矩陣）[特點(diǎn)]

在nn的方陣中，非零元素集中在主對(duì)角線及其兩側(cè)共L(奇數(shù))條對(duì)角線的帶狀區(qū)域內(nèi)—L對(duì)角矩陣。[存儲(chǔ)方法]

只存儲(chǔ)帶狀區(qū)內(nèi)的元素。1）以對(duì)角線的順序存儲(chǔ),共n*L個(gè)元素。

123456182300024203003577680409691550061426000283五對(duì)角矩陣//3385/2061282794347618/5962//s[-2..2;1..6]-2-1012123456i1=i-jj1=j|i-j|(L-1)/2k0n*L-1sa數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表122）只存儲(chǔ)帶狀區(qū)內(nèi)的元素。除首行和末行，按每行L個(gè)元素，共

(n-2)L+(L+1)=(n-1)L+1個(gè)元素。sa[0..(n-1)L]

存儲(chǔ)地址計(jì)算：k=(i-1)L+(j-i)1i,jn|i-j|(L-1)/2

823000

420300

577680096915006142000283823/420357768969156142/283sak012345678910111213141516171819202122232425數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表135.3.4隨機(jī)稀疏矩陣[特點(diǎn)]

大多數(shù)元素為零。[常用存儲(chǔ)方法]

記錄每一非零元素(i,j,aij)—節(jié)省空間，但喪失隨機(jī)存取功能順序存儲(chǔ)：三元組表鏈?zhǔn)酱鎯?chǔ)：十字(正交)鏈表

1500220-150113000000-60000000091000000028000=t/(mn)0.05數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表145.3.4.1三元組表[類型定義]#defineMAXSIZE1000

//設(shè)定非零元素最大值typedefstruct{ inti,j; ElemTypee;}Triple;typedefstruct{ Tripledata[MAXSIZE+1];

//三元組表，data[0]未用

intmu,nu,tu;

//行數(shù)、列數(shù)、非零元個(gè)數(shù)}TSMatrix;ije111514221665191632812345678m數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表15[應(yīng)用例]求轉(zhuǎn)置矩陣

ije1111521422316-15422225233634-67519186328a.data轉(zhuǎn)置

ije11115215913222243235362864122743-6861-15b.data數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表16算法1

{O(nt)}voidTransMatrix(TSMatrix&b,TSMatrixa){b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if(b.tu){q=1;

//指示b中存放數(shù)據(jù)的位置，初值為1for(col=1;col<=a.nu;col++)//對(duì)a的每一列

for(p=1;p<=a.tu;p++)//對(duì)a的每個(gè)三元組檢查

if(a.data[p].j==col){//找列號(hào)為col的三元組

b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].e=a.data[p].e;q++;//修正q值

}}}//TransMatrix數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表17

算法2快速轉(zhuǎn)置法

{O(n+t)}引入兩個(gè)輔助向量：num[1:a.nu]：a中每列的非零元素個(gè)數(shù)cpot[1:a.nu]：a中每列的第一個(gè)非零元素在b中的位置a中的列號(hào)

colnum[col]cpot[col]121213324426508618cpot[1]=1cpot[col]=cpot[col-1]+num[col-1](2coln)ije1111521422316-15422225233634-67519186328a轉(zhuǎn)置ije11115215913222243235362864122743-6861-15b數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表18

StatueFastTransMatrix(TSMatrix&b,TSMatrixa){b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if(b.tu){{ for(col=1;col<=a.nu;++col)//num清零

num[col]=0; for(t=1;t<=a.tu;++t)//對(duì)a.tu個(gè)非零元素按列號(hào)計(jì)數(shù)

++num[a.data[t].j];

cpot[1]=1;//生成cpot for(col=2;col<=a.nu;++col)cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.tu;++p){//對(duì)a.tu個(gè)非零元素轉(zhuǎn)置

col=a.data[p].j;q=cpot[col];b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].e=a.data[p].e;++cpot[col];}}returnOK;}//FastTransMatrix數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表195.3.4.2行邏輯鏈接的表便于隨機(jī)存取任意一行的非零元素。typedefstruct{Tripledata[MAXSIZE+1];intrpos[MAXRC+1];intmu,nu,tu;}RLSMatrix;ije111514221665191328

14607812345612345678M.rposM.dataRLSMatrixM;這種方式可以便于某些運(yùn)算，如：稀疏矩陣相乘等。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表205.3.4.3十字（正交）鏈表［特點(diǎn)］在行、列兩個(gè)方向上，將非零元素鏈接在一起?？朔M表在矩陣的非零元素位置或個(gè)數(shù)經(jīng)常變動(dòng)時(shí)的使用不便。［類型定義］ijedownrighttypedefstructOLNode{inti,j;ElemTypee;structOLNode*right,*down;}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;intmu,nu,tu;}CrossList;數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表2147^^0080-5004007162-5^^14^48^^M.cheadM.rheadCrossListM;數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表22[算法示例]從終端接收信息建立稀疏矩陣的十字鏈表算法思想：1）賦值矩陣的行數(shù)mu、列數(shù)nu和非零元素個(gè)數(shù)tu；2）申請(qǐng)行、列頭指針向量，將各行、列鏈表置為空鏈表；3）讀入一個(gè)非零元素的行號(hào)i、列號(hào)j、值e3.1）建立該元素的結(jié)點(diǎn)，賦值其三元組

3.2）尋找該結(jié)點(diǎn)在行表中的插入位置并插入

3.3）尋找該結(jié)點(diǎn)在列表中的插入位置并插入

3.4）存在下一個(gè)非零元素，轉(zhuǎn)3；否則，結(jié)束。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表235.4廣義表（列表）的定義和表示方法概念

廣義表是由零個(gè)或多個(gè)原子或者子表組成的有限序列?？梢杂涀鳎篖S=(d1,d2,…,dn

)

原子：邏輯上不能再分解的元素。子表：作為廣義表中元素的廣義表。與線性表的關(guān)系廣義表中的元素全部為原子時(shí)即為線性表。線性表是廣義表的特例，廣義表是線性表的推廣。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表24廣義表的表示方法和相關(guān)術(shù)語

表長(zhǎng)表深表頭表尾

A=()01--B=(a,A)=(a,())22a(())C=((a,b),c,d)32(a,b)(c,d)D=(a,D)=(a,(a,(a,…)))2a(D)表的長(zhǎng)度表中的元素（第一層）個(gè)數(shù)。表的深度表中元素的最深嵌套層數(shù)。表頭表中的第一個(gè)元素。表尾除第一個(gè)元素外，剩余元素構(gòu)成的廣義表。

非空廣義表的表尾必定仍為廣義表。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表25廣義表的圖形表達(dá)方法

A=(a,b)abAB=(A,c)BD=(a,D)aDL=(A,B)LABabcAabc表原子含有遞歸含有共享數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表26規(guī)定所有表都有名字時(shí)，廣義表的表示方法例A(a,b)B(A(a,b),c)L(A(a,b),B(A(a,b),c))D(a,D(a,D(…)))廣義表結(jié)構(gòu)的分類純表：與樹型結(jié)構(gòu)對(duì)應(yīng)的廣義表。再入表：允許結(jié)點(diǎn)共享的廣義表。遞歸表：允許遞歸的廣義表。遞歸表再入表純表線性表廣義表的應(yīng)用如：程序的語句結(jié)構(gòu);m元多項(xiàng)式的表示P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z+2yz+15=(x10y3+2x6y3)z2+(3x5y2+2y)z+15P=z((A,2),(B,1),(15,0))A=y((C,3))C=x((1,10),(2,6))B=y((D,2),(2,1))D=x((3,5))數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表27基本操作結(jié)構(gòu)的創(chuàng)建和銷毀

InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);

狀態(tài)函數(shù)

GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);

插入和刪除操作

InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);

遍歷

Traverse_GL(L,Visit());數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表28抽象數(shù)據(jù)類型定義ADTGList{數(shù)據(jù)對(duì)象：D={ei|i=1,2,…,n;n0;eiAtomSet或eiGList,AtomSet為某個(gè)數(shù)據(jù)對(duì)象}

數(shù)據(jù)關(guān)系：R={<ei-1,ei>|ei-1,eiD,2in}

基本操作：

InitGList(&L);

操作結(jié)果：創(chuàng)建空的廣義表L。CreateGList(&L,S);

初始條件：S是廣義表的書寫形式串。

操作結(jié)果：由S創(chuàng)建廣義表L?！瓆ADTGList

數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表295.5廣義表的存儲(chǔ)結(jié)構(gòu)5.5.1方法１—頭尾鏈表形式

[類型定義]tag=0atom原子結(jié)點(diǎn)hp:指示表頭的指針tp:指示表尾的指針typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子；LIST==1：子表typedefstructGLNode{ ElemTagtag; union{ AtomTypeatom; struct{ structGLNode*hp,*tp; }ptr; }}*GList1;tag=1hptp表結(jié)點(diǎn)ptrGL=(a1,a2,……,an)head(GL)=a1Tail(GL)=(a2,……,an)數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表30[示例]A=()A=NULLBC11^^0a111^0c0d11^0a0b11^D0aB=(a,A)C=((a,b),c,d)D=(a,D)(A)(D)(a,b)(c,d)(d)(b)GList1A,B,C,D數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表315.5.2方法2—擴(kuò)展的線性鏈表形式

[類型定義]tag=1hptp表結(jié)點(diǎn)tag=0atomtp原子結(jié)點(diǎn)hp:指向表頭的指針tp:指向同一層的下一個(gè)結(jié)點(diǎn)(a1,a2,……,an)typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子；LIST==1：子表typedefstructGLNode{ ElemTagtag; union{ AtomTypeatom; struct{ structGLNode*hp; } } structGLNode*tp;}*GList2;數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表32[示例]A1^^1^0aA=()1^^BB=(a,A)C=((a,b),c,d)C1^10c0d^0a0b^1^DD=(a,D)0a1^aDaA(a,b)cdabGList2A,B,C,D數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表5.6廣義表的遞歸算法

廣義表的特點(diǎn)：定義是遞歸的。示例約定：非遞歸表且無共享子表。[示例1]

計(jì)算廣義表的深度方法一

分析表中各元素（子表）LS=(a1,a2,……,an)求深度的遞歸函數(shù)

基本項(xiàng)：DEPTH（LS）=1當(dāng)LS為空表時(shí)

DEPTH（LS）=0當(dāng)LS為原子時(shí)歸納項(xiàng)：DEPTH（LS）=1+max{DEPTH(ai)}n1算法描述1in數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表34intGListDepth(GList1L){if(!L)return1;//空表

if(L->tag==ATOM)return0;//單原子

for(max=0,pp=L;pp;pp=pp->ptr.tp){dep=GListDepth(pp->ptr.hp);if(dep>max)max=dep;}returnmax+1;}//GListDepthtag=1hptp表結(jié)點(diǎn)ptrLS=(a1,a2,……,an)

表頭：a1表尾：(a2,……,an)數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表35

方法二

分析表頭和表尾求深度的遞歸函數(shù)

1當(dāng)LS為空表

depth(LS)=0當(dāng)LS為單原子

max{depth(head(LS))+1,depth(tail(LS))}其它情況算法描述

intGListDepth(GList1L){if(!L)return1;//空表

if(L->tag==ATOM)return0;//單原子

dep1=GListDepth(L->ptr.hp)+1;dep2=GListDepth(L->ptr.tp);if(dep1>dep2)returndep1;elsereturndep2;}//GListDepth數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表36[示例2]

復(fù)制廣義表復(fù)制操作的遞歸定義

基本項(xiàng)：InitGList(NEWLS)

當(dāng)LS為空表時(shí)；