AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2016-04-13 1199
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

一：线性表的简单回顾

       上一篇跟大家聊过“线性表"顺序存储，通过实验，大家也知道，如果我每次向

顺序表的头部插入元素，都会引起痉挛，效率比较低下，第二点我们用顺序存储时，容

易受到长度的限制，反之就会造成空间资源的浪费。

 

二：链表

      对于顺序表存在的若干问题，链表都给出了相应的解决方案。

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)的操作，这给我们带来了尴尬的局面，所以就有了很多的

优化方案，比如：双向链表，循环链表。静态链表等等，这些希望大家在懂得单链表的情况下

待深一步的研究。

文章标签：
算法
存储
机器学习/深度学习
关键词：
算法线性表
一线码农
目录
相关文章
日星月云
|
7月前
|
存储 算法 数据安全/隐私保护
第二章 线性表【数据结构与算法】【精致版】
第二章 线性表【数据结构与算法】【精致版】
日星月云
128 0
玥轩
|
算法
数据结构与算法2.1线性表、链表
数据结构与算法2.1线性表、链表
玥轩
39 0
数据结构与算法2.1线性表、链表
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二（5）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
18 0
sky_qiyi
|
6月前
|
算法
数据结构和算法学习记录——线性表之双向链表（上）-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表（上）-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
sky_qiyi
52 0
sky_qiyi
|
6月前
|
存储 算法
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
sky_qiyi
42 0
sky_qiyi
|
6月前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈（下）-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈（下）-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
sky_qiyi
38 0
sky_qiyi
|
6月前
|
算法
数据结构和算法学习记录——特殊线性表之栈（上）-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数
数据结构和算法学习记录——特殊线性表之栈（上）-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数
sky_qiyi
34 0
sky_qiyi
|
6月前
|
算法
数据结构和算法学习记录——线性表之双向链表（下）-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表（下）-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
sky_qiyi
30 0
sky_qiyi
|
6月前
|
算法
数据结构和算法学习记录——线性表之单链表（下）-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表（下）-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
sky_qiyi
64 0
sky_qiyi
|
6月前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
sky_qiyi
41 0

热门文章

最新文章

  • 1
    Flink---13、容错机制（检查点（保存、恢复、算法、配置）、状态一致性、端到端精确一次）
  • 2
    openssl中算法的组织方式
  • 3
    JVM内存模型及垃圾回收算法
  • 4
    【算法研究】Bresenham画线算法
  • 5
    九连环的递归算法（C和C++）
  • 6
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 7
    判断一个数字是否为素数的基于C语言的算法
  • 8
    OpenCV 1 图像分割--分水岭算法代码
  • 9
    希尔排序(shellsort)算法实现
  • 10
    缓存、缓存算法(转)
  • 1
    Android文字基线Baseline算法的使用讲解，Android开发面试题
    83
  • 2
    如何用算法规划完美的相亲假期 - 小美的春节排班挑战
    79
  • 3
    实时计算 Flink版产品使用合集之哪个版本可以做增量快照算法
    79
  • 4
    MATLAB|【免费】融合正余弦和柯西变异的麻雀优化算法SCSSA-CNN-BiLSTM双向长短期记忆网络预测模型
    139
  • 5
    R-Tree算法：空间索引的高效解决方案
    236
  • 6
    Groovy脚本基础全攻略，android面试算法题
    94
  • 7
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    106
  • 8
    【redis源码学习】持久化机制，java程序员面试算法宝典pdf
    79
  • 9
    对标腾讯T9架构师的 Android 面试题新鲜出炉，算法真的太重要了
    54
  • 10
    【机器学习】K-means算法与PCA算法之间有什么联系？
    297

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月