Csharp中的常見的數據結構

數據結構

網站開發，都是上層應用；數據結構：屬于底層的各種數據的存儲方式；
1.數據計算，業務邏輯處理。。。。。---基于數據來來的
2.怎么保存、怎么查詢、怎么刪除、更新。。。。
3.就需要一些規范，定義各種規范，把數據做保存。。。。

數據結構：
1.Set集合：純粹的容器；無需存儲，就是一個容器
2.線型結構：在存儲的時候；一對一存儲；
3.樹形結構：表達式目錄樹（二叉樹）、菜單結構：一對多
4.圖狀結構：拓撲圖、網狀結構（地圖開發,用的上）

常見的數據結構

線程結構：Array/ArrayList/List/LinkedList/Queue/Stack/HastSet/SortedSet/Hashtable/SortedList/Dictionary/SortedDictionary

IEnumerable、ICollection、IList、IQueryable
接口是標識功能的，不同的接口拆開，就是為接口隔離；雖然我們接口內容也可能重復

IEnumerable 任何數據集合，都實現了的,為不同的數據結構，提供了統一的數據訪問方式
這個就是迭代器模式

一、線性結構

線程結構：Array/ArrayList/List/LinkedList/Queue/Stack/HastSet/SortedSet/Hashtable/SortedList/Dictionary/SortedDictionary

數組：內存連續存儲，節約空間，可以索引訪問，讀取快，刪慢

Array

Array：在內存上連續分配的，而且元素類型是一樣的
可以坐標訪問讀取快--增刪慢，長度不變

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

 foreach (var item in stringArray)
 {

 }

 for (int i = 0; i < intArray.Length; i++)
 {
     Console.WriteLine(intArray[i]); 
 }

ArrayList

ArrayList:以前的開發中使用的比較多不定長的，連續分配的；
元素沒有類型限制，任何元素都是當成object處理，如果是值類型，會有裝箱操作
讀取快--增刪慢

Console.WriteLine("***************ArrayList******************");
ArrayList arrayList = new ArrayList();
arrayList.Add("Richard");
arrayList.Add("Is");
arrayList.Add(32);//add增加長度
                  // arrayList[4] = 26;//索引復制，不會增加長度
                  //刪除數據
                  //arrayList.RemoveAt(4);
var value = arrayList[2];
arrayList.RemoveAt(0);
arrayList.Remove("Richard");

foreach (var item in arrayList)
{

}

for (int i = 0; i < arrayList.Count; i++)
{
    Console.WriteLine(arrayList[i]);
}

List

List:也是Array，內存上都是連續擺放;不定長；泛型，保證類型安全，避免裝箱拆箱；性能也是比Arraylist要高
讀取快--增刪慢

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;
List<string> stringList = new List<string>();
//stringList[0] = "123";//異常的
foreach (var item in intList)
{

}

for (int i = 0; i < intList.Count; i++)
{
    Console.WriteLine(intList[i]);
}

以上特點：讀取快，增刪相對慢；

鏈表：非連續擺放，存儲數據+地址，找數據的話就只能順序查找，讀取慢；增刪快

LinkedList

LinkedList：泛型的特點;鏈表，元素不連續分配，每個元素都有記錄前后節點
節點值可以重復
能不能索引訪問？不能，
1.查詢元素就只能遍歷查找不方便--查詢慢
2.增刪就比較方便--增刪快

 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

Queue：隊列，就跟一個沒有瓶底的瓶子一樣；就是鏈表先進先出放任務延遲執行，A不斷寫入日志任務 B不斷獲取任務去執行

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

 Console.WriteLine($"Dequeuing '{numbers.Dequeue()}'");
 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 就是鏈表先進后出解析表達式目錄樹的時候，先產生的數據后使用
操作記錄為命令，撤銷的時候是倒序的

Console.WriteLine("***************Stack<T>******************");
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}");

hash表類型

set

集合：hash分布，元素間沒關系,動態增加容量去重--如果是同一個引用，就可以去掉重復；
應用場景：抖音發布的作品點贊！統計用戶IP；IP投票
提供了一些計算：交叉并補--二次好友/間接關注/粉絲合集
應用場景：一葉知秋：Richard 系統可能推薦一些可能認識的人：找出Richard老師的好友列表：找出一葉知秋這個同學的好友列表：求差集；---是一葉知秋的好友，但是不是Richard好友。系統就給Richard推薦：可能認識的人；

 Console.WriteLine("***************HashSet<string>******************");
 HashSet<string> hashSet = new HashSet<string>();
 hashSet.Add("123");
 hashSet.Add("689");
 hashSet.Add("456");
 string s1 = "12345";
 hashSet.Add(s1);
 string s2 = "12345";
 hashSet.Add(s2);
 string s3 = "12345";
 hashSet.Add(s3);
 //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();

 HashSet<People> peoples = new HashSet<People>();
 People people = new People()
 {
     Id = 123,
     Name = "小菜"
 };
 People people1 = new People()
 {
     Id = 123,
     Name = "小菜"
 };
 peoples.Add(people);
 peoples.Add(people1);
 peoples.Add(people1);

SortedSet

排序的集合：去重而且排序
統計排名--每統計一個就丟進去集合

    Console.WriteLine("***************SortedSet<string>******************");
    SortedSet<string> sortedSet = new SortedSet<string>();
    //IComparer<T> comparer  自定義對象要排序，就用這個指定
    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);//補
        sortedSet1.UnionWith(sortedSet);//并
        sortedSet1.ExceptWith(sortedSet);//差
        sortedSet1.IntersectWith(sortedSet);//交
    }

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

有沒有既能查詢快，也增刪快的數據機構呢？
讀取&增刪都快？有 hash散列字典
key-value，一段連續有限空間放value(開辟的空間比用到的多，hash是用空間換性能)，基于key散列計算得到地址索引，這樣讀取快

增刪也快，刪除時也是計算位置，增加也不影響別人
因為key 是最終生成了索引的；如果數量過多，散列計算后，肯定會出現不同的key計算出的索引只是同一個
肯定會出現2個key(散列沖突)，散列結果一致18，可以讓第二次的+1，
可能會造成效率的降低，尤其是數據量大的情況下，以前測試過dictionary在3w條左右性能就開始下降的厲害

HashTable

Hashtable key-value 體積可以動態增加拿著key計算一個地址，然后放入key - value
object-裝箱拆箱如果不同的key得到相同的地址，第二個在前面地址上 + 1
查找的時候，如果地址對應數據的key不對，那就 + 1查找。。
浪費了空間，Hashtable是基于數組實現
查找個數據一次定位；增刪一次定位；增刪查改都很快
浪費空間，數據太多，重復定位定位，效率就下去了

Console.WriteLine("***************Hashtable******************");
Hashtable table = new Hashtable();
table.Add("123", "456");
//table.Add("123", "456");//key相同  會報錯
table[234] = 456;
table[234] = 567;
table[32] = 4562;
table[1] = 456;
table["Richard"] = 456;
foreach (DictionaryEntry objDE in table)
{
    Console.WriteLine(objDE.Key.ToString());
    Console.WriteLine(objDE.Value.ToString());
}
//線程安全
Hashtable.Synchronized(table);//只有一個線程寫  多個線程讀

字典

字典：泛型；key - value，增刪查改都很快；有序的
字典不是線程安全 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}");
}

SortedDictionary

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

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

這里會產生一個問題，為什么有那么多的數據結構，各種各樣都有不同，都能使用foreach去遍歷，這就是迭代器模式

定義一個通用迭代器的類型:

 public interface IIterator<T>
 {
     /// <summary>
     /// 當前的對象
     /// </summary>
     T Current { get; }
     /// <summary>
     /// 移動到下一個對象，是否存在
     /// </summary>
     /// <returns></returns>
     bool MoveNext();
     /// <summary>
     /// 重置
     /// </summary>
     void Reset();
 }

實現的food類

 public class Food
 {
     public int Id { get; set; }
     public string Name { get; set; }
     public int Price { get; set; }
 }

實現的KFC和MacDonald的菜單的迭代器

KFCMenu.cs

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

 }

MacDonaldMenu.cs

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

來調用我們實現的迭代器，使用foreach循環

    Console.WriteLine("********************KFCMenu********************");
    KFCMenu kFCMenu = new KFCMenu();
    IIterator<Food> iterator = kFCMenu.GetEnumerator();
    foreach (var item in kFCMenu)
    {
        Console.WriteLine(item.Id);
        Console.WriteLine(item.Name);
        Console.WriteLine(item.Price);


    }
    while (iterator.MoveNext())
    {
        Console.WriteLine("再來一次");
        Food food = iterator.Current;
        Console.WriteLine(food.Name);
    }

    Console.WriteLine("********************MacDonaldMenu********************");
    MacDonaldMenu macDonaldMenu = new MacDonaldMenu();
    IIterator<Food> iterator1 = macDonaldMenu.GetEnumerator();
    foreach (var item in macDonaldMenu)
    {
        Console.WriteLine(item.Id);
        Console.WriteLine(item.Name);
        Console.WriteLine(item.Price);


    }
    while (iterator1.MoveNext())
    {
        Console.WriteLine("再來一次");
        Food food = iterator1.Current;
        Console.WriteLine(food.Name);
    }

}

Foreach循環：其實都是通過實現：IEnumerable接口來完后；實現接口，就需要實現一個GetIEnumerator方法；這個方法返回的是一個Enumerator---迭代器；就是這個迭代器，提供了一統一對線型結構數據的一種訪問方式；

yield

Yield是語法糖，編譯時由編譯器生成Iterrator的代碼，包括movenext current reset

定義一個類，方便我們去理解

public class YieldDemo
{
    public IEnumerable<int> Power()
    {
        for (int i = 0; i < 10; i++)
        {
            yield return this.Get(i); 
            Console.WriteLine("yield這里再來一次");
           // yield return this.Get(i) + 1;
        }
    }

    public IEnumerable<int> Common()
    {
        List<int> intList = new List<int>();
        for (int i = 0; i < 10; i++)
        {
            intList.Add(this.Get(i));
            Console.WriteLine("集合這里再來一次");
        }
        return intList;
    }

    private int Get(int num)
    {
        Thread.Sleep(2000);
        return num * DateTime.Now.Second;
    }
}

對應的調用的代碼


 Console.WriteLine("*******************Yield********************");
 YieldDemo yieldDemo = new YieldDemo();
 foreach (var item in yieldDemo.Power())
 {
     Console.WriteLine(item);//按需獲取，要一個拿一個
     if (item > 100)
         break;
 }
 Console.WriteLine("*******************************************");
 foreach (var item in yieldDemo.Common())
 {
     Console.WriteLine(item);//先全部獲取，然后一起返還
     if (item > 100)
         break;
 }

含有yield的函數說明它是一個生成器，而不是普通的函數。當程序運行到yield這一行時，該函數會返回值，并保存當前域的所有變量狀態；等到該函數下一次被調用時，會從上一次中斷的地方開始執行，一直遇到下一個yield, 程序返回值, 并在此保存當前狀態; 如此反復，直到函數正常執行完成。
迭代器模式是設計模式中行為模式(behavioral pattern)的一個例子，他是一種簡化對象間通訊的模式，也是一種非常容易理解和使用的模式。簡單來說，迭代器模式使得你能夠獲取到序列中的所有元素而不用關心是其類型是array，list，linked list或者是其他什么序列結構。這一點使得能夠非常高效的構建數據處理通道(data pipeline)
--即數據能夠進入處理通道，進行一系列的變換，或者過濾，然后得到結果。事實上，這正是LINQ的核心模式。
在.NET中，迭代器模式被IEnumerator和IEnumerable及其對應的泛型接口所封裝。如果一個類實現了IEnumerable接口，那么就能夠被迭代；調用GetEnumerator方法將返回IEnumerator接口的實現，它就是迭代器本身。迭代器類似數據庫中的游標，他是數據序列中的一個位置記錄。迭代器只能向前移動，同一數據序列中可以有多個迭代器同時對數據進行操作。

dynamic

動態dynamic解讀:framework4.0 讓程序有了弱類型的特點

示例代碼

{
    string s = "abcd";
    //int i = (int)s; //強類型：編譯時完成安全檢查
    //s.Hello();
}
{
    dynamic s = "abcd";//弱類型：運行時才檢查類型
    int i = (int)s;
    s.Hello();
    int a = s.Richard;
}
{
    object A = new YieldDemo();
    //A.Power();
    Type type = A.GetType();
    MethodInfo method = type.GetMethod("Power");
    method.Invoke(A, null);

    dynamic dA = A;
    dA.Power();
    
}

1 代替反射 2 數據綁定方便 3 跟C++交互方便
性能比反射高

posted @ 2024-05-30 15:02 飄雨的河閱讀(133) 評論(0) 收藏舉報

刷新頁面返回頂部

飄雨的河

一個自己學習記錄的學習樂園