一元稀疏多项式计算器实习报告[1]

实习报告实习报告 题目 设计一个一元稀疏多项式计算器 班级 姓名 学号 完成日期 一 课程题目 一元稀疏多项式计算器 二 需求分析 1 一元稀疏多项式简单计算器的功能是 1 1 输入并建立多项式 1 2 输出多项式 输出形式为整数序列 n c1 e1 c2 e2 cn en 其中 n 是多项式的项数 ci 和 ei 分别是第 i 项的系数和指数 序列按 指数降序排列 1 3 求多项式 a b 的导函数 1 4 计算多项式在 x 处的值 1 5 多项式 a 和 b 相加 建立多项式 a b 1 6 多项式 a 和 b 相减 建立多项式 a b 2 设计思路 2 1 定义线性表的动态分配顺序存储结构 2 2 建立多项式存储结构 定义指针 next 2 3 利用链表实现队列的构造 每次输入一项的系数和指数 可以输出 构造的一元多项式 3 测试数据 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 三 概要设计 1 有序表的抽象数据类型定义为 ADT List 数据对象 D ai ai R i 1 2 n n 0 数据关系 R1 ai 1 ai D ai 1 ai i 1 2 3 n 基本操作 InitList 操作结果 构造一个空的有序表 L DestroyList L 初始条件 有序表 L 已存在 操作结果 销毁有序表 L ListLength L 初始条件 有序表 L 已存在 操作结果 返回有序表 L 的长度 ClearList L 初始条件 有序表 L 已存在 操作结果 清空链表内容 Ins before N N 初始条件 有序表 L 已存在 操作结果 插入节点到链表 ADT OrderedList 2 多项式的抽象数据类型定义为 ADT Poly 数据对象 D ai ai为实数 i 1 2 n 数据关系 R1 基本操作 CreatePoly L N 初始条件 N 为节点 L 为有序表 操作结果 将 N 插入多项式的适当位置 GetPoly L 操作结果 将用户输入转换为节点 PrintPoly L 初始条件 多项式 L 已存在 操作结果 显示多项式 AddPoly L 1 L 2 L add 初始条件 多项式 L 1 L 2 L add 已存在 操作结果 生成 L 1 L 2 之和的多项式 L add DiffPoly L L diff 初始条件 多项式 L L diff 已存在 操作结果 生成 L 的导数多项式 L add AlterPoly L 初始条件 多项式 L 已存在 操作结果 将 L 多项式取相反数 ADTADT Poly 三 详细设计 1 Constant h ifndef constant define constant include include define TURE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2 typedef int Status endif 2 Polynt h include constant h typedef struct elemType float coef 系数 int expn 指数 ElemType typedef struct node ElemType data 指向结点元素的值 struct node next 后继 Node Polyn 结点类型 指针类型 typedef struct Node head Node tail List Status MakeNode Polyn 分配由 p 指向的数 据元素为 e 后继为 空 的结点 Status InitList List 构造链表 Status DestroyList List 销毁线性表 void Insert List 将 s 指向的结点插 入 L 的最后一个结点 void Insbefore Polyn p Polyn q Status CreatPolyn List 创建 一个一元多项式 polynomial 并输入 m 项的指数和系数 void PrintPolyn List L 打印输出一元多 项式 void AlterPoly List L 减法 void AddPolyn List L1 List L2 List 多项式加法 3 Polyn cpp include Polynt h Status MakeNode Polyn p data coef e coef p data expn e expn p next NULL return OK Status InitList List Polyn p e coef e expn MakeNode p e L head p L tail p return OK Status DestroyList List if L head L tail free L head L head L tail NULL return OK p L head next while p q p next free p p q L head L tail NULL return OK void Insert List s next NULL L tail s else if L head next NULL L head next s return if L tail data expn s data expn L tail next s L tail s return for Polyn p L head next p NULL p p next if s data expn p data expn p data coef s data coef free s return else if p data expn s data expn p next s return Status CreatPolyn List Polyn p for int i 0 inext while p NULL if p L head next if p data coef 0 if p data expn 0 printf gx d p data coef p data expn else printf g p data coef else if p data coefdata expn 0 printf gx d p data coef p data expn else printf g p data coef else printf p p next else if p L head next else printf g p data coef else if p data coefdata expn 0 printf gx d p data coef p data expn else printf g p data coef else printf p p next else return void AlterPoly List L for Polyn p L head next p NULL p p next p data coef 1 void AddPolyn List L1 List L2 List p1 L1 head next p2 L2 head next while p1 NULL Insert L3 p3 p1 p1 next else if p1 data expndata expn MakeNode p3 p2 data Insert L3 p3 p2 p2 next else if p1 data expn p2 data expn MakeNode p3 p2 data p3 data coef p1 data coef p2 data coef p3 data expn p1 data expn Insert L3 p3 p1 p1 next p2 p2 next if p1 NULL Insert L3 p3 p2 p2 next else if p2 NULL Insert L3 p3 p1 p1 next 4 main cpp include Polynt h include include void main system cls printf n printf 欢迎使用一元稀疏多项式计算 n printf n printf 1 创建多项式 A 2 创建多项式 B 3 相加 4 相减 5 退 出 n List polynomialA polynomialB polynomialC InitList polynomialA InitList polynomialB InitList polynomialC char poly int m int n 1 for printf 请输入指令 poly getchar switch poly case 1 创建多项式 A printf 请输入多项式 A 的项数 scanf d printf n 请 输 入 多 项 式 A CreatPolyn polynomialA m printf n 多项式 A 是 PrintPolyn polynomialA printf n break case 2 创建多项式 B printf 请输入多项式 B 的项数 scanf d printf n 请 输 入 多 项 式 B CreatPolyn polynomialB m printf n 多项式 B 是 PrintPolyn polynomialB printf n break case 3 加法 printf 结果是 AddPolyn polynomialA polynomialB polynomialC PrintPolyn polynomialC printf n break case 4 减法 printf 结果是 AlterPoly polynomialB DestroyList p