C# 數(shù)據(jù)結(jié)構(gòu)--單鏈表

什么是單鏈表

　　這兩天看到很多有關(guān)單鏈表的面試題，對單鏈表都不知道是啥的我。經(jīng)過學(xué)習和整理來分享一下啥是單鏈表和單鏈表的一些基本使用方法。最后看些網(wǎng)上有關(guān)單鏈表的面試題代碼實例。

啥是單鏈表?

　　單鏈表是一種鏈式存取的數(shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的。

　　鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構(gòu)成：元素(數(shù)據(jù)元素的映象) +指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)。

　　鏈表的結(jié)點結(jié)構(gòu)：

實例代碼

public class Node<T>{    public T Data { set; get; }          //數(shù)據(jù)域,當前結(jié)點數(shù)據(jù)    public Node<T> Next { set; get; }    //位置域,下一個結(jié)點地址    public Node(T item)    {        this.Data = item;        this.Next = null;    }    public Node()    {        this.Data = default(T);        this.Next = null;    }}

public class LinkList<T>{    public Node<T> Head { set; get; } //單鏈表頭    //構(gòu)造    public LinkList()    {        Head=null;    }    /// <summary>    /// 增加新元素到單鏈表末尾    /// </summary>    public void Append(T item)    {        Node<T> foot = new Node<T>(item);        Node<T> A = new Node<T>();        if (Head == null)        {            Head = foot;            return;        }        A = Head;        while (A.Next != null)        {            A = A.Next;        }        A.Next = foot;    }}

1.如果增加的是頭結(jié)點。直接把數(shù)據(jù)域（Data）給Head，Next為空。因為只有一個頭結(jié)點，沒有對應(yīng)的下結(jié)點。

2.單鏈表是”不走回頭路“，所以每次增加都要從單鏈表的頭開始找到單鏈表最后一個結(jié)點（最后一個結(jié)點就是Next為NULL），然后把最后一個結(jié)點的Next設(shè)置成需增加的結(jié)點,這時要需增加的結(jié)點變身為最后一結(jié)點，他的Next為NULL。

public class LinkList<T>{    public Node<T> Head { set; get; } //單鏈表頭    //構(gòu)造    public LinkList()    {        Head=null;    }    public void Delete(int i)    {        Node<T> A = new Node<T>();        if (i == 1)   //刪除頭        {            A = Head;            Head = Head.Next;            return;        }        Node<T> B = new Node<T>();        B = Head;        int j = 1;        while (B.Next != null && j < i)        {            A = B;            B = B.Next;            j++;        }        if (j == i)        {            A.Next = B.Next;        }    }}

1.如果刪除的是頭結(jié)點，那現(xiàn)在的頭結(jié)點就應(yīng)該是頭結(jié)點的下一結(jié)點。

2.刪除結(jié)點如果不是頭結(jié)點。從單鏈表頭開始查詢要刪除結(jié)點的位置。并記錄刪除的前一結(jié)點值A(chǔ)和所要刪除的結(jié)點B。因為結(jié)點B被刪除了,所以結(jié)點A的Next就應(yīng)該為B的Next。把結(jié)點A的Next設(shè)置為結(jié)點B的Next。

單鏈表類

public class LinkList<T>{    public Node<T> Head { set; get; } //單鏈表頭    //構(gòu)造    public LinkList()    {        Clear();    }    /// <summary>    /// 求單鏈表的長度    /// </summary>    /// <returns></returns>    public int GetLength()    {        Node<T> p = Head;        int length = 0;        while (p != null)        {            p = p.Next;            length++;        }        return length;    }    /// <summary>    /// 判斷單鍵表是否為空    /// </summary>    /// <returns></returns>    public bool IsEmpty()    {        if (Head == null)            return true;        else            return false;    }    /// <summary>    /// 清空單鏈表    /// </summary>    public void Clear()    {        Head = null;    }    /// <summary>    /// 獲得當前位置單鏈表中結(jié)點的值    /// </summary>    /// <param name="i">結(jié)點位置</param>    /// <returns></returns>    public T GetNodeValue(int i)    {        if (IsEmpty() || i<1 || i>GetLength())        {            Console.WriteLine("單鏈表為空或結(jié)點位置有誤！");            return default(T);        }        Node<T> A = new Node<T>();        A = Head;        int j = 1;        while (A.Next!=null && j<i)        {            A = A.Next;            j++;        }        return A.Data;    }    /// <summary>    /// 增加新元素到單鏈表末尾    /// </summary>    public void Append(T item)    {        Node<T> foot = new Node<T>(item);        Node<T> A = new Node<T>();        if (Head == null)        {            Head = foot;            return;        }        A = Head;        while (A.Next != null)        {            A = A.Next;        }        A.Next = foot;    }    /// <summary>    /// 增加單鏈表插入的位置    /// </summary>    /// <param name="item">結(jié)點內(nèi)容</param>    /// <param name="n">結(jié)點插入的位置</param>    public void Insert(T item, int n)    {        if (IsEmpty() || n < 1 || n > GetLength())        {            Console.WriteLine("單鏈表為空或結(jié)點位置有誤！");            return;        }        if (n == 1)  //增加到頭部        {            Node<T> H = new Node<T>(item);            H.Next = Head;            Head = H;            return;        }        Node<T> A = new Node<T>();        Node<T> B = new Node<T>();        B = Head;        int j = 1;        while (B.Next != null && j < n)        {            A = B;            B = B.Next;            j++;        }        if (j==n)        {            Node<T> C = new Node<T>(item);            A.Next = C;            C.Next = B;        }    }    /// <summary>    /// 刪除單鏈表結(jié)點    /// </summary>    /// <param name="i">刪除結(jié)點位置</param>    /// <returns></returns>    public void Delete(int i)    {        if (IsEmpty() || i < 1 || i > GetLength())        {            Console.WriteLine("單鏈表為空或結(jié)點位置有誤！");            return;        }        Node<T> A = new Node<T>();        if (i == 1)   //刪除頭        {            A = Head;            Head = Head.Next;            return;        }        Node<T> B = new Node<T>();        B = Head;        int j = 1;        while (B.Next != null && j < i)        {            A = B;            B = B.Next;            j++;        }        if (j == i)        {            A.Next = B.Next;        }    }    /// <summary>    /// 顯示單鏈表    /// </summary>    public void Dispaly()    {        Node<T> A = new Node<T>();        A = Head;        while (A != null)        {            Console.WriteLine(A.Data);            A = A.Next;        }    }    #region 面試題    /// <summary>    /// 單鏈表反轉(zhuǎn)    /// </summary>    public void Reverse()     {        if (GetLength()==1 || Head==null)        {            return;        }        Node<T> NewNode = null;        Node<T> CurrentNode = Head;        Node<T> TempNode = new Node<T>();        while (CurrentNode!=null)        {            TempNode = CurrentNode.Next;            CurrentNode.Next = NewNode;            NewNode = CurrentNode;            CurrentNode = TempNode;        }        Head = NewNode;        Dispaly();    }    /// <summary>    /// 獲得單鏈表中間值    /// 思路：使用兩個指針，第一個每次走一步，第二個每次走兩步：    /// </summary>    public void GetMiddleValue()    {        Node<T> A = Head;        Node<T> B = Head;        while (B!=null && B.Next!=null)        {            A = A.Next;            B = B.Next.Next;        }        if (B != null) //奇數(shù)        {            Console.WriteLine("奇數(shù):中間值為：{0}", A.Data);        }        else    //偶數(shù)        {            Console.WriteLine("偶數(shù):中間值為：{0}和{1}", A.Data, A.Next.Data);        }    }    #endregion}

調(diào)用實例

static void Main(string[] args){    LinkList<string> link = new LinkList<string>();    link.Append("A");    link.Append("B");    link.Append("C");    link.Append("D");    link.Append("E");    link.Insert("Head", 1);    Console.WriteLine("單鏈表內(nèi)容：");    link.Dispaly();    link.Delete(5);    Console.Write