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

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

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

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

    节点定义：

    1. //node definition
    2. template <typename T>
    3. class Node {
    4. public:
    5.     T value;
    6.     Node* next;
    7.  
    8.     Node() {}
    9.     Node(const T& value) {
    10.         this->value = value;
    11.         next = nullptr;
    12.     }
    13.     Node(const T& value, const Node& next) {
    14.         this->value = value;
    15.         this->next = next;
    16.     }
    17. };

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

    1. //LinkList_cycle definition
    2. template <typename T>
    3. class LinkList_cycle {
    4. public:
    5.     Node* headnode;
    6.  
    7.     LinkList_cycle();
    8.     LinkList_cycle(const T* arr, int len);  //array initial
    9.     LinkList_cycle(const LinkList_cycle& link);
    10.     ~LinkList_cycle();
    11.     LinkList_cycle& push_back(T n);
    12.     LinkList_cycle& push_front(T n);
    13.     LinkList_cycle& insert(int pos, int n, T* arr);
    14.     LinkList_cycle& pop_front();
    15.     LinkList_cycle& pop_back();
    16.     LinkList_cycle& remove(int pos, int num);
    17.     LinkList_cycle& reverse();
    18.     T& operator[](int n);
    19.     T& at(int n);
    20.     LinkList_cycle& replace(int pos, int n, T* arr);
    21.     int getLen() {return len;}
    22.     void clear() {this->~LinkList_cycle();}
    23.     void display();
    24. private:
    25.     int len = 0;
    26.     Node* getNode(int n);
    27.  
    28. };

    各个函数解释：

    LinkList_cycle();      默认构造函数

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

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

    ~LinkList_cycle();     析构函数

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

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

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

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

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

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

    LinkList_cycle& reverse();     反转链表

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

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

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

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

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

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

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

    完整代码：

    1. #include 
    2. using namespace std;
    3.  
    4. //node definition
    5. template <typename T>
    6. class Node {
    7. public:
    8.     T value;
    9.     Node* next;
    10.  
    11.     Node() {}
    12.     Node(const T& value) {
    13.         this->value = value;
    14.         next = nullptr;
    15.     }
    16.     Node(const T& value, const Node& next) {
    17.         this->value = value;
    18.         this->next = next;
    19.     }
    20. };
    21.  
    22. //LinkList_cycle definition
    23. template <typename T>
    24. class LinkList_cycle {
    25. public:
    26.     Node* headnode;
    27.  
    28.     LinkList_cycle();
    29.     LinkList_cycle(const T* arr, int len);  //array initial
    30.     LinkList_cycle(const LinkList_cycle& link);
    31.     ~LinkList_cycle();
    32.     LinkList_cycle& push_back(T n);
    33.     LinkList_cycle& push_front(T n);
    34.     LinkList_cycle& insert(int pos, int n, T* arr);
    35.     LinkList_cycle& pop_front();
    36.     LinkList_cycle& pop_back();
    37.     LinkList_cycle& remove(int pos, int num);
    38.     LinkList_cycle& reverse();
    39.     T& operator[](int n);
    40.     T& at(int n);
    41.     LinkList_cycle& replace(int pos, int n, T* arr);
    42.     int getLen() {return len;}
    43.     void clear() {this->~LinkList_cycle();}
    44.     void display();
    45. private:
    46.     int len = 0;
    47.     Node* getNode(int n);
    48.  
    49. };
    50.  
    51. //default constructor
    52. template <typename T>
    53. LinkList_cycle::LinkList_cycle() {
    54.     headnode = nullptr;
    55.     len = 0;
    56. }
    57.  
    58. //normal constructor
    59. template <typename T>
    60. LinkList_cycle::LinkList_cycle(const T* arr, int len) {
    61.     Node* temp = nullptr;
    62.     Node* node = nullptr;
    63.     if ( len < 0 ) {
    64.         cout << "[error]: illegal length of LinkList_cycle" << endl;
    65.         exit(0);
    66.     }
    67.     node = new Node(arr[0]);
    68.     headnode = node;
    69.     temp = node;
    70.     for ( int i = 1; i < len; i++ ) {
    71.         node = nullptr;
    72.         node = new Node (arr[i]);
    73.         temp->next = node;
    74.         temp = temp->next;
    75.     }
    76.     temp->next = headnode;;
    77.     this->len = len;
    78. }
    79.  
    80. //copy constructor
    81. template <typename T>
    82. LinkList_cycle::LinkList_cycle(const LinkList_cycle& link) {
    83.     this->len = link.getLen();
    84.     this->headnode = link.headnode;
    85. }
    86.  
    87. //deconstructor
    88. template <typename T>
    89. LinkList_cycle::~LinkList_cycle() {
    90.     if ( headnode == nullptr || len == 0 ) {
    91.         headnode = nullptr;
    92.         len = 0;
    93.         return;
    94.     }
    95.     this->len = 0;
    96.     Node* temp1 = headnode;
    97.     Node* temp2 = headnode;  //保存headnode
    98.     while ( headnode != nullptr ) {
    99.         temp1 = headnode;
    100.         headnode = headnode->next;
    101.         delete temp1;
    102.         if ( headnode == temp2 ) //如果next指向headnode了，说明当前的temp1就是最后一个节点了
    103.             break;
    104.         temp1 = nullptr;
    105.     }
    106.     headnode = nullptr;
    107. }
    108.  
    109. //display all elements in LinkList_cycle
    110. template <typename T>
    111. void LinkList_cycle::display() {
    112.     if ( this->len == 0 ) {
    113.         cout << "[warning]: can not display empty linkedlist" << endl;
    114.         return;
    115.     }
    116.     Node *node = headnode;
    117.     for ( int i = 0; i < len; i++ ) {
    118.         cout << node->value << " ";
    119.         node = node->next;
    120.     }
    121.     if ( node != headnode ) {
    122.         cout << "[error]: the last node->next do not point to headnode, check again" << endl;
    123.     }
    124.     node = nullptr;
    125.     cout << endl;
    126. }
    127.  
    128. //add one node at the last position
    129. template <typename T>
    130. LinkList_cycle& LinkList_cycle::push_back(T n) {
    131.     Node *node = this->getNode(len-1); //获取指向第len-1个node的指针，即len-2节点的next，所以node就是指向最后节点的指针
    132.  
    133.     if ( node->next == headnode ) {   //再加一层保护
    134.         Node *temp = new Node(n);  //创建新node
    135.         node->next = temp;           //将最后一个节点的next指向新node
    136.         temp->next = headnode;       //将新node->next指向headnode
    137.         this->len++;
    138.     }
    139.     return *this;
    140. }
    141.  
    142. //add one node at the first position
    143. template <typename T>
    144. LinkList_cycle& LinkList_cycle::push_front(T n) {
    145.     Node* node_new = new Node(n);   //新节点
    146.     Node *node_end = this->getNode(len-1);   //最后节点
    147.     node_new->next = headnode;            //新节点的next指向第一个节点
    148.     node_end->next = node_new;            //最后节点的next指向新节点
    149.     headnode = node_new;                  //再让headnode指向新节点
    150.     this->len++;
    151.     return *this;
    152. }
    153.  
    154. //insert elements to LinkList_cycle
    155. template <typename T>
    156. LinkList_cycle& LinkList_cycle::insert(int pos, int n, T* arr) {
    157.     if ( pos > len-1 || len < 0 ) {
    158.         cout << "[error]: illegal insert position, please check again" << endl;
    159.         exit(0);
    160.     }
    161.     Node* node_N = getNode(len-1); //前半部分
    162.     Node* temp = node_N->next;    //后半部分
    163.     Node* node_new = nullptr;     //新增加的
    164.     for ( int i = 0; i < n; i++ ) {
    165.         node_new = new Node (arr[n-1-i]);
    166.         node_new->next = temp;
    167.         temp = node_new;
    168.         node_new = nullptr;
    169.     }
    170.     node_N->next = temp;
    171.     if ( pos == 0)    //唯有再0处插入的时候，需要改变头节点，其实对pos=0,一直push_front也行
    172.         headnode = temp;
    173.     this->len += n;
    174.     return *this;
    175. }
    176.  
    177. //delete the first element
    178. template <typename T>
    179. LinkList_cycle& LinkList_cycle::pop_front() {
    180.     if ( this->len == 0 ) {
    181.         cout << "[error]: LinkList_cycle don't has any element" << endl;
    182.         exit(0);
    183.     }
    184.     Node* temp = headnode;  //先复制一份headnode
    185.     headnode = headnode->next;  //headnode 前进一步
    186.     delete temp;             //把第一个节点释放掉
    187.     this->len--;
    188.     temp = getNode(len-1);   //获取最后一个节点
    189.     temp->next = headnode;   //把最后一个节点的next指向新的headnode
    190.     return *this;
    191. }
    192.  
    193. //delete the last element
    194. template <typename T>
    195. LinkList_cycle& LinkList_cycle::pop_back() {
    196.     if ( this->len == 0 ) {
    197.         cout << "[error]: LinkList_cycle don't has any element" << endl;
    198.         exit(0);
    199.     }
    200.     Node* temp1 = getNode(len-2);
    201.     Node* temp2 = temp1->next;
    202.     delete temp2;
    203.     temp1->next = headnode;
    204.     this->len--;
    205.     return *this;
    206. }
    207.  
    208. //get the last node pointer
    209. template <typename T>
    210. Node* LinkList_cycle::getNode(int n) {
    211.     if ( n > len-1 || n < 0) {
    212.         cout << "[warning]: index out of range" <
    213.     }
    214.     n = n%len;
    215.     if ( n < 0 )
    216.         n = n + len;
    217.     Node *node = headnode;
    218.     for( int i = 0; i < n; i++ ) {
    219.         node = node->next;
    220.     }
    221.     return node;
    222. }
    223.  
    224. //remove n elements
    225. template <typename T>
    226. LinkList_cycle& LinkList_cycle::remove(int pos, int num) {
    227.     if ( pos > len-1 || len < 0 ) {
    228.         cout << "[error]: illegal remove position, please check again" << endl;
    229.         exit(0);
    230.     } else if ( pos + num > len) {
    231.         cout << "[error]: remove index out of range" << endl;
    232.         exit(0);
    233.     }
    234.     Node* node_N = getNode(pos-1);
    235.     Node* node_N_num = getNode(pos+num);
    236.     Node* temp = getNode(pos);
    237.     while ( 1 ) {
    238.         Node* node = temp;
    239.         temp = temp->next;
    240.         if ( temp == node_N_num ) {
    241.             break;
    242.         }
    243.         delete node;
    244.     }
    245.     if ( pos == 0 ) {   //如果从0位置开始删除，要修改头节点
    246.         headnode = node_N_num;
    247.         node_N->next = headnode;
    248.     }
    249.     node_N->next = node_N_num;
    250.     this->len -= num;
    251.     return *this;
    252. }
    253.  
    254. //reverse LinkList_cycle
    255. template <typename T>
    256. LinkList_cycle& LinkList_cycle::reverse() {
    257.     const int num = len;
    258.     T arr[num];
    259.     Node* temp = headnode;
    260.     for ( int i = 0; i < this->len; i++ ) {
    261.         arr[i] = temp->value;
    262.         temp = temp->next;
    263.     }
    264.     temp = headnode;
    265.     for ( int i = 0; i < this->len; i++ ) {
    266.         temp->value = arr[len-i-1];
    267.         temp = temp->next;
    268.     }
    269.     return *this;
    270. }
    271.  
    272. template <typename T>
    273. T& LinkList_cycle::operator[](int n) {
    274.     return this->getNode(n)->value;
    275. }
    276.  
    277. template <typename T>
    278. LinkList_cycle& LinkList_cycle::replace(int pos, int n, T* arr) {
    279.     if ( pos > len-1 || len < 0 ) {
    280.         cout << "[error]: illegal remove position, please check again" << endl;
    281.         exit(0);
    282.     } else if ( pos + n > len) {
    283.         cout << "[error]: remove index out of range" << endl;
    284.         exit(0);
    285.     }
    286.     Node* temp = nullptr;
    287.     if ( pos == 0 )
    288.         temp = headnode;
    289.     else
    290.         temp = this->getNode(pos);
    291.     for ( int i = 0; i < n; i++ ) {
    292.         temp->value = arr[i];
    293.         temp = temp->next;
    294.     }
    295.     return *this;
    296. }
    297.  
    298. int main(){
    299.     int arr[]{1,2,4,5,0};
    300.     LinkList_cycle<int> link(arr, sizeof(arr)/sizeof(int));
    301.     cout << "LinkLint init with arr: " <
    302.     link.display();
    303.     cout << "push_back:" << endl;
    304.     link.push_back(34);
    305.     link.display();
    306.     cout << "push_front:" << endl;
    307.     link.push_front(10);
    308.     link.display();
    309.     cout << "insert:" << endl;
    310.     link.insert(0,4,arr);
    311.     link.display();
    312.     cout << "pop_front:" << endl;
    313.     link.pop_front();
    314.     link.display();
    315.     cout << "pop_back:" << endl;
    316.     link.pop_back();
    317.     link.display();
    318.     cout << "remove:" << endl;
    319.     link.remove(0,3);
    320.     link.display();
    321.     cout << "[] operator:" << endl;
    322.     cout << link[2] << endl;
    323.     cout << "replace:" << endl;
    324.     int a[] = {6,5,2};
    325.     link.replace(0, sizeof(a)/sizeof(int), a);
    326.     link.display();
    327.     cout << "LinkList_cycle reserve:" << endl;
    328.     link.reverse();
    329.     link.display();
    330.     cout << "clear:" << endl;
    331.     link.clear();
    332.     cout << "len=" << link.getLen() << endl;
    333.     link.display();
    334. }

  • 相关阅读:
    关于差分进化算法(Differential Evolution)
    大三Web课程设计——悬崖上的波妞(4页) HTML+CSS（可以很好的应付老师的作业）
    uni-app开发小程序实用技巧
    秒验丨Android端SDK API使用说明
    规则引擎深度对比，LiteFlow vs Drools！
    Verilog HDL语言要素
    C语言指针详解
    封装你的第一个vue组件
    Mysql编译安装和yum安装
    uniapp中swiper 轮播带左右箭头，点击切换轮播效果demo(整理)
  • 原文地址：https://blog.csdn.net/a1367666195/article/details/128001093