|
using System;
using System.Collections.Generic;
using System.Text;
namespace LinkList
{
/// <summary>
/// 结点类
/// 结点数据类型用double表示
/// </summary>
public class ListNode<T> //: IComparable<T>
{
public T data; //ElemType
public ListNode(T value) : this() { this.data = value; }
internal ListNode() { this.next = null; }
EqualityComparer<T> m_Comparer = EqualityComparer<T>.Default;
public ListNode<T> next;
}
/// <summary>
/// 链表类
/// </summary>
public class LinkList<T>//:IComparable<T>//:ICollection <T>,IEnumerator<T>,IList <T>
{
public int count;
private ListNode<T> hNode;
public ListNode<T> head;
public ListNode<T> first; //第一个结点
EqualityComparer<T> m_Comparer = EqualityComparer<T>.Default;
public LinkList()
{
hNode = new ListNode<T>();
//hNode.data = <T>count;
hNode.next = null;
head = hNode;
first = null;
}
public bool IsEmpty()
{
return head .next == null;
}
public int Length()
{
ListNode<T> current = first;
int length = 0;
while (current != null)
{
length++;
current = current.next;
}
return length;
}
/// <summary>
/// 返回第k个元素至x中
/// </summary>
/// <param name="k"></param>
/// <param name="x"></param>
/// <returns>如果不存在第k个元素则返回false,否则返回true</returns>
public bool Find(int k, ref T x)
{
if (k < 1)
return false;
ListNode<T> current = first;
int index = 1;
while (index < k && current != null)
{
current = current.next;
index++;
}
if (current != null)
{
x = current.data;
return true;
}
return false;
}
/// <summary>
/// 返回x所在的位置
/// </summary>
/// <param name="x"></param>
/// <returns>如果x不在表中则返回0</returns>
public int Search(T x)
{
ListNode<T> current = first;
int index = 1;
while (current != null && !m_Comparer.Equals(x, current.data))
{
current = current.next;
index++;
}
if (current != null)
return index;
return 0;
}
/// <summary>
/// 删除第k个元素，并用x返回其值
/// </summary>
/// <param name="k"></param>
/// <param name="x"></param>
/// <returns></returns>
public LinkList<T> Delete(int k, ref T x)
{
//如果不存在第k个元素则引发异常
if (k < 1 || first == null)
throw (new NullReferenceException());
ListNode<T> pNode = first; //pNode将最终指向第k个结点
//将pNode移动至第k个元素，并从链表中删除该元素
if (k == 1) //pNode已经指向第k个元素
{
x = first.data;
first = first.next; //删除之
}
else
{
//用qNode指向第k-1个元素
ListNode<T> qNode = first;
for (int index = 1; index < k - 1 && qNode != null; index++)
qNode = qNode.next;
if (qNode == null || qNode.next == null)
throw (new NullReferenceException());//不存在第k个元素
pNode = qNode.next; //pNode指向第k个元素
qNode.next = pNode.next; //从链表中删除第k个元素
x = pNode.data;
}
return this;
}
/// <summary>
/// 在第k个元素之后插入x
/// </summary>
/// <param name="k"></param>
/// <param name="x"></param>
/// <returns></returns>
public LinkList<T> Insert(int k, T x)
{
//如果不存在第k个元素,则引发异常NullReferenceException
if (k < 0)
throw (new IndexOutOfRangeException());
ListNode<T> pNode = first; //pNode将最终指向第k个结点
for (int index = 1; index < k && pNode != null; index++)
pNode = pNode.next;
if (k > 0 && pNode == null)
throw (new NullReferenceException());//不存在第k个元素
ListNode<T> xNode = new ListNode<T>(x);
//xNode.data = x;
if (k > 0)
{
//在pNode之后插入
xNode.next = pNode.next;
pNode.next = xNode;
}
else
{
//作为第一个元素插入
xNode.next = first;
first = xNode;
}
return this;
}
public void Clear()
{
first = null;
}
public void OutPut()
{
ListNode<T> current;
for (current = first; current != null; current = current.next)
{
Console.Write("{0}", current.data.ToString());
}
Console.WriteLine();
}
}
public class SortLinkList<T> : LinkList<T> where T : IComparable<T>
{
public override String ToString()
{
StringBuilder sb = new StringBuilder();
return sb.ToString();
}
public IEnumerator<T> GetEnumerator()
{
ListNode<T> current = head;
while (current != null)
{
yield return current.data;
current = current.next;
}
}
/// <summary>
/// 返回x所在的位置
/// </summary>
/// <param name="x"></param>
/// <returns>如果x不在表中则返回0</returns>
public SortLinkList<T> Add(T x)
{
//int index = 1;
ListNode<T> pNode = first; //pNode将最终指向第k个结点
ListNode<T> xNode = new ListNode<T>(x);
//xNode.data = x;
if (pNode != null)
{
while (pNode.next != null)
{
if (pNode.data.CompareTo(x) < 0 && pNode.next.data.CompareTo(x) > 0)
{
xNode.next = pNode.next;
pNode.next = xNode;
count++;
break;
}
else if (pNode.data.CompareTo(x) > 0)
{
xNode.next = pNode;
count++;
first = xNode;
head.next = first;
break;
}
pNode = pNode.next;
}
if (pNode.next == null)
{
if (pNode.data.CompareTo(x) > 0)
{
pNode.next = xNode;
count++;
T temp = xNode.data;
xNode.data = pNode.data;
pNode.data = temp;
}
else
{
pNode.next = xNode;
count++;
}
}
}
else
{
//作为第一个元素插入
count++;
xNode.next = first;
first = xNode;
head.next = first;
}
return this;
}
private ListNode<T> GetNode(int index)
{
if (index < 0 || index >= this.count)
throw new ArgumentOutOfRangeException("index", index, "Index value is out of range, please check!");
ListNode<T> node = this.head.next;
while (index-- > 0) node = node.next;
return node;
}
public T this[int index]
{
get { return this.GetNode(index).data; }
set { this.GetNode(index).data = value; }
}
}
class Program
{
static void Main(string[] args)
{
//Declare and instantiate a new generic SortedList class.
//Person is the type argument.
SortLinkList<Person> list = new SortLinkList<Person>();
//Create name and age values to initialize Person objects.
string[] names = new string[]{"Franscoise", "Bill", "Li", "Sandra", "Gunnar", "Alok", "Hiroyuki", "Maria", "Alessandro", "Raul"};
int[] ages = new int[]{45, 19, 28, 23, 18, 9, 108, 72, 30, 35};
//Populate the list.
for (int x = 0; x < 10; x++)
{
list.Add(new Person(names[x], ages[x]));
}
}
}
public class Person : IComparable<Person>
{
string name;
int age;
public Person()
{
}
public Person(string s, int i)
{
name = s;
age = i;
}
// This will cause list elements
// to be sorted on age values.
public int CompareTo(Person p)
{
return age - p.age;
}
public override string ToString()
{
return name + ":" + age;
}
// Must implement Equals.
public bool Equals(Person p)
{
return (this.age == p.age);
}
}
}
| 