C语言静态链表的实现

这篇具有很好参考价值的文章主要介绍了C语言静态链表的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在静态链表中,元素之间按照顺序存储在数组中,数组中的每个元素都包含两个部分:数据部分和游标部分。数据部分用于存储元素的值,游标部分用于指示下一个元素的索引位置。这种结构使得在插入和删除操作时,只需要修改游标,而不需要像链表那样移动整个元素。

对于静态链表的基本操作,包括插入、删除和查找等,具体实现逻辑如下:

  1. 插入操作:首先需要确定插入的位置,然后修改游标以反映新的元素顺序。如果插入的位置在数组的末尾,那么直接修改游标即可;如果插入的位置在数组的中间或开头,则需要按照一定的规则修改游标。
  2. 删除操作:首先需要确定删除元素的索引位置,然后修改游标以反映删除后的元素顺序。如果删除的是数组的最后一个元素,那么直接修改游标即可;如果删除的是数组的中间或开头元素,则需要按照一定的规则修改游标。
  3. 查找操作:在静态链表中查找元素,需要从头元素开始遍历数组,逐个比较元素的值,直到找到目标元素或遍历完整个数组。
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data;
    int next;
} StaticNode;

typedef struct {
    StaticNode nodes[MAX_SIZE];
    int free[MAX_SIZE];
    int size;
    int freeSize;
} StaticList;

// 初始化静态链表
void initList(StaticList* list) {
    list->size = 0;
    list->freeSize = MAX_SIZE;
    for (int i = 0; i < MAX_SIZE - 1; i++) {
        list->free[i] = i + 1;
    }
    list->free[MAX_SIZE - 1] = -1; // 最后一个元素的next设为-1,表示链表结束
}

// 从空闲链表中获取一个节点
int mallocList(StaticList* list) {
    if (list->freeSize > 0) {
        int index = list->free[0];
        list->freeSize--;
        for (int i = 0; i < list->freeSize; i++) {
            list->free[i] = list->free[i + 1];
        }
        return index;
    }
    return -1; // 空闲链表为空,返回-1
}

// 将节点归还给空闲链表
void freeList(StaticList* list, int index) {
    list->free[list->freeSize] = index;
    list->freeSize++;
}

// 在静态链表末尾添加节点
void appendNode(StaticList* list, int data) {
    int index = mallocList(list);
    if (index != -1) {
        list->nodes[index].data = data;
        list->nodes[index].next = -1; // 新添加的节点next设为-1,表示链表结束
        if (list->size == 0) {
            list->nodes[0].next = index; // 如果是第一个节点,头节点指向它
        } else {
            int temp = 0; // 头节点是哑节点,不存数据
            while (list->nodes[temp].next != -1) {
                temp = list->nodes[temp].next;
            }
            list->nodes[temp].next = index; // 找到尾节点,添加新节点
        }
        list->size++;
    } else {
        printf("静态链表已满,无法添加新节点\n");
    }
}

// 打印静态链表
void printList(StaticList* list) {
    int temp = list->nodes[0].next; // 从头节点的下一个节点开始打印
    while (temp != -1) {
        printf("%d ", list->nodes[temp].data);
        temp = list->nodes[temp].next;
    }
    printf("\n");
}

int main() {
    StaticList list;
    initList(&list);
    
    appendNode(&list, 1);
    appendNode(&list, 2);
    appendNode(&list, 3);
    
    printList(&list);
    
    return 0;
}

 文章来源地址https://www.toymoban.com/news/detail-817505.html

到了这里,关于C语言静态链表的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构_链表_单向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月25日 V1.0 发布于博客园 目录 目录 单向循环链表公式 初始化单向循环链表 构建单向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 CircularLinkedLis

    2024年04月25日
    浏览(50)
  • 【玩转408数据结构】线性表——双链表、循环链表和静态链表(线性表的链式表示 下)

            在前面的学习中,我们已经了解到了链表(线性表的链式存储)的一些基本特点,并且深入的研究探讨了单链表的一些特性,我们知道,单链表在实现插入删除上,是要比顺序表方便的,但是,单链表中每个结点仅存在一个指针指向其后续结点,那么如果我们想要找

    2024年04月10日
    浏览(57)
  • 数据结构-二叉链表的结构与实现

    目录 一、引言 二、什么是二叉链表 三、二叉链表的结构 四、二叉链表的实现 1. 创建二叉链表 2. 遍历二叉链表 3. 插入节点 4. 删除节点 五、应用场景 六、总结 七、代码示例 数据结构是计算机科学中的重要概念,它是计算机程序设计的基础。二叉链表是一种常见的数据结构

    2024年02月08日
    浏览(48)
  • 【(数据结构)— 双向链表的实现】

    注意: 这里的 “带头” 跟前面我们说的 “头节点” 是两个概念,实际前面的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表里的头节点,实际为 “哨兵位” ,哨兵位节点不存储任何有效元素,只是站在这里“放哨 的” “哨

    2024年02月06日
    浏览(42)
  • 【数据结构】双向链表的实现

    我要扼住命运的咽喉,他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表,创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(43)
  • 数据结构——双向链表的实现

    注意: 双向链表又称带头双向循环链表 这⾥的“带头”跟前⾯我们说的“头节点”是两个概念,实际前⾯的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头节点。 带头链表⾥的头节点,实际为“ 哨兵位 ”,哨兵位节点不存储任何有效元素,只

    2024年02月06日
    浏览(46)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬移,故时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后

    2024年02月21日
    浏览(50)
  • 数据结构——链表的实现(Java版)

    目录 一、链表 二、代码实现 1.创建结点 2.构造函数 3.链表的相关属性 4.添加虚拟节点 5.判断链表是否为空 6.添加方法 (1)在头部添加 (2)在尾部添加 (3)在索引位置添加 (4)对头插法和尾插法代码进行简化(调用任意位置添加的方法) 7.打印链表(遍历,重写toString方

    2024年01月23日
    浏览(46)
  • 【数据结构】顺序表的实现——静态分配

    🎈个人主页:豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏:数据结构 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、交流进步! 在数据结构的领域中,顺序表是一种基础且重要的线性表实现方式。它采用一段地址连续的存储

    2024年04月26日
    浏览(39)
  • 数据结构:双向链表的实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 本篇博客,将要实现的是 带头双向循环链表 ,该结构实现尾插,尾删只需要O(1)的时间复杂度。 其结构如下所示: 既然要实现的链表是双向循环的,那么对于指针域,我们就需要 指向节点上一个的指针 和 指向节点

    2024年02月14日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包