数据结构

一般将数据结构分为两大类：

 线性数据结构和非线性数据结构。

 线性数据结构有:

 线性表、栈、队列、串、数组和文件；

 非线性数据结构有:

 散列表、树和图。

线性表

线性表的逻辑结构是n个数据元素的有限序列:

(a1, a2 ,a3,…an)

n为线性表的长度(n≥0)，n=0的表称为空表。

数据元素呈线性关系。必存在唯一的称为“第一个”的数据元素；必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都有且只有一个后继元素。

所有数据元素在同一个线性表中必须是相同的数据类型。

如图

线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表。

将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表。

栈(Stack)也是一种特殊的线性表，是一种后进先出(LIFO)的结构。

栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)。

栈的物理存储可以用顺序存储结构，也可以用链式存储结构。

栈

队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表。

表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)。

队列的操作是按先进先出(FIFO)的原则进行的。

队列的物理存储可以用顺序存储结构，也可以用链式存储结构。

队列

C#中的集合类

Array

数组为数据结构中的顺序表

MyArray[0], MyArray[1], MyArray[2]…………MyArray[6]

MyArray [0] = 1

提供对数组的相关操作

Array是抽象的基类，提供 CreateInstance 方法来创建数组

Array obj = Array.CreateInstance(typeof(string),10);

Array obj1 = Array.CreateInstance(typeof(string),2,3,4);

数组的局限性：

元素个数固定，且必须在创建数组时知道元素个数

元素类型必须相同

只能通过索引访问数组元素

举几个例子：

使用Array对两个数组进行合并操作：

向数组中追加数据对象，若位置不足，请扩容后追加

使用Array判断一个数组是否在另外一个数组中

写一个方法传入一个数组，要求先反转数组，然后对数组进行排序，显示每个阶段的结果

ArrayList

特点：

有序的对象列表 顺序结构.

ArrayList 很类似数组.

ArrayList 类没有固定大小；可以根据需要不断增长.

默认大小为16个元素，当添加第17个元素时会自动扩展到32个.

可以显式地指定其容量.

可以存储不同类型的元素， 因为所有ArrayList中的元素都是对象(System.Object).

ArrayList 的方法：

Add(object) 把一个对象添加到 ArrayList 的末尾.

Insert(index,object) 在指定位置插入一个对象.

Remove(object) 移除一个对象.

RemoveAt(index) 移除一个对象.

Clear() 移除所有元素.

Sort 对ArrayList 中的元素进行排序.

例子：

实现对列表（ArrayList或者List<T>）的增删改查功能

如何将10对象随机存入列表中

队列

特点：

先进先出的对象集合

特殊的顺序表

队列(Queue)

对象按照先进先出，先来先服务的原则

对象按顺序存储在默认大小为32的缓冲区中；当缓冲区空间不足时，按增长因子(2.0)创建一个新的缓冲区，并将现有对象拷贝到新缓冲区中(开销大)

Queue的方法：

Enqueue  入队 进队

Dequeue   出队 离队

Peek    查看队头

Clear  清除队列

Contains  询问是否包含

Count 队列中的元素个数

例子

如何用队列实现约瑟夫环？

        ///约瑟夫环：假设有n个人坐成一圈，从某个人开始报数，数到m的人出圈，

        ///接着从出圈的下一个人开始重新报数，数到m的人再次出圈，如此反复，直到所有人都出圈，请列出出圈顺序。

栈：先进后出(后进先出)的对象集合 特殊的顺序表

栈(Stack)

后进先出，最后插入的对象位于栈的顶端

Stack的方法：

Push 压栈 进栈 入栈

Pop 出栈 弹栈

Peek  查看栈顶

Clear  清空堆栈

Contains  是否包含

Count 栈内元素个数

例子：

/// 用栈实现加法式子的运算

        ///1+2+3+4

        ///+ *混合的怎么运算？