合并两个带头结点的有序循环链表合并为一个带头结点的有序循环链表
#include<stdio.h> //预编译命令
#include<iostream.h>
strUCt list//定义结构体
{
int num;
list*next;
};
list*head,*end; //定义全局变量
list*creat()//创建链表的函数
{
list*p=NULL;
list*q=NULL;
head=NULL;
int num;
printf("Input number:\n");
scanf("%d",&num);
while(num!=0)
{
p=new list; //开辟空间
p->num=num;
if(head==NULL)
head=p;
else
q->next=p;
q=p;
scanf("%d",&num);
}
end=q; //将链表的结尾最后一个结点赋给end
end->next=head; //让最后一个结点的的下个结点的地址不为空而指向头指针
return(head);
}
void print(list*head)//打印循环链表的函数
{
int k=0;
list*r=head;
do
{
cout.width(2);
k=k+1;
cout<<k<<":"<<r->num<<endl;
r=r->next;
}while(r!=head);
}
void insert(list*pHead,list*pNode) //插入接点的函数
{
list*q,*r;
//第一种情况，链表为空
if(pHead==NULL)
{
pHead=pNode; //链表头指向pNode
return; //完成插入操作，返回
}
//第二种情况，pNode结点num的值小于链表头结点num的值
//则将pNode的值插到链表头部
if(pNode->num<=pHead->num)
{
pNode->next=pHead;
pHead=pNode;
return;
}
//第三种情况，循环查找正确位置
r=pHead;
q=pHead->next;
while(q!=pHead)
{
if(pNode->num>q->num)
{
r=q;
q=q->next;
}
else
break;
}
r->next=pNode;
pNode->next=q;
}
list*together(list*p1,list*p2) //定义两个链表合并的函数
{
list*q,*r;
q=p2;
do
{
r=new list; //开辟空间
r->num=q->num; //将q的值赋给r
r->next=NULL; //让r的下一个指针的地址为空，目的是使它成为一个独立的结点
insert(p1,r); //调用插入结点的函数
q=q->next; //指针向后拨一个接点
}while(q!=p2); //当在最后一个结点时停止循环
return(p1); //返回头指针
}
void main() //主函数
{
list*list1,*list2;
printf("Input list1\n");
printf("If number is 0,stop inputing\n");
printf("数据请从小到大输入\n");
list1=creat(); //调用创建链表的函数
print(list1); //打印第一个链表
printf("Input list2\n");
printf("If number is 0,stop inputing\n");
printf("数据请从小到大输入\n");
list2=creat(); //调用创建链表的函数
print(list2); //打印第二个循环链表
head=together(list1,list2); //调用合并两个链表的函数
printf("The new list is:\n");
print(head); //打印最后结果
}
