数据结构 : 循环单链表

C++資料結構

Jonny 自創文章程式設計語言 2017-12-30 1,720 0 0

本文已經過時, 最新文章請點擊 : 《【資料結構-重構】連結串列》

循环单链表和单链表唯一的不同就是循环单链表的最后一个元素的指针域指向了头结点, 而不是指向 nullptr

下面用一张 SVG 图来表示循环单链表

这个是不带尾结点的循环单链表

从上图和上面这句话可以得知, 如果要用类别表示循环单链表, 我能想到的有三种方法

直接继承单链表并且在初始化的时候, 将 first 的指针域指向 first 自身. 并且在加入或者删除结点的时候, 让最后一个指针指向 first
直接继承单链表, 并且加入尾指针 Node *last. 每一次将 last 指向最后一个元素并且 last 的指针域永远指向 first. 这里有两种方法可以检测是否到达 last, 一个是用计数变量, 另外一个是条件判断
直接继承单链表, 并且加入尾指针 Node *last. 与上面的尾指针不同的是, 这个尾指针不再指向最后一个元素, 而是单独代表一个结点, 但是没有具体的数据域, 类似于 first

本篇中的代码将采用第一种方式

循环单链表绝大多数都是和单链表差不多的, 但是由于循环的原因, 在插入或者删除的时候, 尾结点以及最后一个元素要特别注意它们的指针域. 如果指针域指向不正确, 那么可能导致未知的错误

即让最后一个元素的指针域永远指向尾指针或者头指针, 尾指针的指针域永远指向头指针

下面给出源代码, 有错误欢迎指出

分成三个文件, 其中一个是 Class 源文件, 分为 .hpp 文件和 .cpp 文件, 另外一个是 main 函数文件

CircularLinkedList.hpp :

#ifndef CIRCULARLINKEDLIST_CIRCULARLINKEDLIST_HPP
#define CIRCULARLINKEDLIST_CIRCULARLINKEDLIST_HPP

#include <iostream>
#include <cstdlib>

namespace CircularLinkedList {
    using std::cout;
    using std::cin;
    using std::endl;
    class Node {
    protected :
        int data;
        Node *next;
    public :
        int getData();
        Node *getNext();
        void insertData(int data);
        void insertNext(Node *next);
    };
    class LinkList : protected Node {
    protected :
        Node *first;
        bool isEmpty();
        bool deleteFind(int data);
        void deleteOneByElement(int data);
    public :
        LinkList();
        ~LinkList();
        int getLength();
        long long int getElement(int position);
        void insert(int data, int position);
        void insertFromHead(int data);
        void insertFromTail(int data);
        int locateElement(int data);
        int *locateAllData(int data);
        void deleteByPosition(int position);
        void deleteByElement(int data);
        void cleanList();
        void showList();
    };
}


#endif //CIRCULARLINKEDLIST_CIRCULARLINKEDLIST_HPP

CircularLinkedList.cpp :

#include "CircularLinkedList.hpp"

using namespace CircularLinkedList;

int Node::getData() {
    return this->data;
}
Node *Node::getNext() {
    return this->next;
}
void Node::insertNext(Node *next) {
    this->next = next;
}
void Node::insertData(int data) {
    this->data = data;
}
LinkList::LinkList() {
    first = new Node;
    next = first;
    first->insertNext(first);
}
LinkList::~LinkList() {
    Node *linkList = first->getNext();
    while(linkList != first) {
        Node *node;
        node = linkList;
        linkList = node->getNext();
        delete node;
    }
    delete linkList;
}
bool LinkList::isEmpty() {
    if(first->getNext() == first) {
        return true;
    }
    return false;
}
int LinkList::getLength() {
    if(isEmpty()) {
        return 0;
    }
    Node *linkList = first;
    int length = 0;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        length++;
    }
    return length;
}
long long int LinkList::getElement(int position) {
    if(position < 1 || position > getLength()) {
        return INT64_MIN;
    }
    Node *linkList = first;
    for(int i = 1; i <= position; i++) {
        linkList = linkList->getNext();
    }
    auto returnData = (long long int)linkList->getData();
    linkList = nullptr;
    delete linkList;
    return returnData;
}
void LinkList::insert(int data, int position) {
    if(position < 1 || position > getLength() + 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    Node *linkList = first;
    auto *newNode = new Node;
    newNode->insertData(data);
    for(int i = 1; i < position; i++) {
        linkList = linkList->getNext();
    }
    if(position == getLength() + 1) {
        linkList->insertNext(newNode);
        newNode->insertNext(first);
    }else {
        newNode->insertNext(linkList->getNext());
        linkList->insertNext(newNode);
    }
}
void LinkList::insertFromHead(int data) {
    auto *newNode = new Node;
    newNode->insertData(data);
    newNode->insertNext(first->getNext());
    first->insertNext(newNode);
}
void LinkList::insertFromTail(int data) {
    auto *newNode = new Node;
    newNode->insertData(data);
    newNode->insertNext(first);
    int length = getLength();
    Node *linkList = first;
    for(int i = 1; i <= length; i++) {
        linkList = linkList->getNext();
    }
    linkList->insertNext(newNode);
}
int LinkList::locateElement(int data) {
    int position = 0;
    Node *linkList = first;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        position++;
        if(data == linkList->getData()) {
            return position;
        }
    }
    return 0;
}
int *LinkList::locateAllData(int data) {
    int count = 0;
    Node *linkList = first;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        if(linkList->getData() == data) {
            count++;
        }
    }
    if(!count) {
        linkList = nullptr;
        delete linkList;
        return nullptr;
    }
    auto *returnArray = new int[count + 1];
    returnArray[0] = count;
    int returnArrayCount = 1;
    linkList = first;
    int length = getLength();
    for(int i = 1; i <= length; i++) {
        linkList = linkList->getNext();
        if(linkList->getData() == data) {
            returnArray[returnArrayCount] = i;
        }
        returnArrayCount++;
    }
    linkList = nullptr;
    delete linkList;
    return returnArray;
}
void LinkList::deleteByPosition(int position) {
    if(position < 1 || position > getLength()) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    Node *linkList = first;
    for(int i = 1; i < position; i++) {
        linkList = linkList->getNext();
    }
    Node *node;
    node = linkList->getNext();
    if(node->getNext() != first) {
        linkList->insertNext(node->getNext());
        delete node;
    }else {
        linkList->insertNext(first);
        delete node;
    }
    linkList = nullptr;
    delete linkList;
}
bool LinkList::deleteFind(int data) {
    Node *linkList = first;
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        if(linkList->getData() == data) {
            return true;
        }
    }
    linkList = nullptr;
    delete linkList;
    return false;
}
void LinkList::deleteOneByElement(int data) {
    Node *linkList = first;
    while(linkList->getNext() != first) {
        Node *node;
        if(linkList->getNext()->getData() == data) {
            node = linkList->getNext();
            if(node->getNext() == first) {
                linkList->insertNext(first);
                delete node;
            }else {
                linkList->insertNext(node->getNext());
                delete node;
            }
            linkList = nullptr;
            delete linkList;
            break;
        }
        linkList = linkList->getNext();
    }
}
void LinkList::deleteByElement(int data) {
    if(deleteFind(data)) {
        do {
            deleteOneByElement(data);
        }while(deleteFind(data));
    }else {
        cout << "Cannot find the element you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
    }
}
void LinkList::cleanList() {
    Node *linkList = first->getNext();
    while(linkList != first) {
        Node *node;
        node = linkList;
        linkList = linkList->getNext();
    }
    first->insertNext(first);
}
void LinkList::showList() {
    int length = getLength();
    Node *linkList = first;
    cout << "Index : \t";
    for(int i = 1; i <= length; i++) {
        cout << i << "\t";
    }
    cout << endl << "Element : \t";
    while(linkList->getNext() != first) {
        linkList = linkList->getNext();
        cout << linkList->getData() << "\t";
    }
    cout << endl;
}

main.cpp :

#include "CircularLinkedList.hpp"

using namespace CircularLinkedList;

void menu();

int main(int argc, char *argv[]) {
    auto *linkList = new LinkList();
    int choice;
    int length;
    long long int gottenData;
    int location;
    int *locationAll;
    int data, position;
    do {
        system("clear");
        if(linkList->getLength()) {
            linkList->showList();
        }
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                length = linkList->getLength();
                cout << "The length of the list : " << length << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 2 :
                cout << "Please enter the position which you want to get its element : ";
                cin >> position;
                gottenData = linkList->getElement(position);
                if(gottenData == INT64_MIN) {
                    cout << "Cannot find the element you entered!" << endl;
                }else {
                    cout << "Position : " << gottenData << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 3 :
                cout << "Please enter the element's position you want to insert : ";
                cin >> position;
                cout << "Please enter the element you want to insert : ";
                cin >> data;
                linkList->insert(data, position);
                break;
            case 4 :
                cout << "Please enter the element you want to insert : ";
                cin >> data;
                linkList->insertFromHead(data);
                break;
            case 5 :
                cout << "Please enter the element you want to insert : ";
                cin >> data;
                linkList->insertFromTail(data);
                break;
            case 6 :
                cout << "Please enter the element you want to locate : ";
                cin >> data;
                location = linkList->locateElement(data);
                if(location) {
                    cout << "Location : \t" << location << endl;
                }else {
                    cout << "Cannot find the element you entered!" << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 7 :
                cout << "Please enter the element you want to locate : ";
                cin >> data;
                locationAll = linkList->locateAllData(data);
                if(locationAll) {
                    cout << "Location : \t";
                    for(int i = 1; i <= locationAll[0]; i++) {
                        cout << locationAll[i] << "\t";
                    }
                    cout << endl;
                }else {
                    cout << "Cannot find the element you entered!" << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 8 :
                cout << "Please enter the position you want to delete : ";
                cin >> position;
                linkList->deleteByPosition(position);
                break;
            case 9 :
                cout << "Please enter the element you want to delete : ";
                cin >> data;
                linkList->deleteByElement(data);
                break;
            case 10 :
                linkList->cleanList();
                break;
            case 11 :
                delete locationAll;
                delete linkList;
                exit(0);
            default :
                break;
        }
    }while(choice != 11);
}
void menu() {
    cout << "1. Get the list's length." << endl;
    cout << "2. Get element from the list." << endl;
    cout << "3. Insert to the list." << endl;
    cout << "4. Insert from head to the list." << endl;
    cout << "5. Insert from tail to the list." << endl;
    cout << "6. Locate a element from the list." << endl;
    cout << "7. Locate all elements from the list." << endl;
    cout << "8. Delete elements from the list by position." << endl;
    cout << "9. Delete elements from the list by element." << endl;
    cout << "10. Clean the list." << endl;
    cout << "11. Exit." << endl;
    cout << "----------------------------------------------------" << endl;
    cout << "Please enter your choice : ";
}

自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《数据结构 : 循环单链表》https://jonny.vip/2017/12/30/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84-%e5%be%aa%e7%8e%af%e5%8d%95%e9%93%be%e8%a1%a8/

Like (0)