数据结构：归并La和Lb得到新的单链表Lc，Lc的元素也按值非递减排列

深藏阁楼爱情的钟 2022-02-27 00:58 135阅读 0赞

#include <iostream>
    #include <stdio.h>
    #include<stdlib.h>
    using namespace std;
    typedef  int  Status;
    typedef  int ElemType;
    typedef struct LNode
    {
    ElemType       data;
    struct LNode  *next;
    }LNode, *LinkList;
    Status InitList(LinkList &L)
    {
     L = (LinkList)malloc(sizeof(LNode));
        if (!L)
           exit(0);
        L->next = NULL;
        return 1;
    }
    Status CreateList(LinkList L,int n)  //头插法
    {
     LinkList p,q;
        p = L;//第一步，取到头结点,两个指针指向同一内存，改变p指向的内存，L指向的内存不变，L仍为头结点
        printf("请输入%d个数：\n", n);
        for (int i = 1; i <= n; i++)
     {
            q = (LinkList)malloc(sizeof(LNode));
            if (!p)
      {
                printf("p的初始化出现问题！\n");
                return 0;
            }
             scanf("%d", &q->data);
             q->next = p->next;//第二步链接两个结点
             p->next = q;//第二步链接两个结点
             p = q;//关键的一步，更换位置，进行下次循环
            }
            return 1;
     }
    Status GetLinkList(LinkList L) //顺序输出这个链表
    {
        if (!L->next)
        {
            printf("链表没有节点，不能输出!\n");
         return 0;
        }
        LinkList p;
        p = L->next;
        while (p)
        {
           printf("%d", p->data);
           p = p->next;
        }
        return 1;
    }
    Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
     //已知单链线性表La和Lb的元素按值非递减排列
     //归并La和Lb得到新的单链表Lc，Lc的元素也按值非递减排列
     LinkList pa,pb,pc;
      pa=La->next; pb=Lb->next;
      Lc=pc=La;//用La头结点作为Lc的头结点
      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);//释放Lb的头结点
     }
    int main()
    {
     LinkList L1,L2,L3;
     int n,m;
     InitList(L1);
     InitList(L2);
     printf("表1.请输入数据的个数：");
     scanf("%d",&m);
     CreateList(L1,m);
     printf("表2.请输入数据的个数：");
     scanf("%d",&n);
     CreateList(L2,n);
     GetLinkList(L1);
     printf("\n");
     GetLinkList(L2);
     printf("\n");
     printf("两表合并后为：\n");
        MergeList_L(L1,L2,L3);
     GetLinkList(L3);
     return 0;
    }

![程序执行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQyNDE1NA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQyNDE1NA_size_16_color_FFFFFF_t_70]: /images/20220227/c3e7b715c69e4283952c8bb1558eb771.png