串連接Concat（&T,S1,S2）

S1,S2為要連接的兩個(gè)串，T為連接后的串

串T值產(chǎn)生的三種結(jié)果：

1.S1[0]+S2[0]<=MAXSTRLEN。

2.S1[0]<MAXSTRLEN,而S1[0]+S2[0]>MAXSTRLEN，則將串S2的一部分截?cái)唷?/span>

3.S1[0]=MAXSTRLEN，此時(shí)串T和S1[0]相同。

如下圖所示：

代碼如下所示：

Status Concat(SString &T, SString S1, SString S2) { // 用T返回由S1和S2聯(lián)接而成的新串。若未截?cái)?#xff0c;則返回TRUE，否則FALSE。int i;Status uncut;if (S1[0] + S2[0] <= MAXSTRLEN) // 未截?cái)鄘for (i = 1; i <= S1[0]; i++) T[i] = S1[i];for (i = 1; i <= S2[0]; i++) T[i + S1[0]] = S2[i];T[0] = S1[0] + S2[0];uncut = TRUE;}else if (S1[0] < MAXSTRLEN) // 截?cái)鄘 for (i = 1; i <= S1[0]; i++) T[i] = S1[i];for (i = S1[0] + 1; i <= MAXSTRLEN; i++) T[i] = S2[i - S1[0]];T[0] = MAXSTRLEN;uncut = FALSE;}else // 截?cái)?僅取S1){ for (i = 0; i <= MAXSTRLEN; i++) T[i] = S1[i];uncut = FALSE;}return uncut; } // Concat 分析：

這里的MAXSTRLEN是宏，書上把他定義為255。這里，代碼是比較亂，畢竟書上只提供了思路和偽代碼，在此我只能說下思路。

他這個(gè)數(shù)組里面S1[0],和S2[0]，保存了整個(gè)字符串長度，從S1[1]，S2[1]開始才是存數(shù)據(jù)，

算法：4.3求子串SubString(&Sub,S,pos,len)

求子串過程即為復(fù)制字符串序列的過程，將串S中的從第pos個(gè)字符開始長度為len的字符序列復(fù)制到串Sub中。當(dāng)參數(shù)非法是，返回ERROR

代碼如下：

Status SubString(SString &Sub, SString S, int pos, int len) {// 用Sub返回串S的第pos個(gè)字符起長度為len的子串。// 其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。int i;if (pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)return ERROR;for (i = 1; i <= len; i++)Sub[i] = S[pos + i - 1];Sub[0] = len;return OK; } // SubString 下面來分析下：

這里的StrLength(S)意思就是S的長度。這里面len<=StrLength(S)-pos+1。大家可以舉個(gè)例子，如果Strlength(S)是5，pos也是5，那么就是在第五個(gè)位置開始尋址，所以要+1。

這里的pos+i-1也差不多，大家?guī)€(gè)數(shù)進(jìn)去看看，就知道為什么要-1了。

4.2.2堆分配存儲(chǔ)表示：

用malloc()和free()來管理。分配成功則返回起始地址指針，作為串基址。

下面是他的結(jié)構(gòu)體：

typedef struct{char *ch; //若是非空串，則按串長分配存儲(chǔ)區(qū)，否則為NULLint length; //串長 }HString;

算法4.3：串插入操作StrInsert(&S,pos,T)為串S重新分配大小等于串S和串T長度之和的存儲(chǔ)科技，然后進(jìn)行串值復(fù)制。

代碼如下：

Status StrInsert(HString &S, int pos, HString T) { // 1≤pos≤StrLength(S)＋1。在串S的第pos個(gè)字符之前插入串T。int i;if (pos < 1 || pos > S.length + 1) // pos不合法return ERROR;if (T.length) { // T非空,則重新分配空間,插入Tif (!(S.ch = (char *)realloc(S.ch, (S.length + T.length + 1)*sizeof(char))))return ERROR;for (i = S.length - 1; i >= pos - 1; --i) // 為插入T而騰出位置S.ch[i + T.length] = S.ch[i];for (i = 0; i < T.length; i++) // 插入TS.ch[pos - 1 + i] = T.ch[i];S.length += T.length;}return OK; } // StrInsert 分析：

這里的realloc當(dāng)擴(kuò)大堆區(qū)時(shí)，原數(shù)據(jù)沒有被破壞，當(dāng)比以前小了后，才會(huì)被破壞。

算法4.4：

下面的代碼是對(duì)堆分配的存儲(chǔ)結(jié)構(gòu)的操作：

生成一個(gè)其值等于串常量chars的串T

?代碼如下：

Status StrAssign(HString& T, char* chars) {int i;char *c;if (T.ch)free(T.ch);for (i = 0, c = chars; *c; ++i, ++c); //求chars的長度if (!i){T.ch = NULL;T.length = 0;}else{if (!(T.ch = (char*)malloc(i*sizeof(char))))exit(OVERFLOW);for (int j = 0; i < i; j++){T.ch[j] = chars[j];}T.length = i;}return Ok; }

這個(gè)程序的思路就是：

把char*型變量轉(zhuǎn)成HString。首先獲取chars長度，在到HString里面的 char*在堆區(qū)開辟空間，然后把chars依次給T.ch【x】。

求串S的長度：

int StrLength(HString S) {return S.length; }

字符串比較：

代碼如下：

int StrCompare(HString S, HString T) {//S>T返>0,S=T返0，S<T返<09for (int i = 0; i < S.length&&i < T.length; i++){if (S.ch[i] != T.ch[i])return S.ch[i] - T.ch[i];}return S.length - T.length; }

分析下：

這里S.ch[i]-T.ch[i]這個(gè)地方是比較ASCII。前者大返回正，后者大返回負(fù)。

當(dāng)某一個(gè)串比到最后，說明前面的都一樣，最后看長度，如果長度一樣就返回0，不一樣的話，大家懂的。

清空S串：

代碼如下：

Status ClearString(HString& S) {if (S.ch){free(S.ch);S.ch = NULL;}S.length = 0;return Ok; }

4.23串的塊鏈存儲(chǔ)表示：

每個(gè)結(jié)點(diǎn)可以存放一個(gè)字符，或者存放多個(gè)字符

也可以是結(jié)點(diǎn)大小為1的鏈表

如下圖所示：

為了便于進(jìn)行串的操作，當(dāng)以鏈表存儲(chǔ)串時(shí)，除頭指針外還可以附設(shè)一個(gè)尾指針指示鏈表中的最后一個(gè)結(jié)點(diǎn)，并給出當(dāng)前串的長度。稱如此定義的串存儲(chǔ)結(jié)構(gòu)為塊鏈結(jié)構(gòu)，說明如下：

#define CHUNKSZIE 80 typedef struct Chunk{char ch[CHUNKSZIE];struct Chunk* next; }Chunk; typedef struct{Chunk* head, *tail; //串頭和串尾指針int curlen; //串的當(dāng)前長度 }LString;

下面是一個(gè)存儲(chǔ)密度的概念：

存儲(chǔ)密度=串值所占的存儲(chǔ)位/實(shí)際分配的存儲(chǔ)位

密度小：運(yùn)算處理方便，存儲(chǔ)占用大

總結(jié)

以上是生活随笔為你收集整理的4.2串的表示和实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。