數(shù)據(jù)結(jié)構(gòu)-使用C語言 朱戰(zhàn)立 第4章串

1第4章串（String）4.1串4.2串的存儲結(jié)構(gòu)4.3串基本操作的實現(xiàn)算法4.4串的模式匹配算法2記為：

s=“s0,s1,……,sn-1”(n≥0)

串名串值（用“”括起來）一、串的基本概念１、串（又稱字符串）是由n(n≥0)個字符組成的有限序列。（它是數(shù)據(jù)元素為單個字符的特殊線性表。）4.1串隱含結(jié)束符‘\0’

，即ASCII碼NUL為何要單獨討論“串”類型？1）字符串操作比其他數(shù)據(jù)類型更復(fù)雜（如拷貝、連接操作）2）程序設(shè)計中，處理對象很多都是串類型。一般是字母、數(shù)學(xué)、標(biāo)點符號等可屏幕顯示的字符3２、串長串中字符的個數(shù)（n≥0）。３、空串串中字符的個數(shù)為0時稱為空串。４、空白串由一個或多個空格符組成的串。５、子串串S中任意個連續(xù)的字符序列叫S的子串;S叫主串。６、子串位置子串的第一個字符在主串中的序號。７、字符位置字符在串中的序號。８、串相等串長度相等，且對應(yīng)位置上字符相等。（即兩個串中的字符序列一一對應(yīng)相等。）問：空串和空白串有無區(qū)別？答：有區(qū)別?？沾?NullString)是指長度為零的串；而空白串(BlankString),是指包含一個或多個空白字符‘

’(空格鍵)的字符串.4

例1：現(xiàn)有以下4個字符串：a=“BEI” b=“JING”c=“BEIJING”d=“BEIJING”問：①他們各自的長度？a是c和d的子串，在c和d中的位置都是1②a是哪個串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8③空串是哪個串的子串？a是不是自己的子串？空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串。注：串與字符的區(qū)別“a”串，長度為１的串。（它不僅要存儲字符‘a(chǎn)’，還要存儲該串的長度數(shù)據(jù)１）‘a(chǎn)’字符a。(只存儲字符‘a(chǎn)’)

5數(shù)據(jù)集合：串的數(shù)據(jù)集合可以表示為字符序列s0,s1,……,sn-1，每個數(shù)據(jù)元素的數(shù)據(jù)類型為字符類型。操作集合：初始化串Initiate(S)賦值A(chǔ)ssign(S,T)求串長度Length(S)比較Compare(S,T)插入Insert(S,pos,T)刪除Delete(S,pos,len)取子串SubString(Spos,len)查找子串Search(S,start,T)替換子串Replace(S,start,T,V)二、串的抽象數(shù)據(jù)類型6三、C語言的串函數(shù)串長度：intstrlen(char*str);串拷貝：char*strcpy(char*str1,char*str2);串比較：intstrcmp(char*str1,char*str2);子串T定位：char*strchr(char*str,charch);子串查找：char*strstr(char*s1,char*s2);串連接：char*strcat(char*str1,char*str2);……注：用C處理字符串時，要調(diào)用標(biāo)準(zhǔn)庫函數(shù)#include<string.h>7

設(shè)s=“IAMASTUDENT”,t=“GOOD”,q=“WORKER”。求：例1：Length(s)＝

Length(t)＝

SubString(s,7,7)=SubString(t,2,1)=Replace(s,0,‘STUDENT’,q)=144‘STUDENT’‘O’’IAMAWORKER’8解：因為SubString(s,5,2)＝‘A’；SubString(s,6,8)＝‘STUDENT’strcat(t,SubString(s,6,8))＝’GOODSTUDENT’所以：strcat(SubString(s,5,2),strcat(t,SubString(s,6,8)))＝‘AGOODSTUDENT’例2：設(shè)s=“IAMASTUDENT”,t=“GOOD”,求：

strcat(SubString(s,6,2),strcat(t,SubString(s,7,8)))＝？94.2 串的存儲結(jié)構(gòu)靜態(tài)數(shù)組結(jié)構(gòu)——用一組地址連續(xù)的存儲單元存儲串值的字符序列，存儲空間不可改變。屬靜態(tài)存儲方式。動態(tài)數(shù)組結(jié)構(gòu)——用一組地址連續(xù)的存儲單元存儲串值的字符序列,但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。串的鏈?zhǔn)酱鎯Ρ斫Y(jié)構(gòu)首先強(qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。串有兩種存儲表示方法：順序存儲鏈?zhǔn)酱鎯?0

1、靜態(tài)數(shù)組結(jié)構(gòu)特點：用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲分配。

串的靜態(tài)數(shù)組結(jié)構(gòu)體可定義為：typedefstruct{charstr[MaxSize];intlength;}String;11思路：利用malloc函數(shù)合理預(yù)設(shè)串長空間。typedefstruct{char*str;intmaxLength;intlength;}Dstring;２、動態(tài)數(shù)組結(jié)構(gòu)特點：仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。串的動態(tài)數(shù)組結(jié)構(gòu)體定義如下：Str指向動態(tài)數(shù)組的首地址maxLength表示動態(tài)數(shù)組元素的最大個數(shù)Length表示串的當(dāng)前長度12３、串的鏈?zhǔn)酱鎯Y(jié)構(gòu)

它分為單字符結(jié)點和塊鏈兩種。(1)單字符結(jié)點鏈(2)塊鏈typedefstructNode

typedefstructNod{{charstr;charstr[Number];structNode*next;structNode*next;}SCharNode;}NCharNode;13注意：若數(shù)據(jù)元素很多，用法2存儲更優(yōu)—稱為塊鏈結(jié)構(gòu)鏈?zhǔn)酱鎯μ攸c:用鏈表存儲串值，易插入和刪除。法1：鏈表結(jié)點的數(shù)據(jù)分量長度取1（個字符）法2：鏈表結(jié)點（數(shù)據(jù)域）大小取n(例如n=4)

A

B

C

I

NULLheadheadABCDEFGHI###NULL144.3串基本操作的實現(xiàn)算法１、靜態(tài)數(shù)組下串基本操作的實現(xiàn)算法typedefstruct/*結(jié)構(gòu)體定義*/{ charstr[MaxSize]; intlength;}String;(1)初始化操作

voidInitiate(String*s){S->length=0;}15（2）插入子串操作intInsert(String*S,intpos,StringT)/*在串S的pos位置插入子串T*/{ inti; for(i=S->length-1;i>=pos;i--) S->str[i+T.length]=S->str[i]; //依次后移數(shù)據(jù)元素

for(i=0;i<T.length;i++) S->str[pos+i]=T.str[i];//插入

S->length+=T.length; //產(chǎn)生新的串長

return1;}16(3)刪除子串操作intDelete(String*S,intpos,intlen)//刪除串S從pos位置開始長度為len的子串值{ inti; for(i=pos+len;i<=S->length-1;i++) S->str[i-len]=S->str[i];//依次前移數(shù)據(jù)元素

S->length-=len;//產(chǎn)生新的串長度值

return1;}17２、動態(tài)數(shù)組下串基本操作的實現(xiàn)算法(1)初始化voidInitiate(DString*S,intmax,char*string){ inti; S->str=(char*)malloc(sizeof(char)*max);//申請動態(tài)數(shù)組空間 S->maxLength=max;//置動態(tài)數(shù)組元素最大個數(shù) S->length=strlen(string);//置串的當(dāng)前長度值 for(i=0;i<S->length;i++) S->str[i]=string[i];//賦串值}18(2)插入子串操作intInsert(DString*S,intpos,DStringT){ inti; char*p; for(i=S->length-1;i>=pos;i--)

S->str[i+T.length]=S->str[i];//依次后移數(shù)據(jù)元素

for(i=0;i<T.length;i++) S->str[pos+i]=T.str[i];//插入

S->length+=T.length;//產(chǎn)生新的串長度值

return1;}194.４串的模式匹配算法一、基本概念1、模式匹配（定位）設(shè)有主串S和子串T（將S稱為目標(biāo)串，將T稱為模式串），在主串S中，從位置start開始查找，如若在主串S中找到一個與子串T相等的子串，則返回T的第一個字符在主串中的位置，否則返回-1。2、算法目的確定主串中所含子串第一次出現(xiàn)的位置（定位）3、算法種類

BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）

KMP算法20二、Brute-Force算法1、Brute-Force算法的設(shè)計思想：將主串S的第1個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的第2字符起，重新與T的第1個字符比較。依次類推，若從模式串s的第i個字符開始，每個字符依次和目標(biāo)串t中的對應(yīng)字符相等，則匹配成功。21abcba223、BF算法的時間復(fù)雜度討論：若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m＝O(n*m)最好的情況是：一配就中！只比較了m次。最惡劣情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數(shù)為：(n-m)*m+m＝(n-m+1)*m串操作應(yīng)用舉例文本編輯程序用于源程序的輸入和修改，公文書信、報刊和書籍的編輯排版等。常用的文本編輯程序有Word,Notepad,WPS,TC等，文本編輯的實質(zhì)是修改字符數(shù)據(jù)的形式和格式，雖然各個文本編輯程序的功能不同，但基本操作是一樣的，都包括串的查找、插入和刪除等。2324

為了編輯方便，可以用分頁符和換行符將文本分為若干頁，每頁有若干行。我們把文本當(dāng)作一個字符串，稱為文本串，頁是文本串的子串，行是頁的子串。我們采用動態(tài)數(shù)組結(jié)構(gòu)來存儲文本，同時設(shè)立頁指針、行指針和字符指針，分別指向當(dāng)前操作的頁、行和字符，同時建立頁表和行表存儲每一頁、每一行的起始位置和長度。假設(shè)有如下源程序：FUNCmax(x，