資料結構線性表—單向連結清單

單向連結清單
           

其實就是一種鍊式存儲的資料結構，它和數組不同，數組的存儲結構就是連續的，且長度是固定的。而連結清單不一樣，它可以是連續的，也可以是不連續的，而且是可以動态擴容的。

連結清單中的資料是以節點的形式表現出來的。結構為：資料+指針

┌───┬───┐

│data│next│

└───┴───┘

　data域–存放結點值的元素。

　next域–存放結點的直接後繼的位址的指針域[指針]。

　自己為了練習，把它敲了一遍，放在下面，有什麼不足的地方希望大家多多指教~~

public class Node<T>//節點類
{
    private Node<T> m_Next;//直接後繼節點
    private T data;//插入進來的元素
    public Node<T> Next
    {
        get
        {
            return m_Next;
        }
        set
        {
            m_Next = value;
        }
    }
    public T Data
    {
        get
        {
            return data;
        }

        set
        {
            data = value;
        }
    }
    public Node()
    {
        m_Next = null;
        data = default(T);
    }
    public Node(T _data)
    {
        data = _data;
        m_Next = null;
    }
}//節點類
public class MyList<T>
{
    private uint length;
    private Node<T> m_head;//頭結點
    private Node<T> m_tail;//尾節點
    public uint Count//判斷連結清單的長度
    {
        get
        {
            return length;
        }
    }
    public bool IsEmpty
    {
        get
        {
            return (m_head == null ? true : false);
        }
    }
    public void Push_List(T _data)
    {
        Node<T> newNode = new Node<T>(_data);
        if (IsEmpty)
        {
            m_head = newNode;
        }
        else
        {
            m_tail.Next = newNode;
        }
        m_tail = newNode;
        ++length;

    }//直接插入的情況
    public bool Push_Front(T _data, uint position)//前插的情況
    {
        if (IsEmpty)
        {
            Console.WriteLine("連結清單為空，不可進行前插操作");
            return false;
        }
        else if (position > length)
        {
            Console.WriteLine("界限超界，無法進行前插操作");
            return false;
        }
        if (position == 0)//成為了頭結點的情況
        {
            Node<T> newNode = new Node<T>(_data);
            newNode.Next = m_head;
            m_head = newNode;
            ++length;
            return true;
        }
        else//除了頭以後的前插
        {
            Node<T> tempNode = m_head;
            Node<T> tempFront = null;
            uint tempIndex = 1;
            while (tempNode.Next != null && tempIndex <= position)
            {
                tempFront = tempNode;
                tempNode = tempNode.Next;
                ++tempIndex;
            }
            //如果找到了相應的位置
            Node<T> newNode = new Node<T>(_data);
            newNode.Next = tempNode;
            tempFront.Next = newNode;

            ++length;
            return true;

        }

    }
    public bool Push_Back(T _data, uint position)//後插的情況
    {
        Node<T> newNode = new Node<T>(_data);
        if (IsEmpty)
        {
            Console.WriteLine("連結清單為空，不可進行後插操作");
            return false;
        }
        else if (position > length)
        {
            Console.WriteLine("連結清單超界，不可進行後插操作");
            return false;
        }
        if (position == 0)
        {
            newNode.Next = m_head.Next;
            m_head.Next = newNode;
            ++length;
            return true;
        }
        else if (position == length - 1)//成為了尾節點的情況
        {
            m_tail.Next = newNode;
            m_tail = newNode;
            m_tail.Next = m_head;
            length++;
            return true;
        }
        else //除了頭和尾的插入
        {
            Node<T> tempNode = m_head;
            uint tempIndex = 1;
            while (tempNode.Next != null && tempIndex <= length)
            {
                tempNode = tempNode.Next;
                ++length;
            }
            tempNode.Next = newNode.Next;
            tempNode.Next = newNode;
            length++;
            return true;
        }
    }
    public T Check_Data(uint _position)
    {
        T clockNode = default(T);
        if (m_head == null)
            Console.WriteLine("連結清單為空，不可進行查詢操作");
        else
        {
            uint tempIndex = 1;
            Node<T> tempNode = m_head;
            while (tempNode.Next != null && tempIndex <= _position)
            {
                tempNode = tempNode.Next;
                ++tempIndex;
            }
            clockNode = tempNode.Data;
        }
        return clockNode;
    }
    public bool Delete(uint position)//删除指定元素
    {
        if (IsEmpty)
        {
            Console.WriteLine("連結清單為空，不能進行删除操作");
            return false;
        }
        else if (position > length)
        {
            Console.WriteLine("輸入下标超出界限，無法進行删除操作");
            return false;
        }
        else
        {
            uint tempIndex = 1;
            Node<T> tempNode = m_head;
            Node<T> clockNode = null;
            while ((tempNode.Next != null && tempIndex < length))
            {
                clockNode = tempNode;
                tempNode = tempNode.Next;
                ++tempIndex;
            }
            clockNode.Next = tempNode.Next;
            if (position == length - 1)
            {
                m_tail = tempNode;
            }
            --length;
        }
        return true;
    }
    public bool Clear()//清除整個表
    {
        if (IsEmpty)
        {
            Console.WriteLine("連結清單已經為空");
            return true;
        }
        else
        {
            Node<T> tempNode = m_head;
            Node<T> frontNode = null;
            uint position = 1;
            while (position <= length)
            {
                frontNode = tempNode;
                tempNode = tempNode.Next;
            }
            return true;
        }
    }

}
           

}