1、1第第4 4章章 串（串（StringString）4.1 串的基本概念串的基本概念4.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn) 2第第4章章 串（串（String） 字符串（簡稱串）對(duì)大家來說并不陌生。在解決實(shí)際問題時(shí)，經(jīng)常字符串（簡稱串）對(duì)大家來說并不陌生。在解決實(shí)際問題時(shí)，經(jīng)常會(huì)用到串操作。會(huì)用到串操作。一般地說，不同問題中所遇到的字符串具有不同特點(diǎn)。例如，在某一般地說，不同問題中所遇到的字符串具有不同特點(diǎn)。例如，在某些問題中，字符串都是些問題中，字符串都是100來個(gè)字符，比較均勻；而在有些問題中，一部來個(gè)字符，比較均勻；而在有些問題中，一部分字符串很長，另一部分字符串很短，起伏較大。分字符串很

2、長，另一部分字符串很短，起伏較大。顯而易見，在處理不同特點(diǎn)的字符串時(shí)，應(yīng)采用不同的存儲(chǔ)結(jié)構(gòu)，顯而易見，在處理不同特點(diǎn)的字符串時(shí)，應(yīng)采用不同的存儲(chǔ)結(jié)構(gòu)，只有這樣，才能獲得較高的效率。只有這樣，才能獲得較高的效率。在本章中，我們將討論串的幾種存儲(chǔ)結(jié)構(gòu)和一些基本操作。在本章中，我們將討論串的幾種存儲(chǔ)結(jié)構(gòu)和一些基本操作。 3第第4章章 串（串（String） 4.1 4.1 串類型的定義串類型的定義 一、串的定義一、串的定義 串是由串是由n（n0）個(gè)字符組成的序列，常記為）個(gè)字符組成的序列，常記為s=a1a2an 其中，其中， s為串的為串的名字名字 。 a1a2an稱稱為串的為串的值值。為了不至于與

3、變量名或常量混淆，串的值一定。為了不至于與變量名或常量混淆，串的值一定要用單引號(hào)括起來，但單引號(hào)本身不屬于串。要用單引號(hào)括起來，但單引號(hào)本身不屬于串。 串中字符的數(shù)目串中字符的數(shù)目n稱為串的稱為串的長度長度。長度為。長度為0的串稱為的串稱為空串空串，記為，記為 。 串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的子串子串，原串稱為，原串稱為主串主串. 通常把字符在序列中的序號(hào)稱為該字符在串中的通常把字符在序列中的序號(hào)稱為該字符在串中的位置位置（從（從1開始）。開始）。 子串在主串中的位置子串在主串中的位置指的是子串的第一個(gè)字符在主串中的位置。指的是子串的第一

4、個(gè)字符在主串中的位置。 稱兩個(gè)串稱兩個(gè)串相等相等當(dāng)且僅當(dāng)串的值相等，即串的長度相等，而且對(duì)應(yīng)位當(dāng)且僅當(dāng)串的值相等，即串的長度相等，而且對(duì)應(yīng)位置上的字符相等。置上的字符相等。 4一、串的定義一、串的定義 可以看出，串和線性表都是有限的序列，邏輯結(jié)構(gòu)很相似。但是，他可以看出，串和線性表都是有限的序列，邏輯結(jié)構(gòu)很相似。但是，他們有兩點(diǎn)區(qū)別：們有兩點(diǎn)區(qū)別： 串的每個(gè)數(shù)據(jù)元素為單個(gè)字符，數(shù)據(jù)對(duì)象是某個(gè)字符集。串的每個(gè)數(shù)據(jù)元素為單個(gè)字符，數(shù)據(jù)對(duì)象是某個(gè)字符集。 串的基本操作和線性表的基本操作差別較大。串的基本操作和線性表的基本操作差別較大。 線性表的基本操作大多以線性表的基本操作大多以“單個(gè)元素單個(gè)元素”

5、為操作對(duì)象，例如，獲取一為操作對(duì)象，例如，獲取一個(gè)數(shù)據(jù)元素、插入一個(gè)元素以及刪除一個(gè)元素等。個(gè)數(shù)據(jù)元素、插入一個(gè)元素以及刪除一個(gè)元素等。 串的基本操作很少以單個(gè)字符為操作對(duì)象，而大多以串的基本操作很少以單個(gè)字符為操作對(duì)象，而大多以“串的整體串的整體”為操作對(duì)象，例如，在串中取一個(gè)子串、在串中插入為操作對(duì)象，例如，在串中取一個(gè)子串、在串中插入/刪除一個(gè)子串等。刪除一個(gè)子串等。 5二、串的抽象數(shù)據(jù)類型二、串的抽象數(shù)據(jù)類型 P71用抽象數(shù)據(jù)類型用抽象數(shù)據(jù)類型 String 描述了串及其基本操作。描述了串及其基本操作。 ADT String 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=ai|aiCharacterSet,

6、 i=1, ,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1=|ai-1,aiD, i=2, ,n 基本操作：基本操作： StrAssign(&T, chars) 初始條件：初始條件：chars是字符串常量是字符串常量 操作結(jié)果：生成一個(gè)值為操作結(jié)果：生成一個(gè)值為chars的串的串T。 StrCopy(&T, S) 初始條件：串初始條件：串S已經(jīng)存在。已經(jīng)存在。 操作結(jié)果：由串操作結(jié)果：由串S復(fù)制得到串復(fù)制得到串T。 ADT String6三、串的基本操作三、串的基本操作 StrAssign(&S, chars)初始條件：初始條件： chars是字符串常量是字符串常量操作結(jié)果操作

7、結(jié)果：生成一個(gè)值為生成一個(gè)值為chars的串的串S。1.1.串賦值操作串賦值操作 StrCopy(&T, S)初始條件：串初始條件：串S已經(jīng)存在。已經(jīng)存在。操作結(jié)果：由串操作結(jié)果：由串S復(fù)制得到串復(fù)制得到串T。2.2.串復(fù)制操作串復(fù)制操作 StrEmpty(S)初始條件：串初始條件：串S已存在。已存在。操作結(jié)果：若操作結(jié)果：若S為空串，則返回為空串，則返回TRUE，否則，否則FALSE。3.3.判空操作判空操作7三、串的基本操作三、串的基本操作 StrCompare(S, T)初始條件：串初始條件：串S、T已存在。已存在。操作結(jié)果：若操作結(jié)果：若ST，則返回值，則返回值0; 若若S=T

8、，則返回值，則返回值=0; 若若ST，則返回值，則返回值0。4.4.串比較操作串比較操作 Concat(&T, S1, S2)初始條件：串初始條件：串S1、S2已存在。已存在。操作結(jié)果：用操作結(jié)果：用T返回由返回由S1與與S2連接而成的新串。連接而成的新串。6.6.串連接操作串連接操作 StrLength(S)初始條件：串初始條件：串S已存在。已存在。操作結(jié)果：返回串操作結(jié)果：返回串S中的字符個(gè)數(shù)。中的字符個(gè)數(shù)。5.5.求長度操作求長度操作8三、串的基本操作三、串的基本操作 SubString(&Sub, S, pos, len)初始條件：串初始條件：串S已存在，且已存在，且1

9、posStrLength(S), 0 len StrLength(S)-pos+1操作結(jié)果：用操作結(jié)果：用Sub返回返回S中從第中從第pos個(gè)字符起長度為個(gè)字符起長度為len 的子串。的子串。7.7.取子串操作取子串操作 Index(S, T, pos)初始條件：串初始條件：串S、T已存在，且已存在，且1posStrLength(S)。操作結(jié)果：操作結(jié)果：返回返回S中從第中從第pos個(gè)字符起子串個(gè)字符起子串T首次出現(xiàn)的首次出現(xiàn)的 位置。位置。8.8.求子串位置操作求子串位置操作 StrInsert(&S, pos, T)初始條件：串初始條件：串S、T已存在，已存在，1posStrLen

10、gth(S)+1.操作結(jié)果：在操作結(jié)果：在S的第的第pos個(gè)字符前插入串個(gè)字符前插入串T。9.9.串插入操作串插入操作9三、串的基本操作三、串的基本操作 StrDelete(&S, pos, len)初始條件：串初始條件：串S已存在，已存在，1posStrLength(S)-len+1.操作結(jié)果：刪除操作結(jié)果：刪除S中從第中從第pos個(gè)字符起長度為個(gè)字符起長度為len的子串的子串.10.10.串刪除操作串刪除操作 應(yīng)當(dāng)注意，在不同的高級(jí)語言中，對(duì)串操作的定義可能應(yīng)當(dāng)注意，在不同的高級(jí)語言中，對(duì)串操作的定義可能有差異。有差異。 10四、串的基本操作舉例四、串的基本操作舉例 例一、例一、若

11、執(zhí)行以下程序，會(huì)輸出怎樣的結(jié)果若執(zhí)行以下程序，會(huì)輸出怎樣的結(jié)果？ void main()StrAssign(S1,This); StrAssign(S2,is); Concat(S,S1,S2);x=Index(S,S2,2); printf(x); SubString(W,S,2,3); StrDelete(S,3,2);StrInsert(S,2,S2);printf(S);/S1=This/S2=is/S=Thisis/x=3/W=his/S=This/S=Tishis114.2 串的表示和實(shí)現(xiàn)串的表示和實(shí)現(xiàn)串的存儲(chǔ)表示分為兩大類共串的存儲(chǔ)表示分為兩大類共3 3種：種：一、定長順序存儲(chǔ)表

12、示一、定長順序存儲(chǔ)表示定長順序存儲(chǔ)表示就是用固定長度的數(shù)組來存儲(chǔ)每一個(gè)串。其中，第定長順序存儲(chǔ)表示就是用固定長度的數(shù)組來存儲(chǔ)每一個(gè)串。其中，第0分量用來存放串的長度，從第分量用來存放串的長度，從第1分量起依次存放串值的字符序列。分量起依次存放串值的字符序列。 順序存儲(chǔ)表示順序存儲(chǔ)表示鏈?zhǔn)酱鎯?chǔ)表示：鏈?zhǔn)酱鎯?chǔ)表示： 塊鏈存儲(chǔ)表示塊鏈存儲(chǔ)表示定長順序存儲(chǔ)表示定長順序存儲(chǔ)表示 堆分配存儲(chǔ)表示堆分配存儲(chǔ)表示 0123456串長度串長度串值區(qū)域串值區(qū)域12一、定長順序存儲(chǔ)表示一、定長順序存儲(chǔ)表示例如，對(duì)于例如，對(duì)于s1=USAs1=USA和和s2=I am a student.s2=I am a stud

13、ent., ,會(huì)用相同長度的會(huì)用相同長度的數(shù)組來存放。數(shù)組來存放。 01234563U SA012345615Iamastudent.T1T2 教材中規(guī)定，每個(gè)數(shù)組的長度為教材中規(guī)定，每個(gè)數(shù)組的長度為MAXSTRLEN+1，其中，其中，#define MAXSTRLEN255于是，數(shù)組最后分量的下標(biāo)為于是，數(shù)組最后分量的下標(biāo)為MAXSTRLEN。 另外，為便于定義長度為另外，為便于定義長度為MAXSTRLEN+1的數(shù)組，還用的數(shù)組，還用typedef unsigned char SStringMAXSTRLEN+1;定義了新的數(shù)據(jù)類型定義了新的數(shù)據(jù)類型SString。MAXSTRLENMAXS

14、TRLEN 這樣一來，我們可以定義這樣一來，我們可以定義 SString T1，T2；來分別存放來分別存放s1、s2。 13一、定長順序存儲(chǔ)表示一、定長順序存儲(chǔ)表示 再來看一個(gè)例子，對(duì)于再來看一個(gè)例子，對(duì)于s3如何用定長順序存儲(chǔ)方法來表示呢？如何用定長順序存儲(chǔ)方法來表示呢？s3=88888888888888888 8888888888888 由此可以看出，如果用由此可以看出，如果用SString類型的變量來表示一個(gè)長度超過類型的變量來表示一個(gè)長度超過MAXSTRLEN的串，則串值的超出部分將被截?cái)嗌崛ァＲ虼耍ㄩL順序的串，則串值的超出部分將被截?cái)嗌崛ァＲ虼耍ㄩL順序存儲(chǔ)表示只能正確地存儲(chǔ)長度在

15、存儲(chǔ)表示只能正確地存儲(chǔ)長度在0MAXSTRLEN之間的串。之間的串。 總之，定長順序存儲(chǔ)表示適用于所有的串長度均小于某一定數(shù)的應(yīng)總之，定長順序存儲(chǔ)表示適用于所有的串長度均小于某一定數(shù)的應(yīng)用場(chǎng)合。用場(chǎng)合。 當(dāng)然，可以定義當(dāng)然，可以定義SString T3；來存放來存放s3。當(dāng)用。當(dāng)用T3存放存放s3時(shí)，會(huì)出現(xiàn)什么情況呢？時(shí)，會(huì)出現(xiàn)什么情況呢？10000個(gè)個(gè)0123456T3MAXSTRLEN 由于由于s3的長度超過了的長度超過了T3的容量，串值的超出部分將被截?cái)嗌崛ァ５娜萘浚档某霾糠謱⒈唤財(cái)嗌崛ァ?888888888888 88825514一、定長順序存儲(chǔ)表示一、定長順序存儲(chǔ)表示 下面基于

16、定長順序存儲(chǔ)表示，來討論串的基本操作的實(shí)現(xiàn)算法。先下面基于定長順序存儲(chǔ)表示，來討論串的基本操作的實(shí)現(xiàn)算法。先來了解一下來了解一下 am.m+k=bn.n+k; 的含義。的含義。 1.1.串連接操作串連接操作- Concat(SString &T, SString S1, SString S2) 其功能是用其功能是用T返回由返回由S1和和S2連接而成的新串。連接而成的新串。 具體地說就是，假設(shè)具體地說就是，假設(shè)這是這是S1、S2、T，01l 1l 1buS1MAXSTRLEN01l 2l 2CWS2MAXSTRLEN01TMAXSTRLENbuCW串連接操作就是先把串連接操作就是先把S1

17、的串值復(fù)制到的串值復(fù)制到T中，接著再把中，接著再把S2的串值復(fù)制到的串值復(fù)制到T中，中，并設(shè)置結(jié)果串的長度并設(shè)置結(jié)果串的長度T0。 但是，由于可能出現(xiàn)截?cái)喱F(xiàn)象，所以我們分三種情況來討論。但是，由于可能出現(xiàn)截?cái)喱F(xiàn)象，所以我們分三種情況來討論。15串連接操作的實(shí)現(xiàn)算法串連接操作的實(shí)現(xiàn)算法 S10=MAXSTRLEN01buS1MAXSTRLEN01l 2l 2CWS2MAXSTRLEN01TMAXSTRLENbuS1直接復(fù)制，直接復(fù)制，S2全部舍去。全部舍去。該過程用語句表示如下：該過程用語句表示如下：T1S10=S11S10;T0=S10; l 1l 116串連接操作的實(shí)現(xiàn)算法串連接操作的實(shí)現(xiàn)算

18、法 S10 MAXSTRLEN01l 1l 1buS1MAXSTRLEN01l 2l 2CVXWS2MAXSTRLEN01TMAXSTRLENS1直接復(fù)制，直接復(fù)制，S2的超出部分截?cái)嗌崛ァ５某霾糠纸財(cái)嗌崛ァＳ谜Z句表示如下：用語句表示如下：T1S10=S11S10;TS10+1MAXSTRLEN=S21MAXSTRLEN-S10; T0=MAXSTRLEN; buCVl 1l 117串連接操作的實(shí)現(xiàn)算法串連接操作的實(shí)現(xiàn)算法 S10+S20 MAXSTRLEN) T1S10=S11S10; TS10+1MAXSTRLEN=S21MAXSTRLEN-S10; T0=MAXSTRLEN; else

19、 T1S10=S11S10; TS10+1S10+S20=S21S20; T0=S10+S20; /Concat19一、定長順序存儲(chǔ)表示一、定長順序存儲(chǔ)表示 從串連接操作的分析不難想象，在進(jìn)行插入子串等操作時(shí)，也有可從串連接操作的分析不難想象，在進(jìn)行插入子串等操作時(shí)，也有可能出現(xiàn)截?cái)嗌崛ガF(xiàn)象，因此在使用定長順序存儲(chǔ)表示時(shí)要特別注意這一能出現(xiàn)截?cái)嗌崛ガF(xiàn)象，因此在使用定長順序存儲(chǔ)表示時(shí)要特別注意這一點(diǎn)點(diǎn). 定長順序存儲(chǔ)表示之所以會(huì)出現(xiàn)截?cái)喱F(xiàn)象，是因?yàn)樗A(yù)先限定了串定長順序存儲(chǔ)表示之所以會(huì)出現(xiàn)截?cái)喱F(xiàn)象，是因?yàn)樗A(yù)先限定了串的最大長度。要想克服這種弊病，就不應(yīng)該為串長度設(shè)置上限，應(yīng)該按的最大長度。要想

20、克服這種弊病，就不應(yīng)該為串長度設(shè)置上限，應(yīng)該按需為串值分配空間。我們要介紹的堆分配存儲(chǔ)表示就是這樣做的。需為串值分配空間。我們要介紹的堆分配存儲(chǔ)表示就是這樣做的。二、堆分配存儲(chǔ)表示二、堆分配存儲(chǔ)表示 堆分配存儲(chǔ)表示也是用一組地址連續(xù)的存儲(chǔ)單元來依次存放串值的堆分配存儲(chǔ)表示也是用一組地址連續(xù)的存儲(chǔ)單元來依次存放串值的字符序列。但是，這些存儲(chǔ)單元是在程序執(zhí)行過程中，根據(jù)串的長度動(dòng)字符序列。但是，這些存儲(chǔ)單元是在程序執(zhí)行過程中，根據(jù)串的長度動(dòng)態(tài)分配的。態(tài)分配的。 這種存儲(chǔ)表示的類型定義如下：這種存儲(chǔ)表示的類型定義如下：typedef structchar *ch;/串值的基地址串值的基地址int l

21、ength;/串的長度串的長度HString;如果定義如果定義 HString S；則則S有兩個(gè)成員有兩個(gè)成員ch、length。20二、堆分配存儲(chǔ)表示二、堆分配存儲(chǔ)表示 我們知道，在定長順序存儲(chǔ)表示中，當(dāng)用我們知道，在定長順序存儲(chǔ)表示中，當(dāng)用 SString T; 定義變量定義變量T的時(shí)候，系統(tǒng)已經(jīng)分配好了存儲(chǔ)串值的存儲(chǔ)區(qū)域。的時(shí)候，系統(tǒng)已經(jīng)分配好了存儲(chǔ)串值的存儲(chǔ)區(qū)域。 但是，當(dāng)用但是，當(dāng)用 HString S; 定義變量定義變量S的時(shí)候，系統(tǒng)并沒有分配存儲(chǔ)串的時(shí)候，系統(tǒng)并沒有分配存儲(chǔ)串值的存儲(chǔ)區(qū)域。值的存儲(chǔ)區(qū)域。01TMAXSTRLEN 存儲(chǔ)串值的存儲(chǔ)區(qū)域是在程序執(zhí)行存儲(chǔ)串值的存儲(chǔ)區(qū)域是在

22、程序執(zhí)行過程中，根據(jù)當(dāng)時(shí)需要，在確定了串的過程中，根據(jù)當(dāng)時(shí)需要，在確定了串的長度即長度即 S.length 后，用語句后，用語句Slengthch10S.ch=(char*)malloc(S.length*sizeof(char);為為S分配的，并且串值的字符序列從分配的，并且串值的字符序列從第第0分量分量起存放。起存放。 另外，由于另外，由于malloc和和free函數(shù)管理的是函數(shù)管理的是C語言中稱為語言中稱為“堆堆”的存儲(chǔ)區(qū)，的存儲(chǔ)區(qū)，所以上述表示法被稱為所以上述表示法被稱為堆分配存儲(chǔ)表示堆分配存儲(chǔ)表示。 21二、堆分配存儲(chǔ)表示二、堆分配存儲(chǔ)表示 下面來看串連接操作下面來看串連接操作Con

23、cat(&T，S1，S2)在堆分配存儲(chǔ)表示時(shí)如何在堆分配存儲(chǔ)表示時(shí)如何實(shí)現(xiàn)。實(shí)現(xiàn)。 S2lengthchWe1x0S1lengthchQh1t0Tlengthch10確定確定T的長度，的長度，T.length=S1.length+S2.length; 依次復(fù)制依次復(fù)制S1、S2的串值至的串值至T中。中。QhtWex分配串值的存儲(chǔ)區(qū)域。分配串值的存儲(chǔ)區(qū)域。22串連接操作的實(shí)現(xiàn)算法串連接操作的實(shí)現(xiàn)算法Status Concat(HString &T，HString S1，HString S2) T.length=S1.length+S2.length; T.ch=(char*)ma

24、lloc(T.length*sizeof(char); if(!T.ch)return ERROR; T.ch0S1.length-1=S1.ch0S1.length-1; T.chS1.lengthT.length-1=S2.ch0S2.length-1; return OK; /Concat 由于用堆分配存儲(chǔ)表示的串既有順序存儲(chǔ)結(jié)構(gòu)處理方便的特點(diǎn)，又在由于用堆分配存儲(chǔ)表示的串既有順序存儲(chǔ)結(jié)構(gòu)處理方便的特點(diǎn)，又在操作中對(duì)串長無限制，因此，常在應(yīng)用中用來表示串。操作中對(duì)串長無限制，因此，常在應(yīng)用中用來表示串。 23串插入操作的實(shí)現(xiàn)算法串插入操作的實(shí)現(xiàn)算法Status StrInsert(HSt

25、ring &S，int pos，HString T) if(posS.length+1) return ERROR; if(T.length) if(!(S.ch=(char*)realloc(S.ch , (S.length+T.length)*sizeof(char) exit(OVERFLOW); for(i=S.length-1;i=pos-1;-i) S.chi+T.length=S.chi; S.chpos-1pos+T.length-2=T.ch0T.length-1; S.length+=T.length; return OK;24三、塊鏈存儲(chǔ)表示三、塊鏈存儲(chǔ)表示 與線

26、性表類似，我們也可以用單鏈表來表示串與線性表類似，我們也可以用單鏈表來表示串。例如，對(duì)于。例如，對(duì)于 S=CHINA可以表示為可以表示為實(shí)際已分配的字節(jié)數(shù)串值所占字節(jié)數(shù)存儲(chǔ)密度 顯然這種表示存在顯然這種表示存在存儲(chǔ)密度低、存儲(chǔ)效率不高存儲(chǔ)密度低、存儲(chǔ)效率不高的問題。的問題。 為此，人們提出了改進(jìn)方案：為此，人們提出了改進(jìn)方案： 用一個(gè)結(jié)點(diǎn)表示多個(gè)字符。用一個(gè)結(jié)點(diǎn)表示多個(gè)字符。CHINA#head注意：鏈表的尾結(jié)點(diǎn)不一定被串值充滿，通常用非字符集字符注意：鏈表的尾結(jié)點(diǎn)不一定被串值充滿，通常用非字符集字符 # 填充。填充。CheadHINA 為了便于進(jìn)行串連接等操作，設(shè)置串的尾指針和長度域。為了便

27、于進(jìn)行串連接等操作，設(shè)置串的尾指針和長度域。 tail串的這種存儲(chǔ)表示方法稱為串的這種存儲(chǔ)表示方法稱為塊鏈存儲(chǔ)表示塊鏈存儲(chǔ)表示 。25三、塊鏈存儲(chǔ)表示三、塊鏈存儲(chǔ)表示 CHINA#headtail 塊鏈存儲(chǔ)表示的類型定義如下：塊鏈存儲(chǔ)表示的類型定義如下： #define CHUNKSIZE 80/塊大小塊大小typedef struct Chunkchar chCHUNKSIZE;struct Chunk *next;Chunk;typedef structChunk *head, *tail;/串的頭、尾指針串的頭、尾指針int length;/串長度串長度LString; 一般地說，由于塊

28、鏈存儲(chǔ)表示占用存儲(chǔ)空間大，而且操作復(fù)雜，所以一般地說，由于塊鏈存儲(chǔ)表示占用存儲(chǔ)空間大，而且操作復(fù)雜，所以常用另外兩種存儲(chǔ)表示來表示串。常用另外兩種存儲(chǔ)表示來表示串。 26串運(yùn)算實(shí)例串運(yùn)算實(shí)例 文本編輯程序用于源程序的輸入和修改，公文書信、報(bào)刊文本編輯程序用于源程序的輸入和修改，公文書信、報(bào)刊和書籍的編輯排版等。常用的文本編輯程序有和書籍的編輯排版等。常用的文本編輯程序有Word、WPS等。等。文本編輯的實(shí)質(zhì)是修改字符數(shù)據(jù)的形式和格式，雖然各個(gè)文本文本編輯的實(shí)質(zhì)是修改字符數(shù)據(jù)的形式和格式，雖然各個(gè)文本編輯程序的功能強(qiáng)弱不同，但基本操作是一樣的，都包括串的編輯程序的功能強(qiáng)弱不同，但基本操作是一樣的

29、，都包括串的查找、插入和刪除等操作。查找、插入和刪除等操作。 這一節(jié)我們來實(shí)現(xiàn)一個(gè)簡單的文本編輯操作演示程序，包這一節(jié)我們來實(shí)現(xiàn)一個(gè)簡單的文本編輯操作演示程序，包括字符串的部分基本運(yùn)算：賦值、比較、連接、插入、刪除和括字符串的部分基本運(yùn)算：賦值、比較、連接、插入、刪除和清除運(yùn)算。字符串采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)清除運(yùn)算。字符串采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)(即堆分配即堆分配)存儲(chǔ)。存儲(chǔ)。27#define NULL 0typedef struct char *ch; int len; HString;int StrAssign(HString *s,char *chars) int i=0,slen; if(s-ch

30、!=NULL) free(s-ch); while(charsi!=0) i+; slen=i; if(slen)28 s-ch=(char *)malloc(slen*sizeof(char); if(s-ch=NULL) return(0); for(i=0;ichi=charsi; else s-ch=NULL; s-len=slen; return(1);int StrCompare(HString s,HString t) int i; for(i=0;is.len&it.chi) return(1); else return(-1);StrCat(HString *s,HS

31、tring t) /*參見算法參見算法4.4*/StrInsert(HString *s, int pos, HString t) /*參見算法參見算法4.3*/StrDelete(HString *s, int pos,int len) int i; char *temp; if(poss-len-len) return(0); if(len)30 temp=(char*)malloc(s-len-len)*sizeof(char); if(temp=NULL) return(0); for(i=0;ichi; for(i=pos;ilen-len;i+) tempi=s-chi+len;

32、s-len-=len; free(s-ch); s-ch=temp; return(1); 31int ClearString(HString *s) if(s-ch) free(s-ch); s-ch=NULL; s-len=0; return(0);main() int inp,flag=1; char *s,*t; HString s1,s2;32 int pos,len,ret; printf(1-StrAssingn); printf(2-StrComparen); printf(3-StrCatn); printf(4-StrInsertn); printf(5-StrDelete

33、n); printf(6-ClearStringn); printf(7-Exit); printf(please input 1-7nn); while(flag) scanf(%d,&inp); switch(inp) case 1:33 scanf(%s,s); ret=StrAssign(&s1,s); if(ret!=0) printf(the string is:%sn,s1); else printf(errorn); break; case 2: printf(s=); scanf(%s,s); StrAssign(&s1,s); printf(t=); scanf(%s,t); StrAssign(&s2,t); r