【正文】 +) //將 s的前 i1個結點 ?nstr { q=new LinkNode()。 r = 。以下采用尾插法建立鏈串 nstr并返回。 } =null。 =。 =q。 r=q。 ki。 LinkNode p=,p1=,q,r。當 參數(shù)不正確時返回一個空串。 //將 q結點插入到尾部 p=。k++) //將 s的第 i個結點開始的 j個結點 ?nstr { q=new LinkNode()。ki1。 LinkNode p=,q,r。當參數(shù)不正確時返回一個空串。 //將 q結點插入到尾部 p=。 while (p!=null) //將鏈串 t的所有結點 ?nstr { q=new LinkNode()。 =q。//新建一個空串 LinkNode p=,q,r。 //p移到下一個字符結點 } return i。對應的算法如下： public int StrLength() { int i=0。 r=q。 r=head。 //尾結點的 next置為 null } 例如， cstr=“abcdef”，執(zhí)行 StrAssign(cstr)方法的結果如下圖所示。 =cstr[i]。 LinkNode r=head,p。 } //鏈串的基本運算算法 } 下面討論在鏈串上實現(xiàn)串基本運算的算法。 //指向下一個結點 }。 } 串的鏈式存儲結構－鏈串 通常將鏈串中每個結點所存儲的字符個數(shù)稱為結點大小 。 for (i=0。 } 【 例 】 設計一個算法 StrEqueal(s,t)比較兩個順序串 s、t是否相等。 else { for (i=0。 //返回新建的順序串 } （ 9）串輸出 DispStr() 將當前串 s的所有字符構成一個字符串并輸出。klength。 for (k=0。 //新建一個空串 if (i=0 || ilength || i+j1length) //參數(shù)不正確時返回空串 return nstr。 //返回新建的順序串 } （ 8）串替換 RepStr(i,j,s) 將當前串中第 i個字符開始的連續(xù) j個字符用串 s替換而產(chǎn)生一個新串，并返回這個新串。klength。 for (k=0。當參數(shù)不正確時返回一個空串。j++) //將當前串 data[i1..length1]?nstr [+j]=data[j]。j。 for (j=0。當參數(shù)不正確時返回一個空串。k++) //將 [i..i+j1]?nstr [ki+1]=data[k]。 //新建一個空串 int k。 //返回新串 nstr } 例如，串對象 s和 t連接產(chǎn)生新串對象 s1的過程如下圖所示。 for (i=0。 =length+。對應的算法如下： public int StrLength() { return length。i。 } 例如， cstr=“abcdef”，執(zhí)行 StrAssign(cstr)方法的結果如下圖所示。 for (i=0。 length=0。 定義順序串類 SqStringClass如下： class SqStringClass { const int MaxSize=100。 String DelStr(i,j)：串刪除，返回當前串中刪去從第 i個字符開始的 j個字符后的結果。 int StrLength()：求串長，返回當前串中字符個數(shù)。 【 例 】 設 str是一個長度為 n的串，其中的字符各不相同，則 str中的所有子串個數(shù)是多少？ 解： 對于這樣的串 str，有： 空串是其子串，計 1個 每個字符構成的串是其子串，計 n個 每 2個連續(xù)的字符構成的串是其子串，計 n1個 每 3個連續(xù)的字符構成的串是其子串，計 n2個 … 每 n1個連續(xù)的字符構成的串是其子串，計 2個 str是其自身的子串，計 1個 所有子串個數(shù) =1+n+(n1)+…+2+1= n(n+1)/2+1。 一個串中任意連續(xù)的字符組成的子序列稱為該串的 子串 ，例如， a、 ab、 abc和 abcd等都是 abcde的子串。記作 str=a1a2… an（ n≥0），其中 str是串名，用雙引號括起來的字符序列為串值，引號是界限符， ai（ 1≤i≤n）是一個任意字符（字母、數(shù)字或其他字符），它稱為串的元素，是構成串的基本單位，串中所包含的字符個數(shù) n稱為串的長度，當 n=0時，稱為 空串 。當兩個串不相等時，可按“字典順序”區(qū)分大小。 void StrCopy(t)：串復制，由串 t復制產(chǎn)生一個串。 String InsStr(i,s)：串插入，返回串 s插入到當前串的第 i個位置后的子串。 } 串的存儲結構 串的順序存儲結構－順序串 和順序表一樣，用一個 data數(shù)組（大小為 MaxSize）和一個整型變量 length來表示一個順序串， length表示 data數(shù)組中實際字符的個數(shù)。 //存放串長 public SqStringClass() //構造函數(shù) ,用于順序串的初始化 { data=new char[MaxSize]。對應的算法如下： public void StrAssign(string cstr) { int i。 length=i。 for (i=0。 } （ 3）求串長度 StrLength() 返回當前串中的字符個數(shù)。 //新建一個空串 int i。i++)//將當前串 data[0..]?到 nstr [i]=data[i]。 return nstr。對應的算法如下： public SqStringClass SubStr(int i,int j) { SqStringClass nstr=new SqStringClass()。ki+j1。 //返回新建的順序串 } （ 6）串插入 InsStr(i,s) 將串 s插入到當前串的第 i個位置中產(chǎn)生一個新串，并返回這個新串。 //新建一個空串 if (i=0 || ilength+1) //參數(shù)不正確時返回空串 return nstr。 for (j=0。jlength。 //返回新建的順序串 } （ 7）串刪除 DelStr(i,j) 從當前串中刪去第 i個字符開始的連續(xù) j個字符產(chǎn)生一個子串，并返回這個子串。 //新建一個空串 if (i=0 || ilength || i+j1length) //參數(shù)不正確時返回空串 return nstr。 for (k=i+j1。 return nstr。 SqStringClass nstr=new SqStringClass()。k++) //將當前串 data[0..i2]?nstr [k]=data[k]。 for (k=i+j1。 return nstr。 if (length==0) mystr = 空串 。 } return mystr。 if (!=) return false。 return true。 //存放一個字符 public LinkNode next。 //鏈串頭結點 public LinkStringClass() //構造函數(shù) ,用于鏈串初始化