C++ 静态链表

总结归纳

代码实现

/*
静态链表
*/

#define MaxSize 10

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

struct Node {
    int data;
    int next;
};

typedef Node SLinkList[MaxSize]; // 用SLinkList定义一个长度为MaxSize的Node型数组

// 初始化静态链表
void InitList(SLinkList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L[i].data = 0;
        L[i].next = -2; // 清除脏数据
    }
    L[0].next = -1; // -1表示表尾
}

// 随机对静态链表赋值
bool GetValue(SLinkList &L) {
    int last = 0;
    for (int i = 0; i < 6; i++) {
        int address = rand() % 10;
        int number = rand() % 80;
        if (i == 5) {
            L[last].next = -1;
        } else { // 尾结点的next置为-1
            L[last].next = address;
        }
        L[last].data = number;
        last = address;
    }
    return true;
}

// 按位查找：查找第i个结点的位序
int GetElem(SLinkList &L, int i) {
    if (i < 1) {
        return -1;
    }
    int flag = 0;
    int j = 0;
    while (L[flag].next != -2 && j < i - 1) {
        j++;
        flag = L[flag].next;
    }
    return flag;
}

// 得到一个空结点位序
int GetEmptyNode(SLinkList &L) {
    Node p = L[0];
    for (int i = 0; i < MaxSize; i++) {
        if (L[i].next == -2) {
            return i;
        }
    }
    return -1;
}

// 按位序插入
bool InserstList(SLinkList &L, int i, int e) {
    if (i < 1) { // i值不合法
        return false;
    }
    int q = GetEmptyNode(L); // 找到一个空结点位序
    int p = GetElem(L, i - 1); // 找到第i-1个结点
    L[q].data = e;
    L[q].next = L[p].next;
    L[p].next = q;
    return true;
}

// 按位序删除
bool DeleteList(SLinkList &L, int i, int &e) {
    if (i < 1) { // i值不合法
        return false;
    }
    int p = GetElem(L, i); // 待删除的结点
    int q = GetElem(L, i - 1); // 带删除结点的前一个结点
    cout << L[p].data << " " <<L[p].next << endl;
    cout << L[q].data << " " <<L[q].next << endl;
    e = L[p].data;
    L[q].next = L[p].next;
    L[p].data = 0;
    L[p].next = -2;
    return true;
}

/*
// 按物理空间遍历静态链表
void TraverseList(SLinkList &L) {
    for (int i = 0; i < MaxSize; i++) {
        cout << "第" << i << "个：" << L[i].data << " " << L[i].next << endl;
    }
}
*/

// 按逻辑空间遍历静态链表
void TraverseList(SLinkList &L) {
    for (int i = 0; i < MaxSize; i++) {
        if (L[i].next != 0) {
            cout << "第" << i << "个：" << L[i].data << " " << L[i].next
                 << endl;
        }
    }
}

int main() {
    SLinkList L;
    // Node L[MaxSize];  // 最原始的方法，实现同样效果
    InitList(L);
    GetValue(L);
    TraverseList(L);
    InserstList(L, 3, 5244);
    cout << "插入后的效果：" << endl; 
    TraverseList(L);

    int e = -1;
    DeleteList(L, 5, e);
    cout << "删除的e值：" << e << endl;
    TraverseList(L);
}