手写线性表:前言与目录
这组笔记从顺序存储写到链式存储,以 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* 的构造函数要求参数是有效的零结尾字符序列。
在原代码基础上补齐了自身元素插入、顺序串自插入、循环链表自拼接,以及临时内存与构造失败清理等边界。练习时不必逐字复现,但要保证结构、指针、边界和内存责任都正确。
目录
- 顺序表(SeqList)
- 动长数组(Vector)
- 顺序栈(ArrayStack)
- 普通顺序队列(LinearQueue)
- 循环顺序队列(CircularQueue)
- 顺序串(SeqString)
- 无头结点单链表(SinglyList)
- 带头结点单链表(SinglyListDummy)
- 带尾指针单链表(SinglyListTail)
- 无头结点循环单链表(CircularSinglyList)
- 带头结点循环单链表(CircularSinglyListDummy)
- 尾指针循环单链表(CircularSinglyListTail)
- 双向链表(DoublyList)
- 双向循环链表(CircularDoublyList)
- 链式栈(LinkedStack)
- 链式队列(LinkedQueue)
- 链式串(LinkedString)
跳转
上一个:无(子专题起点)