DHU21 单链表ADT模板简单应用算法设计：2个单链表的交叉归并

问题描述 :

目的：使用C++模板设计单链表的抽象数据类型（ADT）。并在此基础上，使用单链表ADT的基本操作，设计并实现单链表的简单算法设计。

内容：（1）请使用模板设计单链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的ADT原型文件。）

（2）ADT的简单应用：使用该ADT设计并实现单链表应用场合的一些简单算法设计。

应用3：假设线性表A=(a1,a2,...,am)，线性表B=(b1,b2,...,bn)，现要求设计一个算法，使用带头结点的单链表存储结构，按照下列规则合并A、B为线性表C。即：A和B的元素间隔排列，且使用A和B的原存储空间，且B不再单独存在。输入中的单链表的长度不得在该算法中利用，仅作为建表使用。

参考函数原型：

template<class ElemType>

void Merge_L( LinkList<ElemType> &A, LinkList<ElemType> &B );

输入说明 :

第一行：单链表A的长度

第二行：单链表A的数据元素（数据元素之间以空格分隔）

第三行：单链表B的长度

第四行：单链表B的数据元素（数据元素之间以空格分隔）

输出说明 :

第一行：单链表A的遍历结果

第二行：单链表B的遍历结果

第三行：交叉归并后单链表A的遍历结果

（输入与输出之间以空行分隔）

输入范例 :

10
13 5 27 9 32 123 76 98 54 87
5
1 3 7 8 11
输出范例 :

13 5 27 9 32 123 76 98 54 87
1 3 7 8 11

13 1 5 3 27 7 9 8 32 11 123 76 98 54 87

image.png

#include <iostream>
using namespace std;

/* 单链表的结点定义 */
template<class ElemType>
struct LinkNode
{
    ElemType data;
    LinkNode<ElemType>* next;
    LinkNode(LinkNode<ElemType>* ptr = NULL) { next = ptr; }
    LinkNode(const ElemType& item, LinkNode<ElemType>* ptr = NULL)
        //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    {
        next = ptr;
        data = item;
    }
};

//带头结点的单链表
template<class ElemType>
class LinkList
{
private:
    LinkNode<ElemType>* head;   // 头结点
    LinkNode<ElemType>* tail;   // 尾结点
public:
    //无参数的构造函数
    LinkList() { head = new LinkNode<ElemType>; }
    //带参数的构造函数
    LinkList(const ElemType& item) { head = new LinkNode<ElemType>(item); }
    //拷贝构造函数
    LinkList(LinkList<ElemType>& List);
    //析构函数
    ~LinkList() { ListDestroy(); }
    //重载函数:赋值
    LinkList<ElemType>& operator=(LinkList<ElemType>& List);
    //销毁链表
    void ListDestroy();
    //清空链表
    void ListClear();
    //返回链表的长度
    int ListLength() const;
    //判断链表是否为空表
    bool ListEmpty() const;
    //在首节点之前插入一个结点
    bool InsFirst(ElemType e);
    //获取链表头结点
    LinkNode<ElemType>* GetHead() const { return head; }
    //获得链表尾结点
    LinkNode<ElemType>* GetTail();
    //设置链表头结点
    void SetHead(LinkNode<ElemType>* p) { head->next = p; }
    //用e返回链表的第i个元素
    ElemType GetElem(int pos);
    //返回第pos的结点指针;
    LinkNode<ElemType>* GetNode(int pos);
    //在链表的第pos个位置之前插入e元素
    bool ListInsert(int pos, ElemType e);
    //删除链表的首结点
    //bool DelFirst( ElemType &e);
    //表头插入法动态生成链表
    void CreateList_Head(int n, ElemType* A);
    //表尾插入法动态生成链表
    void CreateList_Tail(int n, ElemType* A);
    //删除链表的第index个位置的元素
    ElemType ListDelete(int index);
    //compare函数，用来判断a和b是否相等
    bool compare(ElemType a, ElemType* b) { return a == (*b); }
    //按指定条件查找，返回指向第一个符合条件（=e）的元素的指针
    LinkNode<ElemType>* LocateElem(const ElemType& e);
    //返回pos位置的后继结点的指针
    LinkNode<ElemType>* NextNode(LinkNode<ElemType>* pos);
    //返回pos位置的前驱结点的指针
    LinkNode<ElemType>* PriorNode(LinkNode<ElemType>* pos);
    //遍历链表
    bool ListTraverse() const;
};

template<class ElemType>
void Exchange_L(LinkList<ElemType>& L, int m)
{
    LinkNode<ElemType>* p, *temp;
    p = L.GetNode(m);
    if (p == NULL)return;
    temp = L.GetTail();
    temp->next = L.GetHead()->next;
    L.SetHead(p->next);
    p->next = NULL;
}

template<class ElemType>
void Linklist_Contact(LinkList<ElemType>& A, LinkList<ElemType>& B)
{
    LinkNode<ElemType>* tail;
    tail = A.GetTail();
    tail->next = B.GetHead()->next;
    B.GetHead()->next = NULL;
}

template<class ElemType>
void Merge_L(LinkList<ElemType>& A, LinkList<ElemType>& B)
{
    LinkNode<ElemType>* p, * q, * r;
    p = A.GetHead()->next;
    q = B.GetHead()->next;
    if (q == NULL)return;
    for (r = q->next;p != NULL;)
    {
        if (p->next == NULL)
        {
            p->next = q;
            break;
        }
        q->next = p->next;
        p->next = q;
        p = q->next;
        q = r;
        if (r != NULL)r = r->next;
        else break;
    }
    B.GetHead()->next = NULL;
}

int main()
{
    LinkList<string>LA,LB;
    int n;
    string a[1000];
    cin >> n;
    for (int i = 0;i < n;i++)
        cin >> a[i];
    LA.CreateList_Tail(n, a);
    LA.ListTraverse();
    cin >> n;
    for (int i = 0;i < n;i++)
        cin >> a[i];
    LB.CreateList_Tail(n, a);
    LB.ListTraverse();
    cout << endl;
    Merge_L(LA, LB);
    LA.ListTraverse();
}

//拷贝构造函数
template<class ElemType>
LinkList<ElemType>::LinkList(LinkList<ElemType>& List)
{
    head = new LinkNode<ElemType>;
    tail = head;
    LinkNode<ElemType>* r;  //r为指向尾结点的指针
    r = tail;

    LinkNode<ElemType>* p = List.head->next;    //p为指向待插入结点的指针

    while (p)
    {
        LinkNode<ElemType>* q = new LinkNode<ElemType>;
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;
    }
    r->next = NULL;
    tail = r;
}

//重载函数:赋值
template<class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator=(LinkList<ElemType>& List)
{
    head = new LinkNode<ElemType>;
    tail = head;
    LinkNode<ElemType>* r;  //r为指向尾结点的指针
    r = tail;

    LinkNode<ElemType>* p = List.head->next;    //p为指向待插入结点的指针

    while (p)
    {
        LinkNode<ElemType>* q = new LinkNode<ElemType>;
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;
    }
    r->next = NULL;
    tail = r;
    return *this;
}

//销毁链表
template<class ElemType>
void LinkList<ElemType>::ListDestroy()
{
    //销毁以head为头指针的单链表，释放链表中所有结点空间
    LinkNode<ElemType>* p;
    while (head)
    {
        p = head;
        head = head->next;
        delete p;
    }
    head = NULL;
}

//清空链表
template<class ElemType>
void LinkList<ElemType>::ListClear()
{
    //清空以head为头指针的单链表，释放原链表中结点空间，保留头结点
    LinkNode<ElemType>* p = head->next;
    while (p)
    {
        head->next = p->next;
        delete p;
        p = head->next;
    }
}

//返回链表长度
template<class ElemType>
int LinkList<ElemType>::ListLength() const
{
    //返回链表的长度
    int length = 0;
    LinkNode<ElemType>* p;
    p = head->next;
    while (p)
    {
        ++length;
        p = p->next;
    }

    return length;
}

//判断链表是否为空表
template<class ElemType>
bool LinkList<ElemType>::ListEmpty() const
{
    //判断链表是否为空
    if (head->next == NULL) return true;
    return false;
}

//获得链表尾结点
template<class ElemType>
LinkNode<ElemType>* LinkList<ElemType>::GetTail()
{
    LinkNode<ElemType>* p;
    for (p = head;p->next != NULL;p = p->next);
    return p;
}

//在首节点之前插入一个结点
template<class ElemType>
bool LinkList<ElemType>::InsFirst(ElemType e)
{
    LinkNode<ElemType>* p;
    p = new LinkNode<ElemType>;
    p->next = head->next;
    head->next = p;
    p->data = e;
    return true;
}

//返回第i个数据
template<class ElemType>
ElemType LinkList<ElemType>::GetElem(int i)
{
    LinkNode<ElemType>* p;
    p = head->next;
    int pos=1;
    while (p&&pos!=i)
    {
        pos++;
        p = p->next;
    }
    if (pos == i)return p->data;
    else return 0;
}

//返回第pos的结点指针;
template<class ElemType>
LinkNode<ElemType>* LinkList<ElemType>::GetNode(int pos)
{
    if (pos < 1)return NULL;
    int i;
    LinkNode<ElemType>* p;
    p = head->next;
    for (i = 1;i != pos && p != NULL;i++, p = p->next);
    return p;
}

//在链表的第pos个位置之前插入e元素
template<class ElemType>
bool LinkList<ElemType>::ListInsert(int pos, ElemType e)
{
    if (pos > ListLength()||pos<=0)return false;
    LinkNode<ElemType>* p, *q, *r;
    p = head->next;
    q = head;
    int i = 1;
    while (p && pos != i)
    {
        i++;
        q = p;
        p = p->next;
    }
    r = new LinkNode<ElemType>;
    r->data = e;
    r->next = p;
    q->next = r;
    return true;
}

//表头插入动态生成链表
template<class ElemType>
void LinkList<ElemType>::CreateList_Head(int n, ElemType* A)
{
    LinkNode<ElemType>* p;  //p为指向待插入结点的指针
    for (int i = 0; i < n; i++)
    {
        LinkNode<ElemType> p = new LinkNode<ElemType>;
        p->data = A[i];
        p->next = head->next;
        head->next = p;
        if (i == 0)
            tail = p;
    }
}

//表尾插入动态生成链表
template<class ElemType>
void LinkList<ElemType>::CreateList_Tail(int n, ElemType* A)
{
    LinkNode<ElemType>* r;  //r为指向尾结点的指针
    r = head;
    LinkNode<ElemType>* p;  //p为指向待插入结点的指针
    for (int i = 0; i < n; i++)
    {
        p = new LinkNode<ElemType>;
        p->data = A[i];

        r->next = p;
        r = p;
    }
    r->next = NULL;
    tail = r;
}

//删除链表的第index个位置的元素
template<class ElemType>
ElemType LinkList<ElemType>::ListDelete(int index)
{
    //若1≤index≤Length，则删除单链表中第index个元素并以e带回其值，返回函数值为TRUE，
    // 否则不进行删除操作，且返回函数值为FALSE
    LinkNode<ElemType>* p, * q;
    ElemType e;
    p = head;
    int j = 0;
    while (p->next && j < index - 1)    // 查找第pos-1个结点，并令指针p指向其前驱
    {
        p = p->next;
        ++j;
    }  // while
    if (!p->next || (j > index - 1)) return 0;   // 参数不合法，pos小于1或者大于表长+1
    q = p->next;
    p->next = q->next;  // 修改指针
    e = q->data;
    if (q == tail) tail = p; //删除了最后一个结点，需要修改尾指针
    delete(q);  // 释放结点空间
    return e;
}

//按指定条件查找，返回指向第一个符合条件（=e）的元素的指针
template <class ElemType>
LinkNode<ElemType>* LinkList<ElemType>::LocateElem(const ElemType& e)
{
    LinkNode<ElemType>* p;
    p = head->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    return p;
}

//返回pos位置的后继结点的指针
template<class ElemType>
LinkNode<ElemType>* LinkList<ElemType>::NextNode(LinkNode<ElemType>* pos)
{
    return pos->next;
}

//返回pos位置的前驱结点的指针
template<class ElemType>
LinkNode<ElemType>* LinkList<ElemType>::PriorNode(LinkNode<ElemType>* pos)
{
    LinkNode<ElemType>* p, * q;
    for (p = head, q = head->next;q != NULL && q != pos;p = q, q = q->next);
    if (q == NULL||p==head)return NULL;
    return p;
}

//遍历链表
template<class ElemType>
bool LinkList<ElemType>::ListTraverse() const
{
    LinkNode<ElemType>* p;
    p = head->next;
    if (p == NULL)return false;
    for (;p != NULL;p = p->next)
        cout << p->data<<" ";
    cout << endl;
    return true;
}