数据结构课程设计(一元稀疏多项式计算器)

实习报告 1 5 题 一元稀疏多项式计算器 实习报告实习报告 题目 设计一个一元稀疏多项式简单计算器 班级 计科一班 姓名 康宇 学号 完成日期 2013 4 15 一 需求分析一 需求分析 1 一元稀疏多项式简单计算器的功能是 1 输入并建立多项式 2 输出多项式 输出形式为整数序列 n c1 e1 c2 e2 cn en 其中 n 是 多项式的项数 ci 和 ei 分别是第 i 项的系数和指数 序列按指数降序排列 3 多项式 a 和 b 相加 建立多项式 a b 4 多项式 a 和 b 相减 建立多项式 a b 5 计算多项式在 x 处的值 6 求多项式 a b 的导函数 2 测试数据 1 2x 5x 8 3 1x 11 7 5x 8 11x 9 3 1x 11 11x 9 2x 7 2 6x 3 x 4 4x 2 1 2x 9 1 2x 9 6x 3 5 4x 2 x 2 7 8x 15 7 8x 15 1 2x 9 12x 3 x 3 1 x x 2 x 3 x 4 x 5 x 3 x 4 1 x x 2 x 5 4 x x 3 x x 3 0 5 x x 100 x 100 x 200 x 2x 100 x 200 6 x x 2 x 3 0 x x 2 x 3 二 概要设计二 概要设计 为实现上述程序功能 应以有序链表来表示多项式的系数和指数 定义线性表的动 态分配顺序存储结构 建立多项式存储结构 定义指针 next 利用链表实现队列的构造 每次输入一项的系数和指数 可以输出构造的一元多项式 演示程序以用户和计算机的对话方式执行 即在计算机终站上显示 提示信息 之后 由 用户在键盘上输入演示程序中规定的运行命令 最后根据相应的输入数据 滤去输入中的 非法字符 建立的多项式以及多项式相加的运行结果在屏幕上显示 1 元素类型 结点类型和指针类型 typedef struct LNode float xishu 系数 int zhishu 指数 struct LNode next LNode Linklist 2 建立两个全局链表指针 Linklist List1 NULL Linklist List2 NULL 用来存放两个多项式 然后在 main 函数里调用输入函数 3 本程序包括 7 个模块 1 主程序 Void main While 1 输出菜单 接受命令 处理命令 If 命令 退出 则程序退出 释放链表 2 输入函数 Void Input 调用插值函数 In List1 处理链表一 调用插值函数 In List2 处理链表二 3 输出函数 Void Output 调用输值函数 Out List1 处理链表一 调用输值函数 Out List2 处理链表一 4 相加函数 Void Add if List1 节点指数 List2 节点指数 输出 List1 节点 指针后移 else if List1 节点指数 List2 节点指数 输出 List1 节点 指针后移 else if List1 节点指数 List2 节点指数 输出 List2 节点 系数要取负再输出 指针后移 Else 两链表指针都后移 if 链表 1 到头 输出链表 2 剩余的节点 else 即链表二到头 输出链表 1 剩余的节点 6 求值函数 void Calc 输入 x 的值 依次调用链表一的节点 求出单项式的值相加后输出 7 求导函数 void Daohanshu 输出多项式一的导函数 三 详细设计三 详细设计 include include include typedef struct LNode 元素类型 float xishu int zhishu struct LNode next LNode Linklist Linklist List1 NULL Linklist List2 NULL Linklist In Linklist L 依次往链尾插 Linklist p float a int b Linklist head Linklist malloc sizeof LNode L head head zhishu 0 head zhishu 头结点放的是多项式的项数 p head p next NULL printf 请输入一个多项式 n while scanf f d head zhishu printf 3d n L zhishu Linklist q Linklist malloc sizeof LNode q xishu a q zhishu b if p next NULL p next q q next NULL p head else if p next zhishuzhishu q next p next p next q p head else p p next printf 您已成功输入一个多项式 n return L void Input List1 In List1 List2 In List2 void Out Linklist L Linklist p p L next printf 此多项式有 3d 项 L zhishu while p NULL 按指数由大到小输出 printf 0 1f 3d p xishu p zhishu p p next printf n void Output printf 第一个多项式为 n Out List1 printf 第二个多项式为 n Out List2 void Add Linklist p1 p2 p1 List1 next p2 List2 next printf 相加后的多项式为 n while p1 p1 p1 next else if p1 zhishuzhishu printf 0 1f 3d p2 xishu p2 zhishu p2 p2 next else printf 0 1f 3d p1 xishu p2 xishu p1 zhishu p1 p1 next p2 p2 next if p1 NULL while p2 printf 0 1f 3d p2 xishu p2 zhishu p2 p2 next else while p1 printf 0 1f 3d p1 xishu p1 zhishu p1 p1 next printf n void Sub Linklist p1 p2 p1 List1 next p2 List2 next printf 相减后的多项式为 n while p1 p1 p1 next else if p1 zhishuzhishu printf 0 1f 3d p2 xishu p2 zhishu p2 p2 next else if p1 xishu p2 xishu 0 printf 0 1f 3d p1 xishu p2 xishu p1 zhishu p1 p1 next p2 p2 next if p1 NULL while p2 printf 0 1f 3d p2 xishu p2 zhishu p2 p2 next else while p1 printf 0 1f 3d p1 xishu p1 zhishu p1 p1 next printf n void Calc int x double sum 0 Linklist p printf 请输入 x 的值 scanf d p List1 next while p sum p xishu pow x p zhishu p p next printf 多项式 1 在 x 处的值为 0 1lf sum printf n void Daohanshu Linklist p p List1 next printf 多项式 1 的导函数为 n while p printf 0 1f 3d p xishu p zhishu p zhishu 1 p p next printf n int main int num while 1 printf n printf 1 输入并建立多项式 n printf 2 输出其指系数排列 n printf 3 多项式相加 n printf 4 多项式相减 n printf 5 计算多项式在 x 处的值 n printf 6 求多项式 a 的导函数 a n printf 0 退出 n printf n printf 请输入您要选择的功能 scanf d switch num case 1 Input break 输入函数 case 2 Output break 输出函数 case 3 Add break 函数相加 case 4 Sub break 函数相减 case 5 Calc break 计算函数在 x 处的值 case 6 Daohanshu break 求函数的导函数 case 0 exit 1 default printf 输入错误 请重新输入 free List1 free List2 return 0 四 调试分析四 调试分析 1 由于链表是设置成为全局变量 所以任意函数都可以修改它 存在一定风险性 但 这也为后来的函数方便了 所有的函数统一没有参数 2 刚开始时曾忽略了一些变量的类型以及没有考虑到指针的返回问题 使调试程序浪 费了一定的时间 今后应重视确定参数的变量和赋值属性的区分和标识 3 本程序模块简洁 在 main 函数里得到充分体现 4 链表默认用户输入是按指数从小到大的顺序输入的 而默认输出时按指数从大到小 输入时 依次把节点插在