c#常用數據結構解析 http://blog.csdn.net/suifcd/article/details/42869341談談在平時使用U3D時經常用到的數據結構和各種數據結構的應用場景吧。1.幾種常見的數據結構 這裡主要總結下小匹夫在工作中常碰到的幾種數據結構:Array,ArrayList, ...
c#常用數據結構解析
http://blog.csdn.net/suifcd/article/details/42869341
談談在平時使用U3D時經常用到的數據結構和各種數據結構的應用場景吧。
1.幾種常見的數據結構
這裡主要總結下小匹夫在工作中常碰到的幾種數據結構:Array,ArrayList,List<T>,LinkedList<T>,Queue<T>,Stack<T>,Dictionary<K,T>
數組Array:
數組是最簡單的數據結構。其具有如下特點:
數組存儲在連續的記憶體上。
數組的內容都是相同類型。
數組可以直接通過下標訪問。
數組Array的創建:
int size = 5;
int[] test = new int[size];
創建一個新的數組時將在 CLR 托管堆中分配一塊連續的記憶體空間,來盛放數量為size,類型為所聲明類型的數組元素。如果類型為值類型,則將會有size個未裝箱的該類型的值被創建。如果類型為引用類型,則將會有size個相應類型的引用被創建。
由於是在連續記憶體上存儲的,所以它的索引速度非常快,訪問一個元素的時間是恆定的也就是說與數組的元素數量無關,而且賦值與修改元素也很簡單。
string[] test2 = new string[3];
//賦值
test2[0] = "chen";
test2[1] = "j";
test2[2] = "d";
//修改
test2[0] = "chenjd";
但是有優點,那麼就一定會伴隨著缺點。由於是連續存儲,所以在兩個元素之間插入新的元素就變得不方便。而且就像上面的代碼所顯示的那樣,聲明一個新的數組時,必須指定其長度,這就會存在一個潛在的問題,那就是當我們聲明的長度過長時,顯然會浪費記憶體,當我們聲明長度過短的時候,則面臨這溢出的風險。這就使得寫代碼像是投機,小匹夫很厭惡這樣的行為!針對這種缺點,下麵隆重推出ArrayList。
ArrayList:
為瞭解決數組創建時必須指定長度以及只能存放相同類型的缺點而推出的數據結構。ArrayList是System.Collections命名空間下的一部分,所以若要使用則必須引入System.Collections。正如上文所說,ArrayList解決了數組的一些缺點。
不必在聲明ArrayList時指定它的長度,這是由於ArrayList對象的長度是按照其中存儲的數據來動態增長與縮減的。
ArrayList可以存儲不同類型的元素。這是由於ArrayList會把它的元素都當做Object來處理。因而,加入不同類型的元素是允許的。
ArrayList的操作:
ArrayList test3 = new ArrayList();
//新增數據
test3.Add("chen");
test3.Add("j");
test3.Add("d");
test3.Add("is");
test3.Add(25);
//修改數據
test3[4] = 26;
//刪除數據
test3.RemoveAt(4);
說了那麼一堆”優點“,也該說說缺點了吧。為什麼要給”優點”打上引號呢?那是因為ArrayList可以存儲不同類型數據的原因是由於把所有的類型都當做Object來做處理,也就是說ArrayList的元素其實都是Object類型的,辣麽問題就來了。
ArrayList不是類型安全的。因為把不同的類型都當做Object來做處理,很有可能會在使用ArrayList時發生類型不匹配的情況。
如上文所訴,數組存儲值類型時並未發生裝箱,但是ArrayList由於把所有類型都當做了Object,所以不可避免的當插入值類型時會發生裝箱操作,在索引取值時會發生拆箱操作。這能忍嗎?
註:為何說頻繁的沒有必要的裝箱和拆箱不能忍呢?且聽小匹夫慢慢道來:所謂裝箱 (boxing):就是值類型實例到對象的轉換(百度百科)。那麼拆箱:就是將引用類型轉換為值類型咯(還是來自百度百科)。下麵舉個慄子~
//裝箱,將String類型的值FanyoyChenjd賦值給對象。
String info = ”FanyoyChenjd”;
object obj=(object)info;
//拆箱,從Obj中提取值給info
object obj = "FanyoyChenjd";
String info = (String)obj;
那麼結論呢?顯然,從原理上可以看出,裝箱時,生成的是全新的引用對象,這會有時間損耗,也就是造成效率降低。
List<T>泛型List
為瞭解決ArrayList不安全類型與裝箱拆箱的缺點,所以出現了泛型的概念,作為一種新的數組類型引入。也是工作中經常用到的數組類型。和ArrayList很相似,長度都可以靈活的改變,最大的不同在於在聲明List集合時,我們同時需要為其聲明List集合內數據的對象類型,這點又和Array很相似,其實List<T>內部使用了Array來實現。
List<string> test4 = new List<string>();
//新增數據
test4.Add(“Fanyoy”);
test4.Add(“Chenjd”);
//修改數據
test4[1] = “murongxiaopifu”;
//移除數據
test4.RemoveAt(0);
這麼做最大的好處就是即確保了類型安全。也取消了裝箱和拆箱的操作。
它融合了Array可以快速訪問的優點以及ArrayList長度可以靈活變化的優點。
假設各位和小匹夫一樣,在工作中最常使用的一種數據結構就是它。那麼我們是否能再多一點好奇心呢?那就是探究一下,如果我們自己實現一個類似的數據結構,該從何處下手呢?
剛纔說過了,List<T>的內部其實也是一個Array,且是強類型的,所以我們的簡單實現(暫且稱之為EggArray<T>)也秉承這個特點,內部通過一個Array來實現,且需要聲明類型。但是同時我們也看到List<T>繼承和實現了很多介面,比如IEnumerable介面等,而且值類型和引用類型通吃。這裡為了EggArray<T>實現起來輕裝簡行,我們不繼承List<T>繼承的各種介面,同時我們的EggArray只服務於引用類型。
那麼首先明確了,它是一個處理引用類型,且實現了泛型的。那麼定義就出來了:
//EggArray類
//定義
public
class
EggArray<T> where T : class
{
}
那麼下一步呢?該確定它的內部成員了,就先從欄位和屬性開始吧。
屬性&變數
屬性
說明
Capacity EggArray的容量
Count EggArray中的元素個數
items T[],一個Array,因為上一篇文章說過List<T>的內部其實還是Array,所以內部我們也使用Array
//EggArray<T>的屬性&&變數
private int capacity;
private int count;
private T[] items;
public int Count
{
get
{
return this.count;
}
}
public int Capacity
{
get
{
return this.capacity;
}
}
之後呢?好像是需要一個構造函數了。上文也說了,貌似new的時候不需要指定容量呀。那麼我們就把構造函數做成這樣吧。
構造函數:
構造函數 說明
EggArray() 初始化 EggArray<T> 類的新實例,該實例為空並且具有預設初始容量。
EggArray(int32) 初始化 EggArray<T> 類的新實例,該實例為空並且具有指定的初始容量。
//EggArray的構造函數,預設容量為8
public
EggArray() : this(8)
{
}
public
EggArray(int
capacity)
{
this.capacity
= capacity;
this.items
= new
T[capacity];
}
好了,構造函數也說完了,那麼就介紹一下私有方法,因為運行機制全部是有私有方法來運籌的,公共方法只不過是開放給我們的使用的罷了。小匹夫對公共方法的實現沒有興趣,這裡就不做演示了。
剛剛也說了,List<T>是無所謂初始長度的,可以用Add()方法往裡面添加元素,同時也不可能是有一個無限大的空間讓它來存儲,那麼究竟它究竟為何能做到這一點呢?因為有一個能動態調整內部數組大小的方法存在,且調整大小是按照原有長度成倍增長的。我們姑且稱之為Resize。
那麼在進行下麵的內容之前,小匹夫還想先問各位一個問題:
List<int>
test = new
List<int>(){0,1,2,3,4,5,6,7,8,9};
int
count = 0;
for(int
i = 0; i < test.Count; i++)
{
if(i == 1)
test.Remove(test[i]);
count++;
}
Debug.Log (count);
上面這段代碼會輸出什麼呢?答案是9。可能有的盆油會感到奇怪,test進去時長度明明是10啊。就算你中間Remove了一個元素,可為什麼會影響後面的元素呢?(比如把index為1的元素remove掉,原來index為2的元素現在的index就成1了。)感覺亂套有木有?其實這裡List<T>在執行remove的同時,也把內部的數組壓縮了。所以也肯定有一個方法用來壓縮咯。我們姑且稱為Compact。
私有方法
私有方法
說明
Resize 當數組元素個數大於或等於數組的容量時,調用該方法進行擴容,會創建一個新的Array存放數據,“增長因數”為2
Compact 壓縮數組,在Remove時候預設調用
//當數組元素個[/size][/backcolor][/color][i][color=White][backcolor=DarkGreen][size=2]數不小於數組容量時,需要擴容,增長因數growthFactor為2
private
void
Resize()
{
int
capacity = this.capacity
* growthFactor;
if
(this.count
> capacity)
{
this.count
= capacity;
}
T[]
destinationArray = new
T[capacity];
Array.Copy(this.items,
destinationArray, this.count);
this.items
= destinationArray;
this.capacity
= capacity;
}
private
void
Compact()
{
int
num = 0;
for
(int
i = 0; i < this.count;
i++)
{
if
(this.items[i]
== null)
{
num++;
}
else
if
(num > 0)
{
this.items[i
- num] = this.items[i];
this.items[i]
= null;
}
}
this.count
-= num;
}[i][i][i]
LinkedList<T>
也就是鏈表了。和上述的數組最大的不同之處就是在於鏈表在記憶體存儲的排序上可能是不連續的。這是由於鏈表是通過上一個元素指向下一個元素來排列的,所以可能不能通過下標來訪問。如圖
既然鏈表最大的特點就是存儲在記憶體的空間不一定連續,那麼鏈表相對於數組最大優勢和劣勢就顯而易見了。
向鏈表中插入或刪除節點無需調整結構的容量。因為本身不是連續存儲而是靠各對象的指針所決定,所以添加元素和刪除元素都要比數組要有優勢。
鏈表適合在需要有序的排序的情境下增加新的元素,這裡還拿數組做對比,例如要在數組中間某個位置增加新的元素,則可能需要移動移動很多元素,而對於鏈表而言可能只是若幹元素的指向發生變化而已。
有優點就有缺點,由於其在記憶體空間中不一定是連續排列,所以訪問時候無法利用下標,而是必須從頭結點開始,逐次遍歷下一個節點直到尋找到目標。所以當需要快速訪問對象時,數組無疑更有優勢。
綜上,鏈表適合元素數量不固定,需要兩端存取且經常增減節點的情況。
關於鏈表的使用,MSDN上有詳細的例子。
Queue<T>
在Queue<T>這種數據結構中,最先插入在元素將是最先被刪除;反之最後插入的元素將最後被刪除,因此隊列又稱為“先進先出”(FIFO—first in first out)的線性表。通過使用Enqueue和Dequeue這兩個方法來實現對 Queue<T> 的存取。
一些需要註意的地方:
先進先出的情景。
預設情況下,Queue<T>的初始容量為32, 增長因數為2.0。
當使用Enqueue時,會判斷隊列的長度是否足夠,若不足,則依據增長因數來增加容量,例如當為初始的2.0時,則隊列容量增長2倍。
乏善可陳。
關於Queue<T>的使用方法,MSDN上也有相應的例子。
Stack<T>
與Queue<T>相對,當需要使用後進先出順序(LIFO)的數據結構時,我們就需要用到Stack<T>了。
一些需要註意的地方:
後進先出的情景。
預設容量為10。
使用pop和push來操作。
乏善可陳。
同樣,在MSDN你也可以看到大量Stack<T>的例子。
Dictionary<K,T>
字典這東西,小匹夫可是喜歡的不得了。看官們自己也可以想想字典是不是很招人喜歡,創建一個字典之後就可以往裡面扔東西,增加、刪除、訪問那叫一個快字了得。但是直到小匹夫日前看了一個大神的文章,才又想起了那句話“啥好事咋能讓你都占了呢”。那麼字典背後到底隱藏著什麼迷霧,撥開重重迷霧之後,是否才是真相?且聽下回分。。。等等,應該是下麵就讓我們來分析一下字典吧。
提到字典就不得不說Hashtable哈希表以及Hashing(哈希,也有叫散列的),因為字典的實現方式就是哈希表的實現方式,只不過字典是類型安全的,也就是說當創建字典時,必須聲明key和item的類型,這是第一條字典與哈希表的區別。關於哈希表的內容推薦看下這篇博客哈希表。關於哈希,簡單的說就是一種將任意長度的消息壓縮到某一固定長度,比如某學校的學生學號範圍從00000~99999,總共5位數字,若每個數字都對應一個索引的話,那麼就是100000個索引,但是如果我們使用後3位作為索引,那麼索引的範圍就變成了000~999了,當然會衝突的情況,這種情況就是哈希衝突(Hash Collisions)了。扯遠了,關於具體的實現原理還是去看小匹夫推薦的那篇博客吧,當然那篇博客上面那個大大的轉字也是蠻刺眼的。。。
回到Dictionary<K,T>,我們在對字典的操作中各種時間上的優勢都享受到了,那麼它的劣勢到底在哪呢?對嘞,就是空間。以空間換時間,通過更多的記憶體開銷來滿足我們對速度的追求。在創建字典時,我們可以傳入一個容量值,但實際使用的容量並非該值。而是使用“不小於該值的最小質數來作為它使用的實際容量,最小是3。”(老趙),當有了實際容量之後,並非直接實現索引,而是通過創建額外的2個數組來實現間接的索引,即int[] buckets和Entry[] entries兩個數組(即buckets中保存的其實是entries數組的下標),這裡就是第二條字典與哈希表的區別,還記得哈希衝突嗎?對,第二個區別就是處理哈希衝突的策略是不同的!字典會採用額外的數據結構來處理哈希衝突,這就是剛纔提到的數組之一buckets桶了,buckets的長度就是字典的真實長度,因為buckets就是字典每個位置的映射,然後buckets中的每個元素都是一個鏈表,用來存儲相同哈希的元素,然後再分配存儲空間。
因此,我們面臨的情況就是,即便我們新建了一個空的字典,那麼伴隨而來的是2個長度為3的數組。所以當處理的數據不多時,還是慎重使用字典為好,很多情況下使用數組也是可以接受的。
2.幾種常見數據結構的使用情景
Array 需要處理的元素數量確定並且需要使用下標時可以考慮,不過建議使用List<T>
ArrayList 不推薦使用,建議用List<T>
List<T>泛型List 需要處理的元素數量不確定時 通常建議使用
LinkedList<T> 鏈表適合元素數量不固定,需要經常增減節點的情況,2端都可以增減
Queue<T> 先進先出的情況
Stack<T> 後進先出的情況
Dictionary<K,T> 需要鍵值對,快速操作
========
C#數據結構一:基礎知識
http://www.cnblogs.com/walkingp/archive/2010/04/25/1720823.html
在學習數據結構之前先要學習幾個相關的概念及術語1、數據(Data):數據是外部世界信息的載體,它能被電腦識別、存儲和加工處理,是電腦程式加工的原料。2、數據元素(Data Element)和數據項:數據元素是數據的基本單位,有時也被稱為元素、結點、頂點、記錄等。一個數據元素可由若幹個數據項組成;數據項是不可分割的、含有獨立意義的最小數據單位,數據項有時也稱為欄位(Field)或域(Domain).之間關係為數據項組成數據元素,數據元素組成數據(,數據組成文件)。使用資料庫模型來舉例說明:3、數據對象(Data Object):性質相同的數據元素的集合,是數據的一個子集,例如字母表對象{a,b,c,…x,y,z}4、數據類型(Data Type):數據的取值範圍和對數據進行操作的總和。數據類型規定了程式中對象的特性;程式中每個變數、常量或表達式的結果都應該屬於某種確定的數據類型。數據類型可分可兩類:一類是非結構的原子類型,如C#的基本類型;另一類是結構類型,其成分由多個結構類型組成,可以分解;如C#的數組類型。5、數據結構(Data Struct):相互之間存在一種或多種關係 的數據元素的集合。通常有4類基本數據結構:1)集合(Set)2)線性結構(Linear Structure)3)樹形結構(True Structure)4)圖狀結構(Graphic Structure)數據結構(Data Structrue)簡記為DS,是一個二元組,DS=(D,S),其中D為數據元素的有限集合,R是數據元素之間關係的有限集合。6、演算法(Algorithm):是對某一特定類型的問題的求解步驟的一種描述,是指令的有限序列。它具有有窮性(Finity)、確定性(Unambiguousness)、輸入(Input)、輸出(Output)和有效性(Realizability)。針對演算法優劣的評價標準包括正確性(Correctness)、可讀性(Readability)、健壯性(Robustness魯棒性)、運行時間(Running Time)和占用空間(Storage Space)。7、演算法的時間複雜度(Time Complexity):指演算法的運行時間與問題規模的對應關係。通常把演算法中基本操作重覆執行的次數作為演算法的時間複雜度。它是與問題規模n相關的函數。記作T(n)=O(f(n)),例如T(n)=n(n+1),推薦一篇好文http://www.matrix67.com/blog/archives/5298、高等數學相關基礎知識計量單位(Unit):位元組為B,位縮寫為b,兆位元組為MB,千位元組縮寫為KB階乘函數(Factorial Function):5!=5*4*3*2*1=120,特別地,0!=1取下整和取上整(Floor and Ceiling):⌊3.4⌋=3(下整) ,⌈3.4⌉=4(上整)取模操作符(Modulus):n=q*m+r ⇒m=n/q對數(Logarithm):若ab=N,那麼數b叫做以a為底N的對數,記作logaN=b,其中a叫做對數的底數,N叫做真數。遞歸(Recursive):演算法調用自己或間接調用自己。
在學習數據結構之前先要學習幾個相關的概念及術語
1、數據(Data):數據是外部世界信息的載體,它能被電腦識別、存儲和加工處理,是電腦程式加工的原料。
2、數據元素(Data Element)和數據項:數據元素是數據的基本單位,有時也被稱為元素、結點、頂點、記錄等。一個數據元素可由若幹個數據項組成;數據項是不可分割的、含有獨立意義的最小數據單位,數據項有時也稱為欄位(Field)或域(Domain).之間關係為數據項組成數據元素,數據元素組成數據(,數據組成文件)。使用資料庫模型來舉例說明:
3、數據對象(Data Object):性質相同的數據元素的集合,是數據的一個子集,例如字母表對象{a,b,c,…x,y,z}
4、數據類型(Data Type):數據的取值範圍和對數據進行操作的總和。數據類型規定了程式中對象的特性;程式中每個變數、常量或表達式的結果都應該屬於某種確定的數據類型。數據類型可分可兩類:一類是非結構的原子類型,如C#的基本類型;另一類是結構類型,其成分由多個結構類型組成,可以分解;如C#的數組類型
。5、數據結構(Data Struct):相互之間存在一種或多種關係 的數據元素的集合。通常有4類基本數據結構:
1)集合(Set)
2)線性結構(Linear Structure)
3)樹形結構(True Structure)
4)圖狀結構(Graphic Structure)
數據結構(Data Structrue)簡記為DS,是一個二元組,DS=(D,S),其中D為數據元素的有限集合,R是數據元素之間關係的有限集合。
6、演算法(Algorithm):是對某一特定類型的問題的求解步驟的一種描述,是指令的有限序列。它具有有窮性(Finity)、確定性(Unambiguousness)、輸入(Input)、輸出(Output)和有效性(Realizability)。針對演算法優劣的評價標準包括正確性(Correctness)、可讀性(Readability)、健壯性(Robustness魯棒性)、運行時間(Running Time)和占用空間(Storage Space)。
7、演算法的時間複雜度(Time Complexity):指演算法的運行時間與問題規模的對應關係。通常把演算法中基本操作重覆執行的次數作為演算法的時間複雜度。它是與問題規模n相關的函數。記作T(n)=O(f(n)),例如T(n)=n(n+1)。
常見時間複雜度舉例:
1)、O(n)
x=n;
y=0;
while(y<x){
y=y+1;
}
2)、O(n2)
for(int i=1;i<n;++i){
for(int j=0;j<n;++j){
A[i][j]=i*j;
}
}
3)、O(\sqrt{n})
x=n;
y=0;
while(x>=(y+1)*(y+1)){//即x=y2+1
y=y+1;
}
關於演算法複雜度,推薦一篇好文http://www.matrix67.com/blog/archives/529
8、高等數學相關基礎知識
計量單位(Unit):位元組為B,位縮寫為b,兆位元組為MB,千位元組縮寫為KB
階乘函數(Factorial Function):5!=5*4*3*2*1=120,特別地,0!=1
取下整和取上整(Floor and Ceiling):⌊3.4⌋=3(下整) ,⌈3.4⌉=4(上整)
取模操作符(Modulus):n=q*m+r ⇒m=n/q
對數(Logarithm):若ab=N,那麼數b叫做以a為底N的對數,記作logaN=b,其中a叫做對數的底數,N叫做真數。
遞歸(Recursive):演算法調用自己或間接調用自己。
C#數據結構系列文章:
1、基礎知識
2、順序表Sequence List
3、單鏈表Singly Linked List
4、雙向鏈表Double Linked List
5、迴圈鏈表Circular Linked List
6、棧Stack
7、隊列Queue
8、串
9、數組Array
10、樹Tree