C#数据结构与算法总结
线性表
线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract)，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系，即：
- 除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素；
- 除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。也就是说，数据元素是一个接一个的排列。因此，可以把线性表想象为一种数据元素序列的数据结构。
线性表就是位置有先后关系，一个接着一个排列的数据结构。
CLR中的线性表
c# 1.1 提供了一个非泛型接口IList接口，接口中的项是object,实现了IList解扣子的类有ArrayList,ListDictionary,StringCollection,StringDictionary.
c# 2.0 提供了泛型的IList接口，实现了List接口的类有List
线性表的接口定义
interface IListDS<T>
{
int GetLength(); //求长度
void Clear(); //清空操作
bool IsEmpty();//判断线性表是否为空
void Add(T item);//附加操作
void Insert(T item, int index); //插入操作
T Delete(int index); //删除操作
T this[int index] { get; }//定义一个索引器 获取元素
T GetEle(int index);//取表元
int Locate(T value);//按值查找
}
线性表的实现方式
线性表的实现方式有下面几种
- 顺序表
- 单链表
- 双向链表
- 循环链表
顺序表
在计算机内，保存线性表最简单、最自然的方式，就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储(Sequence Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表(Sequence List)，如图所示。顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻。
顺序表的存储
假设顺序表中的每个数据元素占w个存储单元，设第i个数据元素的存储地址为Loc(ai)，则有：
Loc(ai)= Loc(a1)+(i-1)*w 1≤i≤n式中的Loc(a1)表示第一个数据元素a1的存储地址，也是顺序表的起始存储地址，称为顺序表的基地址(Base Address)。也就是说，只要知道顺序表的基地址和每个数据元素所占的存储单元的个数就可以求出顺序表中任何一个数据元素的存储地址。并且，由于计算顺序表中每个数据元素存储地址的时间相同，所以顺序表具有任意存取的特点。(可以在任意位置存取东西)
C#语言中的数组在内存中占用的存储空间就是一组连续的存储区域，因此，数组具有任意存取的特点。所以，数组天生具有表示顺序表的数据存储区域的特性。
顺序表的实现
class SeqList<T> : IListDS<T>
{
private T[] data;//用来存储数据
private int count = 0;
public SeqList(int size)
{
data = new T[size];
}
public SeqList() : this(10)
{
}
public T this[int index]
{
get
{
return GetEle(index);
}
}
public void Add(T item)
{
if (count == data.Length)//当前数组已经存满
{
Console.WriteLine("当前顺序表已存满，不允许再存入");
}
else
{
data[count] = item;
count++;
}
}
public void Clear()
{
count = 0;
}
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;
}
public void Insert(T item, int index)
{
for (int i = count - 1; i >= index; i--)
{
data[i + 1] = data[i];
}
data[index] = item;
count++;
}
public T Delete(int index)
{
T temp = data[index];
for (int i = index + 1; i < count; i++)
{
data[i - 1] = data[i];
}
count--;
return temp;
}
public bool IsEmpty()
{
return count == 0;
}
public int Locate(T value)
{
for (int i = 0; i < count; i++)
{
if (data[i].Equals(value))
{
return i;
}
}
return -1;
}
}
单链表
顺序表是用地址连续的存储单元顺序存储线性表中的各个数据元素，逻辑上相邻的数据元素在物理位置上也相邻。因此，在顺序表中查找任何一个位置上的数据元素非常方便，这是顺序存储的优点。但是，在对顺序表进行插入和删除时，需要通过移动数据元素来实现，影响了运行效率。线性表的另外一种存储结构——链式存储(Linked Storage)，这样的线性表叫链表(Linked List)。链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻，因此，在对链表进行插入和删除时不需要移动数据元素，但同时也失去了顺序表可随机存储的优点。
单链表的存储
链表是用一组任意的存储单元来存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。那么，怎么表示两个数据元素逻辑上的相邻关系呢？即如何表示数据元素之间的线性关系呢？为此，在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像(Image)，称为结点(Node)。把存储据元素本身信息的域叫结点的数据域(Data Domain)，把存储与它相邻的数据元素的存储地址信息的域叫结点的引用域(Reference Domain)。因此，线性表通过每个结点的引用域形成了一根“链条”，这就是“链表”名称的由来。
如果结点的引用域只存储该结点直接后继结点的存储地址，则该链表叫单链表(Singly Linked List)。把该引用域叫 next。单链表结点的结构如图所示，图中 data 表示结点的数据域。
链式存储结构
下图是线性表(a1,a2,a3,a4,a5,a6)对应的链式存储结构示意图。
另外一种表示形式
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D01GDnI3-1581864714521)(https://s1.ax1x.com/2018/12/26/F2lFwn.jpg)]
单链表节点定义
class Node<T>
{
private T data;
private Node<T> next;
public Node()
{
data = default(T);
next = null;
}
public Node(T value)
{
this.data = value;
this.next = null;
}
public Node(T value, Node<T> next)
{
this.data = value;
this.next = next;
}
public Node(Node<T> next)
{
this.next = next;
}
public T Data
{
get { return data; }
set { data = value; }
}
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
单链表实现
class LinkList<T> : IListDS<T>
{
private Node<T> head;
public LinkList()
{
head = null;
}
public T this[int index]
{
get
{
return GetEle(index);
}
}
public void Add(T item)
{
Node<T> newNode = new Node<T>(item);
if (head == null)
{
head = newNode;
}
else
{
Node<T> temp = head;
while (true)
{
if (temp.Next != null)
{
temp = temp.Next;
}
else
{
break;
}
}
temp.Next = newNode;
}
}
public void Clear()
{
head = null;
}
public T Delete(int index)
{
T data = default(T);
if (index == 0)
{
data = head.Data;
head = head.Next;
}
else
{
Node<T> temp = head;
for (int i = 0; i < index - 1; i++)
{
temp = temp.Next;
}
Node<T> preNode = temp;
Node<T> currentNode = temp.Next;
data = currentNode.Data;
Node<T> nextNode = temp.Next.Next;
preNode.Next = nextNode;
}
return data;
}
public T GetEle(int index)
{
Node<T> temp = head;
T data = temp.Data;
if (index == 0)
{
return data = temp.Data;
}
else
{
for (int i = 0; i < index; i++)
{
temp = temp.Next;
}
data = temp.Data;
}
return data;
}
public int GetLength()
{
if (head == null) return 0;
Node<T> temp = head;
int count = 1;
while (true)
{
if (temp.Next != null)
{
count++;
temp = temp.Next;
}
else
{
break;
}
}
return count;
}
public void Insert(T item, int index)
{
Node<T> newNode = new Node<T>(item);
if (index == 0)
{
newNode.Next = head;
head = newNode;
}
else
{
Node<T> temp = head;
for (int i = 0; i < index - 1; i++)
{
temp = temp.Next;
}
Node<T> preNode = temp;
Node<T> currentNode = temp.Next;
preNode.Next = newNode;
newNode.Next = currentNode;
}
}
public bool IsEmpty()
{
return head == null;
}
public int Locate(T value)
{
Node<T> temp = head;
if (temp == null)
{
return -1;
}
else
{
int index = 0;
while (true)
{
if (temp.Data.Equals(value))
{
return index;
}
else
{
if (temp.Next != null)
{
index++;
temp = temp.Next;
}
else
{
break;
}
}
}
return -1;
}
}
}
双向链表
前面介绍的单链表允许从一个结点直接访问它的后继结点，所以, 找直接后继结点的时间复杂度是 O(1)。但是,要找某个结点的直接前驱结点，只能从表的头引用开始遍历各结点。如果某个结点的 Next 等于该结点，那么，这个结点就是该结点的直接前驱结点。也就是说，找直接前驱结点的时间复杂度是 O(n)， n是单链表的长度。当然，我们也可以在结点的引用域中保存直接前驱结点的地址而不是直接后继结点的地址。这样，找直接前驱结点的时间复杂度只有 O(1)，但找直接后继结点的时间复杂度是 O(n)。如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1)，那么，需要在结点中设两个引用域，一个保存直接前驱结点的地址，叫 prev，一个直接后继结点的地址，叫 next，这样的链表就是双向链表(Doubly Linked List)。双向链表的结点结构示意图如图所示。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UNn84VOH-1581864714522)(https://s1.ax1x.com/2018/12/26/Fg5Mhn.png)]
双向链表节点实现
public class DbNode<T>
{
private T data; //数据域
private DbNode<T> prev; //前驱引用域
private DbNode<T> next; //后继引用域
//构造器
public DbNode(T val, DbNode<T> p)
{
data = val;
next = p;
}
//构造器
public DbNode(DbNode<T> p)
{
next = p;
}
//构造器
public DbNode(T val)
{
data = val;
next = null;
}
//构造器
public DbNode()
{
data = default(T);
next = null;
}
//数据域属性
public T Data
{
get { return data; }
set { data = value; }
}
//前驱引用域属性
public DbNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
//后继引用域属性
public DbNode<T> Next
{
get { return next; }
set { next = value; }
}
}
双向链表插入示意图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yCTPlLtM-1581864714522)(https://s1.ax1x.com/2018/12/26/Fg5B1x.png)]
循环链表
有些应用不需要链表中有明显的头尾结点。在这种情况下，可能需要方便地从最后一个结点访问到第一个结点。此时，最后一个结点的引用域不是空引用，而是保存的第一个结点的地址（如果该链表带结点，则保存的是头结点的地址），也就是头引用的值。带头结点的循环链表(Circular Linked List)如图所示。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Oihv4m5h-1581864714523)(https://s1.ax1x.com/2018/12/26/Fg52AH.png)]
栈和队列
栈和队列是非常重要的两种数据结构，在软件设计中应用很多。栈和队列也是线性结构，线性表、栈和队列这三种数据结构的数据元素以及数据元素间的逻辑关系完全相同，差别是线性表的操作不受限制，而栈和队列的操作受到限制。
栈的操作只能在表的一端进行，队列的插入操作在表的一端进行而其它操作在表的另一端进行，所以，把栈和队列称为操作受限的线性表。
栈
栈(Stack)是操作限定在表的尾端进行的线性表。表尾由于要进行插入、删除等操作，所以，它具有特殊的含义，把表尾称为栈顶（ Top），另一端是固定的，叫栈底（ Bottom）。当栈中没有数据元素时叫空栈(Empty Stack)。
栈通常记为： S= (a1,a2,…,an)，S是英文单词stack的第 1 个字母。a1为栈底元素，an为栈顶元素。这n个数据元素按照a1,a2,…,an的顺序依次入栈，而出栈的次序相反，an第一个出栈，a1最后一个出栈。所以，栈的操作是按照后进先出(Last In First Out，简称LIFO)或先进后出(First In Last Out，简称FILO)的原则进行的，因此，栈又称为LIFO表或FILO表。栈的操作示意图如图所示。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y4ib2xIf-1581864714523)(https://s1.ax1x.com/2018/12/26/FggUzD.png)]
BCL中的栈
C#2.0 一下版本只提供了非泛型的Stack类(存储object类型)
C#2.0 提供了泛型的Stack类
重要的方法如下：
- Push()入栈（添加数据）
- Pop()出栈（删除数据，返回被删除的数据）
- Peek()取得栈顶的数据，不删除
- Clear()清空所有数据
- Count取得栈中数据的个数
栈的接口定义
public interface IStackDS<T>
{
int Count { get; }
int GetLength(); //求栈的长度
bool IsEmpty(); //判断栈是否为空
void Clear(); //清空操作
void Push(T item); //入栈操作
T Pop(); //出栈操作
T Peek(); //取栈顶元素
}
栈的存储和代码实现
顺序栈
用一片连续的存储空间来存储栈中的数据元素(使用数组)，这样的栈称为顺序栈(Sequence Stack)。类似于顺序表，用一维数组来存放顺序栈中的数据元素。栈顶指示器 top 设在数组下标为 0 的端， top 随着插入和删除而变化，当栈为空时，top=-1。下图是顺序栈的栈顶指示器 top 与栈中数据元素的关系图。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ngxwFMDC-1581864714524)(https://s1.ax1x.com/2018/12/26/FgRZgU.png)]
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)
{
}
public int Count
{
get
{
return top + 1;
}
}
public void Clear()
{
top = -1;
}
public int GetLength()
{
return Count;
}
public bool IsEmpty()
{
return Count == 0;
}
public T Peek()
{
return data[top];
}
public T Pop()
{
T temp = data[top];
top--;
return temp;
}
public void Push(T item)
{
data[top + 1] = item;
top++;
}
}
链栈
栈的另外一种存储方式是链式存储，这样的栈称为链栈(Linked Stack)。链栈通常用单链表来表示，它的实现是单链表的简化。所以，链栈结点的结构与单链表结点的结构一样。由于链栈的操作只是在一端进行，为了操作方便，把栈顶设在链表的头部，并且不需要头结点。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5nlAdDJY-1581864714524)(https://s1.ax1x.com/2018/12/26/FgRvI1.png)]
链栈结点实现
链栈结点代码实现：
class Node<T>
{
private T data;
private Node<T> next;
public Node()
{
this.data = default(T);
this.next = null;
}
public Node(T data)
{
this.data = data;
this.next = null;
}
public Node(T value, Node<T> next)
{
this.data = value;
this.next = next;
}
public Node(Node<T> next)
{
this.data = default(T);
this.next = next;
}
public T Data
{
set { data = value; }
get { return data; }
}
public Node<T> Next
{
set { next = value; }
get { return next; }
}
}
链栈代码实现
把链栈看作一个泛型类，类名为 LinkStack。 LinkStack类中有一个字段 top 表示栈顶指示器。由于栈只能访问栈顶的数据元素，而链栈的栈顶指示器又不能指示栈的数据元素的个数。所以，求链栈的长度时，必须把栈中的数据元素一个个出栈，每出栈一个数据元素，计数器就增加 1，但这样会破坏栈的结构。为保留栈中的数据元素，需把出栈的数据元素先压入另外一个栈，计算完长度后，再把数据元素压入原来的栈。但这种算法的空间复杂度和时间复杂度都很高，所以，以上两种算法都不是理想的解决方法。理想的解决方法是 LinkStack类增设一个字段 num 表示链栈中结点的个数。
class LinkStack<T> : IStackDS<T>
{
private Node<T> top;
private int count = 0;
public int Count
{
get
{
return count;
}
}
public void Clear()
{
count = 0;
top = null;
}
public int GetLength()
{
return count;
}
public bool IsEmpty()
{
return count == 0;
}
public T Peek()
{
return top.Data;
}
public T Pop()
{
T data = top.Data;
top = top.Next;
count--;
return data;
}
public void Push(T item)
{
Node<T> temp = new Node<T>(item);
temp.Next = top;
top = temp;
count++;
}
}
队列
队列(Queue)是插入操作限定在表的尾部而其它操作限定在表的头部进行的线性表。把进行插入操作的表尾称为队尾(Rear)，把进行其它操作的头部称为队头(Front)。当队列中没有数据元素时称为空队列(Empty Queue)。
队列通常记为： Q= (a1,a2,…,an)，Q是英文单词queue的第 1 个字母。a1为队头元素，an为队尾元素。这n个元素是按照a1,a2,…,an的次序依次入队的，出对的次序与入队相同，a1第一个出队，an最后一个出队。所以，对列的操作是按照先进先出(First In First Out)或后进后出( Last In Last Out)的原则进行的，因此，队列又称为FIFO表或LILO表。队列Q的操作示意图如图所示。
在实际生活中有许多类似于队列的例子。比如，排队取钱，先来的先取，后来的排在队尾。
队列的操作是线性表操作的一个子集。队列的操作主要包括在队尾插入元素、在队头删除元素、取队头元素和判断队列是否为空等。与栈一样，队列的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在物理存储结构层次上的。因此，把队列的操作作为逻辑结构的一部分，每个操作的具体实现只有在确定了队列的存储结构之后才能完成。队列的基本运算不是它的全部运算，而是一些常用的基本运算。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FX5KlOEk-1581864714524)(https://s1.ax1x.com/2018/12/26/FgfCYq.png)]
BCL 中的队列
C#2.0 以下版本提供了非泛型的Ｑueue类
C#2.0 提供了泛型Queue类
方法：
- Enqueue()入队(放在队尾)
- Dequeue()出队(移除队首元素，并返回被移除的元素)
- Peek()取得队首的元素，不移除
- Clear()清空元素
属性 - Count获取队列中元素的个数
队列接口定义
interface IQueue<T>
{
int Count { get; }
int GetLeng();
bool IsEmpty();
void Clear();
void Enqueue(T item);
T Dequeue();
T Peek();
}
队列的存储和代码实现
顺序队列
用一片连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列(Sequence Queue)。类似于顺序栈，用一维数组来存放顺序队列中的数据元素。队头位置设在数组下标为 0 的端，用 front 表示；队尾位置设在数组的另一端，用 rear 表示。 front 和 rear 随着插入和删除而变化。当队列为空时， front=rear=-1。
图是顺序队列的两个指示器与队列中数据元素的关系图。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gGCIaKwp-1581864714525)(https://s1.ax1x.com/2018/12/26/FgfEXF.png)]
class SeqQueue<T> : IQueue<T>
{
private T[] data;
private int count;//数量
private int rear;//队尾
private int front;//队首
public SeqQueue(int size)
{
data = new T[size];
count = 0;
rear = front = -1;
}
public SeqQueue() : this(10)
{
}
public int Count
{
get
{
return count;
}
}
public void Clear()
{
count = 0;
rear = front = -1;
}
public T Dequeue()
{
if (count > 0)
{
T temp = data[front + 1];
front++;
count--;
return temp;
}
else
{
Console.WriteLine("队列为空，无法取得队首数据。");
return default(T);
}
}
public void Enqueue(T item)
{
if (count == data.Length)
{
Console.WriteLine("队列已满，不可以在添加数据");
}
else
{
if (rear == data.Length - 1)
{
data[0] = item;
rear = 0;
count++;
}
else
{
data[rear + 1] = item;
rear++;
count++;
}
}
}
public int GetLeng()
{
return count;
}
public bool IsEmpty()
{
return count == 0;
}
public T Peek()
{
T temp = data[front + 1];
return temp;
}
}
循环顺序队列
如果再有一个数据元素入队就会出现溢出。但事实上队列中并未满，还有空闲空间，把这种现象称为“假溢出”。这是由于队列“队尾入队头出”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列(Circular sequence Queue)。循环队列如图所示。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GKnRoYFl-1581864714525)(https://s1.ax1x.com/2018/12/26/Fgfc7j.png)]
把循环顺序队列看作是一个泛型类，类名叫 CSeqStack，“ C”是英文单词 circular 的第 1 个字母。 CSeqStack类实现了接口 IQueue。用数组来存储循环顺序队列中的元素，在 CSeqStack类中用字段 data 来表示。用字段maxsize 表示循环顺序队列的容量， maxsize 的值可以根据实际需要修改，这通过CSeqStack类的构造器中的参数 size 来实现，循环顺序队列中的元素由 data[0]开始依次顺序存放。字段 front 表示队头， front 的范围是 0 到 maxsize-1。字段 rear表示队尾，rear 的范围也是 0 到 maxsize-1。如果循环顺序队列为空，front=rear=-1。当执行入队列操作时需要判断循环顺序队列是否已满，如果循环顺序队列已满，(rear + 1) % maxsize==front ， 循 环 顺 序 队 列 已 满 不 能 插 入 元 素 。 所 以 ，CSeqStack类除了要实现接口 IQueue中的方法外，还需要实现判断循环顺序队列是否已满的成员方法。
链队列
队列的另外一种存储方式是链式存储，这样的队列称为链队列(Linked Queue)。同链栈一样，链队列通常用单链表来表示，它的实现是单链表的简化。所以，链队列的结点的结构与单链表一样，如图所示。由于链队列的操作只是在一端进行，为了操作方便，把队头设在链表的头部，并且不需要头结点。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x6cYEpNA-1581864714526)(https://s1.ax1x.com/2018/12/26/FgfqE9.png)]
链队列结点类
class Node<T>
{
private T data;
private Node<T> next;
public Node(T data)
{
this.data = data;
}
public T Data
{
set { data = value; }
get { return data; }
}
public Node<T> Next
{
set { next = value; }
get { return next; }
}
}
链队列代码实现
把链队列看作一个泛型类，类名为 LinkQueue。 LinkQueue类中有两个字段 front 和 rear，表示队头指示器和队尾指示器。由于队列只能访问队头的数据元素，而链队列的队头指示器和队尾指示器又不能指示队列的元素个数，所以，与链栈一样，在 LinkQueue类增设一个字段 num 表示链队列中结点的个数。
class LinkQueue<T> : IQueue<T>
{
private Node<T> front;
private Node<T> rear;
private int count;
public LinkQueue()
{
front = rear = null;
count = 0;
}
public int Count
{
get { return count; }
}
public void Clear()
{
count = 0;
rear = front = null;
}
public T Dequeue()
{
if (count == 0)
{
Console.WriteLine("队列为空，无法出队");
return default(T);
}
else if (count == 1)
{
T temp = front.Data;
front = rear = null;
count = 0;
return temp;
}
else
{
T temp = front.Data;
front = front.Next;
count--;
return temp;
}
}
public void Enqueue(T item)
{
Node<T> temp = new Node<T>(item);
if (count == 0)
{
front = rear = temp;
count = 1;
}
else
{
rear.Next = temp;
rear = temp;
count++;
}
}
public int GetLeng()
{
return count;
}
public bool IsEmpty()
{
return count == 0;
}
public T Peek()
{
return front.Data;
}
}
栈和队列的应用举例
编程判断一个字符串是否是回文。回文是指一个字符序列以中间字符为基准两边字符完全相同，如字符序列“ ACBDEDBCA”是回文。
算法思想：判断一个字符序列是否是回文，就是把第一个字符与最后一个字符相比较，第二个字符与倒数第二个字符比较，依次类推，第 i 个字符与第 n-i个字符比较。如果每次比较都相等，则为回文，如果某次比较不相等，就不是回文。因此，可以把字符序列分别入队列和栈，然后逐个出队列和出栈并比较出队列的字符和出栈的字符是否相等，若全部相等则该字符序列就是回文，否则就不是回文。
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
string str = Console.ReadLine();
Stack<char> stack = new Stack<char>();
Queue<char> queue = new Queue<char>();
for (int i = 0; i < str.Length; i++)
{
stack.Push(str[i]);
queue.Enqueue(str[i]);
}
bool isHui = true;
while (stack.Count > 0)
{
if (stack.Pop() != queue.Dequeue())
{
isHui = false;
break;
}
}
Console.WriteLine("是否是回文字符串：" + isHui);
Console.ReadKey();
}
}
串和数组
在应用程序中使用最频繁的类型是字符串。字符串简称串，是一种特殊的线性表，其特殊性在于串中的数据元素是一个个的字符。字符串在计算机的许多方面应用很广。如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据。在事务处理程序中，顾客的信息如姓名、地址等及货物的名称、产地和规格等，都被作为字符串来处理。另外，字符串还具有自身的一些特性。因此，把字符串作为一种数据结构来研究。
串
串的基本概念
串(String)由 n(n≥0)字符组成的有限序列。一般记为：
S=”c1c2…cn” (n≥0)
其中， S是串名，双引号作为串的定界符，用双引号引起来的字符序列是串值。 ci（ 1≤i≤n）可以是字母、数字或其它字符， n为串的长度，当n=0 时，称为空串(Empty String)。
串中任意个连续的字符组成的子序列称为该串的子串(Substring)。包含子串的串相应地称为主串。子串的第一个字符在主串中的位置叫子串的位置。如串s1”abcdefg”，它的长度是 7，串s2”cdef”的长度是 4， s2是s1的子串， s2的位置是 3。
如果两个串的长度相等并且对应位置的字符都相等，则称这两个串相等。而在 C#中，比较两个串是否相等还要看串的语言文化等信息。
串的存储和代码实现
由于串中的字符都是连续存储的，而在 C#中串具有恒定不变的特性，即字符串一经创建，就不能将其变长、变短或者改变其中任何的字符。所以，这里不讨论串的链式存储，也不用接口来表示串的操作。同样，把串看作是一个类，类名为 StringDS。取名为 StringDS 是为了和 C#自身的字符串类 String 相区别。类StringDS 只有一个字段，即存放串中字符序列的数组 data。由于串的运算有很多，类 StringDS 中只包含部分基本的运算。串类 StringDS中的方法和属性:
class StringDS
{
private char[] data;//用来存放字符串
/// <summary>
/// 构造器
/// </summary>
/// <param name="array">字符数组</param>
public StringDS(char[] array)
{
data = new char[array.Length];
for (int i = 0; i < array.Length; i++)
{
data[i] = array[i];
}
}
/// <summary>
/// 构造器
/// </summary>
/// <param name="str">字符串</param>
public StringDS(string str)
{
data = new char[str.Length];
for (int i = 0; i < str.Length; i++)
{
data[i] = str[i];
}
}
/// <summary>
/// 索引器
/// </summary>
/// <param name="index">索引下标</param>
/// <returns></returns>
public char this[int index]
{
get
{
return data[index];
}
}
/// <summary>
/// 获得串的长度
/// </summary>
/// <returns>长度</returns>
public int GetLength()
{
return data.Length;
}
/// <summary>
/// 如果两个字符串一样长，返回0
/// 如果当前字符串小于s，那么返回-1
/// 如果当前字符串大于s，那么返回1
/// </summary>
/// <param name="">要比较的串</param>
/// <returns></returns>
public int Compare(StringDS s)
{
int len = this.GetLength() > s.GetLength() ? this.GetLength() : s.GetLength(); //取得较短字符串；
int index = -1;//用来记录两个字符串不相同字符的位置；
for (int i = 0; i < len; i++)
{
if (this[i] != s[i])
{
index = i;
break;
}
}
if (index != -1)
{
if (this[index] > s[index])
{
return 1;
}
else
{
return -1;
}
}
else
{
if (this.GetLength() == s.GetLength())
{
return 0;
}
else
{
if (this.GetLength() > s.GetLength())
{
return 1;
}
else
{
return -1;
}
}
}
}
/// <summary>
/// 剪切字符串
/// </summary>
/// <param name="index">剪切点的下标</param>
/// <param name="length">要剪切的长度</param>
/// <returns></returns>
public StringDS SubString(int index, int length)
{
char[] newData = new char[length];
for (int i = index; i < index + length; i++)
{
newData[i - index] = data[i];
}
return new StringDS(newData);
}
/// <summary>
/// 拼接字符串
/// </summary>
/// <param name="s1">要拼接的串1</param>
/// <param name="s2">要拼接的串2</param>
/// <returns></returns>
public static StringDS Concat(StringDS s1, StringDS s2)
{
char[] newData = new char[s1.GetLength() + s2.GetLength()];
for (int i = 0; i < s1.GetLength(); i++)
{
newData[i] = s1[i];
}
for (int i = s1.GetLength(); i < s1.GetLength() + s2.GetLength(); i++)
{
newData[i] = s2[i - s1.GetLength()];
}
return new StringDS(newData);
}
/// <summary>
/// 查找当前串中与串s相同的第一个下标
/// </summary>
/// <param name="s">要在当前串中查找的串</param>
/// <returns></returns>
public int IndexOf(StringDS s)
{
for (int i = 0; i <= this.GetLength() - s.GetLength(); i++)
{
bool isEqual = true;
for (int j = i; j < i + s.GetLength(); j++)
{
if (this[j] != s[j - i])
{
isEqual = false;
}
}
if (isEqual)
{
return i;
}
else
{
continue;
}
}
return -1;
}
/// <summary>
/// 重写ToString
/// </summary>
/// <returns>返回一个字符串</returns>
public override string ToString()
{
return new string(data);
}
}
C#中的串
在 C#中，一个 String 表示一个恒定不变的字符序列集合。 String 类型是封闭类型，所以，它不能被其它类继承，而它直接继承自 object。因此， String 是引用类型，不是值类型，在托管堆上而不是在线程的堆栈上分配空间。 String 类型还 继 承 了 IComparable 、 ICloneable 、 IConvertible 、 IComparable<string> 、IEnumerable<char>、 IEnumerable 和 IEquatable<string>等接口。 String 的恒定性指的是一个串一旦被创建，就不能将其变长、变短或者改变其中任何的字符。所以，当我们对一个串进行操作时，不能改变字符串，如在本书定义的 StringDS 类中，串连接、串插入和串删除等操作的结果都是生成了新串而没有改变原串。 C#也提供了 StringBuilder 类型来支持高效地动态创建字符串。
在 C#中，创建串不能用 new 操作符，而是使用一种称为字符串驻留的机制。
这是因为 C#语言将 String 看作是基元类型。基元类型是被编译器直接支持的类型，可以在源代码中用文本常量(Literal)来直接表达字符串。当 C#编译器对源代码进行编译时，将文本常量字符串存放在托管模块的元数据中。而当 CLR 初始化时， CLR 创建一个空的散列表，其中的键是字符串，值为指向托管堆中字符串对象的引用。散列表就是哈希表。当 JIT编译器编译方法时，它会在散列表中查找每一个文本常量字符串。如果找不到，就会在托管堆中构造一个新的 String 对象（指向字符串），然后将该字符串和指向该字符串对象的引用添加到散列表中；如果找到了，不会执行任何操作。
数组
c#中的数组
数组是一种常用的数据结构，可以看作是线性表的推广。数组作为一种数据结构，其特点是结构中的数据元素可以是具有某种结构的数据，甚至可以是数组，但属于同一数据类型。数组在许多高级语言里面都被作为固定类型来使用。
数组是 n(n≥1)个相同数据类型的数据元素的有限序列。一维数组可以看作是一个线性表，二维数组可以看作是“数据元素是一维数组”的一维数组，三维数组可以看作是“数据元素是二维数组”的一维数组，依次类推。
C#支持一维数组、多维数组及交错数组（数组的数组）。所有的数组类型都隐含继承自System.Array。Array 是一个抽象类，本身又继承自 System.Object。所以，数组总是在托管堆上分配空间，是引用类型。任何数组变量包含的是一个指向数组的引用，而非数组本身。当数组中的元素的值类型时，该类型所需的内存空间也作为数组的一部分而分配；当数组的元素是引用类型时，数组包含是只是引用。
Array类中的常用方法
using System;
using System.Collections;
public abstract class Array : ICloneable, IList, ICollection, IEnumerable
{
//判断 Array 是否具有固定大小。
public bool IsFixedSize { get; }
//获取 Array 元素的个数。
public int Length { get; }
//获取 Array 的秩（维数）。
public int Rank { get; }
//实现的 IComparable 接口，在.Array 中搜索特定元素。
public static int BinarySearch(Array array, object value);
//实现的 IComparable<T>泛型接口，在 Array 中搜索特定元素。
public static int BinarySearch<T>(T[] array, T value);
//实现 IComparable 接口，在 Array 的某个范围中搜索值。
public static int BinarySearch(Array array, int index, int length, object value);
//实现的 IComparable<T>泛型接口，在 Array 中搜索值。
public static int BinarySearch<T>(T[] array, int index, int length, T value);
//Array 设置为零、 false 或 null，具体取决于元素类型。
public static void Clear(Array array, int index, int length);
//System.Array 的浅表副本。
public object Clone();
//从第一个元素开始复制 Array 中的一系列元素
//到另一 Array 中（从第一个元素开始）。
public static void Copy(Array sourceArray,
Array destinationArray, int length);
//将一维 Array 的所有元素复制到指定的一维 Array 中。
public void CopyTo(Array array, int index);
//创建使用从零开始的索引、具有指定 Type 和维长的多维 Array。
public static Array CreateInstance(Type elementType, params int[] lengths);
//返回 ArrayIEnumerator。
public IEnumerator GetEnumerator();
//获取 Array 指定维中的元素数。
public int GetLength(int dimension);
//获取一维 Array 中指定位置的值。
public object GetValue(int index);
//返回整个一维 Array 中第一个匹配项的索引。
public static int IndexOf(Array array, object value);
//返回整个.Array 中第一个匹配项的索引。
public static int IndexOf<T>(T[] array, T value);
//返回整个一维 Array 中最后一个匹配项的索引。
public static int LastIndexOf(Array array, object value);
//反转整个一维 Array 中元素的顺序。
public static void Reverse(Array array);
//设置给一维 Array 中指定位置的元素。
public void SetValue(object value, int index);
//对整个一维 Array 中的元素进行排序。
public static void Sort(Array array);
}
简单排序方法
排序
排序（Sort）是计算机程序设计中的一种重要操作，也是日常生活中经常遇到的问题。例如，字典中的单词是以字母的顺序排列，否则，使用起来非常困难。同样，存储在计算机中的数据的次序，对于处理这些数据的算法的速度和简便性而言，也具有非常深远的意义。
基本概念
排序是把一个记录（在排序中把数据元素称为记录）集合或序列重新排列成按记录的某个数据项值递增（或递减）的序列。
下表是一个学生成绩表，其中某个学生记录包括学号、姓名及计算机文化基础、C 语言、数据结构等课程的成绩和总成绩等数据项。在排序时，如果用总成绩来排序，则会得到一个有序序列；如果以数据结构成绩进行排序，则会得到另一个有序序列。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7CevmBS6-1581864714526)(https://s1.ax1x.com/2018/12/26/FgXCbq.png)]
作为排序依据的数据项称为“排序项”，也称为记录的关键码(Keyword)。关键码分为主关键码(Primary Keyword)和次关键码(Secondary Keyword)。一般地，若关键码是主关键码，则对于任意待排序的序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序的结果不一定唯一，这是因为待排序的序列中可能存在具有相同关键码值的记录。此时，这些记录在排序结果中，它们之间的位置关系与排序前不一定保持一致。如果使用某个排序方法对任意的记录序列按关键码进行排序，相同关键码值的记录之间的位置关系与排序前一致，则称此排序方法是稳定的；如果不一致，则称此排序方法是不稳定的。
由于待排序的记录的数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为内部排序（Internal Sorting）和外部排序（External Sorting）两大类。
内部排序指的是在排序的整个过程中，记录全部存放在计算机的内存中，并且在内存中调整记录之间的相对位置，在此期间没有进行内、外存的数据交换。外部排序指的是在排序过程中，记录的主要部分存放在外存中，借助于内存逐步调整记录之间的相对位置。在这个过程中，需要不断地在内、外存之间交换数据。
直接插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ufhWfSCk-1581864714527)(https://s1.ax1x.com/2018/12/26/FgX1IK.png)]
using System;
class Program
{
static void InsertSort(int[] dataArray)
{
for (int i = 1; i < dataArray.Length; i++)
{
int iValue = dataArray[i];
bool isInsert = false;
//拿到i位置的元素 跟前面所有的元素做比较
//如果发现比i大的，就让它向后移动
for (int j = i - 1; j >= 0; j--)
{
if (dataArray[j] > iValue)
{
dataArray[j + 1] = dataArray[j];
}
else
{
//发现一个比i小的值就不移动了
dataArray[j + 1] = iValue;
isInsert = true;
break;
}
}
if (isInsert == false)
{
dataArray[0] = iValue;
}
}
}
static void Main(string[] args)
{
int[] data = new int[] { 42, 20, 17, 27, 13, 8, 17, 48 };
InsertSort(data);
foreach (var temp in data)
{
Console.Write(temp + " ");
}c
Console.ReadKey();
}
}
冒泡排序
冒泡排序(Bubble Sort)的基本思想是：将相邻的记录的关键码进行比较，若前面记录的关键码大于后面记录的关键码，则将它们交换，否则不交换。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z8BCTzaR-1581864714527)(https://s1.ax1x.com/2018/12/26/FgXGGD.png)]
class Program
{
static void Main(string[] args)
{
int temp = 0;
int[] arr = { 23, 44, 66, 76, 98, 11, 3, 9, 7 };
#region 该段与排序无关
Console.WriteLine("排序前的数组：");
foreach (int item in arr)
{
Console.Write(item + "");
}
Console.WriteLine();
#endregion
for (int i = 0; i < arr.Length - 1; i++)
{
#region 将大的数字移到数组的arr.Length-1-i
for (int j = 0; j < arr.Length - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
#endregion
}
Console.WriteLine("排序后的数组：");
foreach (int item in arr)
{
Console.Write(item + "");
}
Console.WriteLine();
Console.ReadKey();
}
}
简单选择排序
简单选择排序(Simple Select Sort)算法的基本思想是：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oDcM6OiN-1581864714527)(https://s1.ax1x.com/2018/12/26/FgX8PO.png)]
using System;
class Program
{
static void SelectSort(int[] dataArray)
{
for (int i = 0; i < dataArray.Length - 1; i++)
{
int min = dataArray[i];
int minIndex = i;//最小值所在索引
for (int j = i + 1; j < dataArray.Length; j++)
{
if (dataArray[j] < min)
{
min = dataArray[j];
minIndex = j;
}
}
if (minIndex != i)
{
int temp = dataArray[i];
dataArray[i] = dataArray[minIndex];
dataArray[minIndex] = temp;
}
}
}
static void Main(string[] args)
{
int[] data = new int[] { 42, 20, 17, 27, 13, 8, 17, 48 };
SelectSort(data);
foreach (var temp in data)
{
Console.Write(temp + " ");
}
Console.ReadKey();
}
}
快速排序
快速排序由于排序效率综合来说你几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
快速排序详细步骤
以一个数组作为示例，取区间第一个数为基准数。
初始时，i = 0; j = 9; X = a[i] = 72
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lqGdbCB6-1581864714528)(https://s1.ax1x.com/2018/12/26/FgjEwt.png)]
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;
数组变为：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nkhzr6nQ-1581864714528)(https://s1.ax1x.com/2018/12/26/FgjAeI.png)]
i = 3; j = 7; X=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H3fTJ27R-1581864714529)(https://s1.ax1x.com/2018/12/30/FhUB4S.png)]
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
快速排序代码实现
using System;
class Program
{
/// <summary>
/// 对数组dataArray中索引从left到right之间的数做排序
/// </summary>
/// <param name="dataArray">要排序的数组</param>
/// <param name="left">要排序数据的开始索引</param>
/// <param name="right">要排序数据的结束索引</param>
static void QuickSort(int[] dataArray, int left, int right)
{
if (left < right)
{
int x = dataArray[left];//基准数， 把比它小或者等于它的 放在它的左边，然后把比它大的放在它的右边
int i = left;
int j = right;//用来做循环的标志位
while (true && i < j)//当i==j的时候，说明我们找到了一个中间位置，这个中间位置就是基准数应该所在的位置
{
//从后往前比较(从右向左比较) 找一个比x小（或者=）的数字，放在我们的坑里 坑位于i的位置
while (true && i < j)
{
if (dataArray[j] <= x) //找到了一个比基准数 小于或者等于的数子，应该把它放在x的左边
{
dataArray[i] = dataArray[j];
break;
}
else
{
j--;//向左移动 到下一个数字，然后做比较
}
}
//从前往后（从左向右）找一个比x大的数字，放在我们的坑里面 现在的坑位于j的位置
while (true && i < j)
{
if (dataArray[i] > x)
{
dataArray[j] = dataArray[i];
break;
}
else
{
i++;
}
}
}
//跳出循环 现在i==j i是中间位置
dataArray[i] = x;// left -i- right
QuickSort(dataArray, left, i - 1);
QuickSort(dataArray, i + 1, right);
}
}
static void Main(string[] args)
{
int[] data = new int[] { 42, 20, 17, 27, 13, 8, 17, 48 };
QuickSort(data, 0, data.Length - 1);
foreach (var temp in data)
{
Console.Write(temp + " ");
}
Console.ReadKey();
}
}
快排总结：
- i =L; j = R; 将基准数挖出形成第一个坑a[i]。
- j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
- i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
- 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
10
0- 0
已为社区贡献1条内容
所有评论(0)