数据结构课程设计报告范本

'``《数据结构与算法》课程设计报告（2011—2012学年第1学期）专业：软件工程班级：信息技术外包姓名学号：陈扬扬1007092104指导教师：翁伟成绩：计算机科学与技术系2011年12月23日``` ``目录目录2一、设计目的3二、设计任务及要求3三、题目分析与解答41.航班查询系统41.1任务描述41.2数据结构与算法描述41.3实验结果52.字符串的操作72.1任务描述72.2数据结构与算法描述72.3实验结果73.1任务描述83.2数据结构与算法描述83.3实验结果94.1任务描述104.2数据结构与算法描述105.1任务描述115.2数据结构与算法描述115.3实验结果116.1任务描述126.2数据结构与算法描述126.3实验结果12六、指导教师评语15``` ``一、设计目的1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。3、培养学生初步的软件设计及软件测试的能力。二、设计任务及要求基本要求:学生必须仔细阅读《数据结构》课程设计指导书，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准；（周二下午开始逐一检查）内容：本次课程设计完成如下模块（共11个模块，学生可以在其中至少挑选4个功能块完成，但有**号的模块是必须要选择的,多做可以加分）``` ``三、题目分析与解答1.航班查询系统1.1任务描述飞机航班信息包括：航班号、起点站、终点站、起飞时间、到达时间、机型以及票价，实例如下：设计航班查询系统要求能对飞机航班信息进行排序和查找。可按航班的航班号、起点站、终点站、起飞时间以及到达时间进行查询。1.2数据结构与算法描述程序首先定义了一个用于储存航班信息的数据类型应对此数据结构注释下，每个项是什么意思。typedefstructtypedefstructtypedefstruct{{{charstart[20];keytypekeys[keylen];slnodesl[maxspace];charend[20];infotypeothers;intkeynum;charsche[10];intnext;intlength;chartime1[8];}slnode;}sllist;chartime2[8];charmodel[4];intprice;}infotype;再由用户录入航班数据(voidinputdata(sllist&l),voidradixsort(sllist&l)(建立链表))在录入的同时并对数据进行排序(voidarrange(sllist&l))后执行数据查询和检索。在查询设计中，使用二分查找法对排好序的航班数据按航班号实现快速查找(intbinsearch(sllistl,keytypekey[]))、按起点站、终点站、起飞时间、到达时间查找的采用顺序查询方法(voideqsearch(sllistl,keytypekey[],inti))。voidsearchcon(sllistl)(主菜单)``` ``定义数据类型数据输入、排序输出查找结果此图太简单，不是数据流程图，也没有写算法，不合格。1.3实验结果``` ````` ``2.字符串的操作2.1任务描述任务：字符串采用数组存储，建立两个字符串String1和String2.输出两个字符串。将字符串String2的头n个字符添加到String1的尾部，输出结果。查找String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。输出结果。2.2数据结构与算法描述char*str1=NULL,*str2=NULL,*str3=NULL,*p=NULL,*str4=NULL;定义数据结构，申请节点空间结束输入字符串str1，str2，字符数n输入字符串str3是否在str1内输出位置p输入位置m输出str4开始是否2.3实验结果``` ``3.一元多项式计算3.1任务描述设有一元多项式Am(x)和Bm(x)。任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加M(x)=Am(x)+Bm(x)，并将结果输出；能够完成两个多项式的相减M(x)=Am(x)-Bm(x)，并将结果输出；3.2数据结构与算法描述typedefstructPolynomial{floatcoef;//系数intexpn;//指数structPolynomial*next;}*Polyn,Polynomial;PolynCreatePolyn(Polynhead,intm)建立一个头指针为ahead、项数y为的一元多项式PolynAddPolyn(Polynpa,Polynpb)计算a+bintcompare(Polyna,Polynb)比较a与b,如果a空b非空,返回-1;a非空b空,返回1;项数相同返回0PolynSubtractPolyn(Polynpa,Polynpb)求解a并建立多项式a+b，返回头指针a、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）测试要点：输入的多项式是否正确，若输入错误则重新输入``` ``开始输入多项式的项数+++++++++++++++++++++++++++++++++++++++++++++++++++++++num定义数据结构，申请节点空间输入多项式各项的系数x，指数y输出多项式+++++++++++++++++++++++++++++++++++++++++++++++++++++++num是否正确合并多项式、输出+++++++++++++++++++++++++++++++++++++++++++++++++++++++num开始否是开始定义存储结果的空链r存储多项式a的空链P是否为空存储多项式b的空链q是否为空同指数项系数相加后存入r直接把q中各项存入r把p中各项系数改变符号后存入r合并同类项输出存储多项式的和的链r结束b、多项式的加减法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加减后的结果。（4）程序流程图：多项式的加减法流程图如图所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。3.3实验结果``` ``4.文章编辑4.1任务描述功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；4.2数据结构与算法描述typedefstructline{char*data;structline*next;}LINE;链表voidCreate(LINE*&head)接收文章voidOutPut(LINE*&head)输出文章intCountLetter(LINE*&head)统计字母intCountNumber(LINE*&head)统计数字intCountSpace(LINE*&head)统计空格intCountAll(LINE*&head)统计总字数intFindString(LINE*&head,char*str)字符串出现的次数voidDelString(LINE*&head,char*str)删除指定字符遍历链表voiddelstringword(char*s,char*str)删除指定字符(str)4.3实验结果``` ``5.二叉树运算15.1任务描述任务：求二叉树中指定两个结点共同的最近祖先。5.2数据结构与算法描述typedefstructnode{intdata;//data域structnode*l;//定义左节点域structnode*r;//定义右节点域}nike;定义数据结构，申请节点空间结束新建一棵二叉树先序遍历二叉树开始输入想要查询的节点编号输出它们的共同祖先5.3实验结果``` ``6.各种排序6.1任务描述任务：随机产生N个整数（1000以下），用程序实现插入法排序、起泡法改进算法排序；利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。6.2数据结构与算法描述直接插入排序：当插入第i(i≥1)个对象时，前面的V[0],V[1],…,v[i-1]已经排好序。这时，用v[i]的关键码与v[i-1],v[i-2],…的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。起泡排序：需反复比较相邻两个数的比较与交换这两种基本操作。对相邻的两个数进行比较时，如果反面的数大于（或小于）前面的数，将这两个数进行交换，大的数（小的数）往前冒。6.3实验结果``` ``四、文件清单航班查询系统——airport.app字符串的操作——char.app一元多项式——polynomial.app文章编辑——article.app二叉树运算1——binarytree.app各种排序——sort.app（插入法）&BubbleSort（冒泡法）``` ``五、设计日志与总结设计日志与总结这次的课程设计基本上是在周末和周一把代码都做好的（包括拷贝别人的）。剩下的几天基本上每天都是在努力读懂代码中度过的。本次数据结构课程设计做的是比较纠结的，因为平时上课没有认真的听讲，导致好大一部分知识都是一知半解。做起来十分吃力。在做这些程序的时候有一部分是借鉴了其他人的成果，但是哪怕是借鉴了，也有很多是看不懂的，还得慢慢去理解它们的意思。通过这次课程设计，我看到了很多自己的不足之处，动手能力有待加强，有几题都是自己写一写，改不对，然后就没信心写下去就找别人的代码来看。书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。自己对这门课的很多基础知识还没很好的掌握，觉得很难，也没有很有效的想到解决办法。今后要多督促自己学习好。``` ``六、指导教师评语（注：指导教师评语和成绩所在表格另起一页）指导教师评语课程设计成绩指导教师签字年月日```'