题目描述
新建两个链表,一个无序,一个降序。然后将无序的链表插入到降序的链表中,并使原来降序的链表仍然保持降序。输入的整形以空格隔开
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(SNODE)
typedef struct node
{
int num;
struct node *next;
}SNODE;
//打印函数
void print(SNODE* head)
{
head=head->next;
while(head!=NULL)
{
printf("%d ",head->num);
head=head->next;
}
putchar('\n');
}//print
//创建降序链表
void creatLinkDown(int n,SNODE *head)
{
SNODE *p,*q=head;;
p=(SNODE*)malloc(LEN);
p->num=n;
if(head->next==NULL)//表空
{
p->next=NULL;
head->next=p;
}
else
{
while(q->next!=NULL)//找到第一个比待插入节点num值小的节点,插入其前面
{
if(q->next->num < p->num)
{
p->next=q->next;
q->next=p;
break;
}
q=q->next;
}
if(q->next==NULL)//没有比待插入节点num小的节点则插入表尾
{
p->next=NULL;
q->next=p;
}
}
}//creatLinkDown
//创建无序链表
void creatLink(int n,SNODE *head)
{
SNODE *p,*q=head;
while(q->next!=NULL) q=q->next;
p=(SNODE *)malloc(LEN);
p->next=NULL;
p->num=n;
q->next=p;
}//creatLink
//插入链表
void combine(SNODE *headDown,SNODE *head)
{
SNODE *p=head,*q=headDown;
while(p->next!=NULL)//当前链表不空
{
q=headDown;
while(q->next!=NULL)//从要插入的链表中找到比当前节点num小的节点,插入其前面
{
if(q->next->num < p->next->num)
{
p=p->next;
head->next=p->next;
p->next=q->next;
q->next=p;
break;
}
q=q->next;
}
if(q->next==NULL)//没有找到比当前节点num小的节点,插入尾部
{
p=p->next;
head->next=p->next;
p->next=NULL;
q->next=p;
}
p=head;
}
}//combine
int main()
{
SNODE *heada,*headb;
heada=(SNODE*)malloc(LEN);//无序链表头节点
heada->next=NULL;
heada->num=-1;
headb=(SNODE*)malloc(LEN);//降序链表头节点
headb->next=NULL;
headb->num=-1;
int n;
char ch;
while(1)//创建无序链表
{
scanf("%d",&n);//读入整形
creatLink(n,heada);//加入无序链表
ch=getchar();//吃掉空格
if(ch=='\n') break;
}
while(1)//创建有序链表
{
scanf("%d",&n);
creatLinkDown(n,headb);
ch=getchar();
if(ch=='\n') break;
}
print(heada);//打印无序链表
print(headb);//打印降序链表
combine(headb,heada);//插入链表
print(headb);//打印插入后的表
return 0;
}//main