C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘六

黃金屋1 2017-04-10

展開全文

這節(jié)我們討論兩種用的蠻多的數(shù)據(jù)結(jié)構(gòu)——串和數(shù)組

首先，老樣子，什么是串，這里串不是吃的牛肉串，羊肉串，而是字符串。在應(yīng)用程序中使用最頻繁的類型是字符串。字符串簡稱串，是一種特殊的線性表，其特殊性在于串中的數(shù)據(jù)元素是一個個的字符。字符串在計算機的許多方面應(yīng)用很廣。如在匯編和高級語言的編譯程序中，源程序和目標程序都是字符串?dāng)?shù)據(jù)。在事務(wù)處理程序中，顧客的信息如姓名、地址等及貨物的名稱、產(chǎn)地和規(guī)格等，都被作為字符串來處理。另外，字符串還具有自身的一些特性。因此，把字符串作為一種數(shù)據(jù)結(jié)構(gòu)來研究。具體情況，如圖所示，顧客信息處理的字符串。

串有哪些基本的概念了，串(String)由 n(n≥0)字符組成的有限序列。一般記為： S=”c1c2…cn” (n≥0) 其中，S是串名，雙引號作為串的定界符，用雙引號引起來的字符序列是串

值。ci（1≤i≤n）可以是字母、數(shù)字或其它字符，n為串的長度，當(dāng)n=0 時，稱為空串(Empty String)。串中任意個連續(xù)的字符組成的子序列稱為該串的子串(Substring)。包含子串的串相應(yīng)地稱為主串。子串的第一個字符在主串中的位置叫子串的位置。如串s1”abcdefg”，它的長度是 7，串s2”cdef”的長度是 4，s2是s1的子串，s2的位置是 3。
如果兩個串的長度相等并且對應(yīng)位置的字符都相等，則稱這兩個串相等。而在 C#中，比較兩個串是否相等還要看串的語言文化等信息。所謂語言文化，是指中文的字符串和中文字符串進行了比較，英文字符串與英文字符串進行了比較。父串子串的示意圖：

串是如何存儲及類定義的了，由于串中的字符都是連續(xù)存儲的，而在 C#中串具有恒定不變的特性，即字符串一經(jīng)創(chuàng)建，就不能將其變長、變短或者改變其中任何的字符。相應(yīng)的示意圖如下所示：

所以，這里不討論串的鏈式存儲，也不用接口來表示串的操作。同樣，把串看作是一個類，類名為 StringDS。取名為 StringDS 是為了和 C#自身的字符串類 String 相區(qū)別。類
StringDS 只有一個字段，即存放串中字符序列的數(shù)組 data。由于串的運算有很多，在類 StringDS 中只包含部分基本的運算增加，清空，球長度等等操作。給串類 StringDS 的源代碼實現(xiàn)如下所示：

public class StringDS
{
private char[] data; //字符數(shù)組

//索引器
public char this[int index]
{
get
{
return data[index];
}
}

//構(gòu)造器
public StringDS(char[] arr)
{

data = new char[arr.Length];
for(int i = 0; i < arr.Length; ++i)
{
data[i] = arr[i];
}
}

//構(gòu)造器
public StringDS(StringDS s)
{
for(int i = 0; i < arr.Length; ++i)
{
data[i] = s[i];
}
}

//構(gòu)造器
public StringDS(int len)
{
char[] arr = new char[len];
data = arr;
}

//求串長
public int GetLength()
{
return data.Length;
}

求串的長度就是求串中字符的個數(shù)，可以通過求數(shù)組 data 的長度來求串的長度。算法的時間復(fù)雜度是O(1),具體情況，如圖所示：

//串比較
public int Compare(StringDS s)
{
int len=((this.GetLength()<=s.GetLength())?
this.GetLength():s.GetLength());
int i = 0;
for (i = 0; i < len; ++i)
{
if (this[i] != s[i])
{
break;
}
}

if (i <= len)

{
if (this[i] < s[i])
{
return -1;
}
else if (this[i] > s[i])
{
return 1;
}
}
else if(this.GetLength() == s.GetLength())
{
return 0;
}
else if (this.GetLength() < s.GetLength())
{
return -1;
}

return 1;
}

如果兩個串的長度相等并且對應(yīng)位置的字符相同，則串相等，返回 0；如果串 s 對應(yīng)位置的字符大于該串的字符或者如果串 s 的長度大于該串，而在該串的長度返回內(nèi)二者對應(yīng)位置的字符相同，則返回-1，該串小于串 s；其余情況返回1，該串大于串 s。該算法的時間復(fù)雜度是O(n) 涉及到字符串?dāng)?shù)組的遍歷。具體偽代碼，如圖所示：

//求子串
public StringDS SubString(int index, int len)
{
if ((index<0) || (index>this.GetLength()–1)
|| (len<0) || (len>this.GetLength()–index))
{
Console.WriteLine("Position or Length is error!");
return null;
}

StringDS s = new StringDS(len);

for (int i = 0; i < len; ++i)
{
s[i] = this[i + index-1];
}

return s;
}

{
StringDS s1 = new StringDS(this.GetLength() +
s.GetLength());

for(int i = 0; i < this.GetLength(); ++i)
{
s1.data[i] = this[i];
}

for(int j = 0; j < s.GetLength(); ++j)
{
s1.data[this.GetLength() + j] = s[j];
}

return s1;
}

從主串的index位置起找長度為len的子串，若找到，返回該子串，否則，返回一個空串。涉及字符串的遍歷，所以時間復(fù)雜度是O(n) 相應(yīng)圖如圖所示：

//串插入
public StringDS Insert(int index, StringDS s)
{
int len = s.GetLength();
int len2 = len + this.GetLength();
StringDS s1 = new StringDS(len2);

if (index < 0 || index > this.GetLength() - 1)
{
Console.WriteLine("Position is error!");
return null;
}

for (int i = 0; i < index; ++i)
{
s1[i] = this[i];
}

for(int i = index; i < index + len ; ++i)
{
s1[i] = s[i - index];
}

for (int i = index + len; i < len2; ++i)
{
s1[i] = this[i - len];

return s1;
}

串插入是在一個串的位置index處插入一個串s。如果位置符合條件，則該操作返回一個新串，新串的長度是該串的長度與串s的長度之和，新串的第1部分是該串的開始字符到第index之間的字符，第2部分是串s,第3部分是該串從index位置字符到該串的結(jié)束位置處的字符。如果位置不符合條件，則返回一個空串。時間復(fù)雜度是O(n),具體操作如圖所示：

//串刪除
public StringDS Delete(int index, int len)
{
if ((index<0) || (index>this.GetLength()-1)
|| (len<0) || (len>this.GetLength()-index))
{
Console.WriteLine("Position or Length is error!");
return null;
}

StringDS s = new StringDS(this.GetLength() - len);

for (int i = 0; i < index; ++i)
{
s[i] = this[i];
}

for (int i = index + len; i < this.GetLength(); ++i)
{
s[i] = this[i];
}

return s;
}

串刪除是從把串的第index位置起連續(xù)的len個字符的子串從主串中刪除掉。如果位置和長度符合條件，則該操作返回一個新串，新串的長度是原串的長度減去len，新串的前部分是原串的開始到第index個位置之間的字符，后部分是原串從第index+len位置到原串結(jié)束的字符。如果位置和長度不符合條件，則返回一個空串。相應(yīng)的時間復(fù)雜度是O(n),相應(yīng)情況，如圖所示:

}

這就是我對串的理解，我們看看數(shù)組的理解。

什么是數(shù)組。所謂數(shù)組是數(shù)組是一種常用的數(shù)據(jù)結(jié)構(gòu)，可以看作是線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點是結(jié)構(gòu)中的數(shù)據(jù)元素可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，甚至可以是數(shù)組，但屬于同一數(shù)據(jù)類型。數(shù)組在許多高級語言里面都被作為固定類型來使用。

數(shù)組是 n(n≥1)個相同數(shù)據(jù)類型的數(shù)據(jù)元素的有限序列。一維數(shù)組可以看作是一個線性表，二維數(shù)組可以看作是“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作是“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依次類推。圖是一個 m 行 n 列的二維數(shù)組。

數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素通過唯一的下標來標識和訪問。通常，一個數(shù)組一經(jīng)定義，每一維的大小及上下界都不能改變。所以，在數(shù)組上不能進行插入、刪除數(shù)據(jù)元素等操作。數(shù)組上的操作一般有：

1、取值操作：給定一組下標，讀其對應(yīng)的數(shù)據(jù)元素；算法的復(fù)雜度是O(1)

2、賦值操作：給定一組下儲或修改與其對應(yīng)的數(shù)據(jù)元素；算法的復(fù)雜度是O(1)
3、清空操作：將數(shù)組中的所有數(shù)據(jù)元素清除；算法的復(fù)雜度是O(1)
4、復(fù)制操作：將一個數(shù)組的數(shù)據(jù)元素賦給另外一個數(shù)組；算法的復(fù)雜度是O(n)
5、排序操作：對數(shù)組中的數(shù)據(jù)元素進行排序，這要求數(shù)組中的數(shù)據(jù)元素是可排序的；希爾排序，冒泡排序等等，算法的復(fù)雜度是O(n2)
6、反轉(zhuǎn)操作：反轉(zhuǎn)數(shù)組中數(shù)據(jù)元素的順序。以前提過，請見了C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘一。

什么是數(shù)組的內(nèi)存映象，

通常，采用順序存儲結(jié)構(gòu)來存儲數(shù)組中的數(shù)據(jù)元素，因為數(shù)組中的元素要求連續(xù)存放。本質(zhì)上，計算機的內(nèi)存是一個一維數(shù)組，內(nèi)存地址就是數(shù)組的下標。所以，對于一維數(shù)組，可根據(jù)數(shù)組元素的下標得到它的存儲地址，也可根據(jù)下標來訪問一維數(shù)組中的元素。而對于多維數(shù)組，需要把多維的下標表達式轉(zhuǎn)換成一維的下標表達式。當(dāng)行列固定后，要用一組連續(xù)的存儲單元存放數(shù)組中的元素，有一個次序約定問題，這產(chǎn)生了兩種存儲方式：一種是以行序為主序（先行后列）的順序存放，另一種是以列序為主序（先列后行）的順序存放。下圖給出了圖中的二維數(shù)組的兩種存放方式示意圖。

下面按元素的下標求地址：當(dāng)以行序為主序進行存儲時，設(shè)數(shù)組的基址是Loc(a11)，每個數(shù)據(jù)元素占w個存儲單元，則a11的物理地址可由下式計算： Loc(aij)= Loc(a11)+((i-1)*n+j-1)*w 這是因為數(shù)組元素aij的前面有i-1行，每一行有n個數(shù)據(jù)元素，在第i行中aij的前面還有j-1個元素。如圖所示