MENU

数据结构 - 静态链表

March 14, 2021 • Read: 306 • 数据结构

静态链表

单链表:各个节点在内存中星罗棋布、散乱存储
静态链表:分配一整片凉鞋的内存空间,各个节点集中安置

如下图:

定义

// 定义一个静态链表

#define MaxSize 10        // 静态链表的最大长度
struct Node {                // 静态链表的定义
    int data;                // 静态链表类型(int)的定义
    int next;                // 下一个元素数组的下标
};

如下可以使用数组的形式声明一个静态数组

void test() {
    struct Node a[MaxSize];  // 数组a作为静态链表
}
typedef struct Node SLinkList[MaxSize];

书上使用的方式定义一个静态链表

typedef struct { // 静态链表类型定义
    int data;        // 数据元素
    int next;        // 指向下一个元素的数组下标
}SLinkList[MaxSize];

初始化

初始化静态链表
把a[0]的next设置为-1(假设规定数组下标为-1的该链表的表尾节点)
把其他的next设置为一个特色的值来表示节点空闲,如-2(放置空闲节点有脏数据)

查找

从头节点出发挨个向后面遍历节点 O(n)

插入位序为i的节点
① 找到一个空的节点,存入数据元素
② 从头节点出发找到位序为i-1的节点
③ 修改新节点next
④ 修改i-1号节点的next

删除

① 从头节点出发找到前驱节点
② 修改前驱节点的游标
③ 被删除节点next设置为空(如-2)

总结

  • 静态链表:用数组的方式实现的链表

    • 优点:增、删参数不需要大量移动元素
    • 缺点:不能随机存储,只能从头开始一次往后查找:容量固定不变
  • 使用场景:

    • ① 不支持指针的低级语言
    • ②数据元素数量固定不变的场景(如操作系统的文件分配边FAT)

版权声明:文章转载请注明来源,如有侵权请联系删除!

Last Modified: April 12, 2021
Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

3 Comments
  1. TEST TEST

    @(捂嘴笑)

    1. @TEST@(哈哈)

  2. 文章不错非常喜欢