企业官网建设流程全解析

简介：面向南京邮电大学《数据结构》课程学生的实验一完整实验报告，主题为线性表的基本运算及多项式的算术运算。资源内容覆盖顺序表和带表头单链表的基本操作（初始化、查找、插入、删除、输出、撤销），并细致讲解一元多项式的创建、输出、加法与乘法运算；代码基于Windows和Microsoft Visual C++6.0环境编写，核心算法附有注释和复杂度分析，例如顺序表查找为O(1)、插入为O(n)，便于对照理解。压缩包内为单个docx文档，大小444KB，包含实验目的、算法设计、流程图、模块划分、详细源码、测试数据及运行结果截图，结构完整、排版清晰，可直接作为南京邮电大学数据结构实验报告的写作参考。已有772人学习使用，适合正在完成同类实验的本科生及需要复习线性表与多项式运算的读者。

1. 线性表的基本运算与多项式算术运算，这道实验一到底在考什么

“线性表操作”四个字，第一次出现在书本上是概念，第二次出现在试卷上就是区别会不会写代码的筛子。南京邮电大学数据结构实验一把线性表的基本运算和多项式的算术运算放在同一个题目里，用意很明显：先用顺序表和单链表把初始化、插入、删除、查找这些基本操作写熟练，再用多项式相加和相乘这类应用去检验对链表指针的控制力。由于多项式天然适合用有序链表表示，这道题几乎没有跳板，直接从“存数据”进入“算数据”。这篇博客按实验的常见顺序推进：先对比顺序表与链表的复杂度，给出两份可直接编译的基本运算代码；再把多项式加法、乘法实现成链表操作；最后用对拍脚本验证结果是否正确。适合正在写实验报告的人，也适合把这道题当作考研数据结构复习入口的人。

2. 线性表的基本运算：顺序表与单链表的选取和实现

线性表这个实验的第一部分，通常要求完成两种存储结构的基本运算。顺序表在逻辑上用数组顺序存储，按下标随机访问是 O(1)；单链表用 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, length+1]，允许在表尾追加，但不允许跳过当前长度插到后面去。移动元素时从后往前搬，这样才能避免覆盖未处理的元素。删除函数把被删元素通过指针参数*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 等于 30，length 变成 4。如果打印出来不是这个结果，多半是 pos 传参时把数组下标从 0 开始当成位置用了。

2.2 单链表的基本运算：带头结点的插入与删除

带头结点的单链表为什么普遍？因为带头结点之后，pos=1 和 pos=n+1 的处理逻辑被统一了，插入和删除都不需要单独处理“第一个结点”这个分支。下面的代码把这一层顾虑交给 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(n+m)。

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 输入与输出格式约定

输入输出格式如果实验指导书有强制要求，以要求为准。没有要求时，下面这组规则最不容易出错。

输出格式建议写一个专用函数，避免在 main 里散落逻辑。系数为 1 时省略系数，指数为 0 时只输出系数，首项为正时不带加号。这些细节不需要一次做全，但对拍前必须统一，否则两种实现输出格式不一致，diff 就没法用。

4. 运行实验时的纠错点：边界条件、内存回收与输入陷阱

代码能编译通过只完成了三分之一，跑出来的结果对才算真正做完。线性表实验的报错集中在边界条件、内存和输入格式三块，下面按优先级排。

4.1 空表与表尾：插入和删除的两个特判

顺序表插入时允许 pos 等于length + 1，也就是表尾追加。这个条件经常被误写成pos > length，导致最后一项永远插不进去。链表删除时 while 循环要用p->next作为条件，而不是p，否则删最后一个结点时会把 p 走到 NULL，后续解引用直接段错误。

正确写法对比：

写链表删除时，画一个两结点的图，把指针箭头标出来，比盯着代码想快得多。

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[i+j] += 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, key=lambda 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" done

diff没有输出说明两个版本在 100 组随机数据上完全一致。测试数据生成时要故意覆盖几种特殊场景：系数相加为 0 的项、指数为 0 的常数项、单项式多项式（项数为 1）、系数为负的首项。这几个场景分别对应合并删除、常数输出、边界循环和符号处理四个易错分支。

5.3 把实验题拆成面试题训练

这套实验做完后，不要急着删代码。把题目稍微改一改，就是考研数据结构和招聘面试的常客：合并两个有序链表，本质是多项式加法的骨架；对链表做插入排序，对应InsertPolynomial的定位逻辑；反转链表，训练的是指针重连的顺序感。面试时被问到“链表和数组的区别”，直接拿这道实验里的复杂度对比表和稀疏多项式例子回答，比背定义有说服力得多。遇到对拍失败的 case，先看 diff 输出的第一个位置，它通常暴露的是指数合并漏边，而不是大逻辑问题，定位到结点后打断点单步跟踪一遍就够了。

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