C#資料結構－連結清單

理論基礎：

連結清單是用一組任意的存儲單元來存儲線性表中的資料元素。

如果結點的引用域隻存儲該結點直接後繼結點的存儲位址，則該連結清單叫單連結清單(Singly Linked List)。

單連結清單由頭引用H唯一确定。頭引用指向單連結清單的第一個結點，也就是把單連結清單第一個結點的位址放在H中。

C#實作：

1接口

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

2實作

<script language="JavaScript" src="http://book.book560.com/ads/ads728x15.js" type="text/javascript"></script>

首先，必須定義一個單連結清單的節點類

public class Node<T>

{

    private T data;        //資料域

    private Node<T> next;  //引用域

    public Node(T val)

    {

        data = val;

        next = null;

    }

    public Node()

    {

        data = default(T);

        next = null;

    }

    public T Data

    {

        get { return data; }

        set { data = value; }

    }

    public Node<T> Next

    {

        get { return next; }

        set { next = value; }

    }

}

實作主體類

<script language="JavaScript" src="http://book.book560.com/ads/ads728x15.js" type="text/javascript"></script>

Append,Insert,InsertBack三個方法實質上都是插入操作，可以考慮用overload或者override來實作，有興趣的朋友試試。

public class LinkList<T> : IListDS<T>

{

    private Node<T> head;

    public Node<T> Head

    {

        get { return head; }

        set { head = value; }

    }

    public LinkList()

    {

        head = null;

    }

    /// <summary>

    /// 擷取長度

    /// </summary>

    /// <returns></returns>

    public int GetLength()

    {

        Node<T> p = head;

        int len = 0;

        while (p != null)

        {

            ++len;

            p = p.Next;

        }

        return len;

    }

    /// <summary>

    /// 清空操作

    /// </summary>

    public void Clear()

    {

        head = null;

    }

    /// <summary>

    /// 判斷線性表是否為空

    /// </summary>

    /// <returns></returns>

    public bool IsEmpty()

    {

        if (head == null)

        {

            return true;

        }

        else

        {

            return false;

        }

    }

    /// <summary>

    /// 附加操作,線性表未滿，将值為item的新元素添加到末尾

    /// </summary>

    /// <param name="item"></param>

    public void Append(T item)

    {

        Node<T> newNode = new Node<T>(item);  //根據元素建立新的節點

        Node<T> node = new Node<T>();

        if (head == null)

        {

            head = newNode;

            return;

        }

        node = head;

        while (node.Next != null)

        {

            node = node.Next;

        }

        node.Next = newNode;

    }

    /// <summary>

    /// 尋找節點

    /// </summary>

    /// <param name="i"></param>

    /// <returns></returns>

    public Node<T> FindNode(int i)

    {

        if (IsEmpty())

        {

            Console.Write("List is empty");

            return null;

        }

        if (i < 1)

        {

            Console.Write("Index is error");

            return null;

        }

        Node<T> current = head;

        int j = 1;

        while (current.Next != null && j < i)

        {

            ++j;

            current = current.Next;

        }

        return current;

    }

    /// <summary>

    /// 插入操作,在第i個節點前面插入item

    /// </summary>

    /// <param name="item"></param>

    /// <param name="i"></param>

    public void Insert(T item, int i)

    {

        Node<T> newNode = new Node<T>(item);

        Node<T> node = new Node<T>();

        Node<T> current = FindNode(i);

        if (current != null)

        {

            node = current;       //對目标節點備份

            newNode.Next = current;

            node.Next = newNode;

        }

    }

    /// <summary>

    /// 插入操作,在第i個節點後面插入item

    /// </summary>

    /// <param name="item"></param>

    /// <param name="i"></param>

    public void InsertBack(T item, int i)

    {

        Node<T> newNode = new Node<T>(item);

        Node<T> current = FindNode(i);

        if (current != null)

        {

            newNode.Next = current.Next;

            current.Next = newNode;

        }

    }

    /// <summary>

    /// 删除操作

    /// </summary>

    /// <param name="i"></param>

    /// <returns></returns>

    public T Delete(int i)

    {

        Node<T> current = FindNode(i);

        Node<T> node = new Node<T>();

        if (current != null)

        {

            node = current;   //對目标節點備份

            node.Next = current.Next;

            return current.Data;

        }

        else

        {

            Console.Write("the node is not exist!");

            return default(T);

        }

    }