数据结构实验指导手册答案

《数据结构》

实验指导手册

计算机教研室

2008.6

1．实验教学的目的：通过实验，加深对算法与数据结构基本知识的理解，掌握数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。

2．实验教学的要求：学生每次实验前必须根据实验指导手册，设计出实验方案（程序和实验步骤）；在实验过程中要求独立进行程序调试和排错，必须学会使用在线帮助解决实验中遇到的问题，必须应用理论知识分析问题、解决问题。

3．实验内容：

实验1：VC6的使用

一、实验目的

理解和掌握如何使用Visual C＋＋6.0环境编写C/C＋＋程序。

二、实验环境

装有Visual C＋＋6.0的计算机。 本次实验共计4学时。

三、实验内容 1、熟悉VC6环境

掌握如何创建控制台应用程序。

掌握一些常用快捷键，例如编译F7，运行Ctrl＋F5，调试运行F5，单步运行F10/F11，设置断点F9，格式化代码Alt＋F8。

2、掌握如何编译程序

理解编译过程中的错误信息，并掌握如何排错。

3、掌握如何调试程序

掌握如何通过设置断点来单步调试程序，如何查看当前变量的值。

4、实验题：

完成实验教材的实验题1.1、1.2、1.3。要求：

实现该实验结果。通过该实验题，熟悉VC6环

第１章 上机实验内容及指导

上机实验是对学生的一种全面综合训练，是与课堂讲授的内容相辅相成的必不可少的一个教学环节。通过上机实验，既可以加深对讲授内容的理解、深化，也可以培养学生的思维能力和创造精神。在上机实验时，千万不要在已给出的源程序通过运行后就认为完成任务了，而要在所给的例子的基础上，完成每章的课后习题。

上机实验一般包括以下几个步骤：

（1）准备好上机所需的程序。为提高上机效率，上机前应认真检查手编程序，以减少错误率。

（2）上机输入和调试自己所编的程序。上机过程中，应该善于分析判断，尽量独立去处理出现的问题，这是提高调试程序能力的良好机会。

（3）程序调试通过后，要记录程序在不同条件下的运行结果，为实验报告作准备。

（4）上机结束后，要及时整理出实验报告。实验报告除了在开头写上班级、姓名、学号和完成日期外，还应该包括以下内容：

①实验题目 ②实验内容 ③程序构思 ④程序清单 ⑤运行结果

最后，在每次上机后，自己应该对程序的运行情况作一下分析，总结本次上机调试程序所取得的经验。若程序未能通过，应分析其原因。

- 1 -

第2章 线性表

实验一 线性表的顺序存储结构

一、实验目的

通过本次实验，掌握线性表的顺序存储结构的基本操作及

实验一 线性表

一、 实验目的

线性表是最简单、最常用的基本数据结构，在实际问题中有着广泛的应用。通过本章的实验，巩固对线性表逻辑结构的理解，掌握线性表的存储结构及基本操作的实现，为应用线性表解决实际问题奠定良好的基础，并进一步培养以线性表作为数据结构解决实际问题的应用能力。

（1）掌握线性表的顺序存储结构； （2）验证顺序表及其基本操作的实现；

（3）掌握数据结构及算法的程序实现的基本方法。 （4）掌握线性表的链接存储结构； （5）验证单链表及其基本操作的实现；

（6）进一步掌握数据结构及算法的程序实现的基本方法。 二、实验示例学习——顺序表操作 实验要求：

（1）建立含有若干个元素的顺序表；

（2）对已建立的顺序表实现插入、删除、查找等基本操作。 实现提示：

首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。

const int MaxSize=10;

template //定义模板类SeqList class SeqList {

public:

SeqList( ){length=0;} //

据 结 实 验 指 导 书

构1

数

目 录

实验说明 ................................................. 3 实验要求 ................................................. 4 实验1 线性表的顺序存储结构的实现及其应用 ................ 5 实验2 线性表的链式存储结构的实现及其应用 ............... 10 实验3 栈和队列的存储结构的实现 ......................... 17 实验4 树和二叉树的存储结构的实现 ....................... 26 实验5 图的存储结构的实现 ............................... 34 实验6 图的简单应用 .................................... 39 实验7 查找算法的实现................................... 44 实验8 排序算法的实现................................... 47 上机实验报告（仅

1

第一部分习题

第一章 绪论

一．单选题

1．若一个数据具有集合结构，则元素之间具有（ ）。

A．线性关系 B．层次关系 C．网状关系 D．无任何关系 2．下面程序段的时间复杂度为（ ）。 int i,j;

for(i=0;i

A．O(m2) B．O(n2) C．O(mхn) D．O(m+n) 3．执行下面程序段时，S语句被执行的次数为（ ）。 int i,j;

for(i=1;i<=n;i++) for(j=1;j<=i;j++) S;

A．n2 B．n2/2 C．n(n+1) D．n(n+1)/2

二．填空题

1．数据的逻辑结构被分为_____________、_____________、_____________和_____________四种。

2．数据的存储结构被分为_____________、_____________、_____________和_____________四种。

3．在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着_____________、_____________和_____________的联系。

4．在C语言中，一个数组a所占有的存储空间的大小即数组长度为

石 家 庄 铁 道 大 学

实 验 任 务 书

课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院

石 家 庄 铁 道 大 学

14学年—15学年第 2学期 数据结构实验任务书

专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 王明明 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的：

1、掌握线性表的定义；

2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：

定义一个包含学生信息（学号，姓名，成绩）的的顺序表或链表，使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息；

(3) 根据姓名进行查找，返回此学生的学号和成绩；

(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。

信息管理与信息系统专业《数据结构》实验指导

实验一 线性表的插入和删除

一、

实验目的

1、掌握使用Turbo Pascal上机调试线性表的基本方法；

2、掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、

实验要求

1、认真阅读和掌握本实验的程序。 2、上机运行本程序。

3、保存和打印出程序的运行结果，并结合程序进行分析。

4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果

三、

注意事项：

在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 四、

实验内容

程序1：线性表基本操作的实现

这个程序中演示了顺序表的创建、插入、删除和查找。 程序如下：

PROGRAM seqlist(input,output);

{线性表可能达到的最大长度} CONST

maxlen = 1024;

TYPE

elemtp = integer;

{线性表的顺序存储结构} TYPE

seqlisttp = RECORD

1

{用一维数组来描述线性表的顺序存储结构} elem: ARRAY[1..maxlen] OF elemtp;

{

《数据结构》实验指导书

杨先凤 朱小梅 编

西南石油大学计算机科学学院

二零零七年九月

目 录

写在上机实习之前 ........................................ I 实验一 顺序表的建立和基本运算 ........................... 1 实验二 实验三 实验四 实验五 实验六 实验七 实验八 实验九

链表的建立和基本运算 ............................. 8 栈结构及其应用 .................................. 14 队列应用 ....................................... 17 串的操作及应用 .................................. 18 二叉树的建立和遍历 .............................. 19 图的应用及其算法 ................................ 23 查找 ........................................... 27 内排序 .........

《数据结构与算法》实验指导书

《数据结构与算法》实验指导书

实验1 顺序表

一、实验目的

（1）掌握顺序表的逻辑结构、存储结构及描述方式。 （2）掌握顺序表的定位、插入、删除等操作。

二、实验要求

（1）调试程序要记录调试过程中出现的问题及解决办法； （2）给出每个问题的算法或画出流程图；

（3）编写程序要规范、正确，上机调试过程和结果要有记录，并注意调试程序集成环境的掌握及应用，不断积累编程及调试经验； （4）做完实验后给出本实验的实验报告。

三、实验设备、环境

奔腾以上计算机，装有Turbo C 2.0或Visual C++软件

四、实验步骤及内容

实验步骤：

1．根据题目，编写程序。 2．上机调试通过。

3．按照实验报告格式，撰写各实验报告。 实验内容：

（1）编写一个函数print_all_data，该函数的作用是逐个输出顺序表中所有数据元素的值。编写主函数，从键盘输入顺序表，调用函数print_all_data，测试结果。

（2）编写顺序表定位操作函数locata，该函数的作用是在顺序表中查找是否存在数据元素的值与变量x的值相等。如果存在满足条件的数据元素，则返回顺序表中和x值相等的第1个数据元素在表中的下标；如果不存在，则返回－

数据结构实验指导书

适用所有数据结构实验独立设课的专业

雷 文 梁金明 编写

概 述

一、课程目的

《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，实验题中的问题比平时的练习题要复杂，也更接近实际，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

本课程实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。

二、实验名称与学时分配

序号 1 2 3 4 5 6 链表应用 利用栈实现递归 链队列应用 二叉树遍历 图的遍历 实 验 名 称 线性表顺序存储结构 学时数 2 2 2 2 4 4 实验类型 验证 验证 验证 验证 综合 综合 三、实验要求

⒈ 问题分析

充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。

⒉ 数据结构设计 针对要求解决的问题，考虑各种可能的数据结构，并且