学习笔记 --C#基础其他知识点（数据结构）

C#中的数据结构《二》–视频学习笔记

在数据结构的分类：
1.集合 2.线性 3.树形 4.图状结构

数据结构是数据在程序中的存储结构，和基本的数据操作
算法：解决问题的解决思路，基于数据结构

本课程包括：线性表，栈和队列，串和数组，简单的排序方法，快速排序

1.线性表：

一对一线性关系，位置有先后关系，一个接着一个排列的数据结构
（C#）CLR中的线性表：
1.提供了一个非泛型接口IList接口，接口中的项是object，实现了IList的类有：ArrayList，ListDictionary，StringCollection，StringDictionary。
2.提供了泛型的IList接口，实现了List接口的类有List【重要】

使用：

//1.使用list线性表
List<string> strlist = new List<string>();
//存入数据
strlist.Add("1");   //0
strlist.Add("2");   //1
strlist.Add("3");   //2
strlist.Add("4");   //3
//读出数据
Console.WriteLine(strlist[3]);  //通过索引器访问元素
//移除字符串
strlist.Remove("4");    //根据内容移除
strlist.Remove(strlist[3]);     //根据索引移除
//大小
Console.WriteLine(strlist.Count);
//清空数据
strlist.Clear();

⭐如果自己去实现一个线性表，如何去实现？
线性表的实现方式有下面几种：顺序表，单链表，双向链表，循环链表。
⭕顺序表：是最简单的存储结构，把表中的元素一个接一个地放进内存，特点：表中相邻的数据元素在内存中的存储位置也相邻。
写一个新的接口：IListDS（接口一般以I开头）【同时也使用泛型编程和接口】

namespace List_T_Study
{
    interface IListDS<T>    //泛型接口
    {
        int GetLength();
        void Clear();
        bool IsEmpty();
        void Add(T item);
        void Insert(int index, T item);
        T Delate(int index);
        T this[int index] {  get;  }    //索引
        T GetEle(int index);    //根据索引得到值
        int Locate(T value);    //根据值得到索引
    }
}

以顺序表为例，实现接口，继承IListDS接口之后，实现全部的接口函数
由于篇幅原因，只显示

namespace List_T_Study
{
    //顺序表的实现方式
    class SeqList<T> : IListDS<T>
    {
        private T[] data;   //用来存储数据
        private int count = 0;  //表示存了多少个数据
        public SeqList(int size)
        {
            //传入固定大小【最大容量】，不提供自动扩容的功能（系统中的list有自动扩容的功能）
            data = new T[size];
        }
        public SeqList():this (10) //默认构造函数 容量为10
        {
        }
        public T this[int index] => throw new NotImplementedException();

        //添加
        public void Add(T item)
        {
            if (count == data.Length)   //说明当前顺序表已经存满了，不允许再存入
            {
                Console.WriteLine("当前顺序表已经存满了，不允许再存入");
            }
            else
            {
                data[count] = item;
                count++;
            }
        }

        public T GetEle(int index)
        {
            if(index>=0 && index<=count-1)  //当索引存在
                return data[index];
            else
            {
                Console.WriteLine("索引不存在");
                return default(T);
            }
        }

        //取得数据的个数
        public int GetLength()
        {
            return count;
        }
    }
}

⭕单链表：
顺序表在插入删除时需要移动元素来实现，影响了运行效率，链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻，但也同时失去了顺序表可随机存储的优点。
先定义一个节点的类：Node

然后再新建一个LinkList的类，类似顺序表继承IListDS接口，并实现接口的函数。

⭕双向链表：
prev指针，data存储数据，next指针

⭕循环链表：
循环链表：最后一个元素指向了第一个元素

2.栈和队列：

也是线性结构
⭕栈：先进后出
C#基类库中的栈：泛型的Stack类
重要方法：Push入栈，pop出栈，peek获取栈顶数据，clear清空，count获取栈中的数据的个数

//3.使用BCL中Stack<T>  栈
Stack<char> stack = new Stack<char>();

stack.Push('a');
stack.Push('b');
stack.Push('c');
Console.WriteLine(stack.Count);

⭐如果自己去实现一个栈，如何去实现？
写一个新的接口：IStackDS（接口一般以I开头）【同时也使用泛型编程和接口】

namespace List_T_Study
{
    //栈接口
    interface IStackDS<T>
    {
        int Count { get; }
        int GetLength();
        bool IsEmpty();
        void Clear();
        void Push(T item);
        T Pop();
        T Peek();
    }
}

分为顺序栈和链栈，顺序栈定义数组存放，链栈以链表的形式，新建一个SeqStack类，继承接口IStackDS并实现接口函数。
列举一部分函数：

namespace List_T_Study
{
    class SeqStack<T> : IStackDS<T>
    {
        private T[] data;//数据
        private int top;    //栈顶的标志

        public SeqStack(int size)
        {
            data = new T[size];
            top = -1;
        }

        public SeqStack():this(10) 
        {
            //无参构造 则默认传长度10
        }
        public int Count {
            get
            {
                return top+1;
            }
        }

        public T Pop()
        {
            T temp = data[top];
            top--;
            return temp;
        }

        public void Push(T item)
        {
            data[top+1] = item;
            top++;
        }
    }
}

链栈，需要知道
⭕队列：先进先出
插入限定在表的尾部，
C#（CLR中的队列）：泛型Queue类，
常用方法：Enqueue入队（放在队尾），Dequeue出队（移除队首元素），Peek，clear，count

//4.队列
Queue<int> queue = new Queue<int>();  
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Dequeue();
Console.WriteLine(queue.Count);

栈和队列应用举例：回文判断

3.串和数组

实现字符串类的存储，构造和比较

4.排序

介绍，直接插入排序，简单选择排序，快速排序思想，