數(shù)據(jù)結(jié)構(gòu)串?dāng)?shù)組和廣義表PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)串?dāng)?shù)組和廣義表數(shù)據(jù)結(jié)構(gòu)串?dāng)?shù)組和廣義表串比較，strcmp(char s1,char s2) 串復(fù)制，strcpy(char to,char from)串連接，strcat(char to,char from) 求串長(zhǎng)，strlen(char s) 調(diào)用標(biāo)準(zhǔn)庫(kù)函數(shù) #include補(bǔ)充：C語(yǔ)言中常用的串運(yùn)算第1頁(yè)/共60頁(yè)第4章串、數(shù)組和廣義表 1. 了解串的存儲(chǔ)方法，理解串的兩種模式匹配算法，重點(diǎn)掌握BF算法。2. 明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，掌握數(shù)組地址計(jì)算方法，了解幾種特殊矩陣的壓縮存儲(chǔ)方法。 3.掌握廣義表的定義、性質(zhì)及其GetHead和GetTail的操作。第

2、2頁(yè)/共60頁(yè)4.1 串串串(String)-(String)-零個(gè)或多個(gè)字符組成的有限序零個(gè)或多個(gè)字符組成的有限序列列21naaas串名串名串值串值串長(zhǎng)串長(zhǎng)n空串空串n=0第3頁(yè)/共60頁(yè)a=a=BEIBEI, , b=b=JINGJING c=c=BEIJINGBEIJING d=d=BEI JINGBEI JING子串子串字符位置字符位置主串主串子串位置子串位置串相等串相等空格串空格串第4頁(yè)/共60頁(yè)0n , 2 , 1,|nietCharacterSaaDii數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象: :數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: :, 2 , 1,| ,111niDaaaaRiiii基本操作基本操作: :(1) S

3、trAssign (&T,chars) /串賦值(2) StrCompare (S,T) /串比較(3) StrLength (S) /求串長(zhǎng)(4) Concat(&T,S1,S2) /串聯(lián) ADT String 串的抽象數(shù)據(jù)類型第5頁(yè)/共60頁(yè) (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,p

4、os,T) /子串插入 (12) StrDelete(&S,pos,len) /子串刪除 (13) DestroyString(&S) /串銷毀ADT String第6頁(yè)/共60頁(yè)p 順序存儲(chǔ)p 鏈?zhǔn)酱鎯?chǔ)串的存儲(chǔ)結(jié)構(gòu)第7頁(yè)/共60頁(yè)typedef struct char *ch; /若串非空,則按串長(zhǎng)分配存儲(chǔ)區(qū), /否則ch為NULL int length; /串長(zhǎng)度HString; 順序存儲(chǔ)表示第8頁(yè)/共60頁(yè)ABCDEFGHI#headABCIhead.鏈?zhǔn)酱鎯?chǔ)表示第9頁(yè)/共60頁(yè)#define CHUNKSIZE 80 /可由用戶定義的塊大小typedef struct Chunk ch

5、ar chCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head,*tail; /串的頭指針和尾指針 int curlen; /串的當(dāng)前長(zhǎng)度LString; 鏈?zhǔn)酱鎯?chǔ)表示第10頁(yè)/共60頁(yè)可將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，以克服其缺點(diǎn)可將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，以克服其缺點(diǎn)實(shí)際分配的存儲(chǔ)位串值所占的存儲(chǔ)位存儲(chǔ)密度ABCDEFGHI#headABCIhead.鏈?zhǔn)酱鎯?chǔ)表示第11頁(yè)/共60頁(yè)算法目的：算法目的：BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法（特點(diǎn)：速度快）算法種類：確定主串中所含子串第一次出現(xiàn)的位置（定位

6、）串的模式匹配算法第12頁(yè)/共60頁(yè) BF算法設(shè)計(jì)思想第13頁(yè)/共60頁(yè)將主串的第pos個(gè)字符和模式的第一個(gè)字符比較， 若相等，繼續(xù)逐個(gè)比較后續(xù)字符； 若不等，從主串的下一字符起，重新與模式的第一個(gè)字符比較。 直到主串的一個(gè)連續(xù)子串字符序列與模式相等 。返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。 否則，匹配失敗，返回值 0BF算法設(shè)計(jì)思想Index(S,T,pos)第14頁(yè)/共60頁(yè)int Index(Sstring S,Sstring T,int pos) i=pos; j=1; while (i=S 0 & j T 0 ) return iT0; else return 0

7、;BF算法描述（算法4.1）第15頁(yè)/共60頁(yè)若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 0 a, i = 0 a+i*la第24頁(yè)/共60頁(yè)mnmmnnnmaaaaaaaaaA212222111211mnmmnnnmaaaaaaaaaA212222111211naaamjjjjj1 ),(21miaaainiii1 ),(21n)m(p ),(21或pA二維數(shù)組第25頁(yè)/共60頁(yè)以行序?yàn)橹餍蛞孕行驗(yàn)橹餍驍?shù)組的順序存儲(chǔ)第26頁(yè)/共60頁(yè)

8、以列序?yàn)橹餍蛞粤行驗(yàn)橹餍虻?7頁(yè)/共60頁(yè)111101121202111101101000mnananamaaamaaamaaaa設(shè)數(shù)組開始存放位置設(shè)數(shù)組開始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k二維數(shù)組的行序優(yōu)先表示第28頁(yè)/共60頁(yè)l1u1l2u2l3u3三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先的順序存儲(chǔ)第29頁(yè)/共60頁(yè)各維元素個(gè)數(shù)為 m1, m2, m3F 下標(biāo)為 i1, i2, i3的數(shù)組元素的存儲(chǔ)位置： LOC ( i1, i2, i3 ) = a + i1* m2 * m3 + i2* m3 + i3前前i1頁(yè)總頁(yè)總元素個(gè)數(shù)元素

9、個(gè)數(shù)第第i1頁(yè)的頁(yè)的前前i2行總行總元素個(gè)數(shù)元素個(gè)數(shù)第第 i2 行前行前 i3 列元素個(gè)數(shù)列元素個(gè)數(shù)三維數(shù)組第30頁(yè)/共60頁(yè)各維元素個(gè)數(shù)為 m1, m2, m3, , mnF 下標(biāo)為 i1, i2, i3, , in 的數(shù)組元素的存儲(chǔ)位置： nnjnjkkjnnnnnnimiimimmmimmmiiiiLOC111143232121 a a),(n維數(shù)組第31頁(yè)/共60頁(yè) L0 , 0 , 0,121niiinjcLOCjjjLOCni1 ,1iiincbcLcn維數(shù)組第32頁(yè)/共60頁(yè)設(shè)有一個(gè)二維數(shù)組Amn按行優(yōu)先順序存儲(chǔ)，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)

10、，每個(gè)元素占一個(gè)空間，問(wèn)A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。設(shè)數(shù)組元素Aij存放在起始地址為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í)第33頁(yè)/共60頁(yè)設(shè)有二維數(shù)組A10,20，其每個(gè)元素占兩個(gè)字節(jié)， A00存儲(chǔ)地址為100，若按行優(yōu)先順序存儲(chǔ)，則元素A6

11、,6的存儲(chǔ)地址為 ，按列優(yōu)先順序存儲(chǔ)，元素A6,6的存儲(chǔ)地址為 。 練習(xí)352232(6*20+6)*2+100 = 352(6*10+6)*2+100 = 232第34頁(yè)/共60頁(yè)1. 什么是壓縮存儲(chǔ)？ 若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2. 什么樣的矩陣能夠壓縮？ 一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。3. 什么叫稀疏矩陣？ 矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）特殊矩陣的壓縮存儲(chǔ)第35頁(yè)/共60頁(yè)對(duì)稱矩陣 對(duì)稱矩陣的特點(diǎn)是aij=ajijiijjjijiik, 12/) 1(12/) 1(， a11 a12 . . a1

12、n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍喊葱行驗(yàn)橹餍颍旱?6頁(yè)/共60頁(yè)下（上）三角矩陣的特點(diǎn)是以主對(duì)角線為界的上（下）半部分是一個(gè)固定的值，下（上）半部分的元素值沒(méi)有任何規(guī)律。三角矩陣 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0Loc(aij)=Loc(a11)+( +(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n

13、(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍喊葱行驗(yàn)橹餍颍旱?7頁(yè)/共60頁(yè)對(duì)角矩陣的特點(diǎn)是所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。比如，一個(gè)3階對(duì)角矩陣：對(duì)角矩陣 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 ann-1 ann . .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍喊葱行驗(yàn)橹餍颍旱?8頁(yè)

14、/共60頁(yè)7600070015000001800000240001400003000000000009120MM M由由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) (5,2,18), (6,1,15), (6,4,-7) 和矩陣維數(shù)（和矩陣維數(shù)（6,76,7）唯一確定）唯一確定稀疏矩陣定義：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣壓縮存儲(chǔ)原則：只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其

15、值第39頁(yè)/共60頁(yè)6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 ma i j v0 1 2 3 4 5 6 7 8行列下標(biāo)非零元值稀疏矩陣的壓縮存儲(chǔ)方法順序存儲(chǔ)結(jié)構(gòu)三元組表#define M 20typedef struct node int i, j; int v; JD;JD maM;7600070015000001800000240001400003000000000009120M三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)ma0.i,ma0.j,ma0.v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)第40頁(yè)/

16、共60頁(yè)求轉(zhuǎn)置矩陣Y問(wèn)題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表Y問(wèn)題分析一般矩陣轉(zhuǎn)置算法：for( col=0; coln; col+ ) for( row=0; rowm; row+ ) ncolrow = mrowcol;T( n ) = O( m n )第41頁(yè)/共60頁(yè)7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1

17、 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8 mb?第42頁(yè)/共60頁(yè)Y 解決思路：只要做到 將矩陣行、列維數(shù)互換 將每個(gè)三元組中的i和j相互調(diào)換 重排三元組次序，使mb中元素以N的行(M的列)為主序按按M的列序轉(zhuǎn)置的列序轉(zhuǎn)置 即按即按mb中三元組次序依次在中三元組次序依次在ma中找到相應(yīng)的三元組進(jìn)中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。為找到行轉(zhuǎn)置。為找到M中每一列所有非零元素，需對(duì)其三元組表中每一列所有非零元素，

18、需對(duì)其三元組表ma從第一行起掃描一遍。由于從第一行起掃描一遍。由于ma中以中以M行序?yàn)橹餍蛐行驗(yàn)橹餍?所以由所以由此得到的恰是此得到的恰是mb中應(yīng)有的順序。中應(yīng)有的順序。Y算法分析：T(n)=O(M的列數(shù)n非零元個(gè)數(shù)t) 若 t 與mn同數(shù)量級(jí)，則)()(2nmOnT第43頁(yè)/共60頁(yè)6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2

19、3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1col=2第44頁(yè)/共60頁(yè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)帶行指針向量的單鏈表表示Y 每行的非零元用一個(gè)單鏈表存放 Y 設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無(wú)非零元，則指針為空Y 表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義typedef struct node int col; int val; struct node *link;JD;typedef struct node *TD;0200000000000210010070003A1 35 73 -11 -12 -24 2需存儲(chǔ)單元個(gè)數(shù)為3t+m第45頁(yè)/共60頁(yè)十字鏈表Y 設(shè)

20、行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元Y 結(jié)點(diǎn)定義tpedef struct node int row,col,val; struct node *down, *right; JD;row col valdownright34008000450003A113418225234第46頁(yè)/共60頁(yè)4.3 廣義表n 廣義表（列表）：廣義表（列表）： n ( 0 )個(gè)表元素組成的有限序列個(gè)表元素組成的有限序列， 記作記作LS = (a0, a1, a2, , an-1) LS是表名，是表名，ai是表元素，它可以是表是表元素，它可以是表 （稱為（稱為子表子表），可），可以是數(shù)據(jù)元素（以是數(shù)

21、據(jù)元素（稱為稱為原子原子）。）。n n為表的長(zhǎng)度。為表的長(zhǎng)度。n = 0 的廣義表為空表。的廣義表為空表。第47頁(yè)/共60頁(yè)線性表的成分都是結(jié)構(gòu)上不可分的單元素線性表的成分都是結(jié)構(gòu)上不可分的單元素廣義表的成分可以是單元素，也可以是有結(jié)構(gòu)的廣義表的成分可以是單元素，也可以是有結(jié)構(gòu)的表表線性表是一種特殊的廣義表線性表是一種特殊的廣義表廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)廣義表與線性表的區(qū)別？第48頁(yè)/共60頁(yè) 廣義表是一個(gè)廣義表是一個(gè)多層次多層次的的線性結(jié)構(gòu)線性結(jié)構(gòu)。例如：例如：有有A、B、C、D、E五個(gè)廣義表的描述如下：五個(gè)廣義表的描述如下： A =

22、() A是一個(gè)空表，它的長(zhǎng)度為零是一個(gè)空表，它的長(zhǎng)度為零 B = (e) 列表列表B只有一個(gè)原子只有一個(gè)原子e，B的長(zhǎng)度為的長(zhǎng)度為1 C = (a，(b，c，d) 列表列表C的長(zhǎng)度為的長(zhǎng)度為2，兩個(gè)元素分別為原子，兩個(gè)元素分別為原子a和子和子表表( b，c，d ) D = (A，B，C) 列表列表D的長(zhǎng)度為的長(zhǎng)度為3，三個(gè)元素都是列表，三個(gè)元素都是列表,顯然顯然,將子表將子表的值代入后，則有的值代入后，則有D =( )，( e )，( a，( b，c，d ) E = (a，E) 這是一個(gè)遞歸的表這是一個(gè)遞歸的表,它的長(zhǎng)度為它的長(zhǎng)度為2，E相當(dāng)于一個(gè)無(wú)限的相當(dāng)于一個(gè)無(wú)限的列表列表E = ( a，

23、( a，( a，.)第49頁(yè)/共60頁(yè)廣義表的結(jié)構(gòu)特點(diǎn)：廣義表的結(jié)構(gòu)特點(diǎn)：1) 廣義表中的數(shù)據(jù)元素有相對(duì)廣義表中的數(shù)據(jù)元素有相對(duì)次序次序。2) 廣義表的廣義表的長(zhǎng)度長(zhǎng)度定義為最外層包含的元素個(gè)數(shù)。定義為最外層包含的元素個(gè)數(shù)。3) 廣義表的廣義表的深度深度定義為所含括弧的重?cái)?shù)。定義為所含括弧的重?cái)?shù)。 注意：注意：“原子原子”的深度為的深度為“0”；“空表空表”的深度為的深度為1。4) 表頭可以是原子或列表；表尾必定是列表。表頭可以是原子或列表；表尾必定是列表。5) 廣義表可以是一個(gè)廣義表可以是一個(gè)遞歸遞歸的表；遞歸表的深度是無(wú)窮值，長(zhǎng)度的表；遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。是有限值。6) 任

24、何一個(gè)非空廣義表任何一個(gè)非空廣義表 LS = ( 1， 2， n ) 均可分解為均可分解為表頭表頭Head( LS ) = 1和和表尾表尾Tail( LS ) = ( 2， n ) 兩部分。兩部分。第50頁(yè)/共60頁(yè)廣義表的基本運(yùn)算（1）求表頭）求表頭GetHead(L)：非空廣義表的第一個(gè)元：非空廣義表的第一個(gè)元素，可以是一個(gè)單元素，也可以是一個(gè)子表素，可以是一個(gè)單元素，也可以是一個(gè)子表（2）求表尾）求表尾GetTail(L)：非空廣義表除去表頭元素：非空廣義表除去表頭元素以外其它元素所構(gòu)成的表。表尾一定是一個(gè)表以外其它元素所構(gòu)成的表。表尾一定是一個(gè)表第51頁(yè)/共60頁(yè)練習(xí)A=( ) GetHead和和GetTail均無(wú)定義均無(wú)定義A=(a,b) GetHead(A)=a GetTail(A)=(b) A=(a) GetHead(A)=a GetTail(A)=( ) A=(a) GetHead(A)=(a) GetTail(A)=( ) GetHead(GetTail(GetHead(GetTai