跳转至

AA2-链表的数据结构定义

在C语言中，链表（Linked List）是一种动态的线性数据结构，通过指针将一组零散的存储单元（结点）链接起来。最常见的链表类型是单向链表（Singly Linked List）。

✅ 单向链表的C语言数据结构定义

C
1
2
3
4
5
6
7
8
// 定义链表结点结构
typedef struct ListNode {
    int data;                    // 数据域（以int为例，可改为其他类型）
    struct ListNode *next;       // 指针域，指向下一个结点
} ListNode;

// （可选）定义链表头指针类型
typedef ListNode* LinkList;

🔍 各部分说明

  • data：存储数据元素，可根据需要改为 float、char* 等。
  • next：指向下一个结点的指针，最后一个结点的 next 指向 NULL。
  • ListNode：结点类型名。
  • LinkList：等价于 ListNode*，表示链表的头指针（强调“链表”这一抽象概念）。

✅ 示例：创建一个空链表

C
1
LinkList L = NULL;  // 空链表，头指针为NULL

✅ 结点的动态创建示例

C
1
2
3
4
5
6
7
ListNode *p = (ListNode*)malloc(sizeof(ListNode));
if (p == NULL) {
    printf("内存分配失败\n");
    exit(1);
}
p->data = 10;
p->next = NULL;

🔄 其他常见链表类型定义

1. 带头结点的链表

  • 头结点不存储有效数据，仅作为统一操作的辅助。
  • 插入、删除更方便。
C
1
2
3
4
5
LinkList CreateEmptyList() {
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    return head;
}

2. 双向链表（Doubly Linked List）

C
1
2
3
4
5
typedef struct DListNode {
    int data;
    struct DListNode *prev;  // 指向前一个结点
    struct DListNode *next;  // 指向后一个结点
} DListNode, *DLinkList;

优点：可前后遍历；缺点：占用更多空间。

3. 循环链表（Circular Linked List）

  • 尾结点的 next 指向头结点（或头结点本身）。
C
1
2
// 单向循环链表
ListNode *tail->next = head;  // 形成环

🧠 相关知识点延伸

特性 说明
存储方式 链式存储（非连续内存）
存取方式 顺序访问（O(n) 查找）
插入/删除 O(1)（已知位置），无需移动元素
空间开销 每个结点额外一个（或两个）指针
动态性 可动态申请/释放结点，灵活

📌 常用操作函数原型（建议实现）

C
1
2
3
4
5
6
7
void InitList(LinkList *L);           // 初始化为空链表
int ListInsert(LinkList *L, int i, int e); // 在位置i插入元素e
int ListDelete(LinkList *L, int i, int *e); // 删除位置i的元素
int GetElem(LinkList L, int i, int *e);     // 获取第i个元素
int LocateElem(LinkList L, int e);          // 查找元素e
int ListLength(LinkList L);                 // 返回长度
void DestroyList(LinkList *L);              // 销毁链表，释放内存

✅ 总结：链表通过结构体和指针实现，核心是 data + next 的结点设计。相比顺序表，链表具有动态扩容、插入删除高效等优点，适合频繁增删的场景。掌握链表是学习数据结构的基础。