an_tang
2016-09-23 12:33
采纳率: 25%
浏览 1.0k
已采纳

求高手啊 两个有序指针按大小合并到一个指针中,为什么会在第一个while循环中陷入死循环

#include
#include
struct stu
{
int num;
struct stu next;
};
struct stu
creat(void)//建立一个链表
{
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 {
p2=(struct stu *)malloc(sizeof(struct stu));
p2->next=NULL;
scanf("%d",&p2->num);
p1->next=p2;
p1=p2;
}
p1->next=NULL;
return head;
}
int main()
{
struct stu *p1,*pt_a,*pt_b;
struct stu
head=(struct stu *)malloc(sizeof(struct stu));新链表的表头
p1=head;
p1->next==NULL;
pt_a=creat();
pt_b=creat();
while(pt_a->next&&pt_b->next)//判断一个链表是否遍历到结尾
{

if(pt_a->next->num>pt_b->next->num);判断大小
{
p1->next=pt_b->next;连接到新链表上
p1=pt_b->next;新表指针指向最后一个
pt_b=pt_b->next;原先的链表后移
}

经过调试发现旧链表不会后移,所以一直死循环             
                else{
                    p1->next=pt_a->next;
                    p1=pt_a->next;
                    pt_a=pt_a->next;
                }
        }
        p1->next=NULL;
    while(head->next!=NULL)
    {
        printf("%5d",head->next->num);
        head=head->next;
    }
return 0;

}

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

3条回答 默认 最新

  • leewers 2016-09-23 19:29
    已采纳

    陷入死循环的原因是,旧链表中某个节点的next指针又指向了自身。这种情况发生在新链表依次从两个旧链表中轮流加入元素,比如a为1 2 3,b也为1 2 3,那么表面上看,新链表加入顺序应该为b1 a1 b2 a2 b3 a3,但实际上新链表加入的顺序其实是 b1 a1 a1 a1.......,也就表现为死循环。
    接下来开始一步步分析,如果不感兴趣的话可以跳到最后,附有修改过的代码,直接替换掉while循环一直到p1->next=NULL;就行了。
    一开始pt_a->next->num和pt_b->next->num都为1,那么(pt_a->next->num>pt_b->next->num)为假,
    则执行else中的语句 p1->next=pt_a->next,将p1->next指向pt_a->next,也就是a1;
    p1 = pt_a->next; pt_a = pt_a->next;,也就是将p1和pt_a指向a1;
    直到目前,情况还没有出现异常。

    执行完else中的语句后,pt_a->next->num为2, pt_b->next->num为1,则(pt_a->next->num>pt_b->next->num)为真,
    执行if中的语句p1->next=pt_b->next;,关键问题来了!!!现在p1指向了a1,这句代码将a1的next指针指向了pt_b->next,也就是b1!!!更糟糕的是,由于没有用指针记录下a2的地址,a链表上的剩余节点都无法访问到了(其实属于内存泄漏,但不在本题讨论范围内)。
    接下来是p1=pt_b->next; pt_b=pt_b->next; 将p1和pt_b指向b1。

    执行完这段代码后,pt_a仍指向a1,而a1的next指针已经指向了b1, 因此pt_a->next->num = 1(pt_a->next指向b1), pt_b->next->num = 2(pt_b->next指向b2), 则(pt_a->next->num>pt_b->next->num)为假,执行else中的语句,
    p1->next=pt_a->next; 现在p1指向b1,而pt_a->next也指向b1,这句话也就变成了节点b1->next = 节点b1,也就是节点b1的next指针指向了自身,同时链表b的剩余节点也无法访问了。
    p1=pt_a->next; pt_a=pt_a->next; 将p1和pt_a指向b1节点

    接下来死循环就开始展现出来了,由于pt_a和pt_b均指向b1,因此pt_a->next和pt_b->next也都指向b1,所有pt_a->next->num和pt_b->next->num都为1,(pt_a->next->num>pt_b->next->num)为假,执行else中的语句,
    p1->next=pt_a->next; 其实就是节点b1->next = 节点b1 -> next,也就什么都没干;
    p1=pt_a->next; pt_a=pt_a->next; 将p1和pt_a指向b1节点,也相当于什么都没干;
    于是程序陷入死循环。

    pt_a = pt_a -> next;
    pt_b = pt_b -> next;
    struct stu* pTemp; 
    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; //别忘了当一条链表还有剩余元素时添加入新元素
    
    
    已采纳该答案
    打赏 评论
  • leewers 2016-09-24 05:58

    图片说明

    打赏 评论
  • YXTS122 2016-09-30 01:51
     #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;
    
    }
    
    打赏 评论

相关推荐 更多相似问题