第四章串
4.1 串及其運算
1.串的基本概念
串(string)：串是大於等於零個字元的有限序列，記為s=「a1a2…an」。其中s為串名，ai可以是字母、數字或其它字元，n為長度，當n=0時稱為空串。
例如：a=「this is a string」
b=「is」
主串，子串，串常量，串變數。
2.串的基本運算
運算：(1)賦值(=)
2)連線(strcat)
3)求串長(strlen)
4)求子串(substr)
5)比較(strcmp)
6)拷貝(strcpy)
7)插入(insret)
8)刪除(delete)
9)子串定位(index)
10)置換(replace)
假設：s1=「a1a2…an」
s2=「b1b2…bm」
其中1<=m<=n
上述串的基本運算，在高階語言的實現中都作為基本的運算子或內部函式來提供，當然語言間可能略有差異。
4.2 串的儲存結構
1.順序儲存
順序串：串的順序儲存稱為順序串。字元被順序地存放在一片連續的單元裡。定義：typedef struct
char ch[maxsize];
int curlen;
seqstring;
或者：char ch[maxsize],*ps; //以\0作為結束標誌
和順序表類似，順序串的插入刪除不方便，需移動字元。
2.鏈式儲存
鏈串：串的鏈式儲存結構簡稱鏈串。通常由乙個指標唯一確定。
定義：typedef struct linknode
char data;
struct linknode *next;
linkstring;
linkstring *ps;
討論：(1)鏈式儲存便於插入刪除，但空間效率較低。
2)可增加結點存放的字元個數，以增加儲存密度。
3.索引儲存
索引儲存：用串變數的名字作為關鍵字組織索引表，表中儲存的是串名和串值之間的對應關係。
名字表的儲存方式：順序儲存，雜湊儲存
末位址的表示方法：給出串長，在末尾加結束符，設定尾指標直接指向串值的末位址。
(1)帶長度的名字表：typedef struct
char name[maxsize]; //串名
int lengh串長
char *stadr串值位址
lnode;
p65 圖4.3(a)
(2)帶指標的名字表：typedef struct
char name[maxsize]; //串名
char *stadr，*endadr; //首尾指標
pnode;
p65 圖4.3(b)
(3)帶特徵的名字表：typedef struct
char name[maxsize]; //串名
int tag特徵位，標明指標或串值
union
char *stadr;
char value[4];
uval;
tagnode;
p65 圖4.3(c)
(4)帶位移的名字表：當運算中出現大量子串時，為節省子串重複儲存，可採用子串在主串中的首尾相對位移來指出子串值的位置，這樣串值資料區的資訊可以共享。
typedef struct
char name[maxsize]; //串名
char *stadr，*endadr; //首尾指標
int offset1,offset2; //位移量
onode;
p65 圖4.3(d)
4.3 串運算的實現
順序串上的運算相當於在順序表上進行操作。
鏈串上的運算相當於在鍊錶上進行操作。
1. 順序串上的子串定位運算——模式匹配
設有：s=「s0s1…sn-1」
t=「t0t1…tm-1」
其中0<=m<=n (通常情況下m結果：若s中有模式為t的子串，返回t在s中的位置，通常只返回第乙個子串的位置，否則匹配失敗。
思想：用t中的字元依次與s中的字元比較。
引入兩個變數i，j分別指示s、t中字元的位置。
目標s： s0 s1 …… **-1 …… sn-1
模式t： t0 t1 tm-1
例如：s=「abbaba」
t=「aba」
p68 圖4.5
演算法：int index(seqstring *s,seqstring *t)
}改進演算法：若某一趟匹配失敗，i指標回溯時加以判斷：
if (i>s->curlen-t->curlen)
則s串剩餘長度已小於t串的長度。
return -1；。
或者i回溯前判斷：
if (i>s->curlen-t->curlen+j-1)
效果相同。
分析：最好情況：第i趟比較次數——i-1+m
t(n)=o(m+n)
最壞情況：第i-1趟每趟比較m次，第i趟成功比較m次，共比較i*m次。
t(n)=o(m*n)
改進演算法：匹配時如果出現不等字元，i不回溯，而是利用部分匹配結果將模式滑動一定距離繼續比較，則匹配演算法可控制在o(m+n)級別上。讀者可參見kmp演算法。
2. 鏈串上的子串定位運算——模式匹配
設計思想：同前述一樣，只要用乙個指標first記住每趟開始時目標串起始比較結點的位址，匹配成功返回first的值，否則返回空。
演算法：linkstring *indexl(linkstring *s,linkstring *t)
else
if (tptr==null)
return first;
}return null;
}分析：時間複雜度於前述相同。
資料結構複習第四章串
第四章串 string 重點 掌握串的基本概念，掌握串的基本操作 掌握串的三種不同的儲存方式。難點 掌握串的三種不同的儲存方式。學習提要 1.熟悉串的七種基本操作的定義，並能利用這些基本操作來實現串的其它各種操作的方法。2.熟練掌握在串的定長順序儲存結構上實現串的各種操作的方法。3.掌握串的堆儲存結...
資料結構習題第四章串答案
第四章串 一 選擇題 注 子串的定義是 串中任意個連續的字元組成的子串行，並規定空串是任意串的子串，任意串是其自身的子串。若字串長度為n n 0 長為n的子串有1個，長為n 1的子串有2個，長為n 2的子串有3個，長為1的子串有n個。由於空串是任何串的子串，所以本題的答案為 8 8 1 2 1 37...
資料結構第三章第四章
第3章棧和佇列 一選擇題 1.對於棧運算元據的原則是 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.在作進棧運算時,應先判別棧是否 在作退棧運算時應先判別棧是否 當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為 為了增加記憶體空間的利用率和減少溢位的可能性,由兩個棧共享一...