玩轉C#之【數據結構】

by NickChi
數據結構

Array

在記憶體中連續分配,而且元素類型是一樣的,長度不變
優點:讀取快,可以使用座標訪問
缺點:新增、刪除慢

記憶體:

範例程式碼:

Console.WriteLine("***************Array******************");
int[] intArray = new int[3];
intArray[0] = 123;
string[] stringArray = new string[] { "123", "234" };//Array

ArrayList

不定長度,在記憶體中連續分配的,元素沒有類型限制,任何元素都是當成object處理,如果是值類型,會有裝箱的操作
優點:讀取快
缺點:新增、刪除慢

範例程式碼:

Console.WriteLine("***************ArrayList******************");
ArrayList arrayList = new ArrayList();
arrayList.Add("Eleven");
arrayList.Add("Is");
arrayList.Add(32);//add增加長度
//arrayList[4] = 26;//索引覆制,不會增加長度
//刪除資料
arrayList.RemoveAt(4);
var value = arrayList[2];
arrayList.RemoveAt(0);
arrayList.Remove("Eleven");

List

也是Array,在記憶體中是連續擺放,不定長度,泛型,保證類型安全,避免裝箱拆箱
優點:讀取快
缺點:增刪慢

範例程式碼:

Console.WriteLine("***************List<T>******************");
List<int> intList = new List<int>() { 1, 2, 3, 4 };
intList.Add(123);
intList.Add(123);
//intList.Add("123");
//intList[0] = 123;

鏈結串列(LinkedList)

LinkedList 泛型的特點,在記憶體不連續分配,每個元素都有紀錄前後節點,節點值可以重複,不能座標訪問,找元素就只能遍歷
優點:增加、刪除 快
缺點:查尋不方便

記憶體:

範例程式碼:

Console.WriteLine("***************LinkedList<T>******************");
LinkedList<int> linkedList = new LinkedList<int>();
 //linkedList[3] =>不能直接座標訪問
linkedList.AddFirst(123);
linkedList.AddLast(456);

bool isContain = linkedList.Contains(123);
LinkedListNode<int> node123 = linkedList.Find(123);  //找元素123的位置  從頭開始找
linkedList.AddBefore(node123, 123);
linkedList.AddBefore(node123, 123);
linkedList.AddAfter(node123, 9);

//移除&清除
linkedList.Remove(456);
linkedList.Remove(node123);
linkedList.RemoveFirst();
linkedList.RemoveLast();
linkedList.Clear();

Queue(對列)

鏈表的一種,先進先出,放任務延遲執行
應用場景:A不斷寫入日誌任務、B不斷獲取任務去執行

Queue VS Stack:

範例程式碼:

Console.WriteLine("***************Queue<T>******************");
Queue<string> numbers = new Queue<string>();
numbers.Enqueue("one");
numbers.Enqueue("two");
numbers.Enqueue("three");
numbers.Enqueue("four");
numbers.Enqueue("four");
numbers.Enqueue("five");
//印出全部資料
foreach (string number in numbers)
{
    Console.WriteLine(number);
}
//Dequeuing 會取出資料並從Queue中移除
Console.WriteLine($"Dequeuing '{numbers.Dequeue()}'");
//Peek 會取出資料
Console.WriteLine($"Peek at next item to dequeue: { numbers.Peek()}");
Console.WriteLine($"Dequeuing '{numbers.Dequeue()}'");

//也可以一開始指定陣列的資料禁去
Queue<string> queueCopy = new Queue<string>(numbers.ToArray());
foreach (string number in queueCopy)
{
    Console.WriteLine(number);
}

Console.WriteLine($"queueCopy.Contains(\"four\") = {queueCopy.Contains("four")}");
queueCopy.Clear();
Console.WriteLine($"queueCopy.Count = {queueCopy.Count}");

Stack

先進後出
應用場景:解析表達式目錄樹的時候,先產生的數據後使用

Stack<string> numbers = new Stack<string>();
numbers.Push("one");
numbers.Push("two");
numbers.Push("three");
numbers.Push("four");
numbers.Push("five");//放進去

foreach (string number in numbers)
{
    Console.WriteLine(number);
}

Console.WriteLine($"Pop '{numbers.Pop()}'");//獲取並移除
Console.WriteLine($"Peek at next item to dequeue: { numbers.Peek()}");//獲取不移除
Console.WriteLine($"Pop '{numbers.Pop()}'");

Stack<string> stackCopy = new Stack<string>(numbers.ToArray());
foreach (string number in stackCopy)
{
    Console.WriteLine(number);
}

Console.WriteLine($"stackCopy.Contains(\"four\") = {stackCopy.Contains("four")}");
stackCopy.Clear();
Console.WriteLine($"stackCopy.Count = {stackCopy.Count}");

Set

HashSet是以數學Set集合為基礎的,使用HashSet可以提高集合的運算。使用HashSet集合不自帶排序方法,如果需要排序的需求可以參考使用List集合配合Sort方法。

HashSet的優勢在與運算快,作為一種存放在記憶體的資料,可以很快的進行設定和取值的操作。HashSet無法向裡面新增重複的資料,避免新增HashSet裡面的資料重複。我們使用HashSet常常在集合相加集合相減這些集合與集合之間的操作之中。

使用HashSet作為記憶體儲存的快速資料庫,這個需要隨時跟新HashSet裡面的資料,因為在HashSet中一個長時間未被訪問的資料,將被系統自動回收掉,那麼就會導致失敗,那麼如何才能保證HashSet裡面的值是長存在的而且達到不斷的更新裡面的值呢?

首先程式過來訪問我們HashSet裡面有沒有需要的資料,如果有我們需要的資料就直接返回給使用者,不用呼叫查詢資料庫的操作。如果HashSet裡面沒有我們需要的資料,程式再去查詢一次資料庫是否有該Query資料,如果有返回給使用者同時把查詢的結果新增到HashSet裡面,這麼做可以一定程度的降低查詢資料庫所帶來的不便,但是不能根除,需要進一步提升效能,可以檢視前面的快取策略使用memcached來提高網站查詢和訪問。

優點:交集、聯集、差集、補集,去重複

記憶體:

參考資料

交集、聯集、差集、補集

範例程式碼:

Console.WriteLine("***************HashSet<string>******************");
HashSet<string> hashSet = new HashSet<string>();
hashSet.Add("123");
hashSet.Add("689");
hashSet.Add("456");
hashSet.Add("12435");
hashSet.Add("12435");
hashSet.Add("12435");
//hashSet[0];
foreach (var item in hashSet)
{
    Console.WriteLine(item);
}
Console.WriteLine(hashSet.Count);
Console.WriteLine(hashSet.Contains("12345"));


HashSet<string> hashSet1 = new HashSet<string>();
hashSet1.Add("123");
hashSet1.Add("689");
hashSet1.Add("789");
hashSet1.Add("12435");
hashSet1.Add("12435");
hashSet1.Add("12435");
//求兩個集合的對稱差集。
hashSet1.SymmetricExceptWith(hashSet);
//求兩個集合的並集
hashSet1.UnionWith(hashSet);
//求兩個集合的差集。
hashSet1.ExceptWith(hashSet);
//求兩個集合的交集。
hashSet1.IntersectWith(hashSet);

hashSet.ToList();
hashSet.Clear();

SortSet

排序的集合,可以做排序,去重複
應用場景:統計排名,每統計一個就丟進去集合

範例程式碼:

Console.WriteLine("***************SortedSet<string>******************");
SortedSet<string> sortedSet = new SortedSet<string>();

sortedSet.Add("123");
sortedSet.Add("689");
sortedSet.Add("456");
sortedSet.Add("12435");
sortedSet.Add("12435");
sortedSet.Add("12435");

foreach (var item in sortedSet)
{
    Console.WriteLine(item);
}
Console.WriteLine(sortedSet.Count);
Console.WriteLine(sortedSet.Contains("12345"));

SortedSet<string> sortedSet1 = new SortedSet<string>();
sortedSet1.Add("123");
sortedSet1.Add("689");
sortedSet1.Add("456");
sortedSet1.Add("12435");
sortedSet1.Add("12435");
sortedSet1.Add("12435");
//求兩個集合的對稱差集。
sortedSet1.SymmetricExceptWith(sortedSet);
//求兩個集合的並集
ortedSet1.UnionWith(sortedSet);
//求兩個集合的差集。
sortedSet1.ExceptWith(sortedSet);
//求兩個集合的交集。
sortedSet1.IntersectWith(sortedSet);


sortedSet.ToList();
sortedSet.Clear();

自訂排序規則:

1. 撰寫新的排序規則繼承IComparer
2. 建立自定義的排序物件
3. 建立SortedSet將排序物件放進建構子當中

public class Box
    {
        /// <summary>
        /// 高度
        /// </summary>
        public double Height { get; set; }
        /// <summary>
        /// 長度
        /// </summary>
        public double Length { get; set; }
        /// <summary>
        /// 寬度
        /// </summary>
        public double Width { get; set; }
    }
//撰寫新的排序規則繼承IComparer<T>
 public class BoxComp : IComparer<Box>
    {
        // Compares by Height, Length, and Width.
        public int Compare(Box x, Box y)
        {
            if (x.Height.CompareTo(y.Height) != 0)
            {
                return x.Height.CompareTo(y.Height);
            }
            else if (x.Length.CompareTo(y.Length) != 0)
            {
                return x.Length.CompareTo(y.Length);
            }
            else if (x.Width.CompareTo(y.Width) != 0)
            {
                return x.Width.CompareTo(y.Width);
            }
            else
            {
                return 0;
            }
        }
    }
}
//建立自定義的排序物件
var boxIComparer = new BoxComp();
//建立SortedSet將排序物件放進建構子當中
SortedSet<Box> boxSortedSet = new SortedSet<Box>(boxIComparer);

HashTable

動態增加、key -value 拿者key計算一個地址,然後放入key-value
object-裝箱拆箱 如果不同的key得到相同的地址,第二個在前面地址上+1 查找的時候 如果地址對應數據的key不對 那就+1查找…在不對就在+1 =>浪費了空間
HashTable基於數組實現
優點:查找個數據 一次定位 增刪 一次定位 增刪查改 都很快
缺點:浪費空間,數據太多 重複訂位定位 效率就下去了

記憶體:

範例程式碼:

Console.WriteLine("***************Hashtable******************");
Hashtable table = new Hashtable();
table.Add("123", "456");
table[234] = 456;
table[234] = 567;
table[32] = 4562;
table[1] = 456;
table["eleven"] = 456;
foreach (DictionaryEntry objDE in table)
{
    Console.WriteLine(objDE.Key.ToString());
    Console.WriteLine(objDE.Value.ToString());
}

線程安全的

Hashtable.Synchronized(table);//可以保證 只有一個現成寫 多個現成讀

字典

泛型 key-value 有順序的 類似HashTable 但不完全是
Dictionary =>執行緒不安全的版本
ConcurrentDictionary => 執行緒安全的版本
優點:增刪改查都很快
缺點:數據量太多 查找效率也是會慢下來的

範例程式碼:

Console.WriteLine("***************Dictionary******************");
Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "HaHa");
dic.Add(5, "HoHo");
dic.Add(3, "HeHe");
dic.Add(2, "HiHi");
dic.Add(4, "HuHu1");
dic[4] = "HuHu";
dic.Add(4, "HuHu");
foreach (var item in dic)
{
  Console.WriteLine($"Key:{item.Key}, Value:{item.Value}");
}

排序字典

增刪改會比字典效率低,但是會排序

範例程式碼:

Console.WriteLine("***************SortedDictionary******************");
SortedDictionary<int, string> dic = new SortedDictionary<int, string>();
dic.Add(1, "HaHa");
dic.Add(5, "HoHo");
dic.Add(3, "HeHe");
dic.Add(2, "HiHi");
dic.Add(4, "HuHu1");
dic[4] = "HuHu";
dic.Add(4, "HuHu");
foreach (var item in dic)
{
    Console.WriteLine($"Key:{item.Key}, Value:{item.Value}");
}

SortList

集合型式 可以按照key做排序

範例程式碼:

Console.WriteLine("***************SortedList******************");
SortedList sortedList = new SortedList();//IComparer
sortedList.Add("First", "Hello");
sortedList.Add("Second", "World");
sortedList.Add("Third", "!");

sortedList["Third"] = "~~";//
sortedList.Add("Fourth", "!");
sortedList.Add("Fourth", "!");//重覆的Key Add會錯
sortedList["Fourth"] = "!!!";
var keyList = sortedList.GetKeyList();
var valueList = sortedList.GetValueList();

sortedList.TrimToSize();//用於最小化集合的內存開銷

sortedList.Remove("Third");
sortedList.RemoveAt(0);
sortedList.Clear();

各類線程安全的版本

ConcurrentQueue 線程安全的版本的Queue
ConcurrentStack 線程安全的版本的Stack
ConcurrentBag   線程安全的的對象集合
ConcurrentDictionary 線程安全的Dictionary
BlockingCollection

Collection

Q:為什麼要這麼多介面、類型區分?

A:Interface是標示功能的,不同的接口拆開,就是為了接口隔離;雖然我們接口內容可能重複

各種集合 疊代器

  • IEnumerable =>傳的的是委託
    遍歷才會去查詢比較 疊代器yield
  • IQueryable => 傳的的是表達式目錄樹
    表達式目錄樹的解析 延遲到遍歷的時後才去執行

IEnumerable 我們可以觀察出,任何數據集合都繼承它,為了不同的數據結構,提供統的一個遍歷方式,這個就是疊代器模式

Yield

含有yield的函數說明它是一個生成器,而不是普通的函數。當程序運行到yield這一行時,該函數會返回值,並保存當前域的所有變量狀態;等到該函數下一次被調用時,會從上一次中斷的地方開始執行,一直遇到下一個yield,程序返回值, 並在此保存當前狀態; 如此反覆,直到函數正常執行完成。

?範例程式碼:

void Main()
{
    foreach (var i in CreateEnumerable())
    {
        Console.WriteLine("外部迴圈讀取 => 傳回值【{0}】", i);
    }
}

// Define other methods and classes here
public IEnumerable<int> CreateEnumerable()
{
    Console.WriteLine("{0} CreateEnumerable()方法開始", DateTime.Now);
    for (int i = 0; i < 5; i++)
    {
        Console.WriteLine("{0}開始 yield {1}", DateTime.Now, i);
        yield return i;
        Console.WriteLine("{0}yield 結束", DateTime.Now);
    }
}

叠代器模式是設計模式中行為模式(behavioral pattern)的一個例子,他是一種簡化對象間通訊的模式,也是一種非常容易理解和使用的模式。簡單來說,叠代器模式使得你能夠獲取到序列中的所有元素 而不用關心是其類型是array,list,linked list或者是其他什麼序列結構。這一點使得能夠非常高效的構建數據處理通道(data pipeline)
即數據能夠進入處理通道,進行一系列的變換,或者過濾,然後得到結果。事實上,這正是LINQ的核心模式。

範例程式碼:

建立範例類別

public class Food
{
    public int Id { get; set; }
    public string Name { get; set; }
    public int Price { get; set; }
}
/// <summary>
/// 肯德基的菜單
/// </summary>
public class KFCMenu
{
    private Food[] _FoodList = new Food[3];

    public KFCMenu()
    {
        this._FoodList[0] = new Food()
        {
            Id = 1,
            Name = "漢堡包",
            Price = 15
        };
        this._FoodList[1] = new Food()
        {
            Id = 2,
            Name = "可樂",
            Price = 10
        };
        this._FoodList[2] = new Food()
        {
            Id = 3,
            Name = "薯條",
            Price = 8
        };
    }

    public Food[] GetFoods()
    {
        return this._FoodList;
    }


    public IIterator<Food> GetEnumerator()
    {
        return new KFCMenuIterator(this);
    }

}
/// <summary>
    /// 麥當勞菜單
    /// </summary>
    public class MacDonaldMenu
    {
        private List<Food> _FoodList = new List<Food>();

        public MacDonaldMenu()
        {
            this._FoodList.Add(new Food()
            {
                Id = 1,
                Name = "雞肉捲",
                Price = 15
            });
            this._FoodList.Add(new Food()
            {
                Id = 2,
                Name = "紅豆派",
                Price = 10
            });
            this._FoodList.Add(new Food()
            {
                Id = 3,
                Name = "薯條",
                Price = 9
            });
        }

        public List<Food> GetFoods()
        {
            return this._FoodList;
        }


        public IIterator<Food> GetEnumerator()
        {
            return new MacDonaldIterator(this);
        }
    }

從這可以看出,如果我們要讀取陣列中每個元素,會因為是array或List導致讀取的方式不一樣
foodCollection.Length or foodCollection.Count()

//Array
Console.WriteLine("**************kfc Show*************");
KFCMenu kfcMenu = new KFCMenu();
Food[] foodCollection = kfcMenu.GetFoods();
for (int i = 0; i < foodCollection.Length; i++)
{
    Console.WriteLine("KFC: Id={0} Name={1} Price={2}",foodCollection[i].Id, foodCollection[i].Name, foodCollection[i].Price);
}
//List
Console.WriteLine("**************MacDonald Show*************");
MacDonaldMenu macDonaldMenu = new MacDonaldMenu();
List<Food> foodCollection = macDonaldMenu.GetFoods();
for (int i = 0; i < foodCollection.Count(); i++)
{
    Console.WriteLine("MacDonald: Id={0} Name={1} Price={2}", foodCollection[i].Id, foodCollection[i].Name, foodCollection[i].Price);
}

在.NET中,叠代器模式被IEnumerator和IEnumerable及其對應的泛型接口所封裝。如果一個類實現了IEnumerable接 口,那麼就能夠被叠代;調用GetEnumerator方法將返回IEnumerator接口的實現,它就是叠代器本身。叠代器類似數據庫中的遊標,他是 數據序列中的一個位置記錄。叠代器只能向前移動,同一數據序列中可以有多個叠代器同時對數據進行操作。

?範例程式碼:

實做Iterator

 public interface IIterator<T>
    {
        /// <summary>
        /// 當前的對象
        /// </summary>
        T Current { get; }
        /// <summary>
        /// 移動到下一個對象,是否存在
        /// </summary>
        /// <returns></returns>
        bool MoveNext();
        /// <summary>
        /// 重制
        /// </summary>
        void Reset();
    }
public class KFCMenuIterator : IIterator<Food>
    {
        private Food[] _FoodList = null;

        public KFCMenuIterator(KFCMenu kfcMenu)
        {
            this._FoodList = kfcMenu.GetFoods();
        }

        private int _CurrentIndex = -1;
        public Food Current
        {
            get
            {
                return this._FoodList[_CurrentIndex];
            }
        }

        public bool MoveNext()
        {
            return this._FoodList.Length > ++this._CurrentIndex;

        }

        public void Reset()
        {
            this._CurrentIndex = -1;
        }
    }
 public class MacDonaldIterator : IIterator<Food>
    {
        private List<Food> _FoodList = null;

        public MacDonaldIterator(MacDonaldMenu macDonaldMenu)
        {
            this._FoodList = macDonaldMenu.GetFoods();
        }

        private int _CurrentIndex = -1;
        public Food Current
        {
            get
            {
                return this._FoodList[_CurrentIndex];
            }
        }

        public bool MoveNext()
        {
            return this._FoodList.Count > ++this._CurrentIndex;

        }

        public void Reset()
        {
            this._CurrentIndex = -1;
        }
    }

這樣讀取元素的格式就不用管是arry或者List了,foreach也是一樣原理

IIterator<Food> foodIterator = kfcMenu.GetEnumerator();// new KFCMenuIterator(kfcMenu);
while (foodIterator.MoveNext())
{
    Food food = foodIterator.Current;
    Console.WriteLine("KFC: Id={0} Name={1} Price={2}", food.Id, food.Name, food.Price);
}
IIterator<Food> foodIterator = macDonaldMenu.GetEnumerator();// new MacDonaldIterator(macDonaldMenu);
while (foodIterator.MoveNext())
{
    Food food = foodIterator.Current;
    Console.WriteLine("MacDonald: Id={0} Name={1} Price={2}", food.Id, food.Name, food.Price);
}

我的鐵人賽文章

https://ithelp.ithome.com.tw/articles/10292384

You may also like

Leave a Comment