成都工业学院
课程设计报告
课程名称数据结构课程设计
题目一元多项式相加
姓名涂显超
班级1405012
学号22
指导教师杨勇
设计时间2015-12-21至2013-12-25 成都工业学院计算机工程系
成都工业学院
课程设计(论文)任务书
一、课程设计(论文)题目一元多项式相加
二、课程设计(论文)工作自 2015年 12月 21日至 2015年 12月 25日。
三、课程设计(论文) 地点: 2307
四、课程设计(论文)内容要求：
1．本课程设计的目的
1) 使学生增进对数据结构各理论知识的熟练程度，
2) 加强算法设计的能力，为以后的数据库原理等课程的学习打下良好基
础。，
2．课程设计的任务及要求
□题目一：大整数的代数运算（难度0.5）
□题目二：一元多项式相加（难度0.5）
□题目三：表达式求值（难度0.7）
□题目四：迷宫问题（难度0.6）
□题目五：近似串匹配（难度0.7）
□题目六：数字旋转方阵（难度0.5）
□题目七：信号放大器（难度0.5）
□题目八：哈夫曼算法的应用（难度0.8）
□题目九：农夫过河（难度0.7）
□题目十：医院选址问题（难度0.7）
□题目十一：个人电话号码查询系统（难度0.5）
□题目十二：斐波那契查找（难度0.6）
在以上分属各章的题目从不同章选至少三个题目完成，分别填写三份报告。3）课程设计论文编写要求
1）详细清晰地描述个人的课程设计工作；
2）要按照本模板的规格打印誊写课程报告；
3）课设报告包括目录、内容提要、正文、课程设计体会、参考文献、附录等；
4）课程报告装订按学校的统一要求完成
4）评分标准：
1）完成原理分析：20分；
2）完成设计过程：40分；
3）完成代码分析：20分。
4）个人创新工作：20分。
学生签名：涂显超
2015年12 月23日
课程设计(论文)评审意见
（1）原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）程序流程（20分）：优（）、良（）、中（）、一般（）、差（）；（4）代码分析（20分）：优（）、良（）、中（）、一般（）、差（）；（5）个人创新（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）
评阅人：职称：
年月日
目录
目录................................................................................................................... - 1 - 正文................................................................................................................... - 1 -
一、需求分析............................................................................................. - 1 -
二、个人工作............................................................................................. - 1 -
三、概要设计............................................................................................... - 3 -
五、程序结果............................................................................................... - 9 - 课程设计体会..................................................................................................... - 12 -
正文一、需求分析
本人选择课程设计题目:一元多项式相加
对于一个一元多项式，在计算机中的存储以及运算，没有一种固定的数据结构来存储它以及运算它，因此，在本课程设计中，我们要设计一中存储结构来表示一元多项式，并且设计算法来实现一元多项式相加。
二、个人工作
根据问题的需求分析:
我提出以下设计过程
要存储一元多项式，那么我们就要设计一种
结构来存储一元多项式，一个一元多项式
A(x)=a0+a1x+a2x^2+a3x^3+a4x^4….+anx^
n。由n+1个系数唯一确定，因此，可以用一
个线性表（a0.a1.a2.a3.a4……..an）来表示，
每一项的指数i隐含在其系数ai的序号里，
但是，单多想多项式的指数很高且变化较大
时，在多项式的线性表中就会存在很多0元
素，一个较好的存储方法是只存储非0元素，
但是需要在存储非0元素的同时存储存储相应的指数，这样，一个一元多项式的每一非0元素可由指数和系数唯一表示。但是，考虑到两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表这种存储结构并不适合进行一元多项式的运算，如果，采用单链表来存储，则每一个非0项对应着单链表的一个节点，且单链表按指数递增有序排列，其结构如下
其中：
Xishu是系数域，存放非0项的系数；Zhishu是指数域，存放非0项的指数；Next是指针域，存放指向下一节点的指针
三、概要设计
四、源程序（关键代码分析）
首先设计一个结构体来存储每一个节点
struct Node
{
double xishu;
int zhishu;
Node *next;
};
对于存储一元表达式，可用单链表来;
void Creat(Node *&head, int n) // 生成带表头结点的单链表，除头结点外另生成n个结点
{
head = (Node *)malloc(STRUCTSIZE);
head->xishu = 0;
head->zhishu = 0;
head->next = NULL; // 初始化头结点
cout << "请输入各项系数及指数（用空格隔开，如：a b表示系数为a，指数为b）：" << endl;
Node *p = head;
for(int i = 0; i < n; i++) {
p->next = (Node *)malloc(STRUCTSIZE); // 生成新结点，尾插入生成链表
p = p->next;
cin >> p->xishu >> p->zhishu;
p->next = NULL;
}
}
打印输出节点：
void Print(Node *&head)
{
if(head->next == NULL) // 结果是0时直接输出0
putchar('0');
else {
for(Node *p = head->next; p != NULL; p = p->next) {
if(p != head->next && p->xishu >0) // 当p非首项且指向的系数为正时才输出'+'
putchar('+'); // 之前只判定了p->xishu >0
if(p->xishu == 1) { // 系数为1或-1时特殊处理
if(p->zhishu == 0)
putchar('1'); // 判断条件不能写在一起：
} // if(p->xishu == 1 && p->zhishu == 0) putchar('1');
else if(p->xishu == -1)
putchar('-');
else
cout << p->xishu;
switch(p->zhishu) { // 指数为0或1时特殊处理
case 0:
break;
case 1:
putchar('x');
break;
default:
p->zhishu < 0 ? printf("x^(%d)", p->zhishu) : printf("x^%d", p->zhishu); // 指数小于0时打括号
break;
}
}
}
cout << endl;
}
两个表达式相加并输出：
oid PrintAdd(Node *&pA, Node *&pB) // 传进两个链表的头指针
{
Node *ha = pA;
Node *hb = pB;
Node *qa = ha->next; // ha, hb分别跟在qa, qb的后一位置
Node *qb = hb->next; // qa, qb分别指向Pa, Pb中当前比较元素
while(qa && qb)
{
double sum = 0;
int a = qa->zhishu;
int b = qb->zhishu;
switch( Compare(a, b) ) {
case '<': //第一种情况非ha = ha->next;
ha = qa;
qa = qa->next;
break;
case '=': //第二种情况
sum = qa->xishu + qb->xishu;
if(sum != 0.0) {
qa->xishu = sum;
ha = qa;
}
else {
if(ha->next != qa)
cout << "Error: ha->next != qa" << endl;
ha->next = ha->next->next; // 删除和为0的结点，ha不变，还在qa后一位置
Delete(qa);
}
if(hb->next != qb)
cout << "Error: hb->next != qb" << endl;
hb->next = hb->next->next;
Delete(qb);
qb = hb->next;
qa = ha->next;
break;
case '>'://第三种情况
hb->next = hb->next->next; // 删除qb指向的结点
qb->next = ha->next; // 将qb插入ha后qa 前
ha->next = qb;
qb = hb->next;
ha = ha->next;
break;
default:
cout << "Error!" << endl;
break;
}
}
if(qb)
ha->next = qb;
Delete(hb);
}
主函数代码如下：
int main(void)
{
Node *A = NULL;
Node *B = NULL;
int lenA;
int lenB;
int flag = 0;
while (true) {
cout << "====================================================== ==========================" << endl;
cout << "\t\t\t 一元多项式相加计算" << endl;
cout << "====================================================== ==========================" << endl;
cout << endl;
cout << "输入任意数字继续，输入0退出:" << endl;
cin >> flag;
if (flag == 0)
{
cout << endl; cout << endl; cout << endl; cout << endl; cout << endl;
cout << "\t\t\t\t谢谢使用!!!" << endl;
cout << endl; cout << endl; cout << endl; cout << endl; cout << endl;
system("pause");
exit(0);
}
cout << "请输入第一个多项式A的项数：" << endl,
cin >> lenA;
Creat(A, lenA); //生成A链表
cout << "请输入第二个多项式B的项数：" << endl;
cin >> lenB; //生成B链表
Creat(B, lenB);
cout << "\t\tA = "; // 输出A链表
Print(A);
cout << "\t\tB = "; // 输出B链表
Print(B);
PrintAdd(A, B); // A = A + B
cout << "\t\tA + B = ";
Print(A); // 输出A+B
cout << endl;
Delete(A); Delete(B);// 务必释放结点
system("pause");
system("cls");
}
return 0;
}
四、程序结果程序开始：
输入测试数据运行结果：
按任意键继续：
六、参考文献
1. 《数据结构C++版（第2版）》作者：王红梅，出版社：清华
大学出版社2012年
2. 《数据结构》作者：严蔚敏，出版社：清华大学出版社2000
年
3. 《数据结构实验题集》作者：严蔚敏，出版社：清华大学出版社2000 年
课程设计体会
在课程设计过程中的个人感想，字数不多于200。（包括: 课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容）
通过此数据结构课程设计题目为:一元多项式相加
在此课程设计过程中遇到好多问题呀,可能还没有学好吧.如创建单链表，对两个表达式相加,有好多代码呀.我实在没有什么好的方法能决此问题呀.总算还是把我搞出来了.
可能遇到最大问题是,写当单链表来存储一元多项式，可能就是
实践这些数据结构原理太少了吧,刚学这此原理一看能懂,好像没有什么事样,但一试一下就出现了好多问题呀.
不知怎么用呀.
在本课程设计中，最需要注意的一点就是，创建节点时，每新增加一个节点的时候，就要动态分配一片内存，考
虑到每次需要分配相同的大小sizeof（Node）,所以干脆
将他定义为#define STRUCTSIZE sizeof（Node），还有最
重要的一点时，在每次运算完毕后，需要手动释放内存，即写一个Delete函数来释放单链表所占用的内存。
我想学好编程不光要精通各原理呀,还要多实践呀,
再实践呀.