#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *pnext;
} NODE,*PNODE;
PNODE chuangjian(void);
void bianli(PNODE phead);
PNODE paixu(PNODE phead);
PNODE hebing(PNODE phead1,PNODE phead2);
int lenth(PNODE phead);
int main(void)
{ PNODE phead1=NULL;
PNODE phead2=NULL;
PNODE phead3=NULL;
printf("請輸入鏈表1的信息:\n");
phead1=chuangjian();
printf("鏈表1的信息為:");
paixu(phead1);
bianli(phead1);
printf("請輸入鏈表2的信息:\n");
phead2=chuangjian();
printf("鏈表2的信息為:");
paixu(phead2);
bianli(phead2);
printf("合並後的鏈表為:");
phead3=hebing(phead1,phead2);
bianli(phead3);
system("pause");
return 0;
}
PNODE chuangjian(void)
{
PNODE phead=(PNODE)malloc(sizeof(NODE));
PNODE ptail;
ptail=phead;
ptail->pnext=NULL;
int len=0;
int i=0;
int val=0;
printf("請輸入鏈表的長度:");
scanf_s("%d",&len);getchar();
for(i=0;i<len;i++)
{
scanf_s("%d",&val);getchar();
PNODE pnew=(PNODE)malloc(sizeof(NODE));
if(pnew==NULL)
{
printf("分配失敗,程序終止!\n");
exit(-1);
}
pnew->data=val;
ptail->pnext=pnew;
pnew->pnext=NULL;
ptail=pnew;
}
return phead;
}
void bianli(PNODE phead)
{
PNODE p;
p=phead->pnext;
while(p!=NULL)
{ printf("%d ",p->data);
p=p->pnext;
}
printf("\n");
return;
}
PNODE paixu(PNODE phead)
{
PNODE p,q;
int t;
int i,j;
int len=lenth(phead);
for(i=0,p=phead->pnext;i<len-1;i++,p=p->pnext)
for(j=0,q=p->pnext;j<len-i-1;j++,q=q->pnext)
{
if(p->data>q->data)
{
t=p->data;
p->data=q->data;
q->data=t;
}
}
return phead;
}
PNODE hebing(PNODE p1,PNODE p2)
{
PNODE ptail,pnew,phead1=p1,phead2=p2,phead3;
phead3=(PNODE)malloc(sizeof(NODE));
ptail=phead3;
ptail->pnext=NULL;
while(phead1&&phead2)
{
if(phead1->data<=phead2->data)
{
pnew=(PNODE)malloc(sizeof(NODE));
pnew->data=phead1->data;
ptail->pnext=pnew;
pnew->pnext=NULL;
ptail=pnew;
phead1=phead1->pnext;
}
else
{
pnew=(PNODE)malloc(sizeof(NODE));
pnew->data=phead2->data;
ptail->pnext=pnew;
pnew->pnext=NULL;
ptail=pnew;
phead2=phead2->pnext;
}
}
while(phead1)
{
pnew=(PNODE)malloc(sizeof(NODE));
pnew->data=phead1->data;
ptail->pnext=pnew;
pnew->pnext=NULL;
ptail=pnew;
phead1=phead1->pnext;
}
while(phead2)
{
pnew=(PNODE)malloc(sizeof(NODE));
pnew->data=phead2->data;
ptail->pnext=pnew;
pnew->pnext=NULL;
ptail=pnew;
phead2=phead2->pnext;
}
return phead3;
}
int lenth(PNODE phead)
{
int i=0;
PNODE p;
p=phead->pnext;
while(p!=NULL)
{
p=p->pnext;
i++;
}
return i;
}