莊朝暉-數(shù)據(jù)結(jié)構(gòu)第四章串

1、數(shù)據(jù)結(jié)構(gòu) 第四章 串4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn) 4.2.1 定長(zhǎng)順序存儲(chǔ)表示 4.2.2 堆分配存儲(chǔ)表示 4.2.3 串的塊鏈存儲(chǔ)表示4.3 串的模式匹配算法 4.3.1 求子串位置的定位函數(shù) 4.3.2 模式匹配的一種改進(jìn)算法4.4 串操作應(yīng)用舉例 4.4.1 文本編輯 4.4.2 建立詞索引表 4.1 串類型的定義一、串和基本概念 串(String)是零個(gè)或多個(gè)字符組成的有限序列。一般記作S=“a1a2a3an”，其中S 是串名，雙引號(hào)括起來的字符序列是串值；ai(1in)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。長(zhǎng)度為零的串稱為空串(Empty St

2、ring)，它不包含任何字符。 通常將僅由一個(gè)或多個(gè)空格組成的串稱為空白串(Blank String) 注意：空串和空白串的不同，例如” ”和”分別表示長(zhǎng)度為1的空白串和長(zhǎng)度為0的空串。串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)的主串中的序號(hào)，定義為子串在主串中的序號(hào)（或位置）。例如，設(shè)A和B分別為 A=“This is a string” B=“is”則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對(duì)應(yīng)的主串位置是3。因此，稱B在A中的序號(hào)（或位置）為3 特別地，空串是任意串的子串，任意串是其自身的子

3、串。 通常在程序中使用的串可分為兩種：串變量和串常量。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能不能改變其值，即只能讀不能寫。通常串常量是由直接量來表示的，例如語句Error(“OVERFLOW”)中“OVERFLOW”是直接量。但有的語言允許對(duì)串常量命名，以使程序易讀、易寫。如C+中，可定義 const char path=“dir/bin/appl”;這里path是一個(gè)串常量，對(duì)它只能讀不能寫。串變量和其它類型的變量一樣，其取值是可以改變的。二、串的抽象數(shù)據(jù)定義 串的抽象數(shù)據(jù)類型定義：書P71三、串的基本操作 對(duì)于串的基本操作，許多高級(jí)語言均提供了相應(yīng)的運(yùn)算或標(biāo)準(zhǔn)庫函數(shù)來實(shí)現(xiàn)。下

4、面僅介紹幾種在C語言中常用的串運(yùn)算，其它的串操作見的文件。 定義下列幾個(gè)變量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;求串長(zhǎng)(length) int strlen(char *s); /求串的長(zhǎng)度 例如：printf(“%d”,strlen(s1); 輸出13（2）串復(fù)制(copy) char *strcpy(char *to,char *from); 該函數(shù)將串from復(fù)制到串to中，并且返回一個(gè)指向串to的開始處的指針。 例如：strcpy(s3,s1); /s3=“dirtreeformat

5、”(3)聯(lián)接(concatenation) char * strcat(char * to,char * from) 該函數(shù)將串from復(fù)制到串to的末尾，并且返回一個(gè)指向串to的開始處的指針。 例如：strcat(s3,”/”) strcat(s3,s2); /s3=“dirtreeformat/file.mem”(4)串比較（compare) int strcmp(char *s1,char *s2); 該函數(shù)比較串s1和串s2的大小，當(dāng)返回值小于0，等于0或大于0時(shí)分別表示s1s2 例如：result=strcmp(“baker”,”Baker”) result0 result=strc

6、mp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result0（5）字符定位(index) char* strchr(char * s,char c); 該函數(shù)是找c在字符串中第一次出現(xiàn)的位置，若找到則返回該位置的地址指針，否則返回NULL。 例如：p=strchr(s2,”.”); p 指向“file”之后的位置。s2=“file.mem” if(p) strcpy(p,”.cpp”); s2=“file.cpp” 上述串的操作是最基本的，其中后四個(gè)還有變種形式：strncpy，strncat，strncmp。串的其余操作可由這些

7、基本操作組合而成。 例1、求子串 求子串的過程即為復(fù)制字符序列的過程，將串s中的第pos個(gè)字符開始長(zhǎng)度為len的字符復(fù)制到串sub中。 void substr(char * sub, char * s,int pos,int len) if(posstrlen(s)-1 | len0) n=strlen(s); m=strlen(t); i=pos; while(i=n-m+1) substr(sub,s,i,m); if(strcmp(sub,t)!=0) +i; else return(i); return(0); 4.2 串的表現(xiàn)和實(shí)現(xiàn) 因?yàn)榇翘厥獾木€性表，故其存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)

8、構(gòu)類似。只不過由于組成串的結(jié)點(diǎn)是單個(gè)字符。串有三種機(jī)內(nèi)表示方法，下面分別介紹。4.2.1定長(zhǎng)順序存儲(chǔ)表示 定長(zhǎng)順序存儲(chǔ)表示,也稱為靜態(tài)存儲(chǔ)分配的順應(yīng)表。它是用一組連續(xù)的存儲(chǔ)單元來存放串中的字符序列。所謂定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)，是直接使用定長(zhǎng)的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出： #define MAXSTRLEN 256 typedef char SStringMAXSTRLEN; SString s; /s是一個(gè)可容納255個(gè)字符的順序串。 一般可使用一個(gè)不會(huì)出現(xiàn)在串中的特殊字符在串值的尾部來表示串的結(jié)束。例如，C語言中以字符0表示串值的終結(jié)，這就是為什么在上述定義中，串空間最大值MAXSTRLE

9、N為256，但最多只能存放255個(gè)字符的原因，因?yàn)楸仨毩粢粋€(gè)字節(jié)來存放0字符。若不設(shè)終結(jié)符，可用一個(gè)整數(shù)來表示串的長(zhǎng)度，那么該長(zhǎng)度減1的位置就是串值的最后一個(gè)字符的位置。此時(shí)順序串的類型定義和順序表類似： typedef struct char chMAXSTRLEN; int length; SString; /其優(yōu)點(diǎn)是涉及到串長(zhǎng)操作時(shí)速度快。 4.2.2堆分配存儲(chǔ)表示 這種存儲(chǔ)表示的特點(diǎn)是，仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得。所以也稱為動(dòng)態(tài)存儲(chǔ)分配的順序表。在C語言中，利用和等動(dòng)態(tài)存儲(chǔ)管理函數(shù)，來根據(jù)實(shí)際需要?jiǎng)討B(tài)分配和釋放字符數(shù)組空間

10、。這樣定義的順序串類型也有兩種形式。 typedef char *string; /c中的串庫相當(dāng)于此類型定義，或者再額外加入一個(gè)長(zhǎng)度變量。 typedef struct char *ch; int length; HSring;/*將字符串t插入到字符串s的pos位置*/Status StrInsert(HString &s, int pos, HString t) /*檢查pos位置的合法性*/ if(poss.length+1) return ERROR; if(t.length) /*重新分配字符串s的存儲(chǔ)空間*/ if(!(s.ch=(char*)realloc(s.ch,(s.le

11、ngth+t.length)*sizeof(char) exit(OVERFLOW); /*移動(dòng)s中pos位置之后的字符*/ for(i=s.length-1; i=pos-1; -i) s.chi+t.length=s.chi; /*插入字符串t并修改字符串s的長(zhǎng)度*/ s.chpos-1.pos+t.length-2=t.ch0.t.length-1; s.length+=t.length; return OK;/*生成一個(gè)其值等于串常量chars的串t*/Status StrAssign(HString &t, char *chars) /*釋放字符串t原有的空間*/ if(t.ch)

12、free(t.ch); /*計(jì)算字符串chars的長(zhǎng)度*/ for(i=0, c=chars; c ; +i, +c); if(!i) /*若chars長(zhǎng)度為0，則設(shè)置字符串t為空字符串*/ t.ch=NULL; t.length=0; else /*否則，分配空間并拷貝chars到字符串t中*/ if(!(t.ch=(char *)malloc(i*sizeof(char) exit(OVERFLOW); t.ch0.i-1=chars0.i-1; t.length=i; return OK; /*求字符串s的長(zhǎng)度*/int StrLength(HString s) return s.len

13、gth;/*比較字符串s,t的大小*/int pare(HString s, HString t) /*在s和t的長(zhǎng)度范圍內(nèi)逐個(gè)比較字符，找到一個(gè)不相等字符，返回該字符的比較結(jié)果*/ for(i=0; is.length & it.length; +i) if(s.chi!=t.chi) return(s.chi-t.chi); /*若超出長(zhǎng)度范圍，則返回s和t的長(zhǎng)度比較結(jié)果*/ return s.length-t.length;/*清除字符串s*/Status ClearString(HString &s) if(s.ch) free(s.ch); s.ch=NULL; s.length=0

14、; return ok;/*將s1和s2連接成的字符串拷貝到t中*/Status Concat(HString &t, HString s1, HString s2) /*給目標(biāo)字符串t分配空間*/ if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char) exit(OVERFLOW); /*拷貝s1和s2的內(nèi)容，并修改字符串的長(zhǎng)度*/ t.ch0.s1.length-1=s1.ch0.s1.length-1; t.length=s1.length+s2.length; t.chs1.length.t.length-1=s2.ch0.

15、s2.length-1; return ok; /*返回串s中的第pos個(gè)字符起長(zhǎng)度為len的子串*/Status SubString(HString &sub, HString s, int pos, int len) /*檢查位置pos和長(zhǎng)度len的合法性*/ if(poss.length | lens.length-pos+1) return ERROR; /*釋放sub的空間*/ if(sub.ch) free(sub.ch); if( ! len ) /*若長(zhǎng)度len為0，則設(shè)置sub為空串*/ sub.ch=NULL; sub.length=0; else/*否則，分配空間，拷貝第

16、pos個(gè)字符起長(zhǎng)度為len的子串，并設(shè)置長(zhǎng)度*/ sub.ch=(char *)malloc(len*sizeof(char); sub.ch0.len-1=spos-1.pos+len-2; sub.length=len; return OK;4.2.3 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序串上的插入和刪除操作不方便，需要移動(dòng)大量的字符。因此，我們可用單鏈表方式來存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。 typedef struct node char data; struct node *next; LString; 一個(gè)鏈串由頭指針唯一確定。 這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲(chǔ)空間利用率太低。為了提高存儲(chǔ)密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小，顯然，當(dāng)結(jié)點(diǎn)大小大于 1時(shí)，串的長(zhǎng)度不一定正好是結(jié)點(diǎn)大小的整數(shù)倍，因此要用特殊字符來填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)。 對(duì)于結(jié)點(diǎn)大小不為1的鏈串，其類型定為義只需對(duì)上述的結(jié)點(diǎn)類型做簡(jiǎn)單的修改即可。#define CHUNKSIZE 80typedef struct Chunk char dataCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head, *tail; int curlen