尧图网站开发 
简介这份数据结构实验报告针对南京邮电大学《数据结构》课程实验一完整覆盖线性表顺序存储与链式存储的基本运算以及一元多项式的创建、输出、加法、乘法实现。报告包含顺序表和带表头单链表的初始化、查找、插入、删除、输出、撤销等操作的核心C代码与时间复杂度分析并给出多项式加减乘运算的算法设计与测试结果适合计算机专业本科生在完成同类实验时参考对照。资源包内为1个docx文档共444KB包含实验目的、环境、原理、完整源码及运行结果结构清晰便于查阅。该资源已有779人浏览学习尤其适合需要撰写数据结构实验报告或理解线性表应用的初学者。1. 为什么多项式算术运算能检验线性表的基本运算到底学没学会很多人第一次看到这个题目会习惯性地把它拆成两件事前面背顺序表的插入删除后面再背一遍链表的多项式相加。但真实情况恰好相反。当你把多项式写成 (系数, 指数) 的按指数升序链表时会发现多项式相加就是在做线性表的插入、删除和合并指数相等就合项指数不等就按顺序挂链所谓“算术运算”剥开以后仍是链表指针的那点基本移动。这也是南邮这类数据结构实验把线性表和多项式放在同一个题里的原因它想让你用同一套线性表技能连续跨过顺序存储和链式存储两道坎。这篇笔记按 C 语言落地把结构体设计、核心函数和最容易丢分的细节一次讲透。适合刚做完理论作业、正准备上机敲代码的同学也适合用链表重写多项式运算但一直在断链和段错误里挣扎的读者。建议先看存储结构为什么这样选再动手复制代码否则只抄得形遇到边界条件照样翻车。2. 先定存储结构顺序表的连续内存和多项式链表的“离散”为什么必须分开2.1 顺序表 vs 单链表基本运算的“地利”和“硬伤”线性表基本运算的第一课通常是两套模板顺序表和单链表。实验里线性表部分常用顺序表实现多项式部分则用带头结点的单链表。先把两套结构定义摆出来后面的函数才有依托。顺序表的核心是数组加长度#define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; /* 当前元素个数 */ } SqList; void InitList(SqList *L) { L-length 0; }这里必须强调length存的是元素个数不是“最后一个元素的下标”。空表时length 0表里只有一个元素时length 1。后续所有插入、删除的边界判断都靠length来卡它一错程序就会在读到空位置或越界写入之间反复横跳。顺序表最大的优势是随机访问。想取第 i 个元素data[i-1]一步到位这是链表做不到的但它的最大痛点也在插入和删除。要在位置 i 插入时从 i 到表尾的所有元素都得往后挪一位平均移动约 n/2 个元素删除时又整体前移。这也是顺序表看似好写却最容易在边界判断上翻车的原因。另一套是单链表定义typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; void InitLinkList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); /* 头结点 */ (*L)-next NULL; }链表的插入删除只改指针不需要整体搬移数据。麻烦的是找第 i 个节点必须从头结点开始一步步p p-next想找尾部就得遍历。把两种结构并排看差距就清楚了。存储结构读取第 i 个元素在第 i 位置插入/删除空间分配顺序表O(1)按下标访问O(n)大量移动数据需要预知 MAXSIZE可能浪费单链表O(n)从头遍历O(n)但只改指针按需分配更灵活如果只是做一个 5 个数的线性表顺序表写起来更省事但实验后半段的多项式项的个数在运行前无法确定还要频繁插入和删除所以我会选链表。真正要练的不是“哪种更快”而是“哪种结构更匹配问题”。2.2 多项式链表里的结点比普通链表多一个“指数”多项式里每一项有两个核心信息系数和指数。普通链表的data字段在多项式这里被拆成两个字段这也是它看起来难、其实只是换了层皮的根源。typedef struct PolyNode { float coef; /* 系数 */ int exp; /* 指数 */ struct PolyNode *next; /* 指向下一项 */ } PolyNode, *Polynomial;按实验的常见做法链表带头结点头结点的coef和exp不存真实数据只用next指向第一项。空多项式判定为head-next NULL而不是指数等于 0。这一点非常重要后面避坑章节还会专门展开。为什么系数要用float而不是int如果只用int当两个多项式相减出现 0.3、-0.5 这类系数结果会被截断成 0程序在逻辑上就错了。虽然很多实验数据故意用整数我也建议定义成float在判断系数之和是否为零时保留一点误差空间。指数用int存。一元多项式的指数一般是非负整数把负数指数丢进去会让有序插入逻辑变得混乱所以读入时要做一次校验。如果题目扩展要求支持负指数也必须先定好比较规则而不是让q-next-exp exp这种判断去猜。整体上可以按下面这张图分工实验模块存储结构主要操作线性表基本运算顺序表 SqListInit / Insert / Delete / Locate / GetElem / Print多项式算术运算带头结点单链表 Polynomial创建 / 加法 / 减法 / 乘法 / 销毁这条线理清后代码就不容易混。很多人的问题在于拿顺序表的“下标”思路去写链表或者反过来让多项式去套数组结果越写越乱。2.3 带头结点还是不带一个影响全部后续代码的细节我习惯给单链表和多项式链表都加头结点。理由是操作第一个真实节点时分叉变少。如果不带头结点插入到第一位、删除第一位都要单独判断原指针是否为空还要处理“前驱不存在”的逻辑带头结点后head-next就是第一项的前驱插入删除统一写一套逻辑。代价是需要多 malloc 一个头结点。只要销毁时记得把头结点也 free这个代价完全可接受。有些教材会建议把多项式的项数存在头结点里我不推荐。头结点的coef和exp一旦参与运算所有遍历逻辑都要额外判断“这个节点是不是头结点”代码马上复杂一倍。让头结点保持next不空、数据字段不参与运算才是最省心的约定。3. 让线性表的基本运算落地插入、删除和查找的三个边界细节3.1 插入先从后往前移动再把新元素放进去顺序表插入的完整函数如下#define OK 1 #define ERROR 0 int ListInsert(SqList *L, int i, ElemType e) { if (L-length MAXSIZE) return ERROR; /* 表满 */ if (i 1 || i L-length 1) return ERROR; /* 非法位置 */ for (int j L-length; j i; --j) { L-data[j] L-data[j - 1]; /* 从后往前挪 */ } L-data[i - 1] e; L-length; return OK; }这里三个位置别猜错。第一j从L-length开始而不是从L-length - 1开始当表内有 n 个元素时data[n]是空位要先让最后一个元素data[n-1]挪到空位循环才能继续倒着走。第二循环条件必须是j i不能是j i否则位置 i 被让不出来。第三data[j] data[j - 1]是从后往前覆盖反过来从前往后会把后面的元素全部盖掉打印时出现一串重复数字。插入位置i的合法范围是 1 到length 1。i 1表示插到表头i length 1表示插到表尾后面。很多新手在i length 1时直接返回错误结果想追加元素永远失败这不是 bug是位序和数组下标混在一起了。测试时主函数这样写SqList L; InitList(L); for (int i 1; i 5; i) { ListInsert(L, i, i * 10); }这段代码每次都把新元素追加到末尾最终表内容是10 20 30 40 50。我故意把插入位置设为i是想让你亲手确认“当前有 4 个元素时插到第 5 位是合法的”这比背边界公式更可靠。3.2 删除先取出再前移最后长度减一删除函数与插入对应只是位移方向相反int ListDelete(SqList *L, int i, ElemType *e) { if (L-length 0) return ERROR; /* 空表 */ if (i 1 || i L-length) return ERROR; /* 非法位置 */ *e L-data[i - 1]; for (int j i; j L-length; j) { L-data[j - 1] L-data[j]; /* 从前往后挪 */ } L-length--; return OK; }删除的位移方向是从被删位置的后一位开始向前填空位。j的范围是i到length - 1如果删除的是最后一个元素循环不执行只执行length--行为正确。出参*e是个值得养成的习惯。函数只把被删的值放回给调用者主函数里定义ElemType deleted; ListDelete(L, 3, deleted);然后打印deleted。如果让删除函数直接返回被删元素遇到失败时容易把ERROR和合法数据混在一起。我更习惯用 int 返回成功与否、用指针带出数据。边界容易翻车的是i length删除最后一项时需要*e data[length - 1]然后length--结束不要试图给data[length - 1]清 0。顺序表里多余的空间本来就不参与输出清不清没有意义。3.3 查找和打印位序与下标之差是这个部分的小黑匣子下面的代码是线性表部分最常见的三个小函数int GetElem(SqList L, int i, ElemType *e) { if (i 1 || i L.length) return ERROR; /* 防越界 */ *e L.data[i - 1]; return OK; } int LocateElem(SqList L, ElemType e) { for (int i 0; i L.length; i) { if (L.data[i] e) return i 1; /* 返回位序 */ } return 0; /* 0 表示没找到 */ } void ListPrint(SqList L) { for (int i 0; i L.length; i) { printf(%d , L.data[i]); } printf(\n); }GetElem是“按位查找”输入位序输出元素LocateElem是“按值查找”输入元素返回位序。实际运行中总有人拿LocateElem的结果直接当数组下标用先找到第 3 位元素是 30想改它写L.data[pos] 0这一脚就把第 4 个元素改掉了。删除函数内部会用i - 1做一次换算所以ListDelete(L, pos, e)没问题但直接操作数组时位序和下标必须差 1。打印时只关心[0, length)范围内的数据。调试器里看到data[length]有旧值不用慌顺序表把length当成边界超出边界的空间就不算数。最后给一个能直接跑通的主函数片段int main() { SqList L; InitList(L); for (int i 1; i 5; i) ListInsert(L, i, i * 10); ElemType removed; ListDelete(L, 3, removed); printf(deleted%d\n, removed); /* deleted30 */ ListPrint(L); /* 10 20 40 50 */ int pos LocateElem(L, 40); printf(pos%d\n, pos); /* pos3 */ return 0; }这个主函数就是线性表部分的最小验收脚本初始化、连续插入、按位删除、输出、按值查找五个基本运算一次验完。如果输出全对线性表部分基本就稳了。4. 多项式的算术运算如何用一条有序链表完成加法、减法和乘法4.1 创建与插入多项式的“构造函数”要顺便排好序多项式链表的创建不能只做追加到末尾的Create因为加减法运算都依赖“指数升序”这个前提。我通常先实现下面这个按指数插入的InsertTerm后面所有算术运算都复用它。#include math.h #include stdlib.h void InsertTerm(Polynomial *p, float coef, int exp) { PolyNode *q *p; while (q-next ! NULL q-next-exp exp) { q q-next; /* 找到第一个指数不小于新项的节点 */ } if (q-next ! NULL q-next-exp exp) { q-next-coef coef; if (fabs(q-next-coef) 1e-6) { /* 合并后系数归零则删项 */ PolyNode *tmp q-next; q-next tmp-next; free(tmp); } } else { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); s-coef coef; s-exp exp; s-next q-next; q-next s; } }函数参数用Polynomial *p也就是指向头结点指针的指针。如果只是改节点内部字段传一级指针也可以但要统一处理“空链表时让头结点挂上第一项”就必须通过二级指针拿到头结点的地址。实验里全部用二级指针更省心看代码的人也不会猜迷糊。q-next-exp exp表示当前节点的后继比新项指数小继续向前走一旦后继指数等于新项指数说明这是同类项直接合并系数。合并后用fabs(q-next-coef) 1e-6判断零项并及时 free避免输出里出现“0x^2”这样的幽灵项。调用示例Polynomial head (Polynomial)malloc(sizeof(PolyNode)); head-next NULL; InsertTerm(head, 3, 2); /* 3x^2 */ InsertTerm(head, -1, 5); /* -x^5 */ InsertTerm(head, 1, 2); /* 合出 4x^2 */插完头序列是4x^2 - x^5不是输入顺序。关键是InsertTerm会一直维护指数升序即使中间插入也不会乱序。4.2 多项式加法两个链表各走一个指针指数谁小先挂谁有InsertTerm做地基加法就能写成直观的三段式Polynomial AddPoly(Polynomial a, Polynomial b) { Polynomial ans (Polynomial)malloc(sizeof(PolyNode)); ans-next NULL; PolyNode *pa a-next; PolyNode *pb b-next; while (pa ! NULL pb ! NULL) { if (pa-exp pb-exp) { InsertTerm(ans, pa-coef, pa-exp); pa pa-next; } else if (pa-exp pb-exp) { InsertTerm(ans, pb-coef, pb-exp); pb pb-next; } else { float sum pa-coef pb-coef; if (fabs(sum) 1e-6) InsertTerm(ans, sum, pa-exp); pa pa-next; pb pb-next; } } while (pa ! NULL) { InsertTerm(ans, pa-coef, pa-exp); pa pa-next; } while (pb ! NULL) { InsertTerm(ans, pb-coef, pb-exp); pb pb-next; } return ans; }逻辑是从两个多项式头部开始各用一个指针向后走。指数谁小谁就先被挂到结果链表指数相等时两系数相加。相加结果不为零就插入为零就当作这一项不存在。任一条链表走完后另一条链表的剩余项直接复制进结果链表因为结果链表本身有序不需要再排序。这样写不会破坏原来的两个多项式。InsertTerm内部始终 malloc 新节点所以a和b在加法后仍能打印和复用。如果你贪图省事直接把pa节点改链到ans加法做完后原多项式会断链后面的减法和乘法就真的没法做了。实验阶段最稳妥的做法就是“读一个、插一个、复制一个”空间少省几字节调试时少掉一大把头发。时间复杂度一眼能看出主循环最多走lenA lenB次每次InsertTerm还可能做线性查找所以不是严格意义的 O(n)。对课程实验的十几项规模来说完全够用先求对再谈优化。减法只改一处while (pb ! NULL) { InsertTerm(ans, -pb-coef, pb-exp); pb pb-next; }也就是把多项式 b 的每一项系数取负后再走一遍加法逻辑。实验报告里写“减法复用加法对 b 取负”即可不需要另写一套归并。4.3 多项式乘法逐项相乘再用同一个 InsertTerm 合并乘法的经典做法是双重循环。外层遍历 a 的每一项内层遍历 b 的每一项两项相乘得到新系数和新指数把结果交给InsertTerm自动排序和合并同类项。Polynomial MulPoly(Polynomial a, Polynomial b) { Polynomial ans (Polynomial)malloc(sizeof(PolyNode)); ans-next NULL; for (PolyNode *pa a-next; pa ! NULL; pa pa-next) { for (PolyNode *pb b-next; pb ! NULL; pb pb-next) { float c pa-coef * pb-coef; int e pa-exp pb-exp; if (fabs(c) 1e-6) InsertTerm(ans, c, e); } } return ans; }比如 a 有项3x^2b 有项-2x^4乘法产生新项c -6, e 6。即使已有同指数项InsertTerm也会通过exp exp的分支合并不需要乘法自己写归并。零系数的结果直接跳过避免出现一堆“0x^k”。这个写法最坏复杂度是 O(lenA * lenB * lenResult)对课程数据足够。如果以后做大整数或稀疏多项式再考虑用快速傅里叶变换一类方法第一课不需要碰。打印多项式需要控制格式。一个基础版本void PrintPoly(Polynomial p) { if (p-next NULL) { printf(0\n); return; } for (PolyNode *q p-next; q ! NULL; q q-next) { if (q ! p-next q-coef 0) printf(); printf(%.2fx^%d, q-coef, q-exp); } printf(\n); }这里仍有点粗糙指数为 0 时应当只打印常数项而不是x^0。输出格式化属于“答辩细节”最后一章再做。5. 常见问题排查四个让我在实验机房蹲到锁门的现场5.1 打印链表只输出一半或者直接段错误插入时指针顺序反了现象插入函数运行后遍历打印发现中间节点“消失”再访问一次就段错误。追踪起来插入好像没执行其实执行了只是后继被覆盖。原因单链表插入新节点时顺序必须是“先让新节点指向后继再让前驱指向新节点”。如果写成反例q-next s; s-next q-next; /* 错误s-next 指向了自己 */第二行里q-next已经被改成s于是s-next变成它自己链表形成环或者干脆把原后继节点的地址丢掉了。解决用InsertTerm这类统一函数管理插入不直接在主函数里手动拼指针。手动写时先做s-next q-next;再做q-next s;从右往左接线。review 代码时重点看这两行是否严格相邻且顺序正确。5.2 指数为 0 的项总丢加完后连常数项都不见现象多项式3x^2 5和x 2相加期望结果有常数项7实际输出只剩3x^2 x。原因很多入门代码喜欢用exp 0作为链表结束的标志理由是“普通多项式经常写到常数项结束”。这个约定在手算时没问题但题目里的常数项恰好是3x^0中的0链表还没走到真正的尾部就被exp 0判定为结束。解决统一改用next NULL判断链表结束绝不用指数做结束标志。头结点的数据字段也不要参与业务判断线性表边界由指针字段决定数据字段只负责存系数和指数。5.3 scanf 读多项式时系数和指数错位项数总是不对现象循环里用scanf(%f%d, coef, exp)读多项式第一次正常第二次以后程序莫名跳过系数直接把指数读成了下一行的系数。原因scanf不会吃掉输入行末尾的回车。换行留在输入缓冲区如果代码里混用了按字符读取的函数回车就会被当成可读字符吞掉。另外如果把输入的“项数”和“每项系数、指数”的格式写死成同一行实际输入时却每项换一行格式串就会按错位的方式解析。解决格式串scanf( %f %d, coef, exp);最前面加一个空格可以跳过空白字符。更稳的方案是fgets读整行再用sscanf解析。我个人偏向后一种因为它把“输入到哪里结束”交给字符串处理比 scanf 的流式读取更直观也更容易打印出来调试。5.4 临时结果一直 malloc内存只增不减现象程序能跑完但连续做十次多项式加法后内存占用明显上涨老师一问DestroyPoly怎么写支支吾吾。原因AddPoly和MulPoly每次都 malloc 结果头结点和多个结果节点。如果主函数里只保留最新结果指针旧结果既没有 free也没有指针能再找到它这就是内存泄漏。解决写一个完整销毁函数每次运算结束后立刻调用void DestroyPoly(Polynomial *p) { PolyNode *cur *p; while (cur ! NULL) { PolyNode *tmp cur; cur cur-next; free(tmp); } *p NULL; }tmp先保存当前要释放的节点cur先移到下一个节点再 free 掉tmp这样不会把下个节点的地址弄丢。最后*p NULL也是习惯防止野指针在后面的代码里二次炸雷。Linux 下可以用valgrind --leak-checkfull ./poly_test检查看到definitely lost: 0 bytes就安心了。6. 从“能交”到“能答”多项式加法的一组边界测试和内存体检实验课最差的结果不是报错而是“输出看起来对”但你说不出为什么对。交代码前我建议自己多跑几组专门刁难程序的用例。以两个多项式为例P1 5x^2 3x 1指数分别是 2、1、0P2 -5x^2 3x - 1。肉眼相加应得到6x。用程序输出时要检查三件事第一同类项正负抵消后InsertTerm有没有把归零节点删干净第二指数 0 的常数项有没有被错误漏掉第三结果6x是按指数升序打印而不是乱序。这组数据故意让首尾抵消、只留中间一项把合并、零项删除、有序插入三个逻辑同时逼出来。再测一个有代表性的减法边界P1 - P1结果应打印0。这时PrintPoly必须单独处理head-next NULL的空多项式情况不能什么都不输出。很多人的代码在“0 多项式”上翻车因为头结点后面没有节点循环一次都不进控制台空荡荡老师还以为程序卡死了。内存方面我习惯让AddPoly的返回值用一个临时指针先接着Polynomial result AddPoly(a, b); PrintPoly(result); DestroyPoly(result);如果实验还要打印原多项式一定要在 AddPoly 前先打印 a、b不要在 AddPoly 后再用 a 的指针去打印。我早先贪图省事把加法结果直接覆盖到 a后面想复用 a 做减法只能重建整个链表从那次起就再也不用“原地改”的写法。验证完成后把多组测试用例留在源文件里注释标明“指数升降/零系数/空多项式”。老师抽查时直接运行给他看比临时手敲数据可靠得多。数据结构实验的价值不只在跑通代码而在于你能说清楚每一个指针为什么这样走。希望这份踩坑记录对你也有用祝你一次过。本文还有配套的精品资源点击获取 
简介这份数据结构实验报告针对南京邮电大学《数据结构》课程实验一完整覆盖线性表顺序存储与链式存储的基本运算以及一元多项式的创建、输出、加法、乘法实现。报告包含顺序表和带表头单链表的初始化、查找、插入、删除、输出、撤销等操作的核心C代码与时间复杂度分析并给出多项式加减乘运算的算法设计与测试结果适合计算机专业本科生在完成同类实验时参考对照。资源包内为1个docx文档共444KB包含实验目的、环境、原理、完整源码及运行结果结构清晰便于查阅。该资源已有779人浏览学习尤其适合需要撰写数据结构实验报告或理解线性表应用的初学者。1. 为什么多项式算术运算能检验线性表的基本运算到底学没学会很多人第一次看到这个题目会习惯性地把它拆成两件事前面背顺序表的插入删除后面再背一遍链表的多项式相加。但真实情况恰好相反。当你把多项式写成 (系数, 指数) 的按指数升序链表时会发现多项式相加就是在做线性表的插入、删除和合并指数相等就合项指数不等就按顺序挂链所谓“算术运算”剥开以后仍是链表指针的那点基本移动。这也是南邮这类数据结构实验把线性表和多项式放在同一个题里的原因它想让你用同一套线性表技能连续跨过顺序存储和链式存储两道坎。这篇笔记按 C 语言落地把结构体设计、核心函数和最容易丢分的细节一次讲透。适合刚做完理论作业、正准备上机敲代码的同学也适合用链表重写多项式运算但一直在断链和段错误里挣扎的读者。建议先看存储结构为什么这样选再动手复制代码否则只抄得形遇到边界条件照样翻车。2. 先定存储结构顺序表的连续内存和多项式链表的“离散”为什么必须分开2.1 顺序表 vs 单链表基本运算的“地利”和“硬伤”线性表基本运算的第一课通常是两套模板顺序表和单链表。实验里线性表部分常用顺序表实现多项式部分则用带头结点的单链表。先把两套结构定义摆出来后面的函数才有依托。顺序表的核心是数组加长度#define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; /* 当前元素个数 */ } SqList; void InitList(SqList *L) { L-length 0; }这里必须强调length存的是元素个数不是“最后一个元素的下标”。空表时length 0表里只有一个元素时length 1。后续所有插入、删除的边界判断都靠length来卡它一错程序就会在读到空位置或越界写入之间反复横跳。顺序表最大的优势是随机访问。想取第 i 个元素data[i-1]一步到位这是链表做不到的但它的最大痛点也在插入和删除。要在位置 i 插入时从 i 到表尾的所有元素都得往后挪一位平均移动约 n/2 个元素删除时又整体前移。这也是顺序表看似好写却最容易在边界判断上翻车的原因。另一套是单链表定义typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; void InitLinkList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); /* 头结点 */ (*L)-next NULL; }链表的插入删除只改指针不需要整体搬移数据。麻烦的是找第 i 个节点必须从头结点开始一步步p p-next想找尾部就得遍历。把两种结构并排看差距就清楚了。存储结构读取第 i 个元素在第 i 位置插入/删除空间分配顺序表O(1)按下标访问O(n)大量移动数据需要预知 MAXSIZE可能浪费单链表O(n)从头遍历O(n)但只改指针按需分配更灵活如果只是做一个 5 个数的线性表顺序表写起来更省事但实验后半段的多项式项的个数在运行前无法确定还要频繁插入和删除所以我会选链表。真正要练的不是“哪种更快”而是“哪种结构更匹配问题”。2.2 多项式链表里的结点比普通链表多一个“指数”多项式里每一项有两个核心信息系数和指数。普通链表的data字段在多项式这里被拆成两个字段这也是它看起来难、其实只是换了层皮的根源。typedef struct PolyNode { float coef; /* 系数 */ int exp; /* 指数 */ struct PolyNode *next; /* 指向下一项 */ } PolyNode, *Polynomial;按实验的常见做法链表带头结点头结点的coef和exp不存真实数据只用next指向第一项。空多项式判定为head-next NULL而不是指数等于 0。这一点非常重要后面避坑章节还会专门展开。为什么系数要用float而不是int如果只用int当两个多项式相减出现 0.3、-0.5 这类系数结果会被截断成 0程序在逻辑上就错了。虽然很多实验数据故意用整数我也建议定义成float在判断系数之和是否为零时保留一点误差空间。指数用int存。一元多项式的指数一般是非负整数把负数指数丢进去会让有序插入逻辑变得混乱所以读入时要做一次校验。如果题目扩展要求支持负指数也必须先定好比较规则而不是让q-next-exp exp这种判断去猜。整体上可以按下面这张图分工实验模块存储结构主要操作线性表基本运算顺序表 SqListInit / Insert / Delete / Locate / GetElem / Print多项式算术运算带头结点单链表 Polynomial创建 / 加法 / 减法 / 乘法 / 销毁这条线理清后代码就不容易混。很多人的问题在于拿顺序表的“下标”思路去写链表或者反过来让多项式去套数组结果越写越乱。2.3 带头结点还是不带一个影响全部后续代码的细节我习惯给单链表和多项式链表都加头结点。理由是操作第一个真实节点时分叉变少。如果不带头结点插入到第一位、删除第一位都要单独判断原指针是否为空还要处理“前驱不存在”的逻辑带头结点后head-next就是第一项的前驱插入删除统一写一套逻辑。代价是需要多 malloc 一个头结点。只要销毁时记得把头结点也 free这个代价完全可接受。有些教材会建议把多项式的项数存在头结点里我不推荐。头结点的coef和exp一旦参与运算所有遍历逻辑都要额外判断“这个节点是不是头结点”代码马上复杂一倍。让头结点保持next不空、数据字段不参与运算才是最省心的约定。3. 让线性表的基本运算落地插入、删除和查找的三个边界细节3.1 插入先从后往前移动再把新元素放进去顺序表插入的完整函数如下#define OK 1 #define ERROR 0 int ListInsert(SqList *L, int i, ElemType e) { if (L-length MAXSIZE) return ERROR; /* 表满 */ if (i 1 || i L-length 1) return ERROR; /* 非法位置 */ for (int j L-length; j i; --j) { L-data[j] L-data[j - 1]; /* 从后往前挪 */ } L-data[i - 1] e; L-length; return OK; }这里三个位置别猜错。第一j从L-length开始而不是从L-length - 1开始当表内有 n 个元素时data[n]是空位要先让最后一个元素data[n-1]挪到空位循环才能继续倒着走。第二循环条件必须是j i不能是j i否则位置 i 被让不出来。第三data[j] data[j - 1]是从后往前覆盖反过来从前往后会把后面的元素全部盖掉打印时出现一串重复数字。插入位置i的合法范围是 1 到length 1。i 1表示插到表头i length 1表示插到表尾后面。很多新手在i length 1时直接返回错误结果想追加元素永远失败这不是 bug是位序和数组下标混在一起了。测试时主函数这样写SqList L; InitList(L); for (int i 1; i 5; i) { ListInsert(L, i, i * 10); }这段代码每次都把新元素追加到末尾最终表内容是10 20 30 40 50。我故意把插入位置设为i是想让你亲手确认“当前有 4 个元素时插到第 5 位是合法的”这比背边界公式更可靠。3.2 删除先取出再前移最后长度减一删除函数与插入对应只是位移方向相反int ListDelete(SqList *L, int i, ElemType *e) { if (L-length 0) return ERROR; /* 空表 */ if (i 1 || i L-length) return ERROR; /* 非法位置 */ *e L-data[i - 1]; for (int j i; j L-length; j) { L-data[j - 1] L-data[j]; /* 从前往后挪 */ } L-length--; return OK; }删除的位移方向是从被删位置的后一位开始向前填空位。j的范围是i到length - 1如果删除的是最后一个元素循环不执行只执行length--行为正确。出参*e是个值得养成的习惯。函数只把被删的值放回给调用者主函数里定义ElemType deleted; ListDelete(L, 3, deleted);然后打印deleted。如果让删除函数直接返回被删元素遇到失败时容易把ERROR和合法数据混在一起。我更习惯用 int 返回成功与否、用指针带出数据。边界容易翻车的是i length删除最后一项时需要*e data[length - 1]然后length--结束不要试图给data[length - 1]清 0。顺序表里多余的空间本来就不参与输出清不清没有意义。3.3 查找和打印位序与下标之差是这个部分的小黑匣子下面的代码是线性表部分最常见的三个小函数int GetElem(SqList L, int i, ElemType *e) { if (i 1 || i L.length) return ERROR; /* 防越界 */ *e L.data[i - 1]; return OK; } int LocateElem(SqList L, ElemType e) { for (int i 0; i L.length; i) { if (L.data[i] e) return i 1; /* 返回位序 */ } return 0; /* 0 表示没找到 */ } void ListPrint(SqList L) { for (int i 0; i L.length; i) { printf(%d , L.data[i]); } printf(\n); }GetElem是“按位查找”输入位序输出元素LocateElem是“按值查找”输入元素返回位序。实际运行中总有人拿LocateElem的结果直接当数组下标用先找到第 3 位元素是 30想改它写L.data[pos] 0这一脚就把第 4 个元素改掉了。删除函数内部会用i - 1做一次换算所以ListDelete(L, pos, e)没问题但直接操作数组时位序和下标必须差 1。打印时只关心[0, length)范围内的数据。调试器里看到data[length]有旧值不用慌顺序表把length当成边界超出边界的空间就不算数。最后给一个能直接跑通的主函数片段int main() { SqList L; InitList(L); for (int i 1; i 5; i) ListInsert(L, i, i * 10); ElemType removed; ListDelete(L, 3, removed); printf(deleted%d\n, removed); /* deleted30 */ ListPrint(L); /* 10 20 40 50 */ int pos LocateElem(L, 40); printf(pos%d\n, pos); /* pos3 */ return 0; }这个主函数就是线性表部分的最小验收脚本初始化、连续插入、按位删除、输出、按值查找五个基本运算一次验完。如果输出全对线性表部分基本就稳了。4. 多项式的算术运算如何用一条有序链表完成加法、减法和乘法4.1 创建与插入多项式的“构造函数”要顺便排好序多项式链表的创建不能只做追加到末尾的Create因为加减法运算都依赖“指数升序”这个前提。我通常先实现下面这个按指数插入的InsertTerm后面所有算术运算都复用它。#include math.h #include stdlib.h void InsertTerm(Polynomial *p, float coef, int exp) { PolyNode *q *p; while (q-next ! NULL q-next-exp exp) { q q-next; /* 找到第一个指数不小于新项的节点 */ } if (q-next ! NULL q-next-exp exp) { q-next-coef coef; if (fabs(q-next-coef) 1e-6) { /* 合并后系数归零则删项 */ PolyNode *tmp q-next; q-next tmp-next; free(tmp); } } else { PolyNode *s (PolyNode *)malloc(sizeof(PolyNode)); s-coef coef; s-exp exp; s-next q-next; q-next s; } }函数参数用Polynomial *p也就是指向头结点指针的指针。如果只是改节点内部字段传一级指针也可以但要统一处理“空链表时让头结点挂上第一项”就必须通过二级指针拿到头结点的地址。实验里全部用二级指针更省心看代码的人也不会猜迷糊。q-next-exp exp表示当前节点的后继比新项指数小继续向前走一旦后继指数等于新项指数说明这是同类项直接合并系数。合并后用fabs(q-next-coef) 1e-6判断零项并及时 free避免输出里出现“0x^2”这样的幽灵项。调用示例Polynomial head (Polynomial)malloc(sizeof(PolyNode)); head-next NULL; InsertTerm(head, 3, 2); /* 3x^2 */ InsertTerm(head, -1, 5); /* -x^5 */ InsertTerm(head, 1, 2); /* 合出 4x^2 */插完头序列是4x^2 - x^5不是输入顺序。关键是InsertTerm会一直维护指数升序即使中间插入也不会乱序。4.2 多项式加法两个链表各走一个指针指数谁小先挂谁有InsertTerm做地基加法就能写成直观的三段式Polynomial AddPoly(Polynomial a, Polynomial b) { Polynomial ans (Polynomial)malloc(sizeof(PolyNode)); ans-next NULL; PolyNode *pa a-next; PolyNode *pb b-next; while (pa ! NULL pb ! NULL) { if (pa-exp pb-exp) { InsertTerm(ans, pa-coef, pa-exp); pa pa-next; } else if (pa-exp pb-exp) { InsertTerm(ans, pb-coef, pb-exp); pb pb-next; } else { float sum pa-coef pb-coef; if (fabs(sum) 1e-6) InsertTerm(ans, sum, pa-exp); pa pa-next; pb pb-next; } } while (pa ! NULL) { InsertTerm(ans, pa-coef, pa-exp); pa pa-next; } while (pb ! NULL) { InsertTerm(ans, pb-coef, pb-exp); pb pb-next; } return ans; }逻辑是从两个多项式头部开始各用一个指针向后走。指数谁小谁就先被挂到结果链表指数相等时两系数相加。相加结果不为零就插入为零就当作这一项不存在。任一条链表走完后另一条链表的剩余项直接复制进结果链表因为结果链表本身有序不需要再排序。这样写不会破坏原来的两个多项式。InsertTerm内部始终 malloc 新节点所以a和b在加法后仍能打印和复用。如果你贪图省事直接把pa节点改链到ans加法做完后原多项式会断链后面的减法和乘法就真的没法做了。实验阶段最稳妥的做法就是“读一个、插一个、复制一个”空间少省几字节调试时少掉一大把头发。时间复杂度一眼能看出主循环最多走lenA lenB次每次InsertTerm还可能做线性查找所以不是严格意义的 O(n)。对课程实验的十几项规模来说完全够用先求对再谈优化。减法只改一处while (pb ! NULL) { InsertTerm(ans, -pb-coef, pb-exp); pb pb-next; }也就是把多项式 b 的每一项系数取负后再走一遍加法逻辑。实验报告里写“减法复用加法对 b 取负”即可不需要另写一套归并。4.3 多项式乘法逐项相乘再用同一个 InsertTerm 合并乘法的经典做法是双重循环。外层遍历 a 的每一项内层遍历 b 的每一项两项相乘得到新系数和新指数把结果交给InsertTerm自动排序和合并同类项。Polynomial MulPoly(Polynomial a, Polynomial b) { Polynomial ans (Polynomial)malloc(sizeof(PolyNode)); ans-next NULL; for (PolyNode *pa a-next; pa ! NULL; pa pa-next) { for (PolyNode *pb b-next; pb ! NULL; pb pb-next) { float c pa-coef * pb-coef; int e pa-exp pb-exp; if (fabs(c) 1e-6) InsertTerm(ans, c, e); } } return ans; }比如 a 有项3x^2b 有项-2x^4乘法产生新项c -6, e 6。即使已有同指数项InsertTerm也会通过exp exp的分支合并不需要乘法自己写归并。零系数的结果直接跳过避免出现一堆“0x^k”。这个写法最坏复杂度是 O(lenA * lenB * lenResult)对课程数据足够。如果以后做大整数或稀疏多项式再考虑用快速傅里叶变换一类方法第一课不需要碰。打印多项式需要控制格式。一个基础版本void PrintPoly(Polynomial p) { if (p-next NULL) { printf(0\n); return; } for (PolyNode *q p-next; q ! NULL; q q-next) { if (q ! p-next q-coef 0) printf(); printf(%.2fx^%d, q-coef, q-exp); } printf(\n); }这里仍有点粗糙指数为 0 时应当只打印常数项而不是x^0。输出格式化属于“答辩细节”最后一章再做。5. 常见问题排查四个让我在实验机房蹲到锁门的现场5.1 打印链表只输出一半或者直接段错误插入时指针顺序反了现象插入函数运行后遍历打印发现中间节点“消失”再访问一次就段错误。追踪起来插入好像没执行其实执行了只是后继被覆盖。原因单链表插入新节点时顺序必须是“先让新节点指向后继再让前驱指向新节点”。如果写成反例q-next s; s-next q-next; /* 错误s-next 指向了自己 */第二行里q-next已经被改成s于是s-next变成它自己链表形成环或者干脆把原后继节点的地址丢掉了。解决用InsertTerm这类统一函数管理插入不直接在主函数里手动拼指针。手动写时先做s-next q-next;再做q-next s;从右往左接线。review 代码时重点看这两行是否严格相邻且顺序正确。5.2 指数为 0 的项总丢加完后连常数项都不见现象多项式3x^2 5和x 2相加期望结果有常数项7实际输出只剩3x^2 x。原因很多入门代码喜欢用exp 0作为链表结束的标志理由是“普通多项式经常写到常数项结束”。这个约定在手算时没问题但题目里的常数项恰好是3x^0中的0链表还没走到真正的尾部就被exp 0判定为结束。解决统一改用next NULL判断链表结束绝不用指数做结束标志。头结点的数据字段也不要参与业务判断线性表边界由指针字段决定数据字段只负责存系数和指数。5.3 scanf 读多项式时系数和指数错位项数总是不对现象循环里用scanf(%f%d, coef, exp)读多项式第一次正常第二次以后程序莫名跳过系数直接把指数读成了下一行的系数。原因scanf不会吃掉输入行末尾的回车。换行留在输入缓冲区如果代码里混用了按字符读取的函数回车就会被当成可读字符吞掉。另外如果把输入的“项数”和“每项系数、指数”的格式写死成同一行实际输入时却每项换一行格式串就会按错位的方式解析。解决格式串scanf( %f %d, coef, exp);最前面加一个空格可以跳过空白字符。更稳的方案是fgets读整行再用sscanf解析。我个人偏向后一种因为它把“输入到哪里结束”交给字符串处理比 scanf 的流式读取更直观也更容易打印出来调试。5.4 临时结果一直 malloc内存只增不减现象程序能跑完但连续做十次多项式加法后内存占用明显上涨老师一问DestroyPoly怎么写支支吾吾。原因AddPoly和MulPoly每次都 malloc 结果头结点和多个结果节点。如果主函数里只保留最新结果指针旧结果既没有 free也没有指针能再找到它这就是内存泄漏。解决写一个完整销毁函数每次运算结束后立刻调用void DestroyPoly(Polynomial *p) { PolyNode *cur *p; while (cur ! NULL) { PolyNode *tmp cur; cur cur-next; free(tmp); } *p NULL; }tmp先保存当前要释放的节点cur先移到下一个节点再 free 掉tmp这样不会把下个节点的地址弄丢。最后*p NULL也是习惯防止野指针在后面的代码里二次炸雷。Linux 下可以用valgrind --leak-checkfull ./poly_test检查看到definitely lost: 0 bytes就安心了。6. 从“能交”到“能答”多项式加法的一组边界测试和内存体检实验课最差的结果不是报错而是“输出看起来对”但你说不出为什么对。交代码前我建议自己多跑几组专门刁难程序的用例。以两个多项式为例P1 5x^2 3x 1指数分别是 2、1、0P2 -5x^2 3x - 1。肉眼相加应得到6x。用程序输出时要检查三件事第一同类项正负抵消后InsertTerm有没有把归零节点删干净第二指数 0 的常数项有没有被错误漏掉第三结果6x是按指数升序打印而不是乱序。这组数据故意让首尾抵消、只留中间一项把合并、零项删除、有序插入三个逻辑同时逼出来。再测一个有代表性的减法边界P1 - P1结果应打印0。这时PrintPoly必须单独处理head-next NULL的空多项式情况不能什么都不输出。很多人的代码在“0 多项式”上翻车因为头结点后面没有节点循环一次都不进控制台空荡荡老师还以为程序卡死了。内存方面我习惯让AddPoly的返回值用一个临时指针先接着Polynomial result AddPoly(a, b); PrintPoly(result); DestroyPoly(result);如果实验还要打印原多项式一定要在 AddPoly 前先打印 a、b不要在 AddPoly 后再用 a 的指针去打印。我早先贪图省事把加法结果直接覆盖到 a后面想复用 a 做减法只能重建整个链表从那次起就再也不用“原地改”的写法。验证完成后把多组测试用例留在源文件里注释标明“指数升降/零系数/空多项式”。老师抽查时直接运行给他看比临时手敲数据可靠得多。数据结构实验的价值不只在跑通代码而在于你能说清楚每一个指针为什么这样走。希望这份踩坑记录对你也有用祝你一次过。本文还有配套的精品资源点击获取