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

也有一段时间没有更博了, 主要是最近事情太多, 课程设计、复习和考试压在一起. 最近闲了一点, 于是立马开始更新, 顺便把之前 2048 的算法也更新了, 有兴趣的可以看下

想了想, 还是把数据结构第 x 课改成了数据结构, 这是因为考虑到后期可能会混乱. 最近看中了几本关于数据结构的书, 只是还没有下手

入正题, 单链表实质上也是线性表, 但是它的存储方式不同, 它是以一个一个结点 (Node) 的方式存储在内存中的, 它的地址不一定是像数组一样连续

因为需要 OOP 思想, 转换为对象, 即对象中起码有两个属性, 数据和指针. 数据用来存储当前结点的具体内容, 指针用来保存下一个结点的地址, 一个连着一个, 最后构成一个完整的单链表

基础的操作与前面的顺序表是差不多的, 只不过存储方式不同而已, 这里不再累赘. 这里主要讲一下单链表中要注意的地方

这里假设有一个对象 : aoto *linkList = new LinkList(), 并且对象中的属性都是 public, 外界可以直接访问 (正式的编程中, 不建议这么操作)

1. 结点的移动操作

单链表的移动其实非常的直观, 就是当前元素的下一个 : linkList->next

这里的 next, 其实就是一个内存地址, 这个地址指向了下一个存储元素. 而 linkList 在这里, 如果用模型去描述, 其实就相当于一个方框. 移动到哪个结点, 就用 linkList 这个 "方框" 把这个结点框住, 代表目前正在访问这个结点

在下面的 SVG 图像中, 很形象地表示了结点的移动, 这里并没有用方框, 而是用了一个向上的箭头代表 linkList

2. 为什么删除结点的时候, 需要用到一个临时的指针 node, 不可以直接删除当前的 linkList 吗?

如果直接删除当前的 linkList, 会造成一个问题, 就是单链表断开

linkList 的前一个元素的 next 指向的是一个被删除的地址, 也就是刚刚被你删除的 linkList 之前的地址, 这就可能会导致程式产生错误

如果还没有明白, 可以看一下以下两张 SVG 图像

第一张是正确删除结点

node 结点被正确删除的时候, linkList->next 会正确地指向被删除前 node->next 结点

但是如果错误删除呢?

看到没, 如果直接删除, 就会找不到下一个地址, 也就是之前所说的单链表断开. 如果单链表断开, 之后的所有操作都将无法进行

3. 插入

上面的删除非常形象地说明了单链表对于结点的操作有着严格的要求, 也就是每一个结点的 next 必须在操作完成之前设置正确, 否则这个单链表就会废掉

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

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

LinkList.hpp :

#ifndef LINKLIST_LINKLIST_HPP
#define LINKLIST_LINKLIST_HPP

#include <iostream>
#include <cstdlib>

namespace singleLinkList {
    using std::cin;
    using std::cout;
    using std::endl;
    class Node {
    protected :
        int data;
        Node *next;
    public :
        Node *getNext();
        int getData();
        void insertData(int data);
        void insertNext(Node *next);
    };
    class LinkList : protected Node{
    protected :
        Node *first;
        bool isEmpty();
        bool deleteFind(int data);
        void deleteAllByElement(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 //LINKLIST_LINKLIST_HPP

LinkList.cpp :

#include "LinkList.hpp"

using namespace singleLinkList;

Node *Node::getNext() {
    return next;
}
int Node::getData() {
    return data;
}
void Node::insertData(int data) {
    this->data = data;
}
void Node::insertNext(Node *next) {
    this->next = next;
}
LinkList::LinkList() {
    first = new Node;
    first->insertNext(nullptr);
}
LinkList::~LinkList() {
    Node *linkList = first;
    while(linkList->getNext() != nullptr) {
        Node *node;
        linkList = linkList->getNext();
        node = linkList;
        linkList = node->getNext();
        delete node;
    }
    delete linkList;
    delete first;
    delete next;
}
bool LinkList::isEmpty() {
    if(first->getNext() == nullptr) {
        return true;
    }
    return false;
}
int LinkList::getLength() {
    int length = 0;
    if(isEmpty()) {
        return 0;
    }else {
        Node *linkList = first;
        while(linkList->getNext() != nullptr) {
            linkList = linkList->getNext();
            length++;
        }
    }
    return length;
}
long long int LinkList::getElement(int position) {
    long long int element;
    if(position < 0 || position > getLength()) {
        return INT64_MIN;
    }
    Node *linkList = first;
    for(int i = 1; i <= position && linkList->getNext() != nullptr; i++) {
        linkList = linkList->getNext();
        if(i == position) {
            break;
        }
    }
    auto returnData = (long long int)linkList->getData();
    linkList = nullptr;
    delete linkList;
    return returnData;
}
void LinkList::insert(int data, int position) {
    if(position > getLength() + 1 || position < 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();
    }
    newNode->insertNext(linkList->getNext());
    linkList->insertNext(newNode);
}
void LinkList::insertFromHead(int data) {
    auto *newNode = new Node();
    newNode->insertData(data);
    Node *linkList = first;
    newNode->insertNext(linkList->getNext());
    linkList->insertNext(newNode);
}
void LinkList::insertFromTail(int data) {
    auto *newNode = new Node();
    newNode->insertData(data);
    newNode->insertNext(nullptr);
    Node *linkList = first;
    while(linkList->getNext() != nullptr) {
        linkList = linkList->getNext();
    }
    linkList->insertNext(newNode);
}
int LinkList::locateElement(int data) {
    Node *linkList = first;
    int position = 0;
    while(linkList->getNext() != nullptr) {
        linkList = linkList->getNext();
        position++;
        if(linkList->getData() == data) {
            break;
        }
    }
    if(position == getLength()) {
        return -1;
    }
    return position;
}
int *LinkList::locateAllData(int data) {
    int length = getLength();
    auto *locatedArray = new int[length];
    Node *linkList = first;
    int count = 0;
    while(linkList->getNext() != nullptr) {
        linkList = linkList->getNext();
        locatedArray[count] = linkList->getData();
        count++;
    }
    if(count == 0) {
        return nullptr;
    }
    int positionNumber = 0;
    int positionCount = 1;
    for(int i = 0; i < count; i++) {
        if(locatedArray[i] == data) {
            positionNumber++;
        }
    }
    auto *position = new int[positionNumber + 1];
    position[0] = positionNumber;
    for(int i = 0; i < count; i++) {
        if(locatedArray[i] == data) {
            position[positionCount] = i + 1;
            positionCount++;
        }
    }
    return position;
}
void LinkList::deleteByPosition(int position) {
    if(position < 0 || 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 = linkList->getNext();
    linkList->insertNext(node->getNext());
    delete node;
    linkList = nullptr;
    delete linkList;
}
bool LinkList::deleteFind(int data) {
    Node *linkList = first;
    while(linkList->getNext() != nullptr) {
        linkList = linkList->getNext();
        if(linkList->getData() == data) {
            return true;
        }
    }
    return false;
}
void LinkList::deleteAllByElement(int data) {
    Node *linkList = first;
    while(linkList->getNext() != nullptr) {
        if(linkList->getNext()->getData() == data) {
            Node *node;
            node = linkList->getNext();
            if(node->getNext()) {
                linkList->insertNext(node->getNext());
                delete node;
            }else {
                linkList->insertNext(nullptr);
                delete node;
                linkList = nullptr;
                delete linkList;
                return;
            }
        }
        linkList = linkList->getNext();
    }
    linkList = nullptr;
    delete linkList;
}
void LinkList::deleteByElement(int data) {
    if(deleteFind(data)) {
        while(deleteFind(data)) {
            deleteAllByElement(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->getNext() != nullptr) {
        Node *node;
        node = linkList;
        linkList = linkList->getNext();
        delete node;
    }
    linkList = nullptr;
    delete linkList;
}
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() != nullptr) {
        linkList = linkList->getNext();
        cout << linkList->getData() << "\t";
    }
    cout << endl;
    cout << "----------------------------------------------------" << endl;
}

main.cpp :

#include "LinkList.hpp"

using namespace singleLinkList;

void menu();

int main(int argc, char *argv[]) {
    LinkList *linkList = new LinkList();
    int choice;
    int length;
    long long int gottenData;
    int location;
    int *locationAll, locationArrayNumber;
    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 : " << 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);
                locationArrayNumber = locationAll[0];
                if(locationArrayNumber) {
                    cout << "Location : ";
                    for(int i = 1; i <= locationArrayNumber; 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 : ";
}