C#学习笔记（十八）：数据结构和泛型

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› c#›C#教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

数据结构

只有这四种

a、集合：数据之间没有特定的关系

b、线性结构：数据之间有一对一的前后联系

c、树形结构：数据之间有一对多的关系，一个父节点有多个子节点，一个子节点只能有一个父节点

d、图状结构：数据之间有多对多的关系，一个节点可以有多个子节点，也可以多个父节点

线性结构：列表、链表、栈、队列

树形结构：字典

列表（数据量小，100以下，无脑使用）

1、列表可以动态增长，数组不可以动态增长

2、列表可以不通过下标添加元素，数组不可以

3、列表索引元素特别快（首地址加下标），但是内存中的元素必须相连，不允许跳过单元格

4、列表修改元素效能差，当删除（插入）元素时，需要把后面的元素一个个的向前（向后）移

链表（数据量大，万计以上）

若干个小块构成，每个小块由三个单元格构成，若干个单元格相互关联（当前元素的后一元素指向下一个元素的当前元素）

双向链表：前一元素、当前元素、后一元素

单向链表：当前元素、后一元素

1、动态增长

2、C#链表没有下标

3、索引元素特别慢，一个个查找，可以用迭代器优化

4、元素不是相连的，修改元素特别快

散列结构：数据取余，哈希表，哈希算法MD5（把无限的数据存储在有限的空间中）

碰撞：两个数据取余相同，尽量避免数据相同（索引：必须唯一，值：可以相同）

1、允许任意类型（不考虑具体类型，只考虑变化关系）

2、但必须是同一类型

泛型：统一代码逻辑应用于所有类型

泛型集合和集合功能相似，增加了泛型的特性

集合：需要转成Object，存在性能消耗，转换会出错

泛型集合：通过翻译官转化，效能无损

List列表

Capcity默认长度、Count实际元素个数、Data（Int[]）数组

添加元素超过默认长度，会调用Data重新创建一个Capcity * 2的新数组，旧数组变为垃圾

添加准确的初始长度，或给出一个合理基数，可以减少性能消耗

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace m1w4d4_list
{
    //在我们要使用泛型集合时
    //首先我们要确认是否using System.Collections.Generic;
    class Monster
    {
    }
    class Program
    {
        //我们学习了列表的数据结构（增删改查）
        //实例化，属性
        //增加元素
        //删除元素
        //访问，修改元素
        //插入元素
        //查找元素
        static void Main(string[] args)
        {
            #region 泛型列表
            //泛型列表允许我们做任意类型的列表，只需要在<>中填入相应类型
            List<int> list = new List<int>();//这种构造让我使用默认的初始长度（4）
            List<int> list1 = new List<int>(10);//这种构造允许我们设置列表的初始长度
            List<Monster> list3 = new List<Monster>();
            //list.Capacity; Capacity表示列表的实际长度
            //list.Count; Count表示list中有多少个有意义的元素
            //添加元素
            list.Add(123);
            //访问元素 
            //通过索引器可以访问对应元素，但索引器的标号必须小于Count        
            Console.WriteLine(list[0]);
            Console.WriteLine(list.Capacity);//初始为0.由Add创建
            Console.WriteLine();
            //修改元素
            for (int i = 0; i < 10; i++)
            {
                list.Add(i);
            }
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i] + "  ");
            }
            Console.WriteLine("\t");
            list[4] = 999;
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i] + "  ");
            }
            Console.WriteLine("\n");
            //删除元素
            list.RemoveAt(0);//移除指定下标中的元素
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i] + "  ");
            }
            Console.WriteLine();
            list.Remove(999);//移除指定元素（从头查找到的）
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i] + "  ");
            }
            Console.WriteLine("\n");
            //插入元素
            //list.Insert();//在指定下标处，插入指定元素，原元素及其后的元素均排在插入元素的后方
            list.Insert(4, 999);
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i] + "  ");
            }
            Console.WriteLine("\n");
            //查找元素
            //从头查找
            int id = list.IndexOf(999);//根据元素从头查找，并返回找到的第一个元素的位置
            Console.WriteLine($"从头查找，删除值为{list[id]}的元素");
            list.RemoveAt(id);//删除从头找到的第一个元素
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i] + "  ");
            }
            Console.WriteLine("\n");
            //从尾查找
            int id1 = list.LastIndexOf(8);//根据元素从尾查找，并返回找到的第一个元素的位置
            Console.WriteLine($"从头查找，删除值为{list[id1]}的元素");
            list.RemoveAt(id);//删除从尾找到的第一个元素
            for (int i = 0; i < list.Count; i++)
            {
                Console.Write(list[i] + "  ");
            }
            Console.WriteLine("\n");
            #endregion
            //遍历
            //用for，遍历次数是Count
            //for (int i = 0; i < list.Count; i++)
            //{
            //    Console.Write(list[i] + "  ");
            //}
            //用foreach
            //foreach (var item in list)
            //{
            //}
            #region 练习1
            //建立一个整型List，给List中添加倒序添加10-1
            Console.WriteLine("建立一个整型List，给List中添加倒序添加10-1");
            for (int i = 10; i >= 1; i--)
            {
                list1.Add(i);
            }
            //删除List中的第五个元素
            list1.RemoveAt(4);
            //遍历剩余元素并打印出来
            foreach (var item in list1)
            {
                Console.Write(item + "  ");
            }
            Console.WriteLine();
            #endregion        
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace m1w4d4_list1
{
    #region 泛型列表排序IComparable
    public class Monster : IComparable<Monster>
    {
        public Monster(string name, int attack, int defend, int health)
        {
            this.name = name;
            this.attack = attack;
            this.defend = defend;
            this.health = health;
        }
        public string name;
        public int attack;
        public int defend;
        public int health;
        public override string ToString()
        {
            return string.Format("{0},攻击{1},防御{2}，血量{3}", name, attack, defend, health);
        }
        public static int DefendSort(Monster a, Monster b)
        {
            return a.defend - b.defend;
        }
        public int CompareTo(Monster other)
        {
            //比较某一个参数，返回对应值
            //如果大就返回大于0的数，自己排在对比参数的后面
            //如果小就返回小于0的数，自己排在对比参数的前面
            //如果相等就返回0，不换
            //这样在外部调用Sort的时候会形成一个以这个参数为标准的升序排序
            return attack - other.attack;
        }
    }
    #endregion
    #region 泛型列表排序IComparer
    class MonsterAttackSort : IComparer<Monster>
    {
        //这个方法是用 参数x 和参数y 比较，返回相应整数
        //如果返回大于零的数，x将放在y的后面，如果用升序的逻辑，就是x比y大
        //如果返回大于零的数，x将放在y的后面
        //如果返回零，表示相等
        public int Compare(Monster x, Monster y)
        {
            return x.attack - y.attack;
        }
    }
    class MonsterDefendSort : IComparer<Monster>
    {
        public int Compare(Monster x, Monster y)
        {
            return x.defend - y.defend;
        }
    }
    class MonsterHealthSort : IComparer<Monster>
    {
        public int Compare(Monster x, Monster y)
        {
            return x.health - y.health;
        }
    }
    #endregion
    class Program
    {
        #region 泛型列表排序Comparition
        static int AttackSort(Monster a, Monster b)
        {
            return a.attack - b.attack;
        }
        #endregion
        //用一个List排序
        //泛型集合都是实现System.Collections.Generic;中对应接口的一些类型
        //如果要实现一个自定义类的排序
        //1、实现一个IComparable的接口
        //2、调用Sort的重载，用一个接口类型IComparer
        //3、调用Sort的重载，用一个委托类型Comparition
        //需要一个和List装载的类型相同的一排序方法 int 函数名 （对应类型 对应类型）
        static void Main(string[] args)
        {
            #region 泛型列表排序
            Random roll = new Random();
            List<int> list = new List<int>();
            for (int i = 10 - 1; i >= 0; i--)
            {
                list.Add(roll.Next(0, 100));
            }
            foreach (var item in list)
            {
                Console.Write(item + "  ");
            }
            Console.WriteLine("\n");
            list.Sort();//通过Sort对List进行（升序）排序
            foreach (var item in list)
            {
                Console.Write(item + "  ");
            }
            Console.WriteLine("\n");
            list.Reverse();//通过Sort对List进行（升序）排序
            foreach (var item in list)
            {
                Console.Write(item + "  ");
            }
            Console.WriteLine("\n");
            #endregion
            #region 排100000个数
            //用冒泡排序，排100000个数，速度没有Sort快
            List<int> list1 = new List<int>();
            for (int i = 0; i < 100000; i++)
            {
                list1.Add(roll.Next(0, 100));
            }
            int temp = list1[0];
            for (int i = 0; i < 100000 - 1; i++)
            {
                for (int j = 0; j < 100000 - 1 - i; j++)
                {
                    if (list1[i] > list1[i + 1])
                    {
                        temp = list1[i];
                        list1[i] = list1[i + 1];
                        list1[i + 1] = temp;
                    }
                }
            }
            foreach (var item in list1)
            {
                Console.Write(item + "  ");
            }
            Console.WriteLine("\n");
            //用Sort排序，排100000个数
            List<int> list2 = new List<int>();
            for (int i = 0; i < 100000 - 1; i++)
            {
                list2.Add(roll.Next(0, 100));
            }
            list2.Sort();
            foreach (var item in list2)
            {
                Console.Write(item + "  ");
            }
            Console.WriteLine("\n");
            #endregion
            #region 泛型列表排序IComparable
            List<Monster> monsterList = new List<Monster>();
            for (int i = 0; i < 10; i++)
            {
                monsterList.Add(new Monster("怪物" + (i + 1) + "号", roll.Next(10, 20), roll.Next(10, 20), roll.Next(10, 20)));
            }
            monsterList.Sort();
            foreach (var item in monsterList)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine("\n");
            #endregion
            #region 泛型列表排序IComparer
            //排序器
            MonsterAttackSort mAttackSort = new MonsterAttackSort();
            MonsterDefendSort mDefendSort = new MonsterDefendSort();
            MonsterHealthSort mHealthSort = new MonsterHealthSort();
            monsterList.Sort(mAttackSort);
            monsterList.Sort(mDefendSort);
            monsterList.Sort(mHealthSort);
            //monsterList.Reverse();
            foreach (var item in monsterList)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine("\n");
            #endregion
            #region 泛型列表排序Comparition
            monsterList.Sort(AttackSort);
            foreach (var item in monsterList)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine("\n");
            monsterList.Sort((a,b)=>-(a.health - b.health));
            foreach (var item in monsterList)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine("\n");
            monsterList.Sort(Monster.DefendSort);
            foreach (var item in monsterList)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine("\n");
            #endregion
        }
    }
}

复习

委托补充

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 委托补充
{
    // 创建一个数据类型
    delegate void Del1();
    delegate void Del2(int n);
    delegate void Del3(string n);
    delegate void Del4(int a, string b, char c, bool d);
    delegate int Del5();
    delegate string Del6(int n);
    delegate int Del7(int a, string b, bool c);
    class Program
    {
        static void Main(string[] args)
        {
            #region 没有返回值的委托 Action
            // Aciton 针对于没有返回值的委托
            // 没有参数的 那就不用泛型的 直接用Aciton
            // 有参数的 那就根据参数的个数和类型来使用泛型的Aciton<T1 a, T2 b, T3 c ....>
            // 使用
            Del1 del1 = delegate () { Console.WriteLine("这是一个没有参数，没有返回值的委托"); };
            Action del1 = delegate () { Console.WriteLine("这是一个没有参数，没有返回值的委托"); };
            del1();
            //Del2 del2 = n => Console.WriteLine("这是一个没有返回值，有一个参数的委托");
            Action<int> del2 = n => Console.WriteLine("这是一个没有返回值，有一个参数的委托" + n);
            del2(100);
            Action<string> del3 = n => Console.WriteLine("这是一个没有返回值，有一个字符串的参数的委托" + n);
            del3("abc");
            Action<int, string, char, bool> del4 = (int a, string b, char c, bool d) => { };
            #endregion
            #region 有返回值的委托  Func<T1, T2, T3....>  最后一个占位符 永远对应返回值类型  （占位符最少有1个，最多可以有20多个，来表示返回值类型的）
            Func<int> del5 = () => 0;
            Func<int, string> del6 = abc => abc.ToString();
            Func<int, string, bool, int> del7 = (a, b, c) => a;
            #endregion
            #region Predicate有一个参数，参数的类型由泛型占位符指定 返回值 bool
            Predicate<string> del9 = a => true;
            #endregion
            #region Comparison<int> 有两个参数都是根据泛型占位符指定的类型 返回值int
            Comparison<string> del8 = (a, b) => a.Length - b.Length;
            #endregion
        }
    }
}

泛型列表

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 泛型列表
{
    class Program
    {
        static void Main(string[] args)
        {
            // List 动态数组
            List<int> array = new List<int>();
            List<int> array2 = new List<int>() { 303, 27, 309, 40 };     // 使用初始化器添加数据
            // 增
            array.Add(1000);
            array.AddRange(new int[] { 1, 2, 3, 42 });//AddRange批量增加，数组和列表
            array.AddRange(array2);
            // 删
            //array.Remove(1000);   // 删到找到的第一个 没找到也不发生什么
            //array.RemoveAt(0);
            //array.RemoveRange(0, 3);  // 删除一定范围的元素  从哪个下标开始， 总共删除几个元素
            //array.RemoveAll(n => n % 2 == 0);   // 把所有偶数全部删除
            // 改
            //array[0] = 888;
            // 查
            int index = array.IndexOf(301);       // 找不到会返回 -1
            Console.WriteLine("找到的下标为：" + index);
            index = array.LastIndexOf(301);
            Console.WriteLine("找到的下标为：" + index);
            int result = array.Find(n => n % 40 == 0);   // 找到匹配条件的第一个元素，Find查找返回的是元素
            Console.WriteLine(result);
            List<int> resultArray = array.FindAll(n => n % 3 == 0);//FindAll查找返回的是新的列表
            foreach (var item in resultArray)
            {
                Console.Write(item + "\t");
            }
            // 遍历
            //for (int i = 0; i < array.Count; i++)
            //{
            //    Console.Write(array[i] + "\t");
            //}
            Console.WriteLine();
        }
    }
}