<em id="hanht"></em>

    <dd id="hanht"></dd>

    <em id="hanht"><acronym id="hanht"></acronym></em>
    
    <button id="hanht"></button>
    <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>

    首頁 > 學院 > 邏輯算法 > 正文

    算法系列15天速成 第八天 線性表【下】

    2020-10-08 16:14:32
    字體:
    來源:轉載
    供稿:網友

    一:線性表的簡單回顧

           上一篇跟大家聊過“線性表"順序存儲,通過實驗,大家也知道,如果我每次向順序表的頭部插入元素,都會引起痙攣,效率比較低下,第二點我們用順序存儲時,容易受到長度的限制,反之就會造成空間資源的浪費。

    二:鏈表

          對于順序表存在的若干問題,鏈表都給出了相應的解決方案。

    1. 概念:其實鏈表的“每個節點”都包含一個”數據域“和”指針域“。

                ”數據域“中包含當前的數據。

                ”指針域“中包含下一個節點的指針。

                ”頭指針”也就是head,指向頭結點數據。

                “末節點“作為單向鏈表,因為是最后一個節點,通常設置指針域為null。

    代碼段如下:

    復制代碼 代碼如下:

    #region 鏈表節點的數據結構
    /// <summary>
    /// 鏈表節點的數據結構
    /// </summary>
        public class Node<T>
        {
     7/// <summary>
    /// 節點的數據域
    /// </summary>
            public T data;

    /// <summary>
    /// 節點的指針域
    /// </summary>
            public Node<T> next;
        }
        #endregion

    2.常用操作:

        鏈表的常用操作一般有:

               ①添加節點到鏈接尾,②添加節點到鏈表頭,③插入節點。

               ④刪除節點,⑤按關鍵字查找節點,⑥取鏈表長度。

    <1> 添加節點到鏈接尾:

              前面已經說過,鏈表是采用指針來指向下一個元素,所以說要想找到鏈表最后一個節點,必須從頭指針開始一步一步向后找,少不了一個for循環,所以時間復雜度為O(N)。

    代碼段如下:

    復制代碼 代碼如下:

    #region 將節點添加到鏈表的末尾
            /// <summary>
    /// 將節點添加到鏈表的末尾
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListAddEnd<T>(Node<T> head, T data)
            {
                Node<T> node = new Node<T>();

                node.data = data;
                node.next = null;

                ///說明是一個空鏈表
                if (head == null)
                {
                    head = node;
                    return head;
                }

                //獲取當前鏈表的最后一個節點
                ChainListGetLast(head).next = node;

                return head;
            }
    #endregion
    #region 得到當前鏈表的最后一個節點
            /// <summary>
    /// 得到當前鏈表的最后一個節點
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <returns></returns>
            public Node<T> ChainListGetLast<T>(Node<T> head)
            {
                if (head.next == null)
                    return head;
                return ChainListGetLast(head.next);
            }
            #endregion

    <2> 添加節點到鏈表頭:

              大家現在都知道,鏈表是采用指針指向的,要想將元素插入鏈表頭,其實還是很簡單的,

          思想就是:① 將head的next指針給新增節點的next。②將整個新增節點給head的next。

          所以可以看出,此種添加的時間復雜度為O(1)。

    效果圖:

    代碼段如下:

    復制代碼 代碼如下:

    1#region 將節點添加到鏈表的開頭
    /// <summary>
    /// 將節點添加到鏈表的開頭
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="chainList"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListAddFirst<T>(Node<T> head, T data)
            {
                Node<T> node = new Node<T>();

                node.data = data;
                node.next = head;

                head = node;

                return head;

            }
            #endregion

    <3> 插入節點:

               其實這個思想跟插入到”首節點“是一個模式,不過多了一步就是要找到當前節點的操作。然后找到

          這個節點的花費是O(N)。上圖上代碼,大家一看就明白。

    效果圖:

    代碼段:

    復制代碼 代碼如下:

    #region 將節點插入到指定位置
    /// <summary>
    /// 將節點插入到指定位置
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <param name="currentNode"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListInsert<T, W>(Node<T> head, string key, Func<T, W> where, T data) where W : IComparable
            {
                if (head == null)
                    return null;

                if (where(head.data).CompareTo(key) == 0)
                {
                    Node<T> node = new Node<T>();

                    node.data = data;

                    node.next = head.next;

                    head.next = node;
                }

                ChainListInsert(head.next, key, where, data);

                return head;
            }
            #endregion

    <4> 刪除節點:

            這個也比較簡單,不解釋,圖跟代碼更具有說服力,口頭表達反而讓人一頭霧水。
            當然時間復雜度就為O(N),N是來自于查找到要刪除的節點。

    效果圖:

    代碼段:

    復制代碼 代碼如下:

    #region 將指定關鍵字的節點刪除
            /// <summary>
    /// 將指定關鍵字的節點刪除
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <typeparam name="W"></typeparam>
    /// <param name="head"></param>
    /// <param name="key"></param>
    /// <param name="where"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListDelete<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
            {
                if (head == null)
                    return null;

                //這是針對只有一個節點的解決方案
                if (where(head.data).CompareTo(key) == 0)
                {
                    if (head.next != null)
                        head = head.next;
                    else
                        return head = null;
                }
                else
                {
                    //判斷一下此節點是否是要刪除的節點的前一節點
                    while (head.next != null && where(head.next.data).CompareTo(key) == 0)
                    {
                        //將刪除節點的next域指向前一節點
                        head.next = head.next.next;
                    }
                }

                ChainListDelete(head.next, key, where);

                return head;
            }
            #endregion

    <5> 按關鍵字查找節點:

             這個思想已經包含到“插入節點”和“刪除節點”的具體運用中的,其時間復雜度為O(N)。

    代碼段:

    復制代碼 代碼如下:

    #region 通過關鍵字查找指定的節點
            /// <summary>
    /// 通過關鍵字查找指定的節點
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <typeparam name="W"></typeparam>
    /// <param name="head"></param>
    /// <param name="key"></param>
    /// <param name="where"></param>
    /// <returns></returns>
            public Node<T> ChainListFindByKey<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
            {
                if (head == null)
                    return null;

                if (where(head.data).CompareTo(key) == 0)
                    return head;

                return ChainListFindByKey<T, W>(head.next, key, where);
            }
            #endregion

    <6> 取鏈表長度:

              在單鏈表的操作中,取鏈表長度還是比較糾結的,因為他不像順序表那樣是在內存中連續存儲的,

          因此我們就糾結的遍歷一下鏈表的總長度。時間復雜度為O(N)。

    代碼段:

    復制代碼 代碼如下:

    #region 獲取鏈表的長度
            /// <summary>
    ///// 獲取鏈表的長度
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <returns></returns>
            public int ChanListLength<T>(Node<T> head)
            {
                int count = 0;

                while (head != null)
                {
                    ++count;
                    head = head.next;
                }

                return count;
            }
            #endregion

    好了,最后上一下總的運行代碼:

    復制代碼 代碼如下:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace ChainList
    {
        class Program
        {
            static void Main(string[] args)
            {
                ChainList chainList = new ChainList();

                Node<Student> node = null;

                Console.WriteLine("將三條數據添加到鏈表的尾部:/n");

                //將數據添加到鏈表的尾部
                node = chainList.ChainListAddEnd(node, new Student() { ID = 2, Name = "hxc520", Age = 23 });
                node = chainList.ChainListAddEnd(node, new Student() { ID = 3, Name = "博客園", Age = 33 });
                node = chainList.ChainListAddEnd(node, new Student() { ID = 5, Name = "一線碼農", Age = 23 });

                Dispaly(node);

                Console.WriteLine("將ID=1的數據插入到鏈表開頭:/n");

                //將ID=1的數據插入到鏈表開頭
                node = chainList.ChainListAddFirst(node, new Student() { ID = 1, Name = "i can fly", Age = 23 });

                Dispaly(node);

                Console.WriteLine("查找Name=“一線碼農”的節點/n");

                //查找Name=“一線碼農”的節點
                var result = chainList.ChainListFindByKey(node, "一線碼農", i => i.Name);

                DisplaySingle(node);

                Console.WriteLine("將”ID=4“的實體插入到“博客園”這個節點的之后/n");

                //將”ID=4“的實體插入到"博客園"這個節點的之后
                node = chainList.ChainListInsert(node, "博客園", i => i.Name, new Student() { ID = 4, Name = "51cto", Age = 30 });

                Dispaly(node);

                Console.WriteLine("刪除Name=‘51cto‘的節點數據/n");

                //刪除Name=‘51cto‘的節點數據
                node = chainList.ChainListDelete(node, "51cto", i => i.Name);

                Dispaly(node);

                Console.WriteLine("獲取鏈表的個數:" + chainList.ChanListLength(node));
            }

            //輸出數據
            public static void Dispaly(Node<Student> head)
            {
                Console.WriteLine("******************* 鏈表數據如下 *******************");
                var tempNode = head;

                while (tempNode != null)
                {
                    Console.WriteLine("ID:" + tempNode.data.ID + ", Name:" + tempNode.data.Name + ",Age:" + tempNode.data.Age);
                    tempNode = tempNode.next;
                }

                Console.WriteLine("******************* 鏈表數據展示完畢 *******************/n");
            }

            //展示當前節點數據
            public static void DisplaySingle(Node<Student> head)
            {
                if (head != null)
                    Console.WriteLine("ID:" + head.data.ID + ", Name:" + head.data.Name + ",Age:" + head.data.Age);
                else
                    Console.WriteLine("未查找到數據!");
            }
        }

        #region 學生數據實體
        /// <summary>
    /// 學生數據實體
    /// </summary>
        public class Student
        {
            public int ID { get; set; }

            public string Name { get; set; }

            public int Age { get; set; }
        }
        #endregion

        #region 鏈表節點的數據結構
        /// <summary>
    /// 鏈表節點的數據結構
    /// </summary>
        public class Node<T>
        {
            /// <summary>
    /// 節點的數據域
    /// </summary>
            public T data;

            /// <summary>
    /// 節點的指針域
    /// </summary>
            public Node<T> next;
        }
        #endregion

        #region 鏈表的相關操作
        /// <summary>
    /// 鏈表的相關操作
    /// </summary>
        public class ChainList
        {
            #region 將節點添加到鏈表的末尾
            /// <summary>
    /// 將節點添加到鏈表的末尾
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListAddEnd<T>(Node<T> head, T data)
            {
                Node<T> node = new Node<T>();

                node.data = data;
                node.next = null;

                ///說明是一個空鏈表
                if (head == null)
                {
                    head = node;
                    return head;
                }

                //獲取當前鏈表的最后一個節點
                ChainListGetLast(head).next = node;

                return head;
            }
            #endregion

            #region 將節點添加到鏈表的開頭
            /// <summary>
    /// 將節點添加到鏈表的開頭
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="chainList"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListAddFirst<T>(Node<T> head, T data)
            {
                Node<T> node = new Node<T>();

                node.data = data;
                node.next = head;

                head = node;

                return head;

            }
            #endregion

            #region 將節點插入到指定位置
            /// <summary>
    /// 將節點插入到指定位置
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <param name="currentNode"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListInsert<T, W>(Node<T> head, string key, Func<T, W> where, T data) where W : IComparable
            {
                if (head == null)
                    return null;

                if (where(head.data).CompareTo(key) == 0)
                {
                    Node<T> node = new Node<T>();

                    node.data = data;

                    node.next = head.next;

                    head.next = node;
                }

                ChainListInsert(head.next, key, where, data);

                return head;
            }
            #endregion

            #region 將指定關鍵字的節點刪除
            /// <summary>
    /// 將指定關鍵字的節點刪除
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <typeparam name="W"></typeparam>
    /// <param name="head"></param>
    /// <param name="key"></param>
    /// <param name="where"></param>
    /// <param name="data"></param>
    /// <returns></returns>
            public Node<T> ChainListDelete<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
            {
                if (head == null)
                    return null;

                //這是針對只有一個節點的解決方案
                if (where(head.data).CompareTo(key) == 0)
                {
                    if (head.next != null)
                        head = head.next;
                    else
                        return head = null;
                }
                else
                {
                    //判斷一下此節點是否是要刪除的節點的前一節點
                    if (head.next != null && where(head.next.data).CompareTo(key) == 0)
                    {
                        //將刪除節點的next域指向前一節點
                        head.next = head.next.next;
                    }
                }

                ChainListDelete(head.next, key, where);

                return head;
            }
            #endregion

            #region 通過關鍵字查找指定的節點
            /// <summary>
    /// 通過關鍵字查找指定的節點
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <typeparam name="W"></typeparam>
    /// <param name="head"></param>
    /// <param name="key"></param>
    /// <param name="where"></param>
    /// <returns></returns>
            public Node<T> ChainListFindByKey<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
            {
                if (head == null)
                    return null;

                if (where(head.data).CompareTo(key) == 0)
                    return head;

                return ChainListFindByKey<T, W>(head.next, key, where);
            }
            #endregion

            #region 獲取鏈表的長度
            /// <summary>
    ///// 獲取鏈表的長度
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <returns></returns>
            public int ChanListLength<T>(Node<T> head)
            {
                int count = 0;

                while (head != null)
                {
                    ++count;
                    head = head.next;
                }

                return count;
            }
            #endregion

            #region 得到當前鏈表的最后一個節點
            /// <summary>
    /// 得到當前鏈表的最后一個節點
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="head"></param>
    /// <returns></returns>
            public Node<T> ChainListGetLast<T>(Node<T> head)
            {
                if (head.next == null)
                    return head;
                return ChainListGetLast(head.next);
            }
            #endregion

        }
        #endregion
    }

    運行結果:

    當然,單鏈表操作中有很多是O(N)的操作,這給我們帶來了尷尬的局面,所以就有了很多的優化方案,比如:雙向鏈表,循環鏈表。靜態鏈表等等,這些希望大家在懂得單鏈表的情況下待深一步的研究。

    發表評論 共有條評論
    用戶名: 密碼:
    驗證碼: 匿名發表
    一级特黄大片欧美久久久久_一本一道久久综合狠狠老_JLZZ日本人年轻护士_欧美男男作爱VIDEOS可播放
      <em id="hanht"></em>

      <dd id="hanht"></dd>

      <em id="hanht"><acronym id="hanht"></acronym></em>
      
      <button id="hanht"></button>
      <rp id="hanht"><object id="hanht"><blockquote id="hanht"></blockquote></object></rp><em id="hanht"></em>