logo资料库

算法与数据结构训练.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.22M 资料格式：pdf 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    实验指导书概述
    实验大纲实习题
    实习报告规范
    实习步骤
    附录1：实验报告示例
    附录2：实验教学大纲
    一、课程性质、目的及任务
    二、主要参考书
    三、考试考核办法
    四、实验项目与内容提要
    《数据结构》小学期 实验指导书 石家庄铁道学院计算机系 2006.8 2006.8 2006.8 2006.8
    目 录 实验指导书概述.........................................................................................3 实验大纲实习题.........................................................................................4 实习报告规范.............................................................................................5 实习步骤.....................................................................................................6 附录 1：实验报告示例............................................................................. 7 附录 2：实验教学大纲........................................................................... 10 2
    实验指导书概述 “数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课 程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常 用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后 续课程的学习以及软件设计水平的提高打下良好的基础。 · · · · 由于以下原因，使得掌握这门课程具有较大难度： (1) 内容多，时间短，给学习带来困难； (2) 贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点； (3) 隐含在各部分的技术和方法丰富，也是学习的重点和难点； (4) 先修课程中所介绍的专业性知识不多，加大了学习难度。 由于数据结构课程的技术性与实践性，《数据结构》课程实验的设置十分必要。为了帮 助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要 求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练， 使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能 同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术， 与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算 法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。通过实验实践内容 的训练，突出构造性思维训练的特征, 提高学生组织数据及编写大型程序的能力。 上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可 少的一个教学环节。较大的实习题比平时的习题要复杂得多，也更接近实际。实习着眼于原 理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所 需要的动手能力。实习还能使书上的知识变“活”，达到深化理解和灵活掌握教学内容的目的。 平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括 问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整 套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师 都严格的检查者。 每个实习题采取了统一的格式，由问题描述、基本要求、实现提示等部分组成。 问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”； 基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规 定该题的最低限度要求； 实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实 现。 在实现的时候应注意，要尽量减少依赖于具体机器计算环境的用法，若使用，也应在 注释中指出。这样得出的程序易于在不同机器上运行，有好的可移植性。C 语言是结构化程 序设计语言，具有递归能力，可移植性也较好，是特别推荐的实现语言。 本书的一个特点是为实习制定了严格的规范。一种普遍存在的错误观念是，调试程序 全凭运气。学生花 2 个小时的机上时间只找出一个错误，甚至一无所获的情况是常见的。其 原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应 该如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格 3
    按照实习步骤规范进行实习，不但能有效地避免上述种种问题，更重要的是有利于培养软件 工作者不可缺少的科学工作方法和作风。 在附录中提供了一个完整的实习报告示例，在起到实习报告规格范例作用的同时，还 隐含地提供了很多有益的东西，比如基于数据类型的系统划分方法以及所提倡的程序设计风 格等等。计算机学科在不断发展，可以使用的语言工具越来越丰富，在本书中的实习示例是 应用面向过程的语言进行设计和编程，同样的实习题，也可以用面向对象的语言来实现。 实验大纲实习题 校园导游程序 [问题描述] 实习一 用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名 称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景 点介绍、游览路径等问题。游客通过终端可询问： （1）从某一景点到另一景点的最短路径。 （2）游客从公园进入，选取一条最佳路线。 （3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。 [基本要求] （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的 道路，边上的权值表示距离．为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择浏览路线。 （3）画出景点分布图于屏幕上。 [实现提示] （1）构造一个无向图 G 并用邻接矩阵来存储。 （2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组 p[i][] 来记录，最短路径长度就用一维数组 d[i]存放；i 的范围：0～20。 （3）一维数组 have[]是用来记录最短路径出现顶点的顺序。 （4）根据起点和终点输出最短路径和路径长度。 员工管理系统 [问题描述] 实习二 每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。 [基本要求] 根据实验内容编程，上机调试、得出正确的运行程序。系统能够完成员工信息的查询、 更新、插入、删除、排序功能。写出实验报告（包括源程序和运行结果）。 [实现提示] （1）建立一个带头结点的单向链表（无序）。 （2）对单链表进行插入，删除，更新操作。 （3）在主函数中设计一个简单的菜单，分别调试上述算法。 4
    实习报告规范 实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下 7 个内容： 1111．需求分析 以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定： (1)输入的形式和输入值的范围； (2)输出的形式； (3)程序所能达到的功能； (4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 2222．概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层 次(调用)关系。 3333．详细设计 实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其 他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算 机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。 4444．调试分析 内容包括： a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析； b．算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 改进设想； c．经验和体会等。 5555．用户使用说明 说明如何使用你编写的程序，详细列出每一步的操作步骤。 6666．测试结果 列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求 分析中所列。 7777．附录 带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。 在以下各实习单元中都提供了实习报告实例。值得注意的是，实习报告的各种文档资 料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然可 以也应该最后用实验报告纸誊清或打印)。 5
    实习步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个 10000 行的程序的难度绝不仅仅是一个 5000 行的程序的两倍，因此软件开发需要系统的方 法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。 虽然数据结构课程中的实习题的复杂度远不如(从实际问题中提出来的)一个“真正的” 软 件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述 完 成实习的 5 个步骤： 1111．问题分析和任务定义 通常，实习题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之 前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步 骤强调 的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是 对所需完 成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式； 输出数据的类 型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否 接受非法的输入， 对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测 试数据，包括合法的 输入数据和非法形式输入的数据。 2222．数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述 中 涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义 主程 序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的 伪码 算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于 调试，抽象 数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。 作为逻辑设计 的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操 作的规格说 明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设汁的结果是 对数据结构和 基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按 照算法书写规范用类 Pascal 语言写出过程或函数形式的算法框架。在求精的过程中，应尽量 避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 3333．编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过 60 个 字符。每个过程(函数)体，即不计首部和规格说明部分，一般不要超过 40 行。最长不得超 过 60 行，否则应该分割成较小的过程(函数)。要控制 1D1 语句连续嵌套的深度。其他要求 参见第一篇的算法书写规范。如何编写程序才能较快地完成调试是特别要注意的问题。对于 编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以 不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直 接用键盘输入。 然而，不管你是否写出编码的程序，在上机之前，认真的静态检查却是必不可少的。 多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信 6
    不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有 害的。事实上，非训练有素的程序设计者编写的程序长度超过 50 行时，极少不含有除语法 错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查 主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查)；二是通过阅读 或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断 言。如果程序中逻辑概念清楚，后者将比前者有效。 4444．上机准备和上机调试 上机准备包括以下几个方面： (1) 高级语言文本(体现与编译程序用户手册)的扩充和限制。 (2) 如果用 c 语言，要特别注意平时惯用的类 c 语言与标准 c 语言之间的细微差别。 (3) 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便 顺利进行上机的基本活动。 (4) 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍 柴 工”。计算机各专业的学生应该能够熟练运用高级语言的程序调试器 DEBUG 调试程序。 上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即 先调试低层过程或函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上 可以大大降低调试所面临的复杂性，提高调试工作效率。 在调试过程中可以不断借助 DEBUG 的各种功能，提高调试效率。调试中遇到的各种 异常现象往往是预料不到的，此时不应“苦思具想”，而应动手确定疑点，通过修改程序来证 实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的 源程序清单和结果。 5555．总结和整理实习报告 附录 1111：实验报告示例 _____ _______ _______ __________ __________ __________ __________ _______ _______ _____ __________班 _______ __________ _______月_____ _______年_______ __________级 __________ _____日 ____________ ____________ _____________ ____________ _____________ ____________ 姓名____________ ____________ 电话_____________ ____________ 学号____________ _____________ 1111．实验题目 编制一个演示单链表插入、删除、查找等操作的程序 2222．需求分析 本演示程序用 TC 编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元 素在单链表中的位置。 ① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元 7
    素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整 数 ② 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其 中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 ③ 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操 作 ④ 测试数据： A． 插入操作中依次输入 11，12，13，14，15，16，生成一个单链表 B． 查找操作中依次输入 12，15，22 返回这 3 个元素在单链表中的位置 C． 删除操作中依次输入 2，5，删除位于 2 和 5 的元素 3333．概要设计 1）为了实现上述程序功能，需要定义单链表的抽象数据类型： ADT LinkList { 数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系：R={|ai,ai+1 ∈D} 基本操作： InitLinkList(&L) 操作结果：构造一个空的单链表 L. InsLinkList(&L,pos,e) 初始条件：单链表 L 已存在 操作结果：将元素 e 插入到单链表 L 的 pos 位置 DelLinkList(&L,pos,&e) 初始条件：单链表 L 已存在 操作结果：将单链表 L 中 pos 位置的元素删除， 元素值置入 e 中返回 LocLinkList(L,e) 初始条件：单链表 L 依存在 操作结果：单链表 L 中查找是否元素 e， 若存在，返回元素在表中的位置；若不存在，返回-1. Menu() 操作结果：在屏幕上显示操作菜单 2）本程序包含 7 个函数： ① 主函数 main() ② 初始化单链表函数 InitLinkList() ③ 显示操作菜单函数 menu() ④ 显示单链表内容函数 dispLinkList() ⑤ 插入元素函数 InsLinkList() ⑥ 删除元素函数 DelLinkList() ⑦ 查找元素函数 LocLinkList() 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料