C++ 手动实现单向循环链表（课后作业版）

单向循环链表，并实现增删查改等功能

首先定义节点类，类成员包含当前节点的值，指向下一个节点的指针

循环链表的尾节点指向头节点

节点定义：

//node definition

template <typename T>

class Node {

public:

    T value;

    Node<T>* next;

    Node() {}

    Node(const T& value) {

        this->value = value;

        next = nullptr;

    }

    Node(const T& value, const Node<T>& next) {

        this->value = value;

        this->next = next;

    }

};

然后是链表类的定义，主要包含了增删查改等功能

//LinkList_cycle definition

template <typename T>

class LinkList_cycle {

public:

    Node<T>* headnode;

    LinkList_cycle();

    LinkList_cycle(const T* arr, int len);  //array initial

    LinkList_cycle(const LinkList_cycle<T>& link);

    ~LinkList_cycle();

    LinkList_cycle<T>& push_back(T n);

    LinkList_cycle<T>& push_front(T n);

    LinkList_cycle<T>& insert(int pos, int n, T* arr);

    LinkList_cycle<T>& pop_front();

    LinkList_cycle<T>& pop_back();

    LinkList_cycle<T>& remove(int pos, int num);

    LinkList_cycle<T>& reverse();

    T& operator[](int n);

    T& at(int n);

    LinkList_cycle<T>& replace(int pos, int n, T* arr);

    int getLen() {return len;}

    void clear() {this->~LinkList_cycle();}

    void display();

private:

    int len = 0;

    Node<T>* getNode(int n);

};

各个函数解释：

LinkList_cycle(); 默认构造函数

LinkList_cycle(const T* arr, int len); 一般构造函数

LinkList_cycle(const LinkList_cycle<T>& link) 拷贝构造函数

~LinkList_cycle(); 析构函数

LinkList_cycle<T>& push_back(T n); 在尾部添加一个元素

LinkList_cycle<T>& push_front(T n); 在头部添加一个元素

LinkList_cycle<T>& insert(int pos, int n, T* arr); 在pos处插入n个元素

LinkList_cycle<T>& pop_front(); 删除第一个节点

LinkList_cycle<T>& pop_back(); 删除最后一个节点

LinkList_cycle<T>& remove(int pos, int num); 删除pos开始的num个元素

LinkList_cycle<T>& reverse(); 反转链表

T& operator[](int n); 重载[ ]运算符，返回第n个节点的值

T& at(int n); 与[ ]一样，只不过会检查索引是否越界

LinkList_cycle<T>& replace(int pos, int n, T* arr); 替换n个节点

int getLen() {return len;} 返回长度，因为len是private

void clear() {this->~LinkList_cycle();} 清除链表

void display(); 显示链表所有元素

Node<T>* getNode(int n); 返回第n个节点的指针，是private函数，在其他函数中经常用到

完整代码：

#include <iostream>

using namespace std;

//node definition

template <typename T>

class Node {

public:

    T value;

    Node<T>* next;

    Node() {}

    Node(const T& value) {

        this->value = value;

        next = nullptr;

    }

    Node(const T& value, const Node<T>& next) {

        this->value = value;

        this->next = next;

    }

};

//LinkList_cycle definition

template <typename T>

class LinkList_cycle {

public:

    Node<T>* headnode;

    LinkList_cycle();

    LinkList_cycle(const T* arr, int len);  //array initial

    LinkList_cycle(const LinkList_cycle<T>& link);

    ~LinkList_cycle();

    LinkList_cycle<T>& push_back(T n);

    LinkList_cycle<T>& push_front(T n);

    LinkList_cycle<T>& insert(int pos, int n, T* arr);

    LinkList_cycle<T>& pop_front();

    LinkList_cycle<T>& pop_back();

    LinkList_cycle<T>& remove(int pos, int num);

    LinkList_cycle<T>& reverse();

    T& operator[](int n);

    T& at(int n);

    LinkList_cycle<T>& replace(int pos, int n, T* arr);

    int getLen() {return len;}

    void clear() {this->~LinkList_cycle();}

    void display();

private:

    int len = 0;

    Node<T>* getNode(int n);

};

//default constructor

template <typename T>

LinkList_cycle<T>::LinkList_cycle() {

    headnode = nullptr;

    len = 0;

}

//normal constructor

template <typename T>

LinkList_cycle<T>::LinkList_cycle(const T* arr, int len) {

    Node<T>* temp = nullptr;

    Node<T>* node = nullptr;

    if ( len < 0 ) {

        cout << "[error]: illegal length of LinkList_cycle" << endl;

        exit(0);

    }

    node = new Node<T>(arr[0]);

    headnode = node;

    temp = node;

    for ( int i = 1; i < len; i++ ) {

        node = nullptr;

        node = new Node<T> (arr[i]);

        temp->next = node;

        temp = temp->next;

    }

    temp->next = headnode;;

    this->len = len;

}

//copy constructor

template <typename T>

LinkList_cycle<T>::LinkList_cycle(const LinkList_cycle<T>& link) {

    this->len = link.getLen();

    this->headnode = link.headnode;

}

//deconstructor

template <typename T>

LinkList_cycle<T>::~LinkList_cycle() {

    if ( headnode == nullptr || len == 0 ) {

        headnode = nullptr;

        len = 0;

        return;

    }

    this->len = 0;

    Node<T>* temp1 = headnode;

    Node<T>* temp2 = headnode;  //保存headnode

    while ( headnode != nullptr ) {

        temp1 = headnode;

        headnode = headnode->next;

        delete temp1;

        if ( headnode == temp2 ) //如果next指向headnode了，说明当前的temp1就是最后一个节点了

            break;

        temp1 = nullptr;

    }

    headnode = nullptr;

}

//display all elements in LinkList_cycle<T>

template <typename T>

void LinkList_cycle<T>::display() {

    if ( this->len == 0 ) {

        cout << "[warning]: can not display empty linkedlist" << endl;

        return;

    }

    Node<T> *node = headnode;

    for ( int i = 0; i < len; i++ ) {

        cout << node->value << " ";

        node = node->next;

    }

    if ( node != headnode ) {

        cout << "[error]: the last node->next do not point to headnode, check again" << endl;

    }

    node = nullptr;

    cout << endl;

}

//add one node at the last position

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::push_back(T n) {

    Node<T> *node = this->getNode(len-1); //获取指向第len-1个node的指针，即len-2节点的next，所以node就是指向最后节点的指针

    if ( node->next == headnode ) {   //再加一层保护

        Node<T> *temp = new Node<T>(n);  //创建新node

        node->next = temp;           //将最后一个节点的next指向新node

        temp->next = headnode;       //将新node->next指向headnode

        this->len++;

    }

    return *this;

}

//add one node at the first position

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::push_front(T n) {

    Node<T>* node_new = new Node<T>(n);   //新节点

    Node<T> *node_end = this->getNode(len-1);   //最后节点

    node_new->next = headnode;            //新节点的next指向第一个节点

    node_end->next = node_new;            //最后节点的next指向新节点

    headnode = node_new;                  //再让headnode指向新节点

    this->len++;

    return *this;

}

//insert elements to LinkList_cycle

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::insert(int pos, int n, T* arr) {

    if ( pos > len-1 || len < 0 ) {

        cout << "[error]: illegal insert position, please check again" << endl;

        exit(0);

    }

    Node<T>* node_N = getNode(len-1); //前半部分

    Node<T>* temp = node_N->next;    //后半部分

    Node<T>* node_new = nullptr;     //新增加的

    for ( int i = 0; i < n; i++ ) {

        node_new = new Node<T> (arr[n-1-i]);

        node_new->next = temp;

        temp = node_new;

        node_new = nullptr;

    }

    node_N->next = temp;

    if ( pos == 0)    //唯有再0处插入的时候，需要改变头节点，其实对pos=0,一直push_front也行

        headnode = temp;

    this->len += n;

    return *this;

}

//delete the first element

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::pop_front() {

    if ( this->len == 0 ) {

        cout << "[error]: LinkList_cycle don't has any element" << endl;

        exit(0);

    }

    Node<T>* temp = headnode;  //先复制一份headnode

    headnode = headnode->next;  //headnode 前进一步

    delete temp;             //把第一个节点释放掉

    this->len--;

    temp = getNode(len-1);   //获取最后一个节点

    temp->next = headnode;   //把最后一个节点的next指向新的headnode

    return *this;

}

//delete the last element

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::pop_back() {

    if ( this->len == 0 ) {

        cout << "[error]: LinkList_cycle don't has any element" << endl;

        exit(0);

    }

    Node<T>* temp1 = getNode(len-2);

    Node<T>* temp2 = temp1->next;

    delete temp2;

    temp1->next = headnode;

    this->len--;

    return *this;

}

//get the last node pointer

template <typename T>

Node<T>* LinkList_cycle<T>::getNode(int n) {

    if ( n > len-1 || n < 0) {

        cout << "[warning]: index out of range" <<endl;

    }

    n = n%len;

    if ( n < 0 )

        n = n + len;

    Node<T> *node = headnode;

    for( int i = 0; i < n; i++ ) {

        node = node->next;

    }

    return node;

}

//remove n elements

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::remove(int pos, int num) {

    if ( pos > len-1 || len < 0 ) {

        cout << "[error]: illegal remove position, please check again" << endl;

        exit(0);

    } else if ( pos + num > len) {

        cout << "[error]: remove index out of range" << endl;

        exit(0);

    }

    Node<T>* node_N = getNode(pos-1);

    Node<T>* node_N_num = getNode(pos+num);

    Node<T>* temp = getNode(pos);

    while ( 1 ) {

        Node<T>* node = temp;

        temp = temp->next;

        if ( temp == node_N_num ) {

            break;

        }

        delete node;

    }

    if ( pos == 0 ) {   //如果从0位置开始删除，要修改头节点

        headnode = node_N_num;

        node_N->next = headnode;

    }

    node_N->next = node_N_num;

    this->len -= num;

    return *this;

}

//reverse LinkList_cycle

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::reverse() {

    const int num = len;

    T arr[num];

    Node<T>* temp = headnode;

    for ( int i = 0; i < this->len; i++ ) {

        arr[i] = temp->value;

        temp = temp->next;

    }

    temp = headnode;

    for ( int i = 0; i < this->len; i++ ) {

        temp->value = arr[len-i-1];

        temp = temp->next;

    }

    return *this;

}

template <typename T>

T& LinkList_cycle<T>::operator[](int n) {

    return this->getNode(n)->value;

}

template <typename T>

LinkList_cycle<T>& LinkList_cycle<T>::replace(int pos, int n, T* arr) {

    if ( pos > len-1 || len < 0 ) {

        cout << "[error]: illegal remove position, please check again" << endl;

        exit(0);

    } else if ( pos + n > len) {

        cout << "[error]: remove index out of range" << endl;

        exit(0);

    }

    Node<T>* temp = nullptr;

    if ( pos == 0 )

        temp = headnode;

    else

        temp = this->getNode(pos);

    for ( int i = 0; i < n; i++ ) {

        temp->value = arr[i];

        temp = temp->next;

    }

    return *this;

}

int main(){

    int arr[]{1,2,4,5,0};

    LinkList_cycle<int> link(arr, sizeof(arr)/sizeof(int));

    cout << "LinkLint init with arr: " <<endl;

    link.display();

    cout << "push_back:" << endl;

    link.push_back(34);

    link.display();

    cout << "push_front:" << endl;

    link.push_front(10);

    link.display();

    cout << "insert:" << endl;

    link.insert(0,4,arr);

    link.display();

    cout << "pop_front:" << endl;

    link.pop_front();

    link.display();

    cout << "pop_back:" << endl;

    link.pop_back();

    link.display();

    cout << "remove:" << endl;

    link.remove(0,3);

    link.display();

    cout << "[] operator:" << endl;

    cout << link[2] << endl;

    cout << "replace:" << endl;

    int a[] = {6,5,2};

    link.replace(0, sizeof(a)/sizeof(int), a);

    link.display();

    cout << "LinkList_cycle reserve:" << endl;

    link.reverse();

    link.display();

    cout << "clear:" << endl;

    link.clear();

    cout << "len=" << link.getLen() << endl;

    link.display();

}

C++ 手动实现单向循环链表（课后作业版）

C++ 手动实现单向循环链表（课后 作业版）的相关教程结束。

相关推荐

一种flink 作业提交失败的情况描述与原因排查

【算法训练营day4】LeetCode24. 两两交换链表中的结点 LeetCode19. 删除链表的倒数第N个结点 LeetCode面试题 02.07. 链表相交 LeetCode142. 环形链表II

使用C语言实现简单的通用的链表

OO第一次博客作业总结反思

2021-09-17：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？

《DL/T 976-2017 带电作业用工具、装置和设备预防性试验规程》中的样品名称及试验项目

2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。

LeeCode链表问题（一）