线性表（Linear List）
具有相同特性的数据元素的一个有限序列。
线性表的顺序存储结构—顺序表
线性表的顺序存储结构是指用一块地址连续的存储空间依次存储线性表的数据元素。这种存储方式好比改革前的银行，需要在业务窗口前排队取钱。由此可以看出顺序表中逻辑上相邻的元素在物理上也是相邻的。
顺序表的特点
1.容量固定
存储顺序表的元素需要一整块内存空间，因而顺序表的容量一旦确定，便不能更改。
2.访问速度快
在顺序表使用索引访问数据元素是非常简单、快速的。如图2.3所示，假设顺序表中的第一个元素的位置是Loc，每个数据元素所占用的存储空间为n，那么可以很快地计算出第i个元素的存储地址为：Loc + (i – 1) * n。
数组
线性表的顺序存储结构在C#中的最直接表现形式就是数组。在C#语言中，数组是最基础也是存取速度最快的一种集合类型。数组是引用类型，保存它们所需的内存空间会在托管堆上分配，一旦数组被创建，其中的所有元素将被初始化为它们的默认值。
int[] arrInt = newint[5];
arrInt[2] = 5;
arrInt[4] = 3;
以上代码声明了一个值类型int的数组，并把它的长度初始化为5，最后分别给第3和第5个元素赋值。
当数组元素为值类型时，数组对象存放的是值类型对象本身。当元素为引用类型时，数组对象存放的则是对象的引用（指针）。
Control[] arrCtrl = new Control[5];
arrCtrl[0] = new Button();
arrCtrl[3] = new Label();
以上代码声明了一个引用类型Control的数组，并把它的长度初始化为5，最后分别给第1和第4个元素赋值。两个值是分别Button和Label对象，虽然它们都继承自Control类，但两者却是不同类，它们的大小不一样。
C#与数据结构--ArrayList
2.2.3 ArrayList
C#中的ArrayList动态改变数组大小的。ArrayList又被称为动态数组，它的存储空间可以被动态改变，同时还拥有添加、删除元素的功能。
Insert(int index, object value)方法用于在指定索引处插入一个元素。为了保证顺序表中的每个元素物理上相邻，插入点后面的所有元素都将后移一位。
RemoveAt(int index)方法用于删除指定索引的元素，删除指定元素后，删除点后的所有元素将向前移动一位。
二叉树的存储结构
二叉树的存储可分为两种：顺序存储结构和链式存储结构。
1.顺序存储结构
把一个满二叉树自上而下、从左到右顺序编号，依次存放在数组内，可得到图6.8(a)所示的结果。设满二叉树结点在数组中的索引号为i，那么有如下性质。
（1） 如果i = 0，此结点为根结点，无双亲。
（2） 如果i > 0，则其双亲结点为(i -1) / 2 。（注意，这里的除法是整除，结果中的小数部分会被舍弃。）
（3） 结点i的左孩子为2i + 1，右孩子为2i + 2。
（4） 如果i > 0，当i为奇数时，它是双亲结点的左孩子，它的兄弟为i + 1；当i为偶数时，它是双新结点的右孩子，它的兄弟结点为i – 1。
（5） 深度为k的满二叉树需要长度为2 k-1的数组进行存储。
通过以上性质可知，使用数组存放满二叉树的各结点非常方便，可以根据一个结点的索引号很容易地推算出它的双亲、孩子、兄弟等结点的编号，从而对这些结点进行访问，这是一种存储二叉满二叉树或完全二叉树的最简单、最省空间的做法。
为了用结点在数组中的位置反映出结点之间的逻辑关系，存储一般二叉树时，只需要将数组中空结点所对应的位置设为空即可，其效果如图6.8(b)所示。这会造成一定的空间浪费，但如果空结点的数量不是很多，这些浪费可以忽略。
一个深度为k的二叉树需要2 k-1个存储空间，当k值很大并且二叉树的空结点很多时，最坏的情况是每层只有一个结点，再使用顺序存储结构来存储显然会造成极大地浪费，这时就应该使用链式存储结构来存储二叉树中的数据。
2.链式存储结构
二叉树的链式存储结构可分为二叉链表和三叉链表。二叉链表中，每个结点除了存储本身的数据外，还应该设置两个指针域left和right，它们分别指向左孩子和右孩子，当需要在二叉树中经常寻找某结点的双亲，每个结点还可以加一个指向双亲的指针域parent。
3二叉树的深度优先遍历
1.先序遍历
若二叉树为非空，则过程为：
（1） 访问根节点。
（2） 先序遍历左子树。
（3） 先序遍历右子树。
图6.13中，先序遍历就是把标号为(1)的结点按搜索路径访问的先后次序连接起来，得出结果为：ABDECF。
2.中序遍历
若二叉树为非空，则过程为：
（1） 按中序遍历左子树。
（2） 访问根结点。
（3） 按中序遍历右子树。
图6.13中，先序遍历就是把标号为(2)的结点按搜索路径访问的先后次序连接起来，得出结果为：DBEACF。
3.后序遍历
若二叉树为非空，则过程为：
（1） 按后序遍历左子树。
（2） 按后序遍历右子树
（3） 访问根结点。