資源描述：
《串類型的定義串的表示與實(shí)現(xiàn)串的模式匹配算法串操作應(yīng)用舉例ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、串類型的定義串的表示和實(shí)現(xiàn)串的模式匹配算法串操作應(yīng)用舉例第四章串1、了解串的概念；學(xué)習(xí)要點(diǎn)2、熟悉串的基本運(yùn)算的定義及實(shí)現(xiàn)方法；3、掌握基本串匹配算法。在較早的程序設(shè)計(jì)語言中，字符串（簡(jiǎn)稱串）是作為輸入或輸出的常量（是直接量，不參加運(yùn)算）出現(xiàn)，而非數(shù)值處理的對(duì)象基本上是字符串?dāng)?shù)據(jù)。這就要求字符串也能以變量的形式出現(xiàn)，能進(jìn)行一系列字符串操作（運(yùn)算）。目前大多數(shù)程序設(shè)計(jì)語言都支持串這種數(shù)據(jù)類型。1、串2、串長：串中所包含的字符個(gè)數(shù)。3、空串：長度為零的串，它不包含任何字符。記作“?”4、子串：串中任意個(gè)連續(xù)的字符組成的子序列。5、主
2、串：包含子串的串。4.1串類型的定義基本概念：零個(gè)或多個(gè)字符組成的有限序列，即數(shù)據(jù)元素為字符的線性表。一般記為S=‘a(chǎn)1a2...an’，其中，S是串名，單引號(hào)括起的字符序列是串值。7、子串在主串中的位置：子串在主串中第一次出現(xiàn)時(shí)，子串的第一個(gè)字符在主串中的位置。6、字符在串中的位置：字符在序列中的序號(hào)。8、兩個(gè)串相等：兩個(gè)串的長度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。9、空格串：由一個(gè)或多個(gè)空格組成的串，其長度為串中空格字符的個(gè)數(shù)。它與空串?是不同的概念。串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象為字符集。串的
3、基本操作和線性表有很大差別：在線性表的基本操作中，大多以“單個(gè)元素”作為操作對(duì)象；在串的基本操作中，通常以“串的整體”作為操作對(duì)象。ADTString{數(shù)據(jù)對(duì)象：D＝{ai
4、ai∈CharacterSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{
5、ai-1,ai∈D,i=2,...,n}基本操作：……}ADTStringADT串的定義StrAssign(&T,chars)//串賦值初始條件：chars是字符串常量。操作結(jié)果：把chars賦為T的值。StrCopy(&T,S)//串復(fù)制初始條件：串S存在
6、。操作結(jié)果：由串S復(fù)制得串T。DestroyString(&S)//串銷毀初始條件：串S存在。操作結(jié)果：串S被銷毀。StrEmpty(S)//串判空初始條件：串S存在。操作結(jié)果：若S為空串，則返TRUE，否則返回FALSE。StrCompare(S,T)//串比較例如：StrCompare(?data?,?state?)<0StrCompare(?cat?,?case?)>0初始條件：串S和T存在。操作結(jié)果：若S?T，則返回值?0；若S?T，則返回值?0； 若S?T，則返回值?0StrLength(S)//求串長初始條件：串S存
7、在。操作結(jié)果：返回S的元素個(gè)數(shù)， 稱為串的長度。Concat(&T,S1,S2)//串聯(lián)接例如：Concate(T,?man?,?kind?)求得T=?mankind?初始條件：串S1和S2存在。操作結(jié)果：用T返回由S1和S2 聯(lián)接而成的新串。SubString(&Sub,S,pos,len)//求子串初始條件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作結(jié)果：用Sub返回串S的第pos個(gè)字符起長度為len的子串。子串為“串”中的一個(gè)字符子序列。SubString(sub
8、,?commander?,1,9)求得sub=?commander?SubString(sub,?commander?,9,1)求得sub=?r?例如：SubString(sub,?commander?,4,3)求得sub=?man?;SubString(sub,?student?,5,0)得sub=??關(guān)于參數(shù)len（子串長度）的說明：長度為0的子串為“合法”串—空串。事實(shí)上對(duì)任何串S和位置pos都有：SubString(sub,?commander?,4,7)得sub=?mander?SubString(sub,S,pos,
9、0)得sub=??；有時(shí)對(duì)len放寬到len＞StrLength(S)-pos+1，此時(shí)規(guī)定SubString(sub,S,pos,len)的值取S的第pos個(gè)字符到S的最后一個(gè)字符作為子串（長為StrLength(S)-pos+1）。Index(S,T,pos)//(子)串(位置)定位初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作結(jié)果：若主串S中存在和串T值相同 的子串,則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置;否則函數(shù)值為0。假設(shè)S=?abcaabcaaabc?,T=?bca?In
10、dex(S,T,1)=Index(S,T,3)=Index(S,T,8)=“子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序。2;6;0;Replace(&S,T,V)//串替換初始條件：串S,T和V均已存在， 且T是非空串。操作結(jié)果：用V替換主串S中出
