2022年北邮数据结构实验报告实验一线性表.pdf

《2022年北邮数据结构实验报告实验一线性表.pdf》由会员分享，可在线阅读，更多相关《2022年北邮数据结构实验报告实验一线性表.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验名称：实验一线性表题目1学生姓名：申宇飞班级：信通 3 班班内序号： 03学号： 64日期： 2013 年 11 月 4 日1. 实验要求实验目的：熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表线性表的基本功能：1、 构造：使用头插法、尾插法两种方法2、 插入：要求建立的链表按照关键字从小到大有序

2、3、 删除4、 查找5、 获取链表长度6、 销毁7、 其他：可自行定义编写测试 main() 函数测试线性表的正确性。2.程序分析存储结构链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 7 页 - - - - - - - - - - 链表的结

3、点结构? ? datanext ? ? data 域- 存放结点值的数据域? next 域- 存放结点的直接后继的地址（位置）的指针域（链域）地址内存单元1000H头指针 1020H1080H10C0Hfront 关键算法分析1、关键算法： 1 ：头插法自然语言描述： a:在堆中建立新结点 b:将 ai写入到新结点的数据域c: 修改新结点的指针域d: 修改头结点的指针域。将新结点加入链表中伪代码描述a:Node * s=new Node b:s-data=ai c:s-next=front-next; d:front-next=s 2：尾插法自然语言描述：a: 在堆中建立新结点：b: 将 ai

4、写入到新结点的数据域：c: 将新结点加入到链表中d: 修改修改尾指针伪代码描述a:Node * s=new Node a31080Ha110C0Ha4a21000H精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 7 页 - - - - - - - - - - b:s-data=ai c:r-next=s; d:r=s 3：析构 / 删除函数自然语言描述：a: 新建立一个指针，指向头结点b: 判断要释放的结点是否存在，c: 暂时保存要释放的结点d: 移动 a 中建立的指针e: 释放要释放的指针伪

5、代码描述a:Node * p=front b:while(p) c:front=p d:p=p-next e:delete front 4：按位查找函数自然语言描述：a: 初始化工作指针p 和计数器j ，p 指向第一个结点，j=1 b: 循环以下操作，直到p 为空或者 j 等于 1 b1：p 指向下一个结点b2：j 加 1 c: 若 p 为空，说明第i 个元素不存在，抛出异常d: 否则，说明p 指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node * p=front-next;j=1; b:while(p&j!=1) b1:p=p-next b2:j+ c:if(!p) throw

6、”error ”d:return p 5：按位查找函数自然语言描述：a: 初始化工作指针p 和计数器j ，p 指向第一个结点，j=1 b: 循环以下操作，找到这个元素或者p 指向最后一个结点 b1：判断p指向的结点是不是要查找的值，如果是，返回j ，否则p 指向下一个结点，并且j的值加一c: 如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node * p=front-next;j=1; b:while(p) b1: if(p-next=x) return j p=p-next j+ 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载

7、 名师归纳 - - - - - - - - - -第 3 页，共 7 页 - - - - - - - - - - c:return “error ”6：插入函数自然语言描述：a: 在堆中建立新结点b: 将要插入的结点的数据写入到新结点的数据域c: 修改新结点的指针域d: 修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node * s=new Node ; b:s-data=p-data c:s-next=p-next d:p-next=s e:p-data=x 7：删除函数自然语言描述：a: 从第一个结点开始，查找要删除的位数i 前一个位置i-1的结点b: 设 q 指向第 i

8、 个元素c: 将 q 元素从链表中删除d: 保存 q 元素的数据e: 释放 q 元素伪代码描述a:q=p-next b:p-next=q-next c:x=q-data d:delete q 8：遍历打印函数自然语言描述：a: 判断该链表是否为空链表，如果是，报错b: 如果不是空链表，新建立一个temp 指针c: 将 temp 指针指向头结点d: 打印 temp 指针的 data 域e: 逐个往后移动temp 指针，直到temp 指针的指向的指针的next 域为空伪代码描述If front-next=NULL Throw ”an empty list ”Node* temp=front-nex

9、t; while(temp-next) coutdatanext; 9：获取链表长度函数自然语言描述：a: 判断该链表是否为空链表，如果是，输出长度0 b: 如果不是空链表，新建立一个temp 指针，初始化整形数n 为 0 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 7 页 - - - - - - - - - - c: 将 temp 指针指向头结点d: 判断 temp 指针指向的结点的next 域是否为空，如果不是，n 加一，否则return n e: 使 temp 指针逐个后移，重复d

10、操作，直到temp 指针指向的结点的next 域为 0，返回 n 伪代码描述 int n=0 if ront-next=NULL n=0; else Node* temp=front-next; while(temp-next) n+; temp=temp-next; return n;2、代码详细分析：（1）从第一个结点开始，查找节点，使它的数据比x 大，设 p 指向该结点：while (xp-data) p=p-next;（2）新建一个节点s，把 p的数据赋给 s： s-data=p-data;（3）把s加到 p后面： s-next=p-next; p-next=s;（4）p节点的数据用

11、x替换： p-data=x;示意图如图所示pxp-data s3、 关键算法的时间复杂度：O （1)3. 程序运行结果程序截图精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 7 页 - - - - - - - - - - 1. 流程图：2. 测试条件：插入、删除元素的位置一定要在链表的长度范围之内。3. 测试结论：可以正确的对链表进行插入，删除，取长度，输出操作。且插入任意一个元素后，链表的顺序依然是由小到大。4. 总结1. 调试时出现的问题及解决的方法：（1）刚开始时用NULL置空最后一个节

12、点的指针域，发现调试时出现NULL未声明的情况。最后发现用0 去置空最后一个节点的指针域，调试成功。（2）刚开始遍历总是不能完全遍历链表。最后发现循环语句中两个句子顺序写反，更正顺序后，调试成功。2. 心得体会：开始初始化一个对象初始化一个整形数组，作为赋值准备分别利用头插法和尾插法初始化，并且用遍历打印函数来显示数值执行删除函数，之后遍历打印函数来测试是否真的删除执行插入函数，之后遍历打印函数来测试是否真的插入执行按位查找和按值查找函数结束精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 7

13、页 - - - - - - - - - - 这道题是相对比较基础，目的是实现线性表的基本功能，书上也几乎给出了所有的模板类的定义， 但是在自己进行编程时还是出了很多问题。通过这个实例， 我对模板类的定义与使用有了个初步的了解，了解了单链表的基本的操作和函数实现。以后必须自己动手编，实现理论与实践相结合，提高自己的编程能力。3. 下一步的改进：这个程序的交互性不强，可以改进的地方应该是可以从外部输入数组而不仅仅是编程者给定。此外，显示的界面不够友好，有待改善，而且可以增加完善的报错机制。此外，也希望老师能在课上给出更多的优化指导。代码#include iostreamusing namespace std;template struct NodeT data;struct Node * next;template class LinkListpublic:LinkList() LinkList();return 0;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 7 页 - - - - - - - - - -