【正文】 : typedef struct snode { char data。 struct snode *next。 } LiString。 其中 data域用來存儲組成字符串的字符 ,next域用來指向下一個結點 。 每個字符對應一個結點 ,一個這樣的鏈表存儲一個字符串 。 下圖所示是一個結點大小為 1的鏈串 。 鏈串示意圖 下面討論在鏈串上實現(xiàn)串基本運算的算法 。 (1) StrAssign(s,t) 將一個字符串常量 t賦給串 s,即生成一個其值等于 t的串 s。 以下采用尾插法建立鏈串 。 void StrAssign(LiString *amp。s,char t[]) { int i。 LiString *r,*p。 /*r始終指向尾結點 */ s=(LiString *)malloc(sizeof(LiString))。 r=s。 for (i=0。t[i]!=39。\039。i++) { p=(LiString *)malloc(sizeof(LiString))。 pdata=t[i]。rnext=p。r=p。 } rnext=NULL。 } (2) StrCopy(s,t) 將串 t復制給串 s。 以下采用尾插法建立復制后的鏈串 s。 void StrCopy(LiString *amp。s,LiString *t) { LiString *p=tnext,*q,*r。 s=(LiString *)malloc(sizeof(LiString))。 r=s。 /*r始終指向尾結點 */ while (p!=NULL) /*將 t的所有結點復制到 s*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。rnext=q。r=q。 p=pnext。 } rnext=NULL。 } (3) StrEqual(s,t) 判斷兩個串是否相等 :若兩個串 s與 t相等則返回真 (1)；否則返回假 (0)。 int StrEqual(LiString *s,LiString *t) { LiString *p=snext,*q=tnext。 while (p!=NULL amp。amp。 q!=NULL amp。amp。 pdata==qdata) { p=pnext。q=qnext。 } if (p==NULL amp。amp。 q==NULL) return 1。 else return 0。 } (4) StrLength(s) 求串長 :返回串 s中字符個數(shù) 。 int StrLength(LiString *s) { int i=0。 LiString *p=snext。 while (p!=NULL) { i++。 p=pnext。 } return i。 } (5) Concat(s,t) 返回由兩個串 s和 t連接在一起形成的新串 。 LiString *Concat(LiString *s,LiString *t) { LiString *str,*p=snext,*q,*r。 str=(LiString *)malloc(sizeof(LiString))。 r=str。 while (p!=NULL) /*將 s的所有結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。 rnext=q。r=q。 p=pnext。 } p=tnext。 while (p!=NULL) /*將 t的所有結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。 rnext=q。r=q。 p=pnext。 } rnext=NULL。 return str。 } (6) SubStr(s,i,j) 返回串 s中從第 i(1≤i≤StrLength(s))個字符開始的 、 由連續(xù) j個字符組成的子串 。 LiString *SubStr(LiString *s,int i,int j) { int k。 LiString *str,*p=snext,*q,*r。 str=(LiString *)malloc(sizeof(LiString))。 r=str。 if (i=0 || iStrLength(s) || j0 || i+j1StrLength(s)) { printf(參數(shù)不正確 \n)。 return str。 /*參數(shù)不正確時返回空串 */ } for (k=0。ki1。k++) /*找第 i1個結點 ,由 p指向它 */ p=pnext。 for (k=1。k=j。k++) /*s[i]開始的 j個結點 =str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。qnext=NULL。 rnext=q。r=q。 p=pnext。 } rnext=NULL。 return str。 } (7) InsStr(s1,i,s2) 將串 s2插入到串 s1的第 i(1≤i≤StrLength(s)+1)個字符中 ,即將 s2的第一個字符作為 s1的第 i個字符 ,并返回產生的新串 。 LiString *InsStr(LiString *s,int i,LiString *t) { int k。 LiString *str,*p=snext,*p1=tnext,*q,*r。 str=(LiString *)malloc(sizeof(LiString))。 r=str。 if (i=0 || iStrLength(s)+1) { printf(參數(shù)不正確 \n)。 return str。 /*參數(shù)不正確時返回空串 */ } for (k=1。ki。k++) /*將 s的前 i個結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。qnext=NULL。 rnext=q。r=q。p=pnext。 } while (p1!=NULL) /*將 t的所有結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=p1data。qnext=NULL。 rnext=q。r=q。 p1=p1next。 } while (p!=NULL) /*將 *p及其后的結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。qnext=NULL。 rnext=q。r=q。 p=pnext。 } rnext=NULL。 return str。 } (8) DelStr(s,i,j) 從串 s中刪去從第 i(1≤i≤StrLength(s))個字符開始的長度為 j的子串 ,并返回產生的新串 。 LiString *DelStr(LiString *s,int i,int j) { int k。 LiString *str,*p=snext,*q,*r。 str=(LiString *)malloc(sizeof(LiString))。 r=str。 if (i=0 || iStrLength(s) || j0 || i+j1StrLength(s)) { printf(參數(shù)不正確 \n)。 return str。 /*參數(shù)不正確時返回空串 */ } for (k=0。ki1。k++) /*將 s的前 i1個結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。qnext=NULL。 rnext=q。r=q。p=pnext。 } for (k=0。kj。k++) /*讓 p沿 next跳 j個結點 */ p=pnext。 while (p!=NULL) /*將 *p及其后的結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。qnext=NULL。 rnext=q。r=q。p=pnext。 } rnext=NULL。 return str。 } (9) RepStr(s,i,j,t) 在串 s中 ,將第 i(1≤i≤StrLength(s))個字符開始的 j個字符構成的子串用串 t替換 ,并返回產生的新串 。 LiString *RepStr(LiString *s,int i,int j,LiString *t) { int k。 LiString *str,*p=snext,*p1=tnext,*q,*r。 str=(LiString *)malloc(sizeof(LiString))。 r=str。 if (i=0 || iStrLength(s) || j0 || i+j1StrLength(s)) { printf(參數(shù)不正確 \n)。 return str。 /*參數(shù)不正確時返回空串 */ } for (k=0。ki1。k++) /*將 s的前 i1個結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。qnext=NULL。 rnext=q。r=q。p=pnext。 } for (k=0。kj。k++) /*讓 p沿 next跳 j個結點 */ p=pnext。 while (p1!=NULL) /*將 t的所有結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=p1data。qnext=NULL。 rnext=q。r=q。p1=p1next。 } while (p!=NULL) /*將 *p及其后的結點復制到 str*/ { q=(LiString *)malloc(sizeof(LiString))。 qdata=pdata。qnext=NULL。 rnext=q。r=q。