数组一定属于非线性结构吗?
不能按维度直接分类。线性结构关注元素之间的逻辑先后关系;数组、链表、栈和队列可以表达线性序列。矩阵或邻接表使用数组实现,不代表数组本身就只有一种逻辑关系。“线程结构”是历史笔误,本页改为“线性结构”。
逻辑结构与实现不要混在一起
| 问题 | 例子 | 不应推导的结论 |
|---|---|---|
| 元素按什么关系组织 | 序列、树、图 | 树一定用指针实现 |
| 数据如何存储 | 连续数组、分散节点 | 链表逻辑上无序 |
| 对外允许什么操作 | 栈后进先出、队列先进先出 | 栈只能用数组实现 |
Java 的二维数组是数组的数组,不必假设所有行在一块连续区域;具体布局也不是算法复杂度的定义。
用一个查询问题比较实现
在有序序列 [2, 4, 7, 9] 中找 7:顺序扫描最多比较 4 个元素;二分查找需要排序和高效的按索引访问前提。不能把数组上的二分复杂度直接套到单链表上,忽略定位中点的代价。
练习时分别记录输入规模、允许的操作、最坏时间和额外空间。预期能解释为什么“逻辑上有序”不保证任意存储结构都能同样高效地二分。这里只做概念核对,未运行基准测试,也没有给出实测性能。
下一步先实现数组与链表上的查找,再讨论树与图,避免用一句“程序等于数据结构加算法”代替具体问题。
整理范围与出处
本次依据下方版本资料整理说明与示例;历史导入资料的来源状态单独列示,不将技术参考认作原作者信息。原始发布日期与地址保留。