数据结构课程设计总结

1、Hunan Institute of Science and Technology程序设计与数据结构综合课程设计论文题 目程序设计与数据结构综合课程设计专 业：计算机科学与技术班级：N计科12-1F姓 名：吴文定学号：811指导老师：申丽平、课程认识数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操 作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件 和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据 库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系 统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示

2、出来并对 它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用 能力和专业素质的提高。通过此次课程设计主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所 应具备的科学的工作方法和作风。训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构 理论知识，编写程序求解指定问题。、问题描述及分析1、问题描述设计一个一元多项式程序，并完成多项式的加法、

3、减法、以及乘法的运算。如 A(x)=15+6x+9x7+3x18B(x)=4x+5x6+16x7 求 A+B A*B2、问题分析 .在数学上，一个一元多项式Pn(x)可按升幕写成：Pn( x)=a 0+a1 x+a2 xA2+an xan-1 .它由n+1个系数惟一确定，因此，在计算机里，它可用一个线性 表P来表示：Pn=(a0,a1,a2,a每一项的指数i隐含在其系数ai的序号里。设m<n,则两个多项式相加或者相减的结果 Rn(x)=Pn(x)+(-) Qm(x)。乘法也是类 似，通过使用链式存储结构存放多项式的每一项，从而将一元多项式的运算转 化成对链表的运算。 由于一元多项式的建立

4、、运算等操作经常要插入或者删除元素，所以考 虑使用链式存储结构(带头结点的链表)作为数据结构，以减少移动元素的次 数，减少空间复杂度和空间复杂度。 减法运算可以转化为加法运算，因此可以大大地简化程序。 乘法运算可以多次调用加法函数实现。三、数据结构描述1、数据结构选择本程序讨论的是利用线性链表的基本操作来实现一元多项式的运算。2、数据结构与多项式的结合 在数学中，每个单项式都具有系数和指数，当系数为 0 时，该项就失去了意义，在计算机内要表示一个多项式，至少以下数据信息：系数信息、指数 信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接 起来，形式一个多项式，需要说明的是从广义

5、的角度讲，单项式也是一个多 项式。3、数据结构的特点及结点表示线性链表的另一个特点是插入或删除结点是不必移动其他结点， 而仅需 调整指针的指向关系以适应新的数据关系， 从而大大简化了创建、 插入和删 除的工作。基于以上的分析，我们定义多项式的数据结构为如下结构体形式：struct node/ 系数/ 指数/ 指针指向下一个结点float coef;int expn;struct node *next;四、主要算法流程描述（个人负责部分）如图4-1为主函数流程图图4-1图5-1为加法算法的流程图图5-1图6-1为减法算法的流程图图6-1图7-1为输出算法的流程图f 1FFF1ri10-1-2-3

6、-4111F1ririF输出A (X)输出B (X)加法减法乘法除法五、使用说明该程序在VC+中调试通过，没有错误和警告，运行结果经过检验为正确。以下即为该程序运行结果效果图。图中采用的是计算多项式3xA+2xA7+4xA2+1和xA4+5xA3+6xA5的输入方式和加减乘除四种运算结果进行的演示：1、输入并建立多项式链表*；' i：卩爭 用 參 T页昌 詡 千 g命 HWX 鬓:KMK 削耳:MX 鬓:KMKN 耳:MX 鬓:KMKN2r4afi>如女女2nu弋A WWW式=3式式式 -3UJr3sJI.1I#1J 卢. F.-"K F .!1.1 幺kylnrryl

7、rmllnTVImkvInTVInTVInT J二J-二J囱1二1二1- 口口口 nJ0 n n Q 1154 小系系系®系成上.0 勺-勺 4 6 聲点点建r V 針结结结>>0X珂点点占屛结结结结j 一 X1234 xl2 3 一 c 青稼存<暮暂暮 -fl聲穿聲聲B肆穿葺 一入入入入入入入入入土同青青青圭一冃3 55 62 2 2 Hu. nu nu. 女女女2、加、减、乘、除运算两多项式做加法后得到的多项式为：ACx>+B<x>=1-0+3.0X1+4.+5.0X*3+KA4+6.0XA5+2.0XA7 甌多项式做碱迭后得到的多顶式为=A&

8、lt;x>-B<x>=l.B+3,0X"l+4.0K"2+<-6.O>XA5*2,0XA? 两多项式做乘袪后得到的多项式为：A<x>*B<x>=5.0X3+16.0XA4+29,0X5*22.0X6+24.0KA?+10.0N A10+2,0XA11+12,0XA12两寻顶式做除法后得到的多项式为:fi<x>/B<x>=0.3XA24.0X*2+3,0XA1+1,0 * <-0.3 )X% +<-1.7>K*5Pi'ess Any keu to continue3、使用条

9、件及方法条件：请在 Microsoft (R) Developer Studio VC+开发环境下运行。方法：将“ Add”、“ Copy”、“ CreatePolyn”、“ Divide ”、“ log in”、“ Multiply ”、“ Print”、“ ReArrange”、“ struct node ”、“ Substraction ” 包含在同一文件夹下面，运行“ login ”，然后根据提示，输入链表每一个结点的系数和指数值， 然后选择加减乘除这四个运算的任意一个，得到结果。4、注意事项1、在输入多项式每一个结点时， 系数定义为浮点型， 指数定义为整型， 用户输入的时候，应该注意

10、，系数输入浮点和整型都可以，而指数为整型，若输入为 浮点型，则会产生误差。2、用户在输入选择某一个算法时，应该按照界面上的提示说明进行输 入，若超出提示范围，则会提示让用户重新输入。3、用户在包含文件的时候，请注意每一项文件的完整性。缺失则会导 致运行错误。六、调试分析说明调试过程中出现的问题和处理方式：1、在编写加法函数时，比较 p->expn,q->expn 的时候，应该编写下面程序来使问题简化。int compare(int a,int b)if(a<b)return -1;elseif(a=b)return 0;elsereturn 1; 2、在编写减法程序的时候，

11、应该注意调用加法程序， 只需要在后面的链表系数全部乘 以( -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("XA%d+",p->

12、;expn);每一次都会输出+号，所以在最后的时候需要printf( b ”;来删除最后的+号，但是由于用户可能输入A或者B是0，所以最后都没有+,但是原来程序已经把最后一个字符通过b ”删除了，所以设定了一个标志符，判断如果为0,则多输出一个 0，来解决了这个问题七、特色和改进思想一、特色 ：我们组在成功完成一元多项式的加法、减法、和乘法之后，又成功地 解决了一元多项式的除法问题，使得对一元多项式的四项基本运算都可以通过本程序 来解决。并且在编写“ Divide ”函数时，都是通过调用前面已有的算法，使得程序很简 洁，便于移植。二、改进思想 ：1、我们组在编写CreatePolyn ()，创

13、建链表的时候，在考虑到输入时候X的指数可能不是按照顺序来输入的，所以采用了全部输入完成后经过对链表的排序来使其 有序，经过陈老师的指导后，我们实现了“边输入、边排序”这一思想，即在输入的 时候就对每一项进行插入排序。使得程序的算法思想变得更加先进，节省了时间复杂 度和空间复杂度。2、 在由每个人完成个自的模块后进行融合的时候，发现许多工具函数都是可 以相互调用的，之后我们规定了各种函数调用的标准，使得整体程序变得简洁。3、在编写 ”print ”函数时，由于后面会多输出一个号，所以在查找参考书 之后，通过printf( b”);，使得这个问题巧妙的解决了。八、课程设计总结本次的数据结构课程设计

14、针对具体的实际项目来进行需求分析，测试计划，概要设计，详细设计，测试分析等具体的步骤流程走下来，从中我收获了很多经过一周的课程设计，有很多的心得体会。首先，在编写函数之前要充分利用图书资源和网络资源； 其次， 应该更详细的考虑实际情况， 才能使程序更切合实际， 更具有实用性；更多的我想应该是组员之间的合作精神吧！通过这次课程设计练习， 使我更深刻地理解了数据结构重要存储结构的的精髓线性链表的使用。完成整个程序设计有，对线性链表的使用掌握的更加熟练。同时通过直接对链表的各种插入、查找、排序等操作，加深了对数据结构的理解 和认识。并在完成课程设计的过程作主动查阅了相关资料，学到了不少课本上没有的

15、技术知识。经过这次课程设计，我深刻认识到算法在程序设计中的重要性，一个完整的程序 总是由若干个函数构成的，这些相应的函数体现了算法的基本思想。通过此次课程设计，我了解了编写应用软件的一般步骤，获得了很多宝贵的经验。 特别是怎样将理论与实践相结合，把书本上的的内容应用到我们做的程序上。怎样使 各个子模块实施其详细功能，特别是各个子模块之间的接口，一定要相当清晰达到相 互协调的作用。 其次我熟悉了数据结构的知识学会了很多关于程序设计的经验和技巧， 明白了程序设计的使用性和通用性事程序生存周期长短的关键，学会了程序调试的一 般方法。重要的是通过本次程序设计，我逐步具备了走向程序员的基本素质。知道如 何在困难重重时一步一步细心发现问题，解决问题。知道了在软件设计中对界面和功 能如何平衡，如何达到相对完美。编程是一件枯燥乏味工作，但是只要认真专研，我们会从中学到很多在课本上学 不到或者无法在课堂上掌握的知识，同时也能从中感受到编程的乐趣。兴趣是可以培 养的，只要坚持下去，面对困难我们总能够找到解决问题的方法。计算多项式的加、减、乘法还有除法的运算 该程序虽然不是很大，这次还是由几位同学合作才完成这一任务。通过小组的分工与合作，使我充分认识到在项目