1、 串（即字符串）是一種特殊的線性表，它的數據元素僅由一個字符組成，計算機非數值處理的對象經常是字符串數據，如在匯編和高級語言的編譯程序中，源程序和目標程序都是字符串數據。在事物處理程序中，顧客的姓名、地址、貨物的產地、名稱等，一般也是作為字符串處理的。另外串還具有自身的特性，常常把一個串作為一個整體來處理。 第四章 串 串的基本概念 串是由零個或多個任意字符組成的字符序列。一般記作：s=a1 a2 an 其中s 是串名； ai(1=i=n)是一個任意字符，它稱為串的元素，是構成串的基本單位，i是它在整個串中的序號; n為串的長度，表示串中所包含的字符個數，當n=0時，稱為空串，通常記為。 幾個

2、基本概念 子串與主串：串中任意連續的字符組成的子序列稱為該串的子串。包含子串的串相應地稱為主串。 注：空串是任意串的子串；任意串是其自身的子串。 子串的位置：子串的第一個字符在主串中的序號稱為子串的位置。 串相等：稱兩個串是相等的，是指兩個串的長度相等且對應字符都相等。 空格串：有一個或多個空格組成的串。 注意：空格串與空串的區別串的抽象數據類型定義 P71 問題：串的基本操作與線性表的有什么不同？ 串的最小操作子集：串賦值、串比較、求串長、串聯接、求子串。串的定長順序存儲（一） 類似于順序表，用一組地址連續的存儲單元存儲串值中的字符序列，所謂定長是指按預定義的大小，為每一個串變量分配一個固定

3、長度的存儲區 。#define MAXSTRLEN 255Typedef unsigned char SstringMAXSTRLEN+1;/0號單元存放串的長度 注：c語言中用“0”表示串的結束符。 串長的兩種表示方法： 設定長串存儲空間：char sMAXSIZE+1; 用s0存放串的實際長度，串值存放在s1sMAXSIZE，字符的序號和存儲位置一致，應用更為方便。 在串尾存儲一個不會在串中出現的特殊字符作為串的終結符，以此表示串的結尾。比如C語言中處理定長串的方法就是這樣的，它是用0來表示串的結束。這種存儲方法不能直接得到串的長度，是用判斷當前字符是否是0來確定串是否結束，從而求得串的長

4、度。 順序串的基本運算 串聯接：把兩個串s1和s2首尾連接成一個新串s ，即：sMAXSIZE-1) return ERROR ; /* s長度不夠*/j=0;while(s1j!=0) si=s1j;i+; j+; j=0;while(s2j!=0) si=s2j;i+; j+; si=0; return OK;求子串 int StrSub (char *t, char *s, int i, int len)/* 用t返回串s中第i個字符開始的長度為len 的子串1i串長*/ int slen; slen=StrLength(s); if ( islen | lenslen-i+1) pri

5、ntf(參數不對); return ERROR; for (j=0; jlen; j+) tj=si+j-1;tj=0; return OK;串比較int StrComp(char *s1, char *s2) int i=0; while (s1i=s2i & s1i!=0) i+; return (s1i-s2i);串的堆分配存儲表示（二） 堆存儲結構的基本思想是：在內存中開辟能存儲足夠多的串、地址連續的存儲空間作為應用程序中所有串的可利用存儲空間，稱為堆空間。根據每個串的長度，動態的為每個串在堆空間里申請相應大小的存儲區域，這個串順序存儲在所申請的存儲區域中，當操作過程中若原空間不夠了，

6、可以根據串的實際長度重新申請，拷貝原串值后再釋放原空間。 陰影部分是已經為存在的串分配過的，free為未分配部分的起始地址，每當向store中存放一個串時，要填上該串的索引項。 sore堆結構示意圖（未分配區域）（已分配區域）free typedef struct char *ch;/*若是非空串，按串長分配存儲區，否則，ch為NULL*/ int length;/*串長*/ HString;基于堆結構的基本運算 1. 串常量賦值 Status StrAssign(HString &T,char *chars) /*生成一個其值等于chars的字符串T*/ if (T.ch) free(T.c

7、h); For(i=0,c=chars;*c;+i,+c); If(!i) T.ch=NULL;T.length=0 ; else if(!(T.ch=(char*)malloc(i*sizeof(char) exit(OVERFLOW); T.ch0.i-1=chars0.i-1; T.length=i; Return OK; 2. 求子串 Status StrSub(Hstring &T, Hstring S,int i,int len) /*該運算將串s中第i個字符開始的長度為len 的子串送到一個新串t中*/ if (iS. length | lenS.length-i+1) retu

8、rn error ; else T.ch= (char*)malloc(len*sizeof(char) ; T.ch0.len-1=Si-1.i+len-2 ; T.length=len; return OK; 3.串聯接 Status Concat(Hstring &T, Hstring S1, HstringS2) /用T返回由S1和S2聯接而成的新串 if (T.ch) free(T.ch); if(!(T.ch=(char*)malloc(S1.length+S2.length *sizeof(char) exit(OVERFLOW)； T.ch0.S1.length-1=S10.

9、S1.length-1 ; T.length=S1.length+S2.length; T.chS1.length. T.length -1=S20. S2.length-1; Return OK;4.串比較int StrComp(Hstring S, Hstring T) for(i=0;iS.length&iT. length;+i) if (S.chi!=T.chi) return (S.chi- T.ch i); return S.length -T. length; 5.串插入 Status Strinsert(Hstring &S, int pos, Hstring T) /在S的

10、第pos個字符前插入串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-1. Pos+T.length-2=T.ch0. T.length-1; S.length+=T.length; Return OK;串的鏈式存儲表示（三）a b c de f g hi # # #

11、 headabci head 串的塊鏈存儲表示： #define CHUNKSIZE 80 typedef struct Chunk char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct Chunk *head,*tail; /串的頭尾指針 int curlen; /串的當前長度 LString; 串值所占的存儲位 存儲密度= 實際分配的存儲位串操作應用舉例:簡單文本編輯 文本編輯基本原理: 文本編輯可以用于源程序的輸入和修改（如圖一）,也可用于報刊和書籍的編輯排版以及辦公室的公文書信的起草和潤色（如圖二）。 可用于文本編輯的程序很多，功能強弱差別很大，但基本操作是一致的：都包括串的查找，插入和刪除等基本操作。 對用戶來講，一個文本（文件）可以包括若干頁，每頁包括若干行，每行包括若干文字。 對文本編輯程序來講，可把整個文本看成一個長字符串，稱文本串，頁是文本串的子串，行又是頁的子串。為簡化程序復雜程度，可簡單地把文本分成若干行。 下面的一段源程序可以看成一個文本串，下面的一段源程序可以看成一個文本串， 100 mai