[软件工程师][转]C#数据结构篇一(链表类)

xindongfang · 发表于 2006-11-8 17:55:43

  新东方IT职业教育中心

作者：寒羽狼（Dark_Slaer_Tang)

最近，马子跑了，你说女人老是容易翻脸。。。，看来做程序员必定要 “茕茕孑立，行影相吊”悲惨命运了。还是老老实实编程吧，我发现用c# 编一些数据接结构的类也瞒不错的，于是想把数据结构的算法，用C#重写一遍，打发无聊的时光，下面是数据结构中的链表的实现。

首先定义结点类型，定义了，前一个指针域，后一个指针域，如下：

using System;

namespace List
{
/// <summary>
/// Summary description for ListNode.
/// </summary>

// 结点类

public class ListNode
{
  public ListNode(int NewValue)
  {
  Value=NewValue;
  }

  /// <summary>
  /// 前一个
  /// </summary>

  public ListNode Previous;

  /// <summary>
  /// 后一个
  /// </summary>

  public ListNode Next;

  /// <summary>
  /// 值
  /// </summary>

  public int Value;
}
}

using System;

namespace List
{

/// <summary>
/// 链表类
/// </summary>

定义结点之后，开始类线性表的操作编程了.在LIST 类中,采用了，Head ,Tail,  Current，三个指针，使用Append ，MoveFrist,MovePrevious，MoveNext,MoveLast ,Delete,InsertAscending,InsertUnAscending ,Clear 实现移动，添加，[wiki]删除[/wiki],升序插入，降序插入，清空链表操作，GetCurrentValue（）方法取得当前的值。

public class Clist
{
  public Clist()

  {

  //构造函数

  //初始化

  ListCountValue=0;

  Head=null;

  Tail=null;

  }

  /// <summary>
  /// 头指针
  /// </summary>

  private ListNode Head;

  /// <summary>
  /// 尾指针
  /// </summary>

  private ListNode Tail;

  /// <summary>
  /// 当前指针
  /// </summary>

  private ListNode Current;

  /// <summary>
  /// 链表数据的个数
  /// </summary>

  private int ListCountValue;

  /// <summary>
  /// 尾部添加数据
  /// </summary>

  public void Append(int DataValue )
  {
  ListNode NewNode=new ListNode( DataValue);

  if (IsNull())

  //如果头指针为空

  {
Head=NewNode;

Tail=NewNode;

  }
  else
  {
Tail.Next =NewNode;

NewNode.Previous =Tail;

Tail=NewNode;

  }

  Current=NewNode;

  //链表数据个数加一

  ListCountValue+=1;

  }

  /// <summary>
  /// 删除当前的数据
  /// </summary>

  public void Delete()
  {
  //若为空链表

  if ( ! IsNull())
  {
//若删除头

if (IsBof())
{
Head=Current.Next ;

Current=Head;

ListCountValue-=1;

return;
}

//若删除尾

if (IsEof())
{
Tail=Current.Previous ;

Current=Tail;

ListCountValue-=1;

return;
}

//若删除中间数据

Current.Previous.Next =Current.Next ;

Current=Current.Previous ;

ListCountValue-=1;

return;
  }

  }

  /// <summary>
  /// 向后移动一个数据
  /// </summary>

  public void MoveNext()
  {
if (! IsEof()) Current=Current.Next ;
  }
  /// <summary>
  /// 向前移动一个数据
  /// </summary>

  public void MovePrevious()
  {
  if (!IsBof()) Current=Current.Previous  ;
  }

  /// <summary>
  /// 移动到第一个数据
  /// </summary>

  public void MoveFrist()
  {
Current=Head;
  }

  /// <summary>
  /// 移动到最后一个数据
  /// </summary>

  public void MoveLast()
  {
  Current=Tail;
  }

  /// <summary>
  /// 判断是否为空链表
  /// </summary>

  public bool IsNull()
  {
  if (ListCountValue==0)
  return true;

  return false;
  }

  /// <summary>
  /// 判断是否为到达尾部
  /// </summary>

  public bool IsEof()
  {
  if( Current  ==Tail )
  return true;

  return false;
  }

  /// <summary>
  /// 判断是否为到达头部
  /// </summary>


  public bool IsBof()
  {
  if( Current ==Head)
return true;

return false;

  }

  public int GetCurrentValue()
  {

  return Current.Value ;

  }

  /// <summary>
  /// 取得链表的数据个数
  /// </summary>

  public int ListCount
  {
  get
  {
return ListCountValue;
  }
  }

  /// <summary>
  /// 清空链表
  /// </summary>

  public void Clear()
  {
  MoveFrist();
  while (!IsNull())
  {
//若不为空链表,从尾部删除

Delete();

  }
  }

  /// <summary>
  /// 在当前位置前插入数据
  /// </summary>

  public void Insert(int DataValue)

  {
  ListNode NewNode=new  ListNode (DataValue);
  if(IsNull())
  {
//为空表，则添加

Append(DataValue);

return;

  }

  if (IsBof())
  {
      //为头部插入

NewNode.Next =Head;

Head.Previous =NewNode;

Head=NewNode;

Current=Head;

ListCountValue+=1;

return;
  }

  //中间插入


  NewNode.Next =Current;

  NewNode.Previous =Current.Previous ;

  Current.Previous.Next =NewNode;

  Current.Previous =NewNode;

  Current=NewNode;

  ListCountValue+=1;

  }

  /// <summary>
  /// 进行升序插入
  /// </summary>

  public void InsertAscending(int InsertValue)
  {
      //参数：InsertValue 插入的数据


      //为空链表

  if (IsNull())
  {
//添加

Append(InsertValue);

return;

  }

      //移动到头

      MoveFrist();

  if ((InsertValue<GetCurrentValue()))
{
//满足条件，则插入，退出

Insert(InsertValue);

return;

  }

while(true)

  {

if (InsertValue<GetCurrentValue())
{

//满族条件，则插入，退出

Insert(InsertValue);

break;

}

if (IsEof())
{
//尾部添加

Append(InsertValue);

break;

}

         //移动到下一个指针

MoveNext();

  }
}

  /// <summary>
  /// 进行降序插入
  /// </summary>

  public void InsertUnAscending(int InsertValue)
  {
  //参数：InsertValue 插入的数据


  //为空链表

  if (IsNull())
  {
//添加

Append(InsertValue);

return;

  }

  //移动到头

  MoveFrist();

  if (InsertValue>GetCurrentValue())
  {
//满足条件，则插入，退出

Insert(InsertValue);

return;

  }

  while(true)

  {

if (InsertValue>GetCurrentValue())
{

//满族条件，则插入，退出

Insert(InsertValue);

break;

}

if (IsEof())
{
//尾部添加

Append(InsertValue);

break;

}

//移动到下一个指针

MoveNext();

  }
  }
}
}

好了，一个简单的链表类实现了，当然还有许多的功能，可以根据自己的需要添加就好了。TO BE CONTINUE 。

登录/注册后可看大图

广州新东方IT职业教育培训--软件工程师,网络/网站工程师,电脑美术设计师,nit-pro全国计算机技能认证考试