学习笔记 --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.排序

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