Posted on 2007-03-29 17:02
dennis 阅读(1985)
评论(1) 编辑 收藏 所属分类:
C#历程 、
数据结构与算法
今天受一个帖子的刺激，再次复习起了数据结构与算法，那本《数据结构与算法（java版）》我还剩图和高级排序的几章没看，工作上也没我的事需要处理，就用C#重新写了一遍链表结构，权作复习。
定义List接口：
public interface List
{
bool IsEmpty();
void Unshift(Object obj);
Object Shift();
void Push(Object obj);
Object Pop();
bool Contain(Object obj);
void Delete(Object obj);
void PrintAll();
Object getHead();
Object getTail();
void Clear();
}
实现单向链表：
//单向链表
public class SList:List
{
private SNode head, tail;
public SList()
{
this.head = this.tail = null;
}
public bool IsEmpty()
{
return head == null;
}
public void Unshift(Object obj)
{
head = new SNode(obj, head);
if (tail == null)
tail = head;
}
public Object Shift()
{
if (head == null)
throw new NullReferenceException();
Object value = head.value;
if (head == tail)
head = tail = null;
else
head = head.next;
return value;
}
public void Push(Object obj)
{
if (!IsEmpty())
{
tail.next = new SNode(obj);
tail = tail.next;
}
else
head = tail = new SNode(obj);
}
public Object Pop()
{
if (head == null)
throw new NullReferenceException();
Object obj = tail.value;
if (head == tail)
head = tail = null;
else
{
//查找前驱节点
for (SNode temp = head; temp.next != null && !temp.next.Equals(tail); temp = temp.next)
tail = temp;
tail.next = null;
}
return obj;
}
public void PrintAll()
{
string result = "";
for (SNode temp = head; temp != null; temp = temp.next)
result += " " + temp.value.ToString();
Console.WriteLine(result);
}
public bool Contain(Object obj)
{
if (head == null)
return false;
else
{
for (SNode temp = head; temp != null; temp = temp.next)
{
if (temp.value.Equals(obj))
return true;
}
}
return false;
}
public void Delete(Object obj)
{
if (!IsEmpty())
{
if (head == tail && head.value.Equals(obj))
head = tail = null;
else if (head.value.Equals(obj))
head = head.next;
else
{
//temp_prev为删除值的前驱节点
for (SNode temp_prev = head, temp = head.next; temp != null; temp_prev = temp_prev.next, temp = temp.next)
{
if (temp.value.Equals(obj))
{
temp_prev.next = temp.next; //设置前驱节点的next为下个节点
if (temp == tail)
tail = temp_prev;
temp = null;
break;
}
}
}
}
}
public Object getHead()
{
return this.head.value;
}
public Object getTail()
{
return this.tail.value;
}
public void Clear()
{
do
{
Delete(head.value);
} while (!IsEmpty());
}
}
class SNode
{
public Object value;
public SNode next;
public SNode(Object value, SNode next)
{
this.value = value;
this.next = next;
}
public SNode(Object value)
{
this.value = value;
this.next = null;
}
}
实现双向链表：
//双向链表
public class LinkedList:List
{
private LinkedNode head, tail;
public LinkedList()
{
head = tail = null;
}
public bool IsEmpty()
{
return head == null;
}
public void Unshift(Object obj)
{
if (IsEmpty())
head = tail = new LinkedNode(obj);
else
{
head = new LinkedNode(obj, null, head);
head.next.prev = head;
}
}
public Object Shift()
{
if (IsEmpty())
throw new NullReferenceException();
Object obj = head.value;
if (head == tail)
head = tail = null;
else
{
head = head.next;
head.prev = null;
}
return obj;
}
public void Push(Object obj)
{
if (IsEmpty())
head = tail = new LinkedNode(obj);
else
{
tail = new LinkedNode(obj, tail, null);
tail.prev.next = tail;
}
}
public Object Pop()
{
if (IsEmpty())
throw new NullReferenceException();
Object value = tail.value;
if (head == tail)
head = tail = null;
else
{
tail = tail.prev;
tail.next = null;
}
return value;
}
public bool Contain(Object obj)
{
if (IsEmpty())
return false;
else
{
for (LinkedNode temp = head; temp != null; temp = temp.next)
if (temp.value.Equals(obj))
return true;
}
return false;
}
public void Delete(Object obj)
{
if (IsEmpty())
throw new NullReferenceException();
if (head == tail)
head = tail = null;
else
{
for (LinkedNode temp = head; temp != null; temp = temp.next)
{
if (temp.value.Equals(obj))
{
if (temp.value.Equals(obj))
{
if (temp == tail)
{
tail = tail.prev;
tail.next = null;
break;
}
else if (temp == head)
{
head.next.prev = null;
head = head.next;
}
else
temp.prev.next = temp.next;
}
}
}
}
}
public void PrintAll()
{
string result = "";
for(LinkedNode temp=head;temp!=null;temp=temp.next)
result += " " + temp.value.ToString();
Console.WriteLine(result);
}
public Object getHead()
{
return this.head.value;
}
public Object getTail()
{
return this.tail.value;
}
public void Clear()
{
do
{
Delete(head.value);
} while (!IsEmpty());
}
}
class LinkedNode
{
public Object value;
public LinkedNode prev;
public LinkedNode next;
public LinkedNode(Object value, LinkedNode prev, LinkedNode next)
{
this.value = value;
this.next = next;
this.prev = prev;
}
public LinkedNode(Object value)
{
this.value = value;
}
}