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

强烈建议你试试无所不能的chatGPT，快点击我

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

阅读量：4517 次

发布时间：2019-06-08

本文共 12414 字，大约阅读时间需要 41 分钟。

一：线性表的简单回顾

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

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

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

二：链表

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

1. 概念：其实链表的“每个节点”都包含一个”数据域“和”指针域“。

”数据域“中包含当前的数据。

”指针域“中包含下一个节点的指针。

”头指针”也就是head，指向头结点数据。

“末节点“作为单向链表，因为是最后一个节点，通常设置指针域为null。

代码段如下：

1     #region 链表节点的数据结构  2 ///   3 /// 链表节点的数据结构  4 /// 
  5     public class Node
     
        6     {
    7/// 
        8 /// 节点的数据域  9 /// 
 10         public T data; 11 12 /// 
       13 /// 节点的指针域 14 /// 
 15         public Node
      
        next; 16     } 17     #endregion

2.常用操作：

链表的常用操作一般有：

①添加节点到链接尾，②添加节点到链表头，③插入节点。

④删除节点，⑤按关键字查找节点，⑥取链表长度。

<1> 添加节点到链接尾：

前面已经说过，链表是采用指针来指向下一个元素，所以说要想找到链表最后一个节点，

必须从头指针开始一步一步向后找,少不了一个for循环，所以时间复杂度为O(N)。

代码段如下：

1 #region 将节点添加到链表的末尾  2         ///   3 /// 将节点添加到链表的末尾  4 /// 
  5 /// 
       6 ///   7 ///   8 /// 
       9         public Node
     
       ChainListAddEnd
      
       (Node
       
         head, T data) 10         {
   11             Node
        
          node = new Node
         
          (); 12 13             node.data = data; 14             node.next = null; 15 16             ///说明是一个空链表 17             if (head == null) 18             {
   19                 head = node; 20                 return head; 21             } 22 23             //获取当前链表的最后一个节点 24             ChainListGetLast(head).next = node; 25 26             return head; 27         } 28 #endregion 29 #region 得到当前链表的最后一个节点 30         /// 
           31 /// 得到当前链表的最后一个节点 32 /// 
 33 /// 
           34 /// 
           35 /// 
           36         public Node
          
            ChainListGetLast
           
            (Node
            
              head) 37 { 38 if (head.next == null) 39 return head; 40 return ChainListGetLast(head.next); 41 } 42 #endregion

<2> 添加节点到链表头:

大家现在都知道，链表是采用指针指向的，要想将元素插入链表头，其实还是很简单的，

思想就是：① 将head的next指针给新增节点的next。②将整个新增节点给head的next。

所以可以看出，此种添加的时间复杂度为O(1)。

效果图：

代码段如下：

1#region 将节点添加到链表的开头  2 ///   3 /// 将节点添加到链表的开头  4 /// 
  5 /// 
       6 ///   7 ///   8 /// 
       9         public Node
     
       ChainListAddFirst
      
       (Node
       
         head, T data) 10         {
   11             Node
        
          node = new Node
         
          (); 12 13             node.data = data; 14             node.next = head; 15 16             head = node; 17 18             return head; 19 20         } 21         #endregion

<3> 插入节点:

其实这个思想跟插入到”首节点“是一个模式，不过多了一步就是要找到当前节点的操作。然后找到

这个节点的花费是O(N）。上图上代码，大家一看就明白。

效果图：

代码段：

1 #region 将节点插入到指定位置  2 ///   3 /// 将节点插入到指定位置  4 /// 
  5 /// 
       6 ///   7 ///   8 ///   9 /// 
      10         public Node
     
       ChainListInsert
      
       (Node
       
         head, string key, Func
        
          where, T data) where W : IComparable 11         {
   12             if (head == null) 13                 return null; 14 15             if (where(head.data).CompareTo(key) == 0) 16             {
   17                 Node
         
           node = new Node
          
           (); 18 19 node.data = data; 20 21 node.next = head.next; 22 23 head.next = node; 24 } 25 26 ChainListInsert(head.next, key, where, data); 27 28 return head; 29 } 30 #endregion

<4> 删除节点:

这个也比较简单，不解释，图跟代码更具有说服力，口头表达反而让人一头雾水。

当然时间复杂度就为O(N)，N是来自于查找到要删除的节点。

效果图：

代码段：

1 #region 将指定关键字的节点删除  2         ///   3 /// 将指定关键字的节点删除  4 /// 
  5 /// 
       6 /// 
       7 ///   8 ///   9 ///  10 ///  11 /// 
      12         public Node
     
       ChainListDelete
      
       (Node
       
         head, string key, Func
        
          where) where W : IComparable 13         {
   14             if (head == null) 15                 return null; 16 17             //这是针对只有一个节点的解决方案 18             if (where(head.data).CompareTo(key) == 0) 19             {
   20                 if (head.next != null) 21                     head = head.next; 22                 else 23                     return head = null; 24             } 25             else 26             {
   27                 //判断一下此节点是否是要删除的节点的前一节点 28                 while (head.next != null && where(head.next.data).CompareTo(key) == 0) 29                 {
   30                     //将删除节点的next域指向前一节点 31                     head.next = head.next.next; 32                 } 33             } 34 35             ChainListDelete(head.next, key, where); 36 37             return head; 38         } 39         #endregion

<5> 按关键字查找节点：

这个思想已经包含到“插入节点”和“删除节点”的具体运用中的，其时间复杂度为O(N)。

代码段：

1 #region 通过关键字查找指定的节点  2         ///   3 /// 通过关键字查找指定的节点  4 /// 
  5 /// 
       6 /// 
       7 ///   8 ///   9 ///  10 /// 
      11         public Node
     
       ChainListFindByKey
      
       (Node
       
         head, string key, Func
        
          where) where W : IComparable 12         {
   13             if (head == null) 14                 return null; 15 16             if (where(head.data).CompareTo(key) == 0) 17                 return head; 18 19             return ChainListFindByKey
         
          (head.next, key, where); 20         } 21         #endregion

<6> 取链表长度:

在单链表的操作中，取链表长度还是比较纠结的，因为他不像顺序表那样是在内存中连续存储的，

因此我们就纠结的遍历一下链表的总长度。时间复杂度为O(N)。

代码段：

1         #region 获取链表的长度  2         ///   3 ///// 获取链表的长度  4 /// 
  5 /// 
       6 ///   7 /// 
       8         public int ChanListLength
     
      (Node
      
        head)  9         {
   10             int count = 0; 11 12             while (head != null) 13             {
   14                 ++count; 15                 head = head.next; 16             } 17 18             return count; 19         } 20         #endregion

好了，最后上一下总的运行代码：

View Code

1 using System;   2 using System.Collections.Generic;   3 using System.Linq;   4 using System.Text;   5   6 namespace ChainList   7 {
      8     class Program   9     {
     10         static void Main(string[] args)  11         {
     12             ChainList chainList = new ChainList();  13  14             Node
      
        node = null;  15  16             Console.WriteLine("将三条数据添加到链表的尾部:\n");  17  18             //将数据添加到链表的尾部  19             node = chainList.ChainListAddEnd(node, new Student() { ID = 2, Name = "hxc520", Age = 23 });  20             node = chainList.ChainListAddEnd(node, new Student() { ID = 3, Name = "博客园", Age = 33 });  21             node = chainList.ChainListAddEnd(node, new Student() { ID = 5, Name = "一线码农", Age = 23 });  22  23             Dispaly(node);  24  25             Console.WriteLine("将ID=1的数据插入到链表开头:\n");  26  27             //将ID=1的数据插入到链表开头  28             node = chainList.ChainListAddFirst(node, new Student() { ID = 1, Name = "i can fly", Age = 23 });  29  30             Dispaly(node);  31  32             Console.WriteLine("查找Name=“一线码农”的节点\n");  33  34             //查找Name=“一线码农”的节点  35             var result = chainList.ChainListFindByKey(node, "一线码农", i => i.Name);  36  37             DisplaySingle(node);  38  39             Console.WriteLine("将”ID=4“的实体插入到“博客园”这个节点的之后\n");  40  41             //将”ID=4“的实体插入到"博客园"这个节点的之后  42             node = chainList.ChainListInsert(node, "博客园", i => i.Name, new Student() { ID = 4, Name = "51cto", Age = 30 });  43  44             Dispaly(node);  45  46             Console.WriteLine("删除Name=‘51cto‘的节点数据\n");  47  48             //删除Name=‘51cto‘的节点数据  49             node = chainList.ChainListDelete(node, "51cto", i => i.Name);  50  51             Dispaly(node);  52  53             Console.WriteLine("获取链表的个数:" + chainList.ChanListLength(node));  54         }  55  56         //输出数据  57         public static void Dispaly(Node
       
         head)  58         {
     59             Console.WriteLine("******************* 链表数据如下 *******************");  60             var tempNode = head;  61  62             while (tempNode != null)  63             {
     64                 Console.WriteLine("ID:" + tempNode.data.ID + ", Name:" + tempNode.data.Name + ",Age:" + tempNode.data.Age);  65                 tempNode = tempNode.next;  66             }  67  68             Console.WriteLine("******************* 链表数据展示完毕 *******************\n");  69         }  70  71         //展示当前节点数据  72         public static void DisplaySingle(Node
        
          head)  73         {
     74             if (head != null)  75                 Console.WriteLine("ID:" + head.data.ID + ", Name:" + head.data.Name + ",Age:" + head.data.Age);  76             else  77                 Console.WriteLine("未查找到数据！");  78         }  79     }  80  81     #region 学生数据实体  82     /// 
           83 /// 学生数据实体  84 /// 
  85     public class Student  86     {
     87         public int ID { get; set; }  88  89         public string Name { get; set; }  90  91         public int Age { get; set; }  92     }  93     #endregion  94  95     #region 链表节点的数据结构  96     /// 
           97 /// 链表节点的数据结构  98 /// 
  99     public class Node
         
           100     {
    101         /// 
           102 /// 节点的数据域 103 /// 
 104         public T data; 105 106         /// 
           107 /// 节点的指针域 108 /// 
 109         public Node
          
            next; 110     } 111     #endregion 112 113     #region 链表的相关操作 114     /// 
            115 /// 链表的相关操作 116 /// 
 117     public class ChainList 118     {
    119         #region 将节点添加到链表的末尾 120         /// 
            121 /// 将节点添加到链表的末尾 122 /// 
 123 /// 
            124 /// 
            125 /// 
            126 /// 
            127         public Node
           
             ChainListAddEnd
            
             (Node
             
               head, T data) 128 { 129 Node
              
                node = new Node
               
                (); 130 131 node.data = data; 132 node.next = null; 133 134 ///说明是一个空链表 135 if (head == null) 136 { 137 head = node; 138 return head; 139 } 140 141 //获取当前链表的最后一个节点 142 ChainListGetLast(head).next = node; 143 144 return head; 145 } 146 #endregion 147 148 #region 将节点添加到链表的开头 149 /// 
                 150 /// 将节点添加到链表的开头 151 /// 
 152 /// 
                 153 /// 
                 154 /// 
                 155 /// 
                 156 public Node
                
                  ChainListAddFirst
                 
                  (Node
                  
                    head, T data) 157 { 158 Node
                   
                     node = new Node
                    
                     (); 159 160 node.data = data; 161 node.next = head; 162 163 head = node; 164 165 return head; 166 167 } 168 #endregion 169 170 #region 将节点插入到指定位置 171 /// 
                      172 /// 将节点插入到指定位置 173 /// 
 174 /// 
                      175 /// 
                      176 /// 
                      177 /// 
                      178 /// 
                      179 public Node
                     
                       ChainListInsert
                      
                       (Node
                       
                         head, string key, Func
                        
                          where, T data) where W : IComparable 180 { 181 if (head == null) 182 return null; 183 184 if (where(head.data).CompareTo(key) == 0) 185 { 186 Node
                         
                           node = new Node
                          
                           (); 187 188 node.data = data; 189 190 node.next = head.next; 191 192 head.next = node; 193 } 194 195 ChainListInsert(head.next, key, where, data); 196 197 return head; 198 } 199 #endregion 200 201 #region 将指定关键字的节点删除 202 /// 
                            203 /// 将指定关键字的节点删除 204 /// 
 205 /// 
                            206 /// 
                            207 /// 
                            208 /// 
                            209 /// 
                            210 /// 
                            211 /// 
                            212 public Node
                           
                             ChainListDelete
                            
                             (Node
                             
                               head, string key, Func
                              
                                where) where W : IComparable 213 { 214 if (head == null) 215 return null; 216 217 //这是针对只有一个节点的解决方案 218 if (where(head.data).CompareTo(key) == 0) 219 { 220 if (head.next != null) 221 head = head.next; 222 else 223 return head = null; 224 } 225 else 226 { 227 //判断一下此节点是否是要删除的节点的前一节点 228 if (head.next != null && where(head.next.data).CompareTo(key) == 0) 229 { 230 //将删除节点的next域指向前一节点 231 head.next = head.next.next; 232 } 233 } 234 235 ChainListDelete(head.next, key, where); 236 237 return head; 238 } 239 #endregion 240 241 #region 通过关键字查找指定的节点 242 /// 
                                243 /// 通过关键字查找指定的节点 244 /// 
 245 /// 
                                246 /// 
                                247 /// 
                                248 /// 
                                249 /// 
                                250 /// 
                                251 public Node
                               
                                 ChainListFindByKey
                                
                                 (Node
                                 
                                   head, string key, Func
                                  
                                    where) where W : IComparable 252 { 253 if (head == null) 254 return null; 255 256 if (where(head.data).CompareTo(key) == 0) 257 return head; 258 259 return ChainListFindByKey
                                   
                                    (head.next, key, where); 260 } 261 #endregion 262 263 #region 获取链表的长度 264 /// 
                                     265 ///// 获取链表的长度 266 /// 
 267 /// 
                                     268 /// 
                                     269 /// 
                                     270 public int ChanListLength
                                    
                                     (Node
                                     
                                       head) 271 { 272 int count = 0; 273 274 while (head != null) 275 { 276 ++count; 277 head = head.next; 278 } 279 280 return count; 281 } 282 #endregion 283 284 #region 得到当前链表的最后一个节点 285 /// 
                                       286 /// 得到当前链表的最后一个节点 287 /// 
 288 /// 
                                       289 /// 
                                       290 /// 
                                       291 public Node
                                      
                                        ChainListGetLast
                                       
                                        (Node
                                        
                                          head) 292 { 293 if (head.next == null) 294 return head; 295 return ChainListGetLast(head.next); 296 } 297 #endregion 298 299 } 300 #endregion 301 }

运行结果：

当然，单链表操作中有很多是O(N)的操作，这给我们带来了尴尬的局面，所以就有了很多的

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

待深一步的研究。

转载于:https://www.cnblogs.com/huangxincheng/archive/2011/11/30/2268904.html

你可能感兴趣的文章

大白话5分钟带你走进人工智能-第二十四节决策树系列之分裂流程和Gini系数评估(3)...

ubuntu下vim与系统剪切板互相拷贝

01_Java语言基础部分(数据类型与表达式、流程控制语句、数组与方法)

Codeforces Round #248 (Div. 2) B. Kuriyama Mirai's Stones

《30天自制操作系统》学习笔记--第好多天

CodeForces 617 E. XOR and Favorite Number

在spring boot中打印mybaits执行的sql

用动态规划解小朋友分糖问题

tomcat ----> 启动，关闭和配置等等

日常开发中的几个常用跨域处理方式

Centos7中systemctl命令详解

Nhibernate与Castle windsor （个人学习笔记1）

redis入门教程

Spring aop切面插入事物回滚

Android 组件系列-----Activity保存状态

数据类型的内置方法：元组

jQuery学习笔记（一）：入门

【个人项目总结】四则运算生成器

【教程】如何正确的写一个Lemon/Cena的SPJ(special judge)

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-10-15 17:15:43 当前IP: 18.189.178.53 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我