数据结构作业二 List ADT

问题分析

题目要求自行实现list ADT，并在此基础上实现PrintLots函数并且实现懒惰删除功能。对于PrintLots函数，题目要求分析运行时间；对于懒惰删除功能，除编写实现外，题目还要求列出懒惰删除的优点和缺点。

PrintLots(L,P)：有两个链表L和P, 他们包含以升序排列的整数，操作PrintLots(L,P)将打印L中那些由P所指定位置上的元素。

懒惰删除（lazy deletion）：为了删除一个元素，我们只标记上该元素被删除。表中被删除和非被删除元素的个数作为数据结构的一部分被保留。如果被删除元素和非被删除元素一样多，我们遍历整个表，对所有被标记的节点执行标准的删除算法。

解决方案

设计list ADT，准备好PrintLots函数所需要的接口。主文件引用自己编写的list ADT，并在主文件中完成对PrintLots函数的实现，懒惰删除则可以直接封装在ADT中。由于本次实验缺乏示例输入输出，因此还要对输入输出部分稍微加以设计，在此不多赘述。

算法设计

list ADT的实现大体可以按照课本所给的框架来初步构建，之后对其进行丰富，首先实现节点类，再进一步实现List类。考虑到懒惰删除的需要，在实现节点类的时候我在其中加入了是否删除的标志，实现List类时增加了用于统计伪删除元素个数的变量。为了更进一步贴合标准模板库的操作，相对多此一举地加入了迭代器子类。（实践证明，我对迭代器相关知识的了解并不充分…😕）

PrintLots函数

因为两个链表的元素都是升序排列的，所以L的迭代器可以一直向一个方向移动，整个函数的实现降低了一些难度。定义一个整形变量用来记录当前L的迭代器指向位置的编号，编号若与P的迭代器指向的元素相同则进行输出，同时两个迭代器向后移动。若编号与P当前元素不同，则指向L的迭代器向后移动。函数的终止条件为链表P遍历结束。

复杂度分析

从整体上来看，PrintLots函数只是两个链表的单向遍历输出，只是细节方面稍微复杂，但引入的均为常数时间可以完成的操作。因为P的元素个数不可能超过L的元素个数，所以最坏情况便是输出了L的所有元素。时间复杂度为O(n)。

懒惰删除

函数参数为指向要删除元素的迭代器，函数通过迭代器访问该元素内部的删除标志，并对其进行修改。修改之后检查当前伪删除元素的总数，大于总元素一般对整个链表进行遍历删除。总体实现相对简单。

懒惰删除优缺点分析

优点：误删数据有恢复的空间，未被释放的空间可以进行二次利用，减少了资源消耗较大的删除过程的需求次数（链表中体现不明显）。 缺点：记录元素伪删除需要额外的操作和空间，被删除的节点不及时释放增加了空间的占用，也提高了部分操作所需的时间。

流程图

编程实现

共编写了三个文件：listnode.h、my_list.h、main.cpp

1.listnode.h

    #include<iostream>
    using namespace std;

    //定义列表的节点
    template <typename T> struct ListNode
    {
        T data;
        ListNode<T>* pred;
        ListNode<T>* succ;
        bool need_remove;   //need_remove为了方便懒惰消除

        ListNode() : need_remove(false) {}
        ListNode(T e, ListNode<T>* p = NULL, ListNode<T>* s = NULL)
            : data(e), pred(p), succ(s), need_remove(false) {}

        ListNode<T>* insertAsPred(T const& e);
        ListNode<T>* insertAsSucc(T const& e);
    };

    //前插入
    template <typename T>
    ListNode<T>* ListNode<T>::insertAsPred(T const& e){
        ListNode<T>* x = new ListNode(e, pred, this);
        pred->succ = x;
        pred = x;
        return x;
    }

    //后插入
    template <typename T>
    ListNode<T>* ListNode<T>::insertAsSucc(T const& e){
        ListNode<T>* x = new ListNode(e, this, succ);
        succ->pred = x;
        succ = x;
        return x;
    }

2.my_list.h

#include "listnode.h"

template <typename T>
class List
{
  private:
    int _size;
    int _num;
    ListNode<T> *header;
    ListNode<T> *trailer;

  protected:
    void init();
    void copyNodes(ListNode<T> *, int);
    //只写出了有可能用到的函数

  public:
    List() { init(); } //默认构造
    List(List<T> const &L);
    List(List<T> const &L, int r, int n);
    List(ListNode<T> *p, int n);
    int clear();

    ~List(); //析构

    class Iterator{
      public:
        ListNode<T> *ptr;

        Iterator() : ptr(NULL) {}
        Iterator(ListNode<T> *tmp) : ptr(tmp) {}

        T operator*(){
            return ptr->data;
            //为空时如何抛出错误？
        }

        bool operator==(Iterator const &x) { return ptr == x.ptr; }
        bool operator!=(Iterator const &x) { return ptr != x.ptr; }
        Iterator operator++(int){
            //不能在这里访问trailer，那么标准的迭代器是怎么操作的呢
            Iterator tmp(ptr);
            while(1){
                if(ptr->succ != NULL)
                    ptr = ptr->succ;
                if(!ptr->need_remove)   //不需要继续访问，跳出循环
                    break;
            }
            return tmp;
        }
        Iterator operator--(int){
            Iterator tmp(ptr);
            while(1){
                if (ptr->pred != NULL)
                    ptr = ptr->pred;
                if(!ptr->need_remove)
                    break;
            }
            return tmp;
        }
        Iterator& operator++(){
            while(1){
                if(ptr->succ != NULL)
                    ptr = ptr->succ;
                if(!ptr->need_remove)   //不需要继续访问，跳出循环
                    break;
            }
            return *this;
        }
        Iterator& operator--(){
            while(1){
                if (ptr->pred != NULL)
                    ptr = ptr->pred;
                if(!ptr->need_remove)
                    break;
            }
            return *this;
        }
    };

    bool empty() const { return _size <= 0; }
    int size() const { return _size-_num; }
    ListNode<T> *insertAsFirst(T const &e);
    ListNode<T> *insertAsLast(T const &e);
    Iterator begin() { return ++Iterator(header); }
    Iterator end() { return Iterator(trailer); }
    ListNode<T> *first() const { return header->succ; } //first和begin完全没必要
    ListNode<T> *last() const { return trailer->pred; }
    T remove(ListNode<T> *p);
    void lazy_deletion(Iterator i);
    void show();
    void Advance(Iterator &i, int n);
};

template <typename T> //列表初始化
void List<T>::init()
{
    header = new ListNode<T>;
    trailer = new ListNode<T>;
    header->succ = trailer;
    header->pred = NULL;
    trailer->pred = header;
    trailer->succ = NULL;
    _size = 0;
    _num = 0;
}

//复制自p开始的n项
template <typename T>
void List<T>::copyNodes(ListNode<T> *p, int n)
{
    init();
    while (n--)
    {
        insertASLast(p->data);
        p = p->succ;
    }
}

//Clear()
template <typename T>
int List<T>::clear()
{
    int num = _size;
    if (_size)
    {
        ListNode<T> *p = header->succ;
        ListNode<T> *tmp;
        while (p != trailer)
        {
            tmp = p->succ;
            delete p;
            p = tmp;
        }
    }
    _size = 0;
    _num = 0;
    return num;
}

//构造函数
template <typename T>
List<T>::List(List<T> const &L) { copyNodes(L.first(), L.size()); }

template <typename T>
List<T>::List(List<T> const &L, int r, int n)
{
    ListNode<T> *tmp = L.first();
    while (--r)
        tmp = tmp->succ;
    copyNodes(tmp, n);
}

template <typename T>
List<T>::List(ListNode<T> *p, int n) { copyNodes(p, n); }

//析构函数
template <typename T>
List<T>::~List()
{
    clear();
    delete trailer;
    delete header;
}

template <typename T>
ListNode<T> *List<T>::insertAsFirst(T const &e)
{
    _size++;
    return header->insertAsSucc(e);
}

template <typename T>
ListNode<T> *List<T>::insertAsLast(T const &e)
{
    _size++;
    return trailer->insertAsPred(e);
}

//删除
template <typename T>
T List<T>::remove(ListNode<T> *p)
{
    T tmp= p->data;
    _size--;
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    return tmp;
}

template <typename T>
void List<T>::lazy_deletion(Iterator i){
    _num++;
    ListNode<T>* tmp = i.ptr;
    tmp->need_remove = true;

    //数量大于一半开始全部删除
    if(_num >= _size/2){
        _num = 0;
        ListNode<T> *p = header->succ;
        while(trailer != p){
            if(!p->need_remove){
                p = p->succ;
                continue;
            }
                
            tmp = p->succ;
            remove(p);
            p = tmp;       
        }
    }
    return ;
}

//输出格式化
template <typename T>
void List<T>::show(){
    if(_size == 0){
        cout << "None" << endl;
        return ;
    }
    ListNode<T>* p = header;
    while(trailer != (p = p->succ)){
        if(p == header->succ){
            cout << p->data;
            continue;
        }
        if(p->pred->need_remove && p->need_remove)    cout << "____";
        else if(p->need_remove)     cout << "--__";
        else if(p->pred->need_remove)   cout << "__->";
        else    cout << "--->";
        cout << p->data;
    }
    return ;
}

//用于迭代器的移动
template <typename T>
void List<T>::Advance(Iterator & i, int n){
    if(n >= 0){
        while(n--)
            i.ptr = i.ptr->succ;
    }
    else{
        while(n++)
            i.ptr = i.ptr->pred;
    }
}
//如果向容器里面放个pair？

3.main.cpp

#include "my_list.h"


void PrintLots(List<int>& L, List<int>& P){
    int current = 1;

    //是否存在空序列
    if(L.empty() || P.empty())  {   cout<<"Error, input is empty"<<endl; return ;}

    List<int>::Iterator l = L.begin();
    List<int>::Iterator p = P.begin();
    while(1){
        if(L.size() < *p){  
            cout << endl << "Error, the number of P is bigger than the size of L" << endl;  
            break;
        }

        if(current++ == *p){
            cout << *l << " ";
            p++;
        }

        //输出结束
        if(p == P.end()){  
                cout << endl << "Finished!" << endl;
                break;
        }
        l++;
    }
    return ;
}

int main(){
    int m, n, tmp, last;
    int select = 0;
    while(1){
        cout << "Choose function(0 means lazy_deletion, 1 means PrintLots):";
        cin >> select;
        if(select){
            List<int> L, P;
            cout << "Input the size of L and P: ";
            cin >> m >> n;
            cout << "Input the elements of L: " << endl;
            while (m--){
                cin >> tmp;
                L.insertAsLast(tmp);
            }
            cout << "Input the elements of P: " << endl;
            while (n--){
                cin >> tmp;
                P.insertAsLast(tmp);
            }
            PrintLots(L, P);
        }
        else{
            List<int> L;
            cout << "Input the size of L: ";
            cin >> m;
            cout << "Input the elements of L:" << endl;
            for(int j = 0; j < m; j++){
                cin >> tmp;
                L.insertAsLast(tmp);
            }
            cout << "L is: ";
            L.show();
            cout<<endl;


            List<int>::Iterator i = L.begin();
            last = 1;
            cout << "How many elements do you want to delete? ";
            cin >> n;
            cout << "Input them(from 1 to " << m << ")" << endl;
            while(n--){
                cin >> tmp;
                L.Advance(i, tmp-last);
                last = tmp;
                L.lazy_deletion(i);
            }
            cout << "Now L is: ";
            L.show();
            cout << endl;
        } 
    }
}

结果分析

PrintLots进行了四组测试，从测试结果可以看出对错误情况进行了有效的判断，并且能够处理一般情况。

为了方便懒惰删除的查看，设置了一个函数用来表现链表当前的情况，同时进行了三种样例的测试，能够代表所有类型的满足要求的输入情况。可以很容易的看出当删除元素过半时按要求完成了操作。

总结体会

1. 深刻感觉到自己的宏观思维有极大的欠缺，自己设计出的类中的函数不能很好地衔接，编程思维有问题。
2. 自己写的迭代器可能称不上是迭代器，只是稍微包装了一下指针。自己测试的时候发现在iterator已经被定义，意识到平时所用的迭代器并不是定义在容器的头文件中。
3. 边界等特殊情况没有得到很好的处理，不过能够保证在输入规范的情况下得到良好的结果，代码总体有待完善。（总之还是对标准模板库特殊情况处理方式不够了解📌
4. 很多用不到的东西也进行了实现，导致代码量相对较大😓