设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 无头结点单链表的插入
返回列表 发新帖
查看: 2016|回复: 6

[已解决]无头结点单链表的插入

[复制链接]
豌图酱
发表于 2017-8-29 12:24:40 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct link
  4. {
  5.         int data;
  6.         struct link *next;
  7. }*Linklist,Node;
  8. //在无结点的动态单链表上实现insert(L,i,b)
  9. int insert(Linklist L,int i,int b)                //L是头指针
  10. {

  12.         Linklist p,q;
  13.         int k=1;
  14.         p=L;
  15.         if(i<1) return 0;
  16.         //处理要插在表头的情况       
  17.         if(i==1)
  18.         {
  19.                 q = (Linklist)malloc(sizeof(Node));
  20.                 if(q==NULL)
  21.                         exit(0);
  22.                 q->data = b;
  23.                 q->next = p;
  24.                 L = q;
  25.         }
  26.         while(p&&k<i-1)
  27.         {
  28.                 p=p->next;
  29.                 k=k+1;
  30.         }
  31.         if(!p) return 0;
  32.         //建立新的结点
  33.         q = (Linklist)malloc(sizeof(Node));
  34.         if(q==NULL)
  35.                 exit(0);
  36.         q->data = b;
  37.        
  38.         //不插在表头时
  39.         q->next = p->next;
  40.         p->next = q;

  42.         return 1;
  43. }
  44. //建立无头节点链表
  45. void creatlist(Linklist L,int n)
  46. {
  47.         Linklist p;
  48.         int i=0;
  49.         L = (Linklist)malloc(sizeof(Node));
  50.         if(!L)
  51.         {
  52.                 printf("memory failed\n");
  53.                 exit(0);
  54.         }
  55.         L = NULL;
  56.         for(i=0;i<n;i++)
  57.         {
  58.                 p = (Linklist)malloc(sizeof(Node));
  59.                 if(!p)
  60.                         exit(0);
  61.                 scanf("%d",&(p->data));
  62.                 p->next = L;
  63.                 L = p;
  64.         }
  65.         /*调试
  66.         p = L;
  67.         for(i=0;i<10;i++)
  68.         {
  69.                 printf("%d\n",p->data);
  70.                 p = p->next;
  71.         }*/

  73. }
  74. int main()
  75. {
  76.         Linklist L,p;
  77.         int i;
  78.        
  79.         creatlist(L,10);
  80.         insert(L,5,7);
  81.         p = L;
  82.         for(i=0;i<11;i++)
  83.         {
  84.                 printf("%d\n",p->data);
  85.                 p = p->next;
  86.         }
  87.         return 0;
  88. }
复制代码

题目是要给一个无头结点的链表的第i的个元素前插入d；
因为是数据结构的题目，虽然有搜到其他答案，但是运行的时候总是会报错退出，请大家帮我看下问题在哪里。。。
经过测试，是insert函数的问题，但是不知道问题出在哪里~
最佳答案
月排行榜 / 总排行榜
guoxiaopeng
2017-8-31 09:15:50
本帖最后由 guoxiaopeng 于 2017-8-31 09:17 编辑

题主的根本问题在于忽略了一个细节：就是指针变量作为函数参数，本身也遵循值传递的原理，我们可以在函数里改变指针所指向变量的值，但是并不能改变指针变量本身的值，题主在创建链表的函数里改变了L的值，在create函数里边可以打印链表，但是当函数返回主函数时，L的值是没有改变的，要么为空，要么是一个野指针。下面就代码具体分析：
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct link
  4. {
  5.         int data;
  6.         struct link *next;
  7. }*Linklist,Node;
  8. //在无结点的动态单链表上实现insert(L,i,b)

  10. //这里第一个参数应该是Linklist*L(也就是一个二级指针)
  11. int insert(Linklist L,int i,int b)                //L是头指针
  12. {

  14.         Linklist p,q;
  15.         int k=1;
  16.         p=L;
  17.         if(i<1) return 0;
  18.         //处理要插在表头的情况        
  19.         if(i==1)
  20.         {
  21.                 q = (Linklist)malloc(sizeof(Node));
  22.                 if(q==NULL)
  23.                         exit(0);
  24.                 q->data = b;
  25.                 q->next = p;
  26.                 L = q;//题主在这里临时改变了L的值，但是当函数执行完毕后L还是当初传进来的值
  27.         }
  28.         while(p&&k<i-1)
  29.         {
  30.                 p=p->next;
  31.                 k=k+1;
  32.         }
  33.         if(!p) return 0;
  34.         //建立新的结点
  35.         q = (Linklist)malloc(sizeof(Node));
  36.         if(q==NULL)
  37.                 exit(0);
  38.         q->data = b;
  39.         
  40.         //不插在表头时
  41.         q->next = p->next;
  42.         p->next = q;

  44.         return 1;
  45. }
  46. //建立无头节点链表
  47. //这里同样的第一个参数应该是（Linklist*L）
  48. void creatlist(Linklist L,int n)
  49. {
  50.         Linklist p;
  51.         int i=0;
  52.         L = (Linklist)malloc(sizeof(Node));
  53.         if(!L)
  54.         {
  55.                 printf("memory failed\n");
  56.                 exit(0);
  57.         }
  58.         L = NULL;//不知题主这里是什么意思，L= NULL会将刚申请的内存丢掉，但这片内存又没有free，这回导致内存泄漏的（尽管只是一个），应该是L->next = NULL吧
  59.         for(i=0;i<n;i++)
  60.         {
  61.                 p = (Linklist)malloc(sizeof(Node));
  62.                 if(!p)
  63.                         exit(0);
  64.                 scanf("%d",&(p->data));
  65.                 p->next = L;
  66.                 L = p;//同样只是在该函数内部临时改变了L的值，函数执行完毕，L仍然是原来传进来时的值，这样所创建的链表被整个抛弃了，主函数里当然打印失败，这回泄漏的内存就不止一个了，而是一片
  67.         }
  68.         /*调试
  69.         p = L;
  70.         for(i=0;i<10;i++)
  71.         {
  72.                 printf("%d\n",p->data);
  73.                 p = p->next;
  74.         }*/

  76. }
  77. int main()
  78. {
  79.         Linklist L,p;//L,P都没有初始化，也就是是野指针，
  80.         int i;
  81.         
  82.         creatlist(L,10);
  83.         insert(L,5,7);
  84.         p = L;
  85.         for(i=0;i<11;i++)
  86.         {
  87.                 printf("%d\n",p->data);
  88.                 p = p->next;
  89.         }
  90.         return 0;
  91. }
复制代码


下面给出修正后的代码
/************************************************************************************************************************************************/
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct link
  4. {
  5.         int data;
  6.         struct link *next;
  7. }*Linklist,Node;
  8. //在无结点的动态单链表上实现insert(L,i,b)
  9. int insert(Linklist *L,int i,int b)                //L是头指针
  10. {

  12.         Linklist p,q;
  13.         int k=1;
  14.         p= *L;
  15.         if(i<1) return 0;
  16.         //处理要插在表头的情况        
  17.         if(i==1)
  18.         {
  19.                 q = (Linklist)malloc(sizeof(Node));
  20.                 if(q==NULL)
  21.                         exit(0);
  22.                 q->data = b;
  23.                 q->next = p;
  24.                 *L = q;
  25.         }
  26.         while(p&&k<i-1)
  27.         {
  28.                 p=p->next;
  29.                 k=k+1;
  30.         }
  31.         if(!p) return 0;
  32.         //建立新的结点
  33.         q = (Linklist)malloc(sizeof(Node));
  34.         if(q==NULL)
  35.                 exit(0);
  36.         q->data = b;
  37.         
  38.         //不插在表头时
  39.         q->next = p->next;
  40.         p->next = q;

  42.         return 1;
  43. }
  44. //建立无头节点链表
  45. void creatlist(Linklist *L,int n)
  46. {
  47.         Linklist p;
  48.         int i=0;
  49.         *L = (Linklist)malloc(sizeof(Node));
  50.         if(!L)
  51.         {
  52.                 printf("memory failed\n");
  53.                 exit(0);
  54.         }
  55.         (*L)->next = NULL;
  56.         for(i=0;i<n;i++)
  57.         {
  58.                 p = (Linklist)malloc(sizeof(Node));
  59.                 if(!p)
  60.                         exit(0);
  61.                 scanf("%d",&(p->data));
  62.                 p->next = *L;
  63.                 *L = p;
  64.         }
  65.         //调试
  66.        // p = *L;
  67.        // for(i=0;i<10;i++)
  68.        // {
  69.                 //printf("%d\n",p->data);
  70.                // p = p->next;
  71.       //  }

  73. }
  74. int main()
  75. {
  76.         Linklist L = NULL,p = NULL;
  77.         int i;
  78.         
  79.         creatlist(&L,10);
  80.         insert(&L,5,7);
  81.         p = L;
  82.         for(i=0;i<11;i++)
  83.         {
  84.                 printf("%d\n",p->data);
  85.                 p = p->next;
  86.         }
  87.                 //用完了，总得释放啊
  88.                 p = L;
  89.                 while(p)
  90.                 {
  91.                         L = p->next;
  92.                         free(p);
  93.                         p=L;       
  94.                 }
  95.         return 0;
  96. }
复制代码

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

豌图酱
 楼主| 发表于 2017-8-30 16:12:59 | 显示全部楼层
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zj_song
发表于 2017-8-30 18:20:39 | 显示全部楼层

回帖奖励 +2 鱼币

本帖最后由 zj_song 于 2017-8-30 18:27 编辑

似乎这里有问题
搜狗截图20170830181817.jpg
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

豌图酱
 楼主| 发表于 2017-8-30 19:57:56 | 显示全部楼层
zj_song 发表于 2017-8-30 18:20
似乎这里有问题

？是要怎么改的，其实我在创建单链表的函数里创建完测试时可以打印出每个元素的，但是在主函数里面调用再打印就不行了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

ba21
发表于 2017-8-31 00:36:06 | 显示全部楼层

回帖奖励 +2 鱼币


2017-08-31_003058.png
2017-08-31_003159.png
2017-08-31_003249.png
2017-08-31_003321.png


  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct link
  4. {
  5.         int data;
  6.         struct link *next;
  7. }*Linklist,Node;
  8. //在无结点的动态单链表上实现insert(L,i,b)
  9. int insert(Linklist L,int i,int b)                //L是头指针
  10. {

  12.         Linklist current,newnode;
  13.         int k=1;
  14.                 int temp;
  15.         current=L;

  17.         if(i<1) return 0;

  19.                 newnode = (Linklist)malloc(sizeof(Node));
  20.          if(newnode==NULL)
  21.                         exit(0);

  23.                 while(current && (k<i-1))
  24.         {
  25.                 current=current->next;
  26.                 k=k+1;
  27.         }
  28.         if(!current) return 0;

  30.                  newnode->data = b;

  32.         //处理要插在表头的情况        
  33.         if(i==1)
  34.         {               
  35.                 newnode->next = L->next;
  36.                                 L->next = newnode;
  37.                                
  38.                                 temp = L->data;
  39.                                 L->data = newnode->data;
  40.                                 newnode->data = temp;
  41.         }
  42.         else
  43.         {
  44.                                 //不插在表头时
  45.                                 newnode->next = current->next;
  46.                                 current->next = newnode;
  47.                                
  48.                 }
  49.         return 1;
  50. }
  51. //建立无头节点链表
  52. void creatlist(Linklist *L,int n)
  53. {
  54.         Linklist p;
  55.         int i=0;
  56.         *L = (Linklist)malloc(sizeof(Node));
  57.         if(!L)
  58.         {
  59.                 printf("memory failed\n");
  60.                 exit(0);
  61.         }
  62.         for(i=0;i<n;i++)
  63.         {
  64.                 p = (Linklist)malloc(sizeof(Node));
  65.                 if(!p)
  66.                         exit(0);
  67.                 scanf("%d",&(p->data));
  68.                 p->next = *L;
  69.                 *L = p;
  70.         }
  71.         /*调试
  72.         p = L;
  73.         for(i=0;i<10;i++)
  74.         {
  75.                 printf("%d\n",p->data);
  76.                 p = p->next;
  77.         }*/

  79. }
  80. int main()
  81. {
  82.         Linklist L=NULL,p;
  83.         int i;
  84.         
  85.         creatlist(&L,10);
  86.         insert(L,10,20);
  87.         p = L;
  88.         for(i=0;i<11;i++)
  89.         {
  90.                 printf("%d\n",p->data);
  91.                 p = p->next;
  92.         }
  93.         return 0;
  94. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

guoxiaopeng
发表于 2017-8-31 09:15:50 | 显示全部楼层    本楼为最佳答案   

回帖奖励 +2 鱼币

本帖最后由 guoxiaopeng 于 2017-8-31 09:17 编辑

题主的根本问题在于忽略了一个细节：就是指针变量作为函数参数，本身也遵循值传递的原理，我们可以在函数里改变指针所指向变量的值，但是并不能改变指针变量本身的值，题主在创建链表的函数里改变了L的值，在create函数里边可以打印链表，但是当函数返回主函数时，L的值是没有改变的，要么为空，要么是一个野指针。下面就代码具体分析：
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct link
  4. {
  5.         int data;
  6.         struct link *next;
  7. }*Linklist,Node;
  8. //在无结点的动态单链表上实现insert(L,i,b)

  10. //这里第一个参数应该是Linklist*L(也就是一个二级指针)
  11. int insert(Linklist L,int i,int b)                //L是头指针
  12. {

  14.         Linklist p,q;
  15.         int k=1;
  16.         p=L;
  17.         if(i<1) return 0;
  18.         //处理要插在表头的情况        
  19.         if(i==1)
  20.         {
  21.                 q = (Linklist)malloc(sizeof(Node));
  22.                 if(q==NULL)
  23.                         exit(0);
  24.                 q->data = b;
  25.                 q->next = p;
  26.                 L = q;//题主在这里临时改变了L的值，但是当函数执行完毕后L还是当初传进来的值
  27.         }
  28.         while(p&&k<i-1)
  29.         {
  30.                 p=p->next;
  31.                 k=k+1;
  32.         }
  33.         if(!p) return 0;
  34.         //建立新的结点
  35.         q = (Linklist)malloc(sizeof(Node));
  36.         if(q==NULL)
  37.                 exit(0);
  38.         q->data = b;
  39.         
  40.         //不插在表头时
  41.         q->next = p->next;
  42.         p->next = q;

  44.         return 1;
  45. }
  46. //建立无头节点链表
  47. //这里同样的第一个参数应该是（Linklist*L）
  48. void creatlist(Linklist L,int n)
  49. {
  50.         Linklist p;
  51.         int i=0;
  52.         L = (Linklist)malloc(sizeof(Node));
  53.         if(!L)
  54.         {
  55.                 printf("memory failed\n");
  56.                 exit(0);
  57.         }
  58.         L = NULL;//不知题主这里是什么意思，L= NULL会将刚申请的内存丢掉，但这片内存又没有free，这回导致内存泄漏的（尽管只是一个），应该是L->next = NULL吧
  59.         for(i=0;i<n;i++)
  60.         {
  61.                 p = (Linklist)malloc(sizeof(Node));
  62.                 if(!p)
  63.                         exit(0);
  64.                 scanf("%d",&(p->data));
  65.                 p->next = L;
  66.                 L = p;//同样只是在该函数内部临时改变了L的值，函数执行完毕，L仍然是原来传进来时的值，这样所创建的链表被整个抛弃了，主函数里当然打印失败，这回泄漏的内存就不止一个了，而是一片
  67.         }
  68.         /*调试
  69.         p = L;
  70.         for(i=0;i<10;i++)
  71.         {
  72.                 printf("%d\n",p->data);
  73.                 p = p->next;
  74.         }*/

  76. }
  77. int main()
  78. {
  79.         Linklist L,p;//L,P都没有初始化，也就是是野指针，
  80.         int i;
  81.         
  82.         creatlist(L,10);
  83.         insert(L,5,7);
  84.         p = L;
  85.         for(i=0;i<11;i++)
  86.         {
  87.                 printf("%d\n",p->data);
  88.                 p = p->next;
  89.         }
  90.         return 0;
  91. }
复制代码


下面给出修正后的代码
/************************************************************************************************************************************************/
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct link
  4. {
  5.         int data;
  6.         struct link *next;
  7. }*Linklist,Node;
  8. //在无结点的动态单链表上实现insert(L,i,b)
  9. int insert(Linklist *L,int i,int b)                //L是头指针
  10. {

  12.         Linklist p,q;
  13.         int k=1;
  14.         p= *L;
  15.         if(i<1) return 0;
  16.         //处理要插在表头的情况        
  17.         if(i==1)
  18.         {
  19.                 q = (Linklist)malloc(sizeof(Node));
  20.                 if(q==NULL)
  21.                         exit(0);
  22.                 q->data = b;
  23.                 q->next = p;
  24.                 *L = q;
  25.         }
  26.         while(p&&k<i-1)
  27.         {
  28.                 p=p->next;
  29.                 k=k+1;
  30.         }
  31.         if(!p) return 0;
  32.         //建立新的结点
  33.         q = (Linklist)malloc(sizeof(Node));
  34.         if(q==NULL)
  35.                 exit(0);
  36.         q->data = b;
  37.         
  38.         //不插在表头时
  39.         q->next = p->next;
  40.         p->next = q;

  42.         return 1;
  43. }
  44. //建立无头节点链表
  45. void creatlist(Linklist *L,int n)
  46. {
  47.         Linklist p;
  48.         int i=0;
  49.         *L = (Linklist)malloc(sizeof(Node));
  50.         if(!L)
  51.         {
  52.                 printf("memory failed\n");
  53.                 exit(0);
  54.         }
  55.         (*L)->next = NULL;
  56.         for(i=0;i<n;i++)
  57.         {
  58.                 p = (Linklist)malloc(sizeof(Node));
  59.                 if(!p)
  60.                         exit(0);
  61.                 scanf("%d",&(p->data));
  62.                 p->next = *L;
  63.                 *L = p;
  64.         }
  65.         //调试
  66.        // p = *L;
  67.        // for(i=0;i<10;i++)
  68.        // {
  69.                 //printf("%d\n",p->data);
  70.                // p = p->next;
  71.       //  }

  73. }
  74. int main()
  75. {
  76.         Linklist L = NULL,p = NULL;
  77.         int i;
  78.         
  79.         creatlist(&L,10);
  80.         insert(&L,5,7);
  81.         p = L;
  82.         for(i=0;i<11;i++)
  83.         {
  84.                 printf("%d\n",p->data);
  85.                 p = p->next;
  86.         }
  87.                 //用完了，总得释放啊
  88.                 p = L;
  89.                 while(p)
  90.                 {
  91.                         L = p->next;
  92.                         free(p);
  93.                         p=L;       
  94.                 }
  95.         return 0;
  96. }
复制代码

评分

参与人数 1荣誉 +3 鱼币 +5 贡献 +2 收起 理由
豌图酱 + 3 + 5 + 2

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

豌图酱
 楼主| 发表于 2017-8-31 10:47:45 | 显示全部楼层
guoxiaopeng 发表于 2017-8-31 09:15
题主的根本问题在于忽略了一个细节：就是指针变量作为函数参数，本身也遵循值传递的原理，我们可以在函数里 ...

啊这样啊，懂了！！！！谢谢！！！真的好详细的讲解
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-5-11 11:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表