YXTS122
YXTS122
2016-09-28 06:26
采纳率: 100%
浏览 953
已采纳

为什么我这两个有序链表不能合并为一个?

 #include<stdio.h>
#include<stdlib.h>
struct stu
{
    int num;
    struct stu *next;
};
struct stu *creat()
{
//建立一个链表
    int n;
    struct stu *p1,*p2,*head;
    scanf("%d",&n);
    p1=head=(struct stu *)malloc(sizeof (struct stu));
    p1->next=NULL;
    for(int i=0;i<n;i++)
    {
        p2=(struct stu *)malloc(sizeof(struct stu));
        p2->next=NULL;
        scanf("%d",&p2->num);
        getchar();
        p1->next=p2;
        p1=p2;
    }
    p1->next=NULL;
    return head;
}
int main()
{
    struct stu *p1=NULL,*pt_a=NULL,*pt_b=NULL,*ptemp=NULL,*a=NULL,*b=NULL,*ptem=NULL,*h=NULL;
    struct stu *head=NULL;
    //新链表的表头
    a=creat();  pt_a=a;
    b=creat();  pt_b=b;
    h=a;   //head=pt_a;
//  p1=head;
     p1=h;
    while (pt_a->next&&pt_b->next)
    {
    //判断一个链表是否遍历到结尾
        if (pt_a->next->num>pt_b->next->num)
        {
            printf("\npt_a->next->num=%d,pt_b->next->num=%d\n",pt_a->next->num,pt_b->next->num);
            ptem=pt_a->next;
//先把pt_a->next这个地址保留下来
            ptemp=pt_b->next;
            pt_b=pt_b->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_a->next=ptem;
            continue;
        }
        if (pt_a->next->num<=pt_b->next->num)
        {
                printf("\npt_a->next->num=%d,pt_b->next->num=%d\n",pt_a->next->num,pt_b->next->num);
                ptem=pt_b->next;
          ptemp=pt_a->next;
          pt_a=pt_a->next;
            p1->next=ptemp;
           p1=ptemp;
            pt_b->next=ptem;
            continue;
        }



    }

    while (pt_a->next||pt_b->next)
    {
        if  (pt_a->next)
        {
            ptem=pt_b->next;
            ptemp=pt_a->next;
            pt_a=pt_a->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_b->next=ptem;
            continue;
        }

        if (pt_b->next)
        {
            ptem=pt_a->next;
            ptemp=pt_b->next;
            pt_b=pt_b->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_a->next=ptem;
            continue;
        }
    }
    p1->next=NULL;
    printf("\n");

    p1=h->next;
     while (p1!=NULL) 
     {
        printf("%5d",p1->num);
         p1=p1->next; 
     }

     return 0;

}

图片说明

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

3条回答 默认 最新

  • leewers
    leewers 2016-09-28 14:24
    已采纳

    从你的代码可以看出,你已经意识到操作p1 -> next实质上会导致两个旧链表无法访问,所以用了ptem来存储,并在执行操作后将pt_a或者pt_b的next指向ptem,但是有一个问题,在pt_a->next=ptem;这句代码之前,有两句关键代码p1->next=ptemp;和p1=ptemp; 想一下如果一开始p1和pt_a指向同一节点,然后p1->next指向了ptemp, 也就是将pt_a -> next指向了ptemp,然后将p1指向ptemp,但别忘了pt_a仍指向开始的节点,随后的pt_a -> next = ptem实质上干的事情就是将一开始p1指向的节点的next指针指向ptem(也就是a链表上该节点的下一个节点),这也就意味着p1->next = ptemp;这一操作被覆盖了,也就无效了。而这一情况不断出现,就产生了图中的结果,只有其中一条链表的元素加入了新链表。
    另外,其实执行完第一个循环,直接将p1->next指向剩余的一条链表就行了,如果两条链表均为空了,则指向NULL。

    pt_a = pt_a -> next;
         pt_b = pt_b -> next;
         while(pt_a && pt_b){
             if(pt_a->num > pt_b->num){
                 ptemp = pt_b;
                 pt_b = pt_b -> next;
                 p1 -> next = ptemp;
                 p1 = ptemp;
             }
             else{
                 ptemp = pt_a;
                 pt_a = pt_a -> next;
                 p1 -> next = ptemp;
                 p1 = ptemp;
             }
         }
    
         if(pt_a)
             p1 -> next = pt_a;
         else if(pt_b)
             p1 -> next = pt_b;
                else
                    p1 -> next = NULL;
    
    
    点赞 评论
  • YXTS122
    YXTS122 2016-09-29 07:29

    #include<stdio.h>
    #include<stdlib.h>
    struct stu
    {
    int num;
    struct stu *next;
    };
    struct stu *creat()
    {
    //建立一个链表
    int n;
    struct stu *p1,*p2,*head;
    scanf("%d",&n);
    p1=head=(struct stu )malloc(sizeof (struct stu));
    p1->next=NULL;
    for(int i=0;i<n;i++)
    {
    p2=(struct stu *)malloc(sizeof(struct stu));
    p2->next=NULL;
    scanf("%d",&p2->num);
    getchar();
    p1->next=p2;
    p1=p2;
    }
    p1->next=NULL;
    return head;
    }
    int main()
    {
    struct stu *p1=NULL,*pt_a=NULL,*pt_b=NULL,*ptemp=NULL,*a=NULL,*b=NULL,*ptem=NULL,*h=NULL;
    struct stu *head=NULL,*y=NULL;
    struct stu
    f;
    f=(struct stu*)malloc(sizeof (struct stu));
    //新链表的表头
    a=creat(); pt_a=a;
    b=creat(); pt_b=b;
    h=a; //head=pt_a;
    // p1=head;
    p1=h;
    while (pt_a->next&&pt_b->next)
    {
    //判断一个链表是否遍历到结尾
    if (pt_a->next->num>pt_b->next->num)
    {
    // printf("\npt_a->next->num=%d,pt_b->next->num=%d\n",pt_a->next->num,pt_b->next->num);
    ptem=pt_a->next;
    //先把pt_a->next这个地址保留下来
    ptemp=pt_b->next;
    pt_b=pt_b->next->next;
    // printf("\np1->next=%d\n",p1->next);
    p1->next=ptemp;
    //此时p1和pt_a指向同一节点
    p1=ptemp;
    ptemp->next=ptem;
    pt_a=pt_a->next;
    //此时pt_a和pt_b指向同一节点
    f->next=pt_b;
    pt_b=f;
    printf("\n");
    y=h->next;
    while (y!=NULL)
    {
    printf("%4d",y->num);
    y=y->next;
    }
    continue;
    }
    if (pt_a->next->num<=pt_b->next->num)
    {
    // printf("\npt_a->next->num=%d,pt_b->next->num=%d\n",pt_a->next->num,pt_b->next->num);
    ptem=pt_b->next;
    ptemp=pt_a->next;
    pt_a=pt_a->next;
    // printf("\np1->next=%d\n",p1->next);
    p1->next=ptemp;
    p1=ptemp;
    pt_b->next=ptem;
    printf("\n");
    y=h->next;
    while (y!=NULL)
    {
    printf("%4d",y->num);
    y=y->next;
    }
    continue;
    }

    }
    
    while (pt_a->next||pt_b->next)
    {
        if  (pt_a->next)
        {
            ptem=pt_b->next;
            ptemp=pt_a->next;
            pt_a=pt_a->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_b->next=ptem;
            continue;
        }
    
        if (pt_b->next)
        {
            ptem=pt_a->next;
            ptemp=pt_b->next;
            pt_b=pt_b->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_a->next=ptem;
            continue;
        }
    }
    p1->next=NULL;
    printf("\n");
    
    p1=h->next;
     while (p1!=NULL) 
     {
        printf("%5d",p1->num);
         p1=p1->next; 
     }
    
     return 0;
    

    }

    点赞 评论
  • YXTS122
    YXTS122 2016-09-30 01:50
     #include<stdio.h>
    #include<stdlib.h>
    struct stu
    {
        int num;
        struct stu *next;
    };
    struct stu *creat()
    {
    //建立一个链表
        int n;
        struct stu *p1,*p2,*head;
        scanf("%d",&n);
        p1=head=(struct stu *)malloc(sizeof (struct stu));
        p1->next=NULL;
        for(int i=0;i<n;i++)
        {
            p2=(struct stu *)malloc(sizeof(struct stu));
            p2->next=NULL;
            scanf("%d",&p2->num);
            getchar();
            p1->next=p2;
            p1=p2;
        }
        p1->next=NULL;
        return head;
    }
    int main()
    {
        struct stu *p1=NULL,*pt_a=NULL,*pt_b=NULL,*pTemp=NULL,*a=NULL,*b=NULL;
        struct stu *head=NULL;
        a=creat();
        b=creat();
        pt_a =a -> next;
        pt_b =b -> next;
        p1=a;
        while (pt_a && pt_b)
        { //按原来的写法的话,如果两条链表比较到都只剩一个元素,此时两个元素的next指针都指向NULL,因此没有进行比较就退-
         if (pt_a -> num < pt_b -> num)
         { //-出循环了
          pTemp = pt_a; //存储即将加入新链表的a链表中的元素地址 
          pt_a = pt_a -> next; //立即更新a链表剩余部分的头元素 
          p1->next = pTemp; 
          p1 = pTemp; 
          } 
          else
          { 
          pTemp = pt_b;
           pt_b = pt_b -> next;
            p1->next = pTemp; 
            p1 = pTemp; 
    
            }
         }
        //    p1 -> next=( pt_a ? pt_a : pt_b ? pt_b : NULL); //别忘了当一条链表还有剩余元素时添加入新元素
        if (pt_a)
            p1->next=pt_a;
         else if (pt_b)
             p1->next=pt_b;
         else
              p1->next=NULL;
    
    
            head=a->next;
            while (head!=NULL)
            {
                printf("%5d",head->num);
                head=head->next;
            }
    
         return 0;
    
    }
    
    点赞 评论

相关推荐