02-线性结构1 两个有序链表序列的合并（15 分）-蒲公英云

02-线性结构1 两个有序链表序列的合并（15 分）

梦里梦外; 2022-05-27 12:15 257阅读 0赞

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node
{
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */
List Merge( List L1, List L2 );
int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}
/* 你的代码将被嵌在这里 */
List Read()
{
    List head,p,q;
    head = (List)malloc(sizeof(struct Node));
    head->Next = NULL;
    q = head;
    int n,x;
    scanf("%d",&n);
    int i;
    for(i=0; i<n; i++)
    {
        p = (List)malloc(sizeof(struct Node));
        scanf("%d",&x);
        p->Next = NULL;
        p->Data = x;
        q->Next = p;
        q = p;
    }
    return head;
}
void Print( List L )
{
    L = L->Next;
    if(!L)
        printf("NULL");
    while(L)
    {
        printf("%d ",L->Data);
        L = L->Next;
    }
    printf("\n");
}
List Merge( List L1, List L2 )
{
    List L,q;
    L = (List)malloc(sizeof(struct Node));
    L->Next = NULL;
    q = L;
    List p1, p2;
    p1 = L1->Next;
    p2 = L2->Next;
    while(p1 && p2)
    {
        if(p1->Data >= p2->Data)
        {
            q->Next = p2;
            q = p2;
            p2 = p2->Next;
        }
        else if(p1->Data <= p2->Data)
        {
            q->Next = p1;
            q = p1;
            p1 = p1->Next;
        }
    }
    while(p1)
    {
        q->Next = p1;
        q = p1;
        p1 = p1->Next;
    }
    while(p2)
    {
        q->Next = p2;
        q = p2;
        p2 = p2->Next;
    }
    L1->Next = NULL;
    L2->Next = NULL;
    return L;
}