静态单链表和单链表意义上其实是一样的. 如果你的静态单链表带 first 指针, 那么也是从 first 指针开始一个一个寻找下一个, 直到找到相应的位置作出相应的处理为止

静态单链表是为一些没有指针的语言提供的, 例如 PHP. 除去用 C++ 描述, 还会有一篇用 PHP 去描述

在 C++ 中使用静态单链表看起来其实很奇怪, 因为静态单链表本身是面向没有指针的语言的, 但本人在用 C++ 进行描述的过程中, 非但出现了不少的指针, 而且还有用到二级指针

首先来讲一下静态单链表, 以下所讲的静态单链表全部带头指针, 头指针数据域为空

1. 特点

静态单链表的特点就是可以用数组去存储, 也就是用数组存储的单链表. 数组分为两个域, 一个是数据域 (Data), 另外一个是游标域 (Cursor). 值得注意的是, 因为在高级语言中不再使用指针, 所以第二个域对应的也就不是指针域

静态单链表的头指针的游标域不一定是第一个元素, 最后一个元素的游标域一定与其他元素有区别. 例如, 其他元素的游标域是 1 - 10 的数字, 那么最后一个元素的游标域可以设置成 -1 或者 0 (推荐 -1)

静态单链表的游标域并非当前所寻找的位置. 举个例子, 假如你要寻找第 5 个元素, 并不是直接寻找 cursor 为 5 的对应数据, 而是需要像单链表一样, 一个一个走过去, 并且期间需要宣告一个计数变量, 用于统计已经走过了几个元素, 当计数变量等于 5 的时候, 这个时候才是真正需要寻找的元素

下面用一张 SVG 图来表示一张静态单链表

假设有一个对象数组 StaticList

在方框左边的数字代表着这个数据域和游标域在数组中存储的下标 (Index)

第一个代表着数据域 (Data)

第二个代表着游标域 (Cursor)

first 代表头指针

首先, 头指针的游标域为 2, 那么就要去数组里寻找下标为 2 的元素, 也就是 StaticList[2]. 这个元素的数据域 为 c, 那么第一个元素就是 c. 接下来获得 c 的游标域, 为 1. 那么就要去数组里寻找下标为 1 的元素... 如此类推, 得到了最下面一行的 "first -> c -> a -> b", 也就是这个静态单链表所表示的数据

2. 插入元素

插入元素其实非常简单. 直接找一个空的位置插入, 此时只需要注意修改和此元素关联的游标域即可. 不需要移动数组, 因为移动数组会使单链表在性质上变成线性表, 毫无意义

下面的 SVG 图表示在第二个元素之后插入一个 "d"

首先在数组第四个元素的数据域中插入 "d". 注意, 此时数组第几个元素和在第几个元素之后插入是两个不同的概念. 然后, 新插入的元素的游标域, 将游标指向插入位置之前一个元素的游标. 例如, 你将一个元素插入值第三个位置, 那么需要修改第二个位置的对应游标域. 图中, 在第二个元素之后插入, 即插在第三个元素, 那么第二个元素的游标改成了新插入元素的位置. 进行如此操作, 完成一个元素的插入

当插入的元素在最后一个的时候, 要注意把游标域改成 -1 即可, 否则后面的循环将会变成死循环

2. 删除元素

删除则必插入还要简单. 上图表示要删除第一个元素 "c", 直接删除之后, 修改前一个元素的游标域为要删除的元素的游标域即可

3. 假满

以上图为例, 当我们再想插入的时候, 发现下面已经没有空间让我们继续插入元素, 但是实际上, 静态单链表并没有满

此时, 我们可以用一个指针指向空的元素

每次结束插入和删除的时候, 都去更新 InsertPointer. 如果 InsertPointer 指向空的地址, 那么说明静态单链表已满

更新 InsertPointer, 其实就是去遍历数组, 找到第一个空的位置

每次插入都向 InsertPointer 这个指针插入新元素即可


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

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

StaticList.cpp :

#ifndef STATICLIST_STATICLIST_HPP
#define STATICLIST_STATICLIST_HPP

#include <iostream>
#include <cstdlib>

namespace StaticList {
    using std::cin;
    using std::cout;
    using std::endl;
    const int cursorLast = -1;
    const int cursorEmpty = -2;
    class Node {
    protected :
        int data;
        int cursor;
    public :
        int getData();
        int getCursor();
        void insertData(int data);
        void insertCursor(int cursor);
    };
    class LinkList : protected Node {
    protected :
        Node **staticList;
        int usedSize;
        int maxSize;
        Node *insertPointer;
        Node *first;
        void getEmptyPosition();
        int getIndex();
    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 //STATICLIST_STATICLIST_HPP

StaticList.cpp :

#include "StaticList.hpp"

using namespace StaticList;

int Node::getData() {
    return this->data;
}
int Node::getCursor() {
    return this->cursor;
}
void Node::insertData(int data) {
    this->data = data;
}
void Node::insertCursor(int cursor) {
    this->cursor = cursor;
}
LinkList::LinkList(int maxSize) {
    staticList = (Node **)new Node *[maxSize + 1];
    for(int i = 0; i <= maxSize; i++) {
        staticList[i] = new Node;
        staticList[i]->insertCursor(cursorEmpty);
    }
    usedSize = 0;
    this->maxSize = maxSize;
    insertPointer = staticList[1];
    first = staticList[0];
    first->insertCursor(cursorLast);
}
LinkList::~LinkList() {
    for(int i = 0; i <= maxSize; i++) {
        delete staticList[i];
    }
    delete []staticList;
    delete insertPointer;
}
void LinkList::getEmptyPosition() {
    bool flag = false;
    for(int i = 1; i <= maxSize; i++) {
        if(staticList[i]->getCursor() == cursorEmpty) {
            insertPointer = staticList[i];
            flag = true;
            break;
        }
    }
    if(!flag) {
        insertPointer = nullptr;
    }
}
int LinkList::getIndex() {
    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->getCursor()];
        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;
    }
    Node *linkList = first;
    int count = 0;
    while(count != position - 1) {
        linkList = staticList[linkList->getCursor()];
        count++;
    }
    insertPointer->insertData(data);
    if(linkList->getCursor() != cursorLast) {
        insertPointer->insertCursor(linkList->getCursor());
        linkList->insertCursor(getIndex());
    }else {
        insertPointer->insertCursor(cursorLast);
        linkList->insertCursor(getIndex());
    }
    usedSize++;
    linkList = nullptr;
    delete linkList;
    getEmptyPosition();
}
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;
    if(linkList->getCursor() == cursorLast) {
        linkList->insertCursor(getIndex());
        insertPointer->insertCursor(cursorLast);
        linkList = nullptr;
        delete linkList;
        usedSize++;
        getEmptyPosition();
        return;
    }
    insertPointer->insertCursor(linkList->getCursor());
    linkList->insertCursor(getIndex());
    usedSize++;
    getEmptyPosition();
    linkList = nullptr;
    delete linkList;
}
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);
    Node *linkList = first;
    while(linkList->getCursor() != cursorLast) {
        linkList = staticList[linkList->getCursor()];
    }
    linkList->insertCursor(getIndex());
    insertPointer->insertCursor(cursorLast);
    getEmptyPosition();
    linkList = nullptr;
    delete linkList;
    usedSize++;
}
int LinkList::locate(int data) {
    Node *linkList = first;
    int count = 0;
    while(linkList->getCursor() != cursorLast) {
        linkList = staticList[linkList->getCursor()];
        count++;
        if(linkList->getData() == data) {
            return count;
        }
    }
    return 0;
}
int *LinkList::locateAllData(int data) {
    Node *linkList = first;
    int count = 0;
    while(linkList->getCursor() != cursorLast) {
        linkList = staticList[linkList->getCursor()];
        if(linkList->getData() == data) {
            count++;
        }
    }
    if(!count) {
        return nullptr;
    }
    auto *location = new int[count];
    linkList = first;
    count = 1;
    int loopCount = 0;
    while(linkList->getCursor() != cursorLast) {
        loopCount++;
        if(staticList[linkList->getCursor()]->getData() == data) {
            location[count] = loopCount;
            count++;
        }
        linkList = staticList[linkList->getCursor()];
    }
    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;
    }
    Node *linkList = first;
    int count = 0;
    while(count != position - 1) {
        linkList = staticList[linkList->getCursor()];
        count++;
    }
    Node *node = staticList[linkList->getCursor()];
    if(node->getCursor() != cursorLast) {
        linkList->insertCursor(node->getCursor());
        node->insertCursor(cursorLast);
    }else {
        linkList->insertCursor(cursorLast);
        node->insertCursor(cursorEmpty);
    }
    usedSize--;
    node = linkList = nullptr;
    delete node;
    delete linkList;
    getEmptyPosition();
}
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;
    }
    while(locate(data)) {
        Node *linkList = first;
        while (linkList->getCursor() != cursorLast) {
            if (staticList[linkList->getCursor()]->getData() == data &&
                staticList[linkList->getCursor()]->getCursor() != cursorLast) {
                Node *node = staticList[linkList->getCursor()];
                linkList->insertCursor(node->getCursor());
                node->insertCursor(cursorEmpty);
                node = nullptr;
                delete node;
                usedSize--;
            } else if (staticList[linkList->getCursor()]->getData() == data &&
                       staticList[linkList->getCursor()]->getCursor() == cursorLast) {
                Node *node = staticList[linkList->getCursor()];
                linkList->insertCursor(cursorLast);
                node->insertCursor(cursorEmpty);
                node = nullptr;
                delete node;
                usedSize--;
            }
            linkList = staticList[linkList->getCursor()];
        }
        linkList = nullptr;
        delete linkList;
    }
    getEmptyPosition();
}
void LinkList::cleanList() {
    Node *linkList = first;
    linkList = staticList[linkList->getCursor()];
    while(linkList->getCursor() != cursorLast) {
        Node *node = linkList;
        linkList = staticList[linkList->getCursor()];
        node->insertCursor(cursorEmpty);
        node = nullptr;
        delete node;
    }
    linkList->insertCursor(cursorEmpty);
    linkList = nullptr;
    delete linkList;
    first->insertCursor(cursorLast);
    usedSize = 0;
}
void LinkList::showList() {
    Node *linkList = first;
    int length = getLength();
    cout << "Index : \t";
    for(int i = 1; i <= getLength(); i++) {
        cout << i << "\t";
    }
    cout << endl << "Element : \t";
    while(linkList->getCursor() != cursorLast) {
        linkList = staticList[linkList->getCursor()];
        cout << linkList->getData() << "\t";
    }
    cout << endl;
}

main.cpp :

#include "StaticList.hpp"

using namespace StaticList;

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 : ";
}