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;   // 头结点
    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;
};

//调换前m个元素和后n个元素
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;
}

//把链表B连接链表A后面
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;
}

//把链表B逐个插入到链表A
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;
}

//有序链表A、B的合并
template<class ElemType>
void Merge_L_Order(LinkList<ElemType>& A, LinkList<ElemType>& B)
{
    LinkNode<ElemType>* p, * q, * r, * s;
    p = A.GetHead();q = p->next;
    r = B.GetHead();s = r->next;
    while (q != NULL && s != NULL)
    {
        for (;q != NULL && q->data < s->data;p = q, q = q->next);
        if (q == NULL)
        {
            p->next = s;break;
        }
        r = s;s = s->next;
        p->next = r;r->next = q;
        p = r;
    }
    B.GetHead()->next = NULL;
}

//有序单链表的提纯
template<class ElemType>
void Purge_Lk_OL(LinkList<ElemType>& A) //测试数据限定为整数。实际应用时，不受其限制
{
    LinkNode<ElemType>* p, *q;
    p = A.GetHead()->next;
    while (p != NULL)
    {
        for (q = p->next;q != NULL && q->data == p->data;)
        {
            p->next = q->next;
            delete q;
            q = p->next;
        }
        p = p->next;
    }
}

int main()
{
    LinkList<int>LA,LB;
    int n;
    int a[1000];
    cin >> n;
    for (int i = 0;i < n;i++)
        cin >> a[i];
    LA.CreateList_Tail(n, a);
    LA.ListTraverse();
    cout << endl;
    Purge_Lk_OL(LA);
    /*cin >> n;
    for (int i = 0;i < n;i++)
        cin >> a[i];
    LB.CreateList_Tail(n, a);
    LB.ListTraverse();
    cout << endl;
    Merge_L_Order(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;
}

我

#include <bits/stdc++.h>
using namespace std;

struct node{
    int number;
    int code;
};
typedef node ElemType;
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 CirLinkList
{
   private:
      LinkNode<ElemType> *head;   // 头结点
      LinkNode<ElemType> *tail;   // 尾结点
   public:
      //无参数的构造函数
      CirLinkList(){head = new LinkNode<ElemType>; tail = head; head->next = head;}

      //带参数的构造函数
      CirLinkList(const ElemType &item){head = new LinkNode<ElemType>(item); tail = head; head->next = head;}
      //销毁链表
      void ListDestroy();
      //清空链表
      void ListClear();
      //拷贝构造函数
      CirLinkList(CirLinkList<ElemType> &List);
      //返回链表的长度
      int ListLength() const;
      //判断链表是否为空表
      bool ListEmpty() const;
      //获取循环链表头结点
      LinkNode<ElemType>* GetHead() { return head;}
      //获取循环链表尾结点
      LinkNode<ElemType>* GetTail() { return tail;}
      //析构函数
      ~CirLinkList(){ListDestroy();}


      //设置链表头结点
      void SetHead(LinkNode<ElemType> *p){ head = p;}
      //设置链表尾结点
      void SetTail(LinkNode<ElemType> *p){ tail = p;}
      //在链表的第pos个位置之后插入e元素
      bool ListInsert_next(int pos,ElemType e);
      //表头插入法动态生成链表
      void CreateList_Head(int n, ElemType *A);
      //表尾插入法动态生成链表
      void CreateList_Tail(int n, ElemType *A);
      //遍历链表
      bool ListTraverse() const;
};
//拷贝构造函数
template<class ElemType>
CirLinkList<ElemType>::CirLinkList(CirLinkList<ElemType> &List){
    LinkNode<ElemType> *copyhead=List.head->next;
    head=new LinkNode<ElemType>;
    head->data=List.head->data;
    LinkNode<ElemType> *thishead=head;
    while(copyhead != List.head){
        LinkNode<ElemType> *p=new LinkNode<ElemType>;
        p->data=copyhead->data;
        thishead->next=p;
        copyhead=copyhead->next;
        thishead=thishead->next;
    }
    tail=copyhead;
    tail->next=head;
}



//清空链表
template<class ElemType>
void CirLinkList<ElemType>::ListClear(){
    this->ListDestroy();
    head = new LinkNode<ElemType>;
    tail = head;
    head->next = head;
}

//销毁链表
template<class ElemType>
void CirLinkList<ElemType>::ListDestroy(){
    LinkNode<ElemType> *deleteone;
    while(tail!=tail->next){
        deleteone=tail->next;
        tail->next=deleteone->next;
        delete deleteone;
    }
    delete tail;
    head=0;
}

//返回链表的长度
template<class ElemType>
int CirLinkList<ElemType>::ListLength() const{
     int len=1;
     LinkNode<ElemType> *p=head->next;
     while (p != head){
        len++;
        p=p->next;
     }
     return len;
};



//判断链表是否为空表
template<class ElemType>
bool CirLinkList<ElemType>::ListEmpty() const{
    if (head ->data.code == 0) return 1;
    return 0;
};
//在链表的第pos个位置之后插入e元素
template<class ElemType>
bool CirLinkList<ElemType>::ListInsert_next(int pos,ElemType e){
    int k=1;
    LinkNode<ElemType> *thishead=head;
    LinkNode<ElemType> *newone;
    while (thishead!=tail && k!=pos){
        thishead=thishead->next;
        k++;
    }
    if (k==pos){
        newone=new LinkNode<ElemType>;
        newone->data=e;
        newone->next=thishead->next;
        thishead->next=newone;
        return 1;
    }
    else return 0;
}
//表头插入法动态生成链表
template<class ElemType>
void CirLinkList<ElemType>::CreateList_Head(int n, ElemType *A){
    LinkNode<ElemType> *thishead = head;
    head->data=A[0];
    for (int i=1;i<n;i++){
        thishead=new LinkNode<ElemType>;
        thishead->data=A[i];
        thishead->next=head;
        tail->next=thishead;
        head=thishead;
    }
}
//表尾插入法动态生成链表
template<class ElemType>
void CirLinkList<ElemType>::CreateList_Tail(int n, ElemType *A){
    LinkNode<ElemType> *thishead = head;
    head->data=A[0];
    for (int i=1;i<n;i++){
        thishead=new LinkNode<ElemType>;
        thishead->data=A[i];
        tail->next=thishead;
        tail=thishead;
    }
    tail->next=head;
}
//遍历链表
template<class ElemType>
bool CirLinkList<ElemType>::ListTraverse() const{
    LinkNode<ElemType> *p;
    p = head->next;
    if (head->data.code!=0)
        cout<< head->data.number <<' '<<head->data.code<<endl;;
    while( p != head )
    {
        cout<<p->data.number<<" "<<p->data.code<<endl;
        p = p->next;
    }  // while
    cout<<endl;
    return true;
}
template<class ElemType>
void creat(CirLinkList<ElemType> &a){
    int n;
    ElemType listin[1010];
    cin>>n;
    for (int i=0;i<n;i++){
        cin>>listin[i].code;
        listin[i].number=i+1;
    }
    a.CreateList_Tail(n,listin);
}
void Merge_Cur_Linklist( CirLinkList<ElemType> &A, CirLinkList<ElemType> &B ){
    LinkNode<ElemType> *taila,*tailb,*give;
    tailb=B.GetTail();
    taila=A.GetTail();
    if (A.ListEmpty()){

    }
    while (tailb != tailb->next){
        give=tailb->next;
        tailb->next=give->next;
        taila->next=give;
        taila=give;
    }
    taila->next=tailb;
    taila=tailb;
    taila->next=A.GetHead();
    A.SetTail(taila);
    give=new LinkNode<ElemType>;
    give->next=give;
    B.SetHead(give);
    B.SetTail(give);

}
template<class ElemType>
void Joseph(CirLinkList<ElemType> &A, int m){
    LinkNode<ElemType> *head=A.GetHead(),*last=A.GetTail();
    int movenum=m;
    while (A.ListLength()>1){
        while (--movenum){
            last=head;
            head=head->next;
        }
        cout<<head->data.number<<"->";
        movenum=head->data.code;
        last->next=head->next;
        delete head;
        head=last->next;
        A.SetHead(head);
        A.SetTail(last);
    }
    cout<<head->data.number<<endl;
    A.ListClear();
}
int main(){
    CirLinkList<ElemType> a,b,c;
    creat(a);
    a.ListTraverse();
    int renshu;
    cin>>renshu;
    Joseph(a,renshu);
    return 0;
}