数据结构课程设计总结-(1).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语言版〕/严蔚敏，吴伟民编著。----清华大学，2007
.tup.
2、 数据结构题集/史嘉权 编著。 -------清华大学，2008
12 / 12