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

西南科技大学网络教育 《数据结构》课程设计指导书 一、课程基本信息 【课程设计名称】 数据结构课程设计 【课 程 归 属】 计算机科学与技术学院 【适 用 专 业】 计算机科学与技术 【专业基础课程】 C程序设计语言 二、课程设计目的 1、初步具备； 3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风问题定义：根据设计题目的要求，充分地分析和理解问题，限制条件对问题描述中涉及的操作对象定义相应的数据类型和各抽象数据类型写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)：按照以数据结构为中心的原则划分模块定义主程序画出模块之间的调用关系图在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试详细设计：各个主要模块的算法定义。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，伪码写出函数的算法程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚 6、程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析编写课程设计报告集合的并、交和差运算问题描述】 编制一个能演示执行集合的并、交和差运算的程序。 【基本要求】 (1) 集合的元素限定为小写字母字符 [‘a’..’z’] 。 (2) 演示程序以用户和计算机的对话方式执行。 【测试数据】 (1)Set1=agazine，Set2=paper， Set1∪Set2=aegimnprz，Setl ∩Set2=ae，Set1-Set2=gimnz。 (2)Set1= 012oper4a6tion89，Set2=error data， Set1∪Set2=adeinoprt，Setl ∩Set2=aeort，Set1-Set2=inp。 【实现提示】 以有序链表表示集合。 【选作内容】 (1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。 (3) 集合的混合运算表达式求值。 (4) 集合的元素类型推广到其他类型 ， 甚至任意类型。 2、一元稀疏多项式计算器 问题描述】 设计一个一元稀疏多项式简单计算器。 【基本要求】 一元稀疏多项式简单计算器的基本功能是： (1) 输入并建立多项式 ； (2) 输出多项式，输出形式为整数序列n，l，el，c2，，…，cn，其中n是多项式的项数，ci 和e，分别是第 i 项的系数和指数，序列按指数降序排列； (3) 多项式和b相加，建立多项式a +b； (4) 多项式a和b相减，建立多项式 -b 。 【测试数据】 (1)(2+5x8－3.1x11) + (7－5x8+11x9)=(－3.lx11+11x9+2x+7) (2)(6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15) =(-7.8x15-1.2x9+12x-3-x) (3)(1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5) (4)(x+x3)+(-x－x3)=0 (5)(x+x100)+(x100 +x200)=(x+2x100+x200) (6)(x+x2+x3)+0=x+x2+x3 (7) 互换上述测试数据中的前后两个多项式 【实现提示】 用带表头结点的单链表存储多项式。 【选作内容】 (1) 计算多项式在处的值。 (2) 求多项式 a 的导函数 。 3、算术表达式计算 【问题描述】 表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。（难度系数：0.7） 【基本要求】 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用运算符优先关系，实现对算术四则混合运算表达式的求值。 【测试数据】 8；1+2+3+4；88-1*5；1024/4*8；1024/（4*8）；（20+2）*（6/2）；3-3-3；8/（9-9）；2*(6+2*(3+6*(6+6)))；(((6+6)*6+3)*2+6)*2； 【实现提示】 设置运算符栈和运算数栈辅助分析算符优先关系；在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算；在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作等内容。 【选做内容】 （1）扩充运算符