当前位置：首页 > article >正文

考研408-数据结构完整代码线性表的链式存储结构 - 单链表

article 2025/3/31 2:34:11

单链表操作详解（C++实现）

尾插法创建

#include<bits/stdc++.h>
using namespace std;

typedef struct LNode {
    int data;
    struct LNode* next;
} LNode, *LinkList;

// 尾插法创建单链表
void List_TailInsert(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;             // 创建头节点
    LNode* S, * r = L;          // r始终指向尾节点
    int X;
    cin >> X;
    while (X != 9999) {         // 输入9999时停止
        S = (LNode*)malloc(sizeof(LNode));
        r->next = S;            // 将新节点接在尾节点后
        r = S;                  // 更新尾节点指针
        S->next = NULL;         // 新节点的next置空
        S->data = X;            // 存入数据
        cin >> X;
    }
}

// 打印链表
void List_Print(LinkList L) {
    cout << "当前链表：" << endl;
    LNode* P = L->next;
    while (P != NULL) {
        cout << P->data << " ";
        P = P->next;
    }
    cout << endl;
}

int main() {
    LinkList L;
    List_TailInsert(L);
    List_Print(L);
    return 0;
}

代码说明：
• 时间复杂度：O(n)
• 特点：新节点插入链表尾部，输入顺序与链表顺序一致
• 要点：维护尾指针r，每次插入后更新r

头插法创建

#include<bits/stdc++.h>
using namespace std;

typedef struct LNode {
    int data;
    struct LNode* next;
} LNode, *LinkList;

// 头插法创建单链表
void List_HeadInsert(LinkList& L) {
    LNode* S; int X;
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;             // 创建头节点
    cin >> X;
    while (X != 9999) {         // 输入9999时停止
        S = (LNode*)malloc(sizeof(LNode));
        S->next = L->next;      // 新节点指向原首节点
        L->next = S;            // 头节点指向新节点
        S->data = X;            // 存入数据
        cin >> X;
    }
}

// 打印链表
void PrintList(LinkList L) {
    LNode* p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    LinkList L = NULL;
    List_HeadInsert(L);
    PrintList(L);
    return 0;
}

代码说明：
• 时间复杂度：O(n)
• 特点：新节点插入链表头部，输入顺序与链表顺序相反
• 要点：每次插入后修改头节点的next指针

删除指定节点

// 删除指定节点p（非尾节点）
bool DeleteNode(LNode* p) {
    if (p == NULL || p->next == NULL) // 空节点或尾节点无法删除
        return false;
    LNode* q = p->next;         // 获取后继节点
    p->data = q->data;          // 数据域替换
    p->next = q->next;          // 指针域跳过q
    free(q);                    // 释放内存
    return true;
}

代码说明：
• 时间复杂度：O(1)
• 限制：无法删除最后一个节点
• 特点：通过复制后继节点数据实现伪删除

按值查找

// 按值查找并返回位置
LNode* LocateElem(LinkList L, int e, int& Locate) {
    LNode* P = L->next;
    Locate = 1;
    while (P != NULL && P->data != e) {
        P = P->next;
        Locate++;
    }
    if (P == NULL) Locate = -1; // 未找到标记-1
    return P;
}

/* 调用示例 */
int main() {
    // ...（初始化链表）
    int Locate = -1, e;
    cin >> e;
    LNode* K = LocateElem(L, e, Locate);
    if (K != NULL) {
        cout << "找到元素：" << K->data << " 位置：" << Locate;
    } else {
        cout << "元素未找到";
    }
}

按序号查找

// 按序号查找元素
bool List_LocateFind(LinkList L, int loc) {
    if (loc < 1) return false;
    LNode* p = L->next;
    int K = 1;
    while (p != NULL && K < loc) {
        p = p->next;
        ++K;
    }
    if (p == NULL) return false;
    cout << "位置" << loc << "的元素为：" << p->data;
    return true;
}

插入节点

// 带头节点的插入（位置从1开始）
bool List_Insert1(LinkList& L, int i, int e) {
    if (i < 1) return false;
    LNode* P = L;
    int j = 0;
    while (P != NULL && j < i-1) { // 找到i-1位置
        P = P->next;
        ++j;
    }
    if (P == NULL) return false;
    LNode* S = (LNode*)malloc(sizeof(LNode));
    S->data = e;
    S->next = P->next;
    P->next = S;
    return true;
}

// 不带头节点的插入
bool List_Insert2(LinkList& L, int i, int e) {
    if (i < 1) return false;
    if (i == 1) { // 特殊处理第一个节点
        LNode* S = (LNode*)malloc(sizeof(LNode));
        S->data = e;
        S->next = L;
        L = S;
        return true;
    }
    // 其他位置与带头节点操作相同
    // ...（后续代码类似带头节点情况）
}

注意事项

内存管理：每次malloc后需对应free
边界处理：特别注意头节点和尾节点的操作
时间复杂度：
• 查找操作：O(n)
• 插入/删除：O(1)（已知前驱时）
输入约定：示例中使用9999作为终止输入标记

总结

操作	时间复杂度	要点
头插法	O(n)	维护头指针
尾插法	O(n)	维护尾指针
按值查找	O(n)	遍历比较
按序号查找	O(n)	计数器控制
节点插入	O(n)	找到前驱节点修改指针
节点删除	O(1)	需要前驱节点或特殊处理