第四章串
串是由零個或多個字符組成的有限序列;
包含字符的個數稱串的長度;長度為零的串稱空串;由一個或多個空格組成的串稱空白串;
串中任意個連續字符組成的子序列稱該串的子串;包含子串的串稱主串;
子串的首字符在主串中首次出現的位置定義為子串在主串中的位置;
空串是任意串的子串;任意串是自身的子串;
串常量在程序中只能引用但不能改變其值;串變量取值可以改變;
串的順序存儲結構稱順序串
直接用定長的字符數組定義
#define maxstrsize
typedef char seqstring[maxstrsize];
seqstring s;
不設終結符
Typedef struct{
Char ch[maxstrsize];
Int length;
}seqstring;
以上方式的缺點是
簡單定義
復雜定義
char *ch;
int length;
}hstring;
串的鏈式存儲結構稱鏈串
typedef struct node{
char data;
struct node *next;
}linkstrnode;
typedef linkstrnode *linkstring;
linkstring s;
將結點數據域存放的字符個數定義為結點的大小
#define nodesize
typedef struct node{
char data[nodesize];
struct node * next;
}linkstrnode;
子串定位運算又稱串的模式匹配或串匹配
樸素的串匹配算法
Int naivestrmatch(seqstring t
{
int i
int m=p
int n=t
for(i=
j=
while(j j++;k++; } if (j==m) return i; } return –1; } 2. 鏈串上的子串定位運算。TW.wiNGwIT.CoM時間復雜度為O(n^2)。比較的字符總次數為(n-m+1)m。 Linkstrnode * lilnkstrmatch(linkstring T, linkstring P) { linkstrnode *shift, *t, *p; shift=T; t=shift;p=P; while(t&&p){ if(t->data==p->data){ t=t->next; p=p->next; } else{ shift=shift->next; t=shift; p=P; } } if(p==NULL) return shift; else return NULL; } 附二: 第四章串 ************************************************************************************* 串是零個或多個字符組成的有限序列。 ·空串：是指長度為零的串，也就是串中不包含任何字符(結點)。 ·空白串：指串中包含一個或多個空格字符的串。 ·在一個串中任意個連續字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。 ·子串在主串中的序號就是指子串在主串中首次出現的位置。 ·空串是任意串的子串，任意串是自身的子串。 串分為兩種： ·串常量在程序中只能引用不能改變; ·串變量的值可以改變。 ************************************************************************************* 串的基本運算有： ·求串長strlen(char*s) ·串復制strcpy(char*to,char*from) ·串聯接strcat(char*to,char*from) ·串比較charcmp(char*s1,char*s2) ·字符定位strchr(char*s,charc) ************************************************************************************* .串是特殊的線性表(結點是字符)，所以串的存儲結構與線性表的存儲結構類似。串的順序存儲結構簡稱為順序串。 順序串又可按存儲分配的不同分為： ·靜態存儲分配：直接用定長的字符數組來定義。優點是涉及串長的操作速度快，但不適合插入、鏈接操作。 ·動態存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。 ************************************************************************************* 串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數據域為單個字符。為了解決"存儲密度"低的狀況，可以讓一個結點存儲多個字符，即結點的大小。 ************************************************************************************* 順序串上子串定位的運算：又稱串的"模式匹配"或"串匹配"，是在主串中查找出子串出現的位置。在串匹配中，將主串稱為目標(串)，子串稱為模式(串)。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移。最壞的情況下時間復雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。鏈串上的子串定位運算位移是結點地址而不是整數。
From:http://tw.wingwit.com/Article/program/sjjg/201311/23753.html