数据结构课程设计
学院信息科学与工程学院
班级：计算机
班
姓名： 宋凯嵩
学号：
数据结构课程设计
题目： 一元稀疏多项式计算器
班级：计算机
姓名：宋凯嵩学号：
日期：
一、 需求分析
本程序实现了多项式的加法，减法，求导数三种运算，按照要求先输入多项式的
项数，然后分别输入多项式的每一项的系数和指数，且输入常数项时，指数需要输
入 ，输入多项式以“回车符”作为结束标志，多项式的项数不受限制，且允许出现指
数相同的项，然后选择进行的基本运算，按“回车符”得结果，并且如要继续需要按除
外的任意键，按 推出程序。
基本要求：
输入并建立多项式
输出多项式，输出形式为整数序列：其中 是多项式的项数，
和 分别是第 项的系数和指数，序列按指数降序排列；
多项式 和 相加，建立多项式
多项式 和 相减，建立多项式
本程序采用用户和计算机对话的方式执行，即在计算机终端显示“提示信息”之后，
由用户在键盘上输入规定的数据，相应的输入的多项式将显示在计算机终端，按照
提示选择进行的运算，结果显示在最后。
程序执行的运算包括
加法：减法：导数：
测试数据
互换上述测试数据中的前后两个多项式
二、 概要设计
为实现上述程序功能，应以有序链表表示集合。为此，需要抽象数据类型：有序表
有序表的抽象数据类型定义为：
!"!#$%&
数据对象：&'()!*%+,
数据关系：-&.
+'
+
,
基本操作：
/0123!%4#
操作结果：构造一个空的有序表 #。
/1023"14#
初始条件：有序表 # 已存在。
操作结果：销毁有序表 #。
510236/
数据结构课程设计
操作结果：比较有序表中的对应结点的指数大小，+ 返回 ，返回 。. 返回
。
51023""4#4#4#
初始条件：有序表 ## 已存在。
操作结果：将两个表的对应结点相加。
51023$74#4#4#
初始条件：有序表 ## 已存在。
操作结果：将两个表的对应结点相减。
51023"!8984#4#
初始条件：有序表 # 已存在。
操作结果：对有序表中各个结点求导数。
51023/!%4#
初始条件：有序表 # 已经存在。
操作结果：将有序表中各个结点按照指数从小到大的顺序列出。
5!%4#
初始条件：有序表 # 已经存在。
操作结果：将有序表中的各个结点按照指数从大到小的顺序列出。
510230"!$!%4#
初始条件：有需表已经寻在。
操作结果：将新输入的项 与有序表中的个结点的指数进行比较，从大到小。
, "!"#$%
三 详细设计
2/":%;/2/
2/":<0%(0:2/
2/":$%!7%/102&
;/2//
(0:2/0:
*%!7%/102=%
,>0"2/=#?2/
*%%7$/1023!%#?2/)"
@@构造一个带头结点的空的有序链表 #并返回 -A;
@@若分配空间失败，则令 #)" 为 >A##
*%%7$/1023"1#?2/)"
@@销毁有序链表 #
*%%7$510236/;/2/(0:2/
@@比较两个有序链表中对应的指数，若 +则返回 ，若 则返回 ，若 .则返回；
51023""4#4#4#
@@将指针指向 每个结点调用 6/ 函数进行比较指数的大小，若 + 则把 的结果放进
链表中，若 则把相加结果放进链表中，否则把 的结果放进链表中，把运算结果放在
新开辟的链表 # 下。
51023$74#4#4#
@@将指针指向 每个结点调用 6/ 函数进行比较指数的大小，若 + 则把 的结果放进
链表中，若 则把相减结果放进链表中，否则把 的结果放进链表中，把运算结果放在
数据结构课程设计
新开辟的链表 # 下。
51023"!8984#4#
@@将链表中的每个结点求导数
5!%4#
@@将有序表中的各个结点按照指数从大到小的顺序列出。
510230"!$!%4#
@@将新输入的项 与有序表中的个结点的指数进行比较，从大到小。
B17".$%"0)+
B17".6110)+
%2/":%;/2/
%2/":<0%(0:2/
%2/":$%!7%/102&
(0:2/0:
;/2//
$%!7%/102=%
,>0"2/=#?2/
80"/1023!%#?2/)"@=创建一个结点=@
;/2//10236/;/2/;/2/@=比较相对应项的指数=@
80"/1023""#?2/)"3#?2/)"3#?2/)"3@=加法=@
80"/1023$7#?2/)"3#?2/)"3#?2/)"3"@=减法=@
80"/1023"!898#?2/)"#?2/)@=求导数=@
80"/10230!"!$!%#?2/)"#?2/$@=排序=@
80"/!%#?2/)"@=输出最终结果=@
80"/1023"1#?2/)"@=删除链表=@
80"6
&
;/2/)0
#?2/)"3)"3)"3)"3")"3)"3:
"0&
)"3#?2/6110$C0:>0"2/
)"3+%>A##
)"3#?2/6110$C0:>0"2/
)"3+%>A##
)"3#?2/6110$C0:>0"2/
)"3+%>A##
)"3"#?2/6110$C0:>0"2/
)"3"+%>A##
数据结构课程设计
)"3#?2/6110$C0:>0"2/
)"3+%>A##
)"3:#?2/6110$C0:>0"2/
)"3:+%>A##
/!DE=========================多项式加减法========================FE
/!DE请输入 多项式的项数FE
/1023!%)"3
/!DE请输入 多项式的项数FE
/1023!%)"3
/!DE============================================================FE
/!DE========输出的多项式 =========FE
/!%)"3
/!DEFE
/!DE========输出的多项式 G=========FE
/!%)"3/!DEFE
"0&
/!DE请选择进行按 ==加法或 ==减法或 ==求导数 ===推出FE
$:EH"E4)0
/!DE============================================================FE
$I%))0
&
$/1023"")"3)"3)"3/!%)"3/1023"1)"3!?
$/1023$7)"3)"3)"3"/!%)"3"/1023"1)"3"!?
$
/1023"!898)"3)"3/1023"!898)"3)"3:/!DEE/!%)"3/102
3"1)"3/!DEFE/!DEGE
/!%)"3:/1023"1)"3:!?
$!?
":71%/!DEJ- >K;>;-LFE
,
,I)1)0
,I)1)0
,
80"/!%#?2/)"
&
#?2/1?)"+%
:L1?
&
/!DEFE
,1$
&
/!DEHME1?+0:
评论0