加载中

手写数据结构·线性表00:前言与目录

手写线性表:前言与目录

这组笔记从顺序存储写到链式存储,以 CODE_PRACTICE 2 中的实现为基础,整理成便于复习和闭卷重写的类定义。每篇正文只保留数据结构名称、代码、工程细节与前后篇跳转。

所有位置参数统一从 0 开始。插入位置允许等于当前长度,删除与元素访问则要求严格小于长度。operator[] 不检查越界,提供 at() 的结构由 at() 检查;非法插删通常返回 false,空结构的首尾访问抛出 out_of_range。

代码按 C++11 及以上编写,默认已引入 using namespace std;,因此只展示必要的模板声明和类定义,结点类型放在类内;省略头文件、命名空间外壳和使用示例。实际编译按用到的标识补上 <cstddef>、<stdexcept>、<utility>、<memory> 和 <limits>。容量模板使用 size_t,带固定槽位数组的表、栈和队列要求容量大于零。

先确定状态变量和不变量,再写核心操作。每次检查空表、单结点、首尾位置、满容量和清空后重用;循环结构还要检查回绕或重新成环。凡是 new 都要明确释放责任,数组用 delete[],结点用 delete。本组链表、链栈和链队列禁止复制;Vector 与原代码已实现深拷贝的 LinkedString 保留复制和移动接口。

泛型数组实现面向可默认构造、可赋值的普通值类型,适合 int、string 等练习;它们以逻辑长度管理有效区,删除并不立即销毁数组槽位对象。串按 char 字节处理,长度不是 UTF-8 中文字符数。接受 const char* 的构造函数要求参数是有效的零结尾字符序列。

在原代码基础上补齐了自身元素插入、顺序串自插入、循环链表自拼接,以及临时内存与构造失败清理等边界。练习时不必逐字复现,但要保证结构、指针、边界和内存责任都正确。

目录

  1. 顺序表(SeqList)
  2. 动长数组(Vector)
  3. 顺序栈(ArrayStack)
  4. 普通顺序队列(LinearQueue)
  5. 循环顺序队列(CircularQueue)
  6. 顺序串(SeqString)
  7. 无头结点单链表(SinglyList)
  8. 带头结点单链表(SinglyListDummy)
  9. 带尾指针单链表(SinglyListTail)
  10. 无头结点循环单链表(CircularSinglyList)
  11. 带头结点循环单链表(CircularSinglyListDummy)
  12. 尾指针循环单链表(CircularSinglyListTail)
  13. 双向链表(DoublyList)
  14. 双向循环链表(CircularDoublyList)
  15. 链式栈(LinkedStack)
  16. 链式队列(LinkedQueue)
  17. 链式串(LinkedString)

跳转

下一个:顺序表

上一个:无(子专题起点)

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/3305a1a0/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议