字典是一種利用鍵值對來存儲的數(shù)據(jù)結(jié)構(gòu)。作為一種抽象類， dictionaryBase? 類可以實(shí)現(xiàn)不同的結(jié)構(gòu)

sortedList? 是按照分類順序基于鍵值來存儲鍵值對的，它可以通過引用數(shù)據(jù)結(jié)構(gòu)中的值得索引位置也可以訪問存貯在結(jié)構(gòu)中的數(shù)據(jù)。

Dictionary? 中，存儲在字段中的鍵值對于時間上最為? DictionaryEntry? 對象來存儲的。 DictionaryEntry? 結(jié)構(gòu)提供兩個域，一個用于鍵，一個用于值。對于內(nèi)部而言會把鍵值存儲在 innerHashTable?? 的散列對象中。

?

public?class?IPAddresses?:?DictionaryBase

{

????public?IPAddresses()

????{

????}

????public?void?Add(string?name,?string?ip)

????{

????????base.InnerHashtable.Add(name,?ip);

????}

????public?string?Item(string?name)

????{

????????return?base.InnerHashtable[name].ToString();

????}

????public?void?Remove(string?name)

????{

????????base.InnerHashtable.Remove(name);

????}

}

??static?void?Main()

????{

????????IPAddresses?myIPs?=?new?IPAddresses();

????????myIPs.Add("Mike",?"192.155.12.1");

????????myIPs.Add("David",?"192.155.12.2");

????????myIPs.Add("Bernica",?"192.155.12.3");

????????Console.WriteLine("There?are?"?+?myIPs.Count?+?"?IP?addresses");

????????Console.WriteLine("David's?ip?address:?"?+?myIPs.Item("David"));

????????myIPs.Clear();

????????Console.WriteLine("There?are?"?+?myIPs.Count?+?"?IP?addresses");

????}

class?chapter

{

????static?void?Main()

????{

????????for?(int?i?=?0;?i?<?4;?i++)

????????????Console.WriteLine();

????????IPAddresses?myIPs?=?new?IPAddresses(@"c:\data\ips.txt");

????????Console.WriteLine("There?are?{0}?IP?addresses",?myIPs.Count);

????????Console.WriteLine("David's?IP?address:?"?+?myIPs.Item("David"));

????????Console.WriteLine("Bernica's?IP?address:?"?+?myIPs.Item("Bernica"));

????????Console.WriteLine("Mike's?IP?address:?"?+?myIPs.Item("Mike"));

????}

}

?

?

IPAddresses?myIPs?=?new?IPAddresses(@"c:\ips.txt");

DictionaryEntry[]?ips?=?new?DictionaryEntry[myIPs.Count-1];

myIPs.CopyTo(ips,?0);

?

?

泛型KeyValuePair?類，每個對象只能存儲一個值

<string,?int>?mcmillan?=?new?KeyValuePair<string,?int>("McMillan",?99);

Console.Write(mcmillan.Key);

Console.Write("?"?+?mcmillan.Value);

?

?

using?System;

using?System.Collections.Generic;

using?System.Text;

namespace?Generics

{

????class?Program

????{

????????static?void?Main(string[]?args)

????????{

?

????????????KeyValuePair<string,?int>[]?gradeBook?=?new?KeyValuePair<string,?int>[10];

????????????gradeBook[0]?=?new?KeyValuePair<string,int>("McMillan",?99);

????????????gradeBook[1]?=?new?KeyValuePair<string,int>("Ruff",?64);

????????????for?(int?i?=?0;?i?<=?gradeBook.GetUpperBound(0);?i++)

????????????????if?(gradeBook[i].Value?!=?0)

????????????????????Console.WriteLine(gradeBook[i].Key?+?":?"?+?gradeBook[i].Value);

????????????Console.Read();

????????}

????}

}

?

SortedList? 類

?

SortedList?myips?=?new?SortedList();

myips.Add("Mike",?"192.155.12.1");

myips.Add("David",?"192.155.12.2");

myips.Add("Bernica",?"192.155.12.3");

?

?

SortedList<Tkey,?TValue>

?

?

SortedList<string,?string>?myips?=?new?SortedList<string,?string>();

?

SortedList<string,?int>?gradeBook?=?new?SortedList<string,?int>();

?

?

foreach(Object?key?in?myips.Keys)

Console.WriteLine("Name:?"?+?key?+?"\n"?+?"IP:?"?+?myips[key]);

?

for(int?i?=?0;?i?<?myips.Count;?i++)

Console.WriteLine("Name:?"?+?myips.GetKey(i)?+?"\n"?+?"IP:?"?+?myips.GetByIndex(i));

?

myips.Remove("David");

myips.RemoveAt(1);

int?indexDavid?=?myips.IndexOfKey("David");

int?indexIPDavid?=?myips.IndexOfValue(myips["David"]);

?

散列和 HasTable

散列是一種常見的順出數(shù)據(jù)技術(shù)，采用這種技術(shù)可以非常迅速的插入和檢索數(shù)據(jù)。散列所采用的數(shù)據(jù)結(jié)構(gòu)成為散列表。

?

?

?散列表數(shù)據(jù)結(jié)構(gòu)是圍繞數(shù)組設(shè)計(jì)的。存儲在數(shù)組內(nèi)的每一個數(shù)據(jù)讀書基于鍵映射到一個范圍從 0 到散列表大小的數(shù)值上，這被稱為是鍵，為了把一個元素存儲到散列表內(nèi)，利用所謂散列函數(shù)吧鍵映射到一個范圍從 0 到散列表大小的數(shù)上。由于鍵是不受限制的，而數(shù)組的大小又是有限制的，所以散列函數(shù)比較現(xiàn)實(shí)的目標(biāo)是把鍵盡可能平均分布到數(shù)組的單元內(nèi)。即使一個很好的散列函數(shù)也可能會出現(xiàn)兩個鍵散列到相同的數(shù)值情況 , 這種現(xiàn)象稱為沖突。

?

選擇散列函數(shù)?

?選擇散列函數(shù)的依據(jù)是所用鍵的數(shù)據(jù)類型。如果所用的鍵是整數(shù)，那么最簡單的函數(shù)是返回鍵對數(shù)組大小取莫結(jié)果（前提是數(shù)組的大小必須是素?cái)?shù)）。然而許多應(yīng)用中鍵都是字符串，下面一個簡單利用把鍵內(nèi)字母 Ascll 碼相加，上述加和的數(shù)值與數(shù)組大小模莫就是散列值了。

?

?

using?System;

class?chapter

{

????static?void?Main()

????{

????????string[]?names?=?new?string[99];

????????string?name;

????????string[]?someNames?=?new?string[]{"David","Jennifer",?"Donnie",?"Mayo",?"Raymond",

????????????"Bernica",?"Mike",?"Clayton",?"Beata",?"Michael"};

????????int?hashVal;

????????for?(int?i?=?0;?i?<?10;?i++)

????????{

????????????name?=?someNames[i];

????????????hashVal?=?SimpleHash(name,?names);

????????????names[hashVal]?=?name;

????????}

????????ShowDistrib(names);

????}

????static?int?SimpleHash(string?s,?string[]?arr)

????{

????????int?tot?=?0;

????????char[]?cname;

????????cname?=?s.ToCharArray();

????????for?(int?i?=?0;?i?<=?cname.GetUpperBound(0);?i++)

????????????tot?+=?(int)cname[i];

????????return?tot?%?arr.GetUpperBound(0);

????}

????static?void?ShowDistrib(string[]?arr)

????{

????????for?(int?i?=?0;?i?<=?arr.GetUpperBound(0);?i++)

????????????if?(arr[i]?!=?null)

????????????????Console.WriteLine(i?+?"?"?+?arr[i]);

????}

}

問題出現(xiàn)了，鍵分布不均勻都聚集在數(shù)組的開始和結(jié)束處。

最終選擇數(shù)組的小取決于存儲在記錄的確切數(shù)量。一個保險(xiǎn)數(shù)字是 10007 ，它是素?cái)?shù)，而且還沒大到，會使用大量內(nèi)存導(dǎo)致降低程序性能的地步。

一個好的解決方法

static?int?BetterHash(string?s,?string[]?arr)

{

????long?tot?=?0;

????char[]?cname;

????cname?=?s.ToCharArray();

????for?(int?i?=?0;?i?<=?cname.GetUpperBound(0);?i++)

????????tot?+=?37?*?tot?+?(int)cname[i];

????tot?=?tot?%?arr.GetUpperBound(0);

????if?(tot?<?0)

????????tot?+=?arr.GetUpperBound(0);

????return?(int)tot;

}

這個函數(shù)利用霍納法則 (Horner) 來計(jì)算多項(xiàng)式函數(shù)。

?

查找散列表中數(shù)據(jù)

static?bool?InHash(string?s,?string[]?arr)

{

????int?hval?=?BetterHash(s,?arr);

????if?(arr[hval]?==?s)

????????return?true;

????else

????????return?false;

}

?

解決沖突?

?在處理散列表的時候，不可避免的會遇到這種情況，即計(jì)算出的鍵的散列值已經(jīng)存儲到了贏一個鍵，這個就是所謂的沖突。

筒式散列法

public?class?BucketHash

{

????private?const?int?SIZE?=?101;

????ArrayList[]?data;

????public?BucketHash()

????{

????????data?=?new?ArrayList[SIZE];

????????for?(int?i?=?0;?i?<=?SIZE?-?1;?i++)

????????????data[i]?=?new?ArrayList(4);

????}

????public?int?Hash(string?s)

????{

????????long?tot?=?0;

????????char[]?charray;

????????charray?=?s.ToCharArray();

????????for?(int?i?=?0;?i?<=?s.Length?-?1;?i++)

????????????tot?+=?37?*?tot?+?(int)charray[i];

????????tot?=?tot?%?data.GetUpperBound(0);

????????if?(tot?<?0)

????????????tot?+=?data.GetUpperBound(0);

????????return?(int)tot;

????}

????public?void?Insert(string?item)

????{

????????int?hash_value;

????????hash_value?=?Hash(item);

????????if?(data[hash_value].Contains(item))

????????????data[hash_value].Add(item);

????}

????public?void?Remove(string?item)

????{

????????int?hash_value;

????????hash_value?=?Hash(item);

????????if?(data[hash_value].Contains(item))

????????????data[hash_value].Remove(item);

????}

}

?

?

堆排序?

如果將堆看成是一棵完全二叉樹，則這棵完全二叉樹每個非葉子節(jié)點(diǎn)的值均不大于（或不小于）其左，右孩子節(jié)點(diǎn)的值。非葉子節(jié)點(diǎn)大于左右節(jié)點(diǎn)值得堆稱為大根堆，小于左右節(jié)點(diǎn)的值得堆稱為小根堆。

堆的結(jié)構(gòu)類似于二叉樹，但是又不完全相同。首先構(gòu)造堆通常采用的是數(shù)組而不是節(jié)點(diǎn)引用。

堆有兩個非常重要的條件?（ 1 ）堆必須是完整的，這就是意味著每一行都必須有數(shù)據(jù)填充。（ 2 ）每個節(jié)點(diǎn)包含的數(shù)據(jù)大于或者等于此節(jié)點(diǎn)下方孩子節(jié)點(diǎn)所包含的數(shù)據(jù)。

?

using?System;

public?class?Node

{

????public?int?data;

????public?Node(int?key)

????{

????????data?=?key;

????}

}

?

?

public?bool?Insert(int?key)

{

????if?(currSize?==?maxSize)

????????return?false;

????heapArray[currSize]?=?new?Node(key);

????currSize++;

????return?true;

}

?

public?void?ShiftUp(int?index)?//? 移動合適位置。

{

????int?parent?=?(index?-?1)?/?2;

????Node?bottom?=?heapArray[index];

????while?((index?>?0)?&&?(heapArray[parent].data?<?bottom.data))

????{

????????heapArray[index]?=?heapArray[parent];

????????index?=?parent;

????????parent?=?(parent?-?1)?/?2;

????}

????heapArray[index]?=?bottom;

}

?

public?Node?Remove()

{

????Node?root?=?heapArray[0];

????currSize--;

????heapArray[0]?=?heapArray[currSize];

????ShiftDown(0);

????return?root;

}

public?void?ShiftDown(int?index)

{

????int?largerChild;

????Node?top?=?heapArray[index];

????while?(index?<?(int)(currSize?/?2))

????{

????????int?leftChild?=?2?*?index?+?1;

????????int?rightChild?=?leftChild?+?1;

????????if?((rightChild?<?currSize)?&&?heapArray[leftChild].data?<?heapArray[rightChild].data)

????????????largerChild?=?rightChild;

????????else

????????????largerChild?=?leftChild;

????????if?(top.data?>=?heapArray[largerChild].data)

????????????break;

????????heapArray[index]?=?heapArray[largerChild];

????????index?=?largerChild;

????}

????heapArray[index]?=?top;

}

?

public?class?Heap

{

????Node[]?heapArray?=?null;

????private?int?maxSize?=?0;

????private?int?currSize?=?0;

????public?Heap(int?maxSize)

????{

????????this.maxSize?=?maxSize;

????????heapArray?=?new?Node[maxSize];

????}

public?bool?InsertAt(int?pos,?Node?nd)

{

????????heapArray[pos]?=?nd;

????????return?true;

}

????public?void?ShowArray()

????{

????????for?(int?i?=?0;?i?<?maxSize;?i++)

????????{

????????????if?(heapArray[i]?!=?null)

????????????????System.Console.Write(heapArray[i].data?+?"??");

????????}

????}

????static?void?Main()

????{

????????const?int?SIZE?=?9;

????????Heap?aHeap?=?new?Heap(SIZE);

????????Random?RandomClass?=?new?Random();

????????for?(int?i?=?0;?i?<?SIZE;?i++)

????????{

?

????????????int?rn?=?RandomClass.Next(1,?100);

????????????aHeap.Insert(rn);

????????}

????????Console.Write("Random:?");

????????aHeap.ShowArray();

????????Console.WriteLine();

????????Console.Write("Heap:?");

????????for?(int?i?=?(int)SIZE?/?2?-?1;?i?>=?0;?i--)

????????????aHeap.ShiftDown(i);

????????aHeap.ShowArray();

????????for?(int?i?=?SIZE?-?1;?i?>=?0;?i--)

????????{

????????????Node?bigNode?=?aHeap.Remove();

????????????aHeap.InsertAt(i,?bigNode);

????????}

????????Console.WriteLine();

????????Console.Write("Sorted:?");

????????aHeap.ShowArray();

????}

}

字典 DictionaryBase 和 SortedList