【数据结构】带头结点的单链表的基本操作

2401_84149564

1022人浏览 · 2025-09-26 20:44:18

2401_84149564 · 2025-09-26 20:44:18 发布

1. 单链表结构定义

typedef struct LNode *LinkList;
struct LNode {
    ElemType data;   // 数据域（支持double类型）
    LinkList next;   // 指针域，指向下一个节点
};

采用带头结点的单链表设计：头结点不存储实际数据，仅用于简化边界操作（如空表插入、首元节点删除）。

2. 初始化算法（`InitList`）

// 初始化带头结点单链表
Status InitList(LinkList &L) {
    L = new LNode;
    if (!L) return OVERFLOW;  // 内存分配失败
    L->next = NULL;
    return OK;
}

功能：创建带头结点的空单链表。步骤：

为头结点分配内存：L = new LNode;。
若内存分配失败（L为NULL），返回OVERFLOW（表示内存溢出）。
将头结点的next指针置为NULL，表示链表初始为空（无首元节点）。时间复杂度：O(1)（仅执行固定次数的内存操作）。

3. 插入算法（`ListInsert`）

// 插入：在第i个位置前插入元素e
Status ListInsert(LinkList &L, int i, ElemType e) {
    LinkList s, p = L;
    int j = 0;
    while (p && j < i - 1) {  // 找第i-1个节点
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) return ERROR;  // 位置不合法

    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

功能：在带头结点的单链表中，第i个位置之前插入元素e。步骤：

初始化指针p指向头结点，计数器j=0（头结点为 “第 0 个节点”）。
循环查找第i-1个节点：p = p->next; j++，直到j == i-1或p为NULL（位置不合法）。
若p为NULL或j > i-1，说明插入位置i超出范围，返回ERROR。
为新节点s分配内存：s = new LNode;，并设置s->data = e。
建立新节点与后续节点的连接：s->next = p->next;。
建立前驱节点与新节点的连接：p->next = s;，完成插入。时间复杂度：O(n)（最坏情况需遍历到表尾，如插入到最后一个位置）。

4. 删除算法（`ListDelete`）

// 删除：删除第i个元素
Status ListDelete(LinkList &L, int i) {
    LinkList p = L, q;
    int j = 0;
    while (p && j < i - 1) {  // 找第i-1个节点
        p = p->next;
        j++;
    }
    if (!p || !p->next || j > i - 1) return ERROR;  // 位置不合法

    q = p->next;
    p->next = q->next;
    delete q;
    return OK;
}

功能：删除带头结点的单链表中第i个位置的元素。步骤：

初始化指针p指向头结点，计数器j=0。
循环查找第i-1个节点：p = p->next; j++，直到j == i-1或p为NULL。
若p为NULL、p->next为NULL（无第i个节点）或j > i-1，返回ERROR。
临时指针q指向待删除的第i个节点：q = p->next;。
跳过待删除节点：p->next = q->next;。
释放待删除节点的内存：delete q;，返回OK。时间复杂度：O(n)（最坏情况需遍历到表尾，如删除最后一个节点）。

5. 打印算法（`PrintList`）

// 打印链表
void PrintList(LinkList L) {
    if (!L) {
        cout << "已销毁";
        return;
    }
    LinkList p = L->next;
    if (!p) {
        cout << "空表";
        return;
    }
    cout << "[";
    while (p) {
        cout << p->data;
        if (p->next) cout << ", ";
        p = p->next;
    }
    cout << "]";
}

功能：遍历并打印单链表的所有元素。步骤：

若L为NULL（链表已销毁），输出 “已销毁”。
否则，指针p指向首元节点（L->next）。
若p为NULL，输出 “空表”（链表仅含头结点，无实际元素）。
否则，循环遍历p，依次输出每个节点的data，并用逗号分隔。时间复杂度：O(n)（需遍历所有节点）。

6. 求表长算法（`ListLength_L`）

// 求表长
int ListLength_L(LinkList L) {
    if (!L) return 0;
    int len = 0;
    LinkList p = L->next;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

功能：计算单链表的长度（实际元素个数）。步骤：

若L为NULL，返回0（链表已销毁）。
指针p指向首元节点，计数器len初始化为0。
循环遍历p：每经过一个节点，len++，直到p为NULL。
返回len（即元素个数）。时间复杂度：O(n)（需遍历所有节点）。

7. 销毁算法（`DestroyList`）

// 销毁链表
void DestroyList(LinkList &L) {
    LinkList p;
    while (L) {
        p = L;
        L = L->next;
        delete p;
    }
}

功能：释放单链表所有节点的内存（包括头结点），避免内存泄漏。步骤：

循环：用指针p暂存当前头结点L。
L后移到下一个节点（L = L->next）。
释放p指向的节点内存（delete p）。
重复步骤 1-3，直到L为NULL（所有节点均被释放）。时间复杂度：O(n)（需遍历并释放所有节点）。

完整C++代码如下：

#include<iostream>
using namespace std;

// 基础定义
typedef double ElemType;  // 支持小数输入
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -2

// 带头结点单链表结构
typedef struct LNode *LinkList;
struct LNode {
    ElemType data;
    LinkList next;
};

// 核心函数声明
Status InitList(LinkList &L);                  // 初始化（带头结点）
Status ListInsert(LinkList &L, int i, ElemType e); // 插入（带头结点）
Status ListDelete(LinkList &L, int i);         // 删除（带头结点）
void PrintList(LinkList L);                    // 辅助打印链表
int ListLength_L(LinkList L);                  // 辅助求表长
void DestroyList(LinkList &L);                 // 销毁链表

int main() {
    LinkList L = NULL;
    int n, i, deletePos;
    ElemType elem;

    // 1. 初始化链表
    cout << "步骤1：初始化带头结点单链表" << endl;
    if (InitList(L) == OK) {
        cout << "初始化成功！" << endl;
    } else {
        cout << "初始化失败！程序退出。" << endl;
        return 1;
    }
    cout << endl;

    // 2. 输入表长并循环插入元素
    cout << "步骤2：创建链表" << endl;
    cout << "请输入要创建的链表长度：";
    cin >> n;

    if (n <= 0) {
        cout << "链表长度必须为正整数！程序退出。" << endl;
        DestroyList(L);
        return 1;
    }

    cout << "请输入" << n << "个元素（用空格分隔）：";
    for (i = 1; i <= n; i++) {
        cin >> elem;
        if (ListInsert(L, i, elem) != OK) {
            cout << "插入第" << i << "个元素失败！" << endl;
            DestroyList(L);
            return 1;
        }
    }

    cout << "链表创建完成！当前链表：";
    PrintList(L);
    cout << endl;

    // 3. 删除操作
    cout << "步骤3：删除元素" << endl;
    int len = ListLength_L(L);
    cout << "当前链表长度为" << len << "，请输入要删除的位置（1~" << len << "）：";
    cin >> deletePos;

    if (ListDelete(L, deletePos) == OK) {
        cout << "删除成功！当前链表：";
        PrintList(L);
    } else {
        cout << "删除失败！位置不合法。" << endl;
    }

    // 4. 释放内存
    DestroyList(L);
    cout << endl << "程序结束，内存已释放。" << endl;
    return 0;
}

// 初始化带头结点单链表
Status InitList(LinkList &L) {
    L = new LNode;
    if (!L) return OVERFLOW;  // 内存分配失败
    L->next = NULL;
    return OK;
}

// 插入：在第i个位置前插入元素e
Status ListInsert(LinkList &L, int i, ElemType e) {
    LinkList s, p = L;
    int j = 0;
    while (p && j < i - 1) {  // 找第i-1个节点
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) return ERROR;  // 位置不合法

    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

// 删除：删除第i个元素
Status ListDelete(LinkList &L, int i) {
    LinkList p = L, q;
    int j = 0;
    while (p && j < i - 1) {  // 找第i-1个节点
        p = p->next;
        j++;
    }
    if (!p || !p->next || j > i - 1) return ERROR;  // 位置不合法

    q = p->next;
    p->next = q->next;
    delete q;
    return OK;
}

// 打印链表
void PrintList(LinkList L) {
    if (!L) {
        cout << "已销毁";
        return;
    }
    LinkList p = L->next;
    if (!p) {
        cout << "空表";
        return;
    }
    cout << "[";
    while (p) {
        cout << p->data;
        if (p->next) cout << ", ";
        p = p->next;
    }
    cout << "]";
}

// 求表长
int ListLength_L(LinkList L) {
    if (!L) return 0;
    int len = 0;
    LinkList p = L->next;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

// 销毁链表
void DestroyList(LinkList &L) {
    LinkList p;
    while (L) {
        p = L;
        L = L->next;
        delete p;
    }
}

C++程序运行结果如下：

完整Python代码如下：

# 定义常量（对应原C++的宏定义）
OK = 1
ERROR = 0
OVERFLOW = -2  # Python内存溢出极少发生，仅保留常量兼容逻辑


# 1. 节点类：模拟C++的LNode结构体
class Node:
    def __init__(self, data=None):
        self.data = data  # 数据域（支持float类型，对应原double）
        self.next = None  # 指针域：指向下一个节点（Python用None表示空指针）


# 2. 单链表类：封装所有操作（对应原C++的函数集合）
class LinkList:
    def __init__(self):
        """初始化：创建带头结点的空链表（对应原InitList函数）"""
        self.head = Node()  # 头结点（不存储实际数据）
        self.is_destroyed = False  # 标记链表是否已销毁（避免野操作）

    def ListInsert(self, i, e):
        """插入操作：在第i个位置前插入元素e（对应原ListInsert函数）"""
        if self.is_destroyed:
            return ERROR
        
        # 步骤1：找到第i-1个节点（头结点为"第0个节点"）
        p = self.head  # p从首元节点的前驱（头结点）开始
        j = 0
        while p is not None and j < i - 1:
            p = p.next
            j += 1
        
        # 步骤2：判断插入位置是否合法
        if p is None or j > i - 1:
            return ERROR
        
        # 步骤3：创建新节点并插入
        s = Node(e)
        s.next = p.next  # 新节点指向原第i个节点
        p.next = s       # 第i-1个节点指向新节点
        return OK

    def ListDelete(self, i):
        """删除操作：删除第i个位置的元素（对应原ListDelete函数）"""
        if self.is_destroyed or self.head.next is None:
            return ERROR
        
        # 步骤1：找到第i-1个节点
        p = self.head
        j = 0
        while p is not None and j < i - 1:
            p = p.next
            j += 1
        
        # 步骤2：判断删除位置是否合法（需确保存在第i个节点）
        if p is None or p.next is None or j > i - 1:
            return ERROR
        
        # 步骤3：删除第i个节点（Python垃圾回收自动释放内存）
        q = p.next       # q暂存待删除节点
        p.next = q.next  # 第i-1个节点跳过待删除节点
        return OK

    def PrintList(self):
        """打印链表（对应原PrintList函数）"""
        if self.is_destroyed:
            print("已销毁", end="")
            return
        
        p = self.head.next  # 从首元节点开始遍历（跳过不存数据的头结点）
        if p is None:
            print("空表", end="")
            return
        
        # 格式化输出链表元素
        print("[", end="")
        while p is not None:
            print(p.data, end="")
            if p.next is not None:
                print(", ", end="")
            p = p.next
        print("]", end="")

    def ListLength_L(self):
        """求表长（对应原ListLength_L函数）"""
        if self.is_destroyed:
            return 0
        
        len_count = 0
        p = self.head.next
        while p is not None:
            len_count += 1
            p = p.next
        return len_count

    def DestroyList(self):
        """销毁链表（对应原DestroyList函数）"""
        # Python无需手动释放内存，断开头节点引用即可触发垃圾回收
        self.head = None
        self.is_destroyed = True


# 3. 主函数：测试流程（与原C++ main逻辑完全一致）
def main():
    # 步骤1：初始化链表
    print("步骤1：初始化带头结点单链表")
    L = LinkList()
    print("初始化成功！")
    print()

    # 步骤2：输入表长并循环插入元素
    print("步骤2：创建链表")
    n = int(input("请输入要创建的链表长度："))
    
    # 检查表长合法性
    if n <= 0:
        print("链表长度必须为正整数！程序退出。")
        L.DestroyList()
        return
    
    # 输入n个元素（支持小数，空格分隔）
    elem_input = input(f"请输入{n}个元素（用空格分隔）：")
    elems = list(map(float, elem_input.split()))  # 转成float列表（对应原double）
    
    # 检查输入元素个数是否匹配表长
    if len(elems) != n:
        print(f"输入元素个数不符（需{n}个）！程序退出。")
        L.DestroyList()
        return
    
    # 循环插入元素（第i个元素插入到第i个位置）
    for i in range(1, n + 1):
        elem = elems[i - 1]
        if L.ListInsert(i, elem) != OK:
            print(f"插入第{i}个元素失败！")
            L.DestroyList()
            return
    
    # 打印创建完成的链表
    print("链表创建完成！当前链表：", end="")
    L.PrintList()
    print()

    # 步骤3：删除操作
    print("步骤3：删除元素")
    len_L = L.ListLength_L()
    deletePos = int(input(f"当前链表长度为{len_L}，请输入要删除的位置（1~{len_L}）："))
    
    if L.ListDelete(deletePos) == OK:
        print("删除成功！当前链表：", end="")
        L.PrintList()
        print()
    else:
        print("删除失败！位置不合法。")
        print()

    # 步骤4：释放内存（销毁链表）
    L.DestroyList()
    print("程序结束，内存已释放。")


if __name__ == "__main__":
    main()

Python程序运行结果如下：

完整Java代码如下：

import java.util.Scanner;

// 主测试类
public class LinkedListTest {
    // 1. 节点类（对应C++的LNode结构体）：封装数据与引用
    private static class Node {
        double data;   // 数据域（对应原C++的double类型ElemType）
        Node next;     // 引用域（替代C++的指针，指向下一个节点）

        // 头节点构造（无实际数据）
        public Node() {
            this.data = 0.0;
            this.next = null;
        }

        // 数据节点构造（初始化数据）
        public Node(double data) {
            this.data = data;
            this.next = null;
        }
    }

    // 2. 链表类（对应C++的函数集合）：封装所有链表操作
    private static class LinkedList {
        // 状态常量（对应原C++的宏定义）
        public static final int OK = 1;
        public static final int ERROR = 0;
        public static final int OVERFLOW = -2;

        private Node head;  // 头节点引用（替代C++的LinkList指针）

        // 初始化：创建带头结点的空链表（对应原InitList函数）
        public LinkedList() {
            try {
                head = new Node();  // 创建头节点（不存数据）
                head.next = null;   // 初始无首元节点，链表为空
            } catch (OutOfMemoryError e) {
                // 模拟C++的内存分配失败（实际Java中极少触发）
                throw new RuntimeException("链表初始化失败：内存溢出");
            }
        }

        // 插入操作：在第i个位置前插入元素e（对应原ListInsert函数）
        public int listInsert(int i, double e) {
            if (head == null) return ERROR;  // 链表已销毁，拒绝操作

            // 步骤1：找到第i-1个节点（头节点为"第0个节点"）
            Node p = head;  // 替代C++的p指针，从首元节点前驱（头节点）开始
            int j = 0;
            while (p != null && j < i - 1) {
                p = p.next;  // 替代C++的p = p->next
                j++;
            }

            // 步骤2：判断插入位置是否合法（i超出范围）
            if (p == null || j > i - 1) {
                return ERROR;
            }

            // 步骤3：创建新节点并插入（Java用new创建对象，无需手动分配内存）
            Node s = new Node(e);
            s.next = p.next;  // 新节点指向原第i个节点
            p.next = s;       // 第i-1个节点指向新节点，完成插入
            return OK;
        }

        // 删除操作：删除第i个位置的元素（对应原ListDelete函数）
        public int listDelete(int i) {
            // 链表已销毁或空表（无首元节点），拒绝操作
            if (head == null || head.next == null) {
                return ERROR;
            }

            // 步骤1：找到第i-1个节点
            Node p = head;
            int j = 0;
            while (p != null && j < i - 1) {
                p = p.next;
                j++;
            }

            // 步骤2：判断删除位置是否合法（无第i个节点）
            if (p == null || p.next == null || j > i - 1) {
                return ERROR;
            }

            // 步骤3：删除节点（Java垃圾回收自动释放无引用节点，无需手动delete）
            p.next = p.next.next;  // 跳过待删除节点，断其引用
            return OK;
        }

        // 打印链表（对应原PrintList函数）
        public void printList() {
            if (head == null) {
                System.out.print("已销毁");
                return;
            }

            Node p = head.next;  // 从首元节点开始遍历（跳过头节点）
            if (p == null) {
                System.out.print("空表");
                return;
            }

            // 格式化输出（与C++格式一致：[x1, x2, x3]）
            System.out.print("[");
            while (p != null) {
                System.out.print(p.data);
                if (p.next != null) {
                    System.out.print(", ");
                }
                p = p.next;
            }
            System.out.print("]");
        }

        // 求表长（对应原ListLength_L函数）
        public int listLength() {
            if (head == null) return 0;

            int len = 0;
            Node p = head.next;
            while (p != null) {
                len++;
                p = p.next;
            }
            return len;
        }

        // 销毁链表（对应原DestroyList函数）
        public void destroy() {
            // Java无需循环删除节点：断开头节点引用，所有节点自动被垃圾回收
            head = null;
        }
    }

    // 3. 主方法：测试流程（与原C++ main逻辑完全一致）
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        LinkedList ll = new LinkedList();  // 初始化链表（调用构造方法）
        int n, deletePos;
        double elem;

        // 步骤1：初始化链表（构造方法已完成，仅提示）
        System.out.println("步骤1：初始化带头结点单链表");
        System.out.println("初始化成功！");
        System.out.println();

        // 步骤2：输入表长并循环插入元素
        System.out.println("步骤2：创建链表");
        System.out.print("请输入要创建的链表长度：");
        n = scanner.nextInt();

        // 检查表长合法性
        if (n <= 0) {
            System.out.println("链表长度必须为正整数！程序退出。");
            ll.destroy();
            scanner.close();
            return;
        }

        // 输入n个元素（支持小数，空格分隔）
        System.out.print("请输入" + n + "个元素（用空格分隔）：");
        double[] elements = new double[n];
        for (int i = 0; i < n; i++) {
            elements[i] = scanner.nextDouble();
        }

        // 循环插入元素（第i个元素插入到第i个位置）
        for (int i = 1; i <= n; i++) {
            elem = elements[i - 1];
            if (ll.listInsert(i, elem) != LinkedList.OK) {
                System.out.println("插入第" + i + "个元素失败！");
                ll.destroy();
                scanner.close();
                return;
            }
        }

        // 打印创建完成的链表
        System.out.print("链表创建完成！当前链表：");
        ll.printList();
        System.out.println();
        System.out.println();

        // 步骤3：删除操作
        System.out.println("步骤3：删除元素");
        int len = ll.listLength();
        System.out.print("当前链表长度为" + len + "，请输入要删除的位置（1~" + len + "）：");
        deletePos = scanner.nextInt();

        if (ll.listDelete(deletePos) == LinkedList.OK) {
            System.out.print("删除成功！当前链表：");
            ll.printList();
            System.out.println();
        } else {
            System.out.println("删除失败！位置不合法。");
        }

        // 步骤4：释放内存（销毁链表）
        ll.destroy();
        System.out.println();
        System.out.println("程序结束，内存已释放。");

        scanner.close();  // 关闭输入流，释放资源
    }
}