简介：这是一份来自北京邮电大学《数据结构》课程的线性表实验报告，面向信息与通信工程相关专业学生，系统梳理了带头结点单链表的存储结构与核心算法实现。实验报告覆盖构造函数、复制构造函数、头插法、尾插法、插入、删除、查找、获取长度、打印与析构等全部要求，并对每种操作给出分步说明、时间复杂度分析及代码逻辑梳理；此外还补充了单链表倒置操作、程序运行流程和调试问题总结。资源为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(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 = 0，p停在头结点上，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(m+n)。写在报告里时要写“每一趟比较取二者头部较小者，属于归并式扫描，没有回头比较”。用<=取 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 的返回值处理；这三个位置没问题，代码基本稳了。希望帮到你。

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