串?dāng)?shù)組和廣義表

1、串?dāng)?shù)組和廣義表第1頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 第4章串、數(shù)組和廣義表 4.1 串4.2 數(shù)組4.3 廣義表 教學(xué)內(nèi)容第2頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 1. 掌握串的存儲(chǔ)方法，理解串的兩種模式匹配算法；2. 明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，掌握數(shù)組存儲(chǔ)時(shí)地址計(jì)算方法，了解幾種特殊矩陣的壓縮存儲(chǔ)方法。 教學(xué)目標(biāo)1. 了解串的存儲(chǔ)方法，理解串的兩種模式匹配算法，重點(diǎn)掌握BF算法。2. 明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，掌握數(shù)組地址計(jì)算方法，了解幾種特殊矩陣的壓縮存儲(chǔ)方法。 3.掌握廣義表的

2、定義、性質(zhì)及其GetHead和GetTail的操作。第3頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 4.1 串串(String)-零個(gè)或多個(gè)字符組成的有限序列串名串值串長(zhǎng)n空串n=0第4頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 a=BEI, b=JING c=BEIJING d=BEI JING子串字符位置主串子串位置串相等空格串第5頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:基本操作:(1) StrAssign (&T,chars) /串賦值(2) StrComp

3、are (S,T) /串比較(3) StrLength (S) /求串長(zhǎng)(4) Concat(&T,S1,S2) /串聯(lián) ADT String 串的抽象數(shù)據(jù)類型第6頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 北京林業(yè)大學(xué)信息學(xué)院 (5) SubString(&Sub,S,pos,len) /求子串 (6) StrCopy(&T,S) /串拷貝 (7) StrEmpty(S) /串判空 (8) ClearString (&S) /清空串 (9) Index(S,T,pos) /子串的位置 (11) Replace(&S,T,V) /串替換 (12) StrIn

4、sert(&S,pos,T) /子串插入 (12) StrDelete(&S,pos,len) /子串刪除 (13) DestroyString(&S) /串銷毀ADT String第7頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)串的存儲(chǔ)結(jié)構(gòu)第8頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 typedef struct char *ch; /若串非空,則按串長(zhǎng)分配存儲(chǔ)區(qū), /否則ch為NULL int length; /串長(zhǎng)度HString; 順序存儲(chǔ)表示第9頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，

5、星期日 2022年8月30日 鏈?zhǔn)酱鎯?chǔ)表示第10頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 可將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，以克服其缺點(diǎn)優(yōu)點(diǎn)：操作方便缺點(diǎn)：存儲(chǔ)密度較低實(shí)際分配的存儲(chǔ)位串值所占的存儲(chǔ)位存儲(chǔ)密度=鏈?zhǔn)酱鎯?chǔ)表示第11頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 #define CHUNKSIZE 80 /可由用戶定義的塊大小typedef struct Chunk char chCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head,*tail;

6、 /串的頭指針和尾指針 int curlen; /串的當(dāng)前長(zhǎng)度LString; 鏈?zhǔn)酱鎯?chǔ)表示第12頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 算法目的：BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法（特點(diǎn)：速度快）算法種類：確定主串中所含子串第一次出現(xiàn)的位置（定位）即如何實(shí)現(xiàn)教材P72 Index(S,T,pos)函數(shù)串的模式匹配算法第13頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 S : a b a b c a b c a c b a bT : a b cijS : a b a b c a b c a c b

7、a b T : a b cS : a b a b c a b c a c b a bT : a b ci指針回溯BF算法設(shè)計(jì)思想第14頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 將主串的第pos個(gè)字符和模式的第一個(gè)字符比較， 若相等，繼續(xù)逐個(gè)比較后續(xù)字符； 若不等，從主串的下一字符起，重新與模式的第一個(gè)字符比較。 直到主串的一個(gè)連續(xù)子串字符序列與模式相等 。返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。否則，匹配失敗，返回值 0BF算法設(shè)計(jì)思想Index(S,T,pos)第15頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8

8、月30日 int Index(Sstring S,Sstring T,int pos) i=pos; j=1; while (i=S 0 & j T 0 ) return iT0; else return 0;BF算法描述（算法4.1）第16頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 若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若mn，則算法復(fù)雜度O(n*m)例： S=0000000001，T=0001，p

9、os=1第17頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 利用已經(jīng)部分匹配的結(jié)果而加快模式串的滑動(dòng)速度，且主串S的指針i不必回溯！親！可提速到O(n+m)哦！S=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a ciiikk a b aa b ckiiKMP算法設(shè)計(jì)思想（了解）第18頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日KMP算法的時(shí)間復(fù)雜度可以達(dá)到O(m+n) 當(dāng) Si

10、 Tj 時(shí)，已經(jīng)得到的結(jié)果: Si-j+1.i-1 = T1.j-1 若已知 T1.k-1 = Tj-k+1.j-1 則有 Si-k+1.i-1 = T1.k-1三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法第19頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日定義：模式串的next函數(shù)第20頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i = S0 & j T0)

11、 return i-T0; / 匹配成功 else return 0; / Index_KMP第21頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日這實(shí)際上也是一個(gè)匹配的過(guò)程，不同在于：主串和模式串是同一個(gè)串求next函數(shù)值的過(guò)程是一個(gè) 遞推過(guò)程，分析如下:已知：next1 = 0；假設(shè)：nextj = k；又 Tj = Tk則： nextj+1 = k+1若： Tj Tk則需往前回朔，檢查 Tj = T ？第22頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 void get_next(SString &T, int &next ) / 求模式串T的next函數(shù)值并存入數(shù)組

12、next。 i = 1; next1 = 0; j = 0; while (i T0) if (j = 0 | Ti = Tj) +i; +j; nexti = j; else j = nextj; / get_next第23頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日還有一種特殊情況需要考慮：例如： S = aaabaaabaaabaaabaaab T = aaaab nextj= 01234 nextvalj=00004第24頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日void get_nextval(SString &T, int &nextval) i = 1;

13、 nextval1 = 0; j = 0; while (i 0 a, i = 0 a+i*la第34頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 二維數(shù)組第35頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 以行序?yàn)橹餍駽, PASCAL數(shù)組的順序存儲(chǔ)第36頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 以列序?yàn)橹餍騀ORTRAN第37頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 anm設(shè)數(shù)組開(kāi)始存放位置 LOC( 0, 0 ) = a LOC ( j, k )

14、 = a + j * m + k二維數(shù)組的行序優(yōu)先表示第38頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 設(shè)有二維數(shù)組A10,20，其每個(gè)元素占兩個(gè)字節(jié)， A00存儲(chǔ)地址為100，若按行優(yōu)先順序存儲(chǔ)，則元素A6,6的存儲(chǔ)地址為 ，按列優(yōu)先順序存儲(chǔ)，元素A6,6的存儲(chǔ)地址為 。 課堂任務(wù)（經(jīng)驗(yàn)值200）352232(6*20+6)*2+100=352(6*10+6)*2+100=232第39頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 設(shè)有一個(gè)二維數(shù)組Amn按行優(yōu)先順序存儲(chǔ)，假設(shè)A00存放位置在644(10)，A22存放位置在6

15、76(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.課堂任務(wù)（經(jīng)驗(yàn)值200）第40頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 1.

16、 什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2. 什么樣的矩陣能夠壓縮？ 一些值相同的元素或零元素在矩陣中分布有規(guī)律的特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。3. 什么叫稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）特殊矩陣的壓縮存儲(chǔ)(課堂自學(xué)，完成以下任務(wù)，每任務(wù)200經(jīng)驗(yàn)值)第41頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 4.3 廣義表 廣義表（列表）： n ( 0 )個(gè)表元素組成的有限序列， 記作LS = (a0, a1, a2, , an-1) LS是表名，ai是表元素，它可以

17、是表 (稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。 n為表的長(zhǎng)度。n = 0 的廣義表為空表。第42頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 線性表的成分都是結(jié)構(gòu)上不可分的單元素廣義表的成分可以是單元素，也可以是有結(jié)構(gòu)的表線性表是一種特殊的廣義表廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)廣義表與線性表的區(qū)別？（每答出一條區(qū)別加經(jīng)驗(yàn)值100）第43頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 廣義表的基本運(yùn)算（1）求表頭GetHead(L)：非空廣義表的第一個(gè)元素，可以是一個(gè)單元素，也可以是一個(gè)子表（2）求表尾GetTail(L

18、)：非空廣義表除去表頭元素以外其它元素所構(gòu)成的表。表尾一定是一個(gè)表。第44頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 練習(xí)求表頭表尾（每題100經(jīng)驗(yàn)值）A=( ) GetHead 和 GetTail均無(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(GetTail(GetTail(A) =？A=(a,b,(c,d),(e,(f,g) d第45頁(yè)，

19、共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 有次序性有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼表中元素個(gè)數(shù)表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享廣義表的特點(diǎn)第46頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 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)為子表

20、n=3，3個(gè)元素都是子表n=2，a 為原子，E為子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表練習(xí)：求下列廣義表的長(zhǎng)度（每題經(jīng)驗(yàn)值100）第47頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日 2022年8月30日 1. 了解串的存儲(chǔ)方法，理解串的兩種模式匹配算法，重點(diǎn)掌握BF算法。2. 明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，掌握數(shù)組地址計(jì)算方法，了解幾種特殊矩陣的壓縮存儲(chǔ)方法。 3.掌握廣義表的定義、性質(zhì)及其GetHead和GetTail的操作。小結(jié)第48頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日進(jìn)階任務(wù)（每任務(wù)100經(jīng)驗(yàn)值）（1）串是一種特殊的線

21、性表，其特殊性體現(xiàn)在（ ）。 A可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符 C可以鏈?zhǔn)酱鎯?chǔ) D數(shù)據(jù)元素可以是多個(gè)字符若 （2）串下面關(guān)于串的的敘述中，（ ）是不正確的？ A串是字符的有限序列 B空串是由空格構(gòu)成的串 C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)（3）串“ababaaababaa”的next數(shù)組為（ ）。 A C第49頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日進(jìn)階任務(wù)（每任務(wù)100經(jīng)驗(yàn)值）（4）串“ababaabab”的nextval為（ ）。 A010104101 B010102101 C010100011 D010101011 （5）串的長(zhǎng)度

22、是指（ ）。 A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù) C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù)（6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)數(shù)組A=array1.100,1.100，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC5,5=（ ）。 A808 B818 C1010 D1020第50頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日進(jìn)階任務(wù)（每任務(wù)100經(jīng)驗(yàn)值）（7）設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A5,8的存儲(chǔ)首地址為（ ）。 ABA+141 BBA+180 CBA

23、+222 DBA+225（8）設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。 A13 B33 C18 D40（9）若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aij（ij）的位置k的關(guān)系為（ ）。 Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i第51頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日進(jìn)階任務(wù)（每任務(wù)100經(jīng)驗(yàn)值）（10）AN，N是

24、對(duì)稱矩陣，將下面三角（包括對(duì)角線）以行序存儲(chǔ)到一維數(shù)組TN(N+1)/2中，則對(duì)任一上三角元素aij對(duì)應(yīng)Tk的下標(biāo)k是（ ）。 Ai(i-1)/2+j Bj(j-1)/2+i Ci(j-i)/2+1 Dj(i-1)/2+1（11）設(shè)二維數(shù)組A1. m，1. n（即m行n列）按行存儲(chǔ)在數(shù)組B1. m*n中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為（ ）。 A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1（12）數(shù)組A0.4,-1.-3,5.7中含有元素的個(gè)數(shù)（ ）。 A55 B45 C36 D16第52頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日

25、進(jìn)階任務(wù)（每任務(wù)100經(jīng)驗(yàn)值）（13）廣義表A=(a,b,(c,d),(e,(f,g)，則Head(Tail(Head(Tail(Tail(A)的值為（ ）。 A(g) B(d) Cc Dd（14）廣義表(a,b,c,d)的表頭是（ ），表尾是（ ）。 Aa B( ) C(a,b,c,d) D(b,c,d)（15）設(shè)廣義表L=(a,b,c)，則L的長(zhǎng)度和深度分別為（ ）。 A1和1 B1和3 C1和2 D2和3 第53頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日進(jìn)階任務(wù)（每任務(wù)200經(jīng)驗(yàn)值）（1）已知模式串t=abcaabbabcab寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和ne

26、xtval函數(shù)值。模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5第54頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日進(jìn)階任務(wù)（每任務(wù)200經(jīng)驗(yàn)值）（3）數(shù)組A中，每個(gè)元素Ai,j的長(zhǎng)度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9，列下標(biāo)從1到11，從首地址S開(kāi)始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第4列所有元素至少需多少單元？ 數(shù)組按行存放時(shí)，元素A7,4的起始地址是多少？ 數(shù)組按列存放時(shí)，元素A4,7的起始地址是多少？ 每個(gè)元素32個(gè)二進(jìn)制位，主存字長(zhǎng)16位，故每個(gè)元素占2個(gè)字長(zhǎng)，行下標(biāo)可平移至1到11(共11行，11列)。（1）11*11*2=242 （2）11*2=22 （3）s+(8*11+3)*2=s+182 （4）s+(6*11+5)*2=s+142第55頁(yè)，共59頁(yè)，2022年，5月20日，5點(diǎn)56分，星期日進(jìn)階任務(wù)（每任務(wù)200經(jīng)驗(yàn)值）（4）請(qǐng)將香蕉b