当前位置:软件学习 > 其它软件 >>

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

 

一:线性表的简单回顾

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

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

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

 

二:链表

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

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

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

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

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

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

\

代码段如下:

 

 

 1     #region 链表节点的数据结构

 2 /// <summary>

 3 /// 链表节点的数据结构

 4 /// </summary>

 5     public class Node<T>

 6     {

 7/// <summary>

 8 /// 节点的数据域

 9 /// </summary>

10         public T data;

11

12 /// <summary>

13 /// 节点的指针域

14 /// </summary>

15         public Node<T> next;

16     }

17     #endregion

www.zzzyk.com

 

2.常用操作:

 

    链表的常用操作一般有:

 

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

 

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

 

  

 

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

 

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

 

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

 

 

 

代码段如下:

 

 1 #region 将节点添加到链表的末尾

 2         /// <summary>

 3 /// 将节点添加到链表的末尾

 4 /// </summary>

 5 /// <typeparam name="T"></typeparam>

 6 /// <param name="head"></param>

 7 /// <param name="data"></param>

 8 /// <returns></returns>

 9         public Node<T> ChainListAddEnd<T>(Node<T> head, T data)

10         {

11             Node<T> node = new Node<T>();

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         /// <summary>

31 /// 得到当前链表的最后一个节点

32 /// </summary>

33 /// <typeparam name="T"></typeparam>

34 /// <param name="head"></param>

35 /// <returns></returns>

36         public Node<T> ChainListGetLast<T>(Node<T> 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 /// <summary>

 3 /// 将节点添加到链表的开头

 4 /// </summary>

 5 /// <typeparam name="T"></typeparam>

 6 /// <param name="chainList"></param>

 7 /// <param name="data"></param>

 8 /// <returns></returns>

 9         public Node<T> ChainListAddFirst<T>(Node<T> head, T data)

10         {

11             Node<T> node = new Node<T>();

12

13             node.data = data;

14             node.next = head;

15

16             head = node;

17

18             return head;

19

20         }

21         #endregion

 


<3> 插入节点:

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

     

补充:软件开发 , 其他 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,