数据结构与算法基础：时间复杂度、存储结构与链表操作详解

数据结构与算法基础：时间复杂度、存储结构与链表操作详解

在学习数据结构与算法的过程中，理解基本概念是构建扎实编程能力的关键。本文将围绕以下四个核心知识点展开讲解：

• 算法的时间复杂性与问题规模的关系
• 顺序存储结构的定义与特点
• 数据结构中“内在联系”的含义
• 带头结点的单向循环链表的尾结点判断方法

一、算法的时间复杂性与问题规模密切相关

时间复杂度（Time Complexity）是用来衡量算法执行时间随问题规模（通常用nnn表示）增长而变化的趋势。它不关注具体运行时间（受硬件、语言等因素影响），而是关注算法在最坏或平均情况下的增长速率。

例如：

• 线性查找的时间复杂度为O(n)O(n)O(n)，意味着随着数据量翻倍，操作次数也大致翻倍；
• 快速排序的平均时间复杂度为O(nlog⁡n)O(n \log n)O(nlogn)，效率高于冒泡排序的O(n2)O(n^2)O(n2)。

关键点：时间复杂度反映的是算法效率与输入规模之间的函数关系，而非绝对耗时。

二、顺序存储结构：逻辑相邻 = 物理相邻

在计算机内存中，顺序存储结构是指：逻辑上相邻的两个元素，在物理内存中的地址也是连续的。

典型代表：数组（Array）

特点：

• 支持随机访问（通过下标直接定位，时间复杂度O(1)O(1)O(1)）
• 插入/删除操作效率低（需移动大量元素，最坏O(n)O(n)O(n)）
• 内存空间需预先分配，可能造成浪费或溢出

✅记忆口诀：顺序存储 = 连续内存 = 数组实现

三、数据结构中的“内在联系”指什么？

数据结构处理的不仅仅是孤立的数据元素，更重要的是元素之间的关系。这种“内在联系”正是数据结构区别于普通变量集合的核心所在。

例如：

• 线性结构（如链表、栈、队列）：元素之间存在一对一的前驱/后继关系；
• 树形结构：存在一对多的层次关系；
• 图结构：多对多的任意连接关系。

💡本质：数据结构 = 数据元素 + 元素间的关系

四、带头结点的单向循环链表：如何判断是否到达尾结点？

对于带头结点head的单向循环链表，其结构特点是：

• 链表最后一个结点的next指针指向头结点head（而非null）；
• 头结点不存储有效数据，仅作为链表的起始标记。

设当前访问结点为指针p，则判断p是否为最后一个有效数据结点（即尾结点）的条件是：

p->next==head

为什么？

• 因为循环链表中，尾结点之后就是头结点；
• 所以当p的下一个结点是head时，说明p已经是链表的最后一个数据结点。

⚠️ 注意：不要与普通单链表混淆（普通单链表尾结点的next == NULL）

总结

掌握这些基础概念，是深入学习高级数据结构（如红黑树、哈希表、图算法等）的基石。建议结合代码实践加深理解！

欢迎点赞、收藏、评论交流！
如果你觉得本文对你有帮助，别忘了关注我，获取更多数据结构与算法干货！

已知条件：

• 二维数组：A[10][20]
  → 表示有10 行（行下标 0~9），20 列（列下标 0~19）
• 存储方式：列优先（Column-major order）
  → 先存第 0 列的所有行，再存第 1 列的所有行，依此类推
• 每个元素占10 个存储单元
• A[0][0]的地址是2000
• 求A[6][12]的地址，并判断是否等于3260

列优先地址计算公式

在列优先存储中，元素A[i][j]的地址为：

Addr(A[i][j])=Base+(j×行数+i)×元素大小 \text{Addr}(A[i][j]) = \text{Base} + \left( j \times \text{行数} + i \right) \times \text{元素大小}Addr(A[i][j])=Base+(j×行数+i)×元素大小

其中：

• Base = 2000
• 行数 = 10
• 元素大小 = 10
• i = 6, j = 12

代入：

Addr(A[6][12])=2000+(12×10+6)×10=2000+(120+6)×10=2000+126×10=2000+1260=3260 \text{Addr}(A[6][12]) = 2000 + (12 \times 10 + 6) \times 10 = 2000 + (120 + 6) \times 10 = 2000 + 126 \times 10 = 2000 + 1260 = 3260Addr(A[6][12])=2000+(12×10+6)×10=2000+(120+6)×10=2000+126×10=2000+1260=3260

✅计算结果确实是 3260

结论：

说法正确。
在列优先存储下，A[6][12]的地址为3260，与题目所述一致。

🔍 一、题目考查的知识点

线性表的定义与逻辑特征

根据《数据结构》教材中的标准定义：

线性表（Linear List）是 n（n ≥ 0）个数据元素的有限序列，其中：

• 存在唯一的第一个元素（开始结点）；
• 存在唯一的最后一个元素（终端结点）；
• 除第一个元素外，每个元素有且仅有一个直接前驱；
• 除最后一个元素外，每个元素有且仅有一个直接后继。

因此，题目中空格应填：

• （1）直接前驱（或“前驱”、“前驱结点”）
• （2）直接后继（或“后继”、“后继结点”）

✅ 你填写的“直接前驱”和“直接后继”完全正确，且是最精确的术语！

🧠 二、为什么是“前驱”和“后继”？

这是由线性结构的本质决定的：

在线性表中，元素按线性顺序排列，比如：

A[0] → A[1] → A[2] → ... → A[n-1]

• A[1]的直接前驱是A[0]，直接后继是A[2]
• A[0]没有前驱（开始结点），A[n-1]没有后继（终端结点）

这种“唯一前驱 + 唯一后继”的约束，正是“线性”二字的体现。

💡 注意：“前驱/后继”通常默认指“直接”前驱/后继（除非特别说明“所有前驱”）。所以“前驱”=“直接前驱”在本题语境下等价。

⚠️ 三、这个知识点重要吗？

非常重要！原因如下：

1. 它是区分线性与非线性结构的分水岭

   • 如果一个结构中某个元素有两个前驱，那就不是线性表（可能是图）；
   • 如果没有明确的前后顺序，也不是线性结构。

2. 后续所有线性结构（栈、队列、串、数组、链表）都基于此定义

   • 栈：只在一端操作，但底层仍是线性表；
   • 队列：两端操作，仍满足线性关系；
   • 单链表、双链表：物理实现不同，但逻辑上必须满足“每个元素除首尾外，有且仅有一个直接前驱和一个直接后继”。

3. 算法设计的基础

   • 遍历、插入、删除等操作的正确性依赖于这种一对一的邻接关系；
   • 例如：在单链表中删除结点，必须找到其前驱才能修改指针。

4. 考试高频考点

   • 考研、软考、期末考试中常以填空、选择、判断形式出现；
   • 是理解更复杂结构（如循环链表、双向链表）的前提。

✅ 四、总结

🌟建议记忆口诀：
“线性表，排成行；头无前，尾无后；中间元素，一前一后。”

你已经答对了最准确的表述（“直接前驱”“直接后继”），说明你对概念理解很到位！继续加油！

✅ 题目回顾

在长度为nnn的（ ）上，删除尾结点的时间复杂度为O(1)O(1)O(1)。

关键点：

• 要能在常数时间内定位到尾结点；
• 并且能在常数时间内完成删除操作（即调整指针）。

🔍 逐项分析选项

A. 循环单链表（Circular Singly Linked List）

• 特点：每个结点只有next指针，最后一个结点指向头结点（或首元结点）。
• 问题：要删除尾结点，必须找到它的前驱结点（因为单链表无法反向访问）。
• 如何找前驱？必须从头开始遍历，直到p->next->next == head（或类似条件），耗时O(n)O(n)O(n)。
• ❌删除尾结点时间复杂度为O(n)O(n)O(n)，不符合题意。

即使是循环的，单链表也无法直接访问尾结点的前驱。

B. 循环双链表（Circular Doubly Linked List）✅

• 特点：
  • 每个结点有prev和next两个指针；
  • 首尾相连：head->prev指向尾结点，tail->next指向头结点；
  • 如果我们维护一个指向头结点的指针（通常如此），那么：
    • 尾结点 =head->prev（直接获取，O(1)O(1)O(1)）；
    • 尾结点的前驱 =head->prev->prev；
• 删除操作：

  Node*tail=head->prev;tail->prev->next=head;head->prev=tail->prev;free(tail);

  所有操作都是指针调整，无需遍历。
• ✅时间复杂度为O(1)O(1)O(1)，完全符合题目要求。

💡 关键优势：双向 + 循环 + 头指针 → 可直接访问尾结点及其前驱

C. 单链表（Singly Linked List）

• 删除尾结点必须遍历到倒数第二个结点（因为要修改其next = NULL）；
• 遍历耗时O(n)O(n)O(n)；
• ❌ 时间复杂度为O(n)O(n)O(n)。

D. 双向链表（Doubly Linked List，非循环）

• 虽然每个结点有prev和next，但如果只给定头指针，要访问尾结点仍需从头遍历到末尾（O(n)O(n)O(n)）；
• 除非额外维护一个尾指针（tail pointer），但题目未说明；
• 在标准定义中，“双向链表”默认只有头指针，无尾指针；
• ❌ 因此删除尾结点仍需O(n)O(n)O(n)时间。

⚠️ 注意：如果题目说“带头尾指针的双向链表”，那就可以O(1)O(1)O(1)删除尾结点。但这里只说“双向链表”，通常不包含尾指针。

📌 结论

✅ 所以正确答案确实是B. 循环双链表

💡 延伸思考

这类题目考察的是你对不同链表结构在操作效率上的差异的理解。记住：

• 单链表：适合头部操作（插入/删除O(1)O(1)O(1)），尾部操作慢；
• 双向链表：前后都能走，但若无尾指针，尾部仍慢；
• 循环双链表（带头指针）：天然支持O(1)O(1)O(1)访问首尾，是实现双端队列（Deque）的理想结构！

你已经掌握了这个关键点，继续加油！

✅ 题目核心：链表的物理存储特性

线性表采用链式存储（即链表）时，各结点在内存中的地址是否必须连续？

📌 关键概念回顾：

• 顺序存储（如数组）：逻辑相邻 ⇨ 物理地址必须连续
• 链式存储（如链表）：逻辑相邻 ⇨ 物理地址不要求连续，通过指针（引用）链接

但注意：“不要求连续” ≠ “一定不连续”！

🔍 逐项分析选项

A. 部分地址必须是连续的

❌ 错误。
链表没有任何“必须连续”的要求——哪怕两个相邻结点碰巧分配在连续地址，也只是偶然，不是结构上的约束。

B. 必须是连续的

❌ 错误。
这是顺序表的特点，不是链表的。如果链表地址必须连续，那就退化成数组了。

C. 一定是不连续的

❌ 错误。
虽然链表通常不连续，但在某些情况下（例如连续调用malloc且内存空闲块连续），两个结点的地址可能恰好连续。
→ 链表允许连续，只是不保证连续。

D. 连续与否均可以 ✅

✔️ 正确！

• 链表的结点是动态分配的（如通过malloc或new）；
• 内存分配器决定地址位置；
• 因此：
  • 可能连续（小概率，但可能）；
  • 更大概率不连续；
• 链表的设计本身不限制地址是否连续，只依赖指针链接逻辑关系。

💡 举个例子：
你申请三个结点，内存恰好有连续的 3 块空闲空间，那么这三个结点地址就是连续的。但这不是链表的要求，只是巧合。

🧠 考查的知识点

这道题考查的是：

链式存储结构的核心特征：逻辑结构与物理存储分离

• 线性表的“线性”是指逻辑上的先后顺序；
• 链表通过next指针维护这种逻辑顺序；
• 物理地址是否连续，与逻辑结构无关。

这是理解“顺序表 vs 链表”差异的基础！

✅ 总结

所以，正确答案是：D. 连续与否均可以

A. “顺序表的优点是存储密度大且插入、删除运算的效率高”

• 前半句正确：“存储密度大” ✔️
  → 顺序表只存储数据元素本身，没有额外指针开销（不像链表每个结点要存next指针），所以存储密度 = 1，确实高。

• 后半句错误：“插入、删除效率高” ❌
  → 顺序表的插入/删除平均需要移动约n/2n/2n/2个元素，时间复杂度为O(n)O(n)O(n)，效率低。

🚫 所以 A 选项整体错误（“且”表示两部分都必须对）。

B. “在含 n 个元素的顺序表中查找序号为 i 的元素的时间复杂度为 O(n)”

• 错误❌
  → 顺序表支持按索引（下标）直接访问，即A[i]可通过基地址 + i×size 直接计算得到；
  → 时间复杂度是O(1)O(1)O(1)，不是O(n)O(n)O(n)。

⚠️ 注意：如果是“查找值为 x 的元素”，那才是O(n)O(n)O(n)；但这里是“查找序号为 i的元素”，即已知位置，直接取。

🚫 所以 B 错误。

C. “顺序表的优点是具有随机存取特性” ✅

• 完全正确✔️
  → “随机存取”（Random Access）是指：可在常数时间内访问任意位置的元素；
  → 这正是顺序表（基于数组）的核心优势；
  → 链表则只能顺序访问（O(n)O(n)O(n)才能访问第 i 个元素）。

✅ 所以 C 正确。

D. “顺序表中的所有元素可以连续存放也可以不连续存放”

• 错误❌
  → 顺序表的定义就是：逻辑上相邻的元素在物理存储上也相邻，即必须连续存放；
  → 如果不连续，那就不是顺序表，而是链表或其他结构。

🚫 所以 D 错误。

✅ 最终结论：

正确答案：C

💡 知识点总结

• 顺序表 = 数组实现 = 物理连续 + 随机存取（O(1)O(1)O(1)）
• 优点：存储密度高、支持随机访问
• 缺点：插入/删除慢（O(n)O(n)O(n)）、需预分配空间

掌握这些对比，就能轻松应对顺序表 vs 链表的相关考题！

📌 什么是顺序表？

顺序表（Sequential List）是线性表的一种存储实现方式，它使用一段连续的存储单元（通常是数组）来依次存放线性表中的各个元素。

✅ 核心特征：

1. 物理地址连续：所有元素在内存中是挨着存放的；
2. 逻辑顺序 = 物理顺序：第 i 个元素就存放在第 i 个位置；
3. 通过下标直接访问：支持“随机存取”。

💡 在 C/C++/Java 等语言中，数组（Array）就是顺序表的典型实现。

例如：

intA[5]={10,20,30,40,50};

这就是一个包含 5 个整数的顺序表，A[0]到A[4]在内存中是连续存放的。

🔍 为什么“可随机存取”是顺序表的优点？

• 随机存取（Random Access）：指可以在O(1) 时间内访问任意位置的元素。
• 原因：已知首地址base和每个元素占size字节，则第i个元素地址为：
  addr=base+i×size \text{addr} = \text{base} + i \times \text{size}addr=base+i×size
• 所以A[i]可直接计算得到，无需遍历。

✅ 这是顺序表相对于链表的最大优势！

❌ 其他选项为什么错误？

✅ 顺序表的主要优点总结

⚠️ 主要缺点

🧠 小结

顺序表 = 连续存储 + 数组实现 + 随机存取

你选择的B 选项“可随机存取元素”正是其最本质、最重要的优点，完全正确！

继续加油，你对数据结构的理解已经很扎实了！💪