企业官网建设流程全解析

简介：这份数据结构实验报告针对南京邮电大学《数据结构》课程实验一，完整覆盖线性表顺序存储与链式存储的基本运算，以及一元多项式的创建、输出、加法、乘法实现。报告包含顺序表和带表头单链表的初始化、查找、插入、删除、输出、撤销等操作的核心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，想找尾部就得遍历。把两种结构并排看，差距就清楚了。

如果只是做一个 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这种判断去猜。

整体上可以按下面这张图分工：

这条线理清后，代码就不容易混。很多人的问题在于拿顺序表的“下标”思路去写链表，或者反过来让多项式去套数组，结果越写越乱。

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); /* deleted=30 */ ListPrint(L); /* 10 20 40 50 */ int pos = LocateElem(L, 40); printf("pos=%d\n", pos); /* pos=3 */ 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^2，b 有项-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-check=full ./poly_test检查，看到definitely lost: 0 bytes就安心了。

6. 从“能交”到“能答”：多项式加法的一组边界测试和内存体检

实验课最差的结果不是报错，而是“输出看起来对”，但你说不出为什么对。交代码前，我建议自己多跑几组专门刁难程序的用例。

以两个多项式为例：

• P1 = 5x^2 + 3x + 1，指数分别是 2、1、0；
• P2 = -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 做减法只能重建整个链表，从那次起就再也不用“原地改”的写法。

验证完成后，把多组测试用例留在源文件里，注释标明“指数升降/零系数/空多项式”。老师抽查时直接运行给他看，比临时手敲数据可靠得多。数据结构实验的价值不只在跑通代码，而在于你能说清楚每一个指针为什么这样走。希望这份踩坑记录对你也有用，祝你一次过。

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