数据结构链表合并两个有序的单链表 C语言版

迈不过友情╰ 2022-06-09 04:23 161阅读 0赞

#include <cstdio>
    #include <stdlib.h>
    typedef struct Node
    {
        int data;
        struct Node * next;
    } Node,* Linklist;  //定义链表的结点，链表头
    
    void Initlist (Linklist *L)  //初始化链表
    {
        *L=(Linklist)malloc(sizeof(Node));
        (*L)->next=NULL;
    }
    
    void CreateFromTail(Linklist L) //尾插发建表
    {
        Node *r,*s;
        r=L;  //r总是指向链表的最后结点，s是新的结点
        int flag=1; int num;
        while(flag)
        {
            scanf("%d",&num);
            if(num!= -1)
            {
                s=(Node *) malloc(sizeof(Node));
                s->data=num;
                r->next=s;
                r=s;
            }
            else{
                flag=0;
                r->next=NULL;
            }
        }
        return ;
    }
    
    void Output(Linklist L)  //输出单链表
    {
        Node *temp;
        temp=L->next;
        while(temp !=NULL)
        {
            printf("%d ",temp->data);
            temp=temp->next;
        }
        printf("\n");
    }
    
    Linklist Unionlist(Linklist LA,Linklist LB)
    {
        Linklist LC;
        Initlist(&LC);
        Node *pa,*pb,*r;
        pa=LA->next; pb=LB->next;  r=LC;
        while(pa!=NULL && pb!=NULL)
        {
            if(pa->data<=pb->data)
            {
                r->next=pa;
                r=pa;
                pa=pa->next;
            }
            else{
                r->next=pb;
                r=pb;
                pb=pb->next;
            }
        }
        if(pa)
            r->next=pa;
        else
            r->next=pb;
        free(LB);
        free(LA);
        return(LC);
    }
    
    
    
    int main()
    {
        Linklist LA,LB,LC;
        Initlist(& LA);
        Initlist(& LB);
        printf("输入递增单链表LA 以-1为结束标志\n");
        CreateFromTail(LA);
        Output(LA);
    
        printf("输入递增单链表LB 以-1为结束标志\n");
        CreateFromTail(LB);
        Output(LB);
        if(LA->next==NULL) printf("srwefewfawefw\n");
        LC=Unionlist(LA,LB);
        printf("合并为一个有序的单链表为\n");
        Output(LC);
    }