数据结构

• 数据结构是计算机存储、组织、管理数据的方式
• 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

数组

数组是第一个可以管理多个数据的容器，对于系统的预定义类型中，都是针对单个数据。通过数组，可定义一个容器，来管理特定数量和类型的单个数据。

//预定义类型 单个数据
int index = 0;
float money = 3.14f;
bool enable = true;
Console.WriteLine($"{index} {money} {enable}");

//数组 容器
int[] arr = { 1, 2, 4 };
for (int i = 0; i < arr.Length; i++)
{
    Console.WriteLine($"{arr[i]}");
}

数组的不足之处在于，使用数组管理数据时，需要预先知道数组长度。而实际开发中，很多数据往往是无法事先知道元素个数的。

数组是一种非常有用的数据结构，但数组也具有严重的局限性。

• 数组元素的数据类型必须是相同的
• 在创建数组时必须知道元素个数
• 对应用程序来说，需要通过循环索引来访问元素。

因此，数组并不是使用最为方便的数据结构。C#提供了集合，通过它来管理数据将更为方便。

集合

C#提供了一系列特殊功能的类，这些类可存储任意类型的对象，且长度是可变的，统称为集合。C#编程语言中，集合结构分为泛型集合、非泛型集合。

集合命名空间

• 非泛型集合 using System.Collections
• 泛型集合 using System.Collection.Generic

集合是通过高度结构化的方式存储任意对象的类，与无法动态调整大小的数组相比，集合不仅能随意调整大小，而且对存储或检索在其中的对象提供了更为高级的方法。

集合可将一组类似的类型化对象组合在一起，.NET Framework引入了泛型集合或非强类型非泛型集合，使用时要保证元素的类型是集合所需的类型。.NET Framework的强类型集合具有自动执行元素类型验证的功能。

常用集合

• 数组 Array
• 列表 List：List<T>是与数组相当的集合类
• 动态数组 ArrayList、List<T>
• 键值对集合
  • 哈希集合/哈希表 Hashtable
  • 字典 Dictionary<K,V>
• 堆栈 Stack、Stack<T>，堆栈的特点是后进先出（LIFO, Last In First Out）。
• 队列 Queue、Queue<T>，队列的特点是先进先出（FIFO, First In First Out）。
• 可排序键值对：特点是插入、检索没有哈希表集合高效
  • 有序列键值对列表 SortedList、SortedList<K,V> 特点是占用内存更少，可通过索引访问。
  • 有序字典 SortedDictionary 特点是占用内存更多，没有索引，但插入和删除元素的速度比SortedList快。
• Set集合：特点是无序、不重复。
  • HashSet<T>集合可将HashSet类视为不包含值得Dictionary集合，与List<T>类似。
  • SortedSet<T> 在.NET4.0支持，有序无重复的集合。
• 双向链表集合：LinkedList<T>特点是增删速度快

简单数组

数组是一种数据结构可包含同一类型的多个元素

数组声明

// 声明包含整形元素的数组
int[] intArray;

使用[]声明数组是C#中使用Array类的表示法，在后台使用C#语法会创建一个派生自抽象基类Array的新类。Array类是一个抽象类，不能使用构造函数来创建数组。

数组初始化

• 声明数组后必须为数组分配内存，以保存数组的所有元素。
• 数组是引用类型，必须给它分配堆上的内存。

intArray = new int[3];

数组声明和初始化

声明并初始化数组

int[] intArray = new int[3];

使用数组初始化器为数组元素赋值

int[] intArray = new int[3]{1, 2, 4};

初始化数组时可以不指定数组大小，编译器会自动统计元素的个数。

int[] intArray = new int[]{1, 2, 4};

C#编译器中数组简化形式

int[] intArray = {1, 2, 4};

数组元素访问

声明和初始化数组后，可使用索引器访问数组元素，数组仅支持整型参数的索引器，索引器以0开始递增。

int[] intArray = {1, 2, 4};
int i1 = intArray[0];
int i2 = intArray[1];
int i3 = intArray[2];

若使用错误的索引值，即不存在对应的元素则抛出IndexOutOfRangeException类型的异常。

数组的Length属性表示数组元素个数

for(int i=0; i<intArray.Length; i++)
{

}

自定义类型的数组

class User
{
    public int UserID { get; set; }
    public string UserName { get; set; }
    public override string ToString()
    {
        return String.Format("UserID={0} UserName={1}", UserID, UserName);
    }
}

//数组元素是引用类型则必须为数组元素分配内存
//若使用数组中未分配内存的元素则会抛出NullReferenceException
User[] users1 = new User[2];
users1[0] = new User { UserID = 1, UserName = "Alice" };
users1[1] = new User { UserID = 2, UserName = "Ben" };

//对自定义类型使用数组初始化器
User[] users2 =
{
        new User { UserID = 1, UserName = "Superman" },
        new User { UserID = 2, UserName = "Batman" }
};

C#中由于数组Array是固定长度的，开发中不便于扩容，由此产生了ArrayList。

动态数组 ArrayList

动态数组可看成扩充了功能的数组，但不等同于数组。动态数组因没有限制元素的个数和数据类型而得名，可见任意类型的数据保存到动态数组中。

ArrayList与Array的区别

• Array大小是固定的，ArrayList大小可按需自动扩容。
• Array的特点是类型统一且长度固定，ArrayList是可变长数组。
• Array一次只能获取或设置一个元素的值，ArrayList允许添加、插入、移除某个范围的元素。
• Array下限可自定义，ArrayList下限始终未0。
• Array具有多维，ArrayList始终只有一维。
• Array位于System命名空间中，ArrayList位于System.Collections命名空间中。
• ArrayList是非泛型列表，可见任意Object类型作为元素。

ArrayList arrayList = new ArrayList();

动态数组常用属性

• Capacity 属性表示集合中可容纳元素的个数
• Count 属性表示集合中实际存放的元素个数

动态数组常用方法

• ArrayList.Add
• ArrayList.AddRange
• ArrayList.Remove
• ArrayList.RemoveAt
• ArrayList.Clear
• ArrayList.Contains
• ArrayList.ToArray
• ArrayList.Sort
• ArrayList.Reverse

元素的添加

动态数组提供两种元素添加的方法

• ArrayList.Add 将给定的value对象插入到动态数组ArrayList的末尾

public virtual int Add(Object value)

//数组列表集合
ArrayList arrayList = new ArrayList();
//向集合中新增元素
arrayList.Add(true);
//Console.WriteLine("count={0} capacity={1}", arrayList.Count, arrayList.Capacity);//1 4
arrayList.Add(1);
//Console.WriteLine("count={0} capacity={1}", arrayList.Count, arrayList.Capacity);//2 4
arrayList.Add(3.14);
//Console.WriteLine("count={0} capacity={1}", arrayList.Count, arrayList.Capacity);//3 4
arrayList.Add('a');
//Console.WriteLine("count={0} capacity={1}", arrayList.Count, arrayList.Capacity);//4 4
arrayList.Add("hello");
//Console.WriteLine("count={0} capacity={1}", arrayList.Count, arrayList.Capacity);//5 8
arrayList.AddRange(new int[] { 1, 3, 5, 7, 9 });                                      
//Console.WriteLine("count={0} capacity={1}", arrayList.Count, arrayList.Capacity);//10 16 

//插入元素
arrayList.Insert(0, "first");
arrayList.InsertRange(1, new string[] { "java", "c#", "c++", "c" });
//访问集合
var last = arrayList[arrayList.Count - 1];
//删除集合
//arrayList.RemoveAt(2);
arrayList.RemoveRange(0, 3);
//遍历集合
for(int i=0; i<arrayList.Count; i++)
{
    //Console.WriteLine(i+"\t"+arrayList[i]);
}

ArrayList arrlst = new ArrayList();
arrlst.AddRange(new int[] { 1, 3, 5, 7, 9 });
for(int i=0; i<arrlst.Count; i++)
{
    Console.WriteLine(i+"\t"+arrlst[i]);
    arrlst.RemoveAt(i);
}
Console.WriteLine(arrlst.Count);//2

动态数组元素的删除

• ArrayList.Clear 清空元素，从动态数组中移除所有元素。

arrayList.Clear();

• ArrayList.Remove 删除动态数组元素，从动态数组中移除特定对象的第一个匹配项。

// 从指定ArrayList中移除obj对象，若obj不存在则不引发异常，动态数组保持不变。
public virtual void Remove(Object obj)

ArrayList arrayList = new ArrayList();

arrayList.Add(99);
arrayList.Add("chowjun");

string name = new string(new char[] { 'c', 'j' });
arrayList.Add(name);

User u1 = new User() { UserID = 1, UserName = "alice" };
arrayList.Add(u1);

arrayList.Remove(u1);
Console.WriteLine(arrayList.Count);

• ArrayList.RemoveAt 删除指定元素，根据索引值移除动态数组元素。

public virtual void RemoveAt(int index)

• ArrayList.IndexOf 查找动态数组元素
• ArrayList.LastIndexOf
• ArrayList.Contains 确定某元素是否在动态数组中

// item为需确认的元素，方法返回布尔值。
public virtual bool Contains(Object item)

数组反转排序

#region ArrayList
ArrayList arrayList = new ArrayList(new int[] { 1,3,5,7,9});
//降序排序
arrayList.Sort();//默认排序为升序
arrayList.Reverse();//反转
for (int i = 0; i < arrayList.Count; i++)
{
    Console.WriteLine(arrayList[i]);
}
#endregion

初始化器

//集合类初始化器
ArrayList numbers = new ArrayList() { 1, 2, 3, 4, 5, 6, 7 };
Hashtable userage = new Hashtable()
{
    {"John", 20},
    {"Diana", 33},
    {"James", 29},
    {"Francesca",15}
};

实例：扑克牌

• 使用二位数组保存牌面对象

//枚举 花色：黑红梅方 4种
enum Suit
{
    Clubs,
    Diamonds,
    Hearts,
    Spades
}
//枚举 牌面点数 13种
enum Value
{
    Two,
    Three,
    Four,
    Five,
    Six,
    Seven,
    Eight,
    Nine,
    Ten,
    Jack,
    Queen,
    King,
    Ace
}
class Card
{
    public Suit suit;
    public Value value;
}
class Pack
{
    //4种花色
    public const int NumSuits = 4;
    //13张面值
    public const int CardsPerSuit = 13;
    //52张牌面
    //private Hashtable cardPack;
    private Card[,] cardPack;//4x13=52
    //随机发牌
    private Random randomCardSelector = new Random();
    /// <summary>
    /// 构造器：初始化扑克牌数组
    /// </summary>
    public Pack()
    {
        //生成扑克牌数组实例
        this.cardPack = new Card[NumSuits, CardsPerSuit];
        //将扑克牌数组中的每个实例都实例化为一个扑克牌对象
        for (Suit suit = Suit.Clubs; suit <= Suit.Spades; suit++)
        {
            for (Value value = Value.Two; value <= Value.Ace; value++)
            {
                this.cardPack[(int)suit, (int)value] = new PlayingCard(suit, value);
            }
        }
    }
    /// <summary>
    /// 发牌程序
    /// </summary>
    /// <returns></returns>
    public Card DealCardFromPack()
    {
        //随机生成一种花色
        Suit suit = (Suit)randomCardSelector.Next(NumSuits);
        //判断该随机花色是否全部发完牌
        while (this.IsSuitEmpty(suit))
        {
            //重新随机生成一个花色
            suit = (Suit)randomCardSelector.Next(NumSuits);
        }
        //随机生成牌面值
        Value value = (Value)randomCardSelector.Next(CardsPerSuit);
        //随机产生一张扑克牌，其在数组中的值不为空。
        while(this.IsCardAlreadyDealt(suit, value))
        {
            value = (Value)randomCardSelector.Next(CardsPerSuit);
        }
        //设置牌面
        Card card = this.cardPack[(int)suit, (int)value];
        this.cardPack[(int)suit, (int)value] = null;

        return card;
    }
    /// <summary>
    /// 判断是否为空牌面
    /// </summary>
    /// <param name="suit"></param>
    /// <returns></returns>
    private bool IsSuitEmpty(Suit suit)
    {
        bool result = true;
        //判断具有suit花色的每张牌（2~A），若有一张牌不是null的result值为false，否则为true。
        for(Value value=Value.Two; value<=Value.Ace; value++)
        {
            if(!IsCardAlreadyDealt(suit, value))
            {
                result = false;
                break;
            }
        }
        return result;
    }
    //判断数组中的元素为null则表示该牌已经发出
    private bool IsCardAlreadyDealt(Suit suit, Value value)
    {
        return (this.cardPack[(int)suit, (int)value] == null);
    }
}
class Hand
{
    public const int HandSize = 13;
    //用来存储玩家手中得到的牌
    //private Card[] cards = new Card[HandSize];
    public ArrayList cards = new ArrayList();
    private int playingCardCount = 0;
    //给玩家发牌
    public void AddCardToHand(Card cardDealt)
    {
        //使用ArrayList方式
        //if(this.playingCardCount >= HandSize)
        //{
        //    throw new ArgumentException("too many cards");
        //}
        //this.cards[this.playingCardCount] = cardDealt;
        //this.playingCardCount++;

        //使用Hashtable方式
        if(this.cards.Count >= HandSize)
        {
            throw new ArgumentException("too many cards");
        }
        this.cards.Add(cardDealt);
    }                                   
}

• 使用Hashtable保存牌面

    //枚举 花色：黑红梅方 4种
    enum Suit
    {
        Clubs,
        Diamonds,
        Hearts,
        Spades
    }
    //枚举 牌面点数 13种
    enum Value
    {
        Two,
        Three,
        Four,
        Five,
        Six,
        Seven,
        Eight,
        Nine,
        Ten,
        Jack,
        Queen,
        King,
        Ace
    }
    class Card
    {
        public Suit Suit;
        public Value Value;
        public Card(Suit suit, Value value)
        {
            Suit = suit;
            Value = value;
        }
    }
    class Pack
    {
        //4种花色
        public const int NumSuits = 4;
        //13张面值
        public const int CardsPerSuit = 13;
        //52张牌面
        private Hashtable cardPack;             
        //随机发牌
        private Random randomCardSelector = new Random();
        /// <summary>
        /// 构造器：初始化扑克牌数组
        /// </summary>
        public Pack()
        {
            //存入52张牌
            this.cardPack = new Hashtable();
            //顺序读取花色
            for (Suit suit = Suit.Clubs; suit <= Suit.Spades; suit++)
            {
                //为每种花色生成
                SortedList cardsInSuit = new SortedList();
                for (Value value = Value.Two; value <= Value.Ace; value++)
                {
                    cardsInSuit.Add(value, new Card(suit, value));
                }
                this.cardPack.Add(suit, cardsInSuit);
            }
        }
        /// <summary>
        /// 发牌程序
        /// </summary>
        /// <returns></returns>
        public Card DealCardFromPack()
        {
            //随机生成一种花色
            Suit suit = (Suit)randomCardSelector.Next(NumSuits);
            //判断该随机花色是否全部发完牌
            while (this.IsSuitEmpty(suit))
            {
                //重新随机生成一个花色
                suit = (Suit)randomCardSelector.Next(NumSuits);
            }
            //随机生成牌面值
            Value value = (Value)randomCardSelector.Next(CardsPerSuit);
            //随机产生一张扑克牌，其在数组中的值不为空。
            while (this.IsCardAlreadyDealt(suit, value))
            {
                value = (Value)randomCardSelector.Next(CardsPerSuit);
            }
            //设置牌面
            SortedList cardsInSuit = (SortedList)cardPack[suit];
            Card card = (Card)cardsInSuit[value];
            cardsInSuit.Remove(value);

            return card;
        }
        /// <summary>
        /// 判断是否为空牌面
        /// </summary>
        /// <param name="suit"></param>
        /// <returns></returns>
        private bool IsSuitEmpty(Suit suit)
        {
            bool result = true;
            //判断具有suit花色的每张牌（2~A），若有一张牌不是null的result值为false，否则为true。
            for (Value value = Value.Two; value <= Value.Ace; value++)
            {
                if (!IsCardAlreadyDealt(suit, value))
                {
                    result = false;
                    break;
                }
            }
            return result;
        }
        //判断数组中的元素为null则表示该牌已经发出
        private bool IsCardAlreadyDealt(Suit suit, Value value)
        {
            SortedList cardsInSuit = (SortedList)cardPack[suit];
            return !cardsInSuit.ContainsKey(value);
        }
    }
    class Hand
    {
        public const int HandSize = 13;
        //用来存储玩家手中得到的牌
        //private Card[] cards = new Card[HandSize];
        public ArrayList cards = new ArrayList();
        private int playingCardCount = 0;
        //给玩家发牌
        public void AddCardToHand(Card cardDealt)
        {
            //使用ArrayList方式
            //if(this.playingCardCount >= HandSize)
            //{
            //    throw new ArgumentException("too many cards");
            //}
            //this.cards[this.playingCardCount] = cardDealt;
            //this.playingCardCount++;

            //使用Hashtable方式
            if(this.cards.Count >= HandSize)
            {
                throw new ArgumentException("too many cards");
            }
            this.cards.Add(cardDealt);
        }                                   
    }

ArrayList的优点在于它是可变长数组，可将任意多的数据Add到ArrayList中，其内部维护的数组当长度不足时，会自动扩容为原来的两倍。

ArrayList 的缺点是存入ArrayList中的数据都是Object类型的，如果将值类型进行存入取出操作，就会发生装箱拆箱操作（值类型与引用类型相互转换），而装箱拆箱耗时且影响程序性能的。所以在 .NET2.0 泛型出现后，就提供了List<T>。也就是说，List<T>实际上是ArrayList的泛型版本，由于List<T>不再需要装箱拆箱，可直接存取。虽然List<T>与ArrayList操作上是一致的，不过使用前需设置好类型，否则是不允许Add的。

泛型集合 List<T>

从性能上来说，如果存取的数组仅有一种数据类型，那么List<T>是最优选择。

• List<T>只能存储固定类型的对象的一种集合
• 要使用List<T>必须引入System.Collections.Generic命名空间
• List<T>是一个C#内置的类
• List<T>本质和数组是一样的
• List<T>类的内部维护了一个数组
• List<T>比数组灵活，List<T>类封装了方便操作内部数组各种方法，可方便的对数据进行增加、删除、修改等操作。
• List<T>的长度是可以动态改变的
• 实例化List<T>类型对象时时无需指定长度的

创建泛型集合

# 引入命名空间
using System.Collections.Generic;
# 实例化对象
List<T> list = new List<T>();

List<int> list = new List<int>();

泛型声明

如果存取的数组是一个变长且数据类型多样，那最佳的选择仍然是ArrayList。

泛型集合基本操作

增加数据

# 向集合中添加数据，数据会不断地添加到集合，形成一种类似于排队的效果。
集合名.Add(Value)

使用默认的构造函数创建的空列表，元素添加到列表后，列表的容量会扩大为可接纳4个元素。如果添加到第5个元素，列表的大小就重新设置为包含8个元素。如果8个元素仍旧不够，列表的大小会重新设置为包含16个元素。每次都会将列表的容量重新设置为原来的2倍。

如果列表的容量改变了，整个集合就要重新分配到一个新的内存块中。在List<T>泛型类的实现代码中，使用一个T类型的数组。通过重新分配内存，创建一个新数组，Array.Copy()方法将旧数组中的元素复制到新数组中。为节省时间，如果事先知道列表中元素的个数，就可以用构造函数定义其容量。

# 创建容量为10个元素的集合
List<int> intList = new List<int>(10);

# 将集合容量重新设置为20
intList.Capacity = 20;

# 获取集合元素个数
Console.WriteLine($"Capactiy={intList.Capacity} Count={intList.Count}");

如果已经将元素添加到列表中，且不希望添加更多的元素，可调用TrimExcess()方法，去除不需要的容量。但是，因为重新定位需要时间，所以如果元素个数超过了容量的90%，TrimExcess()方法就说明也不做。

intList.TrimExcess();

List<T>泛型集合类的实现代码中，使用了一个T类型的数组。通过重新分配内存，创建了一个新数组，

批量添加

使用List<T>类的AddRange()方法可一次给集合添加多个元素，因为AddRange()方法的参数是IEnumerable<T>类型的对象，所以可以传递一个数组。

查询数据

# 获取指定索引位置的数据
集合名[索引值]

• List<T> 的索引和数组一样，都是从0开始。
• List<T>的长度通过集合名.Count属性获取

Capacity属性可获取和设置集合的容量，集合容量与集合元素个数不同，集合元素个数使用Count属性读取，集合容量总是大于或等于元素个数。只要不将元素添加到列表中，元素个数就为0。

//实例化泛型集合
List<int> intList = new List<int>();
            
//增加元素
intList.Add(1);
intList.Add(2);
intList.Add(4);

//集合容量与大小
Console.WriteLine($"Capacity={intList.Capacity} Count={intList.Count}");//4 3

管理对象

1. 定义对象类

class User
{
    public int UserID;
    public string UserName;
    public User(int userid, string username)
    {
        this.UserID = userid;
        this.UserName = username;   
    }
    public override string ToString()
    {
        return string.Format($"UserID={UserID} UserName={UserName}");
    }

}

2. 实例化对象并添加到集合

//定义数据
List<User> users = new List<User>();
//实例化对象
User u1 = new User(1, "alice");
User u2 = new User(2, "ben");
User u3 = new User(3, "carl");
//添加对象到集合
users.Add(u1);
users.Add(u2);
users.Add(u3);

//添加对象到集合
users.Add(new User(4, "elva"));
users.Add(new User(5, "fifi"));
users.Add(new User(6, "gaga"));

使用List<T>类的AddRange()方法，可一次性给集合添加多个元素，因为AddRange()的参数是IEnumerable<T>类型的对象，所以可传递一个数组。

users.AddRange(new User[] {
    new User(7, "han"),
    new User(8, "irk"),
    new User(9, "lala")
});

如果在实例化列表时知道集合元素个数，可将实现IEnumerable<T>类型的任意对象传递给类的构造函数，类似AddRange()方法。

List<User> userlist = new List<User>(new User[]
{
    new User(1, "alice"),
    new User(2, "ben"),
    new User(3, "carl")
});

3. 插入元素

使用Insert()方法可在位置插入元素

userlist.Insert(0, new User(4, "elva"));

使用InsertRange()方法可批量插入多个元素，类似AddRange()方法。

userlist.InsertRange(1,new User[]
{
        new User(5,"fifi"),
        new User(6,"gaga"),
});

如果索引集大于集合中的元素个数，则会抛出ArgumentOutOfRangeException类型的异常。

4.访问元素

实现了IList和IList<T>接口的所有类都提供了一个索引器，可使用索引器，通过传递元素索引号来访问元素。第一个元素可使用索引值为0来访问。

Console.WriteLine(userlist[0]);

3. 从集合中删除指定数据

指定索引删除元素

users.RemoveAt(0);

按索引删除比较快，因为必须在集合中搜索要删除的元素。Remove()方法先在集合中搜索，使用IndexOf()方法获取元素的索引，再使用该索引删除元素。IndexOf()方法会先检查元素类型是否实现了IEquatable<T>接口。如果实现了，则调用接口的Equals()方法，确定集合中的元素是否等于传递给Equals()方法的元素。如果没有实现这个接口，则使用Object类的Equals()方法比较这些元素。Object类中的Equals()方法默认实现代码对值类型进行按位比较，对引用类型仅比较其引用。

指定元素删除

//删除元素
users.Remove(u1);

4.修改集合中指定数据

5.查询搜索显示集合中的数据

有不同的方式在集合中搜索元素，可获得要查找元素的索引，或搜索元素本身。

• List.IndexOf()
IndexOf()方法需要将一个对象作为参数，若在集合中找到该元素，方法返回该元素的索引。若没有找到元素则返回-1。IndexOf()方法使用IEquatable<T>接口来比较元素。

//定义数据
List<User> users = new List<User>();
//实例化对象
User u1 = new User(1, "alice");
User u2 = new User(2, "ben");
User u3 = new User(3, "carl");
//添加对象到集合
users.Add(u1);
users.Add(u2);
users.Add(u3);       
//删除元素
users.Remove(u1);
//查询元素
Console.WriteLine(users.IndexOf(u1));//-1
Console.WriteLine(users.IndexOf(u2));//0
Console.WriteLine(users.IndexOf(u3));//1 

• List.LastIndexOf()
• List.FindIndex()
• List.FindLastIndex()
• List.Find()

User user = users.Find(x=>x.UserName == "alice");

• List.FindLast()

若只检查元素是否存在，List<T>仅仅提供了Exists()方法。

综合案例：用户管理

（1）创建用户实体类 UserEntity

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace UserManage
{
    /// <summary>
    /// 用户实体类
    /// </summary>
    public class UserEntity
    {
        public int UserID { get; set; }
        public string UserName { get; set; }
        public string Phone { get; set; }
        public string Email { get; set; }
        public UserEntity(string username, string phone, string email)
        {

            this.UserID = new Random().Next(10000000, 99999999);
            this.UserName = username;
            this.Phone = phone;
            this.Email = email;
        }
        public override string ToString()
        {
            return string.Format("{0,-10}\t{1,-10}\t{2,-11}\t{3,-20}", UserID, UserName, Phone, Email);
        }
    }
}

（2）创建用户控制器UserController

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace UserManage
{
    /// <summary>
    /// 用户控制器
    /// </summary>
    public class UserController
    {
        List<UserEntity> userlist = new List<UserEntity>();
        public void Read()
        {
            if(userlist.Count == 0)
            {
                Console.WriteLine("Message: no data...");
            }
            foreach(UserEntity item in userlist)
            {
                Console.WriteLine(item);
            }
        }
        public void Create(UserEntity item)
        {
            userlist.Add(item);
        }
        public void Delete(string key, string val)
        {
            if(key.ToLower() == "userid")
            {
                int userid = Convert.ToInt32(val);
                RemoveByUserID(userid);
            }
            else if(key.ToLower() == "phone")
            {                                    
                RemoveByUserPhone(val);
            }           
        }
        public void RemoveByUserID(int userid)
        { 
            UserEntity user = userlist.Find(x => x.UserID == userid);
            if (user == null)
            {
                Console.WriteLine("Message: user does not exists...");
            }
            userlist.Remove(user);
        }
        public void RemoveByUserPhone(string phone)
        {                              
            UserEntity user = userlist.Find(x => x.Phone == phone);
            if (user == null)
            {
                Console.WriteLine("Message: user does not exists...");
            }
            userlist.Remove(user);
        }        
    }
}

（3）创建用户视图UserView

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace UserManage
{      
    class UserView
    {
        public static void Main(string[] args)
        {
            //实例化控制器程序
            UserController userController = new UserController();
            //接收用户输入
            while (true) { 
                string cmd = string.Empty;
                Console.WriteLine("Please Input Option: [0]EXIT [1]CREATE [2]UPDATE [3]READ [4]DELETE [5]SEARCH");
                Console.Write("Option: ");
                cmd = Console.ReadLine();
                switch (cmd)
                {
                    case "0":
                        Process.GetCurrentProcess().Kill();
                        break;
                    case "1":
                        //接收数据
                        Console.Write("UserName: ");
                        string username = Console.ReadLine();
                        Console.Write("Phone: ");
                        string phone = Console.ReadLine();
                        Console.Write("Email: ");
                        string email = Console.ReadLine();
                        //增加数据
                        userController.Create(new UserEntity(username, phone, email));
                        break;
                    case "2": break;
                    case "3":
                        userController.Read();
                        break;
                    case "4":
                        Console.WriteLine("Please Input Delete Option: [1]UserID [2]Phone");
                        Console.Write("Option: ");
                        string command = Console.ReadLine();
                        if(command == "1")
                        {
                            Console.Write("UserID:");
                            string input = Console.ReadLine();
                            int userid = 0;
                            if (!int.TryParse(input, out userid))
                            {
                                Console.WriteLine("Error: username must be numberic");
                            }
                            else
                            {
                                userController.RemoveByUserID(userid);
                            }
                        }
                        else if(command == "2")
                        {
                            Console.Write("Phone:");
                            string input = Console.ReadLine(); 
                            long output = 0;
                            if (!long.TryParse(input, out output))
                            {
                                Console.WriteLine("Error: phone must be numberic");
                            }
                            else
                            {
                                userController.RemoveByUserPhone(output.ToString());
                            }
                        }
                        else
                        {
                            Console.WriteLine("Please input delete option...");
                        }                 
                        break;
                    default: Console.WriteLine("Please Input Option Number");break;
                }
                Console.WriteLine("=====================================================================");
            }                     
        }                     
    }
}

哈希表 Hashtable

Hashtable称为哈希表，表示键值对的集合，其键值对根据键的哈希代码进行组织，哈希表的每个元素都是存储在DictionaryEntry对象中的键值对。

• 哈希表是键值对的集合，类似于字典。
• 哈希表在查找元素时速度很快
• 哈希表的键值对集合中的键绝对不能重复
• 哈希表的键不能为空引用，值可以。

哈希表的构造函数

• 使用默认的初始容量、加载因子、哈希代码提供程序和比较器进行初始化Hashtable类的新的空实例。

public Hashtable()

• 使用指定的初始容量、默认加载因子、默认哈希代码提供程序和默认比较器来初始化Hashtable类的新的空实例。

public Hashtable(int capacity)
# capacity 表示Hashtable对象最初可以包含的元素的近似数量

哈希表的属性

Hashtable.Count
获取包含在Hashtable中的键值对的数目

Hashtable.IsFixedSize
获取一个值，该值指示哈希表是否具有固定大小。

Hashtable.IsReadOnly
获取一个值，该值指示哈希表是否为只读。

Hashtable.IsSynchronized
获取一个值，该值只是是否同步对哈希表的访问。

Hashtable.Item
获取或设置与指定的键相关联的值

Hashtable.Keys
获取包含哈希表中的键的ICollection

Hashtable.SyncRoot
获取可用于同步哈希表访问的对象

Hashtable.Values 
获取包含哈希表中的值的ICollection

哈希表添加元素

# 将带有指定键和值的元素添加到哈希表中
public virtual void Add(Object key, Object value)
# key 表示要添加元素的键名
# value 表示要添加元素的键值，可为空引用。

若哈希表指定了初始容量，则不用限定向哈希表对象中添加的因子个数，其容量会根据加载的因子自动增加。

Hashtable ht = new Hashtable();
ht.Add("UserID", 1);
ht.Add("UserNO", "BH0001");
ht.Add("UserName", "Tim");
ht.Add("UserGender", 1);
int count = ht.Count;
Console.WriteLine(count); //4

哈希表元素的删除

# 从哈希表中移除所有元素
public virtual void Clear() 
# 从哈希表中移除带有指定键的元素
public virtual void Remove(Object key) 

Hashtable ht = new Hashtable();
ht.Add("UserID", 1);
ht.Add("UserNO", "BH0001");
ht.Add("UserName", "Tim");
ht.Add("UserGender", 1); 
Console.WriteLine(ht.Count); //4

ht.Remove("UserGender");
Console.WriteLine(ht.Count); //3  

ht.Clear();
Console.WriteLine(ht.Count); //0

哈希表的遍历

哈希表的遍历使用foreach，由于哈希表中的元素是键值对，因此需要使用DictionaryEntry类型来进行遍历。DictionaryEntry类型表示一个键值对的集合。

Hashtable ht = new Hashtable();
ht.Add("UserID", 1);
ht.Add("UserNO", "BH0001");
ht.Add("UserName", "Tim");
ht.Add("UserGender", 1);       
foreach(DictionaryEntry dic in ht)
{
    Console.WriteLine($"{dic.Key} = {dic.Value}");
}

哈希表元素的查找

# 确定哈希表中是否包含特定的键
public virtual bool Contains(Object key)
# key 表示要在哈希表中定位的键
# return 若哈希表中包含具有指定键的元素则返回true，否则返回false。

字典 Dictionary<TKey, TValue>

字典表示一种复杂的数据类型，其数据结构允许按照某个键来访问元素，因此也被称为映射或散列表。

字典的主要特征是能够根据键快速查找值，也可以自由添加和删除元素，类似List<T>，但没有在内存中移动后续元素的性能开销。

将键添加到字典后，键会转换为一个散列，利用散列创建一个数字，它将索引和值关联起来。然后索引包含了一个到值得链接。因为一个索引项可以关联多个值，索引可存储为一个树形结构。

Dictionary集合是一种键值对集合，该集合中的每个数据都由两部分组成：键和值。其中键必须唯一，而值可以有重复。通过键去寻找值，这一点和List<T>不同。在List<T>泛型集合中，只限定了数据T的类型，而在Dictionary<K,V>泛型集合中，需要分别限定键K和值V的类型。

Dictionary<[key], [value]>

当大量使用key来查找value的时候，Hashtable无疑是最佳选择。由于Hashtable和ArrayList一样都是非泛型的，存入的value均是object类型，因此存储时都会发生装箱拆箱操作，进而影响程序性能。因此，出现了Dictonary<T,T>，也就是说Dictionary<T,T>实际上就是Hashtable的泛型版本。Dictonary<T,T>不仅存取快速而且无需装箱拆箱，同时它优化了算法，其Hashtable是0.72，从而减少了容量的浪费。

Dictionary<string, User> dict = new Dictionary<string, User>();

字典Dictonary同样也是用来表示键值对的集合，由于它是一个泛型，本身又具有集合的功能，因此可见其视为数组。

键的类型

用作字典中的键必须重写Object类的GetHashCode()方法，只要字典类需要确定元素的位置，就要调用GetHashCode()方法，并返回int由字典用于计算在对应位置放置元素的索引。它涉及素数，所以字典的容量是一个素数。因此，字典的性能取决于GetHashCode()方法的实现代码。

GetHashCode()方法实现代码必要条件

• 相同的对象总是返回相同的值，不同的对象可以返回相同的值。
• 执行比较快，计算的开销不大。
• 不能抛出异常
• 至少使用一个实例字段
• 散列代码应平均分布在int可以存储的整个数字范围上
• 散列代码最好在对象的生存期中不发生变化

Hashtable与Dictionary异同点

1. 在单线程程序中推荐使用Dictionary，由于具有泛型优势且读取速度较快，其容量利用会更加充分。
2. 在多线程程序中推荐使用Hashtable，默认的Hashtable允许单线程写入多线程读取，对Hashtable进一步调用Synchronized()方法可获得完全线程安全的类型。而Dictionary是非线程安全的，必须人为使用lock语句进行保护，其效率大减。
3. 经过测试发现，但key是整型时Dictionary的操作效率要高于Hashtable，而当key是字符串时则Dictionary的效率并没有Hashtable的快。
4. Dictionary有按插入顺序排列数据的特性，但是当调用Remove()方法删除节点后原来的顺序会被打乱掉。因此在需要体现顺序的场景中使用Dictionary能获得一定的便利。
5. 遍历Dictionary时会采用插入时的顺序，而遍历Hashtable则是打乱掉的。

泛型

Dictionary<K,V>基本使用

创建字典泛型集合

• 引入命名空间using System.Collections.Generic
• 实例化对象 Dictionary<K类型,V类型> 集合名称 = new Dictionary<K类型, V类型>();

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace TestApp
{         
    class Program
    {           
        /*统计文本中的单词数量*/
        static Dictionary<string, int> CountWords(string text)
        {
            var frequencies = new Dictionary<string, int>();

            string[] words = Regex.Split(text, @"\W+");
            foreach(string word in words)
            {
                if (frequencies.ContainsKey(word))
                {
                    frequencies[word]++;
                }
                else
                {
                    frequencies[word] = 1;
                }
            }

            return frequencies;
        }
        static void Main(string[] args)
        {
            string text = @"Do you like green eggs and ham? I do not like them, Sam-I-am. I do not like green eggs and ham.";
            Dictionary<string, int> frequencies = CountWords(text);
            foreach(KeyValuePair<string, int> entry in frequencies)
            {
                string word = entry.Key;
                int frequency = entry.Value;
                Console.WriteLine("{0} {1}", word, frequency);
            }
            Console.ReadKey();
        }
    }
}

字典数据操作

字典增加数据

# 向字典中添加数据
Dictionary.Add(K, V)

字典的键是唯一的，不能添加两个相同键名的数据。

查询字典数据

# 获取指定键名所对应的键值
字典泛型集合名[键名]

字典泛型集合的长度可通过字典泛型集合名称.Count属性获取

删除数据

# 删除指定键名所对应的数据
字典泛型集合名.Remove(键名);

修改数据

# 给制定键名所对应的数据重新赋值
字典泛型集合名[键名]=新值;

遍历字典集合

# 实例化字典泛型集合
Dictionary<string, string> dic = new Dictionary<string, string>();
dic.Add("Name", "chowjun");
dic.Add("Email", "chowjun520@hotmail.com");

# 不能添加相同键名的数据
//dic.Add("Name", "junchow");

# 修改键名所对应的数据
dic["Name"] = "junchow";

# 删除指定键名所对应的数据
dic.Remove("Email");

# 获取键名对应的数据
Console.WriteLine(dic["Name"]);//junchow

# 获取字典的元素个数
Console.WriteLine(dic.Count);//1

# 获取所有键名
//dic.Keys;

#遍历字典集合
foreach(var item in dic.Keys)
{
    Console.WriteLine($"Key={item}\tValue={dic[item]}");
}

# 实例化字典泛型集合
Dictionary<Guid, long> dic = new Dictionary<Guid, long>();

# 添加
Guid guid = Guid.NewGuid();
dic.Add(guid, new Random().Next(100000,999999));

# 修改
dic[guid] = new Random().Next(100000, 999999); 

# 遍历
foreach(KeyValuePair<Guid, long> item in dic)
{
    Console.WriteLine($"TKey={item.Key}\tTValue={item.Value}");
}

字典泛型集合应用场景

凡是键值对结构的数据都可以使用Dictionary<K,V>

例如：

• 电脑桌面的快捷方式，图标是键，应用地址是值。
• 城市的邮编，城市名为键，邮政编码是值。
• 电话号码本，姓名为键，电话号码为值。

案例：电话本数据管理