论坛 › C\C++交流 › 无头结点单链表的插入

豌图酱 发表于 2017-8-29 12:24:40

无头结点单链表的插入

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

        Linklist p,q;
        int k=1;
        p=L;
        if(i<1) return 0;
        //处理要插在表头的情况       
        if(i==1)
        {
                q = (Linklist)malloc(sizeof(Node));
                if(q==NULL)
                        exit(0);
                q->data = b;
                q->next = p;
                L = q;
        }
        while(p&&k<i-1)
        {
                p=p->next;
                k=k+1;
        }
        if(!p) return 0;
        //建立新的结点
        q = (Linklist)malloc(sizeof(Node));
        if(q==NULL)
                exit(0);
        q->data = b;
       
        //不插在表头时
        q->next = p->next;
        p->next = q;

        return 1;
}
//建立无头节点链表
void creatlist(Linklist L,int n)
{
        Linklist p;
        int i=0;
        L = (Linklist)malloc(sizeof(Node));
        if(!L)
        {
                printf("memory failed\n");
                exit(0);
        }
        L = NULL;
        for(i=0;i<n;i++)
        {
                p = (Linklist)malloc(sizeof(Node));
                if(!p)
                        exit(0);
                scanf("%d",&(p->data));
                p->next = L;
                L = p;
        }
        /*调试
        p = L;
        for(i=0;i<10;i++)
        {
                printf("%d\n",p->data);
                p = p->next;
        }*/

}
int main()
{
        Linklist L,p;
        int i;
       
        creatlist(L,10);
        insert(L,5,7);
        p = L;
        for(i=0;i<11;i++)
        {
                printf("%d\n",p->data);
                p = p->next;
        }
        return 0;
}
题目是要给一个无头结点的链表的第i的个元素前插入d；
因为是数据结构的题目，虽然有搜到其他答案，但是运行的时候总是会报错退出，请大家帮我看下问题在哪里。。。
经过测试，是insert函数的问题，但是不知道问题出在哪里~

豌图酱 发表于 2017-8-30 16:12:59

{:10_266:}

zj_song 发表于 2017-8-30 18:20:39

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

似乎这里有问题

豌图酱 发表于 2017-8-30 19:57:56

zj_song 发表于 2017-8-30 18:20
似乎这里有问题

？是要怎么改的，其实我在创建单链表的函数里创建完测试时可以打印出每个元素的，但是在主函数里面调用再打印就不行了

ba21 发表于 2017-8-31 00:36:06

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

      Linklist current,newnode;
      int k=1;
                int temp;
      current=L;

      if(i<1) return 0;

                newnode = (Linklist)malloc(sizeof(Node));
         if(newnode==NULL)
                        exit(0);

                while(current && (k<i-1))
      {
                current=current->next;
                k=k+1;
      }
      if(!current) return 0;

               newnode->data = b;

      //处理要插在表头的情况      
      if(i==1)
      {               
                newnode->next = L->next;
                                L->next = newnode;
                               
                                temp = L->data;
                                L->data = newnode->data;
                                newnode->data = temp;
      }
      else
      {
                                //不插在表头时
                                newnode->next = current->next;
                                current->next = newnode;
                               
                }
      return 1;
}
//建立无头节点链表
void creatlist(Linklist *L,int n)
{
      Linklist p;
      int i=0;
      *L = (Linklist)malloc(sizeof(Node));
      if(!L)
      {
                printf("memory failed\n");
                exit(0);
      }
      for(i=0;i<n;i++)
      {
                p = (Linklist)malloc(sizeof(Node));
                if(!p)
                        exit(0);
                scanf("%d",&(p->data));
                p->next = *L;
                *L = p;
      }
      /*调试
      p = L;
      for(i=0;i<10;i++)
      {
                printf("%d\n",p->data);
                p = p->next;
      }*/

}
int main()
{
      Linklist L=NULL,p;
      int i;
      
      creatlist(&L,10);
      insert(L,10,20);
      p = L;
      for(i=0;i<11;i++)
      {
                printf("%d\n",p->data);
                p = p->next;
      }
      return 0;
}

guoxiaopeng 发表于 2017-8-31 09:15:50

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

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

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

      Linklist p,q;
      int k=1;
      p=L;
      if(i<1) return 0;
      //处理要插在表头的情况      
      if(i==1)
      {
                q = (Linklist)malloc(sizeof(Node));
                if(q==NULL)
                        exit(0);
                q->data = b;
                q->next = p;
                L = q;//题主在这里临时改变了L的值，但是当函数执行完毕后L还是当初传进来的值
      }
      while(p&&k<i-1)
      {
                p=p->next;
                k=k+1;
      }
      if(!p) return 0;
      //建立新的结点
      q = (Linklist)malloc(sizeof(Node));
      if(q==NULL)
                exit(0);
      q->data = b;
      
      //不插在表头时
      q->next = p->next;
      p->next = q;

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

}
int main()
{
      Linklist L,p;//L,P都没有初始化，也就是是野指针，
      int i;
      
      creatlist(L,10);
      insert(L,5,7);
      p = L;
      for(i=0;i<11;i++)
      {
                printf("%d\n",p->data);
                p = p->next;
      }
      return 0;
}

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

      Linklist p,q;
      int k=1;
      p= *L;
      if(i<1) return 0;
      //处理要插在表头的情况      
      if(i==1)
      {
                q = (Linklist)malloc(sizeof(Node));
                if(q==NULL)
                        exit(0);
                q->data = b;
                q->next = p;
                *L = q;
      }
      while(p&&k<i-1)
      {
                p=p->next;
                k=k+1;
      }
      if(!p) return 0;
      //建立新的结点
      q = (Linklist)malloc(sizeof(Node));
      if(q==NULL)
                exit(0);
      q->data = b;
      
      //不插在表头时
      q->next = p->next;
      p->next = q;

      return 1;
}
//建立无头节点链表
void creatlist(Linklist *L,int n)
{
      Linklist p;
      int i=0;
      *L = (Linklist)malloc(sizeof(Node));
      if(!L)
      {
                printf("memory failed\n");
                exit(0);
      }
      (*L)->next = NULL;
      for(i=0;i<n;i++)
      {
                p = (Linklist)malloc(sizeof(Node));
                if(!p)
                        exit(0);
                scanf("%d",&(p->data));
                p->next = *L;
                *L = p;
      }
      //调试
       // p = *L;
       // for(i=0;i<10;i++)
       // {
                //printf("%d\n",p->data);
               // p = p->next;
      //}

}
int main()
{
      Linklist L = NULL,p = NULL;
      int i;
      
      creatlist(&L,10);
      insert(&L,5,7);
      p = L;
      for(i=0;i<11;i++)
      {
                printf("%d\n",p->data);
                p = p->next;
      }
                //用完了，总得释放啊
                p = L;
                while(p)
                {
                        L = p->next;
                        free(p);
                        p=L;       
                }
      return 0;
}

豌图酱 发表于 2017-8-31 10:47:45

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

啊这样啊，懂了！！！！谢谢！！！真的好详细的讲解{:9_228:}

查看完整版本: 无头结点单链表的插入