线性.cpp

4． 假设有两个按数据元素值非递减有序排列的线性表A和B

#include <stdio.h>
#include<iostream.h>
#include <malloc.h>    //包含malloc,realloc，sizeof函数的头文件
typedef int ElemType;
typedef struct LinkList//定义
{  
	ElemType data;
    struct LinkList  *next;
}LinkList;
void AddList_L(LinkList *L)//添加元素
{
	int n,i;
	LinkList *p2;
	p2=L;
    printf("\n 输入非递减链L节点数:\n");
    scanf("%d",&n);
    printf("\n 输入非递减节点值:\n");
	for (i=1;i<=n;i++)
	{
		LinkList *p1=(LinkList*)malloc(sizeof(LinkList));
		p1->next=NULL;
		scanf("%d",&p1->data);
		p2->next=p1;
		p2=p1;
	}
}
void MergeList_L(LinkList *La,LinkList *Lb,LinkList *Lc){
	//已知单链线性表La和Lb的元素按值非递减排列
	//归并后得到新的单链线性表Lc,元素也按值非递减排列
	LinkList *pa,*pb;
	pa=La->next;pb=Lb->next;
	while(pa&&pb)
	{
		if(pa->data<=pb->data)
		{
			LinkList *s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pa->data;
			s->next=Lc->next;
			Lc->next=s;
			pa=pa->next;
			
			
		}
		else{
			LinkList *s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pb->data;
			s->next=Lc->next;
			Lc->next=s;
			pb=pb->next;
		
		}
	}
	if(pa) /*插入la链的剩余段 */
	{

		if(pa!=NULL)
		{
			
			LinkList *s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pa->data;
			s->next=Lc->next;
			Lc->next=s;
			pa=pa->next;

		}

	}
    /*插入lb链的剩余段*/
    if(pb)
    {

		if(pb!=NULL)
		{
			LinkList *s=(LinkList *)malloc(sizeof(LinkList));
			s->data=pb->data;
			s->next=Lc->next;
			Lc->next=s;
			pb=pb->next;
			
		}
		
		
	} 
	
}//MergeList_L

void main()
{
	LinkList *la=(LinkList *)malloc(sizeof(LinkList));
	la->next=NULL;
	AddList_L(la);
	LinkList *lb=(LinkList *)malloc(sizeof(LinkList));
	lb->next=NULL;
	AddList_L(lb);
	LinkList *lc=(LinkList *)malloc(sizeof(LinkList));
	lc->next=NULL;
	MergeList_L(la,lb,lc);
	printf("\n合并后的链表\n");
	LinkList *q=lc->next;

	
	while(q!=NULL) 
	{
		cout<<q->data<<" ";
		cout<<endl;
		q=q->next;
	}

}