1、节点定义：
public class Node<T>
{
private T data;//数据域
private Node<T> next;//引用域
/// <summary>
/// 构造器，数据值为输入数据值
/// </summary>
/// <param name="val"></param>
public Node(T val)
{
data = val;
next = null;
}
/// <summary>
/// 构造器，数据值为系统默认值
/// </summary>
public Node()
{
data = default(T);
next = null;
}
/// <summary>
/// 数据域属性
/// </summary>
public T Data
{
get {return data;}
set { data = value; }
}
/// <summary>
/// 引用域属性
/// </summary>
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
2、单链表实现
public interface IListDS<T>
{
bool Insert(T item,int pos);//插入元素
bool IsEmpty();//是否为空
int GetLength();//得到容量
void Append(T item);//添加新元素
void Clear();//清空
T Delete(int pos);//删除元素
T GetElem(int pos);//根据索引查找
int Locate(T value);//根据值查找
}
public class SinglyLinkedList<T>:IListDS<T>
{
private Node<T> head;
/// <summary>
/// 单链表的头节点
/// </summary>
public Node<T> Head
{
get { return head; }
set { head = value; }
}
/// <summary>
/// 构造器，构造具有空指针的头节点
/// </summary>
public SinglyLinkedList()
{
head = null;
}
/// <summary>
/// 求单链表长度
/// </summary>
/// <returns></returns>
public int GetLength()
{
Node<T> currNode = head;
int length = 0;
while (currNode != null)
{
++length;
currNode = currNode.Next;
}
return length;
}
/// <summary>
/// 清空单链表
/// </summary>
public void Clear()
{
head = null;
}
/// <summary>
/// 判断单链表是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return (head == null) ? true : false;
}
/// <summary>
/// 在单链表末尾添加新元素
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
Node<T> newNode = new Node<T>(item);
Node<T> currNode = null;
if (head == null)
{
head = newNode;
return;
}
currNode = head;
while (currNode.Next != null)
{
currNode = currNode.Next;
}
currNode.Next = newNode;
}
/// <summary>
/// 在指定位置插入元素
/// </summary>
/// <param name="item"></param>
/// <param name="pos"></param>
/// <returns></returns>
public bool Insert(T item, int pos)
{
if (IsEmpty() || pos < 0)
{
Console.WriteLine("The list is empty");
return false;
}
Node<T> newNode = new Node<T>(item);
if (pos == 0)
{
newNode.Next = head;
head = newNode;
return true;
}
Node<T> currNode = head.Next;
Node<T> preNode = head;
int index = 1;
while (currNode.Next != null && index < pos)
{
preNode = currNode;
currNode = currNode.Next;
++index;
}//寻到pos-1个节点
if (index == pos)
{
newNode.Next = currNode;
preNode.Next = newNode;
return true;
}
else
{
Console.WriteLine("The position is error");
return false;
}
}
/// <summary>
/// 删除指定索引位置的元素
/// </summary>
/// <param name="pos"></param>
/// <returns></returns>
public T Delete(int pos)
{
if (IsEmpty() || pos < 0)
{
Console.WriteLine("The Link is empty");
return default(T);
}
T data = default(T);
if (pos == 0)
{
data = head.Data;
head = head.Next;
return data;
}
Node<T> preNode = this.head;
Node<T> currNode = this.head.Next;
int index = 1;
while (currNode.Next != null && index < pos)
{
++index;
preNode = currNode;
currNode = currNode.Next;
}//寻到pos-1个节点
if (index == pos)
{
preNode.Next = currNode.Next;
return currNode.Data;
}
else
{
Console.WriteLine("The position is out of range");
return default(T);
}
}
/// <summary>
/// 根据索引查找
/// </summary>
/// <param name="pos"></param>
/// <returns></returns>
public T GetElem(int pos)
{
if (IsEmpty())
{
Console.WriteLine("The list is empty");
return default(T);
}
Node<T> currNode = head;
int index = 0;
while (currNode.Next != null && index < pos)
{
++index;
currNode = currNode.Next;
}
if (index == pos)
return currNode.Data;
else
{
Console.WriteLine("The position is out of range");
return default(T);
}
}
/// <summary>
/// 根据值查找
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("The list is empty");
return -1;
}
Node<T> currNode = new Node<T>();
currNode = head;
int pos = -1;
while (currNode != null && currNode.Data.Equals(value))
{
currNode = currNode.Next;
++pos;
}//此处有问题
if (currNode == null)
return -1;
return pos;
}
}
演示效果：
class Program
{
static void Main(string[] args)
{
SinglyLinkedList<string> demoList = new SinglyLinkedList<string>();
/*添加*/
demoList.Append("Wang Hongjian");
demoList.Append("ZhangSan");
demoList.Append("LiSi");
for (int i = 0; i < demoList.GetLength(); i++)
{
Console.WriteLine("The {0} item is:/t{1}",i, demoList.GetElem(i));
}
/*插入*/
Console.WriteLine("Insert the item:");
demoList.Insert("Zhangyu", 1);
for (int i = 0; i < demoList.GetLength(); i++)
{
Console.WriteLine("The {0} item is:/t{1}", i, demoList.GetElem(i));
}
/*删除*/
Console.WriteLine("Delelte the item:");
demoList.Delete(3);
for (int i = 0; i < demoList.GetLength(); i++)
{
Console.WriteLine("The {0} item is:/t{1}", i, demoList.GetElem(i));
}
/*根据索引查找*/
Console.WriteLine("The 2st item is:/t{0}", demoList.GetElem(1));
/*根据值查找*/
Console.WriteLine("The position of the item 'Wang Hongjian' is:/t{0}", demoList.Locate("Wang Hongjian"));
/*清空*/
demoList.Clear();
Console.WriteLine("Now the list is empty");
Console.ReadKey();
}
}
