|
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); }
}
}
|