數(shù)據(jù)結(jié)構(gòu)串?dāng)?shù)組和廣義表課件教學(xué)內(nèi)容

數(shù)據(jù)結(jié)構(gòu)串?dāng)?shù)組和廣義表課件第4章串、數(shù)組和廣義表1.了解串的存儲(chǔ)方法，理解串的兩種模式匹配算法，重點(diǎn)掌握BF算法。2.明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，掌握數(shù)組地址計(jì)算方法，了解幾種特殊矩陣的壓縮存儲(chǔ)方法。3.掌握廣義表的定義、性質(zhì)及其GetHead和GetTail的操作。4.1串串(String)----零個(gè)或多個(gè)字符組成的有限序列串名串值串長(zhǎng)n空串n=0a=‘BEI’,b=‘JING’

c=‘BEIJING’

d=‘BEIJING’子串字符位置主串子串位置串相等空格串?dāng)?shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:基本操作:(1)

StrAssign(&T,chars)//串賦值(2)StrCompare(S,T)//串比較(3)StrLength(S)//求串長(zhǎng)(4)Concat(&T,S1,S2)//串聯(lián)ADTString{串的抽象數(shù)據(jù)類型(5)SubString(&Sub,S,pos,len)//求子串(6)StrCopy(&T,S)//串拷貝(7)StrEmpty(S)//串判空(8)ClearString(&S)//清空串(9)Index(S,T,pos)//子串的位置(10)Replace(&S,T,V)//串替換(11)StrInsert(&S,pos,T)//子串插入(12)StrDelete(&S,pos,len)//子串刪除(13)DestroyString(&S)//串銷毀}ADTString順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)串的存儲(chǔ)結(jié)構(gòu)typedefstruct{char*ch;//若串非空,則按串長(zhǎng)分配存儲(chǔ)區(qū),//否則ch為NULLintlength;//串長(zhǎng)度}HString;

順序存儲(chǔ)表示鏈?zhǔn)酱鎯?chǔ)表示#defineCHUNKSIZE80//可由用戶定義的塊大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的頭指針和尾指針

intcurlen;//串的當(dāng)前長(zhǎng)度}LString;鏈?zhǔn)酱鎯?chǔ)表示可將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，以克服其缺點(diǎn)優(yōu)點(diǎn)：操作方便缺點(diǎn)：存儲(chǔ)密度較低實(shí)際分配的存儲(chǔ)位串值所占的存儲(chǔ)位存儲(chǔ)密度=鏈?zhǔn)酱鎯?chǔ)表示算法目的：BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法（特點(diǎn)：速度快）算法種類：確定主串中所含子串第一次出現(xiàn)的位置（定位）串的模式匹配算法

S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指針回溯BF算法設(shè)計(jì)思想將主串的第pos個(gè)字符和模式的第一個(gè)字符比較，若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若不等，從主串的下一字符起，重新與模式的第一個(gè)字符比較。直到主串的一個(gè)連續(xù)子串字符序列與模式相等。返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。否則，匹配失敗，返回值0BF算法設(shè)計(jì)思想Index(S,T,pos)intIndex(SstringS,SstringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]=T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni－T[0];elsereturn0;}BF算法描述（算法4.1）若n為主串長(zhǎng)度，m為子串長(zhǎng)度，最壞情況是BF算法時(shí)間復(fù)雜度主串前面n-m個(gè)位置都部分匹配到子串的最后一位，即這n-m位各比較了m次最后m位也各比較了1次總次數(shù)為：(n-m)*m+m＝(n-m+1)*m若m<<n，則算法復(fù)雜度O(n*m)例：S=‘0000000001’，T=‘0001’，pos=1利用已經(jīng)部分匹配的結(jié)果而加快模式串的滑動(dòng)速度？且主串S的指針i不必回溯！可提速到O(n+m)！S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)b

abca

bcacbab’T=‘a(chǎn)bca

c’S=‘a(chǎn)b

abcabcacbab’T=‘a(chǎn)bcac’iiikk

a

b

aa

b

ckiiKMP算法設(shè)計(jì)思想（了解）串操作應(yīng)用舉例－－文本編輯文本可被看作一個(gè)字符串，稱為文本串頁(yè)則是文本串的子串行又是頁(yè)的子串。頁(yè)號(hào)起始行號(hào)頁(yè)表…………行號(hào)起始地址長(zhǎng)度行表…………《數(shù)據(jù)結(jié)構(gòu)》所討論的數(shù)組與高級(jí)語(yǔ)言中的數(shù)組區(qū)別：高級(jí)語(yǔ)言中的數(shù)組是順序結(jié)構(gòu)；而本章的數(shù)組既可以是順序的，也可以是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可根據(jù)需要選擇。4.2數(shù)組數(shù)組的抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:ADTArray{基本操作:

(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

其中，A是數(shù)組結(jié)構(gòu)的名稱，整個(gè)數(shù)組元素可以看成是由m個(gè)行向量和n個(gè)列向量組成，元素總數(shù)為m×n。在C語(yǔ)言中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說(shuō):

typedefelemtypearray2[m][n];

等價(jià)于：

typedefelemtypearray1[n];

typedefarray1array2[m];

數(shù)組結(jié)構(gòu)在創(chuàng)建時(shí)就確定了組成該結(jié)構(gòu)的行向量數(shù)目和列向量數(shù)目，因此，在數(shù)組結(jié)構(gòu)中不存在插入、刪除元素的操作。數(shù)組特點(diǎn)數(shù)組結(jié)構(gòu)固定數(shù)據(jù)元素同構(gòu)數(shù)組運(yùn)算給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，修改數(shù)據(jù)元素的值二維數(shù)組結(jié)構(gòu)的基本操作：（1）給定一組下標(biāo)，修改該位置元素的內(nèi)容

Assign(A,item,index1,index2)（2）給定一組下標(biāo)，返回該位置的元素內(nèi)容

Value(A,item,index1,index2)一維數(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二維數(shù)組以行序?yàn)橹餍驍?shù)組的順序存儲(chǔ)以列序?yàn)橹餍?/p>

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

LOC(j,k)=a+j*m+k二維數(shù)組的行序優(yōu)先表示①②③三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先的順序存儲(chǔ)

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ù)組

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

m1,m2,m3,…,mn

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

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

n維數(shù)組n維數(shù)組設(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í)設(shè)有二維數(shù)組A[10,20]，其每個(gè)元素占兩個(gè)字節(jié)，A[0][0]存儲(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=2321.什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2.什么樣的矩陣能夠壓縮？

一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。3.什么叫稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）特殊矩陣的壓縮存儲(chǔ)對(duì)稱矩陣

對(duì)稱矩陣的特點(diǎn)是aij=aji

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍合拢ㄉ希┤蔷仃嚨奶攸c(diǎn)是以主對(duì)角線為界的上（下）半部分是一個(gè)固定的值，下（上）半部分的元素值沒(méi)有任何規(guī)律。三角矩陣

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann……………….0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍簩?duì)角矩陣的特點(diǎn)是所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。比如，一個(gè)3階對(duì)角矩陣：對(duì)角矩陣

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann.

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍篗由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩陣維數(shù)（6,7）唯一確定稀疏矩陣定義：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣壓縮存儲(chǔ)原則：只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值6

7

8

121213931-3361443245218611564-7maijv012345678行列下標(biāo)非零元值稀疏矩陣的壓縮存儲(chǔ)方法順序存儲(chǔ)結(jié)構(gòu)三元組表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)ma[0].i,ma[0].j,ma[0].v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)求轉(zhuǎn)置矩陣問(wèn)題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表問(wèn)題分析一般矩陣轉(zhuǎn)置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)n[col][row]=m[row][col];T(n)=O(mn)6

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?

解決思路：只要做到將矩陣行、列維數(shù)互換將每個(gè)三元組中的i和j相互調(diào)換重排三元組次序，使mb中元素以N的行(M的列)為主序按M的列序轉(zhuǎn)置即按mb中三元組次序依次在ma中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。為找到M中每一列所有非零元素，需對(duì)其三元組表ma從第一行起掃描一遍。由于ma中以M行序?yàn)橹餍?所以由此得到的恰是mb中應(yīng)有的順序。算法分析：T(n)=O(M的列數(shù)n非零元個(gè)數(shù)t)

若t與mn同數(shù)量級(jí)，則6

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)帶行指針向量的單鏈表表示每行的非零元用一個(gè)單鏈表存放設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無(wú)非零元，則指針為空表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存儲(chǔ)單元個(gè)數(shù)為3t+m十字鏈表設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元結(jié)點(diǎn)定義tpedefstructnode{introw,col,val;structnode*down,*right;}JD;rowcolvaldownright113418225234^^^^^^^4.3廣義表

廣義表（列表）：n(0)個(gè)表元素組成的有限序列，記作LS=(a0,a1,a2,…,an-1)

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

n為表的長(zhǎng)度。n=0的廣義表為空表。線性表的成分都是結(jié)構(gòu)上不可分的單元素廣義表的成分可以是單元素，也可以是有結(jié)構(gòu)的表線性表是一種特殊的廣義表廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)廣義表與線性表的區(qū)別？

廣義表是一個(gè)多層次的線性結(jié)構(gòu)。例如：有A、B、C、D、E五個(gè)廣義表的描述如下：

A=()A是一個(gè)空表，它的長(zhǎng)度為零

B=(e)列表B只有一個(gè)原子e，B的長(zhǎng)度為1

C=(a，(b，c，d))列表C的長(zhǎng)度為2，兩個(gè)元素分別為原子a和子表(b，c，d)

D=(A，B，C)列表D的長(zhǎng)度為3，三個(gè)元素都是列表,顯然,將子表的值代入后，則有D=(()，(e)，(a，(b，c，d)))

E=(a，E)這是一個(gè)遞歸的表,它的長(zhǎng)度為2，E相當(dāng)于一個(gè)無(wú)限的列表E=(a，(a，(a，...)))廣義表的結(jié)構(gòu)特點(diǎn)：1)廣義表中的數(shù)據(jù)元素有相對(duì)次序。2)廣義表的長(zhǎng)度定義為最外層包含的元素個(gè)數(shù)。3)廣義表的深度定義為所含括弧的重?cái)?shù)。注意：“原子”的深度為“0”；“空表”的深度為1。4)表頭可以是原子或列表；表尾必定是列表。5)廣義表可以是一個(gè)遞歸的表；遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。6)任何一個(gè)非空廣義表LS=(1，2，…，n)均可分解為表頭Head(LS)=1和表尾Tail(LS)=(2，…，n)兩部分。廣義表的基本運(yùn)算（1）求表頭GetHead(L)：非空廣義表的第一個(gè)元素，可以是一個(gè)單元素，也可以是一個(gè)子表（2）求表尾GetTail(L)：非空廣義表除去表頭元素以外其它元素所構(gòu)成的表。表尾一定是一個(gè)表練習(xí)A=()

GetHead和GetTail均無(wú)定義A=(a,b)

GetHead(A)=aGetTail(