日韩精品一区二区亚州AV,无码色色

一：線性表的簡(jiǎn)單回顧

上一篇跟大家聊過(guò)“線性表"順序存儲(chǔ)，通過(guò)實(shí)驗(yàn)，大家也知道，如果我每次向順序表的頭部插入元素，都會(huì)引起痙攣，效率比較低下，第二點(diǎn)我們用順序存儲(chǔ)時(shí)，容易受到長(zhǎng)度的限制，反之就會(huì)造成空間資源的浪費(fèi)。

二：鏈表

對(duì)于順序表存在的若干問(wèn)題，鏈表都給出了相應(yīng)的解決方案。

1. 概念：其實(shí)鏈表的“每個(gè)節(jié)點(diǎn)”都包含一個(gè)”數(shù)據(jù)域“和”指針域“。

”數(shù)據(jù)域“中包含當(dāng)前的數(shù)據(jù)。

”指針域“中包含下一個(gè)節(jié)點(diǎn)的指針。

”頭指針”也就是head，指向頭結(jié)點(diǎn)數(shù)據(jù)。

“末節(jié)點(diǎn)“作為單向鏈表，因?yàn)槭亲詈笠粋€(gè)節(jié)點(diǎn)，通常設(shè)置指針域?yàn)閚ull。

代碼段如下：

復(fù)制代碼代碼如下:

#region 鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
/// summary>
/// 鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
    public class NodeT>
    {
7/// summary>
/// 節(jié)點(diǎn)的數(shù)據(jù)域
/// /summary>
        public T data;

/// summary>
/// 節(jié)點(diǎn)的指針域
/// /summary>
        public NodeT> next;
    }
    #endregion

2.常用操作：

鏈表的常用操作一般有：

①添加節(jié)點(diǎn)到鏈接尾，②添加節(jié)點(diǎn)到鏈表頭，③插入節(jié)點(diǎn)。

④刪除節(jié)點(diǎn)，⑤按關(guān)鍵字查找節(jié)點(diǎn)，⑥取鏈表長(zhǎng)度。

1> 添加節(jié)點(diǎn)到鏈接尾：

前面已經(jīng)說(shuō)過(guò)，鏈表是采用指針來(lái)指向下一個(gè)元素，所以說(shuō)要想找到鏈表最后一個(gè)節(jié)點(diǎn)，必須從頭指針開(kāi)始一步一步向后找,少不了一個(gè)for循環(huán)，所以時(shí)間復(fù)雜度為O(N)。

代碼段如下：

復(fù)制代碼代碼如下:

#region 將節(jié)點(diǎn)添加到鏈表的末尾
        /// summary>
/// 將節(jié)點(diǎn)添加到鏈表的末尾
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="head">/param>
/// param name="data">/param>
/// returns>/returns>
        public NodeT> ChainListAddEndT>(NodeT> head, T data)
        {
            NodeT> node = new NodeT>();

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

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

//獲取當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)
ChainListGetLast(head).next = node;

            return head;
        }
#endregion
#region 得到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)
        /// summary>
/// 得到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="head">/param>
/// returns>/returns>
        public NodeT> ChainListGetLastT>(NodeT> head)
        {
            if (head.next == null)
                return head;
            return ChainListGetLast(head.next);
        }
        #endregion

2> 添加節(jié)點(diǎn)到鏈表頭:

大家現(xiàn)在都知道，鏈表是采用指針指向的，要想將元素插入鏈表頭，其實(shí)還是很簡(jiǎn)單的，

思想就是：① 將head的next指針給新增節(jié)點(diǎn)的next。②將整個(gè)新增節(jié)點(diǎn)給head的next。

所以可以看出，此種添加的時(shí)間復(fù)雜度為O(1)。

效果圖：

代碼段如下：

復(fù)制代碼代碼如下:

1#region 將節(jié)點(diǎn)添加到鏈表的開(kāi)頭
/// summary>
/// 將節(jié)點(diǎn)添加到鏈表的開(kāi)頭
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="chainList">/param>
/// param name="data">/param>
/// returns>/returns>
        public NodeT> ChainListAddFirstT>(NodeT> head, T data)
        {
            NodeT> node = new NodeT>();

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

head = node;

return head;

}
#endregion

3> 插入節(jié)點(diǎn):

其實(shí)這個(gè)思想跟插入到”首節(jié)點(diǎn)“是一個(gè)模式，不過(guò)多了一步就是要找到當(dāng)前節(jié)點(diǎn)的操作。然后找到

這個(gè)節(jié)點(diǎn)的花費(fèi)是O(N）。上圖上代碼，大家一看就明白。

效果圖：

代碼段：

復(fù)制代碼代碼如下:

#region 將節(jié)點(diǎn)插入到指定位置
/// summary>
/// 將節(jié)點(diǎn)插入到指定位置
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="head">/param>
/// param name="currentNode">/param>
/// param name="data">/param>
/// returns>/returns>
        public NodeT> ChainListInsertT, W>(NodeT> head, string key, FuncT, W> where, T data) where W : IComparable
        {
            if (head == null)
                return null;

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

node.data = data;

node.next = head.next;

head.next = node;
}

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

            return head;
        }
        #endregion

4> 刪除節(jié)點(diǎn):

這個(gè)也比較簡(jiǎn)單，不解釋，圖跟代碼更具有說(shuō)服力，口頭表達(dá)反而讓人一頭霧水。
當(dāng)然時(shí)間復(fù)雜度就為O(N)，N是來(lái)自于查找到要?jiǎng)h除的節(jié)點(diǎn)。

效果圖：

代碼段：

復(fù)制代碼代碼如下:

#region 將指定關(guān)鍵字的節(jié)點(diǎn)刪除
        /// summary>
/// 將指定關(guān)鍵字的節(jié)點(diǎn)刪除
/// /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 NodeT> ChainListDeleteT, W>(NodeT> head, string key, FuncT, W> where) where W : IComparable
        {
            if (head == null)
                return null;

            //這是針對(duì)只有一個(gè)節(jié)點(diǎn)的解決方案
            if (where(head.data).CompareTo(key) == 0)
            {
                if (head.next != null)
                    head = head.next;
                else
                    return head = null;
            }
            else
            {
                //判斷一下此節(jié)點(diǎn)是否是要?jiǎng)h除的節(jié)點(diǎn)的前一節(jié)點(diǎn)
                while (head.next != null where(head.next.data).CompareTo(key) == 0)
                {
                    //將刪除節(jié)點(diǎn)的next域指向前一節(jié)點(diǎn)
                    head.next = head.next.next;
                }
            }

ChainListDelete(head.next, key, where);

            return head;
        }
        #endregion

5> 按關(guān)鍵字查找節(jié)點(diǎn)：

這個(gè)思想已經(jīng)包含到“插入節(jié)點(diǎn)”和“刪除節(jié)點(diǎn)”的具體運(yùn)用中的，其時(shí)間復(fù)雜度為O(N)。

代碼段：

復(fù)制代碼代碼如下:

#region 通過(guò)關(guān)鍵字查找指定的節(jié)點(diǎn)
        /// summary>
/// 通過(guò)關(guān)鍵字查找指定的節(jié)點(diǎn)
/// /summary>
/// typeparam name="T">/typeparam>
/// typeparam name="W">/typeparam>
/// param name="head">/param>
/// param name="key">/param>
/// param name="where">/param>
/// returns>/returns>
        public NodeT> ChainListFindByKeyT, W>(NodeT> head, string key, FuncT, W> where) where W : IComparable
        {
            if (head == null)
                return null;

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

            return ChainListFindByKeyT, W>(head.next, key, where);
        }
        #endregion

6> 取鏈表長(zhǎng)度:

在單鏈表的操作中，取鏈表長(zhǎng)度還是比較糾結(jié)的，因?yàn)樗幌耥樞虮砟菢邮窃趦?nèi)存中連續(xù)存儲(chǔ)的，

因此我們就糾結(jié)的遍歷一下鏈表的總長(zhǎng)度。時(shí)間復(fù)雜度為O(N)。

代碼段：

復(fù)制代碼代碼如下:

#region 獲取鏈表的長(zhǎng)度
        /// summary>
///// 獲取鏈表的長(zhǎng)度
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="head">/param>
/// returns>/returns>
        public int ChanListLengthT>(NodeT> head)
        {
            int count = 0;

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

            return count;
        }
        #endregion

好了，最后上一下總的運(yùn)行代碼：

復(fù)制代碼代碼如下:

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();

NodeStudent> node = null;

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

            //將數(shù)據(jù)添加到鏈表的尾部
            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 = "一線碼農(nóng)", Age = 23 });

Dispaly(node);

Console.WriteLine("將ID=1的數(shù)據(jù)插入到鏈表開(kāi)頭:\n");

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

Dispaly(node);

Console.WriteLine("查找Name=“一線碼農(nóng)”的節(jié)點(diǎn)\n");

//查找Name=“一線碼農(nóng)”的節(jié)點(diǎn)
var result = chainList.ChainListFindByKey(node, "一線碼農(nóng)", i => i.Name);

DisplaySingle(node);

Console.WriteLine("將”ID=4“的實(shí)體插入到“博客園”這個(gè)節(jié)點(diǎn)的之后\n");

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

Dispaly(node);

Console.WriteLine("刪除Name=‘51cto‘的節(jié)點(diǎn)數(shù)據(jù)\n");

//刪除Name=‘51cto‘的節(jié)點(diǎn)數(shù)據(jù)
node = chainList.ChainListDelete(node, "51cto", i => i.Name);

Dispaly(node);

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

        //輸出數(shù)據(jù)
        public static void Dispaly(NodeStudent> head)
        {
            Console.WriteLine("******************* 鏈表數(shù)據(jù)如下 *******************");
            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("******************* 鏈表數(shù)據(jù)展示完畢 *******************\n");
}

        //展示當(dāng)前節(jié)點(diǎn)數(shù)據(jù)
        public static void DisplaySingle(NodeStudent> head)
        {
            if (head != null)
                Console.WriteLine("ID:" + head.data.ID + ", Name:" + head.data.Name + ",Age:" + head.data.Age);
            else
                Console.WriteLine("未查找到數(shù)據(jù)！");
        }
    }

    #region 學(xué)生數(shù)據(jù)實(shí)體
    /// summary>
/// 學(xué)生數(shù)據(jù)實(shí)體
/// /summary>
    public class Student
    {
        public int ID { get; set; }

public string Name { get; set; }

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

    #region 鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
    /// summary>
/// 鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
/// /summary>
    public class NodeT>
    {
        /// summary>
/// 節(jié)點(diǎn)的數(shù)據(jù)域
/// /summary>
        public T data;

        /// summary>
/// 節(jié)點(diǎn)的指針域
/// /summary>
        public NodeT> next;
    }
    #endregion

    #region 鏈表的相關(guān)操作
    /// summary>
/// 鏈表的相關(guān)操作
/// /summary>
    public class ChainList
    {
        #region 將節(jié)點(diǎn)添加到鏈表的末尾
        /// summary>
/// 將節(jié)點(diǎn)添加到鏈表的末尾
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="head">/param>
/// param name="data">/param>
/// returns>/returns>
        public NodeT> ChainListAddEndT>(NodeT> head, T data)
        {
            NodeT> node = new NodeT>();

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

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

//獲取當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)
ChainListGetLast(head).next = node;

            return head;
        }
        #endregion

        #region 將節(jié)點(diǎn)添加到鏈表的開(kāi)頭
        /// summary>
/// 將節(jié)點(diǎn)添加到鏈表的開(kāi)頭
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="chainList">/param>
/// param name="data">/param>
/// returns>/returns>
        public NodeT> ChainListAddFirstT>(NodeT> head, T data)
        {
            NodeT> node = new NodeT>();

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

head = node;

return head;

}
#endregion

        #region 將節(jié)點(diǎn)插入到指定位置
        /// summary>
/// 將節(jié)點(diǎn)插入到指定位置
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="head">/param>
/// param name="currentNode">/param>
/// param name="data">/param>
/// returns>/returns>
        public NodeT> ChainListInsertT, W>(NodeT> head, string key, FuncT, W> where, T data) where W : IComparable
        {
            if (head == null)
                return null;

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

node.data = data;

node.next = head.next;

head.next = node;
}

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

            return head;
        }
        #endregion

            //這是針對(duì)只有一個(gè)節(jié)點(diǎn)的解決方案
            if (where(head.data).CompareTo(key) == 0)
            {
                if (head.next != null)
                    head = head.next;
                else
                    return head = null;
            }
            else
            {
                //判斷一下此節(jié)點(diǎn)是否是要?jiǎng)h除的節(jié)點(diǎn)的前一節(jié)點(diǎn)
                if (head.next != null where(head.next.data).CompareTo(key) == 0)
                {
                    //將刪除節(jié)點(diǎn)的next域指向前一節(jié)點(diǎn)
                    head.next = head.next.next;
                }
            }

ChainListDelete(head.next, key, where);

            return head;
        }
        #endregion

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

            return ChainListFindByKeyT, W>(head.next, key, where);
        }
        #endregion

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

            return count;
        }
        #endregion

        #region 得到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)
        /// summary>
/// 得到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)
/// /summary>
/// typeparam name="T">/typeparam>
/// param name="head">/param>
/// returns>/returns>
        public NodeT> ChainListGetLastT>(NodeT> head)
        {
            if (head.next == null)
                return head;
            return ChainListGetLast(head.next);
        }
        #endregion

}
#endregion
}

運(yùn)行結(jié)果：

當(dāng)然，單鏈表操作中有很多是O(N)的操作，這給我們帶來(lái)了尷尬的局面，所以就有了很多的優(yōu)化方案，比如：雙向鏈表，循環(huán)鏈表。靜態(tài)鏈表等等，這些希望大家在懂得單鏈表的情況下待深一步的研究。

您可能感興趣的文章:

java線性表排序示例分享
算法系列15天速成第七天線性表【上】
php線性表順序存儲(chǔ)實(shí)現(xiàn)代碼(增刪查改)
數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明備忘錄線性表
C語(yǔ)言安全之?dāng)?shù)組長(zhǎng)度與指針實(shí)例解析
C語(yǔ)言安全編碼數(shù)組記法的一致性
C語(yǔ)言安全編碼之?dāng)?shù)組索引位的合法范圍
C語(yǔ)言安全編碼之?dāng)?shù)值中的sizeof操作符
python和C語(yǔ)言混合編程實(shí)例
C語(yǔ)言線性表的順序表示與實(shí)現(xiàn)實(shí)例詳解

標(biāo)簽：定州 96 山南宜賓日照防城港巴彥淖爾內(nèi)蒙古

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《算法系列15天速成第八天線性表【下】》，本文關(guān)鍵詞算法,系列,15天,速成,第八,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。