《数据结构验证性实验指导书(2015)》由会员分享，可在线阅读，更多相关《数据结构验证性实验指导书(2015)（100页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 基 础课外实验指导书计算机学院2015 年 9 月课外学时：16要求：完成 4 个课外实验（实验题目自选），填写实验报告注意：到教材科购买计算机学院上机实验报告 考核：实验报告成绩作为平时成绩的一部分 提交时间：第 10 周交给各班班长 地点：鉴主 1108一、上机实验概述上机实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相 辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复 杂得多，也更接近实际。实验着眼于原理与应用的结合点，使读者学会如何 把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另 一方面，能使书上的知识变“活”，起到深化理
2、解和灵活掌握教学内容的目的。 平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计 的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本 技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 此外，还有很重要的一点是:机器是比任何教师都严厉的检查者。每个实验题采取了统一的格式，由问题描述、基本要求、测试数据、实 现提示和选做内容五个部分组成。问题描述旨在为读者建立问题提出的背景 环境，指明问题“是什么”。基本要求则对问题进一步求精，划出问题的边界， 指出具体的参量或前提条件，并规定该题的最低限度要求。测试数据部分旨 在为检查学生上机作业提供方便，在完
3、成实验题时应自己设计完整和严格的 测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据。在 实现提示部分，对实现中的难点及其解法思路等问题作了简要提示。选做部 分向那些尚有余力的读者提出了更严峻的挑战，同时也能开拓其他读者的思 路，在完成基本要求时力求避免就事论事的不良思想方法，尽可能寻求具有 普遍意义的解法，使得程序结构合理，容易修改扩充。不难发现，这里与传统的做法不同，题目设计得非常详细。会不会限制 读者的想象力，影响创造力的培养呢？回答是：软件发展的一条历史经验就 是要限制程序设计者在某些方面的创造性，从而使其创造能力集中地用到特 别需要创造性的环节之上。实验题目本身就给出了问
4、题说明和问题分解求精 的范例，使读者在无形中学会模仿，它起到把读者的思路引上正轨的作用， 避免坏结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具 体技术，保证实现预定的训练意图，使某些难点和重点不会被绕过去，而且 也便于教学检查。题目的设计策略是：一方面使其难度和工作量都较大，另 一方面给读者提供的辅助和可以模仿的成份也较多。当然还应指出的是，提 示的实现方法未必是最好的，读者不应拘泥于此，而应努力开发更好的方法 和结构。实验要有严格的规范（见下一节）。一种普遍存在的错误观念是，调试程 序全凭运气。学生花两个小时的上机时间只找出一个错误，甚至一无所获的 情况是常见的。其原因在于，很
5、多人只认识到找错误，而没有认识到努力预 先避免错误的重要性，也不知道应该如何努力。实际上，结构不好、思路和 概念不清的程序可能是根本无法调试正确的。严格按照实验步骤规范进行实 验不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可 缺少的科学工作方法和作风。二、实验步骤随之计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然 而，编制一个 10，000 行的程序的难度绝不仅仅是一个 5，000 行的程序两倍， 因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过 程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题 的复杂度远不如（从实际问题中提出
6、来的）一个“真正的“软件，但为了培养 一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完 成实验的五个步骤:（一）问题分析和任务定义通常，实验题目的陈述比较简洁，或者说是有模棱两可的含义。因此， 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么 ? 限制条件是什么。注意本步骤强调的是做什么?而不是怎么做。对问题的描述 应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。 例如:输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范 围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输 入?对非法输入的回答方式是什么等。这一步
7、还应该为调试程序准备好测试数 据，包括合法的输入数据和非法形式的输入数据。（二）数据类型和系统设计在设计这一步骤中需分概要设计和详细设计 两步实现。概要设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类 型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单 和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说 明尽可能明确具体。作为概要设计的结果，应写出每个抽象数据类型的定义 (包括数据结构的描述和每个基本操作的规格说明 )，各个主要模块的
8、算法， 并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的 规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写 规范用类 C 语言写出函数形式的算法框架。在求精的过程中，应尽量避免陷 入语言细节，不必过早表述辅助数据结构和局部变量。(三) 编码实现和静态检查编码是把详细设计的结果进一步求精为程序 设计语言程序。程序的每行不要超过 60 个字符。每个函数体，即不计首部和 规格说明部分，一般不要超过 40行，最长不得超过60行，否则应该分割成 较小的函数。要控制讦语句连续嵌套的深度。如何编写程序才能较快地完成 调试是特别要注意的问题。对于编程很熟练的读者，如果基于详
9、细设计的伪 码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码， 而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输 入。然而，不管你是否写出编码的程序，在上机之前，认真的静态检查是必 不可少的。多数初学者在编好程序后处于以下两种状态之一：一种是对自己 的“精心作品“的正确性确信不疑；另一种是认为上机前的任务已经完成， 纠查错误是上机的工作。这两种态度是极为有害的。事实上，非训练有素的 程序设计者编写的程序长度超过 50 行时，极少不含有除语法错误以外的错 误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执
10、行程序(通常应先 分模块检查)；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序 逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后 者将比前者有效。(四) 上机准备和上机调试上机准备包括以下几个方面：(1) 高级语言文本(体现于编译程序用户手册)的扩充和限制。例如，常用 的BorlandC(C+)和MicrosoftC(C+)与标准C(C+)的差别，以及相互之间的 差别。(2) 如果使用C或C+语言，要特别注意与教科书的类C语言之间的细 微差别。(3) 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的 命令操作，以便顺利进行上机的基本活动。(4) 掌握调试工具
11、，考虑调试方案，设计测试数据并手工得出正确结果。上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行， 自底向上，即先调试低层函数。必要时可以另写一个调用驱动程序。这种表 面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效 率。调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想” 而应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整 理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。（五）总结和整理实验报告实验一 线性表及其应用一、实验目的1. 熟悉 C 语言的上机环境，进一步掌握 C 语言的结构特点。2. 掌握线性表的顺序存储结
12、构的定义及 C 语言实现。3. 掌握线性表在顺序存储结构即顺序表中的各种基本操作。二、实验内容 顺序线性表的建立、插入及删除。三、实验步骤1. 建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长 度。2. 利用前面的实验先建立一个顺序表L=21, 23, 14，5，56, 17，31, 然后在第 i 个位置插入元素 68。四、实现提示1. 由于 C 语言的数组类型也有随机存取的特点，一维数组的机内表示就 是顺序结构。因此，可用 C 语言的一维数组实现线性表的顺序存储。在此，我们利用 C 语言的结构体类型定义顺序表：#define MAXSIZE 1024typedef int ele
13、mtype; /* 线性表中存放整型元素 */typedef struct elemtype vecMAXSIZE;int len;/* 顺序表的长度 */sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代 码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2. 注意如何取到第 i 个元素，在插入过程中注意溢出情况以及数组的下 标与位序（顺序表中元素的次序）的区别。五、思考与提高1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表2. 在 main 函数里如果去掉 L=&a 语句，会出现什么结果？六、完整参考程序1.顺序线性表的建立、
14、插入及删除。#include #include #define MAX 30/定义线性表的最大长度enum BOOLFalse,True; /定义 BOOL 型 typedef structchar elemMAX;/线性表int last; /last 指示当前线性表的长度 sqlist;void initial(sqlist &);/初始化线性表BOOL insert(sqlist &,int,char); /在线性表中插入元素BOOL del(sqlist&,int,char &);/在线性表中删除元素int locate(sqlist,char);/在线性表中定位元素void prin
15、t(sqlist);/显示线性表中所有元素void main()sqlist S; /S 为一线性表int loc,flag=1;char j,ch;BOOL temp;printf(本程序用来实现顺序结构的线性表。n);printf(可以实现查找、插入、删除等操作。n);initial(S);/初始化线性表while(flag) printf(” 请选择:n);printf(1.显示所有元素n);printf(2.插入一个元素 n);printf(3.删除一个元素 n);printf(4.查找一个元素 n);printf(5.退出程序 n);scanf( %c,&j);switch(j)case 1:print(S); break; /显示所有元素case 2:printf(请输入要插入的元素(一个字符)和插入位置:n);printf(”格式：字符，位置；例如:a,2n);scanf( %c,%d,&ch,&loc); /输入要插入的元素和插入的位置 temp=insert(S,loc,ch);/插入if(temp=False) printf(插入失败!n);插入失败else printf(插入成功
