数据结构基础代码之链表

▼
c++
复制代码
#include <iostream>
using namespace std;
#define eleType int

// 含有头结点的单链表节点结构
struct LNode {
    eleType data;
    LNode *next;
};

// 初始化链表
void initLNode(LNode *&L) {
    L = new LNode;
    L->next = nullptr;
}

// 销毁链表
void destroyLNode(LNode *L) {
    while (L) {
        LNode *p = L;
        L = L->next;
        delete p;
    }
}

// 判断链表是否为空
bool isEmptyLNode(LNode *L) {
    return L->next == nullptr;
}

// 清空链表元素
void clearLNode(LNode *L) {
    LNode *p, *q;
    p = L->next;
    while (p) {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = nullptr;
}

// 获取链表长度
int getLengthLNode(LNode *L) {
    LNode *p = L->next;
    int i = 0;
    for (; p; ++i) {
        p = p->next;
    }
    return i;
}

// 按元素返回索引
int getIndexByValueLNode(LNode *L, eleType value) {
    LNode *p = L->next;
    int index = 1;
    for (; p && p->data != value; ++index) {
        p = p->next;
    }
    return p ? index : -1; // 如果没有找到，返回-1
}

// 按索引查找元素
eleType getValueByIndexLNode(LNode *L, int index) {
    if (index < 1 || index > getLengthLNode(L)) {
        throw invalid_argument("invalid index!");
    }
    LNode *p = L->next;
    for (int i = 1; p && i < index; ++i) {
        p = p->next;
    }
    return p->data;
}

// 按索引修改元素
void updateValueByIndexLNode(LNode *L, int index, eleType value) {
    if (index < 1 || index > getLengthLNode(L)) {
        throw invalid_argument("invalid index!");
    }
    LNode *p = L->next;
    for (int i = 1; p && i < index; ++i) {
        p = p->next;
    }
    p->data = value;
}

// 元素插入
void insertLNode(LNode *L, int index, eleType value) {
    LNode *p = L;
    int len = getLengthLNode(L);
    if (index < 1 || index > len + 1) {
        throw invalid_argument("invalid index!");
    }
    if (index == len + 1) {
        // 在末尾插入
        while (p->next) {
            p = p->next;
        }
        LNode *s = new LNode;
        s->data = value;
        s->next = nullptr;
        p->next = s;
    } else {
        for (int i = 1; p && i < index - 1; ++i) {
            p = p->next;
        }
        LNode *s = new LNode;
        s->data = value;
        s->next = p->next;
        p->next = s;
    }
}

// 头插法建立链表
void setUpFromHeadLNode(LNode *&L, int n) {
    initLNode(L);
    for (int i = n; i > 0; --i) {
        LNode *p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

// 尾插法建立链表
void setUpFromRearLNode(LNode *&L, int n) {
    initLNode(L);
    LNode *r = L;
    for (int i = 0; i < n; ++i) {
        LNode *p = new LNode;
        cin >> p->data;
        p->next = nullptr;
        r->next = p;
        r = p;
    }
}

// 元素删除
void deleteLNode(LNode *L, int index) {
    if (index < 1 || index > getLengthLNode(L)) {
        throw invalid_argument("invalid index!");
    }
    LNode *p, *q;
    p = L;
    for (int i = 1; p && i < index - 1; ++i) {
        p = p->next;
    }
    q = p->next;
    p->next = q->next;
    delete q;
}

// 打印链表
void printLNode(LNode *L) {
    if (L->next == nullptr) {
        cout << "NULL" << endl;
        return;
    }
    LNode *p = L->next;
    while (p) {
        cout << p->data << "->";
        p = p->next;
    }
    cout << "NULL" << endl;
}

//循环链表中没有空指针，那么p!=nullptr与p!=L等价

//例题：合并带尾指针的链表
LNode *connect(LNode *&La, LNode *&Lb) {
    //假设La和Lb都是非空的单链表
    LNode *p = La->next; //1.p存表头结点
    La->next = Lb->next->next; //2.Lb表头连接La表尾
    delete Lb->next; //3.释放La表头结点
    Lb->next = p; //4.修改指针
    return Lb;
}

//双链表的定义
struct DulNode {
    eleType data;
    DulNode *prior, *next;
};

// 初始化双链表
void initDulList(DulNode *&L) {
    L = new DulNode();
    L->prior = L->next = L; // 头结点的prior和next都指向自己，形成空链表
}

// 双链表的插入
void insertDulNode(DulNode *&L, int index, eleType value) {
    if (index < 0) return; // 非法索引，直接返回

    DulNode *newNode = new DulNode();
    newNode->data = value;

    DulNode *p = L; // 从L开始遍历
    for (int i = 0; p&& i < index; i++) {
        p = p->next;
    }

    if (!p) {
        delete newNode; // 插入位置不合理，释放newNode
        return;
    }

    newNode->next = p->next;
    newNode->prior = p;
    p->next->prior = newNode;
    p->next = newNode;
}

// 双链表的删除
void deleteDulNode(DulNode *&L, int index) {
    if (index < 0) return; // 非法索引，直接返回

    DulNode *p = L; // 从L开始遍历
    for (int i = 0; p && i < index; i++) {
        p = p->next;
    }

    if (!p || p == L) {
        return; // 删除位置不合理或尝试删除头结点
    }

    p->prior->next = p->next;
    p->next->prior = p->prior;
    delete p;
}

// 打印双链表
void printDulList(DulNode *L) {
    DulNode *p = L->next;
    while (p != L) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LNode *list = nullptr;
    //头插法创建
    // setUpFromHeadLNode(list, 3);
    //尾插法创建
    setUpFromRearLNode(list, 3);
    //输出链表
    printLNode(list);
    cout << "------------------------------------------" << endl;
    cout << "链表长度：" << getLengthLNode(list) << endl;
    cout << "链表索引为3的值：" << getValueByIndexLNode(list, 3) << endl;
    cout << "链表值为2的索引：" << getIndexByValueLNode(list, 2) << endl;
    cout << "链表是否为空：" << isEmptyLNode(list) << endl;
    //修改链表
    updateValueByIndexLNode(list, 2, 5);
    printLNode(list);
    cout << "------------------------------------------" << endl;
    //插入元素
    insertLNode(list, 4, 1);
    printLNode(list);
    cout << "------------------------------------------" << endl;
    //删除元素
    deleteLNode(list, 1);
    printLNode(list);
    cout << "------------------------------------------" << endl;
    //清空链表
    clearLNode(list);
    cout << "链表长度：" << getLengthLNode(list) << endl;
    //销毁链表
    destroyLNode(list);

    //双链表的调用
    DulNode *L;
    initDulList(L);

    insertDulNode(L, 0, 1);
    insertDulNode(L, 1, 2);
    insertDulNode(L, 2, 3);
    printDulList(L);
    cout << "---------------------" << endl;
    deleteDulNode(L, 1);
    printDulList(L);
    return 0;
}