Question

数据结构（C语言版）用链表归并两个集合，求大神帮我修改一下程序。

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode * next;
}LNode,* LinkList;
void CreateList_L(LinkList &L,int n)//逆位序输入n个元素的值，建立带表头结点的单链线性表L
{ int i;LNode * p;
L=(LinkList) malloc(sizeof(LNode));
L->next=NULL;//先建立一个带头结点的单链表
for(i=n;i>0;--i)
{ p=(LinkList) malloc(sizeof(LNode));//生成新结点
scanf("%d",&p->data);//输入元素值
p->next=L->next;L->next=p;//插入到表头
}
}
/*Status InitList(LinkList &L)
{ L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
return OK;
}*/
void MergeList_L(LinkList &L1,LinkList &L2,LinkList &L3)//已知单链线性表La和Lb的元素按值非递减排列
{ LNode * pa, * pb, * pc; //归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
pa=L1->next;pb=L2->next;
L3=pc=L1;//用La的头结点作为Lc的头结点
while(pa && pb)
{ if(pa->data<=pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else
{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb;//插入剩余段
free(L2);//释放Lb的头结点
}
void Print_L(LinkList &L)//打印链表
{ L=L->next;
if(L=NULL)
printf("空集");
else
{
printf("%d",L->data);
L= L->next;
}
printf("\n");
}
void main()
{ int m,n;
LinkList La, Lb, Lc;
printf("请输入集合La中元素的个数:\n");
scanf("%d",&m);
printf("请输入集合La:\n");
CreateList_L(La,m);
printf("请输入集合Lb中元素的个数:\n");
scanf("%d",&n);
printf("请输入集合Lb:\n");
CreateList_L(Lb,n);
// InitList(Lc);
MergeList_L(La,Lb,Lc);
Print_L(Lc);
}

Answer 1

我把你的程序改好了，先复制在下面吧

#include<stdio.h>
#include<malloc.h>
#include<math.h>

#define OK 1

typedef int Status;
typedef int ElemType;

typedef struct LNode
{ 
	ElemType data;
	struct LNode * next;
}LNode,* LinkList;

void CreateList_L(LinkList &L,int n)//逆位序输入n个元素的值，建立带表头结点的单链线性表L
{ 
	int i;
	LNode * p;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;//先建立一个带头结点的单链表

	for(i=n;i>0;--i)
	{ 
		p=(LinkList)malloc(sizeof(LNode));//生成新结点
		printf("请输入第%d个结点的数据:\n",i);
		scanf("%d",&p->data);//输入元素值

		p->next=L->next;
		L->next=p;//插入到表头
	}
}
/*Status InitList(LinkList &L)
 { L=(LinkList)malloc(sizeof(LNode)); 
   L->next=NULL; 
   return OK;
 }*/

void MergeList_L(LinkList &L1,LinkList &L2,LinkList &L3)//已知单链线性表La和Lb的元素按值非递减排列
{ 
	LNode *pa, *pb, *pc;                    //归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列

	pa=L1->next;
	//printf("%d\n",pa->data);

	pb=L2->next;
	//printf("%d\n",pb->data);

	L3=L1;//用La的头结点作为Lc的头结点
	pc=L3;

	while(pa!=NULL && pb!=NULL)
	{ 
		if(pa->data<=pb->data)
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else
		{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
	}
	pc->next=pa?pa:pb;//插入剩余段
	free(L2);//释放Lb的头结点
}

void Print_L(LinkList &L)//打印链表
{   
	LNode *p;

	p=L->next;
	if(p==NULL)
	{
		printf("该链表为空\n");
	}
	else	
	{
		while(p!=NULL)
		{
			printf("%-5d",p->data);
			p=p->next;
		}
	}
	printf("\n");
}
void main()
{ 	
	int m,n;
    LinkList La, Lb, Lc;

	printf("请输入链表La中结点的个数:\n");
	scanf("%d",&m);
	printf("请输入链表La:\n");
    CreateList_L(La,m);
	printf("链表La为:\n");
	Print_L(La);

	printf("请输入链表Lb中结点的个数:\n");
	scanf("%d",&n);
	printf("请输入链表Lb:\n");
	CreateList_L(Lb,n);
	printf("链表Lb为:\n");
	Print_L(Lb);

	// InitList(Lc);
    MergeList_L(La,Lb,Lc);
	printf("链表Lc为:\n");
	Print_L(Lc);
}

自定义函数Print_L()那里有一些问题，打印链表的时候不能移动头结点，否则归并的时候就找不到头结点了。可以定义一个指针变量p，用来移动到下一个节点。别的没什么问题了。

运行结果如下，你也可以自己跑一下程序，就看到结果了。最后链表Lc也是有序的。