|
using System;
using System.Collections.Generic;
using System.Text;
namespace LinkList
{
/// <summary>
/// 结点类
/// 结点数据类型用double表示
/// </summary>
public class ListNode<T>
{
public T data; //ElemType
public ListNode(T value) : this() { this.data = value; }
internal ListNode() { this.next = null; }
public ListNode<T> next;
}
/// <summary>
/// 链表类
/// </summary>
public class LinkList<T>
{
private 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(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>
{
/// <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(x);
//xNode.data = x;
if (pNode != null)
{
while (pNode.next != null)
{
if (pNode.data < x && pNode.next.data > x)
{
xNode.next = pNode.next;
pNode.next = xNode;
count++;
break;
}
else if(pNode.data >x)
{
xNode.next = pNode;
count++;
first = xNode;
head .next = first;
break;
}
pNode = pNode.next;
}
if (pNode.next == null)
{
if (pNode.data > x)
{
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 object this[int index]
{
get { return this.GetNode(index).data; }
set { this.GetNode(index).data =(double) value; }
}
//public object this[int index]
//{
// get
// {
// int ctr = 0;
// ListNode node = first;
// while (node != null && ctr <= index)
// {
// if (ctr == index)
// {
// return node.data;
// }
// else
// {
// node = node.next;
// }
// ctr++;
// }
// return null;
// }
//}
class Program
{
static void Main(string[] args)
{
SortLinkList slltest = new SortLinkList();
slltest.Add(3.0);
slltest.Add(2.0);
slltest.Add(1.0);
slltest.Add(6.0);
slltest.Add(5.0);
slltest.Add(4.0);
slltest.OutPut();
double a1 = (double)slltest[0];
double a2 = (double)slltest[5];
double a3 = 9;
slltest[5] = a3;
slltest.OutPut();
}
}
}
}
| 