powerpoint 演示文稿 - 串類型的定義

1、14.1 串類型的定義一、串和基本概念 串(string)是零個(gè)或多個(gè)字符組成的有限序列。一般記作s=“a1a2an”，其中s 是串名，雙引號(hào)括起來的字符序列是串值；ai(1in)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。長(zhǎng)度為零的串稱為空串(Empty String)，它不包含任何字符。 通常將僅由一個(gè)或多個(gè)空格組成的串稱為空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分別表示長(zhǎng)度為1的空白串和長(zhǎng)度為0的空串。2 串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。 通常將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)的

2、主串中的序號(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ù)一樣，在程序中只能被引用但不能不能改變其值，即只能讀不能寫。通常串常量是由直接常量來表示的。 例如，語(yǔ)句 printf(“overflow”); 中“overflow”是直接常量。 但有的語(yǔ)言允許對(duì)串常量命名，以使程序易讀、易

3、寫。如C+中，可定義 const char path=“dir/bin/appl”; 這里path是一個(gè)串常量，對(duì)它只能讀不能寫。串變量和其它類型的變量一樣，其取值是可以改變的。4二、串的基本操作對(duì)于串的基本操作，許多高級(jí)語(yǔ)言均提供了相應(yīng)的運(yùn)算或標(biāo)準(zhǔn)庫(kù)函數(shù)來實(shí)現(xiàn)。下面僅介紹幾種在C語(yǔ)言中常用的串運(yùn)算。在使用字符串函數(shù)時(shí)要包含頭文件“string.h”。 定義下列幾個(gè)變量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result; 1. 求串長(zhǎng)(length) int strlen(char *s); /求串的長(zhǎng)度的

4、庫(kù)函數(shù) 例如：printf(“%d”,strlen(s1); /輸出1352 串復(fù)制(copy) char *strcpy(char *to,char *from); 該庫(kù)函數(shù)將串from復(fù)制到串to中，并且返回一個(gè)指向串to的開始處的指針。 例如：strcpy(s3,s1); /s3=“dirtreeformat”定義下列幾個(gè)變量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;63 聯(lián)接(concatenation) char * strcat(char *to,char *from)； 該函數(shù)將串f

5、rom復(fù)制到串to的末尾，并且返回一個(gè)指向串to的開始處的指針。 例如：strcat(s3,”)；/s3= “dirtreeformat” strcat(s3,s2); /s3=“dirtreeformatfile.mem”定義下列幾個(gè)變量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;執(zhí)行了 strcpy(s3,s1); /s3=“dirtreeformat”74 串比較（compare) int strcmp(char *s1,char *s2); 該庫(kù)函數(shù)比較串s1和串s2的大小。s1、s2從左至

6、右，逐個(gè)字符相比（ASCII碼值） 當(dāng)s1s2，返回值大于0。 例如：result=strcmp(“baker”,”Baker”) result0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result0 85 字符定位(index) char *strchr(char *s,int ch); 該庫(kù)函數(shù)是找ch在字符串s中第一次出現(xiàn)的位置，若找到則返回該位置，否則返回NULL。 例如：char s220=“file.mem”; char *p; p=strchr(s2,.); / p 指向“file”之后

7、的位置 if (p) strcpy(p,”.cpp”); /s2=“file.cpp” 上述串的操作是最基本的，其中后四個(gè)還有變種形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由這些基本操作組合而成。9例1:求子串 求子串的過程即為復(fù)制字符序列的過程，將串s中的第pos個(gè)字符開始長(zhǎng)度為len的字符復(fù)制到串sub中。 void substr(string sub,string s,int pos,int len) if (posstrlen(s) | len0) n=strlen(s); m=strlen(t); i=pos; while(i=n-m+1)

8、/i+m=l&i0&k=n-i+1) for(j=0;j=l&i0&k=1 & i0 & k=n-i+1) t.Length=k; t.StrAdr=free; for (j=0;jdata; /頭結(jié)點(diǎn)的data域存放串長(zhǎng)度 if(i=l&i0&k=n-i+1) p=s; for(j=0;jnext; /尋找子串起始位置 t=(nodetype*) malloc(sizeof(nodetype); t-data=k; /子串頭結(jié)點(diǎn)的數(shù)據(jù)域存放長(zhǎng)度 28 v=t; for(j=0;jnext=q; v=q; q-data=p-dat

9、a; p=p-next; /建立子串 return(t); else return(NIL); 29塊鏈結(jié)構(gòu)塊鏈結(jié)構(gòu) #define NODENUM typedef struct node char dataNODENUM; struct node *next;nodetype; /結(jié)點(diǎn)類型定義typedef struct head int len; nodetype *next; headtype; /頭結(jié)點(diǎn)類型定義 30s slenlenData0Data0 Data79Data79Data0Data0 Data79Data79 31headtype *substrl2(headtype

10、*s, int i,int k) headtype *t; nodetype *p, *v; int j,n,m,w,l,u; n=s-len; /n為主串s的長(zhǎng)度 p=s-next; /初始p指向主串 s的結(jié)點(diǎn) if (i=1&i0&k=n-i+1) m=i/NODENUM; /m為所求子串起始結(jié)點(diǎn)號(hào) for(j=0;jnext; t=(headtype*) malloc(sizeof(headtype); t-len=k; t-next=(nodetype*)malloc(sizeof( nodetype); v=t-next; w=1; /子串結(jié)點(diǎn)計(jì)數(shù)器 32 u=1;

11、/主串結(jié)點(diǎn)計(jì)數(shù)器 l=i; /主串序號(hào)計(jì)數(shù)器 for(j=0;j=NODENUM*w) w+; v-next=(nodetype*)malloc(sizeof(nodetype); v=v-next; if (l=NODENUM*u) u+; p=p-next; v-dataj%NODENUM=p-datal%NODENUM; l+; return(t); else return(NIL);334.3 4.3 串的模式匹配算法串的模式匹配算法 子串定位運(yùn)算又稱為模式匹配(Pattern Matching)或串匹配(String Matching)，此運(yùn)算的應(yīng)用在非常廣泛。例如，在文本編輯程序中

12、，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的位置。顯然，解此問題的有效算法能極大地提高文本編輯程序的響應(yīng)性能。 在串匹配中，一般將主串稱為目標(biāo)串，子串稱之為模式串。設(shè)S為目標(biāo)串，T為模式串，且不妨設(shè)： S=“s0s1s2sn-1” T=“t0t1tm-1” 串的匹配實(shí)際上是對(duì)于合法的位置0in-m依次將目標(biāo)串中的子串si.i+m-1和模式串t0.m-1進(jìn)行比較，若si.i+m-1=t0.m-1，34 則稱從位置i開始的匹配成功，亦稱模式t在目標(biāo)s中出現(xiàn)；若si.i+m-1 t0.m-1，則稱從位置i開始的匹配失敗。上述的位置i又稱為位移，當(dāng)si.i+m-1=t0.m-1時(shí)，i稱為有效位移；當(dāng)si

13、.i+m-1 t0.m-1時(shí)，i稱為無效位移。這樣，串匹配問題可簡(jiǎn)化為是找出某給定模式T在一給定目標(biāo)T中首次出現(xiàn)的有效位移。 串匹配的算法很多，這里我們只討論一種最簡(jiǎn)單的稱為樸素的串匹配算法。其基本思想是用一個(gè)循環(huán)來依次檢查n-m+1個(gè)合法的位移i(0in-m)是否為有效位移。35其算法段為： for(i=0;i=n-m;i+) if (Si.i+m-1=T0.m-1) return i; 下面以第二種定長(zhǎng)的順序串類型作為存儲(chǔ)結(jié)構(gòu)，給出具體的串匹配算法。 int index(sstring s,sstring t,int pos) int i,j,k; int m=s.length; int n=t.length; for(i=0;i=n-m;