数据结构课程设计总结

课程设计说明书

课程名：《数据结构课程设计》

题目：一元多项式运算系统

20##年1月

一、课程认识

数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：

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

②由于一元多项式的建立、运算等操作经常要插入或者删除元素，所以考虑使用链式存储结构（带头结点的链表）作为数据结构，以减少移动元素的次数，减少空间复杂度和空间复杂度。

③减法运算可以转化为加法运算，因此可以大大地简化程序。

④乘法运算可以多次调用加法函数实现。

三、数据结构描述

1、数据结构选择

本程序讨论的是利用线性链表的基本操作来实现一元多项式的运算。

2、数据结构与多项式的结合

在数学中，每个单项式都具有系数和指数，当系数为0时，该项就失去了意义，在计算机内要表示一个多项式，至少以下数据信息：系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形式一个多项式，需要说明的是从广义的角度讲，单项式也是一个多项式。

3、数据结构的特点及结点表示

线性链表的另一个特点是插入或删除结点是不必移动其他结点，而仅需调整指针的指向关系以适应新的数据关系，从而大大简化了创建、插入和删除的工作。

基于以上的分析，我们定义多项式的数据结构为如下结构体形式：

struct node

{

float coef; //系数

int expn; //指数

struct node *next; //指针指向下一个结点

};

四、主要算法流程描述（个人负责部分）

如图4-1为主函数流程图

数据结构课程设计总结

图5-1为加法算法的流程图

数据结构课程设计总结

图6-1为减法算法的流程图

数据结构课程设计总结

图6-1

图7-1为输出算法的流程图

数据结构课程设计总结

五、使用说明

该程序在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

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

http://www.tup.com.cn

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