没错, 非限定性线性表还没有完, 还有最后一个 : 静态双向链表

之前一直在想, 这个要不要写, 因为书本上并没有提到这个, 只是我自己从双向链表和静态链表引申出来的. 后来一想, 为了完整, 还是写了吧. 写了才知道, 错误百出, 其实一个星期之前就写完了, 但是调试用了一星期 (实际是忙于考试, 没时间调试, 每次都是打开了 CLion 然后挂在那里开始玩手机, 玩着玩着就说, 明天吧. 今天正式回家第一天, 才把这个搞完, 逃...

我们把上次一次的 SVG 示例图进行拓展, 拓展成双向链表

实际的性质上, 和双向链表是差不多的, 也是多了一个 Previous 指针域. 修改的时候, 初始化、插入和删除注意一下即可. 具体可以参考一下《数据结构 : 双向链表》


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

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

StaticCircularLinkedList.hpp :

#ifndef STATICCIRCULARLINKEDLIST_STATICCIRCULARLINKEDLIST_HPP
#define STATICCIRCULARLINKEDLIST_STATICCIRCULARLINKEDLIST_HPP

#include <iostream>
#include <cstdlib>

namespace StaticCircularLinkedList {
    using std::cin;
    using std::cout;
    using std::endl;
    const int cursorEmpty = -2;
    const int cursorFirst = 0;
    class Node {
    protected :
        int data;
        int previous;
        int next;
    public :
        int getData();
        int getPrevious();
        int getNext();
        void insertData(int data);
        void insertPrevious(int previous);
        void insertNext(int next);
    };
    class LinkList : protected Node {
    protected :
        Node **staticList;
        int usedSize;
        int maxSize;
        Node *insertPointer;
        Node *first;
        int getInsertPointerIndex();
        void insertPointerFind();
    public :
        LinkList(int maxSize);
        ~LinkList();
        int getLength();
        long long int getElement(int position);
        void insert(int data, int position);
        void insertFromHead(int data);
        void insertFromTail(int data);
        int locate(int data);
        int *locateAllData(int data);
        void deleteByPosition(int position);
        void deleteByElement(int data);
        void cleanList();
        void showList();
    };
}

#endif //STATICCIRCULARLINKEDLIST_STATICCIRCULARLINKEDLIST_HPP

StaticCircularLinkedList.cpp :

#include "StaticCircularLinkedList.hpp"

using namespace StaticCircularLinkedList;

int Node::getData() {
    return this->data;
}
int Node::getNext() {
    return this->next;
}
int Node::getPrevious() {
    return this->previous;
}
void Node::insertData(int data) {
    this->data = data;
}
void Node::insertPrevious(int previous) {
    this->previous = previous;
}
void Node::insertNext(int next) {
    this->next = next;
}
LinkList::LinkList(int maxSize) {
    this->maxSize = maxSize;
    staticList = (Node **)new Node *[maxSize + 1];
    for(int i = 0; i <= maxSize; i++) {
        staticList[i] = new Node;
        staticList[i]->insertNext(cursorEmpty);
        staticList[i]->insertPrevious(cursorEmpty);
    }
    usedSize = 0;
    insertPointer = staticList[1];
    first = staticList[0];
    first->insertPrevious(cursorFirst);
    first->insertNext(cursorFirst);
}
LinkList::~LinkList() {
    for(int i = 0; i <= maxSize; i++) {
        delete staticList[i];
    }
    delete []staticList;
    insertPointer = first = nullptr;
    delete insertPointer;
    delete first;
}
void LinkList::insertPointerFind() {
    bool flag = false;
    for(int i = 1; i <= maxSize; i++) {
        if(staticList[i]->getNext() == cursorEmpty) {
            insertPointer = staticList[i];
            flag = true;
            break;
        }
    }
    if(!flag) {
        insertPointer = nullptr;
    }
}
int LinkList::getInsertPointerIndex() {
    for(int i = 1; i <= maxSize; i++) {
        if(insertPointer == staticList[i]) {
            return i;
        }
    }
    return 0;
}
int LinkList::getLength() {
    return usedSize;
}
long long int LinkList::getElement(int position) {
    if(position < 1 || position > usedSize) {
        return INT64_MIN;
    }
    Node *linkList = first;
    int count = 0;
    while(count != position) {
        linkList = staticList[linkList->getNext()];
        count++;
    }
    auto returnData = (long long int)linkList->getData();
    linkList = nullptr;
    delete linkList;
    return returnData;
}
void LinkList::insert(int data, int position) {
    if(!insertPointer) {
        cout << "The static list is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    if(position < 1 || position > usedSize + 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    Node *linkList = first;
    int count = 0;
    while(count != position - 1) {
        linkList = staticList[linkList->getNext()];
        count++;
    }
    insertPointer->insertData(data);
    if(linkList->getNext() != cursorFirst) {
        insertPointer->insertNext(linkList->getNext());
        Node *node = staticList[linkList->getNext()];
        linkList->insertNext(getInsertPointerIndex());
        node->insertPrevious(getInsertPointerIndex());
        node = nullptr;
        delete node;
        int linkListCursor = -1;
        for(int i = 0; i <= usedSize; i++) {
            if(staticList[i] == linkList) {
                linkListCursor = i;
                break;
            }
        }
        insertPointer->insertPrevious(linkListCursor);
    }else {
        insertPointer->insertNext(cursorFirst);
        linkList->insertNext(getInsertPointerIndex());
        first->insertPrevious(getInsertPointerIndex());
        int linkListCursor = -1;
        for(int i = 0; i <= usedSize; i++) {
            if(staticList[i] == linkList) {
                linkListCursor = i;
                break;
            }
        }
        insertPointer->insertPrevious(linkListCursor);
    }
    usedSize++;
    linkList = nullptr;
    delete linkList;
    insertPointerFind();
}
void LinkList::insertFromHead(int data) {
    if(!insertPointer) {
        cout << "The static list is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    insertPointer->insertData(data);
    Node *linkList = first;
    Node *node = staticList[linkList->getNext()];
    insertPointer->insertNext(linkList->getNext());
    insertPointer->insertPrevious(node->getPrevious());
    linkList->insertNext(getInsertPointerIndex());
    node->insertPrevious(getInsertPointerIndex());
    linkList = node = nullptr;
    delete linkList;
    delete node;
    usedSize++;
    insertPointerFind();
}
void LinkList::insertFromTail(int data) {
    if(!insertPointer) {
        cout << "The static list is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    insertPointer->insertData(data);
    insertPointer->insertNext(cursorFirst);
    Node *linkList = first;
    insertPointer->insertPrevious(linkList->getPrevious());
    linkList->insertPrevious(getInsertPointerIndex());
    while(linkList->getNext() != cursorFirst) {
        linkList = staticList[linkList->getNext()];
    }
    linkList->insertNext(getInsertPointerIndex());
    linkList = nullptr;
    usedSize++;
    delete linkList;
    insertPointerFind();
}
int LinkList::locate(int data) {
    int count = 0;
    Node *linkList = first;
    while(linkList->getNext() != cursorFirst) {
        linkList = staticList[linkList->getNext()];
        count++;
        if(linkList->getData() == data) {
            return count;
        }
    }
    return 0;
}
int *LinkList::locateAllData(int data) {
    Node *linkList = first;
    int count = 0;
    while(linkList->getNext() != cursorFirst) {
        linkList = staticList[linkList->getNext()];
        if(linkList->getData() == data) {
            count++;
        }
    }
    if(!count) {
        return nullptr;
    }
    auto *location = new int[count];
    linkList = first;
    count = 1;
    int loopCount = 0;
    while(linkList->getNext() != cursorFirst) {
        loopCount++;
        if(staticList[linkList->getNext()]->getData() == data) {
            location[count] = loopCount;
            count++;
        }
        linkList = staticList[linkList->getNext()];
    }
    location[0] = count - 1;
    linkList = nullptr;
    delete linkList;
    return location;
}
void LinkList::deleteByPosition(int position) {
    if(position < 1 || position > usedSize) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    int count = 0;
    Node *linkList = first;
    while(count != position - 1) {
        linkList = staticList[linkList->getNext()];
        count++;
    }
    Node *node = staticList[linkList->getNext()];
    if(position == usedSize) {
        linkList->insertNext(cursorFirst);
        int linkListCursor = -1;
        for(int i = 1; i <= usedSize; i++) {
            if(staticList[i] == linkList) {
                linkListCursor = i;
                break;
            }
        }
        first->insertPrevious(linkListCursor);
        usedSize--;
        node->insertNext(cursorEmpty);
        node->insertPrevious(cursorEmpty);
        insertPointerFind();
        node = linkList = nullptr;
        delete node;
        delete linkList;
        return;
    }
    linkList->insertNext(node->getNext());
    int pre = node->getPrevious();
    node->insertPrevious(cursorEmpty);
    node->insertNext(cursorEmpty);
    node = staticList[linkList->getNext()];
    node->insertPrevious(pre);
    usedSize--;
    insertPointerFind();
    node = linkList = nullptr;
    delete node;
    delete linkList;
}
void LinkList::deleteByElement(int data) {
    if(!locate(data)) {
        cout << "Cannot find the element you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    do {
        deleteByElement(locate(data));
    }while(locate(data));
}
void LinkList::cleanList() {
    Node *linkList = first;
    linkList = staticList[linkList->getNext()];
    while(linkList->getNext() != cursorFirst) {
        Node *node = linkList;
        linkList = staticList[linkList->getNext()];
        node->insertNext(cursorEmpty);
        node->insertPrevious(cursorEmpty);
        node = nullptr;
        delete node;
    }
    linkList->insertNext(cursorEmpty);
    linkList->insertPrevious(cursorEmpty);
    linkList = nullptr;
    delete linkList;
    first->insertPrevious(cursorFirst);
    first->insertNext(cursorFirst);
    usedSize = 0;
    insertPointer = staticList[1];
}
void LinkList::showList() {
    Node *linkList = first;
    int length = getLength();
    cout << "Index : \t";
    for(int i = 1; i <= length; i++) {
        cout << i << "\t";
    }
    cout << endl << "Element : \t";
    while(linkList->getNext() != cursorFirst) {
        linkList = staticList[linkList->getNext()];
        cout << linkList->getData() << "\t";
    }
    cout << endl;
}

main.cpp :

#include "StaticCircularLinkedList.hpp"

using namespace StaticCircularLinkedList;

void menu();

int main(int argc, char *argv[]) {
    int maxSize;
    cout << "Please enter the static list's size : ";
    cin >> maxSize;
    auto *linkList = new LinkList(maxSize);
    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->locate(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 : ";
}