没有合适的资源?快使用搜索试试~ 我知道了~
实验1:线性表应用1
需积分: 0 2 下载量 176 浏览量
2022-08-08
19:30:26
上传
评论 1
收藏 279KB DOCX 举报
温馨提示
试读
14页
实验报告学院(系)名称:计算机科学与工程学院姓名王帆学号20152180专业计算机科学与技术班级15级1班实验项目实验一:线性表应用课程名称数据结构与算法课程代
资源推荐
资源详情
资源评论
实验报告
学院(系)名称:计算机科学与工程学院
姓名
王帆
学号
20152180
专业
计算机科学与技术
班级
15 级 1 班
实验项目
实验一:线性表应用
课程名称
数据结构与算法
课程代码
0668016
实验时间
2017 年 3 月 10 日 第 5 节
实验地点
7-219
考核
标准
实验过程
25 分
程序运行
20 分
回答问题
15 分
实验报告
30 分
特色
功能
5 分
考勤违
纪情况
5 分
成绩
成绩
栏
考核
内容
评价在实验
课堂中的表
现,包括实
验态度、编
写程序过程
等内容等。
□功能完善,
□功能不全
□有小错
□无法运行
○正确
○基本正确
○有提示
○无法回答
○完整
○较完整
○一般
○内容极少
○无报告
○有
○无
○有
○无
其它批改意见:
教师签字:
一、实验目的
1、 掌握用 C 或 C++上机调试线性表应用的基本方法;
2、 掌握线性表的基本操作,如插入、删除、查找,以及线性表合并等运算在顺序存储结构和
链式存储结构上的运算;并能够运用线性表基本操作解决问题,实现相应算法。
二、实验题目与要求
1、已知单链表 L(带头节点)是一个递增有序表,试编写一算法,删除表中值大于 min 且小
于 max 的节点(若表中有这样的节点),同时释放被删节点的空间,这里 min 和 max 是两个给
定参数。请分析算法时间复杂度。
2、约瑟夫环问题
1)问题描述:有编号为 1, 2…n 的 n 个人按顺时针方向围坐一圈,每人持有一个正整数
密码。开始给定一个正整数 m,从第一个人按顺时针方向自 1 开始报数,报到 m 者出列,
不再参加报数,这时将出列者的密码作为 m,从出列者顺时针方向的下一人开始重新自 1
开始报数。如此下去,直到所有人都出列。试设计算法,输出出列者的序列。
2)实验要求:采用顺序和链式两种存储结构实现
3、一元稀疏多项式简单的计算器
1)问题描述:用线性表表示一元稀疏多项式,设计一个一元多项式运算器
2)实验要求: 采用单链表存储结构一元稀疏多项式,输入并建立多项式,输出多项式,
实现多项式加、减运算。
三、 实验过程与实验结果
实验 1-01:单链表基本操作
算法思路简介与描述:
本实验需要实现以下操作:
1.利用尾插法建立单链表(输入从小到大)
2.给定最大值与最小值,删除单链表内符合要求的节点
3.输出整个单链表
对于链表的操作主要依赖于指针的变换。
1. 尾插法建立单链表在课内已有阐述,即动态分配内存空间->存储数值->建立与前一节点的联系。
2. 输出单链表:利用 next 指针域对单链表进行遍历的思想,将每次结果进行输出。
3. 本题比较关键的删除最大值最小值之间的节点,则需要运用判断与循环条件,先判断给定的两个值与
链表内各节点值的关系,如果超过范围,链表空等情况则以输出“-1”结束,否则进行删除操作。删除
操作的思想是对 next 域内地址的操作,即将两个节点的联系进行变换,断开即将删除节点与前后的联
系,然后释放。
算法实现与测试结果(参考 OJ):
实验 1-02:约瑟夫环问题
算法思路简介与描述:
本实验需要实现以下操作:
1. 建立单循环链表,其中包括两个数据域(ID 与 PW)以及 next 指针域。
建立链表的过程与上一个实验类似,本实验中可以使用不带头节点的单循环链表,我选择了常规带头
节点的单循环链表,最后的差异是将需将末尾元素的指针域指向头节点以构成闭环操作。
2. 给定初始值对链表进行初始化,给定初始密码 m,删除单链表内符合要求的节点,并迭代实现直到结
束。
在本实验中,除了初始化链表以外,我将删除操作分成几个部分,包括 1.通过 PW 与上一轮的 ID 找到
对应出列 ID 的节点位置,2.删除对应 ID 的节点,3.按顺序输出删除元素的序号。
本功能直接在删除内实现,并对其加以格式化操作。
本实验难点:格式化操作
算法实现与测试结果(参考 OJ):
实验 1-03:一元稀疏多项式简单的计算器实现
算法思路简介与描述:
本实验需要实现以下操作:
1. 利用尾插法建立多项式单链表
与实验 1 相同,差别于多项式链表的数据区域是两块(指数域与系数域),因此不再赘述。
2. 对两个多项式进行加减运算,结果显示在第一个多项式中
加法的实现思想是通过对两个多项式链表同时进行遍历,存在着以下情形:
1. 指数相同,系数直接相加。
2. 指数不相同,进行比较
1.A>B,先输出 B 的节点,然后指针移动,再次比较。
2.A<B,先输出 A 的节点,然后指针移动,再次比较。
直到对两个链表都遍历完毕,此时运算结束,将新多项式的头指针返回。
这里特别注意减法的实现,因为第一个多项式减去第二个多项式存在出现负系数的情况,所以相对于
加法只需要加上(-)的情形。
3. 输出两个多项式
运用链表遍历的思想,实现方法与实验 1 相同。
算法实现与测试结果(参考 OJ):
四、 收获与体会
通过本次实验,我加深了对线性表操作的理解。对于线性表基本的增删改查操作有了更进一步的掌握。本
次实验中最大的难点在于对指针的操作以及在 OJ 平台上调试过程中的格式化输出。本次实验充分利用了
TJUT OJ 平台,在线操作的同时也能更加精确地发现在编程中存在的问题。因此,在今后的学习过程中,
我将通过更多的方式对这些弱点与问题进行强化和修正,在实践中成长。
五、 源代码清单
剩余13页未读,继续阅读
资源评论
武藏美-伊雯
- 粉丝: 19
- 资源: 352
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功