luxin.cpp

数据结构中线性表的合并链式实现

#include"iostream.h"
#include"malloc.h"
#include"process.h"
typedef struct lnode{
	int data;
 struct lnode *next;
}lnode,*linklist;
void init(linklist &l)
{
	l=(linklist)malloc(sizeof(lnode));
	if(!l)
		cout<<"分配失败"<<endl;
	else
	{
		l->data=NULL;
		l->next=NULL;
	}
}
void createlist(linklist &l,int n)
{   int i;
	linklist p,s;
	p=(linklist)malloc(sizeof(lnode));
	p=l;
	for(i=n;i>0;--i)
	{
		s=(linklist)malloc(sizeof(lnode));
		cout<<" 请输入链表元素的值：";
		cin>>s->data;
		p->next=s;
		s->next=NULL;
		p=p->next;
	}
}
void mergelist(linklist &A,linklist &B,linklist &C)
{   linklist pa,pb,pc;
    pa=A->next;
	pb=B->next;
	C=pc=A;
	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(B);
}


void listprint(linklist l)
{
	cout<<"--------------------------------"<<endl;
	linklist p=l->next;
	while(p)
	{
		cout<<"链表的元素的值为:"<<p->data<<endl;
		p=p->next;
	}
}
void main()
{
	linklist A,B,C;
    int n;
	init(A);
	init(B);
	init(C);
	cout<<"请输入有序A链表元素的个数：";
	cin>>n;
	createlist(A,n);
	listprint(A);
    cout<<"请输入有序B链表元素的个数：";
	cin>>n;
	createlist(B,n);	
	listprint(B);
	cout<<"所得的有序C链表元素: "<<endl;
	mergelist(A,B,C);
    listprint(C);   
}