线性表算法设计题（一）

题目

将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。

算法思想

从首元结点开始进行比较，当两个链表La和Lb均未到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后的表中无重复的元素。当一个表到达表尾结点为空时，将非空表的剩余元素直接链接在Lc表的最后。最后释放表Lb的头结点。

完整代码

#include <iostream>
#include <stdlib.h>
using namespace std;

//将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

void ListRead(LinkList &L){
    //读取链表，即给链表添加数据 
    int length;
    LinkList  p = NULL, q;
    cout << "Input the length:";
    cin >> length;
    L = (LinkList)malloc(sizeof(struct LNode));
    L -> next = NULL;
    q = L;
    for(int i = 0; i < length; ++ i){
        p = (LinkList)malloc(sizeof(struct LNode));     //生成头结点 
        cin >> p -> data;
        q -> next = p;
        q = q -> next;
    }
    p -> next = NULL;
}

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){
    //将两个递增的有序链表La和Lb合并为一个递增有序的有序链表Lc
    LinkList pa, pb, pc,q;
    pa = La -> next;                                  
    pb = Lb -> next;
    //pa和pb分别是链表La和Lb的工作指针，初始化为响应链表的首元结点 
    Lc = pc = La;                                 //用La的头结点作为Lc的头结点 
    while(pa && pb){                              //两个链表的La和Lb均未到表尾结点 
        if(pa -> data < pb -> data){
            //取较小者La中的元素，将pa链接在pc的后面，pa指针后移 
            pc -> next = pa;
            pc = pa;
            pa = pa -> next;
        }
        else if(pa -> data > pb -> data){
            //取较小者Lb中的元素，将pb链接在pc后面，pb指针后移  
            pc -> next = pb;
            pc = pb;
            pb = pb -> next;
        }
        else{
            //相等时取La中的元素，删除Lb中的元素 
            pc -> next = pa;
            pc = pa;
            pa = pa -> next;
            q = pb -> next;
            delete pb;
            pb = q;
        }
    }
    pc -> next = pa ? pa : pb;                   //将非空表的剩余元素直接链接在Lc表的最后 
    delete Lb;                                   //释放Lb的头结点 
}

void ListPrint(LinkList L){
    //打印链表 
    LNode *p;
    p = L -> next;
    if(L -> next == NULL){
        cout << "NULL" << endl;
    }
    while(p){
        cout << p -> data << "\t";
        p = p -> next;
    }
    cout << endl; 
}

int main(){
    LinkList La, Lb, Lc;
    ListRead(La);
    ListRead(Lb);
    MergeList(La,Lb,Lc);
    cout << "合并之后的链表为：" << endl; 
    ListPrint(Lc); 
    return 0;
} 

结果显示

TIM图片20191021194520.png