简介面向南京邮电大学《数据结构》课程学生的实验一完整实验报告主题为线性表的基本运算及多项式的算术运算。资源内容覆盖顺序表和带表头单链表的基本操作初始化、查找、插入、删除、输出、撤销并细致讲解一元多项式的创建、输出、加法与乘法运算代码基于Windows和Microsoft Visual C6.0环境编写核心算法附有注释和复杂度分析例如顺序表查找为O(1)、插入为O(n)便于对照理解。压缩包内为单个docx文档大小444KB包含实验目的、算法设计、流程图、模块划分、详细源码、测试数据及运行结果截图结构完整、排版清晰可直接作为南京邮电大学数据结构实验报告的写作参考。已有772人学习使用适合正在完成同类实验的本科生及需要复习线性表与多项式运算的读者。1. 线性表的基本运算与多项式算术运算这道实验一到底在考什么“线性表操作”四个字第一次出现在书本上是概念第二次出现在试卷上就是区别会不会写代码的筛子。南京邮电大学数据结构实验一把线性表的基本运算和多项式的算术运算放在同一个题目里用意很明显先用顺序表和单链表把初始化、插入、删除、查找这些基本操作写熟练再用多项式相加和相乘这类应用去检验对链表指针的控制力。由于多项式天然适合用有序链表表示这道题几乎没有跳板直接从“存数据”进入“算数据”。这篇博客按实验的常见顺序推进先对比顺序表与链表的复杂度给出两份可直接编译的基本运算代码再把多项式加法、乘法实现成链表操作最后用对拍脚本验证结果是否正确。适合正在写实验报告的人也适合把这道题当作考研数据结构复习入口的人。2. 线性表的基本运算顺序表与单链表的选取和实现线性表这个实验的第一部分通常要求完成两种存储结构的基本运算。顺序表在逻辑上用数组顺序存储按下标随机访问是 O(1)单链表用 next 指针把不相邻的结点串起来插入和删除只改指针不搬数据。实验一要是把这两种结构写熟练后面的栈、队列基本就不用再学写法因为它们一个是加了操作限制的数组另一个是穿了不同外衣的链表。操作顺序表单链表按位置访问O(1)O(n)按值查找无序O(n)O(n)在已知位置前插入或删除O(n)需搬动元素查找 O(n)找到后指针操作 O(1)存储空间一次性分配 maxsize按需分配额外存一个 next 指针当插入位置集中在表尾时顺序表更划算当插入删除集中在表头或者数据总量不确定时单链表更稳。实验要求两个都写报告里把这张表放上去选型理由就站住了。2.1 顺序表的基本运算初始化、插入、删除的完整代码顺序表的三个核心要素data 数组指针、length 当前长度、maxsize 容量上限。实验里最常见的错误是直接用int data[100]完事一旦把代码扩展到函数传参边界条件就握不住。下面这组函数按“带容量的动态数组”来写方便在 main 里指定容量也为以后学动态扩容留了接口。#include stdio.h #include stdlib.h typedef int ElemType; typedef struct { ElemType *data; int length; int maxsize; } SqList; void InitList(SqList *L, int maxsize) { L-data (ElemType *)malloc(maxsize * sizeof(ElemType)); if (!L-data) exit(1); L-length 0; L-maxsize maxsize; } int ListInsert(SqList *L, int pos, ElemType e) { if (pos 1 || pos L-length 1) return 0; if (L-length L-maxsize) return 0; for (int i L-length - 1; i pos - 1; i--) { L-data[i 1] L-data[i]; } L-data[pos - 1] e; L-length; return 1; } int ListDelete(SqList *L, int pos, ElemType *e) { if (pos 1 || pos L-length) return 0; *e L-data[pos - 1]; for (int i pos; i L-length; i) { L-data[i - 1] L-data[i]; } L-length--; return 1; }插入函数里pos 的取值范围是[1, length1]允许在表尾追加但不允许跳过当前长度插到后面去。移动元素时从后往前搬这样才能避免覆盖未处理的元素。删除函数把被删元素通过指针参数*e带出来返回 1 表示成功0 表示失败。maxsize传 100 还是 1000 取决于实验数据规模一般给 100 就够报告里要写清楚“插入前先判断容量”这一步。main 函数里可以这样验证int main() { SqList L; InitList(L, 100); for (int i 1; i 5; i) { ListInsert(L, i, i * 10); } ElemType e; if (ListDelete(L, 3, e)) { printf(deleted %d\n, e); } printf(length %d\n, L.length); free(L.data); return 0; }删除返回的 e 等于 30length 变成 4。如果打印出来不是这个结果多半是 pos 传参时把数组下标从 0 开始当成位置用了。2.2 单链表的基本运算带头结点的插入与删除带头结点的单链表为什么普遍因为带头结点之后pos1 和 posn1 的处理逻辑被统一了插入和删除都不需要单独处理“第一个结点”这个分支。下面的代码把这一层顾虑交给 while 循环处理。typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; void InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (!*L) exit(1); (*L)-next NULL; } int ListInsert(LinkList L, int pos, ElemType e) { LNode *p L; int j 0; while (p j pos - 1) { p p-next; j; } if (!p || j ! pos - 1) return 0; LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) return 0; s-data e; s-next p-next; p-next s; return 1; } int ListDelete(LinkList L, int pos, ElemType *e) { LNode *p L; int j 0; while (p-next j pos - 1) { p p-next; j; } if (!p-next || j ! pos - 1) return 0; LNode *q p-next; *e q-data; p-next q-next; free(q); return 1; }while 循环结束后p 指向待插入位置的前驱结点j 是 p 走过的步数。j ! pos - 1这个条件能挡掉 pos 过大造成的越界如果只判断p是否为空空链表上插入就会成功逻辑上是错的。删除时先保存q p-next拿到数据改完指针再 free顺序不能反过来。malloc 返回的结点要判空虽然 OJ 上大概率不会失败但内存不足时直接解引用就是段错误。2.3 实验报告里必须交代清楚的三个参数写实验报告时不要把代码贴上去就完事评审老师通常会看你对边界条件的理解。以下三个参数建议在报告里单独说明。maxsize是顺序表的容量上限不是当前长度。删除操作会让 length 变小但 maxsize 不变插入前判断L-length L-maxsize用的是容量不是数组边界。pos从 1 开始内部通过pos - 1映射到数组下标。这是整份代码里最容易错的地方报告开头统一声明“本文所有位置从 1 起内部下标从 0 起”能省很多事。函数返回值统一约定为 1 成功、0 失败而不是 void。这样 main 里可以直接if (ListInsert(L, 5, 99))判断操作是否合法。如果后面复习考研数据结构这个约定就是王道数据结构那套代码风格的前身值得现在养成习惯。3. 多项式的算术运算用有序链表实现加法与乘法多项式算术运算这块实验指导书最常见的要求是“输入两个多项式输出它们的和与积”。第一反应是用数组下标当指数内容当系数。这个做法在指数范围小、多项式稠密的时候没有问题但题目如果给5x^1000 1这种稀疏项数组就要开 1001 个元素绝大多数是 0浪费严重。更合理的方案是让每一项只占一个结点结点里放 coef、expn 和 next这就是标题把线性表和多项式放在同一个实验里的原因把线性表的基本运算用到具体场景里。typedef struct PolyNode { float coef; int expn; struct PolyNode *next; } PolyNode, *Polynomial;3.1 多项式链表创建尾插法保持指数有序创建多项式的常见做法是尾插法。输入时按指数升序排列后一项挂在前一项后面head 是头结点不存数据。void CreatePolynomial(Polynomial *P, int n) { *P (Polynomial)malloc(sizeof(PolyNode)); (*P)-next NULL; PolyNode *tail *P; for (int i 0; i n; i) { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); scanf(%f %d, s-coef, s-expn); s-next NULL; tail-next s; tail s; } }coef 用 float 是因为实验数据可能有小数expn 用 int指数可以为负不影响排序。如果题目没有保证输入按指数有序有两种处理方法一是把链表转成数组排完序再重建二是直接调用后续的InsertPolynomial逐个插入。后者代码量更小推荐优先使用。3.2 多项式相加指数相等时合并同类项多项式加法本质上就是两个有序链表的合并只是当两个结点指数相等时不是简单选一个而是把系数相加后生成新项。实现时用一个辅助函数 copyNode 复制结点这样不会破坏输入链表 A 和 B。PolyNode *copyNode(PolyNode *src) { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); s-coef src-coef; s-expn src-expn; s-next NULL; return s; } Polynomial AddPolynomial(Polynomial A, Polynomial B) { Polynomial C (Polynomial)malloc(sizeof(PolyNode)); C-next NULL; PolyNode *pa A-next, *pb B-next, *pc C; while (pa pb) { if (pa-expn pb-expn) { float sum pa-coef pb-coef; if (sum ! 0) { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); s-coef sum; s-expn pa-expn; s-next NULL; pc-next s; pc s; } pa pa-next; pb pb-next; } else if (pa-expn pb-expn) { pc-next copyNode(pa); pc pc-next; pa pa-next; } else { pc-next copyNode(pb); pc pc-next; pb pb-next; } } while (pa) { pc-next copyNode(pa); pc pc-next; pa pa-next; } while (pb) { pc-next copyNode(pb); pc pc-next; pb pb-next; } return C; }注意sum ! 0这个判断系数相加后恰好为 0 的项结点不创建、不连接、不打印。这是多项式加法里最容易漏掉的分支漏掉的后果是结果里出现0x^3这类无意义项对拍时一眼就能看出来。三个 while 循环加起来的时间复杂度是 O(nm)。3.3 多项式乘法逐项相乘再有序插入乘法比加法多一个维度。常规做法是双重循环把 A 的每一项和 B 的每一项相乘得到coef * coef、expn expn的临时项然后插入结果链表 C。插入时如果指数重复就合并系数如果系数合并后为 0还要把结点删掉。void InsertPolynomial(Polynomial P, float coef, int expn) { if (coef 0) return; PolyNode *pre P, *cur P-next; while (cur cur-expn expn) { pre cur; cur cur-next; } if (cur cur-expn expn) { cur-coef coef; if (cur-coef 0) { pre-next cur-next; free(cur); } } else { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); s-coef coef; s-expn expn; s-next cur; pre-next s; } } Polynomial MultiplyPolynomial(Polynomial A, Polynomial B) { Polynomial C (Polynomial)malloc(sizeof(PolyNode)); C-next NULL; for (PolyNode *pa A-next; pa; pa pa-next) { for (PolyNode *pb B-next; pb; pb pb-next) { InsertPolynomial(C, pa-coef * pb-coef, pa-expn pb-expn); } } return C; }乘法结束后C 天然有序因为每一次 InsertPolynomial 都保持了有序性。这个实现的复杂度是 O(n * m * len(C))len(C)是结果链表的长度。实验报告里写一句“指数范围大时可用哈希表数据结构优化查找”能体现你考虑过更优方案但实验本身不需要实现。3.4 输入与输出格式约定输入输出格式如果实验指导书有强制要求以要求为准。没有要求时下面这组规则最不容易出错。数据建议做法多项式项数 n第一行读入整数每项两个数scanf(%f %d, coef, expn)输入指数顺序默认升序不保证时用 InsertPolynomial 逐个插入项数可能为 0允许 n0head-next 为 NULL系数为 0 的项创建链表时直接跳过输出格式建议写一个专用函数避免在 main 里散落逻辑。系数为 1 时省略系数指数为 0 时只输出系数首项为正时不带加号。这些细节不需要一次做全但对拍前必须统一否则两种实现输出格式不一致diff 就没法用。4. 运行实验时的纠错点边界条件、内存回收与输入陷阱代码能编译通过只完成了三分之一跑出来的结果对才算真正做完。线性表实验的报错集中在边界条件、内存和输入格式三块下面按优先级排。4.1 空表与表尾插入和删除的两个特判顺序表插入时允许 pos 等于length 1也就是表尾追加。这个条件经常被误写成pos length导致最后一项永远插不进去。链表删除时 while 循环要用p-next作为条件而不是p否则删最后一个结点时会把 p 走到 NULL后续解引用直接段错误。正确写法对比场景容易错的写法正确的判断顺序表在末尾插入pos length 返回失败pos length 1 才返回失败链表遍历找前驱while (p)while (p-next)链表删除最后一个循环结束后 p 为 NULL循环结束后 p 指向倒数第二个结点写链表删除时画一个两结点的图把指针箭头标出来比盯着代码想快得多。4.2 内存回收free 之前先保存 next链表删除结点后要用一个临时指针保存下一个结点否则 free 当前结点后就无法访问 next 了。销毁整个链表同样如此void DestroyList(LinkList L) { LNode *p L-next; while (p) { LNode *tmp p; p p-next; free(tmp); } free(L); }顺序表在 main 结束前也要free(L.data)。OJ 不回收内存可能也能过实验报告里如果写了“本程序无内存泄漏”这句代码就是证据。4.3 用断言和打印中间结果定位问题插入删除前后各调用一次打印函数能看到元素搬动方向是否符合预期。多项式相加时在合并分支里临时打印 sum 的值能直接看出输入数据有没有被错误覆盖。assert 宏适合检查理论上的不变量比如插入后 length 应该加一#include assert.h assert(L.length old_len 1);assert 在 release 模式下不生效所以关键逻辑还是要靠显式 if 判断assert 只是辅助。4.4 scanf 的输入格式坑实验中常见的输入格式有两种5 2 3 -1 2 4 0 3 1 -2 2这种就不好用循环 scanf因为每一项两个数需要区分指数和系数。更稳妥、可读性更好的做法是用 fgets 加 sscanf 按行解析char line[128]; while (fgets(line, sizeof(line), stdin)) { float coef; int expn; if (sscanf(line, %f %d, coef, expn) 2) { // 处理一项 } }sscanf返回值是成功解析的参数个数等于 2 才说明这一行是两个有效数字。如果输入里混入空行sscanf返回 0继续读下一行即可。5. 从“跑通”到“跑稳”多项式运算的对拍验证方法实验跑通容易跑稳难。一个隐藏很深的指数合并 bug靠肉眼盯几组手算数据根本发现不了。对拍是竞争性编程里常用的验证手法也适合拿来做数据结构实验写一个逻辑简单的参照实现再写一个随机数据生成器把两个程序的输出 diff 一下。5.1 参照实现数组版多项式数组版多项式用下标当指数值当系数只支持非负小指数的情况但逻辑极简单不容易写错。#define MAX_EXP 100 float polyA[MAX_EXP] {0}; float polyB[MAX_EXP] {0}; // 读入时累加polyA[expn] coef; // 加法polyC[i] polyA[i] polyB[i]; // 乘法先清零再双重循环 polyC[ij] polyA[i] * polyB[j];把这个版本编译成poly_array链表版编译成poly_list两者读同样的输入输出统一的coef expn列表。5.2 随机生成测试数据并自动对比用 Python 生成随机测试用例指数范围控制在 0 到 10 之间保证数组版能用。import random for _ in range(1): n random.randint(1, 8) items [] used_exp set() for _ in range(n): expn random.randint(0, 10) coef random.randint(-5, 5) if coef ! 0 and expn not in used_exp: used_exp.add(expn) items.append((coef, expn)) print(len(items)) for coef, expn in sorted(items, keylambda x: x[1]): print(coef, expn)然后循环跑 100 组for i in $(seq 1 100); do python3 gen_test.py test.in ./poly_list test.in out_list.txt ./poly_array test.in out_array.txt diff out_list.txt out_array.txt || echo case $i failed donediff没有输出说明两个版本在 100 组随机数据上完全一致。测试数据生成时要故意覆盖几种特殊场景系数相加为 0 的项、指数为 0 的常数项、单项式多项式项数为 1、系数为负的首项。这几个场景分别对应合并删除、常数输出、边界循环和符号处理四个易错分支。5.3 把实验题拆成面试题训练这套实验做完后不要急着删代码。把题目稍微改一改就是考研数据结构和招聘面试的常客合并两个有序链表本质是多项式加法的骨架对链表做插入排序对应InsertPolynomial的定位逻辑反转链表训练的是指针重连的顺序感。面试时被问到“链表和数组的区别”直接拿这道实验里的复杂度对比表和稀疏多项式例子回答比背定义有说服力得多。遇到对拍失败的 case先看 diff 输出的第一个位置它通常暴露的是指数合并漏边而不是大逻辑问题定位到结点后打断点单步跟踪一遍就够了。本文还有配套的精品资源点击获取