稀疏一元多项式运算器 实验报告 附源程序

信息学院 12 级 杨征元 PB12210247 13 10 25 稀疏一元多项式运算器稀疏一元多项式运算器 问题描述问题描述 完成一元稀疏多项式运算器 完成多项式创建 显示 复制 求和 求差 求 值 销毁 清空 修改 n 阶微分 不定积分 定积分操作 函数功能描述如下 稀疏一元多项式运算器 0 退出 退出 1 创建多项式 创建并打印 2 显示多项式 打印 3 复制多项式 复制多项式 a 至空域 b 非空报错 4 求和 输入 abc 位置 c a b 5 求差 输入 abc 位置 c a b 6 求值 输入位置 double x 输出 double result 7 销毁多项式 销毁 使 p i 为 NULL 8 清空多项式 清空保留头指针 输出为 0 9 修改多项式 选择插入 删除 修改 删了再插 10 n 阶微分 输入微分位置 阶数 结果存放于原位置 11 不定微分 输入积分位置 不定积分 常数 C 取 0 12 定微分 输入积分位置 上下限值 输出定积分结果 算法描述算法描述 通过主菜单调用函数完成各项功能 函数描述见程序结构描述部分 数据结构描述数据结构描述 多项式每一项结点定义如下 typedef struct lnode double coef int exp struct lnode next lnode linklist 包含指向下一结点指针 linklist next 存储系数的数据单元 double coef 存储指数的数据单 元 int exp 结点名 lnode 指向结点指针 linklist 每一个多项式由头指针引出 头指针数组 lnode p N 每一个单元存储一多项式头指针 当多项式不存在 p i NULL 多项式为空 p i next NULL 即只存在头指针 操作函数见程序结构描述部分 程序结构描述程序结构描述 函数包括创建结点函数 有序插入函数 打印函数 创建多项式函数 多项式清空函数 多项式销毁函数 求值函数 求和函数 求差函数 复制函数 删除结点函数 修改函数 n 阶微分函数 不定积分函数 对函数原型 功能 借口逐一描述如下 1 创建结点函数 函数原型 linklist makenode double coef int exp 输入 double 型系数项 int 型指数项 创建 lnode 结点 返回指向结点的 linklist 指针 功能 创建新结点 在复制函数以及输入系数指数插入结点时 修改多项式 调用 2 有序插入函数 函数原型 void insert linklist phead linklist head 输入插入结点指针 phead 以及多项式头指针 head 无返回值 功能 新结点 phead 有序插入头结点为 head 的多项式内 按指数项降序排列 在创 建 复制 修改函数中调用 3 打印函数 函数原型 void printlinklist linklist phead 输入待打印多项式头指针 phead 无返回值 分别打印系数项和指数项 打印系数项是使用 g 输入取消无效 0 通过特殊情况讨论 如 exp 0 exp 1 首项的加号等情况 使多项式输出符合书写习惯 功能 打印多项式 4 创建多项式 函数原型 linklist creatlist 返回创建多项式头指针 调用时先在主函数中输入该多项式头指针在头指针数组中位 置 实现 先若该位置无多项式 申请头结点 之后新建数据结点 有序插入头结点对应 多项式 5 清空多项式 函数原型 void linklistclear linklist head 输入待清空多项式头结点 无返回值 将 p i 仅保留头结点 实现 用前后两指针 遍历多项式并逐一删去结点 最后将头指针的 next 域置 NULL 6 销毁多项式 函数原型 void linklistdestroy linklist int exp struct lnode next lnode linklist define N 20 lnode p N NULL p 初始化 linklist makenode double coef int exp 构造结点 linklist p p linklist malloc sizeof struct lnode if p return false 分配失败 p coef coef p exp exp p next NULL return p void insert linklist phead linklist head 新结点 phead 有序插入头结点为 head 的多项 式内 if phead coef 0 free phead else linklist p q p head q head next while q if phead exp q exp break p 做后指针 寻找插入位置 p q q q next if q free phead if q coef 若合并系数为 0 删除 p next q next free q else 若不存在则插入 phead next q p next phead void printlinklist linklist phead 打印 传入 p i linklist q phead next int flag 1 if q printf 0 n return while q if q coef 0 系数大于 0 且非第一项 if q coef 1 省去无意义 0 if q exp 1 putchar X else if q exp 0 else if q exp printf X d q exp else if q coef 1 if q exp putchar 1 if q exp 1 putchar X else if q exp 0 else printf X d q exp if q coef 1 if q exp putchar 1 if q exp 1 putchar X else if q exp 0 else printf X d q exp q q next flag printf n linklist creatlist 创建 调用时 p i creatlist linklist phead linklist head phead 为增加节点指针 head 为头指针 phead head linklist malloc sizeof struct lnode 申请头结点 head next NULL while fabs phead coef 1E 8 若 coef 为 0 结束 phead linklist malloc sizeof struct lnode printf input coef exp n scanf lf d if phead coef 0 insert phead head 有序插入 printlinklist head return head void linklistclear linklist head linklist p q p head next q p next while p NULL free p p q if q NULL q q next head next NULL void linklistdestroy linklist p head q p next while p NULL free p p q if q NULL q q next head NULL double linklistvalue linklist head double x double sum 0 t t 项数权重 int i linklist p for p head next p p p next t 1 for i p exp i 0 if icoef t return sum void linklistadd linklist ahead linklist bhead linklist qa ahead next qb bhead next hc linklist malloc sizeof struct lnode hc next NULL hc 为尾结点 chead hc while qa qb qa qb 不全为 NULL qc linklist malloc sizeof struct lnode qc 为新增结点 if qb NULL qc coef qa coef qc exp qa exp qa qa next else if qa NULL 若 a 或 b 为 null qa exp 无意义 即一条 链已插完 先排除这种情况 qc coef qb coef qc exp qb exp qb qb next else if qa exp qb exp qc coef qa coef qc exp qa exp qa qa next else if qa exp qb exp qc coef qa coef qb coef qc exp qa exp qa qa next qb qb next else if qa expexp qc coef qb coef qc exp qb exp qb qb next if fabs qc coef 1E 8 coef 非 0 接入多项式 qc next hc next hc next qc hc qc else free qc void linklistsub linklist ahead linklist bhead linklist qa ahead next qb bhead next hc linklist malloc sizeof struct lnode hc next NULL hc 为尾结点 chead hc while qa qb qa qb 不全为 NULL qc linklist malloc sizeof struct lnode qc 为新增结点 if qb NULL qc coef qa coef qc exp qa exp qa qa next else if qa NULL 若 a 或 b 为 null qa exp 无意义 即一条 链已插完 先排除这种情况 qc coef qb coef qc exp qb exp qb qb next else if qa exp qb exp qc coef qa coef qc exp qa exp qa qa next else if qa exp qb exp qc coef qa coef qb coef qc exp qa exp qa qa next qb qb next else if qa expexp qc coef qb coef qc exp qb exp qb qb next if fabs qc coef 1E 8 coef 非 0 接入多项式 qc next hc next hc next qc hc qc else free qc linklist linklistcopy linklist a linklist qa bhead qa a next bhead lnode malloc sizeof struct lnode bhead next NULL while qa insert makenode qa coef qa exp bhead qa qa next return bhead int linklistdelete linklist head int m 删除 head 中的一个结点 指数为 m linklist p q if head head next return 1 p head q p next while qq q next if q return 1 else p next q next free q return 1 void linklistmodify linklist head int flag exp double coef printf 操作选择 n1 删除结点 n2 增加结点 n3 修改结点 n scanf d switch flag case 1 printf 输入删除结点指数值 scanf d linklistdelete head exp break case 2 printf 输入增加结点指数值 系数 scanf d lf insert makenode coef exp head break case 3 printf 输入指数 修改后系数 scanf d lf linklistdelete head exp insert makenode coef exp head break void linklistdiff linklist while p NULL if p exp 0 linklistdelete head 0 break else p coef p exp p exp 1 p p next void iteintegral linklist head linklist p head next while p NULL p exp 1 p coef p coef p exp p p next int main int flag i printf n printf 稀疏一元多项式运算器 n printf 0 退出 n 退出 printf 1 创建多项式 n 创建并打印 printf 2 显示多项式 n 打印 printf 3 复制多项式 n 复制多项式 a 至 空域 b 非空报错 printf 4 求和 n 输入 abc 位置 c a b printf 5 求差 n 输入 abc 位置 c a b printf 6 求值 n 输入位置 double x 输出 double result printf 7 销毁多项式 n 销毁 使 p i 为 NULL printf 8 清空多项式 n 清空保留头指针 输出为 0 printf 9 修改多项式 n 选择插入 删除 修改 删了再插 printf 10 n 阶微分 n printf 11 不定微分 n printf 12 定微分 n printf n while 1 printf 键入数字选择操作 scanf d switch flag case 0 printf thanks for using n return 0 case 1 printf input location scanf d if p i 1 NULL p i 1 creatlist else printf 空间已被占用 n break case 2 printf 输入显示位置 scanf d if p i 1 NULL printlinklist p i 1 else printf 该位置无多项式 n break case 3 int j printf input 原位置 复制位置 scanf d d if p i 1 NULL else printf 输入位置空或输出位置满 break case 4 int j k printf 输入 a b 位置 以及输出 c 位置 scanf d d d if p i 1 NULL else printf 位置被占用或原多项式不存在 n break case 5 int j k printf 输入 a b 位置 以及输出 c 位置 scanf d d d if p i 1 NULL else printf 位置被占用或原多项式不存在 n break case 6 printf 输入多项式位置 scanf d if p i 1 NULL double tempx printf 输入 x 值 scanf lf printf 结果为 g n linklist