精华内容
下载资源
问答
  • 单链表中增加一个头结点目的
    2022-04-26 20:55:23

    单链表设置头结点的目的是为了方便运算的实现,主要好处体现在:

    第一,有头结点后,插入和删除数据元素的算法统一了,不再需要判断是否在第一个元素之前插入或删除第一个元素;

    第二,不论链表是否为空,其头指针是指向头结点的非空指针,链表的头指针不变,因此空表和非空表的处理也就统一了。
     

    更多相关内容
  • 单链表为什么要设置头结点

    万次阅读 多人点赞 2018-09-25 16:15:00
    单链表为什么要设置头结点 转自https://www.cnblogs.com/youxin/p/3279391.html 链表第一个结点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点,其实就是上一...

    单链表为什么要设置头结点

    转自https://www.cnblogs.com/youxin/p/3279391.html

    链表中第一个结点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点,其实就是上一个的后继指针指向的位置。

    这里有个地方要注意,就是对头指针概念的理解,这个很重要。“链表中第一个结点的存储位置叫做头指针”,如果链表有头结点,那么头指针就是指向头结点数据域的指针。画一个图吧。

     

    头指针就是链表的名字。头指针仅仅是个指针而已。

    • 头结点是为了操作的统一与方便而设立的,放在第一个元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等)。
    • 有了头结点后,对在第一个元素结点前插入结点和删除第一个结点,其操作与对其它结点的操作统一了。
    • 首元结点也就是第一个元素的结点,它是头结点后边的第一个结点。
    • 头结点不是链表所必需的。
    • 是的,对于头指针,我们也可以有相应的理解了。
    • 在线性表的链式存储结构中,头指针是指链表指向第一个结点的指针,若链表有头结点,则头指针就是指向链表头结点的指针。
    • 头指针具有标识作用,故常用头指针冠以链表的名字。
    • 无论链表是否为空,头指针均不为空。头指针是链表的必要元素。
    •  
      单链表也可以没有头结点。如果没有头结点的话,那么单链表就会变成这样:

    typdef struct LNode{

    int data,

    LinkList *next;

    }LNode,*LinkList;

    LinkList head=new LNode();

    head->next=null;

    插入n个元素

    LinkList p=head;

    for(int i=0;i<n;i++)

     {

            LinkList q=new LNode();

            q->data=i; q->next=null;

            p->next=q;

    }

     为了使空链表与非空链表处理一致,我们通常设一个头结点

     

     

     转的一篇文章:

    单链表带头结点&不带头结点

    Node *head;  //声明头结点
     
    带头结点初始化

    void InitList(Node **head){

         *head=(Node *)malloc( sizeof(Node));
         (*head)->next=NULL;
    }
     
    带头结点尾插入,统一操作
    方式一:
    void CreatList(Node **head){
         Node *r=*head,*s;
         int a;
         while(scanf("%d",&a)){
              if(a!=0){
                   s=(Node *)malloc(sizeof(Node));
                   s->value=a;
                   r->next=s;
                   r=s;    
              }
              else{    
                   r->next=NULL;
                   break;    
              }
         }
    }
    调用CreatList(&head);
     
    方式二:
    void CreatList(Node *head){
         Node *r=head,*s;
         ... //下面的都一样
    }
    调用CreatList(head);
     
    ------------------------------------------------------------------------------------------------------
     
    不带头结点初始化
    方式一:
    void InitList(Node **head){
         *head=NULL;
    }
    调用InitList(&head);
     
    方式二:
    void InitList(Node *head){
         head=NULL;
    }
    调用InitList(head);
     
    不带头结点尾插入,第一个节点与其他节点分开操作
    void CreatList(Node  **head){
         Node *p,*t;         /*p工作指针,t临时指针*/
         int a,i=1;
         while(scanf("%d",&a)){
              if(a!=0){
                   t=(Node *)malloc(sizeof(Node));
                   t->value=a;
                   if(i==1){
                        *head=t;    
                   }
                   else{
                        p->next=t;
                   }
                   p=t;
              }
              else{    
                   p->next=NULL;
                   break;    
              }
              i++;
         }
    }
    调用CreatList(&head);
     
     
    一、两者区别:
         1、不带头结点的单链表对于第一个节点的操作与其他节点不一样,需要特殊处理,这增加了程序的复杂性和出现bug的机会,因此,通常
              在单链表的开始结点之前附设一个头结点。
         2、带头结点的单链表,初始时一定返回的是指向头结点的地址,所以一定要用二维指针,否则将导致内存访问失败或异常。
         3、带头结点与不带头结点初始化、插入、删除、输出操作都不样,在遍历输出链表数据时,带头结点的判断条件是while(head->next!=NULL),
              而不带头结点是while(head!=NULL),虽然头指针可以在初始时设定,但是如1所述,对于特殊情况如只有一个节点会出现问题。
             
     
    二、为什么不带头结点初始化有2种方式,而带头结点只有1种方式呢?
     
         因为不带头结点声明Node *head 时;C编译器将其自动初始化为NULL,于是根本不需要调用InitList(head);也即不带头结点的初始化
    是个伪操作。而带头结点的初始化在堆开辟了一段内存,需要修改head指针变量指向的地址(即head的值),所以要修改head的值,必须传保
    存head变量的地址(即二维指针)。而直接调用CreatList(head);相当于传head变量的值,函数修改的是head的副本,无法真正改变head的值。 
     
         注:这里可以将head指针看成一个变量(不管它保存的是地址),就比较好理解了。
          
     
    三(key)、其实本质上还是传值,传址的问题,只不过指针本身保存的地址,让这个过程变得有点纠结。在函数调用需要修改指针变量的指向(value)时,
     应该传递指针变量的地址(address)。
          另外,对于函数的形参是指针时,只要该参数不在左边(即都是右值操作),二维指针(形参)就可以简化为一维指针。如上面带头结点的尾插
    简化版本。

    posted on 2018-09-25 16:15 Magic_chao 阅读(...) 评论(...) 编辑 收藏

    展开全文
  • 本篇博客主要是对线性链表的基本实现,因此无法摆脱链表的基本缺点,比如...本篇博客将网络上对单链表的各种操作进行实现,方便大家学习,如有错误,不吝指正! 一、概念 线性表的链式存储结构的特点使用一组...

    本篇博客主要是对线性链表的基本实现,因此无法摆脱链表的基本缺点,比如无法快速定位前驱、无法快速确定元素个数等等。当然优点是能够快速对链表进行学习。本篇博客将网络上对单链表的各种操作进行实现,方便大家学习,如有错误,不吝指正!

    一、概念

    线性表的链式存储结构的特点使用一组任意的存储单元存储线性表的数据元素。包含两个域:数据域和指针域。

    ① n个节点离散分布,彼此通过指针相联系。
    ② 除头节点和尾节点外,每个节点只有一个前驱节点和一个后续节点。
    ③ 头节点没有前驱节点,尾节点没有后继节点。

    注意:
    头节点的数据类型和首节点类型一样,头节点并不存放有效数据,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。
    加头节点的目的是方便对链表的操作,比如在链表头部进行节点的删除、插入。
    头指针:指向头节点的指针变量。这里以*head进行标识。

    #define ElemType int
    //--------线性表的单链表存储结构--------
    typedef struct LNode
    {
        ElemType data;
        struct LNode *next;
    }LNode;
    

    typedef LNode* LinkList;

    二、函数实现的难点

    由于本篇文章主要是学习单向链表的基本实现,因此这里将遇到的重难点记录下来,方便复习回顾。

    //创建一个头结点
    void InitList(LinkList *head)
     

    该函数主要是创建一个头结点,和我们定义的数据结构对应。如果线性表为空表,则头结点的指针域为“空”。
    也就是说,我们要明白头结点和第一个结点意义是不同的,头结点之后的结点是第一个结点。

    //头插法建立单链表
    void createListH(LinkList *head)
    //尾插法建立单链表
    void createListrR(LinkList *head)
     

    在头结点建立的基础上,我们可以使用头插法或者尾插法进行链表的建立。头插法主要是在头结点和第一个结点直接插入新的结点;尾插法是在尾结点后插入新的结点。

    //特定下标处插入值
    bool insert(LinkList *head, int pos, ElemType val)
    // 删除某个节点
    bool listDelete(LinkList *head, int pos)
     

    在某个特定下标处插入一个结点或者删除一个结点。插入值时需要找到pos-1处,将新的结点尾插;删除结点时找到pos-1处,使其指向pos的next,同时释放pos处结点。
    其实单链表“位序”的概念已淡化,这里只是将其实现,加深对单链表的理解。

    //1.判断非空 2.删除头结点之后第一个结点
    void pop_front(LinkList *head)
    //1.判断非空 2.删除倒数第一个结点
    void pop_back(LinkList *head)
     

    无论是尾删还是头删,首先要考虑链表是否为空,然后找到相应的位置删除结点。
    通过上面四个函数的实现,我们可以发现插入和删除时,最重要的是找到指向想要位置的前驱,而并不是指向想要位置的指针。比如pop_back()函数,虽然我们想要删除尾结点,但最重要的是找到倒数第二个结点,这里我们通过一个临时变量寄存。

    //单链表中数据节点的个数
    int listLength(LinkList *head)
    //链表是否为空
    bool is_empty(LinkList *head)
    //升序排序
    void sort(LinkList *head)
    //查找值
    LNode* find(LinkList *head, ElemType key)
    //仅显示,不修改
    void showList(LinkList head)
     

    这些函数都很简单,这里都不详述。
    综上,我们可以看到,单链表的优势在于插入和删除。如果实现随机访问,元素个数等,链表就要诸多不便了。

    三、代码

    再次重申,本篇文章对单链表的操作都是在建立头结点的基础上,就像一个火车头和后面多节车厢一样,无论后面车厢如何添加、删除,我们的火车头永远是“固定”的。

    #include <stdio.h>
    #include <assert.h>
    #include <malloc.h>
    

    #define ElemType int

    typedef struct LNode
    {
    ElemType data;
    struct LNode *next;
    }LNode;

    typedef LNode* LinkList;

    //创建一个头结点
    void InitList(LinkList head)
    {
    head = (LNode )malloc(sizeof(LNode));
    assert(head != NULL);

    (<span class="hljs-subst">*</span>head)<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> <span class="hljs-built_in">NULL</span>;
    

    }

    //头插法建立单链表
    void createListH(LinkList head)
    {
    for(int i=1;i<=10;i++)
    {
    LNode s = (LNode *)malloc(sizeof(LNode)); //s为新创建结点
    assert(s!=NULL);

        s<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span> <span class="hljs-subst">=</span> i;
        s<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> (<span class="hljs-subst">*</span>head)<span class="hljs-subst">-&gt;</span>next;
    
        (<span class="hljs-subst">*</span>head)<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> s;
    }
    

    }

    //尾插法建立单链表
    void createListrR(LinkList head)
    {
    LNode p = *head;

    for(int i<span class="hljs-subst">=</span><span class="hljs-number">1</span>;i<span class="hljs-subst">&lt;=</span><span class="hljs-number">10</span>;i<span class="hljs-subst">++</span>)
    {
        LNode <span class="hljs-subst">*</span>s <span class="hljs-subst">=</span> (LNode <span class="hljs-subst">*</span>)malloc(sizeof(LNode));  <span class="hljs-comment">//s为新创建结点</span>
        assert(s<span class="hljs-subst">!=</span><span class="hljs-built_in">NULL</span>);
    
        s<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span> <span class="hljs-subst">=</span> i;
        s<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
        p<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> s;
    
        p <span class="hljs-subst">=</span> s; <span class="hljs-comment">//指向最后一个结点地址</span>
    }
    

    }

    //单链表中数据节点的个数
    int listLength(LinkList head)
    {
    LNode p = *head;

    int count<span class="hljs-subst">=</span><span class="hljs-number">0</span>;
    
    <span class="hljs-keyword">while</span>(p<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">!=</span> <span class="hljs-built_in">NULL</span>)
    {
        p <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
        count <span class="hljs-subst">++</span>;
    }
    
    <span class="hljs-keyword">return</span> count;
    

    }

    //链表是否为空
    bool is_empty(LinkList head)
    {
    return ((head)->next == NULL);
    }
    //升序排序
    void sort(LinkList head)
    {
    LNode p,*q;
    ElemType temp;

    for (p <span class="hljs-subst">=</span>(<span class="hljs-subst">*</span>head)<span class="hljs-subst">-&gt;</span>next; p <span class="hljs-subst">!=</span> <span class="hljs-built_in">NULL</span>; p <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next)
    {
         for (q <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next; q <span class="hljs-subst">!=</span> <span class="hljs-built_in">NULL</span>; q <span class="hljs-subst">=</span> q<span class="hljs-subst">-&gt;</span>next)
        {
           <span class="hljs-keyword">if</span> (p<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span> <span class="hljs-subst">&gt;</span> q<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span>)
            {
                temp <span class="hljs-subst">=</span> q<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span>;
                q<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span> <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span>;
                p<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span> <span class="hljs-subst">=</span> temp;
            }
        }
    }
    

    }

    //特定下标处插入值
    bool insert(LinkList head, int pos, ElemType val)
    {
    int n = 0;
    LNode p = *head;
    while (n < pos && p != NULL)
    {
    n++;
    p = p->next;
    }
    if (n != pos || NULL == p)
    {
    return false;
    }

    LNode <span class="hljs-subst">*</span>pNew <span class="hljs-subst">=</span> (LNode <span class="hljs-subst">*</span>)malloc(sizeof(LNode));
    <span class="hljs-keyword">if</span> (<span class="hljs-built_in">NULL</span> <span class="hljs-subst">==</span> pNew)
    {
        printf(<span class="hljs-string">"Error in dynamic allocating memory!"</span>);
    }
    pNew<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span> <span class="hljs-subst">=</span> val;
    pNew<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
    p<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> pNew;
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
    

    }

    // 删除某个节点
    bool listDelete(LinkList head, int pos)
    {
    int n = 0;
    LNode p = *head;

    <span class="hljs-keyword">while</span> (n <span class="hljs-subst">&lt;</span> pos <span class="hljs-subst">&amp;&amp;</span> p <span class="hljs-subst">!=</span> <span class="hljs-built_in">NULL</span>)
    {
        n<span class="hljs-subst">++</span>;
        p <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
    }
    <span class="hljs-keyword">if</span> (n <span class="hljs-subst">!=</span> pos <span class="hljs-subst">||</span> <span class="hljs-built_in">NULL</span> <span class="hljs-subst">==</span> p)
    {
        <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    }
    <span class="hljs-comment">//判断位置合法</span>
    <span class="hljs-keyword">if</span>(p<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">==</span> <span class="hljs-built_in">NULL</span>)
    {
        <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    }
    LNode <span class="hljs-subst">*</span>q <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
    p<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next<span class="hljs-subst">-&gt;</span>next;
    free(q);
    
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
    

    }

    LNode find(LinkList head, ElemType key)
    {
    LNode p = head;
    //为NULL或找到p
    while (p != NULL && p->data != key) { p= p->next; }

    <span class="hljs-keyword">return</span> p;
    

    }

    //1.判断非空 2.删除头结点之后第一个结点
    void pop_front(LinkList head)
    {
    if((head)->next == NULL)
    {
    printf(“error: seqList is empty\n”);
    return;
    }

    LNode <span class="hljs-subst">*</span>q <span class="hljs-subst">=</span> (<span class="hljs-subst">*</span>head)<span class="hljs-subst">-&gt;</span>next;
    
    (<span class="hljs-subst">*</span>head)<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> q<span class="hljs-subst">-&gt;</span>next;
    free(q);
    

    }
    //1.判断非空 2.删除倒数第一个结点
    void pop_back(LinkList head)
    {
    if((head)->next == NULL)
    {
    printf(“error: seqList is empty\n”);
    return;
    }

    LNode <span class="hljs-subst">*</span>p <span class="hljs-subst">=</span> <span class="hljs-subst">*</span>head;
    LNode <span class="hljs-subst">*</span>prev <span class="hljs-subst">=</span> <span class="hljs-built_in">NULL</span>;<span class="hljs-comment">//存p结点之前的结点</span>
    <span class="hljs-keyword">while</span> (p<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">!=</span> <span class="hljs-built_in">NULL</span>)
    {
        prev <span class="hljs-subst">=</span> p;
        p <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
    }
    <span class="hljs-comment">//prev为倒数第二个结点</span>
    <span class="hljs-comment">//p为倒数第一个结点</span>
    prev<span class="hljs-subst">-&gt;</span>next <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
    free(p);
    

    }

    //仅显示,不修改
    void showList(LinkList head)
    {

    LNode <span class="hljs-subst">*</span>p <span class="hljs-subst">=</span> head<span class="hljs-subst">-&gt;</span>next;
    
    <span class="hljs-keyword">while</span>(p <span class="hljs-subst">!=</span> <span class="hljs-built_in">NULL</span>)
    {
        printf(<span class="hljs-string">"%d----&gt;"</span>,p<span class="hljs-subst">-&gt;</span><span class="hljs-built_in">data</span>);
        p <span class="hljs-subst">=</span> p<span class="hljs-subst">-&gt;</span>next;
    }
    printf(<span class="hljs-string">"Nul\n"</span>);
    

    }
    int main()
    {
    LinkList mylist;
    InitList(&mylist);
    printf(“create node in the head:\n”);
    createListH(&mylist);
    //尾插
    //createListrR(&mylist);
    //打印显示
    showList(mylist);

    <span class="hljs-comment">//插入值</span>
    insert(<span class="hljs-subst">&amp;</span>mylist,<span class="hljs-number">2</span>,<span class="hljs-number">88</span>);
    printf(<span class="hljs-string">"insert 88 at pos 2:\n"</span>);
    <span class="hljs-comment">//打印显示</span>
    showList(mylist);
    
    <span class="hljs-comment">//查找</span>
    <span class="hljs-keyword">if</span>(<span class="hljs-subst">!</span>find(<span class="hljs-subst">&amp;</span>mylist,<span class="hljs-number">3</span>))
    printf(<span class="hljs-string">"value 3 not found\n"</span>);
    <span class="hljs-comment">//长度</span>
    printf(<span class="hljs-string">"length:%d\n"</span>, listLength(<span class="hljs-subst">&amp;</span>mylist));
    
    <span class="hljs-comment">//头删</span>
    pop_front(<span class="hljs-subst">&amp;</span>mylist);
    <span class="hljs-comment">//打印显示</span>
    printf(<span class="hljs-string">"delete head element:\n"</span>);
    showList(mylist);
    
    <span class="hljs-comment">//尾删</span>
    pop_back(<span class="hljs-subst">&amp;</span>mylist);
    <span class="hljs-comment">//打印显示</span>
    printf(<span class="hljs-string">"delete tail element:\n"</span>);
    showList(mylist);
    
    <span class="hljs-comment">//删除下标为2</span>
    <span class="hljs-keyword">if</span>(listDelete(<span class="hljs-subst">&amp;</span>mylist,<span class="hljs-number">2</span>)) printf(<span class="hljs-string">"delete success\n"</span>);
    <span class="hljs-keyword">else</span> printf(<span class="hljs-string">"delete failed\n"</span>);
    <span class="hljs-comment">//打印显示</span>
    printf(<span class="hljs-string">"delete value at pos 10:\n"</span>);
    showList(mylist);
    
    <span class="hljs-comment">//升序排序</span>
    sort(<span class="hljs-subst">&amp;</span>mylist);
    printf(<span class="hljs-string">"sort ascend:\n"</span>);
    <span class="hljs-comment">//打印显示</span>
    showList(mylist);
    
    <span class="hljs-comment">//判断是否为空</span>
    <span class="hljs-keyword">if</span>(is_empty(<span class="hljs-subst">&amp;</span>mylist)) printf(<span class="hljs-string">"linklist is empty\n"</span>);
    <span class="hljs-keyword">else</span>  printf(<span class="hljs-string">"linklist is not empty\n"</span>);
    
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    

    }

    四、验证

    在main函数中,我们首先建立了头结点,然后使用前插法建立单链表。之后就是利用我们所实现的函数进行一系列的验证:
    这里写图片描述

    展开全文
  • 问题:在单链表中使用“头结点”,这个哑结点始终是链表的第一个元素,这个技巧的利与弊? 链表第一个结点的存储位置叫做头指针,那么整个链表的存取就必须从头指针开始进行了。之后的每一个结点,其实就是上一个...

    问题:在单链表中使用“头结点”,这个哑结点始终是链表的第一个元素,这个技巧的利与弊?

    链表中第一个结点的存储位置叫做头指针,那么整个链表的存取就必须从头指针开始进行了。之后的每一个结点,其实就是上一个的后继指针指向的位置。
    链表中第一个结点的存储位置叫做头指针
    头指针和头结点不同,头结点即第一个结点,头指针是指向第一个结点的指针。链表中可以没有头结点,但不能没有头指针。
    如果链表有头结点,那么头指针就是指向头结点数据域的指针。

    单链表也可以没有头结点,没有头结点的单链表

    • 头结点是为了操作的统一与方便而设立的,放在第一个元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等)。
    • 有了头结点后,对在第一个元素结点前插入结点和删除第一个结点,其操作与对其它结点的操作统一了。
    • 首元结点也就是第一个元素的结点,它是头结点后边的第一个结点。
    • 头结点不是链表所必需的
    • 在线性表的链式存储结构中,头指针是指链表指向第一个结点的指针,若链表有头结点,则头指针就是指向链表头结点的指针。
    • 头指针具有标识作用,故常用头指针冠以链表的名字。
    • 无论链表是否为空,头指针均不为空,头指针是链表的必要元素

    为了使空链表与非空链表处理一致,我们通常设一个头结点。

    一、两者区别:
    1、不带头结点的单链表对于第一个节点的操作与其他节点不一样,需要特殊处理,这增加了程序的复杂性和出现bug的机会,因此,通常
    在单链表的开始结点之前附设一个头结点。
    2、带头结点的单链表,初始时一定返回的是指向头结点的地址,所以一定要用二维指针,否则将导致内存访问失败或异常。
    3、带头结点与不带头结点初始化、插入、删除、输出操作都不样,在遍历输出链表数据时,带头结点的判断条件是while(head->next!=NULL),
    而不带头结点是while(head!=NULL),虽然头指针可以在初始时设定,但是如1所述,对于特殊情况如只有一个节点会出现问题。



     

    展开全文
  • 本文以管理学生的姓名、学号为背景,归纳了带头结点单链表的初始化、增加结点插和尾插)、遍历输出、删除结点、更正结点数据和逆置链表(三指针)的方法
  • 题目:假设有两个按元素值递增次序排列的线性表,均以单链表的形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的...设f(L,x)的功能是:删除以L为首结点指针的单链表中所有值等于x的结点,显然有...
  • 单链表头结点的作用

    千次阅读 2014-03-27 11:57:57
    数据结构在单链表的开始结点之前附设一个类型相同的结点,称之为头结点头结点的数据域可以不存储任何信息,头结点的指针域存储指向开始结点的指针(即第一个元素结点的存储位置)。 作用: 1、防止单链表是...
  • 这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架...带头结点的单链表和普通的单链表差不多,只是普通单链表的第一个结点之前增加一个特殊的结点,这个结点就叫做头结点带头结点的单链表...
  • 这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架...带头结点的单链表和普通的单链表差不多,只是普通单链表的第一个结点之前增加一个特殊的结点,这个结点就叫做头结点带头结点的单链表...
  • 为什么要设置链表头结点

    千次阅读 多人点赞 2018-10-20 11:59:18
    A:数据结构在单链表的开始结点之前附设一个类型相同的结点,称之为头结点头结点的数据域可以不存储任何信息,头结点的指针域存储指向开始结点的指针(即第一个元素结点的存储位置)。 A:头结点其实就是一个...
  • 头结点的作用

    千次阅读 2021-01-13 15:59:56
    数据结构在单链表的开始结点之前附设一个类型相同的结点,称之为头结点头结点的数据域可以不存储任何信息,头结点的指针域存储指向开始结点的指针(即第一个元素结点的存储位置)。 作用 1、防止单链表是空的...
  • 本文以管理学生的姓名、学号为背景,归纳了不带头结点单链表的初始化、增加结点插和尾插)、遍历输出、删除结点、更正结点数据和逆置链表(三指针)的方法
  • 统计单链表中的节点数

    千次阅读 2016-05-02 22:18:43
    实验一 线性表的基本操作的实现与应用 ...2、 有一个单链表的第一个节点指针为head,编程实现将该单链表逆置,即最后一个节点变成第一个节点,原来倒数第二个节点变成第二个节点,如此等等,逆置不能建立新的单链
  • 单链表是链表家族的一员,每个节点依旧由数据域(data)和指针域(next)组成,链表的具体概念下面有介绍:机器学习入坑者:程序员基本功——链表的基本概念​zhuanlan.zhihu.com基本结构:单链表的结构含有四个概念:...
  • 单链表实验报告

    千次阅读 2021-05-20 06:53:10
    《数据结构》实验报告二分校:学号:日期:班级:姓名:程序名: L2311.CPP一、上机...2. 从键盘输入1个整数,在单链表中查找该结点。若找到,则显示“找到了”;否则,则显示“找不到”。3. 从键盘输入2个整数,一...
  • 作业5-单链表

    千次阅读 2020-11-29 19:35:06
    具有N个结点单链表中, 访问结点增加结点的时间复杂度分别对应为O(1)和O(N)。(F) 1-2 若用链表来表示一个线性表,则表元素的地址一定是连续的。(F) 1-3 将长度分别为m,n的两个单链表合并为一个单链表的时间...
  • 增加头结点后,无论链表是否为空,头指针都是指向头结点的非空指针。 二、基本操作实现 1.初始化 单链表的初始化操作就是构造一个空表,如图: 我们需要进行如下步骤: (1)生成新结点作为头结点,用头指针L指向头...
  • 数据结构在单链表的开始结点之前附设一个类型相同的结点,称之为头结点头结点的数据域可以不存储任何信息,头结点的指针域存储指向开始结点的指针(即第一个元素结点的存储位置)。 作用 1、防止单链表是空的...
  • 一.从零写单链表的算法之尾部&头部插入节点

    万次阅读 多人点赞 2018-01-28 19:36:31
    ①数组所有元素类型必须相同 ②数组定义时必须明确指定数组元素的个数,且个数一般来说是不可改的。 ==如果希望数组的大小能够实时扩展。怎么解决那?== 譬如我刚开始定了一个元素个数是10,后来程序运行时...
  • 数组内存连续,链表不连续;更进一步说就是数组可能会造成内存浪费,但链表的内存利用率高;数组利用下标定位元素,时间复杂度为O(1),链表最坏情况下是O(n);即随机性查找上数组比链表更快。数组进行.....
  • 第二章作业题2-链表(1)

    万次阅读 2019-11-26 20:22:03
    具有N个结点单链表中,访问结点增加结点的时间复杂度分别对应为O(1)和O(N)。F 如果是顺序表,则访问为O(1),增加为O(N) 1-2 若用链表来表示一个线性表,则表元素的地址一定是连续的。F 链表不一定是连续...
  • 选择题 算法分析的目的是 ( ) 找出数据结构的合理性 找出算法输入和输出之间的关系 分析算法的易懂性和可靠性 分析算法的效率以求改进 参考答案 D 在单链表中增加头结点目的是 ( ) 方便运算的 使单链表至少有一...
  • 在单链表指定位置增加一个数! 5.从单链表中删除指定位置的数! 6.从单链表中找出某一个指定的数! 7.将单链表中结点数据替换! 8.输出目前的单链表中的每个数据! 0:退出! 二 代码实例 #include<stdio.h&...
  • 单链表2.1 单链表初始化2.2 单链表插入数据2.3 单链表删除数据2.4 单链表读取数据2.5 插法整体创建链表2.6 尾插法整体创建链表2.7 单链表整体删除3. 单链表与顺序存储结构优缺点4. 循环链表4.1 循环链表定义4.2 ...
  • 然后此篇文章与其他单链表文章不同的是,省略了单链表的操作,专注于循环创建链表的工作。对于链表的基本操作,可能会下篇文章叙述。 C语言语法不太熟练也没关系,我上一次用C是一年前,也是写数据结构。语
  • 1.关于线性表的顺序存储结构和链式存储结构的描述,正确的是( )。  Ⅰ.线性表的顺序存储结构优于其链式存储结构  Ⅱ.链式存储结构比顺序存储结构能更方便地表示各种逻辑结构  Ⅲ.如频繁使用插入和删除结点...
  • 单链表由一系列不必内存连续的结点组成,每一个结点均含有一个表元素和指向包含该元素后继元的结点的指针链。本实验实现单链表和它的一些相关应用。 (1)实验目的 (1)掌握单链表的组织结构; (2)掌握单链表...
  • //对成员属性进行封装,set方法包含合法性验证 string getFlight(); static bool isFlightRight(string flight); bool setFlight(string flight); string getType(); static bool isTypeRight(string type...
  • 单链表的常见面试题有如下: 1.求单链表中有效节点...//head 为头结点 public static int getLength(StudentNode head){ if (head.next == null){ //说明这是一个空链表 return 0; } int length =0; //定义了一

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,228
精华内容 1,691
关键字:

在单链表中增加头结点的目的