数据结构课程设计-西南科技大学继续教育.doc

西南科技大学网络教育《数据结构》课程设计指导书一、课程基本信息【课程设计名称】数据结构课程设计【课程归属】计算机科学与技术学院【适用专业】计算机科学与技术【专业基础课程】 C 程序设计语言二、课程设计目的 1、初步具备根据应用需求选择合理数据结构并进行算法设计的能力; 2、进一步提升 C语言的应用能力; 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 5、训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风; 6、提升文档写作能力。三、设计概况及要求设计概况: 1、问题定义与需求分析:根据设计题目的要求,充分地分析和理解问题, 确定功能需求和限制条件。 2 、数据结构设计: 对问题描述中涉及的操作对象定义相应的数据类型和各抽象数据类型, 写出每个抽象数据类型的定义( 包括数据结构的描述和每个基本操作的功能说明)。 3 、概要设计: 采用结构化设计方法, 按照以数据结构为中心的原则划分模块,设计软件层次结构和模块间的调用关系,定义主程序,画出模块之间的调用关系图。在这个过程中,要综合考虑系统功能,使得系统结构清晰、合理、简单和易于调试。 4、详细设计: 定义数据存储结构, 各个主要模块的算法定义。详细设计的结果是对数据结构和基本操作作出进一步的求精,写出数据存储结构的类型定义, 用伪码写出函数的算法。 5、程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解,使程序中逻辑概念清楚。要求用 C语言编写。 6、程序调试与测试:采用自底向上,分模块进行,即先调试低层函数。能够熟练掌握调试工具的各种功能。调试正确后,认真整理源程序及其注释,形成格式和风格良好的源程序清单和结果。 7 、设计结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 8、编写课程设计报告。要求: 认真分析课题内容和要求,明确设计任务。 2、仔细分析课题,合理设计算法。 3、一人一题,独立完成。对于较难题目可两人一题,但所做模块不能一样。 4、严禁抄袭,否则成绩作废。 5、设计达到一定工作量。四、设计内容、步骤及要求 1、集合的并、交和差运算【问题描述】编制一个能演示执行集合的并、交和差运算的程序。【基本要求】(1) 集合的元素限定为小写字母字符[‘a’..’z’]。(2) 演示程序以用户和计算机的对话方式执行。【测试数据】(1)Set1=" magazine" ,Set2="paper" , Set 1∪Set2=" aegimnprz" ,Setl ∩Set2=" ae",Set1-Set2=" gimnz "。(2)Set1= "012oper4a6tion89" ,Set2=" error data ", Set 1∪Set2=" adeinoprt ",Setl ∩Set2=" aeort ",Set1-Set2=" inp "。【实现提示】以有序链表表示集合。【选作内容】(1) 集合的元素判定和子集判定运算。(2) 求集合的补集。(3) 集合的混合运算表达式求值。(4) 集合的元素类型推广到其他类型,甚至任意类型。 2、一元稀疏多项式计算器【问题描述】设计一个一元稀疏多项式简单计算器。【基本要求】一元稀疏多项式简单计算器的基本功能是: (1) 输入并建立多项式; (2) 输出多项式,输出形式为整数序列:n,c l,e l,c 2,e 2,…,c n,e n,其中n是多项式的项数,c i和e i,分别是第 i项的系数和指数,序列按指数降序排列; (3) 多项式 a和b相加,建立多项式 a+b; (4) 多项式 a和b相减,建立多项式 a-b。【测试数据】(1)(2 x+5x 8- 11)+(7-5x 8+11 x 9)=( - 11+11x 9+2x+7) (2)(6 x -3-x+ 2- 9)-(-6 x -3+ 2-x 2+ 15) =(- 15- 9+12 x -3-x) (3)(1 +x+x 2+x 3+x 4+x 5)+(- x 3-x 4)=(1+ x+x 2+x 5) (4)( x+x 3)+(- x-x 3)=0(5)( x+x 100)+( x 100+x 200)=( x+2x 100+x 200) (6)( x+x 2+x 3)+0= x+x 2+x 3(7) 互换上述测试数据中的前后两个多项式【实现提示】用带表头结点的单链表存储多项式。【选作内容】(1) 计算多项式在 x处的值。(2) 求多项式 a的导函数 a ?。 3 、算术表达式计算【问题描述】表达式计算