C#数据结构

一、数组

数组是用来存储数据的集合，具有以下特点：

1. 元素类型相同；
2. 固定长度；
3. 顺序集合。

数组使用的实例：

void arrayTest(){    // 定义数组    int[] array_1;    int[] array_2 = new int[3];    int[] array_3 = new int[3] { 1, 2, 3 };    int[] array_4 = { 1, 2, 3, 4, 5 };    // 初始化    array_1 = new int[3];    Debug.Log(array_1[0]);    array_1[0] = 5;    Debug.Log(array_1[0]);    // 打印数组的长度    Debug.Log(array_1.Length);    // 数组的遍历    for(int i = 0; i < array_3.Length; i++)    {        Debug.Log(array_3[i]);    }    foreach(var v in array_4)    {        Debug.Log(v);    }}

二、ArrayList

1.ArrayList的概念

动态数组（ArrayList）对象的有序集合。

2.ArrayList的特点

• 相比于数组，动态数组ArrayList会自动重新调整它的大小。
• 可以使用索引在指定的位置添加和移除项目，它也允许在列表中进行动态内存分配。

3.ArrayList的实例

ArrayList arrayList1 = new ArrayList();    int[] arr1 = new int[4] { 1, 2, 3, 4 };void Start(){    // 添加元素    arrayList1.Add(10);    arrayList1.Add(11);    arrayList1.Add(12);    // 将数组元素插入至ArrayList    arrayList1.AddRange(arr1);    // 打印元素    foreach(var v in arrayList1)    {        Debug.Log(v);    }    // 清除元素    arrayList1.Clear();    // 判断是否包含指定元素    if (arrayList1.Contains(12))    {        Debug.Log("包含12");    }    // 返回指定元素第一次出现的索引     // -1 没有找到    Debug.Log(arrayList1.IndexOf(12));    // 插入元素   插入索引 插入的元素    arrayList1.Insert(3, 67);    // 移除元素    arrayList1.Remove(67);    // 逆置元素    arrayList1.Reverse();    // 元素排序    arrayList1.Sort();}

三、List

1. List概述

• 泛型类集合List<>
• 作用与功能近似 ArrayList
• 无需装箱拆箱，类型转换
• 类型安全

2. List使用示例

// 声明和初始化ListList list_1 = new List();int[] arr = new int[2] { 1, 2 };void Start(){    // 添加元素    list_1.Add(10);    list_1.AddRange(arr);    // 计算元素个数    int count = list_1.Count;    Debug.Log(count);    // 打印元素    foreach(var v in list_1)    {        Debug.Log(v);    }    // 判断是否包含指定元素    if (list_1.Contains(10))    {        Debug.Log("包含10");    }    // 移除元素    list_1.Remove(1);    // 清除元素    list_1.Clear();    // 方法与ArrayList大致相同}

3.ArrayList和List的区别

1. 由于ArrayList需要先将类型转变为Object也就是装箱和拆箱的操作，而List不需要，所以 List 性能较高，ArrayList性能较低。
2. 在ArrayList中插入不同类型的数据是允许的，（例如插入字符串后再插入数字）因为ArrayList会把所有插入元素当作Object类型处理；而 List 至始至终只能插入一种类型的数据。
3. ArrayList
4. 不是类型安全的，而 List 是类型安全的。
5. List 需要在初始化时声明元素类型，而ArrayList不需要。
6. 当不知道往集合存多少，也不知道存什么类型时，用ArrayList；知道往集合存什么类型，不知道存多少个时，用 List。

四、Hashtable

1.Hashtable概述

• Hashtable
• 类代表了 基于键的哈希代码组织起来的键/值对集合。
• Hashtable使用键
• 来访问集合中的元素

2.Hashtable使用示例

// 定义哈希表Hashtable hashTable1 = new Hashtable();void Start(){    // 添加元素 键值对    hashTable1.Add("1", 100);    hashTable1.Add(1, 99);    hashTable1.Add(2, 9);    // 判断是否存在键为“1”的值    if (hashTable1.ContainsKey("1"))    {        Debug.Log("包含key为1的数据");    }    // 计算键值对的数量    int count = hashTable1.Count;    // 移除元素 key    hashTable1.Remove("1");    // 取出指定key的值    Debug.Log(hashTable1[1]);    // 修改    hashTable1[1] = 90;    // 遍历    ICollection key = hashTable1.Keys;     foreach(var k in key)    {        Debug.Log(hashTable1[k]);    }    // 清除元素    hashTable1.Clear();}

五、字典

1. 字典定义

• 字典，是一个泛型容器，是用于存储键值对数据的集合。

2. 字典使用示例

Dictionary dic1 = new Dictionary();void Start(){    // 添加键值对    dic1.Add("1", "100");    dic1.Add("2", "200");    dic1.Add("3", "300");    // 判断键是否存在    if (dic1.ContainsKey("1"))    {        Debug.Log("键存在");    }    // 修改值    dic1["1"] = "1000";    // 遍历    foreach(KeyValuePair kvp in dic1)    {        Debug.Log(kvp.Key + " " + kvp.Value);    }    // 移除    dic1.Remove("2");    // 清除    dic1.Clear();}

六、HashSet

HashSet 是一个包含不重复项的无序列表。

使用示例：

HashSet hashset1 = new HashSet();HashSet hashset2 = new HashSet();void Start(){    // 添加数据    hashset1.Add(1);    hashset1.Add(2);    hashset2.Add(2);    hashset2.Add(3);    // 计算数量    Debug.Log(hashset1.Count);    // 集合操作    // 取交集    hashset1.IntersectWith(hashset2);     // 取并集    hashset1.UnionWith(hashset2);     // 差集：该集合中去除两集合中的交集元素剩下的元素    hashset1.ExceptWith(hashset2);     // 对称差集：两个集合中去除交集元素剩下的元素    hashset1.SymmetricExceptWith(hashset2);     // 遍历    foreach (var v in hashset1)    {        Debug.Log(v);    }    // HastSet中没有sort}

Hashtable、HashSet和字典的区别：

• Hashtable
• 与Dictionary的区别

1. Hashtable
2. 不支持泛型，而字典支持泛型；
3. Hashtable
4. 中 key-value键值对均为 object 类型，故在存储或检索时会发生装箱拆箱操作，性能较差，而字典使用泛型，读取性能更好。
5. 单线程
6. 程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分。多线程程序中推荐使用 Hashtable, 默认的 Hashtable 允许单线程写入, 多线程读取。
7. 对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型；而 字典 非线程安全, 必须人为使用 lock 语句进行保护, 效率大减。
8. 在通过代码测试的时候发现key是整数型，Dictionary的效率比Hashtable快，如果key是字符串型，Dictionary的效率没有Hashtable快。

• HashSet
• HashSet类主要是设计用来做高性能集运算的，例如对两个集合求交集、并集、差集等。集合中包含一组不重复出现且无特性顺序的元素，HashSet拒绝接受重复的对象。

七、链表

C# 中的链表一般是 双向链表。

1.LinkedList的特性

• LinkedList无法通过下标查找元素
• ，在查找链表元素时，总是从头结点开始。
• LinkedList
• 容量是链表最大包含的元素数，会根据元素增减而动态调整容量。
• LinkedList
• 中的每个节点都属于 LinkedListNode类型。
• LinkedList
• 的值可以为 null， 并允许重复值。
• LinkedList
• 不自带排序方法。
• LinkedList
• 查询复杂度为 O(n)，操作复杂度为O(1)。

2.LinkedList使用示例

// 定义双向链表LinkedList linkList = new LinkedList();LinkedListNode node;void Start(){    // 在头部添加值    node = linkList.AddFirst(1);    // 在某个节点后添加值    linkList.AddAfter(node, 2);    // 在节点前添加值    linkList.AddBefore(node, 0);    // 在尾部添加值    linkList.AddLast(3);    // 打印链表的长度    Debug.Log(linkList.Count);    // 打印链表头节点的值    Debug.Log(linkList.First.Value);    // 打印链表尾节点的值    Debug.Log(linkList.Last.Value);    // 打印前一个节点的值    Debug.Log(node.Previous.Value); // 0    // 打印当前节点的值    Debug.Log(node.Value); // 1    // 打印后一个节点的值    Debug.Log(node.Next.Value); // 2}

八、堆栈

栈Stack 先进后出的对象集合

1. 堆栈使用示例：

// 定义Stack st1 = new Stack();void Start(){    // 入栈    st1.Push("a");    st1.Push("b");    st1.Push("c");    st1.Push("d");    // 计算栈内元素数量    Debug.Log(st1.Count);    // 出栈    string p = (string)st1.Pop();    Debug.Log(p);    // 获取栈顶元素的值，但不会出栈    string peek = (string)st1.Peek();    // 遍历    foreach(var v in st1)    {        Debug.Log(v);    }}

2. 实现栈

// 实现栈class MyStack{    class StackData    {        public StackData nextItem;        public object topData;        public StackData(StackData next, object data)        {            this.nextItem = next;            this.topData = data;        }    }    StackData top;    public void Push(object data)    {        top = new StackData(top, data);    }    public object Pop()    {        object rs1 = top.topData;        top = top.nextItem;        return rs1;    }}// 验证private void Start(){    MyStack ms = new MyStack();    ms.Push(1);    ms.Push(2);    ms.Push(3);    Debug.Log(ms.Pop());    Debug.Log(ms.Pop());    Debug.Log(ms.Pop());}

九、队列

队列Queue 先进先出的对象集合

1. 队列的使用示例：

// 声明队列，未指定类型故使用ObjectQueue queue_1 = new Queue();// 指定特定类型，减少装箱拆箱操作Queue queue_2 = new Queue();void Start(){    // 入队    queue_1.Enqueue("1");    queue_2.Enqueue(1);    queue_2.Enqueue(2);    queue_2.Enqueue(3);    // 出队    int q = queue_2.Dequeue();    // 遍历    foreach(var v in queue_2)    {        Debug.Log(v);    }    // 清空队列    queue_2.Clear();}

2. 实现队列

// 实现队列class MyQueue{    class QueueData    {        public QueueData nextItem;        public object topData;        public QueueData(QueueData last, object data)        {            last.nextItem = this;            this.topData = data;        }        public QueueData(object data)        {            this.topData = data;        }    }    QueueData top;    QueueData lastData;    public void Enqueue(object data)    {        if (top == null)        {            top = new QueueData(data);            lastData = top;        }        else        {            lastData = new QueueData(lastData, data);        }    }    public object Dequeue()    {        object rs1 = top.topData;        top = top.nextItem;        return rs1;    }}// 验证void Start(){    MyQueue q = new MyQueue();    q.Enqueue(1);    q.Enqueue(2);    q.Enqueue(3);    Debug.Log(q.Dequeue());    Debug.Log(q.Dequeue());    Debug.Log(q.Dequeue());}