企业官网建设流程全解析

简介：北邮数据结构第一次实验的线性表实验报告，面向正在学习数据结构、需要完成单链表实验或准备课程验收的本科生。内容围绕带头结点的单链表展开，从实验要求、存储结构讲起，说明结点由数据域与指针域两部分构成、逻辑次序与物理次序可以不一致；随后逐一拆解头插法、尾插法、析构函数、按位查找、按值查找、插入、删除、遍历、求长度、复制构造函数及倒置操作，给出每步指针修改说明与 O(n)、O(1) 的时间复杂度分析，并附测试 main() 函数的流程示意、测试条件、运行结果与调试问题记录，可直接对照撰写报告或复盘链表实现。压缩包内含 1 个 doc 文件，约 6.3MB，已按实验报告格式排版，目前已有 602 人学习。

1. 一次实验报告能当脚手架用：带头结点单链表要先想清楚接口

带表头的单链表，是数据结构课里线性表那一章的第一个作业，也是很多人第一次亲手在堆上分配、连接、再释放结点的地方。这份资源就是围绕它的一份完整实验报告加源码：结点模板、空表构造、头插与尾插建表、复制构造、按位置插入删除、按位与按值查找、求长度、遍历打印、析构、倒置，外加一个把这些接口全部跑一遍的 main()。它适合两类人：正在做数据结构实验、需要一份能对着调的实现；以及早就写过链表、但想回头把指针边界和内存释放重新捋顺的从业者。线性表看着简单，真正让人翻车的从来不是思路，而是 i 的取值、front 和 front->next 的区别、以及 delete 到底写在哪一行。下面按“结构定死 → 建表 → 增删查 → 释放与倒置 → 排错 → 验证”的顺序拆开讲。

2. 结点模板与两种建表方式：头插、尾插差在哪一行

先把结构定死，再谈算法。链表这类东西最怕边写边改结构，结点里多一个域、类里少一个私有指针，后面十几个成员函数全要跟着动。所以第一步不是写 Insert，而是把 Node 和 LinkList 的骨架敲定，让编译器和自己都清楚“谁是头结点、谁是第一个元素结点、i 从几开始”。

2.1 为什么头结点的 data 域空着不用

报告里的结构是struct Node { T data; Node<T>* next; }，类里只有一个私有成员Node<T>* front指向头结点。头结点的 data 域不存有效数据，它的 next 才指向第一个真正的元素结点。这个设计的价值在于把“空表”和“非空表的插入删除”统一了：不用特判“表为空时插入第一个元素”和“删除最后一个元素”这两种边界，代码量能少三分之一。

代价也很明确：所有遍历都要从front->next开始，而不是从front开始。这一条是后面所有打印、求长度、按位查找出错的根源，写的时候脑子里要一直挂着。

#include <iostream> using namespace std; template <class T> struct Node { T data; // 数据域；头结点的这个域不用 Node<T>* next; // 指针域，指向后继结点 }; template <class T> class LinkList { public: LinkList(); // 只建头结点，空表 LinkList(T a[], int n); // 尾插建表 LinkList(const LinkList<T>& B); // 复制构造，深拷贝 ~LinkList(); // 析构，逐个 delete void PrintList() const; int GetLength() const; Node<T>* Get(int i); // 返回第 i 个元素结点的地址 void Locate(T x); // 按值查找，打印所有命中位置 bool Insert(int i, T x); // 在第 i 个位置插入 bool Delete(int i, T& out); // 删除第 i 个，值通过 out 带出 void Reverse(); private: Node<T>* front; // 头结点 };

几个参数和返回值上的选择值得说明。Get返回Node<T>*而不是T，因为调用方既要取值也要判断“位置合不合法”，返回指针时 nullptr 天然承担了“非法/越界”的语义，比返回一个T()默认值再额外加一个状态位干净。Insert和Delete返回bool是同一个道理：位置越界是常规情况，不该用异常或者 exit 处理。Delete把被删的值通过引用参数带出，是因为 C++ 里没法同时返回“成功与否”和“被删元素”两个值。

i的语义全篇统一为“第几个元素结点”，从 1 开始计数，合法范围是[1, 表长]。插入操作的合法范围更宽一点，是[1, 表长 + 1]，因为可以插在表尾之后。这个约定写在类注释里，后面所有函数都照着它来，不要有的地方从 0 开始、有的地方从 1 开始，那是自找麻烦。

2.2 尾插法：一个 r 指针把建表压到 O(n)

尾插法的核心是维护一个尾指针r，让它始终指向当前最后一个结点。每来一个新元素，就把新结点挂到r->next上，然后r后移。因为r一直在尾部，不需要每次都从头找尾，整个建表过程是 O(n) 而不是 O(n²)。

template <class T> LinkList<T>::LinkList(T a[], int n) { front = new Node<T>; // 头结点，data 域不用 Node<T>* r = front; // r 始终指向当前尾结点 for (int i = 0; i < n; ++i) { Node<T>* s = new Node<T>; s->data = a[i]; r->next = s; // 挂到当前尾部 r = s; // 尾指针后移 } r->next = nullptr; // 收尾必须写，new 不会替你把指针清零 }

r->next = nullptr这一行是整个函数里最关键的一句，也是最容易被漏掉的一句。new Node<T>只保证分配了内存，next域里是上一次这块内存被用过的残留值，不是 nullptr。漏写的话，最后一个结点的 next 指向一块随机地址，PrintList 会在打印完所有数据后继续往后走，运气好崩在访问违例，运气不好走进别的对象的内存里，输出一堆看着像正常数据的垃圾值——这种 bug 现场极其迷惑。

提示：验证这一步最简单的方法是在建表后立刻调用GetLength()，如果返回值不等于 n，先查r->next有没有置空。

头插法和尾插法的时间复杂度都是 O(n)，空间复杂度也都是 O(n)，差别只在“插入位置”和“输出顺序”这两件事上。头插法每次插在头结点之后，所以先插入的元素会被后来的元素挤到后面，最终顺序和插入顺序相反；尾插法插在末尾，顺序和插入顺序一致。

2.3 头插法：数组得倒着扫才是等价的

报告里两种建表方式都给了，头插法那段注释掉的实现有一个细节很多人第一次看会愣一下：它是从n - 1倒着扫到0的。原因很直接——头插会把顺序反转一次，要想最终链表里是a[0], a[1], ..., a[n-1]的顺序，就得先插a[n-1]，最后插a[0]。

template <class T> LinkList<T>::LinkList(T a[], int n) { front = new Node<T>; front->next = nullptr; for (int i = n - 1; i >= 0; --i) { // 倒着扫，最终顺序才是正序 Node<T>* s = new Node<T>; s->data = a[i]; s->next = front->next; // 新结点指向原来的第一个元素 front->next = s; // 头结点改指新结点 } }

这两行指针操作的顺序不能反。如果先写front->next = s再写s->next = front->next，第二句读到的是s自己，s->next就指向了自己，链表立刻成环，PrintList 会无限循环打印同一个值。这种错误在单步调试时看起来每一步都“正常”，只有打印时才会暴露。

选哪个看输入形态。从文件或数组顺序读入、并且希望链表顺序与输入一致，用尾插。做“把一串数据逆序处理”的任务，可以直接用头插配正序扫描，省掉一次反转。

2.4 复制构造函数：不写深拷贝，析构时会炸

默认的拷贝构造函数是逐成员复制，对LinkList来说就是把front指针复制一份，于是两个对象指向同一条链。第一个对象析构时把所有结点 delete 掉，第二个对象析构时再 delete 一遍同一批地址，这就是典型的 double free，在 Linux 上多半直接 abort，在 Windows 上可能只是弹个堆损坏的框，表现很不稳定。

template <class T> LinkList<T>::LinkList(const LinkList<T>& B) { front = new Node<T>; front->next = nullptr; Node<T>* r = front; // 用 B.front->next 而不是 B.Get(1)：Get 不是 const 成员，传 const 引用调不了 for (Node<T>* p = B.front->next; p != nullptr; p = p->next) { Node<T>* s = new Node<T>; s->data = p->data; r->next = s; r = s; } r->next = nullptr; }

参数用const LinkList<T>&而不是报告里写的LinkList&，一是避免不必要的拷贝，二是让编译器帮你保证构造函数里不会改到源对象。既然参数是 const 的，就不能在里面调用非 const 的成员函数Get，所以遍历直接用B.front->next起步——同一个类的不同实例之间可以访问私有成员，这一点在 C++ 里是合法的。

复制构造函数里同样要写r->next = nullptr，理由和尾插法一致。另外注意源链表为空表时循环一次都不进，front->next保持 nullptr，这个分支自然就对，不需要特判。

3. Get、Insert、Delete、Locate：位置语义和边界条件怎么定

这四个函数是链表接口里出错率最高的部分，原因不在于算法难，而在于每一个都隐含了“i 合不合法”的假设，而调用方往往假设函数会自己处理。把边界条件写进函数体内、用返回值表达，比在 main 里到处 if 要稳得多。

3.1 Get(i) 返回地址，是后面所有接口的地基

Get是唯一直接做“走到第 i 个结点”这件事的函数，Insert、Delete 都可以复用它。它的正确性直接决定后两个函数的表现。

template <class T> Node<T>* LinkList<T>::Get(int i) { if (i < 1) return nullptr; // 位置从 1 开始，非法直接返回 Node<T>* p = front->next; // 从第一个元素结点开始，不是头结点 int j = 1; while (p != nullptr && j < i) { // 用 < 而不是 != p = p->next; ++j; } return p; // i 超出表长时 p 自然为 nullptr }

循环条件用j < i而不是报告里写的j != i，是一个不大但很实际的改动。用!=时，如果调用方传了 0 或负数，j从 1 开始递增永远不可能等于它，循环会一直走到p为空才退出，虽然最终也返回 nullptr，但白白走完整条链；更糟的是有些调用方会把“返回 nullptr”理解成“没找到”，而没区分“i 非法”和“链表本身为空”。用<之后，i 非法时循环一次都不进，直接返回首元素结点或 nullptr，行为可预期。

参数取值范围i ∈ [1, 表长]，超出返回 nullptr。这个约定要在类里写清楚，因为Insert和Delete都依赖它。

3.2 Insert 的“数据搬家”写法：省一次指针操作，代价是什么

报告里给的插入实现和教科书常见的写法不一样：它不是找到第 i-1 个结点然后在其后插入，而是找到第 i 个结点，把新结点插在它后面，然后把第 i 个结点原来的数据挪到新结点、把 x 写进第 i 个结点。

template <class T> bool LinkList<T>::Insert(int i, T x) { Node<T>* p = Get(i); // 找到第 i 个结点 if (p == nullptr) return false; Node<T>* s = new Node<T>; s->data = p->data; // 老数据挪到新结点 s->next = p->next; p->next = s; // 新结点接在 p 后面 p->data = x; // p 本身的 data 换成 x return true; }

这个写法的效果是“x 出现在第 i 个位置，原来的第 i 个元素被挤到第 i+1 个位置”，语义上完全正确，而且省去了“找前驱”的步骤，插入本身是 O(1)。代价有两个：一是多了一次T的拷贝，如果 T 是大结构体，成本不可忽略；二是如果 T 是不可拷贝构造的类型，这条路直接走不通。常规做法还是找前驱，代码更长但通用性更好：

template <class T> bool LinkList<T>::Insert(int i, T x) { if (i < 1) return false; Node<T>* p = front; // 从头结点出发，目标是走到第 i-1 个 for (int k = 1; k < i && p != nullptr; ++k) p = p->next; if (p == nullptr) return false; // i 超出 表长+1 Node<T>* s = new Node<T>; s->data = x; s->next = p->next; p->next = s; // 新结点接在 p 后面 return true; }

第二种写法的合法范围是i ∈ [1, 表长 + 1]，因为从front出发、走i-1步，i 等于表长加 1 时 p 正好停在最后一个元素结点上，挂在它后面就是表尾。注意循环的边界是k < i而不是k <= i，差一个等号就会走到第 i 个结点、变成“插在第 i 个之后”，位置整体错一位。

注意：两种写法的返回值都要判。实验里最容易出现的情况是输入位置 11（表长 10 加 1）时，第一种写法走的是Get(11)返回 nullptr 的分支，插入直接被拒绝，而调用方还以为是插入成功只是看不出来。

3.3 Delete 的摘链顺序：先保存、再摘、后释放

删除操作有三个动作必须按顺序做：保存被删结点的值、修改前驱的 next 指针把结点从链上摘下来、delete 掉结点。顺序反了会读到已释放的内存，或者把整条链截断。

template <class T> bool LinkList<T>::Delete(int i, T& out) { if (i < 1) return false; Node<T>* p = front; // 从头结点出发 for (int k = 1; k < i && p != nullptr; ++k) p = p->next; // 走到第 i-1 个 if (p == nullptr || p->next == nullptr) return false; // i 越界 Node<T>* q = p->next; // q 指向真正要删的结点 out = q->data; // 先把值取出来 p->next = q->next; // 摘链，前驱跳过 q delete q; // 最后释放 return true; }

报告里那版 Delete 用的是if (i != 1) p = Get(i - 1);的写法，i=1 时 p 停在 front 上，这是对的；但它的判空只判了p，没判p->next。当 i 恰好等于“表长 + 1”时，Get 返回 nullptr 被挡住了，可如果 i 传成 0 或者负数，Get返回的也是 nullptr，分支同样被挡住——看起来没问题。真正的漏洞出现在 i 合法但 p->next 为空的情形，比如删除表尾之后再删一次同一个位置，q = p->next就是空指针，q->data立刻崩溃。所以p == nullptr || p->next == nullptr这两个条件必须同时判。

还有一个细节：报告那版代码在return x;之后还跟了一句cout，编译器多半会给个“不可达代码”的警告。这类残留语句不影响运行，但会让人误以为进度输出没生效，调试时白白浪费时间去查它。

3.4 Locate 按值查找：命中多个位置时输出要能读

按值查找最容易被忽略的是重复元素。报告里的实现用j计数、命中时打印j + 1，但计数器自增在if外面，而且没有 break，命中多个位置时会把数字连成一串，比如两个命中在第 2 和第 4 位，屏幕上显示的是24，看起来像“第 24 个结点”。

template <class T> void LinkList<T>::Locate(T x) { bool found = false; int j = 1; for (Node<T>* p = front->next; p != nullptr; p = p->next, ++j) { if (p->data == x) { if (found) cout << ","; // 多个位置之间加分隔 cout << j; found = true; } } if (!found) cout << "未找到"; }

位置计数从 1 开始，和Get的语义保持一致；循环变量p从front->next起步，避免把头结点那个无效的 data 域也拿去比较。如果业务上只关心第一次出现的位置，命中后直接 return 并返回位置即可，函数签名改成返回 int 更合适。

把这张表贴在类的注释里，写 main 测试的时候照着边界值各跑一遍，比随机输入靠谱得多。测试用例至少要有：空表上删、表尾删、i=1 删、i=表长+1 插、i=0 插这五种。

4. 析构与倒置：两段最容易写出悬垂指针的遍历

这两段代码有一个共同点：都要在一次遍历里同时操作两个以上的指针，而且都不能“先移动再使用”。它们也是整个实验里最难通过肉眼 reviewing 发现问题的部分，因为错误在编译期完全不可见。

4.1 析构函数的遍历顺序，决定了会不会 double free

析构函数要做的事很简单：从头结点开始，把每一个结点 delete 掉。难点在于 delete 掉当前结点之后，你就再也读不到它的 next 了，所以下一个结点的地址必须在 delete 之前保存到局部变量里。

template <class T> LinkList<T>::~LinkList() { Node<T>* p = front; while (p != nullptr) { Node<T>* q = p->next; // 先把下一个存下来 delete p; // 再释放当前 p = q; // 最后移动工作指针 } front = nullptr; // 防止外部拿到悬垂头指针 }

报告里的写法是front = p; p = p->next; delete front;，效果上也是安全的，因为它同样在 delete 之前读到了 next。但这种写法顺手改掉了成员front，如果之后有人在析构函数体后面加了别的东西、或者这个类被继承、派生类析构时还想访问front，就会拿到一个已经失效的指针。用局部变量q保存、最后统一把front置空，是更稳的写法。

如果顺序写成delete p; p = p->next;，就是典型的释放后使用。这类 bug 的行为极其诡异：在 Debug 配置下可能因为堆填充而立刻崩，在 Release 下可能读到的还是原来的值，程序一切正常；换一台机器、换一个编译器版本，就又崩了。这种“时好时坏”的现象是排查成本最高的一类。

4.2 Reverse 的三指针接力：为什么不能先移动再改指针

链表倒置的标准做法是把原链上的结点一个个摘下来，用头插法重新挂到 head 后面。关键在于每次摘结点之前，必须先把它的后继保存下来，否则改成头插之后就找不到原来的下一个了。

template <class T> void LinkList<T>::Reverse() { Node<T>* p = front->next; // 从第一个元素结点开始 front->next = nullptr; // 先把头结点后面清空，作为新链的起点 while (p != nullptr) { Node<T>* q = p->next; // 保存后继，这是唯一的“后悔药” p->next = front->next; // 头插第一步：新结点指向当前第一个 front->next = p; // 头插第二步：头结点改指新结点 p = q; // 前进到原来的下一个 } }

q = p->next这一句是整段代码的保险。如果省掉它，直接写p->next = front->next; front->next = p; p = p->next;，那么最后一句读到的p->next已经在上一句里被改成了front->next，p会退回链表中部甚至形成环，循环永远退不出来。

front->next = nullptr这一句同样不能省。它把头结点和原来的链断开，既让第一次头插有正确的“链尾”可指，也避免了旧链残留导致的结构混乱。倒置操作本身不分配新结点，空间复杂度 O(1)，时间 O(n)。

提示：验证倒置是否正确，最笨也最有效的办法是连续调用两次 Reverse，然后打印，结果必须和原始链表逐元素相同。任何差一个元素、多一个元素的问题都会在这里暴露。

4.3 带头结点这件事，什么时候值得

带表头不是唯一的写法，也不是所有场景都更优。它的收益在插入删除的边界处理上：不用特判空表、不用特判删除首元结点时头指针要改，所有位置的操作都能统一成“找到前驱、改两个指针”。它的成本是一次额外的new、一份额外的内存，以及所有遍历都要从front->next起步这个容易忘的约定。

如果这门课或者这个项目的接口明确要求“不带头结点”，那就在每个函数里老老实实把首元结点的情况单独拎出来处理，尤其是删除第一个元素时必须回写头指针——这是不带头结点的版本里最常漏的一步，漏了之后链表头还指着已被释放的结点，后续所有操作都在访问野指针。

5. 五个翻车现场：现象、原因和改法

链表相关的问题有个共同特点：编译期全过，运行期随机出结果。下面这几条是我在照着这份报告复现、以及在别的项目里带人写链表时反复见到的，按“现象 → 原因 → 解决”列出来，出问题的时候可以按顺序对照。

一、生成成功，程序一闪而过

现象：编译零警告，双击 exe 或者直接运行，窗口瞬间关闭，什么输出都看不到。原因是main正常返回后控制台窗口随进程退出而销毁，程序其实已经跑完了，只是输出没来得及看。报告里最后加system("pause")就是为了停住窗口。更稳的替代是在 IDE 的调试模式下运行，或者在main末尾加一句cin.get()；system("pause")依赖 Windows 的 cmd 环境，换到 Linux 或某些精简终端上会直接报sh: pause: command not found。

二、LinkList example(a, n);编译报错，一堆“未定义的符号”

现象：类模板定义得好好的，一写对象就开始报错，提示LinkList缺少模板参数。原因是类模板在实例化时必须给出具体类型，不能像普通类那样直接声明对象。改成LinkList<int> example(a, n);就通了。同一类问题还会出现在函数传参和成员声明上：Node* p应写成Node<T>* p，少一个<T>就是一个错误。这类错误编译器提示往往指向模板定义处而不是使用处，第一次遇到容易看错地方。

三、打印链表时多一个或者少一个元素，甚至打印出很大的随机数

现象：输入 10 个元素，打印出来 11 个，最后一个是个莫名其妙的大整数。原因是尾插法的构造函数漏了r->next = nullptr，最后一个结点的 next 是new分配到的残留值，遍历时被当成“还有下一个”。另一种变体是遍历循环条件写成了while (p->next != nullptr)但初始值给了p = front->next，这样会漏掉最后一个元素。解决方式是统一遍历模板：for (Node<T>* p = front->next; p != nullptr; p = p->next)，从首元结点开始、判当前结点是否为空，两头都不容易错。

四、程序跑完在退出时崩溃，或者析构时崩在 delete 上

现象：main 里所有输出都正常打印，最后“析构调用”也打出来了，然后进程异常退出。原因多半是复制构造函数没写（或者是浅拷贝），两个LinkList对象共享同一条链，第一个析构后第二个再删一遍。另一种可能是析构函数里顺序写反成了先 delete 后取 next。解决方式是先确认有没有自定义的复制构造函数和赋值运算符，有的话检查它们是否真的做了深拷贝；再看析构循环是否严格按“存后继 → delete 当前 → 移动”的顺序。

五、Insert 和 Delete 传不同位置时，行为不一致

现象：插在第 3 个位置正常，插在表尾之后直接没反应；删除第 1 个元素正常，删最后一个元素崩。原因是Insert的合法上界是表长加 1，Delete的合法上界是表长，两者差一位，很多人在实现时把两个函数的上界搞混了，或者 Get 的返回值判空覆盖了另一层逻辑。解决方式是把第 3 章那张合法范围表写进注释，并且给每个函数补上边界测试：i=0、i=1、i=表长、i=表长+1 四个值各跑一遍。

6. 用不变量把链表验一遍：三个检查比肉眼盯输出可靠

靠打印结果肉眼比对，只能发现问题，定位不了问题。更省时间的做法是在类里加一个不变量检查函数，每次插入、删除、倒置之后都调一次，让错误在第一时间暴露在真正出错的那一步上，而不是在几十行输出之后才看到异常。

template <class T> bool LinkList<T>::CheckInvariant(int expectLen) const { int n = 0; for (Node<T>* p = front->next; p != nullptr; p = p->next) { if (++n > expectLen) return false; // 走出的结点数超过预期，说明链上有环 } return n == expectLen; // 实际长度必须和预期一致 }

这个函数靠一个expectLen参数来校验两件事：链上没有环（否则计数会超过预期），且结点总数等于预期。预期长度由调用方维护，比如建表前数组长度是 10，插入后是 11，删除后回到 10，倒置不改变长度。任何一个操作之后CheckInvariant返回 false，就说明上一步操作把链改坏了，直接去查那一步的指针顺序，不用管后面的代码。

基于它还能顺手做两个更强的验证，一个是倒置两次是否还原，一个是复制构造出来的对象与原对象逐元素相等且修改其一不影响另一个：

LinkList<int> a(arr, 10); LinkList<int> b(a); // 复制构造 a.Reverse(); a.Reverse(); // 倒置两次应还原 cout << (a.CheckInvariant(10) ? "OK" : "BROKEN") << endl; b.Insert(1, 999); // 改 b 不应影响 a cout << (a.CheckInvariant(10) ? "OK" : "BROKEN") << endl;

这三个检查写在一个 test 函数里，十来行代码，覆盖了构造函数、复制构造、倒置和长度维护四条最容易出错的路径。比起每次改完代码手动输入一串数字看输出，这套自检在改动的第一时间就给出结论。

我自己的习惯是从那以后，任何带指针的结构，不管是一个链表、一棵树还是一张图的邻接表，都先写这样一个不变量检查再写业务逻辑——写完 Insert 就跑一次，写完 Delete 再跑一次，而不是攒到最后一起调试。链表这种结构最难受的地方在于，一个指针写错，问题往往在几十行之后才显现，到那时候现场早就没了。先把检查写好，等于给自己留了一份随时可用的后悔药。希望帮到你。

本文还有配套的精品资源，点击获取