精华内容
下载资源
问答
  • 头结点的含义以及引入头结点的作用

    千次阅读 多人点赞 2020-06-23 11:56:15
    一、概念 头结点:是虚拟出来的一个节点,不保存数据。...如果有头结点,头指针就指向头结点。 二、为何引入头结点 1)对链表的删除、插入操作时,第一个结点的操作更方便 如果链表没有头结点,那么头

    一、概念

    头结点:是虚拟出来的一个节点,不保存数据。头结点的next指针指向链表中的第一个节点。对于头结点,数据域可以不存储任何信息,也可存储如链表长度等附加信息。头结点不是链表所必需的

    头指针:是指向第一个结点的指针,如果链表没有引入头结点,那么头指针指向的是链表的第一个结点。头指针是链表所必需的

    [注意]无论是否有头结点,头指针始终指向链表的第一个结点。如果有头结点,头指针就指向头结点。

    二、为何引入头结点

    1)对链表的删除、插入操作时,第一个结点的操作更方便

    如果链表没有头结点,那么头指针指向的是链表的第一个结点,当在第一个结点前插入一个节点时,那么头指针要相应指向新插入的结点,把第一个结点删除时,头指针的指向也要更新。也就是说如果没有头结点,我们需要维护着头指针的指向更新。因为头指针指向的是链表的第一个结点,如果引入头结点的话,那么头结点的next始终都是链表的第一个结点。

                带头结点的单链表

     

     

           不带头结点的单链表

     

     

     

    引入头结点后,头指针指向头结点,那么无论链表是否为空,头指针均不为空。

    2)统一空表和非空表的处理

    有了头结点之后头指针指向头结点,不论链表是否为空,头指针总是非空,而且头结点的设置使得对链表的第一个位置上的操作与在表中其它位置上的操作一致,即统一空表和非空表的处理

     

     

     

    展开全文
  • 一、概念辨析 线性表的插入删除需要移动大量的元素,因此引入链表(本文讨论单链表)的概念...头结点:在单链表的第一个结点之前附加一个结点,称为头结点头结点的Data域可以不设任何信息,也可以记录表长等相关...

    一、概念辨析

    线性表的插入删除需要移动大量的元素,因此引入链表(本文讨论单链表)的概念,链表元素之间通过“链”来链接,因此插入和删除时不需要大量的移动元素,而只需要改变“链”的关系即可。

    • 头指针:通常使用“头指针”来标识一个链表,如单链表L,头指针为NULL的时表示一个空链表。
    • 头结点:在单链表的第一个结点之前附加一个结点,称为头结点。头结点的Data域可以不设任何信息,也可以记录表长等相关信息。

    [注意]无论是否有头结点,头指针始终指向链表的第一个结点。如果有头结点,头指针就指向头结点。


    二、引入头结点的优势

    刚刚提到,链表可以没有头结点,但是必须要有头指针,因为要用头指针来标识一个链表。设链表的头指针为pHead。除了头结点之外,还需要一个指向链表一般元素的指针pNode(因为pHead只能指向表头,不能指向其他元素,故需要另设指针)。

    优势1:第1个位置的插入删除更加方便

    若使用头结点,则第1个位置的插入和删除都是对p—>next进行操作,而不用动p本身,而且减少了算法分支(即if else分支)具体的流程为:

    插入操作如下
    1. p指向要插入结点的前驱结点,若要插入的结点为第1个位置,则其前驱结点就是头结点,此时p指向头结点。
    2. 让新结点s的next指向p的next,即s—>next = p—>next;
    3. 让p—>next指向s,即p—>next = s;
    删除操作如下
    1. p指向要删除结点的前驱结点,若要删除的结点为第1个位置,则其前驱结点就是头结点,此时p指向头结点。
    2. 让临时指针q指向要删除的结点,即q = p—>next;
    3. 让p的next指向要删除结点的下一个结点,即p—>next = q—>next;
    4. 释放q的空间,即free(q);

    若没有头结点,在第1个位置插入或删除时,需要动头指针。

    插入操作如下
    1. 判断要插入的是否是第1个位置,若是需要特殊处理。
    2. 若是第1个位置,让新结点s的next指向头指针PtrL。
    3. return s,此时s作为链表的头指针。此时的更新了链表的头指针。
    4. 若不是第1个位置,首先找到要插入结点的前驱结点,让p指向这个前驱结点。
    5. 让新结点s的next指向p的next,即s—>next = p—>next;
    6. 让p—>next指向s,即p—>next = s;
    7. return PtrL,此时PtrL还是作为链表的头指针,没有被修改,但考虑到一致性需要这样写。
    删除操作如下
    1. 判断要删除的是否是第1个位置,若是需要特殊处理。
    2. 若是第1个位置,让s指向要删除的结点。首先判断PtrL是否为空,若是直接return NULL;若不为空,则将链表的头结点挪到下一个位置,即PtrL = PtrL—>next;
    3. free(s);然后return PtrL
    4. 若不是第1个位置,首先找到要删除结点的前驱结点,让p指向这个前驱结点。
    5. 让临时指针q指向要删除的结点,即q = p—>next;
    6. 让p的next指向要删除结点的下一个结点,即p—>next = q—>next;
    7. 释放q的空间,即free(q);
    8. return PtrL

    优势2:统一空表和非空表的处理

    若使用头结点,无论表是否为空,头指针都指向头结点,也就是*LNode类型,对于空表和非空表的操作是一致的。

    若不使用头结点,当表非空时,头指针指向第1个结点的地址,即*LNode类型,但是对于空表,头指针指向的是NULL,此时空表和非空表的操作是不一致的。


    展开全文
  • 头结点和没有头结点

    千次阅读 2019-04-27 15:36:04
    一、概念辨析 线性表的插入删除需要移动大量的元素,因此引入链表(本文讨论单链表)的...头结点:在单链表的第一个结点之前附加一个结点,称为头结点头结点的Data域可以不设任何信息,也可以记录表长等相关信息...

    一、概念辨析
    线性表的插入删除需要移动大量的元素,因此引入链表(本文讨论单链表)的概念,链表元素之间通过“链”来链接,因此插入和删除时不需要大量的移动元素,而只需要改变“链”的关系即可。

    头指针:通常使用“头指针”来标识一个链表,如单链表L,头指针为NULL的时表示一个空链表。
    头结点:在单链表的第一个结点之前附加一个结点,称为头结点。头结点的Data域可以不设任何信息,也可以记录表长等相关信息。
    [注意]无论是否有头结点,头指针始终指向链表的第一个结点。如果有头结点,头指针就指向头结点。

    二、引入头结点的优势
    刚刚提到,链表可以没有头结点,但是必须要有头指针,因为要用头指针来标识一个链表。设链表的头指针为pHead。除了头结点之外,还需要一个指向链表一般元素的指针pNode(因为pHead只能指向表头,不能指向其他元素,故需要另设指针)。

    优势1:第1个位置的插入删除更加方便
    若使用头结点,则第1个位置的插入和删除都是对p—>next进行操作,而不用动p本身,而且减少了算法分支(即if else分支)具体的流程为:

    插入操作如下
    p指向要插入结点的前驱结点,若要插入的结点为第1个位置,则其前驱结点就是头结点,此时p指向头结点。
    让新结点s的next指向p的next,即s—>next = p—>next;
    让p—>next指向s,即p—>next = s;
    删除操作如下
    p指向要删除结点的前驱结点,若要删除的结点为第1个位置,则其前驱结点就是头结点,此时p指向头结点。
    让临时指针q指向要删除的结点,即q = p—>next;
    让p的next指向要删除结点的下一个结点,即p—>next = q—>next;
    释放q的空间,即free(q);
    若没有头结点,在第1个位置插入或删除时,需要动头指针。

    插入操作如下
    判断要插入的是否是第1个位置,若是需要特殊处理。
    若是第1个位置,让新结点s的next指向头指针PtrL。
    return s,此时s作为链表的头指针。此时的更新了链表的头指针。
    若不是第1个位置,首先找到要插入结点的前驱结点,让p指向这个前驱结点。
    让新结点s的next指向p的next,即s—>next = p—>next;
    让p—>next指向s,即p—>next = s;
    return PtrL,此时PtrL还是作为链表的头指针,没有被修改,但考虑到一致性需要这样写。
    删除操作如下
    判断要删除的是否是第1个位置,若是需要特殊处理。
    若是第1个位置,让s指向要删除的结点。首先判断PtrL是否为空,若是直接return NULL;若不为空,则将链表的头结点挪到下一个位置,即PtrL = PtrL—>next;
    free(s);然后return PtrL
    若不是第1个位置,首先找到要删除结点的前驱结点,让p指向这个前驱结点。
    让临时指针q指向要删除的结点,即q = p—>next;
    让p的next指向要删除结点的下一个结点,即p—>next = q—>next;
    释放q的空间,即free(q);
    return PtrL


    优势2:统一空表和非空表的处理
    若使用头结点,无论表是否为空,头指针都指向头结点,也就是*LNode类型,对于空表和非空表的操作是一致的。

    若不使用头结点,当表非空时,头指针指向第1个结点的地址,即*LNode类型,但是对于空表,头指针指向的是NULL,此时空表和非空表的操作是不一致的


    原文:https://blog.csdn.net/qq_24118527/article/details/81317410 
     

    展开全文
  • 如果该链表有头结点,则头指针head指向头结点,如果没有头结点,则头指针head指向链表的第一个节点。 1 带头结点的单链表中头指针head指向头结点头结点的值域不含任何信息,从头结点的后继结点开始存储信息。头...

    不论是带头结点的链表还是不带头结点的链表,头指针head都指向链表中的第一个结点。如果该链表有头结点,则头指针head指向头结点,如果没有头结点,则头指针head指向链表的第一个节点。

    1 带头结点的单链表中头指针head指向头结点,头结点的值域不含任何信息,从头结点的后继结点开始存储信息。头指针head始终不等于NULL,head->next等于NULL的时候链表为空。

    2 不带头结点的单链表中的头指针head直接指向开始结点,当head等于NULL的时候链表为空。

    头结点的存在,使得空链表与非空链表的处理变得一直,也方便了对链表的开始结点插入或删除操作。

    不带头结点的实现如下:

    class ListNode:
        def __init__(self, value=None, next=None):
            self.data = value
            self.next = next
     
     
    def creat_List(l, n):
        l.data = int(input())
        p = l
        for i in range(n-1):
            node = ListNode()
            node.data = int(input())
            p.next = node
            p = p.next
        
        p.next = None
        
    def length(l):
        p = l
        len = 0
        while p:
            len += 1
            p = p.next
        return len
     
    # 链表逆转
    def reverse(l):
        res = pre = None
        p = l
        while p:
            pre = p.next
            p.next = res
            res = p
            p = pre
        return res 
     
    def traverse(l):
        p = l
        while p:
            print(p.data, ' ', end='')
            p = p.next
        
        print()
     
    if __name__ == '__main__':
        l = ListNode()
        creat_List(l, 5)
        traverse(l)
        ll = reverse(l)
        traverse(ll)
        traverse(l)
    

     

    展开全文
  • 对于数据结构的头结点、头指针问题,一直都有点不太清楚理解。现对其中涉及的概念与如何使用python语言创建链表(带有头结点与不带头结点)进行解释。 一、基本概念 假设我们将对数组array[a1,a2,a3]创建链表结果...
  • 在线性表的链式存储结构中,头指针指的是指向第一个节点的指针,如果链表中有头结点,则头指针指向头结点,若链表不设头结点,则指向该链表的首元结点。 首元结点: 指链表中存储第一个元素的结点。 头结点头结点...
  • 头指针、头结点、首元结点(第一个元素结点)。在单链表中的作用是什么? 首元结点是指链表中存储线性表中第一个数据元素a1的结点。 头结点: 为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点,该...
  • /* 内容:链表的基本操作 时间:2014.9.19*/ #include ...//判断是否为头结点 ...//头结点后移一位 ...这段代码删除头结点头结点后移了,但是输出的时候为什么出现错误?是不是指针的问题?找不出来了,求助
  • 头指针和头结点意义和区别

    万次阅读 多人点赞 2019-01-08 23:09:14
    由定义可知头指针指向链表第一个存储位置,当存在头结点时头指针指向头结点,这时如果删除链表中的节点头指针不会改变(头指针不能删除)。 当不存在头结点时,头指针指向首结点,如果这时候删除首...
  • 数据结构中头结点的作用

    万次阅读 多人点赞 2019-01-19 12:20:36
    数据结构中,在单链表的开始结点之前附设一个类型相同的结点,称之为头结点头结点的数据域可以不存储任何信息,头结点的指针域存储指向开始结点的指针(即第一个元素结点的存储位置)。 作用 1、防止单链表是空的...
  • 头指针 头结点 优点

    2017-04-24 15:23:59
    对于单链表来说,头结点可有可无,但为了操作方便,一般情况下单链表都具有头结点,后面的分析将会区别一下有头结点和没有头结点的区别。 优点: 减少了单链表添加删除时特殊情况的判断,减少了程序的复杂性,主要...
  • 链表头结点和不带头结点的区别

    千次阅读 多人点赞 2019-11-17 22:53:43
    一、概念辨析 线性表的插入删除需要移动大量的元素,因此引入链表(本文讨论单链表)的概念,链表元素之间通过“链”来链接,因此插入和...头结点:在单链表的第一个结点之前附加一个结点,称为头结点头结点的Dat...
  • //带头结点的单链表 #include<iostream> using namespace std; struct Node { int data; Node * next; }; typedef struct Node Node,*LinkList; //初始化 void initLink(LinkList &...
  • 头结点和头指针的详解
  • 单链表:带头结点和不带头结点 总结

    万次阅读 多人点赞 2019-03-25 17:54:01
    一直以来,带头结点和不带头节点的单链表的操作实现困扰着我。在没有理解和实现之前,光凭思考真的是很难理解清楚 1.两者之间代码的差异; 2.带不带头结点的区别; 3.带头结点之后,什么情况下形参必须传二级指针...
  • 头结点和头指针的区别

    千次阅读 2019-09-24 10:13:38
    头结点和头指针的区别? 不管带不带头结点,头指针始终指向链表的第一个结点,而头结点是带头结点链表中的第一个结点,结点内通常不存储信息,它是为了方便做的一种处理。 为什么要设置头结点? 处理起来方便。例如...
  • 头结点的好处以及如何设头结点

    千次阅读 2011-11-23 23:51:31
    如何设置头结点以及头结点的好处   在链表的建立时,如果使用头结点,可以使第一个结点在的操作一般化,也就是第一个结点和后面的结点的操作方法一样, 假如不建立头结点,那在链表的第一个节点前插入一个结点...
  • 头结点,第一个结点,头指针

    千次阅读 2019-01-21 15:19:35
    △头指针、头结点、第一个节点的区别 第一个节点:链表中存储第一个元素的结点,是头结点后边第一个结点。 头指针:指链表的指针,是指向链表中第一个节点(或为头结点或为首元结点)的指针。 头结点:是在...
  • C语言带头结点的单链表

    千次阅读 2018-11-07 22:43:47
    带头结点的单链表 之前的文章创建的单链表都是不带头结点的单链表。有时,我们为了更加方便地对链表进行操作,会在单链表...头结点头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般...
  • 头指针和头结点

    千次阅读 2016-12-11 23:42:53
    对于一个链表来说 头指针是必须的 头结点是可有可无的 不过头结点为链表的插入实现了统一化 在一个没有头结点的链表里面,我们要插入一个结点我们要传的是头指针的地址,因为我们在插入第一个结点的时候要改变头...
  • 头指针、头结点、首元结点概念区别

    万次阅读 多人点赞 2018-06-11 14:34:51
    转自:https://blog.csdn.net/liangxingda/article/details/52755800链表中第一个结点的存储位置叫做头指针,那么整个...“链表中第一个结点的存储位置叫做头指针”,如果链表有头结点,那么头指针就是指向头结点...
  • 头指针和头结点的区别

    万次阅读 多人点赞 2015-05-24 17:50:17
    头指针和头结点的区别: 头指针: --头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针 --头指针具有标识作用,所以头指针冠以链表的名字(指针变量的名字) --无论链表是否为空,头...
  • 头结点:在单链表的第一个结点之前附加一个结点,称为头结点。 (通常头结点的data域可以为空)。 带头结点的优点: 1、更快删除/插入第一个结点 2、统一空表和非空表的处理 ...
  • 头指针:一个普通的指针,它的特点是永远指向链表第一个节点的...对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题,有了头结点之后头指针指向头结点,不论链表是否为空,头指针总是非空。...
  • 带头结点的优点: 1、更快删除/插入第一个结点 2、统一空表和非空表的处理 不带头节点: p1->p2->p3 ->p1->p2->p3-> p1… 我们先创建指针,初始化的时候只需要将指针赋NULL就可以了;大家...
  • Python实现单链表(带头结点

    千次阅读 2021-02-09 11:04:30
    为了操作上的方便,在单链表第一个结点之前增加一个结点,称为头结点头结点的数据域可以不设任何信息,也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。 不管带不带头结点,头指针始终指向...
  • 下面列举出头结点与没有头结点链表的区别,以便使用时很好的选择! 1. 头结点的数据域可以不存储任何信息,也可以存储线性表的长度等附加信息,头结点的指针域存储第一个元素结点的地址,即首元结点的存储地址。若...
  • 在初学数据结构单链表的时候,对于链表的的头指针和头结点之间的区别和联系不是很清楚,后来查阅了一些资料,根据自己的理解大概整理了一下这两者之间的关系,主要就是下面这几点: 1.头指针表明了链表的起点,可以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 218,810
精华内容 87,524
关键字:

头结点