數(shù)據(jù)結(jié)構(gòu)中的串PPT學(xué)習(xí)教案

1、會計學(xué)1數(shù)據(jù)結(jié)構(gòu)中的串?dāng)?shù)據(jù)結(jié)構(gòu)中的串44第1頁/共40頁第2頁/共40頁第3頁/共40頁第4頁/共40頁第5頁/共40頁為了清楚起見我們以后用為了清楚起見我們以后用來表示來表示空串空串第6頁/共40頁more第7頁/共40頁第8頁/共40頁第9頁/共40頁第10頁/共40頁n3 塊鏈存儲表示第11頁/共40頁第12頁/共40頁第13頁/共40頁第14頁/共40頁第15頁/共40頁第16頁/共40頁分配大小等于串S和串T長度之和的存儲空間，然后進(jìn)行串復(fù)制。第17頁/共40頁第18頁/共40頁第19頁/共40頁第20頁/共40頁第21頁/共40頁通常稱為正文模式匹配第22頁/共40頁第23頁/共4

2、0頁我們應(yīng)注意到，算法我們應(yīng)注意到，算法4.6可以實現(xiàn)可以實現(xiàn)從任意位置起的查詢，其方法是從任意位置起的查詢，其方法是起始起始pos=i+Strlength(T)第24頁/共40頁第25頁/共40頁第26頁/共40頁第27頁/共40頁n步改進(jìn)。第28頁/共40頁第29頁/共40頁第30頁/共40頁第31頁/共40頁next(j)=MAX k | T1.k-1=Tj-(k-1).j-1 kj 第32頁/共40頁next(j)=MAX k | T1.k-1=Tj-(k-1).j-1 k b m a, & a , & b ) ; i f a b m ax = a ; e l s e m a x =

3、b ; x = a ; e l s e m a x = b ; ; ; 201201例：有如下源程序清單例：有如下源程序清單main() float a,b,max; scanf(“%f,%f”,&a,&b); if ab max=a; else max=b;存入內(nèi)存后形式如下：存入內(nèi)存后形式如下：起始地址起始地址第36頁/共40頁m am a i i n ( ) n ( ) f f l l o o a t a t a , b ,a , b ,m a x ; m a x ; s c a n f s c a n f ( ( “ % f , % f % f , % f ”, & a , & b )

4、 ; , & a , & b ) ; i f i f a b a b m am ax = a ; x = a ; e l s e e l s e m a x = b ; m a x = b ; ; ; 201201209209226226240240266266280280284284建立線性表：建立線性表：行號行號 開始地址開始地址 長度長度 1 201 7 1 201 7 2 209 16 2 209 16 3 226 23 3 226 23 4 240 14 4 240 14 4 266 13 4 266 13 6 280 4 6 280 4線性表中的元素線性表中的元素第37頁/共40頁

5、如將第二行由如將第二行由 float a,b,max; float a,b,max; 改為改為 float a,b,m; float a,b,m; 或或 float float a,b,maxelem; a,b,maxelem; 新行長度新行長度原行長度：原行長度： 按對照表指出的第二行開始位置，變更相應(yīng)的字符，按對照表指出的第二行開始位置，變更相應(yīng)的字符，并修改相應(yīng)長度并修改相應(yīng)長度, ,新行長度原行長度：新行長度原行長度：重新為該行分配存儲空間重新為該行分配存儲空間, ,即生成一個新的結(jié)點即生成一個新的結(jié)點( (包括該行的行號、開始地址和長度包括該行的行號、開始地址和長度) )刪除原結(jié)點刪

6、除原結(jié)點, , 對照表變?yōu)閷φ毡碜優(yōu)? :行號行號 開始地址開始地址 長度長度 1 201 7 1 201 7 3 226 23 3 226 23 4 240 14 4 240 14 4 266 13 4 266 13 6 280 4 6 280 4 2 284 20 2 284 20行號行號 開始地址開始地址 長度長度 1 201 7 1 201 7 2 284 20 2 284 20 3 226 23 3 226 23 4 240 14 4 240 14 4 266 13 4 266 13 6 280 4 6 280 4即結(jié)點的即結(jié)點的指針鏈保指針鏈保持不變持不變 修改開始地址及長度修改開

7、始地址及長度刪除若干字符刪除若干字符: : 同上同上, ,變更相應(yīng)字節(jié)內(nèi)容和行長度變更相應(yīng)字節(jié)內(nèi)容和行長度插入若干字符插入若干字符: : 分插入后長度是否超長處理分插入后長度是否超長處理插入行插入行: : 在線性表中增加新的結(jié)點在線性表中增加新的結(jié)點 刪除行刪除行: : 在線性表中刪除結(jié)點在線性表中刪除結(jié)點 第38頁/共40頁信息檢索中的詞索引表信息檢索中的詞索引表1. 1. 信息檢索的常見方式信息檢索的常見方式按書名按書名：內(nèi)容相似的書籍書名互不相同內(nèi)容相似的書籍書名互不相同按分類號按分類號: : 從分類號中無法了解圖書的主要內(nèi)容從分類號中無法了解圖書的主要內(nèi)容按作者名按作者名: :2. 2

8、. 信息檢索方式的改進(jìn)信息檢索方式的改進(jìn)例例: : 已知某圖書數(shù)據(jù)庫保存如下圖書目錄已知某圖書數(shù)據(jù)庫保存如下圖書目錄書號書號 書書 名名004 Computer Data Structures004 Computer Data Structures010 Introduction to Data Structures010 Introduction to Data Structures023 Fundamentals of Data Structures023 Fundamentals of Data Structures034 The Design and Analysis of Compu

9、ter 034 The Design and Analysis of Computer AlgorithmsAlgorithms040 Introduction to Numerical Analysis040 Introduction to Numerical Analysis067 Numerical Analysis067 Numerical Analysis關(guān)鍵詞關(guān)鍵詞 書號索引書號索引Algorithms 034Algorithms 034analysis 034,040,067analysis 034,040,067computer 004,034computer 004,034data 004,010,023data 004,010,023design 034design 034fundamentals 023fundament