数据结构上机实验指导

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

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

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

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

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

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

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

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

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

- 1 -

第2章 线性表

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

一、实验目的

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

《数据结构》上机实验题目 （共8次，每次上机4小时）

第一阶段（线性部分）

《数据结构》第1上机题 （线性表练习） 1．编程实现书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现； 2．编程实现顺序表和单链表的就地逆置（习题集P18 2.21 2.22）。

《数据结构》第2上机题 （线性表练习）

1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B 分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P18 2.25 2.26）；

2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P19 2.38）。

《数据结构》 第3

《数据结构》上机实验题目 （共8次，每次上机4小时）

第一阶段（线性部分）

《数据结构》第1上机题 （线性表练习） 1．编程实现书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现； 2．编程实现顺序表和单链表的就地逆置（习题集P18 2.21 2.22）。

《数据结构》第2上机题 （线性表练习）

1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B 分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P18 2.25 2.26）；

2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P19 2.38）。

《数据结构》 第3

1． 已知长度为n的线性表L采用顺序存储结构，编写一个时间复杂度为O(n)，空间复杂度

为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

2． 用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小

到大顺序排列的，且这(m+n)个数据中没有相重的。设计一个算法将些两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中。

3． 已知线性表{a0,a1,……,an-1}按顺序存储，且每个元素都是不相等的整数。设计把所有

的奇数移到所有的偶数前边的算法（要求时间最少，辅助空间最少）。 4． 输入一组整型元素序列，建立单链表。

5． 写出在带头结点的单向链表l中删除第i个结点的算法。

6． 编写算法,将带头结点的单链表拆分成一个奇数链表和一个偶数链表。

7． 设C={a1,b1,a2,b2,……,an,bn}为一线性表，采用带头结点的Hc单链表存放，编写一个

就地算法，将其拆分成两个线性表，使得：A={a1,a2,…..,an} C={b1,b2,….,bn} 8． 编写出判断带头结点的双向循环链表L是否对称相等的算法。 9． 设计一算法，将一带头结点的数据域依次为a1,a2,…,an(n>=3)的单

实验一 线性表

一、 实验目的

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

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

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

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

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

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

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

const int MaxSize=10;

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

public:

SeqList( ){length=0;} //

数据结构上机答案

1.1顺序线性表的基本操作

#include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; if(L.length==0) printf(\ else { printf(\ for(i=0;i

int ListInsert_Sq(SqList &L,int i,int e) { if(i<1||i>L.length+1) return ERROR; ElemType *newbase,

《数据结构》

实验指导手册

计算机教研室

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

数

目 录

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

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

《计算机软件技术基础》

实验报告I—数据结构

班号： 0312207 学号： 031210335 姓名： 白雷

Email： leibai@nuaa.edu.cn 签名：

南京航空航天大学 2014年11月5日

第 1 页 共 22 页

《计算机软件技术基础》2014实验报告I—数据结构_03121210335_白雷

目录

实验一：顺序表的定义、创建、插入和删除操作，将数据元素显示出来。………………………3

实验二：单链表的定义、创建、插入和删除操作，将数据元素显示出

来。………………………6

实验三：二叉树的链式存储结构的数据结构定义、创建、先序/中序/后序遍历，并将结

果序列输出。………………………10

实验四：图的邻接表数据结构的定义、创建；图的深度优先遍历、广度优先遍历。………………………14

实验五：邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍

历。………………………18

第 2 页 共 22 页

《计算机软件技术基础》2014实验

数据结构上机报告

课程：有向图中求各顶点之间的最短路径

算法设计：

现设一个矩阵F，用来记录路径长度。初始时，顶点Vi到顶点Vj的最短路径长度F[i][j]=weight[i][j],即弧上的权值。若不存在,则F[][]=∞（程序中用1000表示）。此时，把矩阵F记做F0。F0考虑到了有弧相连直接到达的路径，但这个长度不是最短长度，所以要进行探索。

① 让路径经过V0（第一个顶点），并比较路径（Vi,Vj）和路径（Vi,V0,Vj）的长度，去较短的作为最短路径长度。其中，路径（Vi,V0,Vj）的长度等于路径（Vi,V0）和（V0,Vj）长度之和，即F[i][j]=F[i][0]+F[0][j]。把此时得到的矩阵F记做F1，F1考虑到了各项点间除直接到达的路径外，其他经过V0的路径，只取其中最短的作为最短路径长度。

② 在F1的基础上让路径经过第二个顶点V1，依照?的方法求得最短路径长度，得到F2。

③ 以此类推，经过n次试探，将n个顶点都考虑到路径之中，此时求得最短路径长度。

例：有向图如下：

求任意两个顶点之间的最短路径长度

程序运行如下：

程序代码：

#include using namespace std;

#def