03-09 11:37 李群 山东航空学院 在数据结构课程中提问：

广义表与线性表本质区别

从逻辑结构角度阐述广义表与线性表的本质区别，并说明这种差异对存储实现的影响。

• 07-19 22:43 孙宝林

  本质结构差异线性表：一维单线结构，每个结点仅有一组前驱、后继，不可嵌套。广义表：支持嵌套子表，元素能是子表，具备层级递归结构。存储影响线性表：可连续数组随机存取，或普通链表存数据；广义表：只能分原子、表结点用链式递归存储，无法直接随机下标访问，指针占用更多内存。

查看全部(193条)

03-09 11:37 李群 山东航空学院 在数据结构课程中提问：

广义表还是表？

通过学习，你觉得广义表是不是普通意义的线性表，它具备哪些特殊性质？

• 07-19 22:43 孙宝林

  广义表并不是普通意义上的线性表。普通线性表的元素只能是不可再分的原子数据，属于线性结构；广义表元素既可以是原子，也可以是另一个子表，整体是非线性的递归结构。

查看全部(90条)

03-09 11:37 李群 山东航空学院 在数据结构课程中提问：

怎样存储高维矩阵才能节省空间？

在许多科学计算中，会用到高维矩阵，在计算机内存储它们时如何能有效节省空间，你有什么方法？

• 07-19 22:42 孙宝林

  稀疏压缩（零元多）COO/CSR 格式，仅存非零元素与下标
  精度量化（容忍小幅误差）FP64 降为 FP16/INT8，缩减字节开销
  张量分解（低秩结构数据）CP、Tucker 分解，以小规模因子还原张量
  结构专属优化对称矩阵只存单侧三角；对角矩阵仅存对角线
  分块分片（体量超限）切块按需载入内存，冷数据存入磁盘

查看全部(89条)

03-08 18:47 李群 山东航空学院 在数据结构课程中提问：

在C/C++语言里有没有办法不用指针做出链表呢？

• 07-19 22:39 孙宝林

  可以，借助数组模拟链表实现，不用原生指针。用两个数组，一个存数据，一个存下一个节点在数组中的下标，通过下标模拟指针指向。本质是静态链表，开辟一段连续数组空间来存放链表节点，用数组下标代替指针地址完成节点跳转、插入删除操作。优点：避开指针操作，适合不熟练指针的场景；缺点：数组长度固定，空间分配

查看全部(138条)

03-08 18:47 李群 山东航空学院 在数据结构课程中提问：

顺序表or链表

顺序表和链表到底孰强孰弱，你是如何看待这个问题的？

• 07-19 22:38 孙宝林

  一、核心底层原理
  1. 顺序表（数组实现，连续内存）
  数据在内存中一段连续整块空间存放，通过下标偏移直接寻址。
  2. 链表（单 / 双 / 循环链表，离散内存）
  每个节点 = 数据域 + 指针域，节点分散在内存各处，靠指针串联，无连续空间。
  二、关键性能维度对比
  1. 随机访问（按下标查找元素）
  
  顺序表极强：时间复杂度 O（1）公式：元素地址 = 首地址 + 下标 × 单个元素大小，一步定位。
  链表极弱：时间复杂度 O（n）必须从表头顺着指针逐个遍历到目标下标，无法跳跃访问。
  
  
  场景结论：频繁随机读取、遍历查询优先顺序表。
  
  2. 中间 / 头部插入、删除元素
  
  顺序表极差：O（n）插入 / 删除后，后方所有元素必须整体向后 / 向前平移，数据量大时代价极高。仅尾部追加性能优秀（容量充足时 O（1））。
  链表极强：O（1）（找到目标节点后）只需要修改相邻节点的指针指向，不需要移动任何数据；代价仅在于：查找目标节点仍要遍历 O（n）。
  
  
  场景结论：频繁在任意位置增删数据优先链表。
  
  3. 内存空间开销
  
  顺序表：仅存储数据，无额外开销；但会存在预留闲置容量（扩容预留空间浪费）。
  链表：每个节点多存 1~2 个指针（额外内存开销），数据量越大，内存损耗越明显。例：存 int 数据，顺序表 4 字节 / 元素；单链表 8~12 字节 / 元素。
  
  4. 扩容机制
  
  顺序表：固定容量，满了需要重新申请更大连续内存 + 拷贝全部数据，一次性开销大；
  链表：按需分配节点，不存在整体扩容拷贝，新增节点随时申请小块内存。
  
  5. 缓存命中率（计算机底层硬件优化）
  CPU 缓存会预加载连续相邻内存的数据：
  
  顺序表连续存储，遍历数据时缓存命中率极高，实际运行速度理论值更快；
  链表节点离散分布，遍历时频繁缓存失效，即使理论复杂度相同，实际速度往往更慢。
  
  6. 支持逆序、快速取尾节点
  
  顺序表：直接下标取尾 O（1）；
  单链表：取尾必须遍历全表 O（n）；双向循环链表可优化到 O（1），但额外增加指针开销。
  
  三、优缺点汇总
  顺序表优点
  
  随机访问快，支持下标；
  内存紧凑，无指针额外开销；
  遍历缓存友好，连续读取速度快；
  尾部插入高效。
  
  顺序表缺点
  
  头部 / 中间增删需要大量平移元素；
  需要连续大块内存，大数据量易内存分配失败；
  扩容存在数据拷贝开销，会预留空闲空间浪费内存。
  
  链表优点
  
  任意位置插入删除仅改指针，无数据移动；
  动态分配内存，无需预先开辟整块空间；
  无容量上限限制，不会预留闲置内存。
  
  链表缺点
  
  无法随机访问，查找下标必须遍历；
  每个节点带指针，内存开销更大；
  离散存储，遍历缓存效率低；
  单链表反向遍历困难。
  
  四、分场景选型（核心判断标准）
  选顺序表（数组、ArrayList、Vector）
  
  业务以查询、随机读取为主，增删操作很少；
  数据量稳定，很少频繁扩容；
  只在尾部追加、删除；
  需要大量连续遍历，追求缓存效率；
  内存资源充足，可接受少量预留空间。典型例子：数组、List 存固定配置、栈、哈希表底层数组。
  
  选链表（LinkedList、单 / 双向链表）
  
  需要频繁在头部、中间插入删除；
  数据动态变化剧烈，无法预估容量；
  内存碎片化严重，拿不出连续大块内存；
  几乎不用下标随机访问，只顺序遍历。典型例子：队列、LRU 缓存、多项式存储、操作系统内存管理、链表实现栈。
  
  五、怎么看待 “孰强孰弱”？
  
  不存在绝对更强的数据结构，性能由业务操作决定拿随机访问场景比，顺序表碾压链表；拿中间频繁插入场景比，链表完胜顺序表，脱离使用场景对比没有意义。
  
  现代工程中顺序表使用远多于链表硬件缓存机制大幅放大顺序表优势；日常业务大多是查多改少，尾部操作居多。比如 Java 中 ArrayList 使用频率远高于 LinkedList，绝大多数场景 LinkedList 性能反而更差。
  
  链表的不可替代场景集中在底层系统应用开发很少手动写链表，但操作系统内核、内存分配、进程队列、数据库索引、图邻接表等底层组件高度依赖链表，它解决了 “连续内存不足” 的痛点。
  
  二者可以互补融合很多高级结构结合两者优点：
  
  分块链表（块内顺序表，块间链表）；
  跳表（链表 + 索引，实现近似 O（logn） 随机查找，Redis 底层）。
  
  
  
  一句话总结
  
  读多、尾部增删、随机下标访问 → 顺序表更强；
  频繁中间 / 头部增删、内存不连续、容量不可预测 → 链表更强；抛开业务场景谈谁更强，都是片面结论。

查看全部(108条)

03-08 18:47 李群 山东航空学院 在数据结构课程中提问：

在线性表中查找数据可以有多快？

如果有一线性表，我们要在其中查找一个与给定值相同的元素，时间复杂度是多少？你认为最快能有多快呢？

• 07-19 22:36 孙宝林

  普通未排序线性表顺序查找：时间复杂度0（n）；最好单次命中0（1），但最坏必须遍历全部。有序数组二分查找：0（logn），是线性顺序存储结构能达到的最优查找复杂度。

查看全部(198条)

03-04 17:33 李群 山东航空学院 在数据结构课程中提问：

何为优秀的程序？

你认为什么样的程序称得上优秀，有哪些评判标准？

• 07-11 15:05 张佳宇

  优秀的程序首先要完整实现预定功能，全部用例都可以正常通过，并且拥有较低的时间与空间复杂度，运行效率高。代码格式工整，变量和函数命名规范，关键位置添加必要注释，可读性强，他人可以轻松看懂逻辑。程序鲁棒性强，能够应对异常输入，不会轻易报错崩溃。代码模块化程度高，消除重复冗余内容，复用性好，方便后续功能扩展与修改维护，在运行性能和开发维护成本之间做到合理平衡。

查看全部(53条)

03-04 17:33 李群 山东航空学院 在数据结构课程中提问：

有多少个不同值？

编写算法，求一个整型数组中有多少个不同值。如：数组{5，3，5，2，6，1，7，3，5}，不同的值有6个。你有什么办法解决该问题，能不能找到比较高效的算法？

• 07-11 15:04 张佳宇

  第一种方法是先将数组整体排序，再从头到尾遍历，相邻元素不相等就计数加一，整体时间复杂度为O（nlogn），可以原地运行节省额外空间，第二种是效率更高的哈希集合法，依次遍历每一个数组元素，判断元素是否存在于集合中，如果不存在就将元素存入集合并且数量加一，已经存在则直接跳过，该算法平均时间复杂度只有O（n），遍历仅执行一次，是解决这个问题最优的常用方案，以题目数组为例，最终统计出集合内元素总数就是不同数值的个数。

查看全部(56条)

03-04 17:33 李群 山东航空学院 在数据结构课程中提问：

说说你在编程中使用过的或者了解的一些算法

有很多经典算法，就像计算机科学里的颗颗明珠，相信大家在学习和使用程序设计语言时已经有所应用。你使用过哪些算法或者了解哪些，跟大家一起分享一下。

• 07-11 15:04 张佳宇

  我学习并实践过不少经典算法，排序算法里有冒泡排序、插入排序和快速排序，冒泡排序通过相邻元素逐一比较交换来整理数据，代码简单易懂，适合小规模数据，快速排序选定基准元素划分区间，排序效率更高，是日常处理大量数据常用的方法，查找算法里运用过顺序查找和二分查找，二分查找依托有序数组不断缩小检索范围，查找速度远快于顺序遍历，除此之外还接触了递归算法，利用递归思想求解阶乘、遍历线性表，依靠函数自身调用简化循环逻辑，这些算法覆盖了数据整理与元素检索的常用场景，也是编写程序时优化代码效率的基础。

查看全部(55条)

03-04 17:33 李群 山东航空学院 在数据结构课程中提问：

怎样修炼自己的编程能力？

通过本章的学习，结合你的编程学习之路，谈谈你是怎样或者打算怎样提高自己的编程能力。

• 07-11 15:04 张佳宇

  在学习数据结构之后，我明白编程不能只满足功能实现，还要兼顾程序的时间与空间效率，接下来我会坚持多加动手练习，日常独立完成算法习题，循序渐进巩固链表、查找、排序等基础知识，锻炼自身逻辑思维，写完代码后主动复盘优化复杂度，同时尝试独立编写小型程序项目，把学到的数据结构知识运用到实际代码中，遇到难题先自主思考，尝试构思多种解题方案，长期坚持积累代码量，一步步打磨自己的编程能力。

查看全部(58条)

查看更多