线性表（二）：单链表
2012-03-04 20:34:02一、链表概述
线性表的链式表示就是采用链表实现存储，即表中数据元素是用一组任意的存储单元存储，它不要求逻辑上相邻的元素在物理位置上也相邻。这种数据结构有以下优点：其一，在进行插入和删除操作时，无需移动大量元素；其二，给长度变化较大的线性表无需预先分配最大空间；其三，表容量容易扩充。链表的特点是用一组任意的存储单元存储线性表的数据元素。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。
二、线性表的链式表示之单链表
由n个结点链接起来，且每个节点只包含一个引用域的链表称为单链表。
对单链表进行操作
1.初始化单链表
步骤：
a.声明一个为结点类型的start变量，用来指向单链表的第一个结点。
b.在单链表的构造函数中将start变量的值赋为null。
2.插入操作
步骤：
①在单链表开头插入新的结点
a.为新结点分配内存并为数据字段分配值。
b.使新结点的next字段指向列表中的第一个结点。
c.是start指向新结点。
②在单链表两个结点之间插入结点
a.为新结点分配内存并为数据字段分配值。
b.确定要在那两个结点之间插入新结点。将它们标记为前结点previous和当前结点current。找到前一个和当前结点，请执行步骤：
⑴.使previous指向null；
⑵使current指向第一个结点；
⑶如果新结点的序号大于当前结点的值，重复步骤⑷、⑸；
⑷使previous指向current；
⑸使current指向序列中的下一个结点。
c.使新结点的next字段指向当前结点。
d.使前一个结点的next字段指向新结点。
③在单链表末尾插入一个新结点
a.为新结点分配内存并为数据字段分配值。
b.找到列表中的最后一个结点，将它标记为current。
c.是current的next字段指向新结点。
d.使新结点的next字段指向null，释放current空间。
3.删除操作
步骤：
①在单链表开头删除结点
a.将列表中的一个结点标记为当前结点。
b.使start指向单链表中的下一个结点。
c.释放标记为当前结点的内存。
②在单链表两个结点之间删除结点
a.定位要删除的结点，请执行步骤：
⑴.将previous设置为null；⑵将current设置为start；⑶比较当前结点和要删除结点的序号，直到相等或当前结点变成为null为止，否则重复步骤⑷、⑸；
⑷使previous指向current；⑸使current指向序列中的下一个结点。
c.使前一个结点指向序列中的下一个结点。
d.释放标记为当前结点的结点内存，previous设为null。
③在单链表末尾插入一个新结点
和在两个结点之间删除结点方法一致，因当前结点current指向列表中最后一个结点，则说明要删除的结点是列表中最后一个结点。
4.取表元素
步骤：
a.将单链表的启始结点标记为当前结点current。
b.如果单链表不为空链表，比较要查找的序号或值是否与current的引用所指向的序号或值相等，如果不等的话current指向下一个结点，找到该结点时，返回current。
c.当current为null时，表示没有找到指定的结点。
其他操作比较简单，不再分析，实现细节参见下面代码。
三、单链表的实现
因单链表不像顺序表那样可以用数组存储，因此需要先定义一个类型来存储单链表，实现如下：
public class Node<T>
{
private T data; //数据域
private Node<T> next; //引用域
public Node(T data, Node<T> next)
{
this.data = data;
this.next = next;
}
public Node(T data)
{
this.data = data;
next = null;
}
public Node(Node<T> next)
{
this.next = next;
}
public Node()
{
data = default(T);
next = null;
}
public T Data
{
get { return this.data; }
set { this.data = value; }
}
public Node<T> Next
{
get { return this.next; }
set { this.next = value; }
}
}
基本运算在单链表上的实现如下：
public class LinkList<T>
{
private Node<T> start; //头引用
private int length; //长度
public int Length
{
get { return this.length; }
}
public LinkList()
{
start = null;
}
public void InsertNode(T data)
{
if (start == null)
{
start = new Node<T>(data);
length = 1;
return;
}
Node<T> current = start;
while (current.Next != null)
{
current = current.Next;
}
current.Next = new Node<T>(data);
length++;
}
public void InsertNode(T data, int i)
{
if (i < 0 || i > length + 1)
{
throw new Exception("输入的位置有误");
}
Node<T> current;
Node<T> previous;
Node<T> newNode = new Node<T>(data);
//在空链表或第一个元素前插入第一个元素
if (i == 1)
{
newNode.Next = start;
start = newNode;
length++;
return;
}
//在两个元素间插入一个元素
current = start;
previous = null;
int j = 1;
while (current != null && j < i)
{
previous = current;
current = current.Next;
j++;
}
previous.Next = newNode;
newNode.Next = current;
length++;
}
public void DeleteNode(int i)
{
if (IsEmpty() || i < 1 || i > length)
{
throw new Exception("链表为空或者要删除的位置不正确");
}
Node<T> current = start;
//删除表头元素
if (i == 1)
{
start = current.Next;
length--;
return;
}
Node<T> previous = null;
int j=1;
while (current != null && j < i)
{
previous = current;
current = current.Next;
j++;
}
previous.Next = current.Next;
current = null;
length--;
}
public T SearchNode(int i)
{
if (IsEmpty() || i < 1 || i > length)
{
return default(T);
}
Node<T> current = start;
int j = 1;
while (current.Next != null && j < i)
{
current = current.Next;
j++;
}
return current.Data;
}
public T SearchNode(T value)
{
if (IsEmpty())
{
throw new Exception("链表为空");
}
Node<T> current = start;
while (current.Data.ToString().Contains(value.ToString()) && current != null)
{
current = current.Next;
}
if(current != null)
return current.Data;
else
return default(T);
}
public void Clear()
{
start = null;
length = 0;
}
public bool IsEmpty()
{
if (start == null)
return true;
else
return false;
}
}
