• C语言单链表的算法之插入节点

    一：访问各个节点中的数据

            （1）访问链表中的各个节点的有效数据，这个访问必须注意不能使用p、p1、p2，而只能使用phead

            （2）只能用头指针不能用各个节点自己的指针。因为在实际当中我们保存链表的时候是不会保存各个节点的指针的，只能通过头指针来访问链表节点

            （3）前一个节点的pNEXT指针能帮助我们找到下一个节点

    1. #include         
    2. #include         
    3. #include         
    4.  
    5. //构建一个链表的节点
    6. struct node
    7. {
    8.  
    9.     int datas;                      //有效数据
    10.     struct node *pNEXT;             //指向下一个节点的指针
    11.     
    12.  
    13. };
    14.  
    15. int main(void)
    16. {
    17.  
    18.     //定义头指针
    19.     struct node *phead = NULL;
    20.  
    21.     //创建一个链表节点
    22.     struct node *p = (struct node *)malloc(sizeof(struct node));        
    23.  
    24.     if(NULL == p)                //检查申请结果是否正确
    25.         {
    26.             printf("malloc error!\n");        
    27.  
    28.             return -1;
    29.  
    30.         }
    31.  
    32.       //memset(p,0,sizeof(struct node));          
    33.       bzero(p,sizeof(struct node));            //清理申请到的堆内存
    34.         
    35.       //填充节点
    36.       p->datas = 1;                            //填充数据区
    37.       p->pNEXT = NULL;                         //将来要执行下一个节点的首地址
    38.         
    39.       phead = p;                              //将本节点和前面的头指针关联起来
    40.  
    41.  
    42.      //创建一个链表节点并和上一个节点关联起来
    43.     struct node *p1 = (struct node *)malloc(sizeof(struct node));        
    44.  
    45.     if(NULL == p1)                //检查申请结果是否正确
    46.         {
    47.             printf("malloc error!\n");        
    48.  
    49.             return -1;
    50.  
    51.         }
    52.  
    53.       //memset(p,0,sizeof(struct node));          
    54.       bzero(p1,sizeof(struct node));            //清理申请到的堆内存
    55.         
    56.       //填充节点
    57.       p1->datas = 1;                            //填充数据区
    58.       p1->pNEXT = NULL;                         //将来要执行下一个节点的首地址
    59.         
    60.       p-pNEXT>= p1;                            //将本节点和前面的节点关联起来
    61.  
    62.     
    63.         //再创建一个链表节点并和上一个节点关联起来
    64.     struct node *p2 = (struct node *)malloc(sizeof(struct node));        
    65.  
    66.     if(NULL == p2)                //检查申请结果是否正确
    67.         {
    68.             printf("malloc error!\n");        
    69.  
    70.             return -1;
    71.  
    72.         }
    73.  
    74.       //memset(p2,0,sizeof(struct node));          
    75.       bzero(p2,sizeof(struct node));            //清理申请到的堆内存
    76.         
    77.       //填充节点
    78.       p2->datas = 1;                            //填充数据区
    79.       p2->pNEXT = NULL;                         //将来要执行下一个节点的首地址
    80.             
    81.       p1-pNEXT>= p2;                           //将本节点和前面的节点关联起来
    82.  
    83.  
    84.       //访问链表节点的第一个节点的有效数据
    85.  
    86.         printf("phead->p->datas = %d\n",phead->datas);
    87.         printf("p->datas =  %d\n",p->datas);
    88.      
    89.      //访问链表节点的第二个有效数据
    90.         printf("phead->pNEXT->datas =%d\n",phead->pNEXT->datas);
    91.         printf("p1->datas = %d\n",p1->datas);
    92.    
    93.      
    94.      //访问链表节点的第三个有效数据
    95.         printf("phead->pNEXT->datas = %d\n",phead->pNEXT->pNEXT->datas);
    96.         printf("p2->datas = %d\n",p2->datas);
    97.  
    98.  
    99.      
    100.  
    101.  
    102.  
    103.   
    104.  
    105.    
    106.  
    107.       return 0;
    108.  
    109.  
    110. }

    二：将创建的节点封装成一个函数

            （1）封装时的关键就是函数的接口（函数参数和返回值）的设计

               

    1. #include         
    2. #include         
    3. #include         
    4.  
    5. //构建一个链表的节点
    6. struct node
    7. {
    8.  
    9.     int datas;                      //有效数据
    10.     struct node *pNEXT;             //指向下一个节点的指针
    11.     
    12.  
    13. };
    14.  
    15. /****************************************
    16. 函数名：create
    17. 作用：创建一个链表节点
    18. 返回值：p 指针，指针指向本函数创建的一个节点的首地址
    19. 参数：
    20. ****************************************/
    21. struct node *create(int a)
    22. {
    23.  
    24.  
    25.     struct node *p = (struct node *)malloc(sizeof(struct node));
    26.  
    27.     if(NULL == p)
    28.         {
    29.             printf("malloc error!\n");
    30.  
    31.             return NULL;
    32.  
    33.         }
    34.  
    35.       memset(p,0,sizeof(struct node));  
    36.       //bzero(p,sizeof(struct node));
    37.  
    38.       p->datas = a;
    39.       p->pNEXT = NULL;
    40.  
    41.  
    42.       return p;
    43.  
    44.  
    45.  
    46.  
    47.  
    48.  
    49.  
    50. int main(void)
    51. {
    52.  
    53.     //定义头指针
    54.     struct node *phead = NULL;
    55.      
    56.     
    57.     //调用函数实现创建链表节点并将数据放到有效数据区                                
    58.     phead = create(100);          //调用一次函数，创建一个链表节点返回节点首地址给头指针
    59.     phead->pNEXT = create(200);   //再次创建一个链表节点返回节点首地址给上一个节点的指针 
    60.     phead->pNEXT->pNEXT = create(300); //同上
    61.  
    62.  
    63.     
    64.     printf("phead->p->datas = %d\n",phead->datas);        
    65.     //printf("p->datas =  %d\n",p->datas);        //使用功能函数创建链表节点就不能再使用
    66.                                                   //节点指针访问有效数据区，只能通过头    
    67.                                                   //指针                
    68.  
    69.     printf("phead->pNEXT->datas =%d\n",phead->pNEXT->datas);
    70.     //printf("p1->datas = %d\n",p1->datas);
    71.  
    72.     printf("phead->pNEXT->datas = %d\n",phead->pNEXT->pNEXT->datas);
    73.     //printf("p2->datas = %d\n",p2->datas);
    74.       
    75.  
    76.  
    77.  
    78.   
    79.  
    80.    
    81.  
    82.       return 0;
    83.  
    84.  
    85. }
    86.  
    87.  
    88.  
    89.  
    90.  
    91.  
    92.  
    93.  
    94. }

     运行结果：

         

    三：从链表头部插入新节点

      （1）思路：第一步：新节点的next指向原来的第一个节点

                          第二步：头指针的next指向新节点

                          第三步：头节点的计数要加一     

                         

      （2）代码示例：

            

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. struct node
    6. {
    7.  
    8.     int datas;
    9.     struct node *pNEXT;
    10.  
    11.  
    12. };
    13.  
    14. struct node *create(int a)
    15. {
    16.  
    17.  
    18.     struct node *p = (struct node *)malloc(sizeof(struct node));
    19.  
    20.     if(NULL == p)
    21.         {
    22.             printf("malloc error!\n");
    23.  
    24.             return NULL;
    25.  
    26.         }
    27.  
    28.       memset(p,0,sizeof(struct node));  
    29.       //bzero(p,sizeof(struct node));
    30.  
    31.       p->datas = a;
    32.       p->pNEXT = NULL;
    33.  
    34.  
    35.       return p;
    36.  
    37.  
    38. }
    39.  
    40.  
    41.  
    42. void insert_tail(struct node *phead,struct node *new)
    43. {
    44.  
    45.     struct node *p = phead;
    46.     int cat = 0;
    47.     while(NULL !=  p->pNEXT)
    48.         {
    49.  
    50.  
    51.             p = p->pNEXT;
    52.             cat++;
    53.  
    54.         }
    55.  
    56.         p->pNEXT = new;
    57.         phead->datas = cat +1;
    58.  
    59.  
    60. }
    61.  
    62.  
    63.  
    64. void insert_head(struct node *head,struct node *new)
    65. {
    66.  
    67.     new->pNEXT =  head->pNEXT;            //新节点的next指向之前的第一个节点
    68.  
    69.     head->pNEXT = new;                    //头节点的next指向新节点地址
    70.     
    71.     head->datas += 1;                    //头节点的计数加一
    72.  
    73. }
    74.  
    75.  
    76.  
    77. int main(void)
    78. {
    79.     struct node *phead = create(0);
    80.  
    81.     insert_head(phead,create(1));
    82.     insert_head(phead,create(2));
    83.     insert_head(phead,create(3));
    84.  
    85.  
    86.  
    87.  
    88.     /*
    89.     
    90.             phead = create(100);
    91.             phead->pNEXT = create(200);
    92.             phead->pNEXT->pNEXT = create(300);
    94.     */
    95.     
    96.  
    97.         printf("phead->p->datas = %d\n",phead->datas);
    98.         //printf("p->datas =  %d\n",p->datas);
    99.  
    100.         printf("phead->pNEXT->datas =%d\n",phead->pNEXT->datas);
    101.         //printf("p1->datas = %d\n",p1->datas);
    102.  
    103.         printf("phead->pNEXT->datas = %d\n",phead->pNEXT->pNEXT->datas);
    104.         //printf("p2->datas = %d\n",p2->datas);
    105.  
    106.         printf("phead->pNEXT->datas = %d\n",phead->pNEXT->pNEXT->pNEXT->datas);
    107.         //printf("p2->datas = %d\n",p2->datas);
    108.  
    109.       return 0;
    110.  
    111.  
    112. }

     运行结果：

            

    四：从链表尾部插入新节点

            （1）思路：从头指针往后开始遍历指针指向的地址判断是不是NILL，直到最后一个节点，因为最后一个节点的是指向NULL的，所以遍历结束，然后将最后一个节点的指针指向新创建的节点

    1. #include 
    2. #include 
    3. #include 
    4.  
    5.  
    6. //构建一个链表的节点
    7. struct node
    8. {
    9.  
    10.     int datas;
    11.     struct node *pNEXT;
    12.  
    13.  
    14. };
    15.  
    16.  
    17. //创建一个链表节点
    18. struct node *create(int a)
    19. {
    20.  
    21.  
    22.     struct node *p = (struct node *)malloc(sizeof(struct node));
    23.  
    24.     if(NULL == p)
    25.         {
    26.             printf("malloc error!\n");
    27.  
    28.             return NULL;
    29.  
    30.         }
    31.  
    32.       memset(p,0,sizeof(struct node));  
    33.       //bzero(p,sizeof(struct node));
    34.  
    35.       p->datas = a;
    36.       p->pNEXT = NULL;
    37.  
    38.  
    39.       return p;
    40.  
    41.  
    42. }
    43.  
    44.  
    45. //从尾部插入节点
    46. void insert_tail(struct node *phead,struct node *new)
    47. {
    48.  
    49.     struct node *p = phead;        //定义临时指针变量
    50.     
    51.     //循环遍历指针
    52.     while(NULL !=  p->pNEXT)
    53.         {
    54.  
    55.  
    56.             p = p->pNEXT;
    57.  
    58.         }
    59.  
    60.         p->pNEXT = new;    //节点尾部指针指向新节点
    61.  
    62.  
    63. }
    64.  
    65.  
    66.  
    67. int main(void)
    68. {
    69.     struct node *phead = create(100);        //由于实现尾部插入判断是否是最后一个节点
    70.                                              //所以如果将头指针指向NULL那么程序就出错了
    71.                                              //这里就先创建一个节点让头指针指向它
    72.  
    73.     insert_tail(phead,create(200));          //再从单链接尾部插入节点
    74.     insert_tail(phead,create(300));          //同上
    75.  
    76.  
    77.     /*
    78.     
    79.             phead = create(100);
    80.             phead->pNEXT = create(200);
    81.             phead->pNEXT->pNEXT = create(300);
    83.     */
    84.     
    85.  
    86.         printf("phead->p->datas = %d\n",phead->datas);
    87.         //printf("p->datas =  %d\n",p->datas);
    88.  
    89.         printf("phead->pNEXT->datas =%d\n",phead->pNEXT->datas);
    90.         //printf("p1->datas = %d\n",p1->datas);
    91.  
    92.         printf("phead->pNEXT->datas = %d\n",phead->pNEXT->pNEXT->datas);
    93.         //printf("p2->datas = %d\n",p2->datas);
    94.  
    95.       return 0;
    96.  
    97.  
    98. }

    （2）问题：因为我们在inserttail中直接默认了头指针指向的有一个节点，因此如果程序中直接
    定义了头指针后就直接insert tail就会报段错误。我们不得不在定义头指针之后先create_node
    创建一个新节点给头指针初始化，否则不能避免这个错误;但是这样解决让程序看起来逻辑有点
    不太顺，因为看起来第一个节点和后面的节点的创建、添加方式有点不同。 

    （3）链表还有另一种用法，就是把头指针指向的第一个节点作为头节点使用。头节点的特点是它紧跟在头指针后面；它的数据区是空的（有时候不是空的，用来存储链表节点个数）；指针部分指向下一个节点（第一个链表节点）

    1. #include 
    2. #include 
    3. #include 
    4.  
    5.  
    6. //构建一个链表的节点
    7. struct node
    8. {
    9.  
    10.     int datas;
    11.     struct node *pNEXT;
    12.  
    13.  
    14. };
    15.  
    16.  
    17. //创建一个链表节点
    18. struct node *create(int a)
    19. {
    20.  
    21.  
    22.     struct node *p = (struct node *)malloc(sizeof(struct node));
    23.  
    24.     if(NULL == p)
    25.         {
    26.             printf("malloc error!\n");
    27.  
    28.             return NULL;
    29.  
    30.         }
    31.  
    32.       memset(p,0,sizeof(struct node));  
    33.       //bzero(p,sizeof(struct node));
    34.  
    35.       p->datas = a;
    36.       p->pNEXT = NULL;
    37.  
    38.  
    39.       return p;
    40.  
    41.  
    42. }
    43.  
    44.  
    45. //从尾部插入节点
    46. void insert_tail(struct node *phead,struct node *new)
    47. {
    48.  
    49.     struct node *p = phead;        //定义临时指针变量
    50.     int cat = 0;                   //创建一个计数器变量 
    51.     
    52.     //循环遍历指针
    53.     while(NULL !=  p->pNEXT)
    54.         {
    55.  
    56.  
    57.             p = p->pNEXT;
    58.             cat++;                 //每循环一次加一
    59.  
    60.         }
    61.  
    62.         p->pNEXT = new;    //节点尾部指针指向新节点
    63.         phead->datas = cat +1;
    64.  
    65.  
    66. }
    67.  
    68.  
    69.  
    70. int main(void)
    71. {
    72.     struct node *phead = create(0);          //由于实现尾部插入判断是否是最后一个节点
    73.                                              //所以如果将头指针指向NULL那么程序就出错了
    74.                                              //这里就先创建一个头节点让头指针指向它
    75.  
    76.     insert_tail(phead,create(1));          
    77.     insert_tail(phead,create(2));
    78.     insert_tail(phead,create(3));
    79.              
    80.  
    81.  
    82.     /*
    83.     
    84.             phead = create(100);
    85.             phead->pNEXT = create(200);
    86.             phead->pNEXT->pNEXT = create(300);
    88.     */
    89.     
    90.  
    91.         printf("phead->p->datas = %d\n",phead->datas);            //节点数
    92.       
    93.  
    94.         printf("phead->pNEXT->datas =%d\n",phead->pNEXT->datas);  //第一个节点数据区数据
    95.    
    96.  
    97.         printf("phead->pNEXT->datas = %d\n",phead->pNEXT->pNEXT->datas);   //第二个
    98.    
    99.         
    100.          printf("phead->pNEXT->datas = %d\n",phead->pNEXT->pNEXT->pNEXT->datas);  //三
    101.         
    102.  
    103.       return 0;
    104.  
    105.  
    106. }

    运行 结果：链表节点数 3   第一个节点数据区为1   第二个为2 第三个为3

    （4）这样看来，头节点确实和其他节点不同。我们在创建一个链表时添加节点的方法也不同。头
    节点在创建头指针时一并创建并且和头指针关联起来;后面的真正的存储数据的节点用节点添加
    的函数来完成，譬如insert tail。

    （5）链表有没有头节点是不同的。体现在链表的插入节点、删除节点、遍历节点、解析链表的各
    个算法函数都不同。所以如果一个链表设计的时候就有头节点那么后面的所有算法都应该这样来
    处理:如果设计时就没有头节点，那么后面的所有算法都应该按照没有头节点来做。实际编程中
    两种链表都有人用，所以程序员在看别人写的代码时一定要注意看它有没有头节点

    注意：注意在写代码过程中的箭头符号，和说话过程中的指针指向。这是两码事，容易搞混箭头符号实质是用指针来访问结构体，所以箭头的实质是访问结构体中的成员。清楚的来说程序中的箭头和链表的连接没有任何的关系；链表中的节点通过指针指向来连接，编程中表现为赋值语句（用=来连接），实质是把最后一个节点的首地址，赋值给前一个节点中的pnext元素作为值

    链表可以从头部插入，也可以尾部插入，也可以两头插入。对链表来说几乎没有差别，但是有时候对业务逻辑有差别

  • 相关阅读:
    【JavaScript原型链prototype详解】
    verilog不常规用法
    设计模式与应用：迭代器模式
    StableSwarmUI 安装教程（详细）
    小啊呜产品读书笔记001：《邱岳的产品手记-14》第26讲 写好产品文档的诀窍 & 第27讲 产品案例分析： Quartz&Hooked的对话式交互
    【数组】最多能完成排序的块 数学
    小微企业可以申请高新技术企业吗？
    linux性能优化--性能追踪建议
    刷题日记【第十一篇】-笔试必刷题【小易的升级之路+找出字符串中第一个只出现一次的字符+微信红包+计算字符串的编辑距离】
    CUDA-矩阵乘2
  • 原文地址：https://blog.csdn.net/tmk1234567890/article/details/139854864