1、线性表
概念：:零个或多个数据元素的有序序列。
描述：
2、线性表的抽象数据类型：
ADT线性表
Data：线性表的数据对象集合为{a1,a2,...,an}，每个元素的类型均为DataType。其中除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素，数据元素之间的关系是一对一的关系。
Operation
Init(*L):初始化操作，建立一个空的线性表；
IsEmpty（*L）:判断线性表是否为空，若为空，则返回true，否则返回false；
Clear(*L)：清空线性表；
GetElem(*L,i)：返回线性表位置为i的元素；
LocateElem（*L,e）：返回线性表中与元素i相同值的位置；
Insert(*L,i,e)：在线性表i位置插入元素e；
Delete（*L，i）：删除线性表位置i的元素；
GetLength（*L）：获得当前线性表的长度。
endADT
3、线性表的顺序存储结构
概念：用一段地址连续的存储单元存储线性表的数据元素。
如图：
算法的C#语言实现
/// <summary>
/// 线性表的顺序存储结构
/// </summary>
public class SequentialStorageLinearList<T>
{
//最大存放数量
private int _maxLength; /// <summary>
/// 最大存储数量
/// </summary>
public int MaxLength
{
get
{
return _maxLength;
}
} // 当前存放位置
private int _currentLength; private T[] _LinearList; //利用构造函数创建一个数组，用来存放数据
public SequentialStorageLinearList(int maxLength)
{
if (maxLength <= 0)
throw new Exception("The length can not be less than zero.");
_maxLength = maxLength;
_currentLength = 0;
_LinearList = new T[_maxLength];
} /// <summary>
/// 判断线性表是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return _currentLength == 0;
} /// <summary>
/// 清空所有的元素
/// </summary>
public void ClearAll()
{
if (_currentLength > 0)
{
/*
* 在高级语言.net中，我们可以重新创建一个新的数组，将其指向当前的_linearList
*由于是托管代码，资源不需要手动释放，会自动释放
*但是在c语言中，我们需要手动的释放其占用的空间(free)
*/
_LinearList = new T[0];
}
} /// <summary>
/// 根据
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T GetElement(int i)
{
if (_currentLength == 0 || _currentLength < i || i < 1)
throw new Exception("Not find any Element.");
T t = _LinearList[i];
return t;
} /// <summary>
/// 查找数据中是否存在元素e
/// </summary>
/// <param name="e"></param>
/// <returns></returns>
public int IndexOf(T e)
{
if (_currentLength == 0)
throw new Exception("The array is empty.");
for (int i = 0; i < _currentLength; i++)
{
T t = _LinearList[i];
/*
* T可能是引用类型，我们暂时的比较方式，不考虑重写equals
*/
if (t.Equals(e))
{
return i;
}
}
return -1;
} /// <summary>
/// 在位置i处插入元素e
/// </summary>
/// <param name="e">待插入的元素e</param>
/// <param name="i">插入位置i</param>
public void Insert(T e, int i)
{
//数组已经存满
if (_currentLength == _maxLength)
throw new Exception("The array is full.");
//当i位置不在范围内
if (i < 1 || i > _currentLength + 1)
throw new Exception("The location is illegal.");
//若插入的数据不在表尾，在需要移动插入位置后面的数据一位
if (i <= _currentLength - 1)
{
for (int j = _currentLength - 1; j > i; j--)
{
_LinearList[j + 1] = _LinearList[j];
}
}
_LinearList[i - 1] = e;
_currentLength++;
} /// <summary>
/// 删除位置i处的元素
/// </summary>
/// <param name="i">位置i</param>
public void Delete(int i)
{
if (_currentLength == 0)
throw new Exception("The array is Empty.");
if (i < 1 || i > _currentLength)
throw new Exception("The location is illegal.");
//删除位置i元素后需要将i后面的元素依次递增一位
if (i < _currentLength)
{
for (int k = k-1; k < _currentLength; k++)
{
_LinearList[k - 1] = _LinearList[k];
}
}
_currentLength--;
}
}
4、线性表的链式存储结构
数据域：存储数据元素信息的域；
指针域：存储直接后继位置的域；
节点（Node）：由数据域和指针域组成的数据元素ai的存储映像；
我们把由n个节点链结成一个链表，即为线性表的链式存储结构。
如图：
5、单链表
链表的每个将结点中只包含一个指针域，我们称为单链表。同时我们把链表中第 一个结点的存储位置称为头指针。同时在链表的第一个结点前附设一个结点，称 为头结点。
单链表的C#实现：
/// <summary>
/// 单链表的实现
/// </summary>
/// <typeparam name="T"></typeparam>
public class SingleNode<T>
{
/// <summary>
/// 序号
/// </summary>
public int Index { get; private set; } /// <summary>
/// 头指针
/// </summary>
public SingleNode<T> HeadNode { get; private set; } /// <summary>
/// 指针域
/// </summary>
public SingleNode<T> NextNode { get; set; } /// <summary>
/// 数据域
/// </summary>
public T Data { get; set; } public SingleNode()
{
HeadNode = new SingleNode<T>();
Index = ;
NextNode = null;
} public SingleNode(T t)
{
Data = t;
NextNode = null;
} /// <summary>
/// 判断单链表是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return Index == ;
} /// <summary>
/// 清空所有的元素
/// </summary>
public void ClearAll()
{
if (Index > )
{
NextNode = null;
Data = default(T);
Index = ;
}
} /// <summary>
/// 获得位置为i的元素
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public SingleNode<T> GetElement(int i)
{
if (Index == || Index < i || i < )
throw new Exception("Not find any Element.");
SingleNode<T> head = HeadNode;
SingleNode<T> next;
for (int k = ; k < Index; k++)
{
next = head.NextNode;
if (next.Index == i)
{
return next;
}
head = next.NextNode;
}
return null;
} /// <summary>
/// 查找数据中是否存在元素e
/// </summary>
/// <param name="e"></param>
/// <returns></returns>
public int IndexOf(T e)
{
if (Index == )
throw new Exception("The array is empty.");
SingleNode<T> head = HeadNode;
SingleNode<T> next;
for (int k = ; k < Index; k++)
{
next = head.NextNode;
if (next.Equals(e))
{
return next.Index;
}
head = next.NextNode;
}
return -;
} /// <summary>
/// 在位置i处插入元素e
/// </summary>
/// <param name="e">待插入的元素e</param>
/// <param name="i">插入位置i</param>
public void Insert(T t, int i)
{
/*
*1.先判断i是否存在
*2.若存在则创建一个空节点，将值t赋给该空节点
*3.修改该节点的前驱和后继节点
*/
if (i < || i > Index)
throw new Exception("The location is illegal.");
//获得当前位置i的节点
var preNode = GetElement(i); //创建空节点
SingleNode<T> currentNode = new SingleNode<T>(t); //修改前驱节点指向当前节点
var nextNode = preNode.NextNode;
preNode.NextNode = currentNode; //将新节点的后继节点修改
currentNode.NextNode = nextNode; Index++;
} /// <summary>
/// 删除位置i处的元素
/// </summary>
/// <param name="i">位置i</param>
public void Delete(int i)
{
/*
*1.查找位置为i的节点
*2.修改节点的前继节点为查找节点的下一节点
*/
//获得当前位置i-1的节点
if (i < || i > Index)
throw new Exception("The location is illegal.");
var preNode = GetElement(i - );
var nextNextNode = preNode.NextNode.NextNode;
preNode.NextNode = nextNextNode;
Index--;
}
}
6、循环链表
将单链表中终端节点的指针端由空指针改为指向头节点，这样整个单链表就成为了一个环，这种头尾相接的单链表称为单循环链表。
如图：
实现代码类似与单链表。
7、双向链表
在单链表的每个节点中，再设置一个指向其前驱节点的指针，从而形成的链表，我们称为双向链表。
如图：
C#代码实现：
8、链表和线性表的优缺点比较
如图：
9、参考资料：
单链表的19种操作： http://www.cnblogs.com/lifuqing/archive/2011/08/20/List.html
单链表的C#实现：http://www.cnblogs.com/linzheng/news/2011/07/14/2106173.html