数据结构——循环链表模板类

迈不过友情╰ 2022-06-06 22:17 192阅读 0赞

**数据结构相关笔记整理（1.2）**  
最近数据结构进展缓慢，每个结构的代码少说都得200行，但是依旧喜欢成功运行时的成就感！这次主要整理了循环链表的模板class，新手上路难免有不当和瑕疵之处，希望群众们及时指出。下面贴出代码：  
class及其函数定义：

//循环链表模板class
    #include <iostream>
    using namespace std;
    
    template<class T>
    struct CircleLinkNode {
        T data;
        CircleLinkNode<T> *link;
        //构造函数
        CircleLinkNode(CircleLinkNode<T> * next = NULL) : link(next) {}
        CircleLinkNode(T d, CircleLinkNode<T> * next = NULL) : data(d), link(next) {}
    };
    
    template<class T>
    class CircleList {
    public:
        CircleList(const T & x);                        //构造函数
        CircleList(CircleList<T> & L);                  //复制构造函数
        ~CircleList();                                 //析构函数
        int Length() const;                             //计算循环链表的长度
        bool IsEmpty()
        {
            return first->link == first ? true : false; //判断是否是空表
        }
        CircleLinkNode<T> * getHead() const;            //返回附加头节点的地址
        void setHead(CircleLinkNode<T> * p);            //设置附加头节点的地址
        CircleLinkNode<T> * Search(T x);                //搜索含数据x的节点
        CircleLinkNode<T> * Locate(int i);              //搜索第i个元素的地址
        T getData(int i);                               //取出第i个元素的值
        void setData(int i, T & x);                     //用修改第i个元素的值
        bool Insert(int i, T & x);                      //在第i个元素后插入x
        bool Remove(int i, T & x);                      //删除第i个元素，用x保存删除的数据
        void createList(T endFlag);                     //创建单链表
        void outputList(int stopSequence);
    protected:
        CircleLinkNode<T> *first, *last;                //头指针、尾指针
    };
    
    //函数定义
    template<class T>
    CircleList<T>::CircleList(const T & x) {
        //构造函数: 开辟头节点并赋值
        first = new CircleLinkNode<T>(x);
        first->link = first;
    }
    
    template<class T>
    CircleList<T>::~CircleList() {
        //释放相应的资源
        delete first;
        delete last;
    }
    
    template<class T>
    CircleLinkNode<T> * CircleList<T>::getHead() const {
        //得到函数的头指针
        return first;
    }
    
    template<class T>
    int CircleList<T>::Length() const {
        //计算链表的长度
        CircleLinkNode<T> *calculLen = NULL;
        int Len = 0;
        calculLen = first->link;
        while (calculLen != first) {                    //当再一次循环到first时，返回计数长度
            Len++;
            calculLen = calculLen->link;
        }
        return Len;
    }
    
    template<class T>
    CircleList<T>::CircleList(CircleList<T> &L) {
        //复制构造函数
        int Len = Length();                             //得到当前链表的长度
        CircleLinkNode<T> *create = NULL, *destData, *srcData;
        create = new CircleLinkNode<T>(0);
        if (!create) {
            cerr << "内存分配错误" << endl;
            exit(1);
        }
        last = create;                                  //标记尾节点
        for (int i = 0; i < Len - 1; i ++) {
            create->link = first->link;
            first->link = create;
            create = new CircleLinkNode<T>(0);
            if (!create) {
                cerr << "内存分配错误" << endl;
                exit(1);
            }
        }
        //将L中的data域逐一copy到当前链表中
        copyData = first->link;
        srcData = L.first->link;
        while (srcData == L.first) {
            destData->data = srcData->data;
            destData = destData->link;
            srcData = srcData->link;
        }
        //构建循环链表
        last->link = first;
    }
    
    template<class T>
    CircleLinkNode<T> * CircleList<T>::Search(T x) {
        //查找数据域为x的节点并返回其地址
        CircleLinkNode<T> * current = NULL;
        current = first->link;
        while (current != first) {
            if (current->data == x) {
                break;
            }
            current = current->link;
        }
        return current;
    }
    
    template<class T>
    CircleLinkNode<T> * CircleList<T>::Locate(int i) {
        //定位函数， 返回第i个节点的地址，可供插入与删除函数用
        while (i <= 0 || i > Length()) {
            cout << "数据不合法，请重新输入" << endl;
            cin >> i;
        }
        CircleLinkNode<T> * current = NULL;
        current = first->link;
        for (int j = 1; j < i; j ++) {
            current = current->link;
        }
        return current;
    }
    
    template<class T>
    void CircleList<T>::createList(T endFlag) {
        //逆序创建单链表
        T inputData = 0;
        CircleLinkNode<T> *create = NULL;
        cin >> inputData;
        create = new CircleLinkNode<T>(inputData);      //在循环外侧创建尾节点
        if (!create) {
            cerr << "内存分配错误" << endl;
            exit(1);
        }
        last = create;                                  //标记尾节点
        while (inputData != endFlag) {                  //是否满足结束条件
            create->link = first->link;                 //建立链接
            first->link = create;
            cin >> inputData;
            create = new CircleLinkNode<T>(inputData);  //依次建立其他节点
            if (!create) {
                cerr << "内存分配错误" << endl;
                exit(1);
            }
        }
        //单链表建立完成
        last->link = first;                             //构建循环链表
    }
    
    template<class T>
    T CircleList<T>::getData(int i) {
        CircleLinkNode<T> * current;
        current = Locate(i);                            //定位函数调用
        return current->data;
    }
    
    template<class T>
    void CircleList<T>::setData(int i, T & x) {
        //设置第i个节点的数据域为x
        CircleLinkNode<T> * current = NULL;
        current = Locate(i);
        current->data = x;                              //完成修改
    }
    
    template<class T>
    bool CircleList<T>::Insert(int i, T & x) {
        //在第i个节点后插入新的节点，并使其数据域赋值为x
        CircleLinkNode<T> * flagPtr;
        CircleLinkNode<T> * newNode = new CircleLinkNode<T>(x);
        if (!newNode) {                                 //内存分配错误
            return false;
        }
        if (0 == i) {                                   //插入在首位置
            newNode->link = first->link;
            first->link = newNode;
        }
        else {
            flagPtr = Locate(i);
            newNode->link = flagPtr->link;
            flagPtr->link = newNode;
        }
        return true;
    }
    
    template<class T>
    bool CircleList<T>::Remove(int i, T & x) {
        //删除第i个节点并将删除的数据存储在x当中
        CircleLinkNode<T> *preNode = NULL, *delNode = NULL;
        preNode = Locate(i - 1);
        delNode = Locate(i);
        preNode->link = delNode->link;
        delete delNode;
        return true;
    }
    
    template<class T>
    void CircleList<T>::outputList(int stopSequence) {
        if (first == first->link) {
            cout << "此为空表" << endl;
            return;
        }
        //输出循环链表,直到指定序号停止输出(方便测试循环特性)
        CircleLinkNode<T> * current = NULL;
        current = first->link;
        for (int i = 0; i < stopSequence; i ++) {
            cout << current->data << " ";
            current = current->link;
            if (current == first) {
                current = current->link;                //跳过first的输出
            }
        }
        cout << endl;
    }

下面是主函数测试部分：

int main()
    {
        //int modifValue = 100;
        //CircleList<int> circle1(0);
        //circle1.createList(0);
        //cout << circle1.getData(2) << endl;               //读取数据测试（这里指定是5）
        //circle1.setData(3, modifValue);                   //修改数据测试（这里指定是3）
        //cout << circle1.getData(3) << endl;
        //circle1.outputList(circle1.Length());
    
        //CircleList<int> circle2(0);                       //循环输出测试
        //circle2.createList(0);
        //circle2.outputList(10);
    
        int InseValue = 100, delValue = 0;
        CircleList<int> circle3(0);                         //插入与删除节点测试
        circle3.createList(0);
        circle3.outputList(circle3.Length());
        circle3.Insert(3, InseValue);                       //数据插入操作
        circle3.outputList(2 * circle3.Length());           //循环两遍输出
        circle3.Remove(3, delValue);
        circle3.outputList(2 * circle3.Length());
    
        system("pause");
        return 0;
    }

运行的部分结果：![这里写图片描述][SouthEast]最后也希望大家能够多加练习，更重要的是多做相关的练习，相信最终能熟练掌握的！

[SouthEast]: /images/20220607/bd065148b6a14bbd93da42e20ddd1abb.png