简介这是面向南京邮电大学《数据结构》课程实验一的完整实验报告资源主题围绕线性表的基本运算及多项式的算术运算。资源适合正在学习顺序存储与链接存储、顺序表与单链表操作的本科生也可作为复习数据结构考点或准备实验报告的参考素材。包内共1个docx文档大小约444KB报告详细给出了顺序表的初始化、查找、插入、删除、输出、销毁以及带表头单链表的对应操作核心代码并附有算法流程图与时间复杂度分析同时针对一元多项式实现了创建、输出、加法、乘法等运算包含完整可读的C语言源码和实验结论。已有772人学习浏览尤其能帮助计算机专业学生理解线性表在实际问题中的应用与代码落地。1. 线性表两种存储结构的选择逻辑与场景判断去年帮一个学弟调这份实验他卡在“顺序表和链表都实现了却不知道为什么要写两遍”上。这个问题的答案其实就是这份实验报告真正的考点线性表两种存储结构分别是内存连续与内存不连续的典型它们的基本运算查找、插入、删除在时间复杂度上有着本质差异——顺序表随机访问是 O(1) 但插入删除要搬移数据链表的随机访问是 O(n) 但插入删除只需要改指针。多项式运算之所以放到这个实验里是因为一元多项式天然适合用链表存储每一项包含系数和指数项数不确定、排序频繁用顺序表会因为中间插入和删除导致大量数据搬移而链表的离散存储结构恰好对症。这篇博文把顺序表、带表头链表和多项式加乘的完整实现路径拆开讲适合正在做数据结构课设的学生也适合面试前复习线性表底层逻辑的开发者。2. 顺序表基本运算的实现细则2.1 顺序表初始化的隐藏约束顺序表的核心是预分配一块连续内存用n记录当前长度用maxLength记录容量上限。初始化时最容易踩的坑是忘记设置容量上限或者在插入时不做空间检查——这份实验的原始代码里就明确写了如果传入的数据个数大于申请的空间会产生报错。我一般会这样写初始化#include stdio.h #include stdlib.h #define MAX_LENGTH 100 // 预分配容量 typedef struct { int* element; // 存储元素的数组指针 int n; // 当前表长 int maxLength; // 最大容量 } SeqList; // 初始化分配空间并设置初始表长 Status InitList(SeqList* L, int maxLen) { L-element (int*)malloc(maxLen * sizeof(int)); if (!L-element) { return ERROR; // 内存分配失败 } L-n 0; L-maxLength maxLen; return OK; }初始化里有个细节分配空间后务必检查malloc的返回值。VC 6.0 的老环境下内存分配失败通常返回NULL不做检查的话后续操作会直接段错误。参数maxLen是表的容量上限n是当前元素个数二者不等价后者会随着插入删除动态增减。2.2 查找、插入与删除的三种典型写法查找操作简单因为顺序表支持随机访问直接按下标取元素即可时间复杂度 O(1)// 按下标查找结果通过 x 返回 Status Find(SeqList* L, int i, int* x) { if (i 0 || i L-n - 1) { return ERROR; // 判断下标越界 } *x L-element[i]; // 直接通过下标访问 return OK; }插入操作要复杂一些。核心思路是从最后一个元素开始从后往前搬移给待插入位置腾出空间// 在第 i 个元素后面插入 x即插入到下标 i1 处 Status Insert(SeqList* L, int i, int x) { int j; if (i -1 || i L-n - 1) // 判断下标越界 return ERROR; if (L-n L-maxLength) // 判断空间是否已满 return ERROR; for (j L-n - 1; j i; j--) { L-element[j 1] L-element[j]; // 从后往前搬移 } L-element[i 1] x; // 新元素放入腾出的位置 L-n; // 表长加 1 return OK; }注意这里的边界判断i -1是合法的因为i -1表示在表头插入而j i这个循环条件意味着如果插入位置是表头i -1所有元素都要后移。如果是表尾插入i n-1循环一次都不执行直接赋值。删除操作正好相反从前往后搬移把目标位置之后的元素逐个前移覆盖掉。这三种操作合在一起形成了顺序表的完整生命周期初始化负责分配空间查找利用随机访问优势插入删除通过数据搬移维护连续性。时间复杂度上查找 O(1) 是顺序表的招牌插入删除平均要搬移 n/2 个元素所以是 O(n)。2.3 顺序表什么时候该用、什么时候该弃根据这份实验报告的实验结果顺序表的优势集中在查多改少的场景。比如存放一台机器的配置历史读取频繁、很少增删顺序表就比链表合适。但如果你的数据有明显的时间排序特征、经常在中间插入删除搬移代价就很高。有一个常见的误用是在需要频繁头插的场景还坚持用顺序表——每一次头插都是 O(n) 搬移此时应该果断换链表。判断标准很朴素看你操作的是数据还是位置。按下标访问就选顺序表按指针追踪就选链表。3. 带表头单链表的核心操作实现3.1 表头结点一个哨兵换来的边界简化链表的定义在实验报告里已经给出headerList结构体用head指针指向表头结点用n记录长度。这里的关键设计是“带头结点”——头结点本身不存数据它的link指向第一个真正存储数据的结点。为什么要多浪费一个结点看下面的例子如果链表为空head-link指向NULL如果不带头结点空链表时head本身就是NULL。插入删除时带头结点的版本可以统一用同一套逻辑处理头部和中间位置不带头结点的版本则要单独写if (head NULL)这种分支。这类空间换代码复杂度的手法在很多教材的数据结构设计里都叫哨兵结点。这份实验把带头结点的链表单独列为一节就是为了让你体会这个设计带来的操作统一性。typedef struct Node { int element; // 结点的数据域 struct Node* link; // 结点的指针域 } Node; typedef struct { struct Node* head; // 表头结点不存数据 int n; // 链表长度 } ListHeader; // 初始化带头结点的空链表 Status InitList(ListHeader* h) { h-head (Node*)malloc(sizeof(Node)); if (!h-head) return ERROR; h-head-link NULL; // 头结点的指针域置空 h-n 0; return OK; }初始化时头结点的link置空很重要。如果不做这个操作head-link会指向一块随机的内存后续遍历链表时会发生不可预料的访问异常。3.2 插入与删除两步改写指针带头结点链表的插入核心是找到目标位置的前驱结点然后修改两个指针// 在下标 i 之后插入 x第 -1 个位置即头结点表示头插 Status Insert(ListHeader* h, int i, int x) { Node* p, * q; int j; if (i -1 || i h-n - 1) return ERROR; p h-head; // 从头结点开始找 for (j 0; j i; j) { p p-link; // 循环结束后 p 指向第 i 个结点 } q (Node*)malloc(sizeof(Node)); // 生成新结点 if (!q) return ERROR; q-element x; q-link p-link; // 新结点先连上后继 p-link q; // 前驱再连上新结点 h-n; return OK; }这里的两步指针操作顺序是固定的必须先让新结点q的link指向前驱p原来的后继再让p-link指向q。如果顺序反了p-link先被改写原来后继结点的地址就丢了链表在这里断开。这类问题在链表面试里常被叫做“指针重连顺序错误”。删除操作逻辑上是插入的逆操作找到待删结点p的前驱q然后让q-link跳过p直接指向后继最后释放p的空间Status Delete(ListHeader* h, int i) { int j; Node* p, * q; if (!h-n) return ERROR; // 空表不能删除 if (i 0 || i h-n - 1) return ERROR; q h-head; for (j 0; j i; j) { q q-link; // 循环结束后 q 指向第 i 个结点的前驱 } p q-link; // p 指向待删除结点 q-link q-link-link; // 跳过 p free(p); // 释放 p 的空间 h-n--; return OK; }这段代码的一个细节是循环条件j i而不是j i。因为删除需要找前驱插入时需要让 p 指向第 i 个结点删除时 q 只需要走到第 i 个结点的前驱。下标语义上的细微差别如果没想明白调试的时候很容易出现删错结点。3.3 链表操作的时间复杂度与缓存开销链表的查找、插入、删除在涉及到位置时需要遍历找前驱所以都是 O(n)。但在已知前驱结点的前提下插入删除是纯指针操作不搬移数据——这是链表的理论优势。实际运行时要注意的是链表结点是malloc逐个分配的内存地址不像顺序表那样连续遍历时 CPU 缓存命中率通常低于顺序表。在小数据量场景下顺序表可能反而更快数据量到几万甚至几十万时链表在插入删除场景下的优势才真正体现。做实验测试时不要把两组数据直接对比绝对值要观察它的增长趋势是否是线性的。4. 一元多项式的算术运算与链表应用4.1 用链表表达多项式的本质多项式3x^5 2x^2 1可以抽象成若干组“系数 指数”的二元组。用链表存储时每个结点就是一个项coef存系数exp存指数link指向下一项。实验报告里要求指数按递减顺序存储这个约定很重要它直接简化了加法和乘法的实现——类似归并的合并逻辑。typedef struct PNode { int coef; // 系数 int exp; // 指数 struct PNode* link; // 指向下一项 } PNode; typedef struct { struct PNode* head; // 表头结点exp 置为 -1 作结束标记 } Polynominal;表头结点的exp设为 -1利用“合法指数必然不小于 0”这个性质把 -1 当作链表的结束哨兵。遍历多项式时判断p-exp 0就继续等于 -1 就终止。这和带头结点链表是同一个思路的不同变体——哨兵不只是简化边界判断还可以携带业务语义。4.2 创建多项式头插法还是尾插法创建多项式的常规做法是先给头结点分配空间并设置exp -1然后循环读入每一项的系数和指数按指数递减的顺序插入。因为录入时通常不会正好按指数由高到低输入需要插入时找到合适的位置// 按指数递减顺序插入一项 void InsertTerm(Polynominal* poly, int coef, int exp) { PNode* p poly-head; PNode* newNode; // 找到第一个指数小于新项的结点 while (p-link ! NULL p-link-exp exp) { p p-link; } // 如果指数相同的项已存在合并系数 if (p-link ! NULL p-link-exp exp) { p-link-coef coef; if (p-link-coef 0) { // 合并后系数为 0删除该项 PNode* tmp p-link; p-link tmp-link; free(tmp); } return; } // 指数不重复插入新结点 newNode (PNode*)malloc(sizeof(PNode)); newNode-coef coef; newNode-exp exp; newNode-link p-link; p-link newNode; }这段代码隐含了两个操作逻辑指数相同就合并系数合并后系数为 0 就删除结点。如果不做系数为 0 的处理后续加法和乘法都会出现多余的零项输出结果不干净比较两个多项式时也会因为零项的存在导致结果不稳定。4.3 多项式加法游标扫描与同类项合并加法的思路用一句话概括两个多项式都按指数递减排列依次比较当前两项的指数。如果p-exp q-exp说明 q 的这一项在结果里暂无人能合并直接保留如果相等系数相加如果p-exp q-exp说明 p 的这一项要插入到结果链表中。实验报告里的Add函数是把结果写入qx并修改 qx 本身void Add(Polynominal* px, Polynominal* qx) { PNode* p px-head-link; // p 指向 px 的第一项 PNode* p1 px-head; PNode* q qx-head-link; // q 指向 qx 的第一项 PNode* q1 qx-head; while (p-exp 0) { while (p-exp q-exp) { // 跳过 qx 中指数较大的项 q1 q; q q-link; } if (p-exp q-exp) { // 指数相等系数相加 q-coef p-coef; if (q-coef 0) { // 相加后系数为 0删除该结点 q1-link q-link; free(q); q q1-link; } else { q1 q; q q-link; } } else { // p-exp q-exppx 的项插入 PNode* temp (PNode*)malloc(sizeof(PNode)); temp-coef p-coef; temp-exp p-exp; temp-link q1-link; q1-link temp; q1 temp; } p p-link; // px 的游标后移 } }参数说明px是被加数只读不写qx是加数也是最终结果存放处。这里的游标设计是一个减枝技巧每次 p 后移后q 不需要重新从头开始遍历因为两个链表都是按指数递减排序的p 的上一项处理完以后p 的当前项的指数必然小于等于上一项所以 q 只需从当前位置继续向后扫描。外层循环的终止条件是p-exp 0也就是 px 的项全部处理完。此时 qx 中剩余项本身已经有序不需要额外处理。最终 qx 就是两个多项式逐项合并后的结果。4.4 多项式乘法逐项相乘与临时多项式乘法比加法多一个维度。实验报告里的实现思路是先单独计算 px 第一项与 qx 所有项的乘积得到一个临时多项式再逐个计算 px 后续每一项与 qx 的乘积每次得到新的临时多项式后调用Add把它合并到结果中。这个算法是两层嵌套循环void Multiply(Polynominal* px, Polynominal* qx) { Polynominal result; // 保存最终结果 InitPolynominal(result); PNode* p px-head-link; while (p-exp 0) { Polynominal temp; // 当前项与 qx 各项的乘积 InitPolynominal(temp); PNode* q qx-head-link; while (q-exp 0) { int newCoef p-coef * q-coef; int newExp p-exp q-exp; InsertTerm(temp, newCoef, newExp); // 合并同类项 q q-link; } Add(temp, result); // 累加到结果中 p p-link; } Output(result); }这段代码与实验报告中的完整版本相比做了逻辑重构InsertTerm在插入时已经合并了同类项用临时多项式 temp 存当前项的乘积组合Add 再把 temp 并入 result。每一步的产物都是“降幂排列且无同类项”的多项式避免了最终结果的二次整理。乘法的时间复杂度是 O(n²)因为外层每个项都要和内层的所有项相乘。如果多项式有 n 项总共有 n² 次乘法和相应次数的插入合并。实际运行中系数合并是另一个常数因子不影响整体的平方级复杂度。5. 实验验证、边界条件与隐藏问题排查5.1 功能验证的完整测试序列顺序表和链表的基本运算可以共用一套测试序列来验证操作序列输入预期输出验证点初始化无无报错空间分配成功连续插入0~8 依次插入链表内容 0 1 2 3 4 5 6 7 8尾部插入正确删除第 0 个元素下标 0链表内容 1 2 3 4 5 6 7 8头部删除、头结点不丢再次删除第 0 个元素下标 0链表内容 2 3 4 5 6 7 8连续头部删除查找第 0 个元素下标 0返回元素 2删除后查找仍正确插入到末尾下标 6值 9链表内容 2 3 4 5 6 7 8 9尾部插入删除越界下标 10返回 ERROR边界检查生效这个序列是实验报告里明确要求的操作流也是最容易暴露问题的组合。核心技巧是“删除头部后紧接着查找新头部”如果删除时没有正确更新头结点的link查找会拿到被释放的内存里的脏数据。5.2 三个必踩的坑坑一插入位置i的语义混淆。顺序表和链表都支持i -1表示表头位置这是实验报告里的约定。但很多人写的时候会把“在链表的第 i 个位置插入”和“在链表的第 i 个元素前面插入”混为一谈。拿链表举例i 0意思是“在第 0 个结点后面插入”i -1才是“插入到头结点后面”。注释里把这个约定写清楚比自己事后推理要省事得多。坑二系数相加后为零的结点必须释放。多项式的 Add 和 Multiply 中合并系数可能出现结果为 0 的情况。如果只把coef置 0 而不删除结点输出里会有0x^5这样的项做两次连续运算后零项积累最终结果完全不可读。坑三多项式乘法中临时链表的哨兵问题。实验报告原始代码把qx1改造成了循环链表用head-link head判断空而在后续插入中又用exp -1判断结束。这两个条件并存时最容易出错——空链表时head-link指向自己遍历条件exp ! -1在空表时是死循环。如果不做循环链表统一用link NULL判断会更安全这也是上面重构代码采用的方式。5.3 复杂度与性能的二次验证实验报告要求分析算法时间复杂度这里可以做一个小实验生成 n100、1000、5000 的三个多项式分别测量加法和乘法的耗时。结果应该呈现清晰的规律加法耗时接近 O(n)乘法耗时接近 O(n²)。用clock()计时时要注意多项式输入环节占据了一部分时间我一般会把计时点放在Add或Multiply函数调用前后而不是整个程序启动到结束。如果测试结果偏离预期优先看向量排列是否有序——无序输入会让InsertTerm的插入操作退化成 O(n²)整体复杂度随之失控。本文还有配套的精品资源点击获取