蓝派网(www.lan27.com)-精选网络资源,分享和交流! 文章首页站内搜索在线手册广告代码酷站欣赏万年历
您现在的位置: 蓝派网 >> 文章中心 >> 网络编程 >> .NET >> c#(Csharp) >> 正文

C#数据结构-双向链表

作者:佚名    文章来源:小鸟提升之路    更新时间:2008-11-20 2:19:23
理论基础:

在结点中设两个引用域,一个保存直接前驱结点的地址,叫prev,一个直接后继结点的地址,叫next,这样的链表就是双向链表(Doubly Linked List)。
单击显示全图,Ctrl+滚轮缩放图片
双向链表的结点结构示意图如上,双向链表结点的定义与单链表的结点的定义很相似,因此,双向链表节点类的实现可以参考单链表的节点类。


C#实现:

1接口

引用线性表的接口IListDS<T>

2实现

(1)双向链表节点类,参考单链表的节点类
 
public class DBNode<T>
{
    private T data;              //数据域
    private DBNode<T> next;        //后继
    private DBNode<T> prev;        //前驱
    public T Data
    {
        get { return data; }
        set { data = value; }
    }
    public DBNode<T> Next
    {
        get { return next; }
        set { next = value; }
    }
    public DBNode<T> Prev
    {
        get { return prev; }
        set { prev = value; }
    }
    public DBNode()
    {
        data = default(T);
        prev = null;
        next = null;
    }
    public DBNode(T val)
    {
        data = val;
        next = null;
        prev = null;
    }
}

(2) 双向链表操作类实现

注意:由于双向链表的结点有两个引用,所以,在双向链表中插入和删除结点比单链表要复杂。双向链表中结点的插入分为在结点之前插入和在结点之后插入,插入操作要对四个引用进行操作

同样,删除操作也需要多多注意,其他的操作和单链表类似,不再赘述.
 
public class DBLinkList<T> : IListDS<T>
{
    private DBNode<T> header;

    public DBNode<T> Header
    {

        get { return header; }
        set { header = value; }
    }
    public DBLinkList()
    {
        header = new DBNode<T>();
        header.Next = null;
        header.Prev = null;
    }
    /// <summary>
    /// 获取长度
    /// </summary>
    /// <returns></returns>
    public int GetLength()
    {
        DBNode<T> p = header;
        int len = 0;
        while (p != null)
        {
            ++len;
            p = p.Next;
        }
        return len;
    }
    /// <summary>
    /// 清空操作
    /// </summary>
    public void Clear()
    {
        header = null;
    }
    /// <summary>
    /// 判断线性表是否为空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
        if (header.Data == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    /// <summary>
    /// 查找节点
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    private DBNode<T> FindNode(int i)
    {
        if (IsEmpty())
        {
            Console.Write("list is empty");
            return null;
        }
        if (i < 1)
        {
            Console.Write("Index is error");
            return null;
        }
        DBNode<T> current = new DBNode<T>();
        current = header;
        int j = 1;
        while (current.Next != null && j < i)
        {
            ++j;
            current = current.Next;
        }
        return current;
    }
    /// <summary>
    /// 插入操作,在第i个节点前面
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void Insert(T item, int i)
    {
        DBNode<T> current = FindNode(i);
        DBNode<T> newNode = new DBNode<T>(item);
        if (current != null)
        {
            current.Prev.Next = newNode;
            newNode.Next = current;
            newNode.Prev = current.Prev;
            current.Prev = newNode;
        }
        else
        {
            Console.Write("the node is not exist!");
        }
    }
    /// <summary>
    /// 插入操作,在第i个节点后面插入item
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void InsertBack(T item, int i)
    {
        DBNode<T> current = FindNode(i);
        DBNode<T> newNode = new DBNode<T>(item);
        if (current != null)
        {
            current.Next.Prev = newNode;
            newNode.Prev = current;
            newNode.Next = current.Next;
            current.Next = newNode;
        }
        else
        {
            Console.Write("the node is not exist!");
        }
    }
    /// <summary>
    /// 附加操作,线性表未满,将值为item的新元素添加到末尾
    /// </summary>
    /// <param name="item"></param>
    public void Append(T item)
    {
        DBNode<T> newNode = new DBNode<T>(item);
        DBNode<T> p = new DBNode<T>();
        if (header == null)
        {
            header = newNode;
            return;
        }
        p = header;

        while (p.Next != null)
        {
            p = p.Next;
        }
        p.Next = newNode;
    }

    /// <summary>
    /// 删除操作
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T Delete(int i)
    {
        DBNode<T> current = FindNode(i);
        if (current != null)
        {
            current.Prev.Next = current.Next;
            current.Next.Prev = current.Prev;
            current.Prev = null;
            current.Next = null;
            return current.Data;
        }
        else
        {
            Console.Write("the node is not exist!");
            return default(T);
        }
    }
    /// <summary>
    /// 取表元
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T GetElem(int i)
    {
        DBNode<T> current = FindNode(i);
        if (current != null)
        {
            return current.Data;
        }
        else
        {
            Console.Write("the node is not exist!");
            return default(T);
        }
    }

    /// <summary>
    /// 按值查找
    /// </summary>
    /// <param name="value"></param>
    /// <returns>-1:链表或参数异常;0:节点不存在;1:值代表的位置</returns>
    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Console.Write("list is empty");
            return -1;
        }
        if (value == null)
        {
            Console.Write("value is empty");
            return -1;
        }
        DBNode<T> current = new DBNode<T>();
        current = header;
        int result = 0;

        while (current.Next != null)
        {
            if (current.Data.Equals(value))
            {
                result = 1;
            }
        }
        return result;
    }
}

此外,循环链表的基本操作与单链表大体相同,只是判断链表结束的条件并不是判断结点的引用域是否为空,

而是判断结点的引用域是否为头引用,其它没有较大的变化,有兴趣的朋友可以写写。

路曼曼其修远兮,吾将上下而求索
发表评论】【打印此文】【关闭窗口】【点击数:
★好玩的休闲小游戏★