 数据结构双向链表的C#实现
发信人: Jobs (温少), 信区: DotNET
标 题: 数据结构双向链表的C#实现
发信站: BBS 水木清华站 (Thu Jan 2 13:14:38 2003)
/**
*
*
@author <a href="wen">mailto:szuJobs@hotmail.com">wenshaojin</a>
@created January 2, 2003
@version 1
*
**/
using System;
using System.Collections;
using System.IO;
namespace Matrix.Common.Collections
{
/// <summary>
/// 双向链表
/// </summary>
public class DoublyLinkedList : IEnumerable
{
private DoublyLinkedListNode _first;
private int _count;
public DoublyLinkedList()
{
_count = 0;
_first = null;
}
public int Count
{
get
{
return _count;
}
}
public object this[int pos]
{
get
{
if(pos < 0)
{
throw new ArgumentOutOfRangeException("pos");
}
DoublyLinkedListNode current = this._first;
int index = 0;
while(index < pos && current != null)
{
index ++;
current = current.Right;
}
if(current != null)
{
return current.Data;
}
else
{
throw new ArgumentOutOfRangeException("pos");
}
}
}
private DoublyLinkedListNode FindNode(int pos)
{
//p will eventually point to k'th node
DoublyLinkedListNode p = this._first;
for(int i=0; i<pos && p != null; i++) // move p to pos'th
{
p = p.Right;
}
if(pos > 0 && p == null) // no pos'th
{
throw new ArgumentOutOfRangeException("pos");
}
return p;
}
private void InsertBefore(DoublyLinkedListNode p, object data)
{
DoublyLinkedListNode y = new DoublyLinkedListNode();
y.Data = data;
y.Left = p.Left;
y.Right = p;
p.Left.Right = y;
p.Left = y;
}
private void Delete(DoublyLinkedListNode p)
{
if(p == this._first)
{
this._first = this._first.Right;
this._first.Left = null;
}
else if(p.Right == null)
{
p.Left.Right = null;
}
else
{
p.Left.Right = p.Right;
p.Right.Left = p.Left;
}
}
public void Delete(int pos)
{
if(pos < 0)
{
throw new ArgumentOutOfRangeException("pos");
}
DoublyLinkedListNode p = FindNode(pos);
if(p == null)
{
throw new ArgumentOutOfRangeException("pos");
}
this.Delete(p);
_count --;
}
public void Insert(int pos, object data)
{
if(pos < 0)
{
throw new ArgumentOutOfRangeException("pos");
}
if(pos == 0)
{
DoublyLinkedListNode y = new DoublyLinkedListNode();
y.Data = data;
if(this._first == null)
{
this._first = y;
}
else
{
y.Right = this._first;
this._first.Left = y;
this._first = y;
}
}
else
{
DoublyLinkedListNode p = FindNode(pos);
InsertBefore(p, data);
}
_count ++;
}
public void MoveToFirst(int pos)
{
if(pos < 0 || this._first == null)
{
throw new ArgumentOutOfRangeException("pos"); //// no pos'th
}
if(pos == 0)
{
return;
}
DoublyLinkedListNode q = FindNode(pos);
if(q == null)
{
throw new ArgumentOutOfRangeException("pos");
}
this.Delete(q);
this._first.Left = q;
q.Right = this._first;
q.Left = null;
this._first = q;
}
public void Swap(int posA, int posB)
{
if(posA <0 || posA >= this._count)
{
throw new ArgumentOutOfRangeException("posA");
}
if(posB <0 || posB >= this._count)
{
throw new ArgumentOutOfRangeException("posB");
}
DoublyLinkedListNode p = FindNode(posA);
DoublyLinkedListNode q = FindNode(posB);
this.Swap(p, q);
}
private void Swap(DoublyLinkedListNode p , DoublyLinkedListNode q)
{
if(p == q)
{
return;
}
DoublyLinkedListNode pLeft = p.Left;
DoublyLinkedListNode pRight = p.Right;
DoublyLinkedListNode qLeft = q.Left;
DoublyLinkedListNode qRight = q.Right;
if(qRight == p)
{
p.Left = qLeft;
if(qLeft != null)
{
qLeft.Right = p;
}
if(pRight != null)
{
pRight.Left = q;
}
q.Right = pRight;
q.Left = p;
p.Right = q;
}
else if(pRight == q)
{
q.Left = pLeft;
if(pLeft != null)
{
pLeft.Right = q;
}
if(qRight != null)
{
qRight.Left = p;
}
p.Right = qRight;
p.Left = q;
q.Right = p;
}
else
{
q.Left = pLeft;
if(pLeft != null)
{
pLeft.Right = q;
}
q.Right = pRight;
if(pRight != null)
{
pRight.Left = q;
}
Output(q);
p.Left = qLeft;
if(qLeft != null)
{
qLeft.Right = p;
}
p.Right = qRight;
if(qRight != null)
{
qRight.Left = p;
}
Output(p);
}
if(this._first == p)
{
this._first = q;
}
else if(this._first == q)
{
this._first = p;
}
Console.WriteLine("_first");
Output(this._first);
Console.WriteLine("---------------------");
}
public void Add(object data)
{
DoublyLinkedListNode y = new DoublyLinkedListNode();
y.Data = data;
if(this._first == null)
{
this._first = y;
_count ++;
return;
}
DoublyLinkedListNode current = this._first;
while(current.Right != null)
{
current = current.Right;
}
current.Right = y;
y.Left = current;
_count ++;
}
public void Clear()
{
this._first = null;
_count = 0;
}
private void Output(DoublyLinkedListNode node)
{
if(node == null)
{
return;
}
DoublyLinkedListNode left = node.Left;
DoublyLinkedListNode right = node.Right;
Console.WriteLine("left : " + (left != null ? left.Data.ToString()
: "null"));
Console.WriteLine("node : " + node.Data);
Console.WriteLine("right : " + (right != null ? right.Data.ToStrin
g() : "null"));
Console.WriteLine();
}
public void Output()
{
int count = this.Count;
for(int i=0; i<count; i++)
{
DoublyLinkedListNode node = this.FindNode(i);
this.Output(node);
}
}
public IEnumerator GetEnumerator()
{
return new DoublyLinkedListEnumerator(this);
}
private class DoublyLinkedListNode
{
public object Data;
public DoublyLinkedListNode Left;
public DoublyLinkedListNode Right;
}
private class DoublyLinkedListEnumerator : IEnumerator
{
private DoublyLinkedList _list;
private DoublyLinkedListNode _location;
public DoublyLinkedListEnumerator(DoublyLinkedList list)
{
this._list = list;
}
public bool MoveNext()
{
if(this._location == null)
{
this._location = _list._first;
}
else
{
this._location = this._location.Right;
}
return this._location != null;
}
public void Reset()
{
this._location = _list._first;
}
public object Current
{
get
{
return this._location.Data;
}
}
}
}
}
--
※ 来源:·BBS 水木清华站 smth.org·[FROM: 218.17.75.188]
上一篇
返回上一页
回到目录
回到页首
下一篇
|
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机技术与应用 → 『 Dot NET,C#,ASP,VB 』 → 数据结构双向链表的C#实现
(订阅本版)
2004/11/9 2:25:00
新浪微博
