跳转至

单链表

[未完成]

 链表是一种物理存储上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中指针链接次序实现的。

其大致实现方式如图：

其中由数据和指针构成的集合称为：结点。

结点是一个结构体，其成员包括所存储的数据和下一个结点（结构体）的地址。

注意：

  • 链式结构在逻辑上是连续的，但是在物理上不一定连续。
  • 结点一般都是从堆上申请出来的。
  • 从堆上申请的空间按照一定的策略进行分配，两次申请的空间地址可能连续，也可能不连续。

链表有很多分类：

  • 根据方向
    • 单向
    • 双向
  • 是否带头
    • 带头
    • 不带头
  • 是否循环
    • 循环
    • 不循环

单链表的实现

功能函数

删除第i个结点
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool ListDelete(LinkNode *L, int i, ElemType &e){
    // 迭代变量
    int j = 0;
    LinkNode *p = L, *q;
    // 查找到第 i-1 个结点
    while (j < i - 1 && p != NULL){
        j++;
        p = p->next;
    }
    if (p == NULL) return false;
    else{
        // 将第i个元素地址存储至q中
        q = p->next;
        if (q == NULL) return false;
        // 读取数据域数据
        e = q->data;
        // 将第i个元素的next（第i+1个元素的地址）赋值给第i-1的next（第i个元素的地址）
        p -> next = q -> next;
        // 释放空间
        free(q);
        return true;
    }
}