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

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

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

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

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

所以，這里不討論串的鏈?zhǔn)酱鎯?chǔ)，也不用接口來(lái)表示串的操作。同樣，把串看作是一個(gè)類，類名為 StringDS。取名為 StringDS 是為了和 C#自身的字符串類 String 相區(qū)別。類
StringDS 只有一個(gè)字段， 即存放串中字符序列的數(shù)組 data。 由于串的運(yùn)算有很多，在類 StringDS 中只包含部分基本的運(yùn)算增加，清空，球長(zhǎng)度等等操作。給串類 StringDS 的 源代碼實(shí)現(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;
}

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

求串的長(zhǎng)度就是求串中字符的個(gè)數(shù)，可以通過(guò)求數(shù)組 data 的長(zhǎng)度來(lái)求串的長(zhǎng)度。算法的時(shí)間復(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;
}

如果兩個(gè)串的長(zhǎng)度相等并且對(duì)應(yīng)位置的字符相同，則串相等，返回 0；如果串 s 對(duì)應(yīng)位置的字符大于該串的字符或者如果串 s 的長(zhǎng)度大于該串， 而在該串的長(zhǎng)度返回內(nèi)二者對(duì)應(yīng)位置的字符相同，則返回-1，該串小于串 s；其余情況返回1，該串大于串 s。該算法的時(shí)間復(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位置起找長(zhǎng)度為len的子串，若找到，返回該子串，否則，返回一個(gè)空串。涉及字符串的遍歷，所以時(shí)間復(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;
} 

串插入是在一個(gè)串的位置index處插入一個(gè)串s。如果位置符合條件，則該操作返回一個(gè)新串，新串的長(zhǎng)度是該串的長(zhǎng)度與串s的長(zhǎng)度之和，新串的第1部分是該串的開(kāi)始字符到第index之間的字符，第2部分是串s,第3部分是該串從index位置字符到該串的結(jié)束位置處的字符。如果位置不符合條件，則返回一個(gè)空串。時(shí)間復(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個(gè)字符的子串從主串中刪除掉。如果位置和長(zhǎng)度符合條件，則該操作返回一個(gè)新串，新串的長(zhǎng)度是原串的長(zhǎng)度減去len，新串的前部分是原串的開(kāi)始到第index個(gè)位置之間的字符，后部分是原串從第index+len位置到原串結(jié)束的字符。如果位置和長(zhǎng)度不符合條件，則返回一個(gè)空串。相應(yīng)的時(shí)間復(fù)雜度是O(n),相應(yīng)情況，如圖所示:

}

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

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

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

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

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

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

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

通常，采用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)組中的數(shù)據(jù)元素，因?yàn)閿?shù)組中的元素要求連續(xù)存放。本質(zhì)上，計(jì)算機(jī)的內(nèi)存是一個(gè)一維數(shù)組，內(nèi)存地址就是數(shù)組的下標(biāo)。所以，對(duì)于一維數(shù)組，可根據(jù)數(shù)組元素的下標(biāo)得到它的存儲(chǔ)地址，也可根據(jù)下標(biāo)來(lái)訪問(wèn)一維數(shù)組中的元素。而對(duì)于多維數(shù)組，需要把多維的下標(biāo)表達(dá)式轉(zhuǎn)換成一維的下標(biāo)表達(dá)式。當(dāng)行列固定后，要用一組連續(xù)的存儲(chǔ)單元存放數(shù)組中的元素，有一個(gè)次序約定問(wèn)題， 這產(chǎn)生了兩種存儲(chǔ)方式： 一種是以行序?yàn)橹餍?（先行后列）的順序存放，另一種是以列序?yàn)橹餍颍ㄏ攘泻笮校┑捻樞虼娣拧Ｏ聢D給出了圖中的二維數(shù)組的兩種存放方式示意圖。

下面按元素的下標(biāo)求地址： 當(dāng)以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)時(shí)，設(shè)數(shù)組的基址是Loc(a11)，每個(gè)數(shù)據(jù)元素占w個(gè)存儲(chǔ)單元，則a11的物理地址可由下式計(jì)算： Loc(aij)= Loc(a11)+((i-1)*n+j-1)*w 這是因?yàn)閿?shù)組元素aij的前面有i-1行， 每一行有n個(gè)數(shù)據(jù)元素， 在第i行中aij的前面還有j-1個(gè)元素。 如圖所示

當(dāng)以列序?yàn)橹餍蜻M(jìn)行存儲(chǔ)時(shí)，則a11的物理地址可由下式計(jì)算： Loc(aij)= Loc(a11)+((j-1)*m+i-1)*w （4-2） 這是因?yàn)閿?shù)組元素aij的前面有j-1列， 每一列有m個(gè)數(shù)據(jù)元素， 在第j列中aij的前面還有i-1個(gè)元素。 由以上的公式可知，數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)，一旦確定了數(shù)組各維的長(zhǎng)度，就可以計(jì)算任意一個(gè)元素的存儲(chǔ)地址，并且時(shí)間相等。所以，存取數(shù)組中任意一個(gè)元素的時(shí)間也相等，因此，數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。時(shí)間復(fù)雜度是O(n2).相應(yīng)的情況，如圖所示：

這就是我對(duì)數(shù)組的理解