[工學(xué)]數(shù)據(jù)結(jié)構(gòu)——第4章串c(已修改)
2024-10-28 18:32 本頁面
【正文】 第 4章 串 串的基本概念 什么是串 串（或字符串）是由零個或多個字符組成的有限序列。記作 str=a1a2… an（ n≥0），其中 str是串名，用雙引號括起來的字符序列為串值，引號是界限符， ai（ 1≤i≤n）是一個任意字符（字母、數(shù)字或其他字符），它稱為串的元素，是構(gòu)成串的基本單位，串中所包含的字符個數(shù) n稱為串的長度，當(dāng) n=0時，稱為 空串 。 一個串中任意連續(xù)的字符組成的子序列稱為該串的 子串 ，例如， a、 ab、 abc和 abcd等都是 abcde的子串。包含子串的串相應(yīng)地稱為主串。 若兩個串的長度相等且對應(yīng)字符都相等，則稱兩個串是相等 的。當(dāng)兩個串不相等時，可按“字典順序”區(qū)分大小。 【 例 】 設(shè) str是一個長度為 n的串，其中的字符各不相同，則 str中的所有子串個數(shù)是多少？ 解： 對于這樣的串 str，有： 空串是其子串，計 1個 每個字符構(gòu)成的串是其子串，計 n個 每 2個連續(xù)的字符構(gòu)成的串是其子串，計 n1個 每 3個連續(xù)的字符構(gòu)成的串是其子串，計 n2個 … 每 n1個連續(xù)的字符構(gòu)成的串是其子串，計 2個 str是其自身的子串，計 1個 所有子串個數(shù) =1+n+(n1)+…+2+1= n(n+1)/2+1。例如，str=software的子串個數(shù) =(8 9)/2+1=37。 串的抽象數(shù)據(jù)類型 ADT String { 數(shù)據(jù)對象： D={ai | 1≤i≤n,n≥0,ai為 char類型 } 數(shù)據(jù)關(guān)系： R={r} r={ai,ai+1 | ai,ai+1∈ D, i=1,…,n 1} 基本運(yùn)算： void StrAssign(cstr)：由字符串常量 cstr創(chuàng)建一個串，即生成其值等于cstr的串。 void StrCopy(t)：串復(fù)制，由串 t復(fù)制產(chǎn)生一個串。 int StrLength()：求串長，返回當(dāng)前串中字符個數(shù)。 String Concat(t)：串連接，返回一個當(dāng)前串和串 t連接后的結(jié)果。 String SubStr(i,j)：求子串，返回當(dāng)前串中從第 i個字符開始的 j個連續(xù)字符組成的子串。 String InsStr(i,s)：串插入，返回串 s插入到當(dāng)前串的第 i個位置后的子串。 String DelStr(i,j)：串刪除，返回當(dāng)前串中刪去從第 i個字符開始的 j個字符后的結(jié)果。 String RepStr(i,j,s)：串替換，返回用串 s替換當(dāng)前串中第 i個字符開始的 j個字符后的結(jié)果。 DispStr()：串輸出，輸出當(dāng)前串的所有元素值。 } 串的存儲結(jié)構(gòu) 串的順序存儲結(jié)構(gòu)－順序串 和順序表一樣，用一個 data數(shù)組（大小為 MaxSize）和一個整型變量 length來表示一個順序串， length表示 data數(shù)組中實際字符的個數(shù)。 定義順序串類 SqStringClass如下： class SqStringClass { const int MaxSize=100。 public char[] data。 //存放串中字符 public int length。 //存放串長 public SqStringClass() //構(gòu)造函數(shù) ,用于順序串的初始化 { data=new char[MaxSize]。 length=0。 } //順序串的基本運(yùn)算 } 下面討論在順序串上實現(xiàn)串基本運(yùn)算的算法。 （ 1）建立串 StrAssign(cstr) 由一個字符串常量 cstr建立一個串，即生成一個其值等于 cstr的串。對應(yīng)的算法如下： public void StrAssign(string cstr) { int i。 for (i=0。i。i++) data[i]=cstr[i]。 length=i。 } 例如， cstr=“abcdef”，執(zhí)行 StrAssign(cstr)方法的結(jié)果如下圖所示。 c str ： 串對象 s ： a b c d e f b a d c f e 6 … s . S trA ss ig n ( c str ) d a ta len g th （ 2）串復(fù)制 StrCopy(t) 將串 t復(fù)制給當(dāng)前串對象。對應(yīng)的算法如下： public void StrCopy(SqStringClass t) { int i。 for (i=0。i。i++) data[i]=[i]。 length=。 } （ 3）求串長度 StrLength() 返回當(dāng)前串中的字符個數(shù)。對應(yīng)的算法如下： public int StrLength() { return length。 } （ 4）串連接 Concat(t) 將當(dāng)前串和串 t的所有字符連接在一起形成的新串，并返回這個新串。對應(yīng)的算法如下： public SqStringClass Concat(SqStringClass t) { SqStringClass nstr=new SqStringClass()。 //新建一個空串 int i。 =length+。 for (i=0。ilength。i++)//將當(dāng)前串 data[0..]?到 nstr [i]=data[i]。 for (i=0。i。i++)//將 [0..]?nstr [length+i]=[i]。 return nstr。 //返回新串 nstr } 例如，串對象 s和 t連接產(chǎn)生新串對象 s1的過程如下圖所示。 串對象 s ： 串對象 t ： b a d c 2 1 7 … 串對象 s 1 ： s1 = n c a t ( t ) d a ta len g th b a d c … 4 d a ta len g th 2 1 3 3 … d a ta len g th 3 （ 5）求子串 SubStr(i,j) 產(chǎn)生由當(dāng)前串中第 i個字符開始的、連續(xù) j個字符組成的子串，并返回這個子串。當(dāng)參數(shù) i、 j不正確時返回一個空串。對應(yīng)的算法如下： public SqStringClass SubStr(int i,int j) { SqStringClass nstr=new SqStringClass()。 //新建一個空串 int k。 if (i=0 || ilength || j0 || i+j1length) return nstr。 //參數(shù)不正確時返回空串 for (k=i1。ki+j1。k++) //將 [i..i+j1]?nstr [ki+1]=data[k]。 =j。 return nstr。 //返回新建的順序串 } （ 6）串插入 InsStr(i,s) 將串 s插入到當(dāng)前串的第 i個位置中產(chǎn)生一個新串，并返回這個新串。當(dāng)參數(shù)不正確時返回一個空串。對應(yīng)的算法如下： public SqStringClass InsStr(int i,SqStringClass s) { int j。 SqStringClass nstr=new SqStringClass()。 //新建一個空串 if (i=0 || ilength+1) //參數(shù)不正確時返回空串 re
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1