数据结构源代码合集

一、线性表

其他介绍详见数据结构——线性表。

（1）顺序表

静态分配

▶

title

// 静态分配顺序表
#include <iostream>

#define MaxSize 10

class SqList {
public:
    int data[MaxSize];
    int length;

    SqList() {
        length = 0;
        for (int i = 0; i < MaxSize; ++i) {
            data[i] = 0;
        }
    }
};

    // 函数声明
    void InitList(SqList &L);                           // 初始化
    void DestroyList(SqList &L);                        // 销毁
    void ClearList(SqList &L);                          // 重置为空表
    void PrintList(const SqList &L);                    // 打印
    bool ListEmpty(const SqList &L);                    // 判空
    int ListLength(const SqList &L);                    // 获取长度
    bool GetElem(const SqList &L, int i, int &e);       // 按位查找
    int LocateElem(const SqList &L, int e);             // 按值查找
    bool PriorElem(const SqList &L, int cur_e, int &pre_e); // 查找前驱
    bool NextElem(const SqList &L, int cur_e, int &next_e); // 查找后继
    bool ListInsert(SqList &L, int i, int e);           // 插入
    bool ListDelete(SqList &L, int i, int &e);          // 删除
    void ListTraverse(const SqList &L, void (*visit)(int)); // 遍历
    bool LocateChangeElem(SqList &L, int e, int em);    // 先按值查找后改值
    bool GetChangeElem(SqList &L, int i, int em);       // 先按位序查找后改值
void testModule();                                  // 测试模块

    // 实现模块
    void InitList(SqList &L) {
        L.length = 0;
    }

    void DestroyList(SqList &L) {
        // 静态分配，无需显式销毁
    }

    void ClearList(SqList &L) {
        L.length = 0;
        for (int i = 0; i < MaxSize; ++i) {
            L.data[i] = 0;
        }
    }

    void PrintList(const SqList &L) {
        std::cout << "开始打印顺序表\n";
        for (int i = 0; i < L.length; ++i) {
            std::cout << "Data[" << i << "]==" << L.data[i] << "\n";
        }
        std::cout << "打印结束！\n";
    }

bool ListEmpty(const SqList &L) {
    return L.length == 0;
}

int ListLength(const SqList &L) {
    return L.length;
}

bool GetElem(const SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    return true;
}

int LocateElem(const SqList &L, int e) {
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == e)
            return i + 1; // 返回位序
    }
    return 0; // 未找到返回0
}

bool PriorElem(const SqList &L, int cur_e, int &pre_e) {
    for (int i = 1; i < L.length; ++i) {
        if (L.data[i] == cur_e) {
            pre_e = L.data[i - 1];
            return true;
        }
    }
    return false;
}

bool NextElem(const SqList &L, int cur_e, int &next_e) {
    for (int i = 0; i < L.length - 1; ++i) {
        if (L.data[i] == cur_e) {
            next_e = L.data[i + 1];
            return true;
        }
    }
    return false;
}

bool ListInsert(SqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1 || L.length >= MaxSize)
        return false;
    
    for (int j = L.length; j >= i; --j) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    for (int j = i; j < L.length; ++j) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

void ListTraverse(const SqList &L, void (*visit)(int)) {
    for (int i = 0; i < L.length; ++i) {
        visit(L.data[i]);
    }
}

bool LocateChangeElem(SqList &L, int e, int em) {
    int bitOrder = LocateElem(L, e);
    if (bitOrder != 0) {
        L.data[bitOrder - 1] = em;
        return true;
    }
    return false;
}

bool GetChangeElem(SqList &L, int i, int em) {
    if (i < 0 || i >= L.length) return false;
    L.data[i] = em;
    return true;
}

void visit(int a){
    std::cout<<a<<std::endl;
}

// 测试模块
void testModule() {
    SqList L;
    InitList(L);

    // 初始化一些值
    ListInsert(L, 1, 1);
    ListInsert(L, 2, 2);
    ListInsert(L, 3, 3);

    // 插入操作
    if (ListInsert(L, 2, 4)) {
        std::cout << "插入成功了\n";
    } else {
        std::cout << "插入失败了，i的位置不合法，请检查\n";
    }

    // 删除操作
    int e = -1;
    if (ListDelete(L, 2, e)) {
        std::cout << "删除成功！删除的值是：" << e << "\n";
    } else {
        std::cout << "删除失败，请检查位序是否正确\n";
    }

    // 数组当前长度
    std::cout << "数组当前长度是多少？" << ListLength(L) << "\n";

    // 查找第一个元素是什么？
    if (GetElem(L, 1, e)) {
        std::cout << "第一个元素是：" << e << "\n";
    } else {
        std::cout << "查找失败，位置不合法\n";
    }

    // 查找值为3的元素在什么位置
    std::cout << "第一个值为3的元素在什么位置？" << LocateElem(L, 3) << "\n";

    // 打印输出
    PrintList(L);

    // 测试改模块功能是否正常
    int e1 = 2;
    int em1 = 6;
    int i = 1;
    int em2 = 7;
    std::cout << "开始测试【改】\n"
              << "第一种方式先按值查找后改值\n";
    if (LocateChangeElem(L, e1, em1)) {
        std::cout << "第一种先按值查找后改值成功啦，改变后的值如下：\n";
        PrintList(L);
    } else {
        std::cout << "第一种先按值查找后改值失败了，再检查一下吧！\n";
    }
    std::cout << "第二种先按位序查找后改值\n";
    if (GetChangeElem(L, i, em2)) {
        std::cout << "第二种先按位序查找后改值的方式成功啦，改变后的值如下：\n";
        PrintList(L);
    } else {
        std::cout << "第二种先按位序查找后改值的方式失败了，再检查一下吧！\n";
    }
    if (ListEmpty(L)) {
        std::cout << "顺序表为空！\n";
    } else {
        std::cout << "顺序表非空！\n";
    }

    // 打印输出
    PrintList(L);
    ListTraverse(L,visit);
}

// 主函数
int main() {
    testModule();
    return 0;
}

动态分配

▶

title

// 动态分配顺序表
#include <iostream>
#include <stdlib.h>

#define InitSize 10

    class SeqList {
    public:
        int *data; // 指示动态分配数组的指针
        int MaxSize; // 顺序表的最大容量
        int length; // 顺序表当前的长度

        SeqList() : data(new int[InitSize]), MaxSize(InitSize), length(0) {}
        ~SeqList() {
            delete[] data;
        }
    };

// 函数声明
bool InitList(SeqList &L);                         // 初始化
bool Empty(const SeqList &L);                      // 判空
bool Full(const SeqList &L);                       // 判满
void IncreaseSize(SeqList &L, int len);            // 动态扩展空间
bool ListInsert(SeqList &L, int i, int e);         // 插入
int GetElem(const SeqList &L, int i);              // 按位查找
int LocateElem(const SeqList &L, int e);           // 按值查找
bool ListDelete(SeqList &L, int i, int &e);        // 删除
void DestroySqList(SeqList &L);                    // 销毁
void ClearList(SeqList &L);                        // 清空
int ListLength(const SeqList &L);                  // 获取长度
bool PriorElem(const SeqList &L, int cur_e, int &pre_e); // 查找前驱
bool NextElem(const SeqList &L, int cur_e, int &next_e); // 查找后继
void ListTraverse(const SeqList &L, void (*visit)(int)); // 遍历
void PrintSqList(const SeqList &L);                // 打印顺序表

// 实现模块

// 初始化
bool InitList(SeqList &L) {
    L.data = new int[InitSize]; 
    if (L.data == nullptr) return false;
    L.length = 0;
    L.MaxSize = InitSize;
    return true;
}

// 判空
bool Empty(const SeqList &L) {
    return L.length == 0;
}

// 判满
bool Full(const SeqList &L) {
    return L.length >= L.MaxSize;
}

// 扩展空间
void IncreaseSize(SeqList &L, int len) {
    std::cout << "开始扩展表存储空间..." << std::endl;
    int *p = L.data;
    L.data = new int[L.MaxSize + len];
    for (int i = 0; i < L.length; ++i) {
        L.data[i] = p[i];
    }
    L.MaxSize += len;
    delete[] p;
    std::cout << "扩展完成，当前最大容量: " << L.MaxSize << std::endl;
}

// 插入
bool ListInsert(SeqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1) return false;
    if (Full(L)) IncreaseSize(L, InitSize);
    for (int j = L.length; j >= i; --j) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

// 按位查找
int GetElem(const SeqList &L, int i) {
    if (i < 1 || i > L.length) return -1;
    return L.data[i - 1];
}

// 按值查找
int LocateElem(const SeqList &L, int e) {
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == e) return i + 1;
    }
    return -1;
}

// 删除
bool ListDelete(SeqList &L, int i, int &e) {
    if (i < 1 || i > L.length) return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; ++j) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

// 销毁
void DestroySqList(SeqList &L) {
    delete[] L.data;
    L.data = nullptr;
    L.length = 0;
    L.MaxSize = 0;
}

// 清空
void ClearList(SeqList &L) {
    L.length = 0;
}

// 获取长度
int ListLength(const SeqList &L) {
    return L.length;
}

// 查找前驱
bool PriorElem(const SeqList &L, int cur_e, int &pre_e) {
    for (int i = 1; i < L.length; ++i) {
        if (L.data[i] == cur_e) {
            pre_e = L.data[i - 1];
            return true;
        }
    }
    return false;
}

// 查找后继
bool NextElem(const SeqList &L, int cur_e, int &next_e) {
    for (int i = 0; i < L.length - 1; ++i) {
        if (L.data[i] == cur_e) {
            next_e = L.data[i + 1];
            return true;
        }
    }
    return false;
}

// 遍历
void ListTraverse(const SeqList &L, void (*visit)(int)) {
    for (int i = 0; i < L.length; ++i) {
        visit(L.data[i]);
    }
}

// 打印顺序表
void PrintSqList(const SeqList &L) {
    if (L.data == nullptr || L.length == 0) {
        std::cout << "这是一个空表！" << std::endl;
    } else {
        std::cout << "开始打印顺序表" << std::endl;
        for (int i = 0; i < L.length; ++i) {
            std::cout << "Data[" << i << "] == " << L.data[i] << std::endl;
        }
        std::cout << "打印结束！" << std::endl;
    }
}

// 测试输出
void TestPrint(bool test, const char *message) {
    if (test) {
        std::cout << message << "成功啦!" << std::endl;
    } else {
        std::cout << message << "失败啦！" << std::endl;
    }
}

// 访问函数
void visit(int elem) {
    std::cout << elem << " ";
}

void testModule() {
    SeqList L;
    TestPrint(InitList(L), "初始化");

    // 测试插入和打印
    for (int i = 1; i <= 5; ++i) {
        TestPrint(ListInsert(L, i, i), "插入");
    }
    PrintSqList(L);

    // 测试按位查找
    std::cout << "第3个元素是: " << GetElem(L, 3) << std::endl;

    // 测试按值查找
    std::cout << "值为4的元素的位序是: " << LocateElem(L, 4) << std::endl;

    // 测试删除
    int e;
    TestPrint(ListDelete(L, 2, e), "删除");
    std::cout << "删除的元素是: " << e << std::endl;
    PrintSqList(L);

    // 测试清空
    ClearList(L);
    TestPrint(Empty(L), "清空");
    PrintSqList(L);

    // 重新插入测试PriorElem和NextElem
    for (int i = 1; i <= 5; ++i) {
        ListInsert(L, i, i);
    }
    int pre_e, next_e;
    if (PriorElem(L, 3, pre_e)) {
        std::cout << "元素3的前驱是: " << pre_e << std::endl;
    } else {
        std::cout << "没有前驱元素" << std::endl;
    }

    if (NextElem(L, 3, next_e)) {
        std::cout << "元素3的后继是: " << next_e << std::endl;
    } else {
        std::cout << "没有后继元素" << std::endl;
    }

    // 测试遍历
    std::cout << "遍历顺序表: ";
    ListTraverse(L, visit);
    std::cout << std::endl;

    // 测试获取长度
    std::cout << "顺序表长度是: " << ListLength(L) << std::endl;

    // 测试销毁
    DestroySqList(L);
    TestPrint(Empty(L), "销毁");
    PrintSqList(L);
}

int main() {
    testModule();
    return 0;
}