数据结构线性表单链表的归并

绝地灬酷狼 2022-09-18 14:52 217阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <iostream.h>
    
    #define OK          1
    #define ERROR       0
    #define OVERFLOW    -2
    
    typedef int ElemType;
    
    typedef struct LNode
    {
    	ElemType data;
    	struct LNode *next;
    }LNode, *LinkList;
    
    void CreateList_L(LinkList &L, int n)
    {
    	int i;
    	LinkList p,q;
    	L = (LinkList) malloc (sizeof(LNode));
    	if (!L)
    	{
    		exit(OVERFLOW);
    	}
    	p = L;
    	for (i=0; i<n; i++)
    	{
    		q = (LinkList) malloc (sizeof(LNode));
    		if (!q)
    		{
    			exit(OVERFLOW);
    		}
    		scanf("%d",&q->data);
    		p->next = q;
    		p = q;
    	}
    	p->next = NULL;
    
    
    }
    
    
    void Display(LinkList L)
    {
    	LinkList p = L->next;
    	while (p != NULL)
    	{
    		printf("%d ",p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc)
    {
    	LinkList pa,pb,pc;
    	pa = La->next;
    	pb = Lb->next ;
    	Lc = pc = La;
    	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(Lb);
    }
    
    
    
    int main()
    {
    	int n;
    	LinkList La,Lb,Lc;
    	printf("请输入您要创建单链表La的元素的个数:");
    	scanf("%d",&n);
    	CreateList_L(La,n);
    	printf("请输入您要创建单链表Lb的元素的个数:");
    	scanf("%d",&n);
    	CreateList_L(Lb,n);
    	printf("两个链表归并后的链表是:");
    	MergeList_L(La,Lb,Lc);
    	Display(Lc);
    
    
    
    	return 0;
    }