数据结构上机实习课案.ppt

数据结构上机实习 实习步骤 （1）按照每次实习的要求选定题目。 （2）分析题目要求，明确要实现的功能；设计数据结构；根据面向对象编程方法，确定算法的基本思想，主要模块，各模块功能及调用关系，再用C++语言对主要算法进行细化。 （3）编写好上机源程序，并进行静态检查，使程序中的逻辑错误和语法错误减少到最低程度。 （4）准备好测试数据，考虑好调试手段，上机调试程序；程序通过后，打印一份源程序清单及对测试数据的运行结果。 （5）最后写好调试分析报告及使用说明，完成一份完整的实习报告。 实习报告的内容 一 实习题目与要求 包括题目与功能要求? 二 需求分析 包括问题描述、系统环境、运行要求等? 三 概要设计 包括数据结构和存储结构的设计、算法设计、模块设计等? 四 详细设计 包括类的函数成员和数据成员设计、界面设计及其它模块设计与实现? 五 调试分析 调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和分析；算法的时间和空间复杂度的分析；算法的进一步改进等。 六 使用说明 使用说明主要描述如何使用你的程序及使用时的注意事项。 七 测试结果 如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含其他测试数据及其运行输出（需要多组测试数据）。 八 源程序清单 源程序中要添加必要的注释。 实习一 线性表、栈和队列及应用 任选一题 1、一元稀疏多项式运算器 【问题描述】 设计一个一元稀疏多项式简单计算器。 【基本要求】 （1）输入并建立两个多项式； （2）多项式a与b相加，建立和多项式c； （3）多项式a与b相减，建立差多项式d； （4）输出多项式a,b,c,d。输出格式：比如多项式a为：A(x)=c1xe1+ c2xe2+…+ cmxem，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜em。 【测试数据】 （1）(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) （2）(x+x100)+(x100+x200)=(x+2x100+x200) （3）(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11) （4）(6x-3-x+4.4x2-1.2x9)-(-6x-3+4.4x2+7.8x15) =(12x-3-x-1.2x9-7.8x15) 【实现提示】 （1）用带头结点的单链表存储多项式。 （2）每个多项式链表中都只存储非零系数项。若多项式a与b中指数相等的两项相加/减后，系数为零，则在和/差多项式c中不存储该指数项。 【拓展内容】 计算器的仿真界面。 2、n(n20)的阶乘 【问题描述】 大数运算——计算n的阶乘 (n≥20)。 【基本要求】 （1）数据的表示和存储： ①累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求。 ②试设计合适的存储结构，要求每个元素或结点最多存储数据的3位数值。 （2）数据的操作及其实现： 基于设计的存储结构实现乘法操作，要求从键盘上输入n值；在屏幕上显示最终计算结果。 【测试数据】 （1）n=20，n!=2432902008176640000 （2）n=30，n!=265252859812191058636308480000000 【实现提示】 （1）设计数据的存储结构： 介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或结点存储数据的若干位数值。 从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构。 （2）实现两个数的乘法运算需考虑： 乘数的各位数都要与被乘数进行乘法运算； 乘法过程中的进位问题及其实现。 因每个元素或结点最多存储数据的3位数值，故当元素或结点中的数值大于999，需向前一个元素或结点进位。 3、表达式的后缀表示 【问题描述】 表达式中包含运算对象、运算符和圆括号等，习惯上使用中缀表示（指运算符夹在两运算符对象中间）形式。计算表达式的值，涉及到运算符的优先级别，如先乘除后加减。括在一对圆括号中的子表达式必须先计算，因此，圆括号可视为特殊的运算符，具有最高优先级别。圆括号可以任意嵌套，这意味着左圆括号后面又是表达式，形成表达式的递归定义。为了直接指明表达式中各运算对象的先后计算顺序，可将表达式的中缀形式转换成后缀（指运算