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

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)中的串中的串第一頁，共40頁。44第1頁/共40頁第二頁，共40頁。第2頁/共40頁第三頁，共40頁。第3頁/共40頁第四頁，共40頁。第4頁/共40頁第五頁，共40頁。第5頁/共40頁第六頁，共40頁。為了清楚起見我們以后用為了清楚起見我們以后用來表示來表示空串空串第6頁/共40頁第七頁，共40頁。more第7頁/共40頁第八頁，共40頁。第8頁/共40頁第九頁，共40頁。第9頁/共40頁第十頁，共40頁。第10頁/共40頁第十一頁，共40頁。n3 塊鏈存儲表示第11頁/共40頁第十二頁，共40頁。第12頁/共40頁第十三頁，共40頁。第13頁/

2、共40頁第十四頁，共40頁。第14頁/共40頁第十五頁，共40頁。第15頁/共40頁第十六頁，共40頁。第16頁/共40頁第十七頁，共40頁。分配大小等于串S和串T長度之和的存儲空間，然后(rnhu)進(jìn)行串復(fù)制。第17頁/共40頁第十八頁，共40頁。第18頁/共40頁第十九頁，共40頁。第19頁/共40頁第二十頁，共40頁。第20頁/共40頁第二十一頁，共40頁。第21頁/共40頁第二十二頁，共40頁。軟件中，都提供“查找”功能，這種操作就是為串定位的工作，通常稱為正文模式匹配第22頁/共40頁第二十三頁，共40頁。第23頁/共40頁第二十四頁，共40頁。我們應(yīng)注意到，算法我們應(yīng)注意到，算法4

3、.6可以實(shí)現(xiàn)可以實(shí)現(xiàn)從任意位置起的查詢，其方法是從任意位置起的查詢，其方法是起始起始pos=i+Strlength(T)第24頁/共40頁第二十五頁，共40頁。n指針回退nnif ( j T0 ) return i-T0;nelse return 0;n / Index第25頁/共40頁第二十六頁，共40頁。nreturn 0;n / Index第26頁/共40頁第二十七頁，共40頁。第27頁/共40頁第二十八頁，共40頁。n利用這一特征，算法可以進(jìn)一步改進(jìn)。第28頁/共40頁第二十九頁，共40頁。第29頁/共40頁第三十頁，共40頁。第30頁/共40頁第三十一頁，共40頁。第31頁/共40頁

4、第三十二頁，共40頁。next(j)=MAX k | T1.k-1=Tj-(k-1).j-1 kj 第32頁/共40頁第三十三頁，共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 = b ; x = a ; e l s e m a x = b ; ; ; 201201例：有如下例：有如下(rxi)(rxi)源程序清單源程序清單main() float a,b,max; scanf(“%f,%f”,&a,&b); if a

5、b max=a; else max=b;存入存入(cn r)(cn r)內(nèi)存后形式如下：內(nèi)存后形式如下：起始地址起始地址第36頁/共40頁第三十七頁，共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 ) ; , & a , & b ) ; i f i f a b a b m am ax = a ; x = a ; e l s e e l s

6、e m a x = b ; m a x = b ; ; ; 201201209209226226240240266266280280284284建立建立(jinl)(jinl)線線性表：性表：行號行號 開始地址開始地址(dzh) (dzh) 長度長度 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線性表中的元素線性表中的元素(yun s)(yun s)第37頁/共40頁第三十八頁，共40頁。如將第二行由如將第二行由 float a,b,

7、max; float a,b,max; 改為改為(i wi) float a,b,m; (i wi) float a,b,m; 或或 float float a,b,maxelem; a,b,maxelem; 新行長度新行長度(chngd)(chngd)原行長度原行長度(chngd)(chngd)：按對照表指出按對照表指出(zh ch)(zh ch)的第二行開始位置，變更相應(yīng)的的第二行開始位置，變更相應(yīng)的字符，字符，并修改相應(yīng)長度并修改相應(yīng)長度, ,新行長度原行長度：新行長度原行長度：重新為該行分配存儲空間重新為該行分配存儲空間, ,即生成一個(gè)新的結(jié)點(diǎn)即生成一個(gè)新的結(jié)點(diǎn)( (包括該行的行號、開

8、始地址和長度包括該行的行號、開始地址和長度) )刪除原結(jié)點(diǎn)刪除原結(jié)點(diǎn), ,對照表變?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é)點(diǎn)的即結(jié)

9、點(diǎn)的指針鏈保指針鏈保持不變持不變 修改開始地址及長度修改開始地址及長度刪除若干字符刪除若干字符: : 同上同上, ,變更相應(yīng)字節(jié)內(nèi)容和行長度變更相應(yīng)字節(jié)內(nèi)容和行長度插入若干字符插入若干字符: : 分插入后長度是否超長處理分插入后長度是否超長處理插入行插入行: : 在線性表中增加新的結(jié)點(diǎn)在線性表中增加新的結(jié)點(diǎn) 刪除行刪除行: : 在線性表中刪除結(jié)點(diǎn)在線性表中刪除結(jié)點(diǎn) 第38頁/共40頁第三十九頁，共40頁。信息檢索中的詞索引信息檢索中的詞索引(suyn)(suyn)表表1. 1. 信息檢索的常見信息檢索的常見(chn (chn jin)jin)方式方式按書名按書名(sh mn)(sh mn)：內(nèi)

10、容相似的書籍書名互不相同內(nèi)容相似的書籍書名互不相同按分類號按分類號: :從分類號中無法了解圖書的主要內(nèi)容從分類號中無法了解圖書的主要內(nèi)容按作者名按作者名: :2. 2. 信息檢索方式的改進(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 Dat

11、a Structures023 Fundamentals of Data Structures034 The Design and Analysis of Computer Algorithms034 The Design and Analysis of Computer Algorithms040 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 034f