資源描述：
《《串類型的定義》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第四章串4.1串類型的定義4.2串的表示和實現4.2.1定長順序存儲表示4.2.2堆分配存儲表示4.2.3串的塊鏈存儲表示4.3串的模式匹配算法4.4串操作應用舉例—文本編輯10/6/20211第四章串4.1串類型的定義基本概念串(String)是由零個或多個字符組成的有限序列。一般記作S=‘a1a2a3…an’，其中S是串名，單引號括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數字或其它字符；串中所包含的字符個數稱為該串的長度。空串(EmptyString)：長度為零的串。它不包含任何字符?？崭翊?BlankString)：由一個或多個空格組成的串。注意：空串和空格串的不同。10
2、/6/20212第四章串基本概念（續(xù)）子串：串中任意個連續(xù)字符組成的子序列。主串：包含子串的串。通常將子串在主串中首次出現時的該子串的首字符對應的主串中的序號，定義為子串在主串中的序號（或位置）。例如，設A和B分別為A=“Thisisastring”B=“is”則B是A的子串，A為主串。B在A中出現了兩次，其中首次出現所對應的主串位置是3。因此，稱B在A中的序號（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。10/6/20213第四章串基本概念（續(xù)）通常在程序中使用的串可分為兩種：串變量和串常量。串常量和整常數、實常數一樣，在程序中只能被引用但不能不能改變其值，即只能讀不
3、能寫。通常串常量是由直接量來表示的，例如語句Error(“overflow”)中“overflow”是直接量。但有的語言允許對串常量命名，以使程序易讀、易寫。如C++中，可定義constcharpath[]=“dir/bin/appl”;這里path是一個串常量，對它只能讀不能寫。串變量和其它類型的變量一樣，其取值是可以改變的。10/6/20214第四章串串的抽象數據類型定義串的抽象數據類型定義見教材P71串的基本操作(13個)：StrAssign,Strcopy,StrEmpty,StrCompare,StrLength,ClearString,Concat,SubString,Inde
4、x,Replace,StrInsert,StrDelete,DestroyString許多高級語言均提供了串基本操作相應的運算或標準庫函數來實現。下面僅介紹幾種在C語言中常用的串運算，其它的串操作見教材及參考書。10/6/20215第四章串串變量及基本操作：chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;求串長(length)intstrlen(chars);//求串的長度例如：cout<5、copy(charto,charfrom);該函數將串from復制到串to中，并且返回一個指向串to的開始處的指針。例如：strcopy(s3,s1);//s3=“dirtreeformat”(3)聯接(concatenation)charconcat(charto,charfrom)該函數將串from復制到串to的末尾，并且返回一個指向串to的開始處的指針。10/6/20217第四章串基本操作（續(xù)）例如：concat(s3,”/”)concat(s3,s2);//s3=“dirtreeformat/file.mem”(4)串比較（compare)intstrcompare(chars1,
6、chars2);該函數比較串s1和串s2的大小，當返回值小于0，等于0或大于0時分別表示s1s2例如：result=strcompare(“baker”,”Baker”)result>0result=strcompare(“12”,”12”);result=0result=strcompare(“Joe”,”Joseph”);result<010/6/20218第四章串基本操作（續(xù)）（5）字符定位(index)charstrchr(chars,charc);該函數是找c在字符串中第一次出現的位置，若找到則返回該位置，否則返回NULL。例如：p=strchr(s2,
7、”.”);p指向“file”之后的位置if(p)strcpy(p,”.cpp”);s2=“file.cpp”最小操作子集：串賦值StrAssign、串比較Strcompare、求串長StrLength、串聯接concat和求子串SubString。串的其余操作可由這些基本操作組合而成。10/6/20219第四章串4.2串的表示和實現因為串是特殊的線性表，故其存儲結構與線性表的存儲結構類似。只不過由于組成串的結點是單個字符
