01、数据结构与算法:线性结构与存储方式

纠正“线程结构”笔误,区分逻辑关系、存储方式和多维数组的使用语义。

简明结论

不能按维度直接分类。线性结构关注元素之间的逻辑先后关系;数组、链表、栈和队列可以表达线性序列。矩阵或邻接表使用数组实现,不代表数组本身就只有一种逻辑关系。“线程结构”是历史笔误,本页改为“线性结构”。

数组一定属于非线性结构吗?

不能按维度直接分类。线性结构关注元素之间的逻辑先后关系;数组、链表、栈和队列可以表达线性序列。矩阵或邻接表使用数组实现,不代表数组本身就只有一种逻辑关系。“线程结构”是历史笔误,本页改为“线性结构”。

逻辑结构与实现不要混在一起

问题例子不应推导的结论
元素按什么关系组织序列、树、图树一定用指针实现
数据如何存储连续数组、分散节点链表逻辑上无序
对外允许什么操作栈后进先出、队列先进先出栈只能用数组实现

Java 的二维数组是数组的数组,不必假设所有行在一块连续区域;具体布局也不是算法复杂度的定义。

用一个查询问题比较实现

在有序序列 [2, 4, 7, 9] 中找 7:顺序扫描最多比较 4 个元素;二分查找需要排序和高效的按索引访问前提。不能把数组上的二分复杂度直接套到单链表上,忽略定位中点的代价。

练习时分别记录输入规模、允许的操作、最坏时间和额外空间。预期能解释为什么“逻辑上有序”不保证任意存储结构都能同样高效地二分。这里只做概念核对,未运行基准测试,也没有给出实测性能。

下一步先实现数组与链表上的查找,再讨论树与图,避免用一句“程序等于数据结构加算法”代替具体问题。

整理范围与出处

本次依据下方版本资料整理说明与示例;历史导入资料的来源状态单独列示,不将技术参考认作原作者信息。原始发布日期与地址保留。