下面是C#版链表的实现过程
分为两个类:
- CSArrayListNode类,用于表示一个结点
- CSArrayList,用于表示链表本身
下面是这两个类的视图
大家可以根据视图得到这两个类的基本结构 ,代码中有详细的注释.
大家有什么问题可以给我发送邮件：warensoft@163.com
代码
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace 链表
{
/// <summary>
/// 用于表示链表的一个结点
/// </summary>
public class CSArrayListNode
{
private object element;
/// <summary>
/// 当前结点中的元素值
/// </summary>
public object Element
{
get { return element; }
set { element = value; }
}
private CSArrayListNode nextNode;
/// <summary>
/// 该结结点的下一个结点的引用
/// </summary>
public CSArrayListNode NextNode
{
get { return nextNode; }
set { nextNode = value; }
}
}
/// <summary>
/// 用于表示链表
/// </summary>
public class CSArrayList
{
CSArrayListNode firstNode;
int count;bool isReadOnly = false;
/// <summary>
/// 获取 CSArrayList 中实际包含的元素数。
/// </summary>
public int Count
{
get
{
return this.count;
}
}
/// <summary>
/// 将对象添加到 CSArrayList 的结尾处。
/// </summary>
/// <param name="Item">要添加到 CSArrayList 的末尾处的 Object。该值可以为 空引用.</param>
public void Add(object Item)
{
//第一次加入元素
if (this.firstNode ==null )
{
this.firstNode = new CSArrayListNode();
this.firstNode.Element = Item;
}
//非第一次加入元素
else
{
CSArrayListNode tmpnode = this.firstNode ;
//通过循环找到最后一个结点
while (true)
{
//如果该结点为空，则将新值插入该链表
if ( tmpnode.NextNode==null )
{
tmpnode.NextNode = new CSArrayListNode();
tmpnode.NextNode.Element = Item;
break;
}
tmpnode = tmpnode.NextNode;
}
}
//链表长度增加１
this.count++;
}
/// <summary>
/// 从 CSArrayList 中移除所有元素。
/// </summary>
public void Clear()
{
//最好将所有结点清空
this.firstNode = null;
}
/// <summary>
/// 确定某元素是否在 CSArrayList 中。
/// </summary>
/// <param name="item">要在 ArrayList 中查找的 Object。该值可以为 空引用</param>
/// <returns>如果在 CSArrayList 中找到 item，则为 true；否则为 false。</returns>
public bool Contains(object item)
{
CSArrayListNode tmpnode = this.firstNode ;
while (true)
{
if (tmpnode ==null )
{
return false;
}
if (tmpnode .Element .Equals (item))
{
return true;
}
tmpnode = tmpnode.NextNode;
}
}
/// <summary>
/// 搜索指定的 Object，并返回整个 ArrayList 中第一个匹配项的从零开始的索引。
/// </summary>
/// <param name="value">要在 ArrayList 中查找的 Object。</param>
/// <returns>如果在整个 ArrayList 中找到 value 的第一个匹配项，则为该项的从零开始的索引；否则为 -1。 </returns>
public int IndexOf(object value)
{
CSArrayListNode tmpnode = this.firstNode;
int index = 0;
while (true)
{
//如果找到最后一个还找不到，则返回－１
if (tmpnode == null)
{
return -1;
}
//否则返回索引号
if (tmpnode.Element.Equals(value ))
{
return index ;
}
tmpnode = tmpnode.NextNode;
index++;
}
}
/// <summary>
/// 将元素插入 ArrayList 的指定索引处。
/// </summary>
/// <param name="index">从零开始的索引，应在该位置插入 value。</param>
/// <param name="value">要插入的 Object。</param>
public void Insert(int index, object value)
{
//如果索引号大于该链表的长度,则不作为
if (index>this.count )
{
return;
}
//如果索引号是0,则直接将该值插入第一个结点
if (index == 0)
{
CSArrayListNode node = new CSArrayListNode();
node.Element = value;
node.NextNode = this.firstNode;
this.firstNode = node;
this.count++;
return ;
}
CSArrayListNode tmpnode = this.firstNode;
int index1 =0;
while (true)
{
if (tmpnode == null)
{
return ;
}
//插入新值,这里要注意结点是如何交换的
//C#的类名就是引用,这一点类似于C++中的指针
if (index ==(index1+1))
{
CSArrayListNode node = new CSArrayListNode();
node.Element = value;
node.NextNode = tmpnode.NextNode;
tmpnode.NextNode = node;
this.count++;
return ;
}
tmpnode = tmpnode.NextNode;
index1++;
}
}
/// <summary>
/// 从 ArrayList 中移除特定对象的第一个匹配项。
/// </summary>
/// <param name="value">要从 ArrayList 移除的 Object。</param>
public void Remove(object value)
{
if (this.firstNode .Element .Equals (value ))
{
this.firstNode = this.firstNode.NextNode;
this.count--;
return;
}
int index = 0;
CSArrayListNode tmpnode = this.firstNode;
while (true)
{
if (tmpnode.NextNode ==null )
{
return ;
}
if (tmpnode .NextNode .Element .Equals (value ))
{
tmpnode.NextNode = tmpnode.NextNode.NextNode;
this.count--;
return;
}
tmpnode = tmpnode.NextNode;
index++;
}
}
/// <summary>
/// 移除 ArrayList 的指定索引处的元素。
/// </summary>
/// <param name="index">要移除的元素的从零开始的索引。</param>
public void RemoveAt(int index)
{
if (index > this.count )
{
return;
}
if (index==0)
{
this.firstNode = this.firstNode.NextNode;
this.count--;
return;
}
int index1 = 0;
CSArrayListNode tmpnode = this.firstNode;
while (true)
{
if (index1 ==(this.count -1))
{
return;
}
if (index ==(index1 +1))
{
tmpnode.NextNode = tmpnode.NextNode.NextNode;
this.count--;
return;
}
tmpnode = tmpnode.NextNode;
index1++;
}
}
public object this[int index]
{
get
{
if (index > this.count - 1)
{
return null ;
}
CSArrayListNode tmpnode = this.firstNode;
for (int i = 0; i < index; i++)
{
tmpnode = tmpnode.NextNode;
}
return tmpnode.Element;
}
set
{
if (index > this.count - 1)
{
return;
}
CSArrayListNode tmpnode = this.firstNode;
for (int i = 0; i < index; i++)
{
tmpnode.NextNode = tmpnode.NextNode;
}
tmpnode.Element=value ;
}
}
}
}