1305120617-魏伟-计工02班-实验2

计算机科学与工程学院计算机科学与工程学院 算法与数据结构算法与数据结构 实验报告实验报告 二二 专业班级 2013 级计算机工程专 业 02 班 实验地点403 机房 学生学号 1305120617 指导教师蔡琼 学生姓名魏伟实验时间 2015 04 11 实验项目链表的应用 实验类别基础性 设计性 综合性 其它 实验目的 及要求 1 熟练掌握链表结构及有关算法的设计 2 掌握用链表表示特定形式的数据的方法 并能编写出有 关运算的算法 成 绩 评 定 表 类 别评 分 标 准分值得分合 计 上机表现 积极出勤 遵守纪律 按要求完成设计任务 3030 分 程序与报告 程序代码规范 功能正确 报告详实完整 体现收获 7070 分 说明 说明 评阅教师 评阅教师 蔡琼蔡琼 日日 期 期 20152015 年年 4 4 月月 1818 计算机科学与工程学院 算法与数据结构 实验报告2 日日 实 验 内 容 计算机科学与工程学院 算法与数据结构 实验报告3 一 实验内容 一元多项式求和 把任意给定的两个一元多项式 P x Q x 输入计算机 计算它们的和 并输出计算结果 实验说明 一元多项式可以用单链表表示 结点结构图示如下 一元多项式算法伪代码如下 二 设计思路 本程序中 要求用户输入两个一元多项式 将其分别存入两个线性链表中 待计算机将其求和后 将最后结果存入另一个线性链表中 并输出结果 根据 一元多项式链表的结点结构 coef exp next 1 工作指针 p q 初始化 2 while p 存在且 q 存在 执行下列三种情形之一 2 1 如果 p expexp 则指针 p 后移 2 2 如果 p exp q exp 则 2 2 1 将结点 q 插入到结点 p 之前 2 2 2 指针 q 指向原指结点的下一个结点 2 3 如果 p exp q exp 则 2 3 1 p coef p coef q coef 2 3 2 如果 p coef 0 则执行下列操作 否则 指针 p 后移 2 3 2 1 删除结点 p 2 3 2 2 使指针 p 指向它原指结点的下一个结点 2 3 3 删除结点 q 2 3 4 使指针 q 指向它原指结点的下一个结点 3 如果 q 不为空 将结点 q 链接在第一个单链表的后面 计算机科学与工程学院 算法与数据结构 实验报告4 需求 需构造线性链表存储结构 创建三个空链表 和三个函数 一个为求和 函数 一个为输入函数 一个为输出函数 求和函数中应包括一元多项式中各 系数的的比较 相加排序等 采用顺序存储结构存储多项式系数 A 使多项式的某些运算变得更简洁 但 在实际使用时 多项式的阶数可能很高 不同的多项式阶数可能相差很大 这 使顺序存储结构的最大长度难以确定 而且 最高次幂与最低次幂项之间缺项 很多时 采用顺序存储结构显然十分浪费存储空间 因此 一般情况下多采用 链式存储结构来存储高阶多项式 在用线性链表来存储一个多项式时 多项式中的每个非零项系数对应一个结点 结点由数据元素项和指针组成 数据元素项中包含系数和指数值 设计中先定义定义数据元素中的数据 其中有指数 系数级指针 next 等 并要 先构造一元多项式 在定义输出 删除 合并等模块 实 验 内 容 计算机科学与工程学院 算法与数据结构 实验报告5 三 预期结果 a 3x 4 2x 3 5x 2 x b 7x 4 5x 3 3x 2 x 输出为 c 10 x 4 3x 3 2x 2 2x 四 程序代码 include include typedef struct LNode int x z struct LNode next LinkList void OutLinkList LinkList L 输出函数 void PutLinkList LinkList 输入函数 LinkList AddLinkList LinkList a LinkList b 求和函数 void OutXLinkList LinkList L void OutZLinkList LinkList L void main int n m LinkList a b c printf 请输入一元多项式 a 的项数 m scanf d printf 请按照从低次到高次的顺序依此输入一元多项式 a 的系数和指数 n PutLinkList a m printf a OutLinkList a printf 请输入一元多项式 b 的项数 n scanf d printf 请按照从低次到高次的顺序依此输入一元多项式 b 的系数和指数 n PutLinkList b n printf b OutLinkList b c AddLinkList a b printf 两个多项式的和为 na b OutLinkList c void PutLinkList LinkList L LinkList malloc sizeof LinkList r L for int i 0 ix printf 请输入第 d 项的指数 i 1 scanf d r next s r s r next NULL 多项式输出函数 void OutLinkList LinkList L char FuHao LinkList p L next FuHao p x 0 if FuHao printf c FuHao if p x 1 printf 1 OutXLinkList p OutZLinkList p p p next while p NULL FuHao p x 0 printf c FuHao OutXLinkList p OutZLinkList p p p next printf n 输出系数函数 void OutXLinkList LinkList L int xi L x 0 L x L x if L x 1 L x 1 else printf d xi 计算机科学与工程学院 算法与数据结构 实验报告7 输出指数函数 void OutZLinkList LinkList L if L z 0 else if L z 1 L z 1 if L zx 1 L x 1 printf 1 printf printf X else if L zz 0 L z L z printf X d zhi LinkList AddLinkList LinkList a LinkList b a a next b b next LinkList c d s c LinkList malloc sizeof LinkList d c while a NULL s x b x s z b z d next s d s b b next else if a z b z s LinkList malloc sizeof LinkList s x a x 计算机科学与工程学院 算法与数据结构 实验报告8 s z a z d next s d s a a next else s LinkList malloc sizeof LinkList s x a x b x s z a z if s x 0 else d next s d s a a next b b next if a NULL d next a else if b NULL d next b else d next NULL return c