简介这是一份来自北京邮电大学《数据结构》课程的线性表实验报告面向信息与通信工程相关专业学生系统梳理了带头结点单链表的存储结构与核心算法实现。实验报告覆盖构造函数、复制构造函数、头插法、尾插法、插入、删除、查找、获取长度、打印与析构等全部要求并对每种操作给出分步说明、时间复杂度分析及代码逻辑梳理此外还补充了单链表倒置操作、程序运行流程和调试问题总结。资源为1个doc文档压缩包体积约6.3MB内容完整、格式规范适合正在完成北邮数据结构实验、需要对照算法思路或参考报告写法的同学使用。已有597人浏览学习具有一定参考价值。通过研读此报告可更深入理解链式存储中指针移动与结点操作规律并为后续树、图等结构的实验打下基础。 “北邮 数据结构实验 线性表”在课程网站挂出来时很多人以为它是整学期最轻松的题目。真正改过这份实验报告就会知道线性表恰恰是翻车高发区顺序表插入忘了从后往前移动链表插入把指针链接顺序写反报告里的复杂度分析又分不清“移动”和“比较”。这个实验只解决一件事——把线性表的抽象结构用 C 语言落成可运行、可验证、能讲清楚的代码。它适合正在写实验报告的人也适合用 408 数据结构考研知识点复习基础的人。这篇按“选结构、写操作、查边界”的顺序展开每段都附可直接抄的代码和参数说明。2. 顺序表和链表怎么选线性表实验第一步先把结构定下来线性表实验的第一步不是写函数而是决定用顺序存储还是链式存储。同样的 insert 函数写在两种结构上完全是两套代码调试成本也不一样。北邮这类实验一般不会限定存储结构但会在报告里要求说明选型理由。我的建议是第一遍用顺序表把逻辑跑通再用链表做一遍如果你只有时间做一个按实验要求的“验证性 / 设计性”来定设计性题目优先交链表版本。2.1 顺序表的结构体设计与初始化多写一个 capacity 字段不是浪费顺序表最常见的错误写法是int arr[100]; int n;两个分离变量。这样写函数签名时要么把n单独传要么每次在函数里重新数长度边界检查无处安放。实验报告要求实现的是“线性表 ADT”结构体才是能承载 ADT 的形态。#include stdio.h #include stdlib.h #define MAX_SIZE 100 // 实验数据通常不超过 100 个元素 typedef struct { int data[MAX_SIZE]; // 数据区静态数组实现 int length; // 当前元素个数 int capacity; // 当前可容纳元素数量 } SeqList; void InitSeqList(SeqList *L) { L-length 0; L-capacity MAX_SIZE; } void PrintSeqList(const SeqList *L) { for (int i 0; i L-length; i) { printf(%d, L-data[i]); if (i L-length - 1) { printf( ); } } printf(\n); }capacity在静态数组版本里恒等于MAX_SIZE写上它看似冗余但后面如果改成动态扩容函数签名和判断逻辑都不用大改。打印函数手动控制空格而不是printf(%d , ...)是为了避免行尾出现多余空格——很多判题环境会把行尾空格判成格式错误。结构体类型用typedef定义函数里传指针而不传值是为了避免整个数组压栈复制。2.2 带头结点还是不带头结点链表初始化怎么选链表版本第一个选择题是头结点要不要。做实验我建议一律带头结点。带头结点后插入位置 1 和插入位置 n 走同一段指针逻辑不带头结点的写法删除首元节点时要额外把头指针指向第二个节点代码分支多更容易错。严蔚敏版《数据结构C语言版》里的链表基本都带头结点报告里引用也方便。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 带头结点的链表初始化 void InitLinkList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (*L NULL) { exit(1); // 分配失败直接终止比继续跑更安全 } (*L)-next NULL; // 头结点不放数据只做入口 } // 尾插法建立链表保持读入顺序 void AppendNode(LinkList L, int val) { LNode *p L; while (p-next ! NULL) { // 走到当前尾节点 p p-next; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { exit(1); } s-data val; s-next NULL; p-next s; } // 销毁链表先记 next 再 free顺序反了就是野指针 void DestroyLinkList(LinkList *L) { LNode *p *L; while (p ! NULL) { LNode *q p-next; free(p); p q; } *L NULL; }AppendNode每次从头部遍历到尾部再挂新节点单次 O(n)建含 n 个节点的表总代价 O(n^2)。实验数据规模小这样写最不容易出问题如果报告里想写得更漂亮可以维护一个尾指针tail尾插降到 O(1)。销毁函数先把p-next存进临时变量再free(p)是链表内存操作的保命习惯。另一个常见写法是头插法建表代码短但会反转输入顺序做“合并有序表”这类题时容易把输出搞反不推荐作为默认方案。2.3 顺序表和链表的边界一张表看清选型代价对比点顺序表带头结点单链表随机访问O(1)下标直接取O(n)必须从头走插入/删除O(n)主要是移动元素O(n)主要是找前驱空间连续静态分配有上限不连续每次节点 malloc调试难度数组越界容易定位指针断链定位麻烦适合实验场景数据量小、操作以查找为主需要练指针、综合题多表格里的“O(n)”看起来一样但实际开销性质不同顺序表的插入代价在元素移动链表的插入代价在指针寻址。两个复杂度写进实验报告都不能只写一个“O(n)”要写“移动 n-i 个元素”或“遍历到第 i-1 个节点”。这也是 408 数据结构考研代码题喜欢追问的地方。选型时如果实验给定了数据规模按“随机访问多选顺序表、插入删除多选链表”判断即可。到这里结构定下来下一步才是把操作函数写对。3. 插入、删除、查找与合并线性表实验的核心操作一次写对确定结构之后实验主体就是把线性表的标准操作一个个实现。这一章按顺序表、链表两条线分别给代码最后落到合并和去重这两个高频综合题。每个函数都带返回值和参数说明因为实验报告里“失败处理”和“边界检查”也是打分点不能只贴一个能跑的主函数。3.1 顺序表的插入、删除与查找先把位置边界背下来顺序表最常错的是位置边界。教材习惯位置从 1 开始数组下标从 0 开始这个转换关系要在代码注释里写清楚答辩时也会被问到。// 在顺序表 L 的位置 pos从 1 开始插入 val int SeqInsert(SeqList *L, int pos, int val) { if (L-length L-capacity) { return 0; // 表满插入失败 } if (pos 1 || pos L-length 1) { return 0; // 位置越界允许在表尾追加 } for (int i L-length - 1; i pos - 1; i--) { L-data[i 1] L-data[i]; // 从最后一个元素开始后移 } L-data[pos - 1] val; L-length; return 1; }两个判断顺序建议固定为“先判满再判位置”。位置上限是length 1而不是length因为插在最后一位后面是合法操作对应“表尾追加”。移动方向必须从后往前若从前往后移data[pos-1]的新值还没写入原值就被后一个位置覆盖了。返回值用 0/1 表示失败/成功比void函数更适合报告里的错误处理说明。// 删除顺序表位置 pos 的元素用 val 带回被删值 int SeqDelete(SeqList *L, int pos, int *val) { if (pos 1 || pos L-length) { return 0; // 空表或越界都不能删 } *val L-data[pos - 1]; for (int i pos; i L-length; i) { L-data[i - 1] L-data[i]; // 从被删位置的下一个开始前移 } L-length--; return 1; }删除的移动方向是从前到后被删元素的值通过val指针传出调用方可以接着用这个值。注意删除的合法位置是 1 到length插入是 1 到length 1两个边界不要写成一样的。// 按值查找返回第一个等于 val 的位置从 1 开始找不到返回 0 int LocateSeq(const SeqList *L, int val) { for (int i 0; i L-length; i) { if (L-data[i] val) { return i 1; } } return 0; }这里返回 0 表示失败和插入删除函数的返回约定一致。因为位置 1 对应下标 0所以返回i 1时不会产生“下标 0 对应返回 0”的歧义。如果实验要求返回所有匹配位置可以改成把位置写进一个结果数组。3.2 单链表的插入、删除与查找先连后断顺序不能反链表插入和删除的核心是“先连后断”新节点先接到后一个节点上再改前一个节点的 next。顺序反了前一个节点的 next 先被改动后一个节点就从链表里丢了。这个错不会立刻崩溃但打印链表时会发现后半段不见了。// 带头结点链表在位置 pos从 1 开始插入 val int LinkInsert(LinkList L, int pos, int val) { LNode *p L; // p 从头部开始 int j 0; while (p ! NULL j pos - 1) { // 找第 pos-1 个节点 p p-next; j; } if (p NULL || j ! pos - 1) { return 0; // 位置越界 } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) { return 0; } s-data val; s-next p-next; // 先让新节点指向后继 p-next s; // 再让前驱指向新节点 return 1; }为什么p从L开始而不是从L-next开始因为当pos 1时j 0p停在头结点上p-next指向原来的第一个节点新节点正好插在头部。查找循环的判断条件是p ! NULL而不是p-next ! NULL这样位置超尾时会停到空指针上再统一判定。// 删除带头结点链表位置 pos 的节点用 val 带回被删值 int LinkDelete(LinkList L, int pos, int *val) { LNode *p L; int j 0; while (p-next ! NULL j pos - 1) { // 找第 pos-1 个节点 p p-next; j; } if (p-next NULL || j ! pos - 1) { return 0; } LNode *q p-next; // 被删节点 *val q-data; p-next q-next; // 跨过被删节点 free(q); // 释放后不要再解引用 q return 1; }删除的循环条件用p-next ! NULL因为删除时必须保证 p 后面还有节点。极端情况是删除最后一个节点p停在倒数第二个节点q是最后一个p-next q-next把尾指针置 NULL正确。free(q)之后不要再去访问q-data这是 C 语言实验里段错误的经典来源。// 按值查找找到返回节点指针找不到返回 NULL LNode *LocateLink(LinkList L, int val) { LNode *p L-next; while (p ! NULL) { if (p-data val) { return p; } p p-next; } return NULL; }链表查找没有下标便利只能从首元节点开始逐个走。返回指针比返回位置更常用因为拿到节点后可以直接做插入删除不用再遍历一遍。这里的L-next跳过了头结点因为头结点不存数据。3.3 合并有序表和去重实验报告最爱考的派生操作线性表实验的最后一题经常是“将两个有序线性表合并成一个有序线性表”或“删除链表中重复元素”。这两个题都能用前面基础函数实现但这样复杂度不理想面试时会被追问。// 把有序表 A 和 B 合并到 C结果仍有序 int MergeSeqList(const SeqList *A, const SeqList *B, SeqList *C) { if (A-length B-length C-capacity) { return 0; // 容量不够返回失败 } int i 0, j 0, k 0; while (i A-length j B-length) { if (A-data[i] B-data[j]) { C-data[k] A-data[i]; } else { C-data[k] B-data[j]; } } while (i A-length) { // A 还剩元素 C-data[k] A-data[i]; } while (j B-length) { // B 还剩元素 C-data[k] B-data[j]; } C-length k; return 1; }三个 while 循环把两个表各扫描一遍每个元素只访问一次时间复杂度 O(mn)。写在报告里时要写“每一趟比较取二者头部较小者属于归并式扫描没有回头比较”。用取 A 的先走值相等的元素按原顺序接过来了这是“稳定合并”。// 删除有序链表中的连续重复值只保留一个 void DedupSorted(LinkList L) { LNode *cur L-next; // 从首元节点开始 if (cur NULL) { return; // 空表直接返回 } while (cur-next ! NULL) { if (cur-data cur-next-data) { LNode *dup cur-next; // 重复节点是后继 cur-next dup-next; free(dup); } else { cur cur-next; // 不重复才往前走 } } }这个循环的精髓是“删除时不移动 cur不重复才让 cur 前进”。比如1, 2, 2, 2, 3第一次cur停在 2删除第一个重复 2 后cur仍然指向剩下的 2下一次再删除第二个 2然后cur前进到 3。如果把删除分支里也写成cur cur-next就会漏删。原地去重的空间复杂度是 O(1)这一点值得写进实验报告。4. 北邮线性表实验避坑边界、指针和报告里的五个雷区代码写出来和跑通过是两回事。下面几条来自我批改和复审这份数据结构实验报告时常见的返工原因按“现象 → 原因 → 解决”列出。前三条是代码问题后两条是报告和判题问题每一项都会影响最终分数。4.1 malloc 之后不判空本地能跑OJ 上随机崩溃现象链表程序在本地开发环境里一切正常换到在线判题环境后在初始化时偶发段错误多跑几次结果还不一样。原因malloc分配失败时返回 NULL。很多代码直接使用返回的指针不检查就执行(*L)-next NULL对 NULL 解引用必然崩溃。本地机器内存大分配失败概率低但判题环境内存紧张或同一时间跑多个测试用例时这种问题就暴露了。解决每次malloc后都判断。初始化函数里写if (*L NULL) { exit(1); }插入函数里写if (s NULL) { return 0; }。前者让程序快速失败后者让操作返回失败而不是带病运行。报告中这条可以写进“异常处理”一节这是加分项不是可有可无。4.2 插入位置上限写错表尾追加永远失败现象向顺序表表尾追加元素的测试用例一直报插入失败调试发现pos length 1时返回 0。原因插入位置合法范围是 1 到length 1不少写法把判断写成了pos length。这个错误在普通插入时不一定暴露因为练习里很少插到表尾恰恰是建表那一题常用表尾追加方式构造一旦写入length 1就翻车。解决把两个边界条件固定成顺口溜写在注释里——“插入允许表尾后一位删除只能是已存在的位”。代码上if (pos 1 || pos L-length 1) return 0; // 插入 if (pos 1 || pos L-length) return 0; // 删除测试代码里专门加一组边界用例空表、pos 1、pos length 1、pos length 2四种情况都要验证。4.3 scanf 格式串里的换行陷阱输入卡住不动现象用scanf(%d\n, n);读第一个整数时终端里敲完回车没反应还得再敲一次才继续。原因scanf 格式串里的\n会被当成“跳过空白”处理。scanf 读完数据后看到格式串里的\n就去不断吸收后续的换行和空格直到读到下一个非空白字符为止。这导致它比人类输入多等一步表现出来就是输入卡住。解决scanf 的格式串只写%d、%c这类转换说明不要自带空白符。需要读带空格的字符串时用fgets读完后配合sscanf解析。实验报告里如果贴了带\n的 scanf答辩被问“为什么要卡一下”就很难解释。4.4 free 之后指针没置空删除节点后二次释放现象链表删除函数free(q)之后紧接着又对q-next赋值程序表面不报错但第二次删除同一位置时崩溃或者析构时重复 free。原因free只释放内存没有把指针变量置 NULL。如果代码里又用了q就是访问已释放内存如果后来再 free 同一个指针属于 double free运行时错误信息经常指向不明确的位置查起来很费劲。解决free(q);之后补q NULL;。开发阶段建议每次 free 后都写一句置空虽然不影响运行但能防止后续误用。另一个检查技巧把链表的销毁函数单独拆开测试连续销毁两张表不崩溃才算内存逻辑过关。4.5 复杂度分析照抄教材顺序表删除写成 O(1)现象实验报告里写“删除操作时间复杂度 O(1)”答辩时被问“删最后一个元素移动了几个元素”答不上来。原因教材说过尾删除有特殊情形但有些人把特例写成通解。顺序表删除的平均移动次数是(n - 1) / 2时间复杂度 O(n)链表删除要遍历找前驱同样是 O(n)只不过常数不同。真正能做到 O(1) 的是“给定节点指针时删除其后继”这是题目特定条件不能直接下结论。解决报告里不要只写 O(n)要写完整推导。顺序表写“删除位置 i 的元素需要移动 n - i 个元素平均 O(n)”链表写“删除位置 i 的节点需要从头查找第 i - 1 个节点比较 i - 1 次平均 O(n)”。这样写既严谨也让判卷人知道你算过而不是抄结论。最后提醒交代码前把调试用的 printf 删掉输出格式严格按题目要求控制空格和换行格式问题有时比功能问题扣得还狠。5. 从能跑到能答辩线性表实验的验证与一个值得做的升级代码能跑样例不等于能处理边界。我一般会写一个不依赖手工输入的检查函数把空表、表尾、表头、重复值这些用例一次性跑完。用断言当迷你测试用例比手工一遍遍敲输入更可靠实验报告“测试情况”一节也能直接引用。#include assert.h void SelfCheck() { SeqList L; InitSeqList(L); int v; assert(SeqInsert(L, 1, 10) 1); assert(SeqInsert(L, 2, 20) 1); assert(SeqInsert(L, 3, 30) 1); assert(SeqInsert(L, 5, 40) 0); // 越界插入应失败 assert(SeqDelete(L, 2, v) 1); assert(v 20); assert(L.length 2); }静态数组写完及格后把顺序表改成动态扩容是性价比最高的加分点。每次表满时把容量翻倍新容量 旧容量 × 2用realloc搬家。连续插入 n 个元素的均摊复杂度仍是 O(n)这是摊还分析在 408 里也是高频考点。if (L-length L-capacity) { int newCap L-capacity * 2; int *newData (int *)realloc(L-data, newCap * sizeof(int)); if (newData NULL) { return 0; // 扩容失败原表仍然可用 } L-data newData; L-capacity newCap; }realloc搬家后旧指针可能还在原地址也可能已经换到新地址唯一能信任的是它返回的新指针。所以一定要先把返回值存到临时变量成功后再更新L-data——这就是我自己的血泪经验也是动态扩容写法里最容易翻车的位置。答辩时被问“为什么插入次数很多也不卡”把摊还分析和realloc临时变量这两件事讲清楚就够了。我现在拿到别人写的顺序表代码第一反应一定是看插入的移动方向、边界条件和 realloc 的返回值处理这三个位置没问题代码基本稳了。希望帮到你。本文还有配套的精品资源点击获取