數(shù)據(jù)結(jié)構(gòu)的第四講.ppt

第四講 字符串、 String類和 StringBuilder類,引言,字符串對大多數(shù)計算機(jī)程序而言是很普遍的。 像文字處理軟件和網(wǎng)頁應(yīng)用程序這些程序類型都廣泛采用了字符串。 這使得處理這類應(yīng)用程序的程序員在字符串處理的效率問題上需要花費(fèi)額外的心思。 本講主要介紹 C#語言處理字符串的方法，分析如何使用 String類，如何使用 StringBuilder類。,2,主要內(nèi)容,3.1 串類型的定義 3.2 串的物理結(jié)構(gòu) 3.3 串的算法 3.4 STRING類的應(yīng)用 3.5 STRINGBUILDER類 3.6 STRING類和STRINGBUILDER類性能比較,3.1 串類型的定義,串的定義,串是字符線性的一個有限序列。記作： A=“a1a2.an“ 其中： A是串名， 引號括起來的部分為串的值， ai(1in) 為任一字符，它稱為串的元素， n為串的長度，且n0 。,5,串的一些概念,若n=0，則此串稱為空串，記作：A=“”。 若A=“ ”，則稱為空白串，其元素為空格符，常用表示。 串的長度一般應(yīng)有一定的限制。 （如不超過 255 ）,6,串的一些概念,串中任意連續(xù)的若干字符組成的子序列稱為該串的子串。 包含子串的串又稱為該子串的主串。 子串在主串中第一次出現(xiàn)的第一個字符的位置稱為子串在主串中的位置。,7,串的抽象數(shù)據(jù)類型定義,ADT String 數(shù)據(jù)對象： D=ai|aiCharacterSet,i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1=|ai-1, aiD,i=2,.,n 基本操作： StrAssign( 若ST,則返回值0。,8,串的抽象數(shù)據(jù)類型定義,StrLength(S) 初始條件：串S存在。 操作結(jié)果：返回值S的元素個數(shù)，稱為串的長度。 Concat（&T，S1，S2） 初始條件：串S1和S2存在。 操作結(jié)果：用T返回S1和S2聯(lián)接成的新串。 SubString(&Sub,S,pos,len) 初始條件：串S存在，1posStrLength(S) 且0 len StrLength(S)-pos+1 。 操作結(jié)果：用Sub返回串S的第pos個字符起長度為 len的子串。 ADT String,9,串的運(yùn)算,對于串的運(yùn)算來說，一般都是對多個元素構(gòu)成的串操作，當(dāng)然也有對一個元素操作的退化情況。 求串長 len(s) 功能：求串 s 中字符的個數(shù)。 如：s=“program” 則：len(s)=7,10,串的運(yùn)算,聯(lián)接串concat(s,t) 功能：將串 t 聯(lián)接到串 s 的未尾形成新串 s。 如：s=“re”, t=“store” 則：concat(s,t) 后得到 s=“restore” 求子串substr(s,i,j,t) 功能：從串 s 中的第 i 個字符開始，連續(xù)取出 j 個字符（元素），構(gòu)成一個新串 t。 如：s=“store” 則：substr(s,2,3,t) 后得到 t=“tor”,11,串的運(yùn)算,置換子串replace(s,i,j,t) 功能：將串 s 從第 i 個字符開始的連續(xù) j 個字 符（元素）構(gòu)成的串取出，換成另一 個串 t。 如：s=“store”,t=“patu” 則：replace(s,2,3,t) 后得到 s=“spatue” 可以看出，被置換串與置換串長度不一定一致,12,串的運(yùn)算,插入子串insert(s,i,t) 功能：在串 s 中的第 i 個字符之前，插入子串 t。 如：s=“store”,t=“patu” 則：insert(s,3,t) 后得到 s=“stpatuore” 刪除子串delete(s,i,j) 功能：刪除串 s 中第 i 個字符開始的連續(xù) j 個字 符（元素）構(gòu)成的串。 如：s=“store” 則：delete(s,2,3) 后得到 s=“se”,13,串的運(yùn)算,復(fù)制串a(chǎn)ssign(s,t) 功能：將串 t 復(fù)制給串 s 。 如：t=“store” 則：assign(s,t) 后得到 s=“store”,14,串,既然串的邏輯結(jié)構(gòu)與線性表一致，那么它的物理結(jié)構(gòu)就可以沿用線性表的物理結(jié)構(gòu)，即可以用順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)來表示，當(dāng)然串還有其自身的特性，所以又有與線性表不同的物理結(jié)構(gòu) 等量分塊結(jié)構(gòu)。,15,3.2 串的物理結(jié)構(gòu),順序結(jié)構(gòu),在順序存貯結(jié)構(gòu)中，一個串分配一塊連續(xù)的存貯區(qū)。 其特點是： 、對一個串的操作運(yùn)算比較靈活，串與串之間是相互獨立的； 、每個串所分配的空間大小不太好掌握，太大造成浪費(fèi)，太小造成串存貯不下； 、一篇文章的多個串存貯區(qū)域分散，不易進(jìn)行統(tǒng)一操作運(yùn)算。,17,鏈?zhǔn)浇Y(jié)構(gòu),在鏈?zhǔn)浇Y(jié)構(gòu)中，每個串中的元素為一個基本單位。 其特點是： 1、不需考慮串需要的存貯空間； 2、對串的操作運(yùn)算比較靈活； 3、串占用的存貯空間太大； 4、串的元素存貯區(qū)域分散，不易統(tǒng)一操作。,18,等量分塊結(jié)構(gòu),這種結(jié)構(gòu)兼有順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)的特點，是它們的折中方案。 一、等量分塊的存貯結(jié)構(gòu),19,其中每個塊的大小一樣，一個塊可存放六個字符，最后兩個域分別為標(biāo)志域表示該等量塊的結(jié)束，鏈域指向該塊字符的后續(xù)字符塊。 在一塊中，若字符未占滿，則填上空白符。,等量分塊結(jié)構(gòu),二、等量分塊的特點 在每一塊中字符是連續(xù)存貯的，在塊與塊之間，字符是鏈?zhǔn)酱尜A的，所以它有以下特點： 、查詢串中子串比較方便 對于查詢?nèi)粢阎哟鬃址奈恢?，則可根據(jù)位置計算它出所在塊，便可查詢到此子串了。,20,等量分塊結(jié)構(gòu),二、等量分塊的特點 2、刪除運(yùn)算容易實現(xiàn) 若刪除整塊，則只需改變塊與塊之間的鏈指針即可。若刪除非整塊，則可將其中需刪除的部分字符賦予。 如：在串 S=“abcdefghijklmnopq“ 中刪除 “efghijklm“,21,a b c d,等量分塊結(jié)構(gòu),22,二、等量分塊的特點 、插入運(yùn)算比較簡單 若插入點在塊之間，則只需改變鏈指針。若插入點在塊中，則先將含插入點的塊，從插入點開始分成兩塊，然后再用塊間插入方法。 如：在串 S=“abcdefghij“ 的 “e“ 之前插入串 “l(fā)mnop“,等量分塊結(jié)構(gòu),23,二、等量分塊的特點 、插入運(yùn)算比較簡單 如：在串 S=“abcdefghij“ 的 “e“ 之前插入串 “l(fā)mnop“,e f, ,等量分塊結(jié)構(gòu),三、等量分塊的結(jié)構(gòu)定義 typedef struct node char s6; char d; struct node *link; CAKE;,24,串和線性表,25,串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。,串的基本操作和線性表有很大差別。 在線性表的基本操作中，大多以“單個元素”作為操作對象； 在串的基本操作中，通常以“串的整體”作為操作對象。,3.3 串的算法,順序結(jié)構(gòu)的算法,27,一、求串長 Len(s) /* 求串s中除結(jié)束符外的字符個數(shù) */ char s ; int i=0; while (s i != 0) ;,+,-,return( i );,順序結(jié)構(gòu)的算法,28,二、聯(lián)接串 void Concat(s,t) /* 將t連接到s之后 */ char s,t; int n,m,i; n=Len(s); m=Len(t); for(i=0; im; i+) sn+i=ti; sn+m=0; ,順序結(jié)構(gòu)的算法,29,三、求子串 void Substr(s,i,j,t) /* 從s的第i個字符（下標(biāo)為i-1）開始*/ char s ,t ; /* 取j個字符，構(gòu)成的新串送t中 */ int i,j; /* 若無 j 個字符則只取到串尾 */ int k; for(k=0; k+),(kj),tk=si-1+k; tk=0; ,順序結(jié)構(gòu)的算法,30,四、置換子串 假設(shè)：從 s 串的第 i 個字符(下標(biāo)為i-1)開始，取出j個字符，用 t 串置換這 j 個字符。若 t 串長為 m，則有如下幾種情況： 1、mj（新串在原位放不下）,需要從下標(biāo)為 n-1 開始到 i+j-1 的字符向后移動 m-j 位,m-j,順序結(jié)構(gòu)的算法,31,四、置換子串 假設(shè)：從 s 串的第 i 個字符(下標(biāo)為i-1)開始，取出j個字符，用 t 串置換這 j 個字符。若 t 串長為 m，則有如下幾種情況：,2、mj（新串在原位放下后還有空位）,則需要下標(biāo)從 i+j-1 開始到 n-1 的字符向前移動 j-m 位,j-m,順序結(jié)構(gòu)的算法,32,四、置換子串 假設(shè)：從 s 串的第 i 個字符(下標(biāo)為i-1)開始，取出j個字符，用 t 串置換這 j 個字符。若 t 串長為 m，則有如下幾種情況：,3、m=j 新串正好放下，字符不需移位。 然后將 t 串的字符依次復(fù)制到 s 串的預(yù)定字符位上。,順序結(jié)構(gòu)的算法,33,四、置換子串,void Replace(s,i,j,t) /* 從s的第i個字符（下標(biāo)為i-1）開始 */ char s ,t ; /* 取j個字符，置換成t串 */ int i,j; int n,m,k; n=Len(s); m=Len(t); if (i+jj) /* 若t串長大于j */ for(k=n-1; k=i+j-1; k-) sk+m-j=sk; /* 從i+j-1開始依次后移m-j位 */,順序結(jié)構(gòu)的算法,34,四、置換子串,else if (mj) /* 若t串長小于j */ for(k=i+j-1; kn; k+) sk+m-j=sk; /* 從i+j-1開始依次前移j-m位 */ for(k=0; km; k+) sk+i-1=tk; /* 置換進(jìn)新串 */ if (i+jn) sn+m-j=0; else si+m-1=0; ,順序結(jié)構(gòu)的算法,35,五、插入子串 假設(shè)：將串t插入到串s的第i個字符(下標(biāo)為i-1)之前，若串t的長度為m，則需要從n-1到i-1的字符向后移動m位。即：,n+m-1,i+m-1,這時，sn-1移至下標(biāo)為n+m-1，si-1移至下標(biāo)為i+m-1。,順序結(jié)構(gòu)的算法,36,五、插入子串 假設(shè)：將串t插入到串s的第i個字符(下標(biāo)為i-1)之前，若串t的長度為m，則需要從n-1到i-1的字符向后移動m位。即：,n+m-1,si-1 sn-1,t0 ,i+m-1,這時，sn-1移至下標(biāo)為n+m-1，si-1移至下標(biāo)為i+m-1。,然后，將t0復(fù)制到i-1， tm-1移至下標(biāo)為i+m-2。,順序結(jié)構(gòu)的算法,37,五、插入子串,void Insert(s,i,t) /* 將串t插入到串s的第i個字符前 */ char s ,t ; int i; int n,m,k; n=Len(s); m=Len(t); for(k=n-1; k=i-1; k-) sk+m=sk; /* 從i-1開始以后的字符后移m位 */ for(k=0; km; k+) sk+i-1=tk; sn+m=0; ,順序結(jié)構(gòu)的算法,38,六、刪除子串 假設(shè)：刪除串s中從第i個字符（下標(biāo)為 i-1 ）開始的連續(xù)j個字符。即：,i+j-1,n-j-1,i-1,這時，si+j-1移至下標(biāo)為i-1，sn-1移至下標(biāo)為n-j-1。,順序結(jié)構(gòu)的算法,39,六、刪除子串 假設(shè)：刪除串s中從第i個字符（下標(biāo)為 i-1 ）開始的連續(xù)j個字符。即：,i+j-1,n-j-1,i-1,這時，si+j-1移至下標(biāo)為i-1，sn-1移至下標(biāo)為n-j-1。,si+j-1 sn-1,順序結(jié)構(gòu)的算法,40,六、刪除子串,void Delete(s,i,j) /* 刪除串s中從第i個字符(下標(biāo)為 i-1) */ char s ; int i,j; /* 開始的連續(xù)j個字符 */ int n,k; /* 若無 j 個字符則只刪到串尾 */ n=Len(s); if (ni+j) si-1=0; /* 若刪除到串尾，則設(shè)定串未符 */ else for(k=i+j-1; kn; k+) sk-j=sk; /* 從i+j-1開始的字符前移j位 */ sn-j=0; ,鏈?zhǔn)浇Y(jié)構(gòu)的算法,41,一、串結(jié)點結(jié)構(gòu) typedef struct point char ch; struct point *link; CNODE;,鏈?zhǔn)浇Y(jié)構(gòu)的算法,42,二、求串長 Len(s) CNODE *s; /* s為表頭指針 */ CNODE *p; int n=0; p=s; while (p!=NULL) /* p順著鏈表掃描至表末尾 */ n+; /* n計結(jié)點個數(shù) */ p=p-link; return(n); ,鏈?zhǔn)浇Y(jié)構(gòu)的算法,43,三、聯(lián)接串 void Concat(s,t) /* 將串 t 連接到串 s 之后 */ CNODE *s,*t; CNODE *r; r=s; while (r-link!=NULL) /* 尋找 s 串尾 */ r=r-link; r-link=t; /* 串尾結(jié)點的指針域指向t */ ,3.4 STRING類的應(yīng)用,44,STRING類的應(yīng)用,在 C#語言中把字符序列用一對閉合的雙引號包圍起來就可以產(chǎn)生文字串。 “David Ruff” “the quick brown fox jumped over the lazy dog” “123-45-6789” “”,45,C#語言中的字符串,C#語言中的字符串具有精神分裂的天性即字符串既是本地類型又是類的對象。 實際上更準(zhǔn)確的說法應(yīng)該是可以把字符串作為本地數(shù)據(jù)值來使用，但是事實上每個產(chǎn)生的字符串都是 String類的一個對象。,46,創(chuàng)建 String對象,創(chuàng)建 String的方式如下所示： string name = “Jennifer Ingram”; 也可以在兩條分離的語句中先聲明變量然后再進(jìn)行賦值。 聲明的語法使得名字看上去就像一個規(guī)則的變量，但是實際上它是 String對象的一個實例。,47,創(chuàng)建 String對象,C#語言的字符串還允許在字符串中放置轉(zhuǎn)義字符。 轉(zhuǎn)義字符用來把諸如換行符和制表符這類版式字符放置在字符串內(nèi)。 轉(zhuǎn)義字符由一個反斜杠（ ）開始，后邊跟著單獨一個表示版式的字母。 例如， n說明換行，而 t則表示一個制表符。 string name = “Mike McMillannInstructor, CIStRoom 306”;,48,常用 String類的方法,雖然對字符串可以執(zhí)行許多操作，但是一個小的操作集合卻起著支配作用。 三個最重要的操作分別是： 1.找到字符串的子串。 2.確定字符串的長度。 3.確定字符在字符串中的位置。,49,字符串分離成單詞的算法,找到字符串中第一個空格的位置。 抽取第一個單詞。 從空格后邊開始到字符串的末尾構(gòu)建一個新的字符串。 尋找新字符串中的第一個空格。 如果沒有其他空格，那么抽取的單詞就從當(dāng)前位置到字符串的末尾。 否則循環(huán)返回第2步重復(fù)操作。,50,注意,String類已經(jīng)有一個“把字符串分離成部分”的方法（ Split方法），和一個“可以取走一個數(shù)據(jù)集合并且把幾部分組合成一個字符串”的方法（ Join方法）。,Split方法和 Join方法,把字符串分解成獨立的數(shù)據(jù)段是一種非常常見的功能，許多程序都把數(shù)據(jù)存儲在一些字符串格式類型里。 為了簡化字符串的分解以及再次合并在一起的過程， String類提供了兩種可用的方法： 用于分解字符串的 Split方法 用來把存儲在數(shù)組中的數(shù)據(jù)制作成字符串的 Join方法,Split方法,Split方法取得一條字符串后，就會把它分解成數(shù)據(jù)成分塊，然后把這些塊放入String數(shù)組內(nèi)。 Split方法的實現(xiàn)集中在用來確定分解字符串位置的分離字符身上。 在前例中， SplitWords函數(shù)始終采用空格作為分隔符。 而在使用 Split方法時則可以指定要尋找的分隔符的內(nèi)容。 分隔符就是此方法的第一個參數(shù) 該參數(shù)必須以 char型數(shù)組的形式出現(xiàn) 而數(shù)組的第一個元素將是用作分隔符的字符,Split方法,許多應(yīng)用程序是通過寫出用逗號分隔的數(shù)據(jù)串的方式來輸出數(shù)據(jù)的。這被稱為是逗號分隔值串，或簡稱為 CSVs。 逗號分隔串就如同下列這樣的形式： “Mike, McMillan, 3000W. Scenic, North Little Rock, Ar, 72118” 此串內(nèi)的每一個邏輯數(shù)據(jù)塊都是用逗號進(jìn)行分隔的。,Join方法,Join方法從數(shù)組變?yōu)樽址?此方法回取走兩個參數(shù)： 原始數(shù)組 用來分隔元素的字符 字符串是由跟著分隔符元素的數(shù)組元素組成構(gòu)造出來的。 還應(yīng)該注意的是這種方法經(jīng)常會被作為一種類方法來調(diào)用，這就意味著調(diào)用此方法來自 String類本身而不是來自 String的實例。,比較字符串的方法,在 C#語言中有集中比較 String對象的方法。 最顯而易見的方法就是關(guān)系運(yùn)算符。 然而，在某些情況下其他一些比較的方法則會更加有效。 例如，如果希望知道字符串是大于、小于、還是等于另外一個字符串。,比較字符串的方法,字符串之間的互相比較的數(shù)字測量方法。 這種測量就是 Unicode表。 每一個字符（實際上是每一種符號）都有一個 Unicode值，操作系統(tǒng)就是用此數(shù)值把字符的二進(jìn)制表示轉(zhuǎn)化成為字符的形式。 通過使用 ASC函數(shù)可以確定字符的 Unicode值。 ASC實際上指的就是數(shù)的 ASCII碼。 ASCII碼是一種先于 Unicode的早期數(shù)字編碼，而 ASC函數(shù)是在 Unicode包含 ASCII之前被首先開發(fā)出來的。,比較字符串的方法,為了找到字符的 ASCII值，可以采用強(qiáng)制類型轉(zhuǎn)換把字符簡單地轉(zhuǎn)換成為一個整數(shù)，如下所示： int charCode; charCode = (int)a; 這樣會把數(shù)值 97存儲到變量中。,比較字符串的方法,兩個字符串的比較實際就是比較它們的數(shù)字編碼。 字符串 “a”和字符串“b”不相等，就是應(yīng)為編碼 97不同于編碼 98。 事實上 compareTo方法可以用來確定兩個 String對象之間的精確關(guān)系。,Equal方法,第一個要檢測的比較方法就是 Equal方法。 此方法會由一個 String對象調(diào)用，并且會把另外一個 String對象取作它的參數(shù)。 此方法逐個字符的比較兩個 String對象。 如果這兩個 String對象包含有相同的字符，那么方法就會返回一個 True值。 否則，方法就會返回 False值。,CompareTo方法,下一個比較字符串的方法就是 CompareTo。 此方法也是取一個 String作為參數(shù)，但是它不會布爾值。 如果兩個字符串相等，返回一個 0。 而如果傳遞給的字符串“低于 ”調(diào)用方法的字符串，返回 -1。 再如果傳遞給的字符串“高于”調(diào)用方法的字符串，返回的則是 1。 具體數(shù)值要由傳遞給的字符串和調(diào)用此方法的字符串實例之間的關(guān)系來決定,Compare方法,替換 CompareTo方法的就是 Compare方法。 Compare方法通常會被做作為一個類方法來調(diào)用。 Compare方法會執(zhí)行和 CompareTo方法相同的比較類型，而且對于相同的比較會返回相同的值。,StartsWith方法和 EndsWith方法,StartsWith和 EndsWith方法都回取一個字符串作為參數(shù)，而且若實例是以字符串參數(shù)作為開始或結(jié)束那么方法都會返回 True值。,處理字符串的方法,字符串處理通常包括對字符串的改變操作。 在字符串中插入新的字符 從字符串中移除字符 用新字符替換舊字符 改變某些字符的情況 向字符串添加空格 從字符串中移除空格,Insert方法,Insert方法會把某個字符串插入到另外一個字符串的指定位置。 Insert方法會返回新的字符串。 調(diào)用此方法的格式如下所示： String1 = String0.Insert(Position, String);,Remove方法,Remove方法會取走兩個整數(shù)參數(shù)： 一個開始位置 一個計數(shù)器 其中計數(shù)器就是要移除字符的數(shù)量。,Replace方法,Replace方法會取走兩個參數(shù)： 要移除掉的字符串 用來替換掉的字符串 此方方會返回新的字符串。,PadLeft方法和 PadRight方法,PadLeft方法和 PadRight方法在顯示來自程序的數(shù)據(jù)時，為了數(shù)據(jù)排列美觀而需要在打印區(qū)域內(nèi)對數(shù)據(jù)進(jìn)行排列時使用。 PadLeft方法會對字符串進(jìn)行右對齊排列 PadRight方法會對字符串進(jìn)行左對齊排列 例如，需要在一個 10個字符寬度區(qū)域內(nèi)右對齊打印單詞“ Hello”,Concat方法,Concat方法與&運(yùn)算符一樣，都是用于字符串的串聯(lián)。 Concat方法會取走 String對象的列表，把它們串聯(lián)在一起，然后返回結(jié)果字符串。,ToLower方法和 ToUpper方法,ToLower方法和 ToUpper方法還可以把字符串從小寫轉(zhuǎn)換成大寫形式（而且反之亦然）。,70,Trim方法和 TrimEnd,在處理 String對象時，這些對象有時會有額外的空格或者其他格式字符出現(xiàn)在字符串的開始或結(jié)尾處。 Trim方法和 TrimEnd方法將會把空格或其他字符從字符串的任一端移除掉。 可以對指定的單個字符進(jìn)行整理，也可以對字符數(shù)組進(jìn)行整理。 如果指定了字符數(shù)組，且在數(shù)組中沒有找到任何字符，那么它們會受到來自字符串的整理。,71,3.5 STRINGBUILDER類,72,STRINGBUILDER類,String類的對象是不變的，這就意味著不能對他們進(jìn)行改變。 StringBuilder類提供了對多變的 String對象的存取。 每次改變 String對象的值時，就會產(chǎn)生一個新的對象來保存數(shù)值。 當(dāng)對 StringBuidler對象進(jìn)行改變時，正在改變的就是原始對象而不是對副本進(jìn)行操作。 StringBuilder類存在在 System.Text名字域中，所以在能使用 StringBuilder對象之前需要在程序中輸入此名字域。,構(gòu)造 StringBuilder對象,有三種方法中的可以構(gòu)造 StringBuilder對象。 第一種方法：使用默認(rèn)構(gòu)造器來創(chuàng)建對象 StringBuilder stBuff1 = new StringBuilder(); 這一行代碼創(chuàng)建了對象 stBuff1， 此對象的容量可以保存長度為16個字符的字符串， 此容量是默認(rèn)設(shè)置的。,74,構(gòu)造 StringBuilder對象,第二種方法：通過在構(gòu)造器調(diào)用來創(chuàng)建對象 StringBuilder stBuff2 = new StringBuilder(25); 這一行代碼構(gòu)建了一個初始可以保存 25個字符的對象stBuff2 。,75,構(gòu)造 StringBuilder對象,第三種方法：構(gòu)造器調(diào)用會取字符串來創(chuàng)建對象 StringBuilder stBuff3 = new StringBuilder(“Hello,world“); 這里的容量設(shè)置為16，這是因為字符串參數(shù)沒有超過16個字符。 如果字符串參數(shù)長度超過16，那么容量就會設(shè)置為32。 每次一旦超過 StringBuilder對象的容量，那么