关于有序循环链表的归并
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct NODE
{
int value; /*结点*/
struct NODE *next;
}Node;
void InsertBefore(Node *q1, Node *q2)//插入结点,引入结点p,可以让p插入到p2和p1之间
{
Node *p;
p = q1->next;
q1->next = q2;
q2->next = p;
}
Node *Del(Node *p1, Node *q)//删除结点q
{
p1->next = q->next;
return (q);
}
Node *Creat(int n)//创建链表
{
Node *cur, *p, *head;
int i;
head = (Node *)malloc(sizeof(Node)); //创建头结点
p = head;
printf("请输入结点 : ");
for(i = 0; i < n; i++)
{
cur = (Node *)malloc(sizeof(Node));
scanf("%d", &cur -> value);
p->next = cur;
p = cur;
}
p->next = head;
return head;
}
Node *Union(Node *head1, Node *head2)
{//合并链表
Node *p1, *p2, *ha, *hb;
ha = head1;
hb = head2;
p1 = ha->next;
p2 = hb->next;
while(p1!=head1 && p2!=head2)//链表都没结束
{
if(p1->value < p2->value)
{
ha = p1;
p1 = p1->next;//指针后移
}
else if(p1->value > p2->value)
{
if(p1 == head1->next) //p1指向头一个结点
{
Del(hb, p2);
head1->next = p2; //p2就要插入到头结点之后
p2->next = p1;
}
else
{
Del(hb, p2);
InsertBefore(ha, p2);//否则就插入到ha之后
}
p2=hb->next; //p2结点被删除,重新赋值
ha=ha->next; //ha之后多了一个结点要移到下一个结点
}
else //p1->value == p2->value
{
ha = p1;
p1 = p1->next; //p1向下移动一个结点
free(Del(hb, p2)); //p2要删除和释放,只取p1
p2=hb->next;
}
}
if(p2!=head2)//链表2没结束
{
ha->next = p2; //插入p2的剩余结点到ha中
}
free(head2);//释放
// head1=p1->next;
return head1;//返回头结点
}
void print(Node *head)//输出链表
{
Node *cur;//头结点
cur = head->next;
while(cur!= head)
{
printf("%d ", cur->value);
cur = cur->next;//指针后移
}
printf("\n");
}
void main()
{
Node *list1, *list2;//头结点
int num1, num2;
printf("请输入第一个结点数 : ");
scanf("%d", &num1);
list1 = Creat(num1);
printf("第一个链表的数据信息: \n");
print(list1);
printf("\n请输入第二个结点数 : ");
scanf("%d", &num2);
list2 = Creat(num2);
printf("第二个链表的数据信息: \n");
print(list2);
list1 = Union(list1, list2);
printf("\n合并后的数据信息 : \n");
print(list1);
}
归并有问题
[解决办法]
应该没必要做一个循环链表吧!!!
合并之后你没有把最后结点的next指向头结点,所以在调用print输出时,while(cur!= head)是无效的,会造成野指针的访问!
帮你修改了一下(假如循环链表你自己去修改一下合并函数):
#include <stdio.h > #include <malloc.h > #include <stdlib.h > typedef struct NODE { int value; /*结点*/ struct NODE *next; }Node; void InsertBefore(Node *q1, Node *q2)//插入结点,引入结点p,可以让p插入到p2和p1之间 { Node *p; p = q1->next; q1->next = q2; q2->next = p; } Node *Del(Node *p1, Node *q)//删除结点q { p1->next = q->next; return (q); } Node *Creat(int n)//创建链表 { Node *cur, *p, *head; int i; head = (Node *)malloc(sizeof(Node)); //创建头结点 p = head; printf("请输入结点 : "); for(i = 0; i < n; i++) { cur = (Node *)malloc(sizeof(Node)); scanf("%d", &cur -> value); p->next = cur; p = cur; } p->next = NULL; return head; } Node *Union(Node *head1, Node *head2) {//合并链表 Node *p1, *p2, *ha, *hb; ha = head1; hb = head2; p1 = ha->next; p2 = hb->next; while(p1!=NULL && p2!=NULL)//链表都没结束 { if(p1->value < p2->value) { ha = p1; p1 = p1->next;//指针后移 } else if(p1->value > p2->value) { if(p1 == head1->next) //p1指向头一个结点 { Del(hb, p2); head1->next = p2; //p2就要插入到头结点之后 p2->next = p1; } else { Del(hb, p2); InsertBefore(ha, p2);//否则就插入到ha之后 } p2=hb->next; //p2结点被删除,重新赋值 ha=ha->next; //ha之后多了一个结点要移到下一个结点 } else //p1- >value == p2- >value { ha = p1; p1 = p1->next; //p1向下移动一个结点 free(Del(hb, p2)); //p2要删除和释放,只取p1 p2=hb->next; } } if(p2!=head2)//链表2没结束 { ha->next = p2; //插入p2的剩余结点到ha中 } free(head2);//释放 //ha->next = head1; return head1;//返回头结点 } void print(Node *head)//输出链表 { Node *cur;//头结点 cur = head->next; while(cur!= NULL) { printf("%d ", cur->value); //////////// cur = cur->next;//指针后移 } printf("\n"); } void main() { Node *list1, *list2;//头结点 int num1, num2; printf("请输入第一个结点数 : "); scanf("%d", &num1); list1 = Creat(num1); printf("第一个链表的数据信息: \n"); print(list1); printf("\n请输入第二个结点数 : "); scanf("%d", &num2); list2 = Creat(num2); printf("第二个链表的数据信息: \n"); print(list2); list1 = Union(list1, list2); printf("\n合并后的数据信息 : \n"); print(list1); }