简介南京邮电大学《数据结构》课程实验一的完整实验报告围绕线性表基本运算及多项式算术运算展开适合正在学习数据结构、需要参考实验报告写法与C语言实现代码的本科生。压缩包内为1个docx文档大小约444KB内容涵盖顺序表和带表头单链表的初始化、查找、插入、删除、输出、撤销等基本操作同时实现了一元多项式的创建、输出、加法和乘法运算每个模块均包含数据结构定义、算法流程图、核心C源代码与时间复杂度分析例如顺序表查找为O(1)、插入为O(n)链表查找与插入均为O(n)。报告中还给出了实验目的、软硬件环境、测试数据及运行结果能够帮助读者对比顺序存储与链式存储的特点理解线性表在多项式计算中的具体应用。已有779人学习下载对于完成同类实验、复习数据结构考点或撰写实验报告都有直接的参考价值。1. 数据结构实验一这份代码线性表基本运算和多项式算术运算全部能直接抄做数据结构课程实验最怕的不是不会写而是对着课本程序 2.12.7、2.82.14 抄完编译能过、一跑就崩报错了还不知道去哪查。这份来自南京邮电大学《数据结构》课程实验一的完整实验报告把顺序表、带头结点单链表和一元多项式的加法和乘法三块一次讲透完整 C 代码、时间复杂度和实验小结里的真实踩坑记录都在里面。适合两类人一是正在补数据结构实验、想快速拿到可运行代码的本科生二是想用一份完整案例把线性表的顺序存储、链式存储和多项式应用串起来的自学者。后面每一步都能照着敲不用再猜课本代码到底在干什么。2. 顺序表下标查找 O(1)插入删除为什么必须从后往前移2.1 存储结构与两个边界判断顺序表就是拿数组存线性表逻辑相邻的元素物理上也相邻教科书上叫顺序存储。代码里通常用一个结构体把数组指针、当前长度、最大容量捆在一起// 顺序表结构定义对照课本程序 2.1 的常见做法补全 typedef struct { ElemType *element; // 动态数组首地址 int n; // 当前元素个数 int maxLength; // 已分配的最大容量 } SeqList;这里最容易看漏的是i的双重语义。查找操作里i是元素下标取值范围0 ~ n-1插入操作里i是“前驱位置”新元素要放到i1处。也就是说向第 0 位插数据时i -1所以插入的下界判断是i -1不是i 0。这个下界是最先要记住的规则后面所有边界判断都从这里推出来。2.2 查找和插入的代码以及为什么从后往前移查找直接用下标取元素没有任何循环复杂度就是 O(1)插入要把插入位置后面的所有元素整体后移一位平均移动 n/2 个元素复杂度 O(n)。代码和注释如下// 查找把下标 i 处的元素通过指针 x 带回找不到返回 ERROR Status Find(SeqList seqList, int i, ElemType* x) { if (i 0 || i seqList.n - 1) { return ERROR; // 下标越界直接拒绝 } *x seqList.element[i]; // 顺序表可随机存取一步到位 return OK; } // 插入把 x 放到下标 i1 的位置i 是前驱下标 Status Insert(SeqList* seqList, int i, ElemType x) { int j; if (i -1 || i seqList-n - 1) // 注意下界是 -1 return ERROR; if (seqList-n seqList-maxLength) // 空间满先挡住防止越界写 return ERROR; for (j seqList-n - 1; j i; j--) { // 从最后一个元素开始后移 seqList-element[j 1] seqList-element[j]; } seqList-element[i 1] x; // 新元素落到 i1 槽位 seqList-n; // 长度加 1 return OK; }后移的顺序是从j n-1递减写到i这个顺序是死的。如果反过来从前往后写element[j1] element[j]会先把没搬走的元素覆盖掉数组里立刻出现重复值这是顺序表最常见的翻车场景。判断空间满用的n maxLength要放在移动元素之前先判满再动手否则n超过maxLength时数组越界写会悄悄发生运行时不报错过一阵子才出现脏数据。插入完成后n必须在最后顺序表的所有操作都以n为准n错了后面全乱。2.3 与课本 2.12.7 的对应以及销毁操作怎么补实验要求做初始化、查找、插入、删除、输出、撤销六件事与课本程序 2.12.7 的对应关系如下操作函数名注意点时间复杂度初始化InitList分配 element 空间n0O(1)查找Find直接下标访问O(1)插入Insert先判满再从后往前移O(n)删除Delete从前往后移覆盖被删元素O(n)输出Output遍历并按格式打印O(n)撤销Destroy逐段 free 空间O(1)撤销操作很多人最后忘记写free(seqList-element);然后把n和maxLength都置 0。顺序表使用动态数组时不 free 就是内存泄漏实验评分里算法效能和程序设计能力两项都会扣分。写完后可以把Delete自己补一遍对照删除是插入的逆操作移动方向从前往后覆盖掉i处的元素后n--即可。3. 带头结点的单链表插入删除全靠头结点省掉一半边界判断3.1 为什么非要这个“带表头结点”单链表逻辑上相邻的元素物理上不连续靠指针串起来。带头结点和不带头结点的差别实验做一次就能体会不带头结点时插到第 0 位和删除第 0 位都要直接改head指针本身函数里就得传二级指针Node**否则修改带不回去。带头结点之后表头结点永远存在插入删除任何位置的代码完全一样不需要为“第 0 位”单独写分支。实验用的类型定义就是最常见的版本typedef struct node { ElemType element; // 结点的数据域 struct node *link; // 结点的指针域 } node; typedef struct { struct node *head; // 表头结点数据域不用 int n; // 链表结点个数 } headerList;head指向的表头结点的element里不存有效数据link指向第一个真正带数据的结点链表为空时head-link NULLn 0。这样初始化时只要head (node*)malloc(sizeof(node)); head-link NULL; n 0三行就够。3.2 插入和删除代码以及“先接后继再改前驱”的原则插入和删除的完整代码是这份报告里最值得抄的部分// 插入把 x 插入到下标 i1 的位置 Status Insert(headerList* h, int i, ElemType x) { node* p, * q; int j; if (i -1 || i h-n - 1) return ERROR; p h-head; // 从头结点出发找前驱 for (j 0; j i; j) // 走 i1 步p 停在待插位置的前驱 p p-link; q (node*)malloc(sizeof(node)); q-element x; q-link p-link; // 先让新结点接上后继 p-link q; // 再让前驱指向新结点 h-n; // 长度加 1 return OK; } // 删除删除下标 i 处的结点并把它的空间释放掉 Status Delete(headerList* h, int i) { int j; node* p, * q; if (!h-n) // 链表空直接失败 return ERROR; if (i 0 || i h-n - 1) // 注意删除的下界是 0 return ERROR; q h-head; // q 先当前驱用 for (j 0; j i; j) // 走 i 步q 停在待删结点的前驱 q q-link; p q-link; // p 指向真正要删的结点 q-link q-link-link; // 让前驱跳过待删结点 free(p); // 释放待删结点的空间 h-n--; // 长度减 1 return OK; }插入里q-link p-link和p-link q这两行的顺序绝对不能换。先p-link q再接q-link的话原后继会从链表里丢失而且q-link p-link拿到的是自己链表立刻变成环。删除里要特别注意free(p)放在最后先改链接再释放如果先 freep-link已经变成野指针程序前进会访问脏内存表现是时好时坏典型的黑匣子问题。查找操作用同样的思路从头结点出发走i步时间复杂度 O(n)插入删除定位也是 O(n)但定位到之后本身只有几行指针操作这就是链表和顺序表在插入删除上的本质差异——顺序表是移动元素链表是改指针。3.3 初始化、输出和撤销怎么补以及写前先画图的习惯初始化、输出、撤销三个操作补出来如下// 初始化申请表头结点空间链表置空 Status InitList(headerList* h) { h-head (node*)malloc(sizeof(node)); h-head-link NULL; h-n 0; return OK; } // 输出遍历链表打印每个结点的 element Status Output(headerList* h) { node* p h-head-link; while (p) { printf(%d , p-element); p p-link; } printf(\n); return OK; }撤销则要while (h-head-link) { node* p h-head-link; h-head-link p-link; free(p); }最后 free 头结点。我写链表前习惯先在纸上画一排结点用箭头把link标好再对着图写代码这样每个指针指向哪一步里是清楚的写完直接编译通过的概率很高。带表头单链表对应课本程序 2.82.14功能上就是初始化、查找、插入、删除、输出、撤销六件套和顺序表完全对称对比着写会更容易记住。4. 多项式加法和乘法指数 -1 当哨兵按降序存能少踩一半坑4.1 存储设计与按指数降序存储的理由一元多项式用链表存每个结点表示一项包含系数coef和指数exp。头结点的exp固定为-1作为链表的结束哨兵——因为正常指数都大于等于 0读到-1就知道链表走完了。类型定义typedef struct pNode { int coef; // 系数 int exp; // 指数 struct pNode* link; // 指针域 } pNode; typedef struct { struct pNode* head; // 头结点exp 固定为 -1 } polynominal;创建多项式时要把项按指数降序往里插这不是约定俗成的强迫症而是做加法乘法都依赖这个顺序加法里靠指数比较决定指针移动方向乘法里结果链表天然有序最后合并同类项时不用额外排序。创建函数核心就是读入一项后从头结点开始找第一个exp比它小的位置插进去temp-link p-link; p-link temp;两行完成插入。4.2 加法 Add 的实现与三种分支逻辑加法把两个多项式合并结果存到qx里核心是双指针遍历。p指向px当前项q指向qx当前项q1永远是q的前驱方便在需要时插入或删除void Add(polynominal* px, polynominal* qx) { pNode* q, * q1 qx-head; // q1 是 q 的前驱 pNode* p px-head-link; // p 指向 px 的第一项 pNode* p1 px-head, * temp; q q1-link; // q 指向 qx 的第一项 while (p-exp 0) { // p 没读完就继续 while (p-exp q-exp) { // qx 当前指数大跳过它 q1 q; q q-link; } if (p-exp q-exp) { // 指数相等系数相加 q-coef p-coef; if (q-coef 0) { // 相加后归零删掉这个结点 q1-link q-link; free(q); q q1-link; p p-link; } else { q1 q; // 系数非零双双后移 q q-link; p p-link; } } else { // p-exp q-exp把 p 复制一份插入到 q 前面 temp (pNode*)malloc(sizeof(pNode)); temp-coef p-coef; temp-exp p-exp; temp-link q1-link; // 接 q q1-link temp; // 让前驱指向新结点 q1 q1-link; p p-link; } } }三个分支对应三种情况p-exp q-exp说明qx这项指数偏大、px的当前项后面还要比所以q后移p-exp q-exp是合并同类项系数相加后如果归零必须把结点删掉不然结果里会出现0x^5这种脏项p-exp q-exp说明px当前项在qx里没有对应项直接复制一份插到q前面。报告里写加法时间复杂度为 O(n²)如果只看双指针遍历一趟理论上是 O(mn)但实现里有删结点、插新结点和内存分配最坏情况下指针要反复移动课程报告按 O(n²) 保守估计。自己写的时候别只看大 O 记号要清楚代码实际遍历了几趟。4.3 乘法 Multiply逐项相乘再复用一个 Add 合并同类项乘法最朴素的思路是两层循环外层遍历px的每一项内层遍历qx的每一项系数相乘、指数相加得到一个中间多项式再把所有中间多项式加起来。最终版本用qx1存乘积结果每一轮用一个临时多项式qx2存当前项乘出来的结果然后调用上面写好的Add(qx2, qx1)合并同类项void Multiply(polynominal* px, polynominal* qx) { polynominal qx1, qx2; pNode* q1 px-head, * q2, * q3, * q4, * pre; qx1.head (pNode*)malloc(sizeof(pNode)); qx1.head-exp -1; qx1.head-link qx1.head; // 结果多项式先做成循环链表 q2 qx-head-link; // 先处理 px 的第一项结果直接插入 qx1 while (q2-exp ! -1) { q3 (pNode*)malloc(sizeof(pNode)); q3-coef q1-coef * q2-coef; // 系数相乘 q3-exp q1-exp q2-exp; // 指数相加 // 插入 qx1 的尾部和头部……完整插入逻辑见实验代码 q2 q2-link; } q1 q1-link; // px 指针后移一位 while (q1-exp ! -1) { // 处理 px 的剩余每一项 q2 qx-head-link; // 关键每轮都把 q2 重置回 qx 的第一项 qx2.head (pNode*)malloc(sizeof(pNode)); qx2.head-exp -1; qx2.head-link qx2.head; while (q2-exp ! -1) { q4 (pNode*)malloc(sizeof(pNode)); q4-coef q1-coef * q2-coef; q4-exp q1-exp q2-exp; // 把 q4 插入 qx2逻辑同第一轮 q2 q2-link; } Add(qx2, qx1); // 合并这一轮的乘积顺便合并同类项 q1 q1-link; } Output(qx1); }这个实现里最值得记住的思想是“复用”中间多项式出来之后直接调用写好的Add合并而不是再写一遍合并逻辑。乘法的时间复杂度 O(n²)且每次乘法都伴随大量malloc内存开销大所以这个实现适合课程验证型实验不适合实际做大规模多项式运算——那场景下用数组按指数分段存或者直接用快速傅里叶变换复杂度能压到 O(n log n)那是后面算法课的事。4.4 什么时候用顺序存储什么时候用链接存储线性表的两种存储结构在多项式这里的应用边界可以总结成一张表场景顺序存储数组链接存储链表随机查找某一下标O(1)直接取O(n)从头遍历中间插入删除O(n)移动元素O(n)定位后只改指针空间需求需要预分配 maxLength按需申请无空间上限多项式合并需先固定最大指数天然适合稀疏多项式稀疏多项式系数大量为 0 的多项式链表存优势很明显每个结点只存非零项稠密多项式用数组更快。实验里的多项式默认按降序存已经为两种存储选择留好了余地。5. 避坑记录编译能过不算完这四个边界问题当年都翻过车5.1 插入位置 i 传 0数据却跑到下标 1现象在顺序表和链表里调用Insert(list, 0, x)期望结果是 x 在第 0 位打印出来却发现 x 在第 1 位原来的第 0 位元素还在。原因Insert的参数i是前驱下标新元素固定放到i1处插入第 0 位时正确的调用是Insert(list, -1, x)。解决调用前先想清楚这次插入是“插到第几位”如果需要插入到下标 k传入的 i 是 k-1往末尾追加时 i 传n-1。这个语义和Delete不一样删除直接传待删元素下标混用必错。5.2 顺序表空间满没判断数组越界写一路写到脏内存现象程序不报错但插着插着顺序表里出现莫名其妙的随机值严重时直接崩溃。原因Insert里漏写if (seqList-n seqList-maxLength) return ERROR;插入次数超过容量后element[n]越界写写到堆上相邻的内存块破坏掉别的数据。解决把空间满判断放在插入函数最前面实验报告的原始代码也踩过这个坑后来加了溢出报错功能才解决。调试方法是在插入函数入口打印n和maxLength连续插十次看容量变化一眼就能定位。5.3 插入移动元素时从前往后移数组里全是重复值现象在顺序表下标 2 处插入后打印出来的数组出现数据覆盖某个值重复出现两次另一个值凭空消失。原因element[j1] element[j]如果从j i开始正向移动element[i1]的原值还没搬走就被element[i]覆盖搬到后面时被覆盖的值又来自更前面整段数据全部错乱。解决严格按for (j n-1; j i; j--)从后往前搬。判断移动方向很简单插入位置后面的元素要先让出位置必须从最远的那个开始动离插入位置最近的那个最后动。5.4 多项式乘法第二次遍历 q 指针没重置结果缺项或野指针现象乘法结果多项式项数少于理论值或者程序运行到一半访问野指针崩溃。原因第一轮内层循环结束后q2已经走到qx链表的末尾哨兵进入第二轮外层循环时如果还用q2 q2-link继续走等于在哨兵后面往下访问完全丢掉了qx的第一项还可能踩到非法内存。解决每个外层循环开始前执行q2 qx-head-link;把内层指针拉回qx的第一项。这是多项式乘法里最容易出问题的指针重置写完后用一个三项乘三项的用例打印每轮乘积结果缺不缺项一目了然。加一条附带提醒加法里系数相加为 0 时一定要删结点并重置指针否则结果多项式里会出现0x^5这种项后续乘法把 0 系数带进去整个结果全错而且这种错在视觉上极难发现只能靠打印每一步结果排查。6. 收尾验证用“降序输出”这一个标准就能看出多项式写没写对三份代码写完怎么快速确认不是“编译通过但逻辑全错”我一般按下面的顺序做验证。先给顺序表和链表喂同一组操作序列初始化后依次插入 5 个元素删除第 0 位删除末位查找第 2 位。每步操作后打印当前n和全部元素顺序表的输出必须是连续的数组排列链表的输出必须按插入顺序排列。n从 5 变 4 再到 3查找结果与中间状态一致这两份基础代码才算过。多项式用一组能手算验证的测试数据。设 A 5x² 3x 7B 4x 2手算乘积5x² * 4x 20x³5x² * 2 10x²3x * 4x 12x²3x * 2 6x7 * 4x 28x7 * 2 14合并同类项后是 20x³ 22x² 34x 14。把这段输出和程序结果逐项对重点确认三点指数是否严格降序、系数是否合并过、有没有出现 0 系数项。再补边界测试四组按我常踩的顺序来测试用例预期结果空多项式加空多项式结果为空不能崩单项式乘单项式结果只有一项系数乘指数加A (-A)所有项系数归零链表清空A * 1系数 1 指数 0结果等于 A 本身最后一组最容易暴露 4.3 节说的指针重置问题如果 A * 1 的结果不是 A说明乘法循环的指针重置写得不对直接回到q2 qx-head-link那行检查。从那以后我每次写完链表和多项式都强制在提交前让“空表、表头、表尾、合并归零”这四组用例完整走一遍确认free不崩、输出严格降序才敢说这个实验真正做完了。希望帮到你。本文还有配套的精品资源点击获取