DHU23 单链表ADT模板简单应用算法设计：有序单链表的提纯

问题描述 :

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

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

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

应用5：试设计一个算法，删除有序单链表A中的冗余元素，即使得操作之后的单链表中只保留操作之前表中所有值都不相同的元素，并保持其有序性。要求利用原表中的结点，并释放A表中冗余的结点空间。

参考函数原型：

template<class ElemType>

void Purge_Lk_OL( LinkList<ElemType> &A ); //测试数据限定为整数。实际应用时，不受其限制

输入说明 :

第一行：单链表A的长度

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

输出说明 :

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

第二行：提纯后单链表A的遍历结果

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

输入范例 :

7
3 3 5 5 8 11 11
输出范例 :

3 3 5 5 8 11 11

3 5 8 11

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;
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;}
    void SetHead(LinkNode<ElemType> *p) {*head = *p;}
    ElemType GetElem(int pos);
    bool ListInsert(int pos,ElemType e);
    bool DelFirst( ElemType &e);
    void CreateList_Head(int n, ElemType *A);
    void CreateList_Tail(int n, ElemType *A);
    ElemType ListDelete(int pos);
    bool LocateElem(const ElemType &e, LinkNode<ElemType> *pos);
    bool PriorElem(ElemType cur_e, ElemType &pri_e);
    bool NextElem(LinkNode<ElemType> *p, ElemType &e);
    bool ListTraverse() const;
    void ListReverse();
    LinkNode<ElemType> *getIndex(int n);
};

template <class ElemType>
LinkList<ElemType>::LinkList(LinkList<ElemType> &List)
{
    LinkNode<ElemType> *p = List.head;
    head = new LinkNode<ElemType>(*p);
    LinkNode<ElemType> *p2 = head;
    while(p)
    {
        p2->next = new LinkNode<ElemType>(*p->next);
        p = p->next;
        p2 = p2->next;
    }
}

template<class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator=(LinkList<ElemType> &List)
{
    if(!head)
    {
        this = LinkList(List);
    }
    else
    {
        LinkNode<ElemType> *p1 = List->head;
        LinkNode<ElemType> *p2 = head;
        while(p1 && p2)
        {
            *p1 = *p2;
            p1 = p1->next;
            p2 = p2->next;
        }
        if(p1)
        {
            while(p1)
            {
                p2 = new ElemType(*p1);
                p1 = p1->next;
                p2 = p2->next;
            }
            return *this;
        }
        if(p2)
        {
            LinkNode<ElemType> p3 = p2->next;
            while(p2)
            {
                p3 = p2->next;
                delete p2;
                p2 = p3;
            }
            return *this;
        }
    }
}

template<class ElemType>
void LinkList<ElemType>::ListDestroy()
{
    LinkNode<ElemType> *p = NULL;
    while(head)
    {
        p = head->next;
        delete head;
        head = p;
    }
}

template<class ElemType>
int LinkList<ElemType>::ListLength() const
{
    int len = 0;
    LinkNode<ElemType> *p = head->next;
    while(p)
    {
        len ++;
        p = p->next;
    }
    return len;
}

template<class ElemType>
bool LinkList<ElemType>::ListEmpty() const
{
    if(head->next)
    {
        return false;
    }
    else
    {
        return true;
    }
}

template<class ElemType>
void LinkList<ElemType>::CreateList_Tail(int n,ElemType *A)
{
    LinkNode<ElemType> *p = head;
    int len = ListLength(),cont = 0;
    while(p && cont < len)
    {
        p = p->next;
        cont++;
    }

    if(!p || cont<len)
    {
        return;
    }
    for(int i = 0; i < n; i ++)
    {
        p->next = new LinkNode<ElemType>(*(A+i));
        p = p->next;
    }
}

template<class ElemType>
bool LinkList<ElemType>::ListTraverse()const
{
    if(ListEmpty())
    {
        return false;
    }
    LinkNode<ElemType> *p = head->next;
    while (p)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}

template<class ElemType>
void InputList(LinkList<ElemType> &A)
{
    int n;
    cin>>n;
    ElemType a[n];
    for(int i = 0; i < n; i ++)
    {
        cin>>a[i];
    }
    A.CreateList_Tail(n,a);
}

template<class ElemType>
void Purge_Lk_OL( LinkList<ElemType> &A )
{
    LinkNode<ElemType> *pa = A.GetHead()->next;
    LinkNode<ElemType> *p = A.GetHead();
    while(pa)
    {
        while((p->data) == (pa->data))
        {
            p->next=pa->next;
            if (pa->next)
                pa=pa->next;
            else
            {
                p->next=NULL;
                break;
            }
        }
        p=pa;
        if (pa->next)
            pa=pa->next;
        else
            break;
    }
}

int main()
{
    LinkList<int> AList;
    InputList(AList);
    AList.ListTraverse();
    cout<<endl;
    Purge_Lk_OL(AList);
    cout<<endl;
    AList.ListTraverse();
    return 0;
}