2 an tang an_tang 于 2016.09.23 20:33 提问

求高手啊 两个有序指针按大小合并到一个指针中,为什么会在第一个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;

}

5个回答

leewers
leewers   2016.09.24 03: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
leewers 写反了。。。"新链表加入顺序应该为a1 b1 a2 b2 a3 b3,但实际上新链表加入的顺序其实是 a1 b1 b1 b1......."
大约一年之前 回复
YXTS122
YXTS122   2016.09.25 16: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;
struct stu *head=NULL,*p=NULL;
//新链表的表头
pt_a=creat();
pt_b=creat();
while(pt_a->next&&pt_b->next)
{
//判断一个链表是否遍历到结尾
if (pt_a->next->num>pt_b->next->num)
{
ptemp=pt_b->next;
printf("\npt_b->next->num=%d,",pt_b->next->num);
//连接到新链表上
//p1=p1->next;
//p1=ptemp;
//新表指针指向最后一个
pt_b=pt_b->next;
//printf("pt_b->next->num=%d\n",pt_b->next->num);
}
else
{
ptemp=pt_a->next;
printf("\npt_a->next->num=%d,",pt_a->next->num);
// p1=p1->next;
// p1=ptemp;
pt_a=pt_a->next;
//printf("pt_a->next->num=%d\n",pt_a->next->num);
}

    if (head==NULL)
    {
        head=(struct stu*)malloc (sizeof (struct stu));
        head->num=ptemp->num;
        head->next=NULL;
        p1=head;
    }
    else
    {
        p=(struct stu*)malloc (sizeof (struct stu));
        p->num=ptemp->num;
        p->next=NULL;
        p1->next=p;
        p1=p;
    }


}

if (pt_a->next||pt_b->next)
{
    while (pt_a->next)
    {
        p=(struct stu*)malloc (sizeof (struct stu));
        p->num=pt_a->next->num;
        p->next=NULL;
        p1->next=p;
        p1=p;
        pt_a=pt_a->next;
    }

    while (pt_b->next)
    {
        p=(struct stu*)malloc (sizeof (struct stu));
        p->num=pt_b->next->num;
        p->next=NULL;
        p1->next=p;
        p1=p;
        pt_b=pt_b->next;
    }
}
printf("\n");
 while (head!=NULL) 
 {
    printf("%5d",head->num);
     head=head->next; 
 }

 return 0;

}

YXTS122
YXTS122   2016.09.29 15:38

#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 09: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;

}
leewers
leewers   2016.09.24 13:58

图片说明

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!