C++實現(xiàn)單鏈表（Single Linked List）

語言這個東西不用真的會忘辉懒， 我記得前前后后C++的基本語法我也看了好幾遍了愉耙，一直沒有動手寫過什么東西蔬蕊，所以一遍遍的看僧叉，一遍遍的忘... ...

正好最近在看數(shù)據(jù)結(jié)構(gòu)奕枝，想著自己用C++來實現(xiàn)一下，一方面是熟悉整個邏輯過程瓶堕，加深對數(shù)據(jù)結(jié)構(gòu)的理解隘道，另一方面，也熟悉一下C++郎笆。

單鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)谭梗，同順序存儲結(jié)構(gòu)（可以理解為C++中的數(shù)組）不同的是，單鏈表在插入和刪除一個結(jié)點時宛蚓，不需要移動大量的元素激捏，但是單鏈表沒有數(shù)組中索引的概念，所以在查詢一個元素時沒有數(shù)組方便凄吏。

單鏈表由結(jié)點（Node）組成远舅，結(jié)點中有一個數(shù)據(jù)域和一個指針域，數(shù)據(jù)域存放結(jié)點中的數(shù)據(jù)痕钢，指針域指向下一個結(jié)點的地址图柏，我們所實現(xiàn)的單鏈表是帶有頭結(jié)點的單鏈表，與其他結(jié)點不同任连，頭結(jié)點中的數(shù)據(jù)域不存放數(shù)據(jù)蚤吹。下圖是結(jié)點和單鏈表結(jié)構(gòu)的示意圖。
結(jié)點示意圖:

Node

單鏈表示意圖:

Single Linked List

需要說明的是课梳，我的這個程序中的索引是從0開始的距辆，而且默認(rèn)數(shù)據(jù)都是正的int類型余佃。

單鏈表的類定義：

class LinkList {
private:
    class Node {
    public:
        int data;
        Node *next;
    };
    Node *head;
    int length = 0;
public:
    LinkList();

    void create(int n);//初始化n個結(jié)點的單鏈表

    void print() const;//打印單鏈表中的數(shù)據(jù)

    int getLength() const;//獲取單鏈表的長度

    void isEmpty() const;//判斷單鏈表是否為空

    int search(int index) const;//查找索引為index的數(shù)據(jù)并返回

    int find(int elem) const;//查找數(shù)據(jù)為elem的索引并返回

    void insertByIndex(int index, int data);//在索引為index之前的位置插入數(shù)據(jù)為data的結(jié)點

    void deleteByIndex(int index);//刪除索引為index的結(jié)點
};

類中的函數(shù)實現(xiàn)：

LinkList::LinkList() {
    head = new Node;
    head->data = 0;
    head->next = nullptr;
}

int LinkList::getLength() const {
    cout << "鏈表中的元素個數(shù)為：" << length << endl;
    return length;
}

void LinkList::create(int n) {
    Node *pre = head;
    length = n;
    int i = 1;
    while (i <= n) {
        cout << "請輸入第" << i << "個結(jié)點的數(shù)據(jù)：";
        Node *cur = new Node;
        cin >> cur->data;
        ++i;
        pre->next = cur;
        pre = cur;
        cur->next = nullptr;
    }
}

void LinkList::print() const {
    Node *cur = head->next;
    if (!length) {
        cout << "鏈表為空暮刃！" << endl;
        return;
    }
    cout << "*******************" << endl;
    cout << "鏈表中的元素為：" << endl;
    while (cur) {
        cout << cur->data << " ";
        cur = cur->next;
    }
    cout << endl;
    cout << "*******************" << endl;
}

void LinkList::isEmpty() const {
    if (!length) {
        cout << "鏈表為空~" << endl;
        return;
    }
    cout << "鏈表不為空" << "，";
    this->getLength();
}

int LinkList::search(int index) const { //認(rèn)為索引從0開始
    if (index < 0 || index >= length)
        cout << "索引輸入錯誤爆土！" << endl;
    else {
        Node *temp = head->next;
        int i = 0;
        while (temp) {
            if (i == index) {
                cout << "鏈表中索引為" << index << "的數(shù)據(jù)為" << temp->data << endl;
                return temp->data;
            } else {
                ++i;
                temp = temp->next;
            }
        }
    }
    return -1;//假定鏈表中不存入負(fù)數(shù)
}

int LinkList::find(int elem) const {
    Node *cur = head->next;
    int index = 0;
    while (cur) {
        if (cur->data == elem)
            return index;
        else {
            cur = cur->next;
            ++index;
        }
    }
    cout << elem << "不在鏈表中椭懊！" << endl;
    return -1;
}

void LinkList::insertByIndex(int index, int data) { //在index之前插入數(shù)據(jù)為data的結(jié)點
    if (index < 0 || index >= length) {
        cout << "索引位置不合法" << endl;
    } else {
        Node *cur = head;
        int pos = 0;
        while (pos != index) {
            cur = cur->next;
            ++pos;
        }
        Node *temp = new Node;
        temp->data = data;
        temp->next = cur->next;
        cur->next = temp;
        ++length;
        cout << data << "插入成功！" << endl;
    }
}

void LinkList::deleteByIndex(int index) {
    if (index < 0 || index >= length) {
        cout << "索引輸入錯誤！" << endl;
    } else {
        Node *cur = head;
        int pos = 0;
        while (pos != index) {
            cur = cur->next;
            ++pos;
        }
        Node *temp = cur->next;
        cur->next = temp->next;
        delete temp;
        --length;
        cout << "刪除成功!" << endl;
    }
}

測試代碼：

/*
 * Software:Jetbrains clion 2022.1
 * Created by xiaoxin_zh@foxmail.com
 * Implementing Singly Linked List with C++
 */

#include <iostram>

using std::cin;
using std::cout;
using std::endl;

int main() {
    LinkList linkList;
    cout << "請輸入鏈表中結(jié)點的個數(shù)：";
    int n;
    cin >> n;
    linkList.create(n);
    linkList.print();
    linkList.getLength();
    linkList.isEmpty();
    cout << "請輸入需要查詢的索引位置：";
    int index;
    cin >> index;
    linkList.search(index);
    cout << "請輸入需要查詢的數(shù)據(jù):";
    int elem;
    cin >> elem;
    if (linkList.find(elem) != -1) {
        cout << elem << "在鏈表中的索引位置是" << linkList.find(elem) << endl;
    }
    cout << "請輸入需要插入結(jié)點的位置索引和數(shù)值：";
    int pos, data;
    cin >> pos >> data;
    linkList.insertByIndex(pos, data);
    linkList.print();
    linkList.getLength();
    cout << "請輸入需要刪除的結(jié)點索引：";
    int deleteIndex;
    cin >> deleteIndex;
    linkList.deleteByIndex(deleteIndex);
    linkList.print();
    linkList.getLength();
    return 0;
}

假設(shè)實現(xiàn)的原始單鏈表有4個結(jié)點氧猬，數(shù)值分別為12背犯、23、34盅抚、45漠魏，結(jié)構(gòu)如圖所示：

create

查詢索引為1的元素，應(yīng)該返回23妄均；

查找數(shù)據(jù)為45的索引位置柱锹，應(yīng)該返回3；

在索引為2的前面插入一個數(shù)值為88的結(jié)點丰包，其步驟如圖所示：

insert

刪除索引為3的結(jié)點禁熏，其步驟如圖所示：

delete

測試代碼執(zhí)行：

result