数据结构专业课程设计总结.doc

《程序设计和数据结构》
综合课程设计论文

题 目： 程序设计和数据结构综合课程设计
专 业： 计算机科学和技术
班 级： N计科12-1F
姓 名： 吴文定
学 号：
指导老师： 申丽平

一、课程认识
数据结构课程关键是研究非数值计算程序设计问题中所出现计算机操作对象和它们之间关系和操作学科。数据结构是介于数学、计算机软件和计算机硬件之间一门计算机专业关键课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等关键基础，广泛应用于信息学、系统工程等多种领域。
学习数据结构是为了将实际问题中所包含对象在计算机中表示出来并对它们进行处理。经过课程设计能够提升学生思维能力，促进学生综合应用能力和专业素质提升。经过此次课程设计关键达成以下目标：
u 了解并掌握数据结构和算法设计方法，含有初步独立分析和设计能力；
u 初步掌握软件开发过程问题分析、系统设计、程序编码、测试等基础方法和技能；
u 提升综合利用所学理论知识和方法独立分析和处理问题能力；
u 训练用系统见解和软件开发通常规范进行软件开发，培养软件工作者所应含有科学工作方法和作风。
u 训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。

二、问题描述及分析
1、问题描述
设计一个一元多项式程序，并完成多项式加法、减法、和乘法运算。如A(x)=15+6x+9x7+3x18 B(x)=4x+5x6+16x7 求 A+B A*B
2、问题分析
①.在数学上，一个一元多项式Pn(x)可按升幂写成：Pn(x)=a 0+a1 x+a2 x^2 +…+an x^n-1 .它由n+1个系数惟一确定，所以，在计算机里，它可用一个线性表P来表示：Pn=(a0,a1,a2,…,an)每一项指数i隐含在其系数ai序号里。设m<n,则两个多项式相加或相减结果 Rn(x)=Pn(x)+（-）Qm(x)。乘法也是类似，经过使用链式存放结构存放多项式每一项，从而将一元多项式运算转化成对链表运算。
②因为一元多项式建立、运算等操作常常要插入或删除元素，所以考虑使用链式存放结构（带头结点链表）作为数据结构，以降低移动元素次数，降低空间复杂度和空间复杂度。
③减法运算能够转化为加法运算，所以能够大大地简化程序。
④乘法运算能够数次调用加法函数实现。
三、数据结构描述
1、数据结构选择
本程序讨论是利用线性链表基础操作来实现一元多项式运算。
2、数据结构和多项式结合
在数学中，每个单项式全部含有系数和指数，当系数为0时，该项就失去了意义，在计算机内要表示一个多项式，最少以下数据信息：系数信息、指数信息和指向下一个单项式指针。经过指针，我们就能够把多个单项式连接起来，形式一个多项式，需要说明是从广义角度讲，单项式也是一个多项式。
3、数据结构特点及结点表示
线性链表另一个特点是插入或删除结点是无须移动其它结点，而仅需调整指针指向关系以适应新数据关系，从而大大简化了创建、插入和删除工作。

基于以上分析，我们定义多项式数据结构为以下结构体形式：
struct node
{
float coef; //系数
int expn; //指数
struct node *next; //指针指向下一个结点
};

四、关键算法步骤描述（个人负责部分）
图4-1为主函数步骤图

开始
分别输入A 、B
选择需要进行操作（choose ）
1、多项式加法 2、多项式减法
3、多项式乘法 4、多项式除法
Choose=1
Choose=2

Choose=3

Choose=4

调用AddPolyn（）函数

调用Multiply（）函数

调用Divide（）函数

调用Subtraction（）函数

结束

图4-1

图5-1为加法算法步骤图

p、q分别指向下一个结点
若p非空，则连接到结果链
若q非空，则连接到结果链
结 束
N
p和q系数相加存放
q所指结点抄送结果链
p所指结点抄送结果链
p系数大于q系数
p系数等于q系数
p系数小于q系数
两个指针指向结点非空
Y
开 始

图5-1

图6-1为减法算法步骤图

开 始
将B（x）中全部结点系数取相反数
调用加法函数，AddPolyn（A(x),B(x)）

结 束

图6-1

图7-1为输出算法步骤图

开始
判定 flag

1
0
-2
-1
-3
-4

head=head->next;
printf("%.1f+",p->coef);
printf("X^(%d)+",p->expn); printf("\b \n");
输出A（X）
输出B（X）

加法
减法
乘法
除法
结束

五、使用说明
该程序在VC++6.0中调试经过，没有错误和警告，运行结果经过检验为正确。以下即为该程序运行结果效果图。图中采取是计算多项式3x^+2x^7+4x^2+1和x^4+5x^3+6x^5输入方法和加减乘除四种运算结果进行演示：
1、输入并建立多项式链表

2、加、减、乘、除运算
3、使用条件及方法
条件：请在Microsoft (R) Developer Studio VC++6.0 开发环境下运行。
方法：将“Add”、 “Copy” 、 “CreatePolyn” 、“Divide” 、“login”
、“Multiply” 、“Print” 、“ReArrange” 、“struct node” 、“Substraction”包含在同一文件夹下面，运行“login”，然后依据提醒，输入链表每一个结点系数和指数值，然后选择加减乘除这四个运算任意一个，得到结果。
4、注意事项
1、在输入多项式每一个结点时，系数定义为浮点型，指数定义为整型，用户输入时候，应该注意，系数输入浮点和整型全部能够，而指数为整型，若输入为浮点型，则会产生误差。
2、用户在输入选择某一个算法时，应该根据界面上提醒说明进行输入，若超出提醒范围，则会提醒让用户重新输入。
3、用户在包含文件时候，请注意每一项文件完整性。缺失则会造成运行错误。
六、调试分析说明
调试过程中出现问题和处理方法：
1、 在编写加法函数时，比较p->expn,q->expn 时候，应该编写下面程序来使问题简化。
int compare(int a,int b)
{
if(a<b)
return -1;
else
if(a==b)
return 0;
else
return 1; }
2、 在编写减法程序时候，应该注意调用加法程序，只需要在后面链表系数全部乘以（-1），使得减法程序变得十分简练。
struct node *Subtraction(struct node *p,struct node *q)
{
struct node *headq=q,*head;
q=q->next;
while(q)
{
q->coef=q->coef*(-1);
q=q->next;
}
head=AddPolyn(p,headq);
return head;
}
3、在编写”print” 函数时，因为多项式是由单项式相加，所以在输出时候printf("X^%d+",p->expn);每一次全部会输出＋号，所以在最终时候需要 printf(“\b”);来删除最终＋号，不过因为用户可能输入A或B是0，所以最终全部没有＋，不过原来程序已经把最终一个字符经过“\b”删除了，所以设定了一个标志符，判定假如为0，则多输出一个0，来处理了这个问题。

七、特色和改善思想
一、特色：我们组在成功完成一元多项式加法、减法、和乘法以后，又成功地处理了一元多项式除法问题，使得对一元多项式四项基础运算全部能够经过本程序来处理。而且在编写“Divide”函数时，全部是经过调用前面已经有算法，使得程序很简练，便于移植。
二、改善思想：
1、我们组在编写CreatePolyn（），创建链表时候，在考虑到输入时候X指数可能不是根据次序来输入，所以采取了全部输入完成后经过对链表排序来使其有序，经过陈老师指导后，我们实现了“边输入、边排序”这一思想，即在输入时候就对每一项进行插入排序。使得程序算法思想变得愈加优异，节省了时间复杂度和空间复杂度。
2、在由每个人完成个自模块后进行融合时候，发觉很多工具函数全部是能够相互调用，以后我们要求了多种函数调用标准，使得整体程序变得简练。
3、在编写”print” 函数时，因为后面会多输出一个＋号，所以在查找参考书以后，经过printf(“\b”);，使得这个问题巧妙处理了。

八、课程设计总结
此次数据结构课程设计针对具体实际项目来进行需求分析，测试计划，概要设计，具体设计，测试分析等具体步骤步骤走下来，从中我收获了很多
经过一周课程设计，有很多心得体会。首先，在编写函数之前要充足利用图书资源和网络资源；其次，应该更具体考虑实际情况，才能使程序更切合实际，更含有实用性；更多我想应该是组员之间合作精神吧！
经过这次课程设计练习，使我更深刻地了解了数据结构关键存放结构精髓-----线性链表使用。完成整个程序设计有，对线性链表使用掌握愈加熟练。
同时经过直接对链表多种插入、查找、排序等操作，加深了对数据结构了解和认识。并在完成课程设计过程作主动查阅了相关资料，学到了不少书本上没有技术知识。
经过这次课程设计，我深刻认识到算法在程序设计中关键性，一个完整程序总是由若干个函数组成，这些对应函数表现了算法基础思想。
经过此次课程设计，我了解了编写应用软件通常步骤，取得了很多宝贵经验。尤其是怎样将理论和实践相结合，把书本上内容应用到我们做程序上。怎样使各个子模块实施其具体功效，尤其是各个子模块之间接口，一定要相当清楚达成相互协调作用。其次我熟悉了数据结构知识学会了很多相关程序设计经验和技巧，明白了程序设计使用性和通用性事程序生存周期长短关键，学会了程序调试通常方法。关键是经过此次程序设计，我逐步含有了走向程序员基础素质。知道怎样在困难重重时一步一步细心发觉问题，处理问题。知道了在软件设计中对界面和功效怎样平衡，怎样达成相对完美。
编程是一件枯燥乏味工作，不过只要认真专研，我们会从中学到很多在书本上学不到或无法在课堂上掌握知识，同时也能从中感受到编程乐趣。爱好是能够培养，只要坚持下去，面对困难我们总能够找四处理问题方法。
计算多项式加、减、乘法还有除法运算-----该程序即使不是很大，这次还是由几位同学合作才完成这一任务。经过小组分工和合作，使我充足认识到在项目团体开发过程中合作关键性，也愈加了解了沟通协作能力在软件开发行业中关键性。取得实践经验对以后从事开发软件工作中得到了很多关键经验。
另外也需要提出是在这次程序设计过程中，很感谢陈利民老师对我们耐心指导。老师在教学过程中表现出来对学术专研一丝不苟精神让我很有收获。一样也是老师严格要求才使得小组组员能够顺利完成任务。

九、附录
参考资料列表
1、 数据结构（C语言版）/严蔚敏，吴伟民编著。----清华大学出版社，

2、 数据结构题集/史嘉权 编著。 -------清华大学出版社，