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

梦里梦外; 2022-05-27 12:15 150阅读 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;
    }