云南大学软件学院 数据结构实验报告
2010秋季学期
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）
学号：姓名：专业： 指导老师：
实验难度 承担任务 （难度为C时填写） 指导教师评分 【实验题目】
实验2. 线性表及其应用 【问题描述】
用C或C++语言设计并实现一个一元稀疏多项式的简单计算器。 【基本要求】
一元稀疏多项式简单计算器的基本功能是： 1、输入并建立多项式
2、输出多项式，序列按指数降序排列
3、多项式A(x)和B(x)相加，并建立多项式A(x)+B(x) 4、多项式A(x)和B(x)相减，并建立多项式A(x)-B(x) 5、给定 x 的值，计算多项式
6、多项式A(x)和B(x)相乘，建立多项式A(x)*B(x) （* 选做，作为难度B的操作）
A □ B □ C □ （签名） 【CDIO项目要求】
1、有完整的CDIO四个阶段描述 2、有友好美观的操作界面 3、有软件使用说明或帮助文档
4、项目成员分工明确，团结协作【实现提示】 一、【实验构思（Conceive）】(10%)
本实验通过C语言实现了多项式加法、减法、乘法、多项式求导、多项式积分的功能。 利用了冒泡排序的算法作为排序的核心算法。 运用了高等数学中多项式的求导积分的知识。 二、【实验设计(Design)】(15%)
本程序定义了抽象数据结构listnode，用于存储多项式的系数和指数并存储指向下一个listnode的指针来构成链表。 本程序包含如下*个函数：
Main函数：调用input函数—>调用bubble_sort函数—>调用operplus函数—>调用
oper_minus函数—>调用oper_mul函数—>调用oper_dy函数—>调用oper_jifen函数。
Oper_plus函数：将两个链表的相应项系数相加，指数不同项不操作，存入新链表，
再调用排序算法，使之为降序排列。
Oper_minus函数：将两个链表的相应项系数相减，指数不同项不操作，存入新链表，
再调用排序算法，使之为降序排列。
Oper_mul函数：将两个链表的相应项系数相乘，指数指数相加，存入新链表，再调用
排序算法，使之为降序排列。
Oper_dy函数：将链表的相应项系数乘以指数，指数减一，存入新链表，再调用排序
算法，使之为降序排列。
Oper_jifen函数：将链表的相应项系数除以指数+1，指数加一，存入新链表，再调用
排序算法，使之为降序排列。
Bubble_sort函数：使用冒泡排序的算法使链表的各个元素成降序排列，并合并同类
项，返回链表头指针。
Myprintf函数：用于格式化输出多项式的每一项，消除为1的系数以及为1的指数，
使之看上去与人类写法差不多。 三、【实现描述（Implement）】(25%)
（本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）
Listnode包含3个成员变量：系数、指数、指向下一个的指针。 关键算法：bubble_sort函数，时间复杂度：n^2。
四、【测试结果（Testing）】(20%) 测试数据如图：
实验结果：
四、【实验总结】(10%)
这是第一次用链表编写多项式运算器，感到使用抽象数的类型的线性表的方便之处，以后还会多多使用的。
本次试验在很多地方使用了代码的重用。极大的减少了代码的行数。
五、【项目运作描述（Operate）】(10%)
能减轻多项式运算大部分的压力，方便同学们日常使用，加法、减法、乘法、求导、积分这些看似简单的运算常常会占用我们大量的时间，使这软件有一定的实用价值。
六、【代码】(10%)
// 定义控制台应用程序的入口点。 //
#include \#include \
typedef struct node { float con;
int exp; struct node * next; }listnode;
listnode * head; listnode * p; listnode * q; listnode * r;
listnode * head1; listnode * head2;
int head_num = 0; listnode * point[2];
void input() { int j = 0; int exp; float con; head = (listnode *) malloc (sizeof(listnode)); head ->next = NULL; start: scanf(\ if (exp == 0 && con == 0) goto next; p = (listnode *) malloc (sizeof (listnode)); j++; p ->con = con; p ->exp = exp; p ->next =head ->next ; head ->next = p; goto start; next: head ->exp =j; point [head_num] = head; head_num ++; }
int bubble_sort(listnode * myhead) { int i,j; listnode * swap; listnode * real_myhead; real_myhead = myhead; int num = myhead ->exp; //myhead = myhead ->next; if (num == 1 && num == 0 ) goto next; for (i = 0; i < num-1; i ++) { myhead = real_myhead; for (j = 0;j < num-1; j ++) { if ((myhead ->next ->exp ) < (myhead->next ->next->exp )) {
相关推荐：
loading