数据结构
一般将数据结构分为两大类:
线性数据结构和非线性数据结构.
线性数据结构有:
线性表, 栈, 队列, 串, 数组和文件;
非线性数据结构有:
散列表, 树和图.
线性表
线性表的逻辑结构是 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
- ///+ * 混合的怎么运算?
来源: http://www.jianshu.com/p/7699efd462d5