热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2.7.静态链表

图片均来自B站王道考研(侵删)1.静态链表:静态链表:分配一整片连续的内存空间,各个节点集中安置静态链表的每个节点,都包含了:数据元素、下一个结点的数组下标(游标),游标充当“指针




图片均来自B站王道考研(侵删)

请添加图片描述


1.静态链表:


  1. 静态链表:分配一整片连续的内存空间,各个节点集中安置
  2. 静态链表的每个节点,都包含了:数据元素、下一个结点的数组下标(游标),游标充当“指针”,单链表中每个节点存放的指针,只不过指针指明了具体的内存地址,而游标指明了下一个元素存放的数组下标
  3. 单链表中的表尾元素的*next指针指向NULL,而在静态链表中如果想表示这个结点是最后一个节点,则可以将它的游标设置为-1(即游标为-1表示已经到达表尾)
  4. 0号结点充当头结点
  5. 设每个元素的大小为4B,每个游标的大小也为4B(每个节点共8B),设起始地址为addr,则头结点指向的下一个结点地址为:addr+8*n(n为接下来的结点的数组下标)

2.用代码定义一个静态链表:

#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储的数据元素
int next; //下一个元素的数组下标
};
void testSLinkList{
struct Node a[MaxSize]; //数组a作为静态链表
//....
}
//书本代码:
#define MaxSize 10
typedef struct{
ElemType data;
int next;
}SLinkList[MaxSize];
//等价于:
#define MaxSize 10
struct Node{
ElemType data;
int next;
};
typedef struct Node SLinkList[MaxSize]; //可以用SLinkList去定义一个长度为MaxSize的Node型数组;
void testSLinkList{
SLinkList a;
//上面这一行等价于:struct Node a[MaxSize];
//......
}

3.简述基本操作的实现


  1. 初始化静态链表:把a[0]的next设置为-1,将其余的空闲结点的游标设置为-2,以便于后面寻找空余结点时进行判断

  2. 查找:从头结点出发挨个往后遍历节点

  3. 插入位序为i的结点

    ①找到一个空的结点,存入数据元素

    ②从头结点出发找到位序为i-1的结点

    ③修改新的结点的next

    ④修改i-1号结点的next

  4. 删除某个节点:

    ①从头结点出发找到前驱节点

    ②修改前驱节点的游标

    ③被删除的结点的游标设置为-2


4.总结:


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

  2. 优点:增、删操作不需要大连的移动元素,只需要修改相关的结点的游标即可

  3. 缺点:不能随机存取,只能从头结点开始依次往后查找;容量固定不可变

  4. 适用场景:

    ①不支持指针的低级语言

    ②数据元素数量固定不变的场景(如操作系统的文件分配表FAT)



推荐阅读
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 2023年京东Android面试真题解析与经验分享
    本文由一位拥有6年Android开发经验的工程师撰写,详细解析了京东面试中常见的技术问题。涵盖引用传递、Handler机制、ListView优化、多线程控制及ANR处理等核心知识点。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 1.如何在运行状态查看源代码?查看函数的源代码,我们通常会使用IDE来完成。比如在PyCharm中,你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢?当我们想使用一个函 ... [详细]
  • Python自动化处理:从Word文档提取内容并生成带水印的PDF
    本文介绍如何利用Python实现从特定网站下载Word文档,去除水印并添加自定义水印,最终将文档转换为PDF格式。该方法适用于批量处理和自动化需求。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 本文介绍如何使用Python进行文本处理,包括分词和生成词云图。通过整合多个文本文件、去除停用词并生成词云图,展示文本数据的可视化分析方法。 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 汇编语言等号伪指令解析:探究其陡峭的学习曲线
    汇编语言以其独特的特性和复杂的语法结构,一直被认为是编程领域中学习难度较高的语言之一。本文将探讨汇编语言中的等号伪指令及其对初学者带来的挑战,并结合社区反馈分析其学习曲线。 ... [详细]
  • 本文提供了使用Java实现Bellman-Ford算法解决POJ 3259问题的代码示例,详细解释了如何通过该算法检测负权环来判断时间旅行的可能性。 ... [详细]
  • 深入探讨CPU虚拟化与KVM内存管理
    本文详细介绍了现代服务器架构中的CPU虚拟化技术,包括SMP、NUMA和MPP三种多处理器结构,并深入探讨了KVM的内存虚拟化机制。通过对比不同架构的特点和应用场景,帮助读者理解如何选择最适合的架构以优化性能。 ... [详细]
  • Codeforces Round #566 (Div. 2) A~F个人题解
    Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意:给你一个的表格,你 ... [详细]
author-avatar
温德军46867
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有