浅草夏洛洛
2018-11-10 07:57
采纳率: 80%
浏览 652
已采纳

c语言中两个链表的合并(不用结点的方式)总是错误的

初学数据结构,在链表的合成中想尝试不用结点,发现不管咋样都是错误的。
下面是代码

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read();
void Print( List L );

List Merge( List L1, List L2 ); //对两个有序链表进行合并
//链表均带有头结点

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}
List Read()
{
    int n;
    scanf("%d",&n);
    List L=(List)malloc(sizeof(PtrToNode));   ///申请一个头结点
    L->Next = NULL;        ///头指针为空
    if(n)    ///当n不是0时
    {
        List r=L;     ///r是一个中间变量的节点
        for(int i=0;i<n;i++)
        {
            List p=(List)malloc(sizeof(struct Node));
            scanf("%d",&(p->Data));    ///尾插法
            r->Next = p;
            r = p;
        }
        r->Next = NULL;
    }
    return L;
}

void Print( List L )
{
   List p=L->Next;
   if(p)
   {
       List r;
       r = L;
       while(r->Next)
       {
           r = r->Next;
           printf("%d ",r->Data);
       }
   }
   else
   {
       printf("NULL");
   }
   printf("\n ");
}
List Merge( List L1, List L2 )
{
    List L,p,a,b;
    L = (List)malloc(sizeof(struct Node));
    p = L->Next;
    a = L1->Next;
    b = L2->Next;
    while(a && b)
    {
        if(a->Data < b->Data)
        {
            p->Data = a->Data;
            p = p->Next;
            a = a->Next;
        }
        else if(a->Data == b->Data)
        {
            p->Data = a->Data;
            p = p->Next;
            a = a->Next;
            b = b->Next;
        }
        else
        {
            p->Data = b->Data;
            p = p->Next;
            b = b->Next;
        }
    }
    for( ;a;a = a->Next)
    {
        p->Data = a->Data;
        p = p->Next;
    }
    for( ;b;b = b->Next)
    {
        p->Data = L2->Data;
        p = p->Next;
    }
    L1->Next = NULL;
    L2->Next = NULL;
    p = NULL;
    return L;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • blownewbee 2018-11-10 08:28
    已采纳

    l = (List)malloc(sizeof(struct Node));
    p = l->Next;
    这里就错了
    l没有初始化,next是野指针

    你把完整程序包括main都贴出来,输入输出贴出来,代码格式化好(点</>然后放入代码),再帮你调试。

    点赞 打赏 评论
  • 浅草夏洛洛 2018-11-10 14:57

    大概知道了问题所在,后面自己改了下代码。但其中一个还是有错误。也发现这个不用结点的方式真的是太浪费空间,太傻了。发现还有两个地方不太懂?
    一 L = (List)malloc(sizeof(struct Node));L->Next = NULL;中为什么L的next初始化为空后,L就是初始化了?
    二 如果仅对L用malloc分配内存不能算初始化指针吗?
    自己理解:查了malloc函数(malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定,_void* 类型可以强制转换为任何其它类型的指针)那L = (List)malloc(sizeof(struct Node));是否只是对L初始化,而Next并没有初始化导致的错误。另外代码中中的p,a,b,temp在利用完后是否应该再利用free进行释放,以便减少空间内存的占用。
    _**

     List Merge( List L1, List L2 )
    {
        List L,p,a,b;
        List temp;
        L = (List)malloc(sizeof(struct Node));
        L->Next = NULL;
        p = L;
        a = L1->Next;
        b = L2->Next;
        while(a && b)
        {
            if(a->Data < b->Data)
            {
                temp = (List)malloc(sizeof(struct Node));
                temp->Next = NULL;
                temp->Data = a->Data;
                p->Next = temp;
                p = p->Next;
                a = a->Next;
            }
            else if(a->Data == b->Data)
            {
                temp = (List)malloc(sizeof(struct Node));
                temp->Next = NULL;
                temp->Data = a->Data;
                p->Next = temp;
                p = p->Next;
                a = a->Next;
                b = b->Next;
            }
            else
            {
                temp = (List)malloc(sizeof(struct Node));
                temp->Next = NULL;
                temp->Data = b->Data;
                p->Next = temp;
                p = p->Next;
                b = b->Next;
            }
        }
        for( ;a;a = a->Next)
        {
            temp = (List)malloc(sizeof(struct Node));
            temp->Next = NULL;
            temp->Data = a->Data;
            p->Next = temp;
            p = p->Next;
        }
        for( ;b;b = b->Next)
        {
            temp = (List)malloc(sizeof(struct Node));
            temp->Next = NULL;
            temp->Data = b->Data;
            p->Next = temp;
            p = p->Next;
        }
        L1->Next = NULL;
        L2->Next = NULL;
        return L;
    }
    /*List Merge( List L1, List L2 ) 不借用中间变量temp的改写 运行错误
    {
        List L,p,a,b;
        L = (List)malloc(sizeof(struct Node));
        L->Next = (List)malloc(sizeof(struct Node));
        L->Next->Next = NULL;
        p = L->Next;
        a = L1->Next;
        b = L2->Next;
        while(a && b)
        {
            if(a->Data < b->Data)
            {
                p->Data = a->Data;
                p->Next = (List)malloc(sizeof(struct Node));
                p->Next->Next = NULL;
                p = p->Next;
                a = a->Next;
            }
            else if(a->Data == b->Data)
            {
                p->Data = a->Data;
                p->Next = (List)malloc(sizeof(struct Node));
                p->Next->Next = NULL;
                p = p->Next;
                a = a->Next;
                b = b->Next;
            }
            else
            {
                p->Data = b->Data;
                p->Next = (List)malloc(sizeof(struct Node));
                p->Next->Next = NULL;
                p = p->Next;
                b = b->Next;
            }
        }
        for( ;a;a = a->Next)
        {
            p->Data = a->Data;
            p->Next = (List)malloc(sizeof(struct Node));
            p->Next->Next = NULL;
            p = p->Next;
        }
        for( ;b;b = b->Next)
        {
            p->Data = L2->Data;
            p->Next = (List)malloc(sizeof(struct Node));
            p->Next->Next = NULL;
            p = p->Next;
        }
        L1->Next = NULL;
        L2->Next = NULL;
        p = NULL;
        return L;
    }*/
    
    
    点赞 打赏 评论

相关推荐 更多相似问题