字典 DictionaryBase 和 SortedList

字典是一種利用鍵值對來存儲的數據結構。作為一種抽象類，dictionaryBase 類可以實現不同的結構

sortedList 是按照分類順序基于鍵值來存儲鍵值對的，它可以通過引用數據結構中的值得索引位置也可以訪問存貯在結構中的數據。

Dictionary 中，存儲在字段中的鍵值對于時間上最為 DictionaryEntry 對象來存儲的。DictionaryEntry 結構提供兩個域，一個用于鍵，一個用于值。對于內部而言會把鍵值存儲在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

散列是一種常見的順出數據技術，采用這種技術可以非常迅速的插入和檢索數據。散列所采用的數據結構成為散列表。

 

 

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

 

選擇散列函數 

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

 

 

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]);

    }

}

問題出現了，鍵分布不均勻都聚集在數組的開始和結束處。

最終選擇數組的小取決于存儲在記錄的確切數量。一個保險數字是10007，它是素數，而且還沒大到，會使用大量內存導致降低程序性能的地步。

一個好的解決方法

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;

}

這個函數利用霍納法則(Horner)來計算多項式函數。

 

查找散列表中數據

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

{

    int hval = BetterHash(s, arr);

    if (arr[hval] == s)

        return true;

    else

        return false;

}

 

解決沖突 

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

筒式散列法

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);

    }

}

 

 

堆排序 

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

堆的結構類似于二叉樹，但是又不完全相同。首先構造堆通常采用的是數組而不是節點引用。

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

 

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();

    }

}