南邮数据结构实验一：线性表与多项式运算的完整实现与避坑指南

简介：本资源为南京邮电大学《数据结构》课程实验一的完整实验报告，面向计算机相关专业学生及正在学习线性表与多项式运算的编程初学者。报告围绕顺序表与带表头单链表两种存储结构展开，涵盖初始化、查找、插入、删除、输出、撤销等基本运算，并进一步实现一元多项式的创建、输出、相加与相乘，配有核心C源代码、详细注释及时间复杂度分析。资源包共1个docx文件，约444KB，内容按实验目的、实验环境、算法设计、算法实现与分析、实验结果与结论等模块组织，结构清晰，便于对照课本程序2.1至2.14逐步理解。目前已有774人学习下载，适合需要完成同类实验、复习线性表操作或参考多项式链表实现思路的读者，可直接借鉴其模块划分、流程图设计与测试数据组织方式。

1. 线性表与多项式：为什么这个实验值得你花一整个下午

如果你正在上南京邮电大学的数据结构课，实验一大概率是你这学期第一个真正要动手写代码的作业。标题里两个东西——线性表的基本运算、多项式的算术运算——看起来像是两个独立任务，实际上后者就是前者的一个典型应用场景。线性表是最基础的数据结构，顺序表和单链表是它的两种主流实现方式；而一元多项式相加，恰好能把「有序插入」「合并同类项」「链表遍历」这些操作串起来，逼着你把线性表的增删改查真正用一遍。

我带过几届学生的课程设计，发现一个很普遍的现象：很多人顺序表写得飞快，一到单链表就开始翻车，指针指来指去最后自己都不知道指哪了。这个实验的价值不在于写出一个能跑的多项式加法，而在于让你在调试指针的过程中，真正理解「节点」「前驱」「后继」这些概念。适合谁看？如果你刚学完线性表的定义，知道struct和指针的基本用法，但还没完整写过超过两百行的数据结构代码，这篇就是给你准备的。下面我按顺序表、单链表、多项式运算三条线，把能抄的代码、要调的参数、容易踩的坑一次讲清楚。

2. 顺序表的基本运算：从结构体定义到插入删除的完整实现

2.1 顺序表的结构体设计与初始化参数

顺序表的核心就一句话：用一段连续内存存数据，再用一个变量记录当前长度。C 语言里最常见的定义方式是这样：

#define MAXSIZE 100 // 顺序表最大容量，按实验要求调整 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElemType; // 元素类型，多项式实验里可以改成结构体 typedef struct { ElemType data[MAXSIZE]; // 静态分配，编译时确定大小 int length; // 当前实际元素个数，不是下标 } SqList;

这里有几个参数你必须想清楚。MAXSIZE取多少取决于实验数据规模，南邮实验一的多项式项数一般不会超过 20，取 100 绰绰有余。length表示当前元素个数，合法范围是 0 到 MAXSIZE，注意它和数组下标差 1——第 i 个元素存在data[i-1]里，这个「差一」是后面所有越界 bug 的根源。

初始化函数很简单，但别偷懒不写：

int InitList(SqList *L) { if (L == NULL) return ERROR; // 防御性检查，别省 L->length = 0; return OK; }

逻辑说明：初始化只做一件事，把length置零。data数组里的内容是垃圾值，不需要清空，因为length决定了哪些位置是有效的。参数说明：传入的是SqList *指针，因为要修改结构体内容；如果传值，函数内的修改不会影响外部。

2.2 插入与删除：三个必须记住的边界条件

插入操作是顺序表最容易写错的地方。先看代码：

int ListInsert(SqList *L, int i, ElemType e) { // i 表示插入位置，合法范围 1 <= i <= length+1 if (i < 1 || i > L->length + 1) return ERROR; // 位置越界 if (L->length >= MAXSIZE) 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; }

逻辑说明：插入的本质是把第 i 个位置及之后的所有元素往后挪一位，腾出空位。循环必须从后往前，如果从前往后挪，data[i]会被data[i-1]覆盖，后面的数据全丢。参数说明：i是逻辑位置（从 1 开始），e是待插入元素。三个边界条件——i < 1、i > length+1、length >= MAXSIZE——一个都不能少，少一个就是潜在的段错误。

删除操作反过来，从前往后挪：

int ListDelete(SqList *L, int i, ElemType *e) { 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; }

逻辑说明：删除第 i 个元素后，它后面的元素依次前移一位。*e用来把被删的值传回调用者，这是 C 语言里模拟「多返回值」的常见手法。参数说明：i的合法范围是 1 到length，注意和插入不同，删除不能删空位置。

提示：很多同学写插入时把i的范围写成1 <= i <= length，结果最后一个位置永远插不进去。记住，长度为 n 的表有 n+1 个插入点。

2.3 按值查找与遍历输出

查找和遍历是多项式实验里用得最多的辅助操作：

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 表示未找到，因为合法位置从 1 开始 } void PrintList(SqList L) { for (int i = 0; i < L.length; i++) { printf("%d ", L.data[i]); } printf("\n"); }

逻辑说明：LocateElem返回第一个匹配元素的逻辑位置，找不到返回 0。这里用 0 作为「未找到」的标志是安全的，因为合法位置从 1 开始。PrintList直接按length遍历，不依赖任何哨兵值。参数说明：查找传值即可，因为不需要修改表；遍历同理。

顺序表的时间复杂度要心里有数：按位置查找 O(1)，按值查找 O(n)，插入和删除平均 O(n)。这个实验里数据量小，性能不是问题，但面试和考试会问，别只会写不会说。

3. 单链表的基本操作：指针操作的血泪经验

3.1 带头结点的链表定义与头插法建表

单链表和顺序表最大的区别在于，元素不连续存储，每个节点靠指针找到下一个。定义如下：

typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

这里LinkList是指向LNode的指针类型，等价于LNode *。实验里通常要求带头结点，头结点不存有效数据，它的next指向第一个真实节点。带头结点的好处是插入和删除第一个位置时不需要特殊处理，代码统一。

头插法建表：

void CreateListHead(LinkList *L, int n) { *L = (LinkList)malloc(sizeof(LNode)); // 创建头结点 (*L)->next = NULL; for (int i = 0; i < n; i++) { LNode *p = (LNode *)malloc(sizeof(LNode)); scanf("%d", &p->data); p->next = (*L)->next; // 新节点指向原第一个节点 (*L)->next = p; // 头结点指向新节点 } }

逻辑说明：头插法每次把新节点插在头结点后面，所以输入顺序和链表顺序相反。参数说明：LinkList *L是二级指针，因为要修改头指针本身；n是节点个数。注意malloc之后必须检查是否返回 NULL，实验代码里可以省略，但工程代码里不能省。

尾插法建表更符合直觉，需要一个尾指针：

void CreateListTail(LinkList *L, int n) { *L = (LinkList)malloc(sizeof(LNode)); (*L)->next = NULL; LNode *r = *L; // r 始终指向尾节点 for (int i = 0; i < n; i++) { LNode *p = (LNode *)malloc(sizeof(LNode)); scanf("%d", &p->data); r->next = p; r = p; } r->next = NULL; // 尾节点 next 置空，别忘了 }

逻辑说明：尾插法维护一个尾指针r，每次把新节点接到r后面，然后更新r。最后必须把尾节点的next置 NULL，否则链表没有结束标志，遍历时会越界。参数说明：n是节点个数，r是辅助指针，不占额外空间。

3.2 按位插入与删除：指针断链的顺序不能反

单链表的插入操作，关键是找到第 i-1 个节点，然后改指针：

int ListInsert(LinkList L, int i, ElemType e) { LNode *p = L; // p 指向头结点 int j = 0; while (p != NULL && j < i - 1) { // 找第 i-1 个节点 p = p->next; j++; } if (p == NULL || j > i - 1) return ERROR; // i 越界 LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = e; s->next = p->next; // 先接后面 p->next = s; // 再断前面 return OK; }

逻辑说明：插入分两步——新节点先指向原第 i 个节点，然后第 i-1 个节点指向新节点。顺序不能反，如果先执行p->next = s，原来的p->next就丢了，新节点接不上后面的链。参数说明：i是逻辑位置，合法范围 1 到length+1；j是计数器，用来定位。

删除操作类似，但要多一个释放内存的步骤：

int ListDelete(LinkList L, int i, ElemType *e) { LNode *p = L; int j = 0; while (p->next != NULL && j < i - 1) { p = p->next; j++; } if (p->next == NULL || j > i - 1) return ERROR; LNode *q = p->next; // q 指向待删节点 *e = q->data; p->next = q->next; // 跳过 q free(q); // 释放内存，别漏 return OK; }

逻辑说明：删除时先让p停在待删节点的前驱上，然后用q记住待删节点，改指针后free(q)。参数说明：循环条件是p->next != NULL，因为要保证p有后继可删。

注意：单链表插入和删除的时间复杂度都是 O(n)，因为要从头找位置。如果你在面试里被问到「如何在 O(1) 时间删除单链表节点」，那是指给定待删节点指针的情况，和这个实验的场景不同。

3.3 单链表的清空与销毁：两个容易混淆的操作

清空和销毁经常被混为一谈，但它们的语义不同。清空是保留头结点，释放所有数据节点；销毁是连头结点一起释放。

void ClearList(LinkList L) { LNode *p = L->next; while (p != NULL) { LNode *q = p; p = p->next; free(q); } L->next = NULL; // 头结点 next 置空 } void DestroyList(LinkList *L) { LNode *p = *L; while (p != NULL) { LNode *q = p; p = p->next; free(q); } *L = NULL; // 头指针置空 }

逻辑说明：ClearList从头结点的下一个开始释放，最后把头结点next置 NULL，链表变成空表但头结点还在。DestroyList从头结点开始释放，最后把头指针置 NULL，整个链表不复存在。参数说明：ClearList传一级指针即可，因为不修改头指针；DestroyList传二级指针，因为要把头指针置 NULL。

这两个操作在多项式实验里都会用到——清空用于重置多项式，销毁用于程序结束前释放内存。很多同学只写一个free循环就交差了，实验报告里被扣分都不知道为什么。

4. 一元多项式的算术运算：把链表用起来的经典案例

4.1 多项式的链表表示与节点结构

一元多项式比如3x^5 + 2x^3 - 4x + 7，每一项由系数和指数组成。用链表存储时，每个节点存一个项：

typedef struct PNode { float coef; // 系数，用 float 支持小数 int exp; // 指数，非负整数 struct PNode *next; } PNode, *Polynomial;

这里系数用float而不是int，因为多项式运算中可能出现小数系数。指数用int，实验里一般是非负整数。链表按指数递减排列，这样合并同类项时只需要一次遍历。

创建多项式时，输入格式通常是「系数 指数」成对输入，以 0 0 结束：

void CreatePolynomial(Polynomial *P) { *P = (PNode *)malloc(sizeof(PNode)); (*P)->next = NULL; PNode *r = *P; float c; int e; while (scanf("%f %d", &c, &e) && (c != 0 || e != 0)) { PNode *p = (PNode *)malloc(sizeof(PNode)); p->coef = c; p->exp = e; r->next = p; r = p; } r->next = NULL; }

逻辑说明：用尾插法建表，输入以0 0作为结束标志。参数说明：c和e分别接收系数和指数，循环条件c != 0 || e != 0保证只有两者同时为 0 才退出。

4.2 多项式相加：归并思想与同类项合并

两个多项式相加，本质上是两个有序链表归并，指数相同的项系数相加，指数不同的项按序插入。

Polynomial AddPolynomial(Polynomial A, Polynomial B) { PNode *pa = A->next; PNode *pb = B->next; Polynomial C = (PNode *)malloc(sizeof(PNode)); C->next = NULL; PNode *pc = C; // pc 始终指向结果链表尾 while (pa != NULL && pb != NULL) { if (pa->exp > pb->exp) { // A 的项指数大，直接接到结果 pc->next = (PNode *)malloc(sizeof(PNode)); pc = pc->next; pc->coef = pa->coef; pc->exp = pa->exp; pa = pa->next; } else if (pa->exp < pb->exp) { // B 的项指数大 pc->next = (PNode *)malloc(sizeof(PNode)); pc = pc->next; pc->coef = pb->coef; pc->exp = pb->exp; pb = pb->next; } else { // 指数相同，系数相加 float sum = pa->coef + pb->coef; if (sum != 0) { // 系数为 0 的项不存入结果 pc->next = (PNode *)malloc(sizeof(PNode)); pc = pc->next; pc->coef = sum; pc->exp = pa->exp; } pa = pa->next; pb = pb->next; } } // 处理剩余项 PNode *remain = (pa != NULL) ? pa : pb; while (remain != NULL) { pc->next = (PNode *)malloc(sizeof(PNode)); pc = pc->next; pc->coef = remain->coef; pc->exp = remain->exp; remain = remain->next; } pc->next = NULL; return C; }

逻辑说明：这是归并排序的经典套路。两个链表按指数递减排列，每次比较当前节点的指数，大的先输出到结果链表。指数相同时系数相加，如果和为 0 则跳过（不创建节点）。循环结束后把剩余的非空链表直接接上。参数说明：A和B是带头结点的多项式链表，返回的C也是带头结点的结果链表。

这里有个细节值得注意：结果链表是新建节点还是复用原节点？上面的代码是新建节点，好处是不破坏原多项式，坏处是内存占用翻倍。如果实验允许破坏原链表，可以直接把pa或pb的节点摘下来接到C后面，省去malloc。两种写法都对，看实验要求。

4.3 多项式相减与输出格式控制

相减就是把 B 的每个系数取反再相加：

Polynomial SubPolynomial(Polynomial A, Polynomial B) { // 复制 B，系数取反 Polynomial negB = (PNode *)malloc(sizeof(PNode)); negB->next = NULL; PNode *r = negB; PNode *pb = B->next; while (pb != NULL) { PNode *p = (PNode *)malloc(sizeof(PNode)); p->coef = -pb->coef; p->exp = pb->exp; r->next = p; r = p; pb = pb->next; } r->next = NULL; Polynomial result = AddPolynomial(A, negB); // 释放 negB，略 return result; }

逻辑说明：先构造-B，然后调用加法。参数说明：negB是临时链表，用完要释放，实验代码里可以省略但工程代码里不能省。

输出多项式时要注意格式，系数为 1 或 -1 时省略数字，指数为 0 时只输出系数，指数为 1 时省略^1：

void PrintPolynomial(Polynomial P) { PNode *p = P->next; if (p == NULL) { printf("0\n"); return; } int first = 1; // 标记是否是第一项 while (p != NULL) { if (!first && p->coef > 0) printf("+"); if (p->coef != 1 && p->coef != -1) { printf("%.1f", p->coef); } else if (p->coef == -1) { printf("-"); } if (p->exp == 1) { printf("x"); } else if (p->exp > 1) { printf("x^%d", p->exp); } first = 0; p = p->next; } printf("\n"); }

逻辑说明：first标记用来控制正项前的+号，第一项不加。系数为 1 或 -1 时省略数字，但 -1 要输出负号。指数为 1 时输出x，大于 1 时输出x^exp，等于 0 时只输出系数。参数说明：%.1f保留一位小数，按实验要求调整精度。

5. 避坑与排查：那些年我们调指针调出来的教训

5.1 顺序表插入位置越界导致数据错乱

现象：插入后遍历输出，发现最后一个元素重复出现，或者中间某个元素被覆盖。

原因：插入循环for (int j = L->length; j >= i; j--)里，如果i的边界检查漏了i > length+1，当i等于length+2时，循环不会执行，但data[i-1]会写到数组范围外，可能覆盖其他变量。

解决：插入前必须检查i < 1 || i > L->length + 1，两个条件缺一不可。另外length >= MAXSIZE也要检查，否则数组越界写。

5.2 单链表插入时指针断链顺序写反

现象：插入节点后，新节点后面的所有节点都丢了，链表长度不对。

原因：写成了p->next = s; s->next = p->next;。第一步执行后，p->next已经指向s，第二步s->next = p->next相当于s->next = s，新节点自己指向自己，后面的链全断。

解决：记住口诀「先接后，再断前」。s->next = p->next; p->next = s;顺序不能反。画图确认每一步的指针指向，比死记硬背靠谱。

5.3 多项式相加时忘记处理系数为零的项

现象：结果多项式里出现0x^3这样的项，输出格式不对。

原因：指数相同时系数相加，如果和为 0，不应该创建节点。上面的代码里加了if (sum != 0)判断，但很多同学漏了。

解决：合并同类项时，先算sum，只有sum != 0才malloc新节点。另外如果结果链表所有项系数都为 0，最后应该输出0，PrintPolynomial里已经处理了空链表的情况。

5.4 尾插法建表忘记把尾节点 next 置空

现象：遍历链表时多输出一个垃圾值，或者程序崩溃。

原因：尾插法建表时，最后一个节点的next没有置 NULL，指向了未初始化的内存。遍历时while (p != NULL)会一直走下去，直到访问非法地址。

解决：建表循环结束后，必须执行r->next = NULL;。这个操作在头插法里不需要，因为头插法每个新节点的next都指向了原第一个节点，最后一个节点的next自然为 NULL。

5.5 释放链表时 free 顺序错误导致内存泄漏

现象：程序运行正常，但用 valgrind 检查发现内存泄漏。

原因：free(p)之后又访问p->next，这是未定义行为。正确做法是先用q保存p->next，再free(p)，然后p = q。

解决：释放链表的模板代码：

LNode *p = L->next; while (p != NULL) { LNode *q = p->next; // 先保存下一个 free(p); // 再释放当前 p = q; // 最后移动 }

顺序不能乱。这个坑在多项式实验里尤其常见，因为要释放多个链表。

6. 进阶技巧：用二级指针简化插入删除，以及实验报告的写法

6.1 二级指针在单链表操作中的妙用

很多教材的单链表插入删除用一级指针加前驱查找，代码冗长。用二级指针可以简化：

// 在链表 L 中删除第一个值为 e 的节点 int DeleteByValue(LinkList *L, ElemType e) { LNode **p = L; // p 指向「指向当前节点的指针」 while (*p != NULL && (*p)->data != e) { p = &(*p)->next; // p 移动到下一个节点的 next 域地址 } if (*p == NULL) return ERROR; // 没找到 LNode *q = *p; *p = (*p)->next; // 直接修改前驱的 next free(q); return OK; }

逻辑说明：p是二级指针，初始指向头指针L。*p是当前节点，&(*p)->next是当前节点next域的地址。找到目标后，*p = (*p)->next直接修改前驱的next，不需要单独处理头结点。参数说明：LinkList *L是二级指针，因为可能修改头指针（删除第一个节点时）。

这个技巧在 408 考研代码题里经常出现，熟练之后能省不少代码。但实验报告里建议先用常规写法，确保逻辑清晰，再用二级指针优化。

6.2 多项式乘法：从加法到乘法的扩展思路

实验一通常只要求加法，但有些老师会加一个乘法作为加分项。乘法的思路是：用 A 的每一项去乘 B 的每一项，得到临时多项式，再累加。

Polynomial MultiplyPolynomial(Polynomial A, Polynomial B) { Polynomial result = (PNode *)malloc(sizeof(PNode)); result->next = NULL; for (PNode *pa = A->next; pa != NULL; pa = pa->next) { // 构造 A 的当前项与 B 相乘的临时多项式 Polynomial temp = (PNode *)malloc(sizeof(PNode)); temp->next = NULL; PNode *r = temp; for (PNode *pb = B->next; pb != NULL; pb = pb->next) { PNode *p = (PNode *)malloc(sizeof(PNode)); p->coef = pa->coef * pb->coef; p->exp = pa->exp + pb->exp; r->next = p; r = p; } r->next = NULL; // 累加到结果 Polynomial newResult = AddPolynomial(result, temp); // 释放 result 和 temp，略 result = newResult; } return result; }

逻辑说明：双重循环，外层遍历 A 的每一项，内层遍历 B 的每一项，系数相乘、指数相加。每次得到一个临时多项式，用加法累加到结果。参数说明：时间复杂度 O(n*m)，n 和 m 分别是 A 和 B 的项数。注意每次累加后要释放旧的result和temp，否则内存泄漏严重。

6.3 实验报告里老师最看重的三个点

最后说点实在的。南邮数据结构实验一的报告，老师批改时主要看三样东西：

第一，结构体定义和函数声明是否规范。头文件里写清楚#define和typedef，函数原型按功能分组，别把所有代码堆在main里。

第二，边界条件是否考虑完整。插入位置越界、表满、空表删除、查找不存在的值，这些情况你的代码有没有处理。实验报告里可以列一个测试用例表：

第三，时间复杂度分析。顺序表和单链表的插入删除查找，各自的时间复杂度写清楚，最好能对比说明为什么多项式相加用链表比顺序表更合适——因为多项式项数动态变化，链表插入删除不需要移动元素。

我自己的习惯是，写完代码先跑三组数据：一组正常数据、一组边界数据、一组极端数据（比如空表、单项、系数全抵消）。三组都过了再写报告，能省掉大量返工时间。希望帮到你。

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