简介面向北邮数据结构课程第一次实验的线性表实验报告完整呈现带头结点单链表的存储结构并以代码级步骤详解头插法、尾插法、析构函数、按位/按值查找、插入、删除、遍历、获取长度及复制构造函数等核心操作逐一标注时间复杂度便于对照实现与复习。报告还包含测试main()函数的运行流程与结论帮助读者快速验证算法正确性。压缩包内为1个doc文档约6.3MB内容排版清晰既有原理示意图也有程序分析过程适合正在完成北邮实验或自学链表数据结构的学生参考。已有597人学习下载可作为撰写实验报告、理解单链表内部机制及准备上机考试的实用资料。1. 线性表实验应该怎么读这份北邮带头结点单链表报告把构造、查找、删除的坑都踩明白了数据结构的第一道坎基本都是线性表而线性表最容易让人卡住的不是“看不懂”而是“以为看懂了一写就报错”。这份北邮《数据结构实验报告实验1——线性表》选的是带头结点的单链表代码不是贴上去应付检查而是把构造头插/尾插、复制构造、析构、按值/按位查找、插入、删除、倒置这一整套都实现了并且 main() 里跑了一条能一步一步验证的测试链路。对正在做类似实验的人来说它是一份可以直接改完交作业的成品对想复习链表的人来说它的插入用了“数据覆盖”的 O(1) 技巧删除单独处理了 i1 的边界复制构造也是标准的深拷贝这几个点恰恰是新手最容易写崩的地方。把它读透比抄一遍收获大得多。2. 带头结点单链表的内存布局与构造头插、尾插和深拷贝的完整闭环2.1 头结点到底解决了什么问题单链表的结点结构并不复杂看报告里的定义templateclass T struct Node { T data; struct NodeT* next; };data 存数据next 存后继结点的地址逻辑顺序通过指针串起来。为什么实验要求里强调“带头结点”一个很现实的理由没有头结点时空表用 front NULL 表示插入、删除时都要对“第一个结点”单独写分支有了头结点front 永远指向一个不存数据的结点空表判定变成 front-next NULL所有操作对“第一个数据结点”和“中间结点”的处理逻辑完全一致。实验里把front作为私有成员所有函数都通过它找链头这也是带头结点写法比不带头结点省心的地方。这段定义里用了模板参数T意味着这个链表类不只能存 int。报告后面 main() 里写的是LinkListint换成LinkListchar、LinkListdouble甚至自定义结构体只要支持赋值和比较都能直接跑。这也是为什么很多数据结构作业要求模板化不改代码只改实例化类型。2.2 头插法与尾插法什么时候用哪种别搞反构造函数有两个版本报告里实际用的是尾插法头插法被注释掉了。先看默认的尾插法templateclass T LinkListT::LinkList(T a[], int n) { front new NodeT; // 创建头结点 NodeT* r front; // r 一直指向尾结点 for (int i 0; i n; i) { NodeT* s new NodeT; // 新结点 s-data a[i]; r-next s; // 新结点接到链尾 r s; // 尾指针后移 } r-next NULL; }// 头插法注意 i 从 n-1 倒着遍历 templateclass T LinkListT::LinkList(T a[], int n) { front new NodeT; front-next NULL; for (int i n - 1; i 0; i--) { NodeT* s new NodeT; s-data a[i]; s-next front-next; // 新结点指向原第一个结点 front-next s; // 头结点指向新结点 } }尾插法的核心是维护一个r指针每次把新结点挂在r-next再让r移到新结点上。这样数组顺序进链表顺序出{1,2,3} 打印出来就是 1 2 3。头插法每次把新结点塞在头结点后面如果按数组从 0 到 n-1 的顺序读取最后链表是逆序所以代码里用for (int i n - 1; i 0; i--)从数组尾部开始读把顺序“倒回来”。在实际工程里如果数据本身已经按某种顺序给好优先尾插如果你只是想快速构造一个链表不关心顺序头插代码更短。但很多同学在这翻车用了头插法又没注意倒序遍历打印出来发现顺序反了。这是单链表新手最容易踩的第一个坑下面避坑章还会单独讲。两个构造函数的时间复杂度都是 O(n)因为每个结点都只新造一次、挂一次。2.3 复制构造函数和析构一个建链表一个拆链表报告里的复制构造值得细看templateclass T LinkListT::LinkList(LinkList B) { NodeT* p B.Get(1); // 原链表第一个数据结点 front new NodeT; NodeT* r front; while (p) { NodeT* s new NodeT; s-data p-data; p p-next; // 原链表工作指针后移 r-next s; r s; } r-next NULL; }这是标准的深拷贝原链表每个结点都在新链表里 new 一个对应结点data 复制一份next 重新连接。为什么必须深拷贝因为如果直接用front B.front两个对象会指向同一串结点任何一个对象修改或析构另一个就悬空析构时同一段内存还会被 delete 两次程序直接崩溃。报告的 main() 里专门创建了paste_test(example)来测复制构造就是想验证这条链路是独立的。接着看析构templateclass T LinkListT::~LinkList() { NodeT* p front; while (p) { front p; // 保存当前要释放的结点 p p-next; // 先记录下一个结点地址 delete front; // 再释放当前结点 } }这里有个容易写反的顺序先把p p-next存好再去 deletefront。如果先delete front再执行p p-nextfront-next已经访问了被释放的内存属于典型的使用悬空指针。报告里把front当作移动指针用循环结束条件是p为空注意头结点也会被释放所以最后整个链表包括头结点在内全部归还给堆。时间复杂度同样是 O(n)。3. 核心操作逐个拆查找、插入、删除、倒置的代码与边界3.1 按位查找与按值查找工作指针的初始化差别很关键按位查找返回的是结点地址报告里实现成Get(int i)templateclass T NodeT* LinkListT::Get(int i) { NodeT* p front-next; // 指向第一个数据结点 int j 1; // 位置从 1 开始 while (p j ! i) { p p-next; j; } return p; // 找不到时 p 为 NULL }参数 i 是结点序号从 1 开始这是实验里默认的书写习惯。front-next指向第一个数据结点所以 j 从 1 起如果 i 等于 1循环条件j ! 1一开始就不满足直接返回第一个结点地址逻辑上自洽。如果 i 超过链表长度循环在 p 变成 NULL 时停住返回 NULL。注意 i 若传成 0 或负数j 从 1 开始条件j ! 0恒成立指针会一直走到末尾返回 NULL不会报错但结果可能不是你想要的调用前最好先判断一下 i 的范围。按值查找Locate(T x)的思路是遍历整条链找到所有 data 等于 x 的结点并输出位置templateclass T void LinkListT::Locate(T x) { NodeT* p front-next; int j 0; int k 0; while (p) { if (p-data x) { k; // 命中次数 cout 所在结点为 j 1; } j; p p-next; } if (k 0) cout 没有这个数; }这里 j 从 0 开始计数输出时用j 1所以第一次命中的结点输出位置 1。k用来记录命中了几次如果一次都没命中输出“没有这个数”。这个实现允许重复值存在比如链表里有三个 5它会连续输出三次所在结点位置。如果要在工程里用我一般会给输出加个空格或换行不然多个结果会连在一起看不太清。3.2 Insert 的“数据覆盖”技巧为什么定位后是 O(1)插入是这份报告里最有意思的地方它不是常规的“找到前驱再前插”而是用了覆盖数据域的方法templateclass T void LinkListT::Insert(int i, T x) { NodeT* p Get(i); // 先定位到第 i 个结点 if (p) { NodeT* s new NodeT; s-data p-data; // 新结点接管 p 原来的数据 s-next p-next; p-next s; p-data x; // p 的数据被 x 覆盖 cout 插入 x 到结点 i 后; } else { cout 位置错误插入失败; } }这招很巧妙。正常的前插需要找到第 i-1 个结点再把新结点挂在它后面这里改成先在第 i 个结点 p 后面插入一个新结点 s让 s 复制 p 的 data然后把 x 写进 p 的 data。最终效果是“在位置 i 插入 x原 p 的数据顺移到位置 i1”对使用者来说和传统前插的结果一模一样。代价是定位本身要调用Get(i)这是个 O(n) 的遍历。所以严格说一次 Insert 调用的总复杂度是 O(n)但函数内部从定位完成到插完只做了常数次指针修改和一次 new所以报告里写“插入操作时间复杂度 O(1)”指的是定位之后的插入动作。初学的时候很多人把这两层搞混看到书上写“链表插入 O(1)”就以为不需要找前驱实际是按位置插入就要先找位置按已知结点插入才是 O(1)。这份实验正好把这点演示出来了。3.3 删除必须拿前驱i 等于 1 时特殊处理删除函数比插入要老实得多老老实实找前驱templateclass T T LinkListT::Delete(int i) { NodeT* p front; // 默认让 p 指向头结点 if (i ! 1) p Get(i - 1); // 删除第 i 个结点找第 i-1 个结点 if (p) { NodeT* q p-next; T x q-data; p-next q-next; // 摘链 delete q; // 释放结点 return x; cout 删除结点 i 后; // 这行永远不会执行 } else { cout 位置错误,删除失败; } }删除第 i 个结点真正要改的是第 i-1 个结点的 next。所以 i 等于 1 时让 p 指向头结点 front这样p-next就是第一个数据结点可以当作“第 0 个结点”用i 大于 1 时Get(i-1)拿到前驱。这个边界处理是链表删除的标准姿势不带头结点的写法在这里就会多一个 if-else。有个小坑藏在代码里return x;后面的cout是永远执行不到的不可达代码编译器会警告但不会报错。所以 main() 里调用example.Delete(i)后屏幕上不会出现“删除结点后”的提示只会直接打印下一次的链表。你要是照着抄看到删除操作没有提示别慌这是 return 导致的问题不是链表删错了。3.4 倒置 Reverse三个指针完成就地反转倒置操作在原报告里属于“其他”但面试和考试里几乎必考templateclass T void LinkListT::Reverse() { NodeT* p front-next; NodeT* q; front-next NULL; while (p) { q p-next; // 保存下一个结点 p-next front-next; // 当前结点指向前一个结点 front-next p; // 头结点重新接上 p q; // 继续处理下一个 } }思路是把原链表拆散再用头插法重新组装。front-next NULL相当于把链表清空然后 p 从原第一个结点开始每轮先用 q 记住 p 的下一个结点再把 p 插到头结点和当前链表之间。因为每次都是从头部插入最后一轮结束时原来的尾结点变成了第一个数据结点完成倒置。整个过程中没有 new、没有 delete只是改指针所以空间复杂度 O(1)。我建议你把这段和 2.2 的头插法对着看它们本质是同一件事只要不断把结点挂到 front 后面得到的就是逆序。Reverse 只是把“创建新结点”换成了“复用旧结点”。4. main() 测试流程与运行结果一条链路把构造、拷贝、插入、删除全部验完4.1 测试流程设计为什么要按这个顺序跑报告的 main() 把测试设计成了一个顺序流程从建链表一路走到倒置中间每次操作后都重新打印链表方便对照。整体逻辑可以梳理成下面这张表步骤操作输入示例预期结果1数组初始化并尾插建链表a[10]{1..10}链表打印 1..102复制构造 paste_test 并打印无打印同样的 1..10验证深拷贝3获取链表长度无输出 104按值查找5输出“所在结点为5”5按位查找结点地址3输出第 3 个结点地址6插入位置 3值 99链表变成 1,2,99,3,...7删除位置 4链表删掉第 4 个结点8倒置输入 1链表反向打印注意它的顺序是有讲究的先测复制构造再对原链表做插入、删除、倒置。这样操作过程中paste_test一直保持最初的状态如果你在某个操作后发现 example 和 paste_test 同时变了说明复制构造没有做到深拷贝两个对象共享了内存这是非常直观的验证手段。还有一个细节藏在 main() 里按值查找和按位查找用的是同一个输入变量i。按值查找时i是“数字”按位查找时i是“位置”两者语义完全不同。第一次cin i程序把 i 当数据值交给 Locate第二次cin i又把 i 当位置号交给 Get。这种复用输入变量的写法能省变量但可读性一般容易在改测试用例时把自己绕晕。我做实验时会拆成value和pos两个变量逻辑清楚很多。4.2 system(pause) 与析构输出程序结束阶段其实有重要信息main() 最后的system(pause)是很多 Windows 下 C 实验的标配目的是防止程序运行完窗口一闪而过。但很多人忽略一点return 0;之前所有局部对象会依次析构报告里析构函数会打印“析构调用”所以程序结束时你能看到两次“析构调用”顺序是paste_test先析构example后析构。这个顺序符合 C 的规则局部对象按构造顺序的逆序析构。main() 里先构造 example再构造 paste_test所以结束前 paste_test 先析构。如果你把这段代码移植到 Linux 或 macOS 上system(pause)会报sh: pause: command not found虽然不是致命错误但很碍眼。替代方案是用cin.get()等一次回车或者干脆在 IDE 里设断点。验证完这些流程你会发现这个实验虽然基础但它把“建、查、插、删、翻转、析构”全串起来了。数据结构后面的栈、队列、二叉树很多操作的调试思路和它是相通的比如都要先在小数据上跑通流程再测边界输入。5. 避坑清单从 debug 闪现到删除越界的 5 个典型翻车点5.1 程序一闪而过加了 system(pause) 也看不到结果现象VS 里生成解决方案成功运行后窗口秒关什么都看不清。原因在 Visual Studio 中按 F5 是 Debug 模式启动如果程序正常结束控制台窗口会直接关闭。这不是代码逻辑问题只是运行环境的默认行为。解决在 main() 末尾加system(pause);再return 0;或者运行前在 main() 第一行设断点。注意system(pause)依赖 Windows 的命令解释器跨平台时换成std::cin.get();逻辑是阻塞等待一次回车输入效果类似但更干净。如果你用的是在线评测环境一般不需要也不能加 system(pause)交作业前记得删掉。5.2 模板类忘记写 编译报错报半天现象生成解决方案时报一堆错比如LinkList: missing argument list或T: undeclared identifier位置指到 main() 的对象创建行。原因这是典型的“忘记给模板类指定类型”。实验报告里明确提到主函数中创建对象时忘记加T把LinkListint example(a, n);写成了LinkList example(a, n);模板类不能像普通类那样直接作为类型名使用。解决创建对象时必须写完整模板参数比如LinkListint、LinkListchar。如果你用的编译器支持 C17理论上可以写成LinkList example(a, n);让编译器自动推导类型但实验课的老编译器不一定支持而且显式写类型在任何年份都不会出错养成这个习惯更稳。5.3 删除位置输入 11程序直接段错误崩溃现象测试条件里说“删除的结点在 1—11 中选择”但输入 11 时程序崩溃析构函数都没走到。原因链表只有 10 个数据结点。删除第 11 个结点时Get(i-1)也就是Get(10)会返回最后一个结点的地址然后q p-next是 NULL下一行q-data就是对空指针解引用属于非法访问程序直接崩。解决这是报告里测试条件和实现不一致的地方。要么把测试范围改成 1—10要么在 Delete 里加保护if (p p-next) { NodeT* q p-next; T x q-data; p-next q-next; delete q; return x; } else { cout 位置错误删除失败; return -1; // 需要给 T 一个默认值 }从那以后我写删除函数都会先确认p-next不为空再往下解引用。链表的“下一位”是否合法比数组的“下标是否越界”更难一眼看出因为编译器和调试器都不一定帮你兜底。5.4 头插法建立链表打印出来顺序是反的现象把构造函数换成头插法用同一个数组 a[10]{1,2,...,10}PrintList 打印出来却是 10 9 8 ... 1。原因头插法每次把新结点插入到当前链表的最前面这样先处理的数据会被后处理的挤到后面。如果按数组从 0 到 n-1 的顺序处理最后链表顺序和数组顺序相反。报告里的头插法源码用的是for (int i n - 1; i 0; i--)就是为了抵消这个逆序。解决两个方向你只能选一个——要么数组倒序遍历要么接受逆序结果。这个不是 bug是特性。真正要警惕的是很多网上的链表代码默认用头插法你直接拿来做“保持输入顺序”的实验就会输出一个看起来像“错了”的结果。判断链表对错时先确认构造函数是哪一种。5.5 复制构造少了深拷贝析构时 double free现象main() 里创建paste_test(example)后程序能正常打印但程序结束析构时崩溃报错指向 delete 语句。原因如果复制构造函数写的是front B.front;这类浅拷贝example 和 paste_test 两个对象的 front 指向同一串结点。main() 结束时两个对象分别调用析构同一块内存被 delete 两次第二次就是典型的 double free。有些版本在 Windows 下不一定立刻崩而是表现为“内存访问冲突”或随机异常排查起来很玄学。解决用报告里的深拷贝版本每个结点都 new 一份。如果时间紧也可以临时把析构函数里的 delete 注释掉但这只是掩盖问题交实验报告前必须恢复。我自己的习惯是写完复制构造后故意把原链表 delete 掉再看新链表能不能用能正常输出才算深拷贝过关。6. 扩展实验把固定数组改成用户输入顺便写个文件版单链表6.1 从 int a[10] 改成运行时输入报告最后写了“下一步改进将测试函数里面的数组改进让用户可以自行输入”。这个改进其实很简单用一个循环读入 n 个数据再构造链表#include iostream using namespace std; int main() { int n; cout 输入结点个数; cin n; int* a new int[n]; cout 依次输入 n 个数据; for (int i 0; i n; i) cin a[i]; LinkListint example(a, n); example.PrintList(); delete[] a; // 手动数组用完要释放 return 0; }这样实验的测试数据就不局限在 1 到 10 了随便输 5 个、20 个都能验证。注意new int[n]后面要对应delete[] a和单链表的结点释放是两个独立的内存管理逻辑漏写数组释放不会报错但不规范。代码逻辑上先把用户输入全部读进数组再把数组交给构造函数。如果不想用数组也可以直接在当前循环里尾插建链表LinkListint example; for (int i 0; i n; i) { int x; cin x; example.Insert(i 1, x); // 每次都插到末尾 }但 Insert 每次都要从头部重新定位复杂度会变成 O(n²)数据量大了之后很慢。相比之下先读数组再用构造函数尾插是 O(n) 的老实做法。6.2 文件版从文本文件读数据把结果写回文件如果想让实验更完整可以加一层文件读写把测试数据从 “手动输入” 改成 “从文件读取”。一个轻量的做法是重定向标准输入输出#include fstream int main() { ifstream fin(input.txt); int n; fin n; int* a new int[n]; for (int i 0; i n; i) fin a[i]; fin.close(); LinkListint example(a, n); example.PrintList(); // 终端显示 ofstream fout(output.txt); // 这里遍历链表把每个数据写到 fout fout.close(); delete[] a; return 0; }文件版的价值在于实验报告里的测试用例可以反复跑不用每次重敲 10 个数。而且文件输入输出的格式和你将来做课程设计、机试时的要求很接近算是提前练手。要注意ifstream和ofstream记得 close虽然程序结束时也会自动关但显式关闭是好习惯。6.3 一个让我少踩很多坑的测试习惯我后来做链表实验不再满足于“跑通 main()”而是会额外测三个特殊场景空链表、只有一个结点的链表、删除最后一个结点。空链表测 PrintList 和 GetLength 会不会崩单结点测 Reverse 和 Delete(1) 的边界删除最后一位测p-next是否为空的保护逻辑。这三个场景每个都能逼出至少一个隐藏问题比在 10 个结点的正常数据上反复跑有用得多。从那以后每次写完链表我都会强制走一遍“空表、单结点、满表、越界位置”这四个输入再交实验报告。这份北邮的实验报告本身也印证了这一点——它把基础操作都实现了但测试条件里仍然留了“删除位置 11”这种越界输入。读懂别人的代码不只是看成功路径还要看它哪里会崩、哪里不可达这些才是写代码的人真正要有的警觉。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/2 14:40:34 · 阅读 1.2k 带头结点单链表全解析：构造、插入、删除与避坑指南
简介面向北邮数据结构课程第一次实验的线性表实验报告完整呈现带头结点单链表的存储结构并以代码级步骤详解头插法、尾插法、析构函数、按位/按值查找、插入、删除、遍历、获取长度及复制构造函数等核心操作逐一标注时间复杂度便于对照实现与复习。报告还包含测试main()函数的运行流程与结论帮助读者快速验证算法正确性。压缩包内为1个doc文档约6.3MB内容排版清晰既有原理示意图也有程序分析过程适合正在完成北邮实验或自学链表数据结构的学生参考。已有597人学习下载可作为撰写实验报告、理解单链表内部机制及准备上机考试的实用资料。1. 线性表实验应该怎么读这份北邮带头结点单链表报告把构造、查找、删除的坑都踩明白了数据结构的第一道坎基本都是线性表而线性表最容易让人卡住的不是“看不懂”而是“以为看懂了一写就报错”。这份北邮《数据结构实验报告实验1——线性表》选的是带头结点的单链表代码不是贴上去应付检查而是把构造头插/尾插、复制构造、析构、按值/按位查找、插入、删除、倒置这一整套都实现了并且 main() 里跑了一条能一步一步验证的测试链路。对正在做类似实验的人来说它是一份可以直接改完交作业的成品对想复习链表的人来说它的插入用了“数据覆盖”的 O(1) 技巧删除单独处理了 i1 的边界复制构造也是标准的深拷贝这几个点恰恰是新手最容易写崩的地方。把它读透比抄一遍收获大得多。2. 带头结点单链表的内存布局与构造头插、尾插和深拷贝的完整闭环2.1 头结点到底解决了什么问题单链表的结点结构并不复杂看报告里的定义templateclass T struct Node { T data; struct NodeT* next; };data 存数据next 存后继结点的地址逻辑顺序通过指针串起来。为什么实验要求里强调“带头结点”一个很现实的理由没有头结点时空表用 front NULL 表示插入、删除时都要对“第一个结点”单独写分支有了头结点front 永远指向一个不存数据的结点空表判定变成 front-next NULL所有操作对“第一个数据结点”和“中间结点”的处理逻辑完全一致。实验里把front作为私有成员所有函数都通过它找链头这也是带头结点写法比不带头结点省心的地方。这段定义里用了模板参数T意味着这个链表类不只能存 int。报告后面 main() 里写的是LinkListint换成LinkListchar、LinkListdouble甚至自定义结构体只要支持赋值和比较都能直接跑。这也是为什么很多数据结构作业要求模板化不改代码只改实例化类型。2.2 头插法与尾插法什么时候用哪种别搞反构造函数有两个版本报告里实际用的是尾插法头插法被注释掉了。先看默认的尾插法templateclass T LinkListT::LinkList(T a[], int n) { front new NodeT; // 创建头结点 NodeT* r front; // r 一直指向尾结点 for (int i 0; i n; i) { NodeT* s new NodeT; // 新结点 s-data a[i]; r-next s; // 新结点接到链尾 r s; // 尾指针后移 } r-next NULL; }// 头插法注意 i 从 n-1 倒着遍历 templateclass T LinkListT::LinkList(T a[], int n) { front new NodeT; front-next NULL; for (int i n - 1; i 0; i--) { NodeT* s new NodeT; s-data a[i]; s-next front-next; // 新结点指向原第一个结点 front-next s; // 头结点指向新结点 } }尾插法的核心是维护一个r指针每次把新结点挂在r-next再让r移到新结点上。这样数组顺序进链表顺序出{1,2,3} 打印出来就是 1 2 3。头插法每次把新结点塞在头结点后面如果按数组从 0 到 n-1 的顺序读取最后链表是逆序所以代码里用for (int i n - 1; i 0; i--)从数组尾部开始读把顺序“倒回来”。在实际工程里如果数据本身已经按某种顺序给好优先尾插如果你只是想快速构造一个链表不关心顺序头插代码更短。但很多同学在这翻车用了头插法又没注意倒序遍历打印出来发现顺序反了。这是单链表新手最容易踩的第一个坑下面避坑章还会单独讲。两个构造函数的时间复杂度都是 O(n)因为每个结点都只新造一次、挂一次。2.3 复制构造函数和析构一个建链表一个拆链表报告里的复制构造值得细看templateclass T LinkListT::LinkList(LinkList B) { NodeT* p B.Get(1); // 原链表第一个数据结点 front new NodeT; NodeT* r front; while (p) { NodeT* s new NodeT; s-data p-data; p p-next; // 原链表工作指针后移 r-next s; r s; } r-next NULL; }这是标准的深拷贝原链表每个结点都在新链表里 new 一个对应结点data 复制一份next 重新连接。为什么必须深拷贝因为如果直接用front B.front两个对象会指向同一串结点任何一个对象修改或析构另一个就悬空析构时同一段内存还会被 delete 两次程序直接崩溃。报告的 main() 里专门创建了paste_test(example)来测复制构造就是想验证这条链路是独立的。接着看析构templateclass T LinkListT::~LinkList() { NodeT* p front; while (p) { front p; // 保存当前要释放的结点 p p-next; // 先记录下一个结点地址 delete front; // 再释放当前结点 } }这里有个容易写反的顺序先把p p-next存好再去 deletefront。如果先delete front再执行p p-nextfront-next已经访问了被释放的内存属于典型的使用悬空指针。报告里把front当作移动指针用循环结束条件是p为空注意头结点也会被释放所以最后整个链表包括头结点在内全部归还给堆。时间复杂度同样是 O(n)。3. 核心操作逐个拆查找、插入、删除、倒置的代码与边界3.1 按位查找与按值查找工作指针的初始化差别很关键按位查找返回的是结点地址报告里实现成Get(int i)templateclass T NodeT* LinkListT::Get(int i) { NodeT* p front-next; // 指向第一个数据结点 int j 1; // 位置从 1 开始 while (p j ! i) { p p-next; j; } return p; // 找不到时 p 为 NULL }参数 i 是结点序号从 1 开始这是实验里默认的书写习惯。front-next指向第一个数据结点所以 j 从 1 起如果 i 等于 1循环条件j ! 1一开始就不满足直接返回第一个结点地址逻辑上自洽。如果 i 超过链表长度循环在 p 变成 NULL 时停住返回 NULL。注意 i 若传成 0 或负数j 从 1 开始条件j ! 0恒成立指针会一直走到末尾返回 NULL不会报错但结果可能不是你想要的调用前最好先判断一下 i 的范围。按值查找Locate(T x)的思路是遍历整条链找到所有 data 等于 x 的结点并输出位置templateclass T void LinkListT::Locate(T x) { NodeT* p front-next; int j 0; int k 0; while (p) { if (p-data x) { k; // 命中次数 cout 所在结点为 j 1; } j; p p-next; } if (k 0) cout 没有这个数; }这里 j 从 0 开始计数输出时用j 1所以第一次命中的结点输出位置 1。k用来记录命中了几次如果一次都没命中输出“没有这个数”。这个实现允许重复值存在比如链表里有三个 5它会连续输出三次所在结点位置。如果要在工程里用我一般会给输出加个空格或换行不然多个结果会连在一起看不太清。3.2 Insert 的“数据覆盖”技巧为什么定位后是 O(1)插入是这份报告里最有意思的地方它不是常规的“找到前驱再前插”而是用了覆盖数据域的方法templateclass T void LinkListT::Insert(int i, T x) { NodeT* p Get(i); // 先定位到第 i 个结点 if (p) { NodeT* s new NodeT; s-data p-data; // 新结点接管 p 原来的数据 s-next p-next; p-next s; p-data x; // p 的数据被 x 覆盖 cout 插入 x 到结点 i 后; } else { cout 位置错误插入失败; } }这招很巧妙。正常的前插需要找到第 i-1 个结点再把新结点挂在它后面这里改成先在第 i 个结点 p 后面插入一个新结点 s让 s 复制 p 的 data然后把 x 写进 p 的 data。最终效果是“在位置 i 插入 x原 p 的数据顺移到位置 i1”对使用者来说和传统前插的结果一模一样。代价是定位本身要调用Get(i)这是个 O(n) 的遍历。所以严格说一次 Insert 调用的总复杂度是 O(n)但函数内部从定位完成到插完只做了常数次指针修改和一次 new所以报告里写“插入操作时间复杂度 O(1)”指的是定位之后的插入动作。初学的时候很多人把这两层搞混看到书上写“链表插入 O(1)”就以为不需要找前驱实际是按位置插入就要先找位置按已知结点插入才是 O(1)。这份实验正好把这点演示出来了。3.3 删除必须拿前驱i 等于 1 时特殊处理删除函数比插入要老实得多老老实实找前驱templateclass T T LinkListT::Delete(int i) { NodeT* p front; // 默认让 p 指向头结点 if (i ! 1) p Get(i - 1); // 删除第 i 个结点找第 i-1 个结点 if (p) { NodeT* q p-next; T x q-data; p-next q-next; // 摘链 delete q; // 释放结点 return x; cout 删除结点 i 后; // 这行永远不会执行 } else { cout 位置错误,删除失败; } }删除第 i 个结点真正要改的是第 i-1 个结点的 next。所以 i 等于 1 时让 p 指向头结点 front这样p-next就是第一个数据结点可以当作“第 0 个结点”用i 大于 1 时Get(i-1)拿到前驱。这个边界处理是链表删除的标准姿势不带头结点的写法在这里就会多一个 if-else。有个小坑藏在代码里return x;后面的cout是永远执行不到的不可达代码编译器会警告但不会报错。所以 main() 里调用example.Delete(i)后屏幕上不会出现“删除结点后”的提示只会直接打印下一次的链表。你要是照着抄看到删除操作没有提示别慌这是 return 导致的问题不是链表删错了。3.4 倒置 Reverse三个指针完成就地反转倒置操作在原报告里属于“其他”但面试和考试里几乎必考templateclass T void LinkListT::Reverse() { NodeT* p front-next; NodeT* q; front-next NULL; while (p) { q p-next; // 保存下一个结点 p-next front-next; // 当前结点指向前一个结点 front-next p; // 头结点重新接上 p q; // 继续处理下一个 } }思路是把原链表拆散再用头插法重新组装。front-next NULL相当于把链表清空然后 p 从原第一个结点开始每轮先用 q 记住 p 的下一个结点再把 p 插到头结点和当前链表之间。因为每次都是从头部插入最后一轮结束时原来的尾结点变成了第一个数据结点完成倒置。整个过程中没有 new、没有 delete只是改指针所以空间复杂度 O(1)。我建议你把这段和 2.2 的头插法对着看它们本质是同一件事只要不断把结点挂到 front 后面得到的就是逆序。Reverse 只是把“创建新结点”换成了“复用旧结点”。4. main() 测试流程与运行结果一条链路把构造、拷贝、插入、删除全部验完4.1 测试流程设计为什么要按这个顺序跑报告的 main() 把测试设计成了一个顺序流程从建链表一路走到倒置中间每次操作后都重新打印链表方便对照。整体逻辑可以梳理成下面这张表步骤操作输入示例预期结果1数组初始化并尾插建链表a[10]{1..10}链表打印 1..102复制构造 paste_test 并打印无打印同样的 1..10验证深拷贝3获取链表长度无输出 104按值查找5输出“所在结点为5”5按位查找结点地址3输出第 3 个结点地址6插入位置 3值 99链表变成 1,2,99,3,...7删除位置 4链表删掉第 4 个结点8倒置输入 1链表反向打印注意它的顺序是有讲究的先测复制构造再对原链表做插入、删除、倒置。这样操作过程中paste_test一直保持最初的状态如果你在某个操作后发现 example 和 paste_test 同时变了说明复制构造没有做到深拷贝两个对象共享了内存这是非常直观的验证手段。还有一个细节藏在 main() 里按值查找和按位查找用的是同一个输入变量i。按值查找时i是“数字”按位查找时i是“位置”两者语义完全不同。第一次cin i程序把 i 当数据值交给 Locate第二次cin i又把 i 当位置号交给 Get。这种复用输入变量的写法能省变量但可读性一般容易在改测试用例时把自己绕晕。我做实验时会拆成value和pos两个变量逻辑清楚很多。4.2 system(pause) 与析构输出程序结束阶段其实有重要信息main() 最后的system(pause)是很多 Windows 下 C 实验的标配目的是防止程序运行完窗口一闪而过。但很多人忽略一点return 0;之前所有局部对象会依次析构报告里析构函数会打印“析构调用”所以程序结束时你能看到两次“析构调用”顺序是paste_test先析构example后析构。这个顺序符合 C 的规则局部对象按构造顺序的逆序析构。main() 里先构造 example再构造 paste_test所以结束前 paste_test 先析构。如果你把这段代码移植到 Linux 或 macOS 上system(pause)会报sh: pause: command not found虽然不是致命错误但很碍眼。替代方案是用cin.get()等一次回车或者干脆在 IDE 里设断点。验证完这些流程你会发现这个实验虽然基础但它把“建、查、插、删、翻转、析构”全串起来了。数据结构后面的栈、队列、二叉树很多操作的调试思路和它是相通的比如都要先在小数据上跑通流程再测边界输入。5. 避坑清单从 debug 闪现到删除越界的 5 个典型翻车点5.1 程序一闪而过加了 system(pause) 也看不到结果现象VS 里生成解决方案成功运行后窗口秒关什么都看不清。原因在 Visual Studio 中按 F5 是 Debug 模式启动如果程序正常结束控制台窗口会直接关闭。这不是代码逻辑问题只是运行环境的默认行为。解决在 main() 末尾加system(pause);再return 0;或者运行前在 main() 第一行设断点。注意system(pause)依赖 Windows 的命令解释器跨平台时换成std::cin.get();逻辑是阻塞等待一次回车输入效果类似但更干净。如果你用的是在线评测环境一般不需要也不能加 system(pause)交作业前记得删掉。5.2 模板类忘记写 编译报错报半天现象生成解决方案时报一堆错比如LinkList: missing argument list或T: undeclared identifier位置指到 main() 的对象创建行。原因这是典型的“忘记给模板类指定类型”。实验报告里明确提到主函数中创建对象时忘记加T把LinkListint example(a, n);写成了LinkList example(a, n);模板类不能像普通类那样直接作为类型名使用。解决创建对象时必须写完整模板参数比如LinkListint、LinkListchar。如果你用的编译器支持 C17理论上可以写成LinkList example(a, n);让编译器自动推导类型但实验课的老编译器不一定支持而且显式写类型在任何年份都不会出错养成这个习惯更稳。5.3 删除位置输入 11程序直接段错误崩溃现象测试条件里说“删除的结点在 1—11 中选择”但输入 11 时程序崩溃析构函数都没走到。原因链表只有 10 个数据结点。删除第 11 个结点时Get(i-1)也就是Get(10)会返回最后一个结点的地址然后q p-next是 NULL下一行q-data就是对空指针解引用属于非法访问程序直接崩。解决这是报告里测试条件和实现不一致的地方。要么把测试范围改成 1—10要么在 Delete 里加保护if (p p-next) { NodeT* q p-next; T x q-data; p-next q-next; delete q; return x; } else { cout 位置错误删除失败; return -1; // 需要给 T 一个默认值 }从那以后我写删除函数都会先确认p-next不为空再往下解引用。链表的“下一位”是否合法比数组的“下标是否越界”更难一眼看出因为编译器和调试器都不一定帮你兜底。5.4 头插法建立链表打印出来顺序是反的现象把构造函数换成头插法用同一个数组 a[10]{1,2,...,10}PrintList 打印出来却是 10 9 8 ... 1。原因头插法每次把新结点插入到当前链表的最前面这样先处理的数据会被后处理的挤到后面。如果按数组从 0 到 n-1 的顺序处理最后链表顺序和数组顺序相反。报告里的头插法源码用的是for (int i n - 1; i 0; i--)就是为了抵消这个逆序。解决两个方向你只能选一个——要么数组倒序遍历要么接受逆序结果。这个不是 bug是特性。真正要警惕的是很多网上的链表代码默认用头插法你直接拿来做“保持输入顺序”的实验就会输出一个看起来像“错了”的结果。判断链表对错时先确认构造函数是哪一种。5.5 复制构造少了深拷贝析构时 double free现象main() 里创建paste_test(example)后程序能正常打印但程序结束析构时崩溃报错指向 delete 语句。原因如果复制构造函数写的是front B.front;这类浅拷贝example 和 paste_test 两个对象的 front 指向同一串结点。main() 结束时两个对象分别调用析构同一块内存被 delete 两次第二次就是典型的 double free。有些版本在 Windows 下不一定立刻崩而是表现为“内存访问冲突”或随机异常排查起来很玄学。解决用报告里的深拷贝版本每个结点都 new 一份。如果时间紧也可以临时把析构函数里的 delete 注释掉但这只是掩盖问题交实验报告前必须恢复。我自己的习惯是写完复制构造后故意把原链表 delete 掉再看新链表能不能用能正常输出才算深拷贝过关。6. 扩展实验把固定数组改成用户输入顺便写个文件版单链表6.1 从 int a[10] 改成运行时输入报告最后写了“下一步改进将测试函数里面的数组改进让用户可以自行输入”。这个改进其实很简单用一个循环读入 n 个数据再构造链表#include iostream using namespace std; int main() { int n; cout 输入结点个数; cin n; int* a new int[n]; cout 依次输入 n 个数据; for (int i 0; i n; i) cin a[i]; LinkListint example(a, n); example.PrintList(); delete[] a; // 手动数组用完要释放 return 0; }这样实验的测试数据就不局限在 1 到 10 了随便输 5 个、20 个都能验证。注意new int[n]后面要对应delete[] a和单链表的结点释放是两个独立的内存管理逻辑漏写数组释放不会报错但不规范。代码逻辑上先把用户输入全部读进数组再把数组交给构造函数。如果不想用数组也可以直接在当前循环里尾插建链表LinkListint example; for (int i 0; i n; i) { int x; cin x; example.Insert(i 1, x); // 每次都插到末尾 }但 Insert 每次都要从头部重新定位复杂度会变成 O(n²)数据量大了之后很慢。相比之下先读数组再用构造函数尾插是 O(n) 的老实做法。6.2 文件版从文本文件读数据把结果写回文件如果想让实验更完整可以加一层文件读写把测试数据从 “手动输入” 改成 “从文件读取”。一个轻量的做法是重定向标准输入输出#include fstream int main() { ifstream fin(input.txt); int n; fin n; int* a new int[n]; for (int i 0; i n; i) fin a[i]; fin.close(); LinkListint example(a, n); example.PrintList(); // 终端显示 ofstream fout(output.txt); // 这里遍历链表把每个数据写到 fout fout.close(); delete[] a; return 0; }文件版的价值在于实验报告里的测试用例可以反复跑不用每次重敲 10 个数。而且文件输入输出的格式和你将来做课程设计、机试时的要求很接近算是提前练手。要注意ifstream和ofstream记得 close虽然程序结束时也会自动关但显式关闭是好习惯。6.3 一个让我少踩很多坑的测试习惯我后来做链表实验不再满足于“跑通 main()”而是会额外测三个特殊场景空链表、只有一个结点的链表、删除最后一个结点。空链表测 PrintList 和 GetLength 会不会崩单结点测 Reverse 和 Delete(1) 的边界删除最后一位测p-next是否为空的保护逻辑。这三个场景每个都能逼出至少一个隐藏问题比在 10 个结点的正常数据上反复跑有用得多。从那以后每次写完链表我都会强制走一遍“空表、单结点、满表、越界位置”这四个输入再交实验报告。这份北邮的实验报告本身也印证了这一点——它把基础操作都实现了但测试条件里仍然留了“删除位置 11”这种越界输入。读懂别人的代码不只是看成功路径还要看它哪里会崩、哪里不可达这些才是写代码的人真正要有的警觉。希望帮到你。本文还有配套的精品资源点击获取