电 子 工 程 学 院

据 构 实 验 指

耿建平 蒋艳红 编

书数 结 导

前 言

数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间关系和操作等的学科。

数据结构作为一门独立的课程在国外是从1968年才开始设立的。在这之前，它的某些内容曾在其它课程如表处理语言中有所阐述。1968年在美国一些大学计算机系的教学计划中，虽然数据结果作为一门课程，但对课程的范围没有作明确的规定。当时，数据结构几乎和图论、特别是与表和树的理论为同义语。随后数据结构这个概念被扩充到网络、集合代数等方面。由于数据必须在计算机中进行处理，因此不仅考虑数据本身的数学性质，而且还必须考虑数据的存储结构，又随着数据库系统的不断发展，在数据结构课程中又增加了文件管理（特别是大型文件组织）的内容。

1968年美国唐·欧·克努特教授开创了数据结构的最初体系。他所著的《计算机程序设计技巧》第一卷《基本算法》，是第一本比较系统地阐述数据的逻辑结构和存储结构及其操作的著作，从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构化程序设计成为程序设计方法学的主要内容，数据结构的地位显得更为重要，人们认为程序设计的实质是对确定的问题选一个好的结构，加上一个好的算法。目前在我国，数据结构早已成为计算机专业的必修课之一。

数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究 有着密切的关系。无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存储数据元素更为方便，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。

目前数据结构的发展仍在继续，一方面，在面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来讨论数据结构已成为一种趋势，越来越被人们所重视。

说明：关于怎样在Visual C++ 6.0和Turbo C3.0中建立、编译和运行程序，请参见附录1和附录2。

目 录

实验一 线性表··································1 实验二 栈······································3 实验三

实验四

附录1

附录2

队列···································6 排序···································8 在Visual C++ 6.0中建立、编译和运行程序··············10 在Turbo C 3.0中建立、编译和运行程序···············14

实验一 线性表（Linear List）

线性表是最简单的一种数据结构。线性表是由n（n≥0）个数据元素组成的有限序列。当n=0时称为空表。线性表中的数据元素可以是各种各样的，但同一线性表中的数据元素必须有相同的属性，因此是属于同一数据对象的。

在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续存储单元依次存储线性表中的元素。其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。一般地，线性表的顺序存储结构可用C语言中的一个一维数组结构来描述。用这种方法存储的线性表简称为顺序表。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表中的数据元素（这组存储单元既可以是连续的，也可以是不连续的）。不要求逻辑上相邻的元素在物理位置上也相邻。链表中的结点可用C语言中的结构数据类型来描述。用这种方法存储的线性表简称为链表。链表中的结点只有一个链域的链表称为单链表。循环链表是一种首尾相接的链表。线性表上的基本操作有插入、删除、查找等。

一、 实验目的

掌握线性表的逻辑结构和存储结构，以及线性表的顺序存储结构和链式存储结构，熟悉对线性表的基本操作。

二、 实验内容

约瑟夫（Josephu）问题：假设有编号为1，2，……，n的n个人围坐成一圈，约定从编号为k（1 ≤ k ≤ n）的人开始报数，数到m的那个人出列，他的下一个人从1开始重新报数，数到m的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号的序列。若n=8，k=3，m=4，则出队序列为：62743518。

三、 实验原理

因为此问题中有n个人，因此我们可以使用线性表来表示n个人，又由于这n个人围坐成一圈，因此我们很自然地想到可以使用一个不带头结点的单循环链表L实现。报数为m的人出列，可以从单循环链表中删除对应的该结点（假设该结点编号为d）来表示，直到链表L为空时，说明n个人已经全部出列。这样就可以求得出队序列。

因此，我们可以画出程序流程图，如图1所示。

四、 思考题

如果不使用单循环链表，能否可以使用线性表的顺序存储结构（数组）实现。如果可以，那么应该怎样处理n个人围坐成一圈？

图1 求解约瑟夫（Josephu）问题的流程图

实验二 栈（Stack）

栈是一种特殊的线性表，这种表只能在固定的一端进行插入和删除操作，通常称这一端为栈顶（top），不能进行插入和删除的一端称为栈底（bottom）。不含元素的栈称为空栈。由于只允许在栈顶进行插入和删除操作，所以栈的操作是按照“后进先出”（Last In First Out，缩写为LIFO）原则进行的。栈的顺序存储结构简称为顺序栈，栈的链式存储结构简称为链栈。栈的基本操作有入栈、出栈、取栈顶、置空栈、判栈空等操作。

一、 实验目的

掌握栈的LIFO特点，编写栈的各种操作函数，掌握栈的应用方法，理解栈的重要作用。

二、 实验内容

任选下列一个内容或全部进行实验。

1. 数制转换

将十进制数转换成其它进制的数。

例：十进制转换成八进制：(66)10=(102)8

2. 一个简单的行编辑程序

一个简单的行编辑程序的功能是：接受用户从终端输入的字符，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定'#'为退格符，表示前一个字符无效，'@'为退行符，表示当前行所有字符均无效，以换行符（'\n'）表示输入结束。

例：在终端上用户输入为whli##ilr#e(s#*s)

则应为while(*s)

三、实验原理

1. 数制转换

将十进制数转换成其它进制的数，我们可以采用如下的方法：

例：十进制转换成八进制：(66)10=(102)8

66/8=8 余 2

8/8 =1 余 0

1/8 =0 余 1

结果为余数的逆序：102。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的LIFO性质，故可用栈来实现数制转换。

因此，我们可以画出程序流程图，如图2所示。

图2 求解数制转换问题的流程图 2. 一个简单的行编辑程序

我们可以用一个栈来实现这种功能的文字编辑器，每次读入一个字符，编辑器就进行判别：若读入的字符是 '#'，则退栈；若读入的字符是'@'，则置空栈；若读入的字符是'\n'，则编辑结束；当读入其余字符时，则执行进栈操作，将其加入栈中。

因此，我们可以画出程序流程图，如图2所示。

四、思考题

请考虑栈的“下溢”和“上溢”是否是出错状态？还有哪些问题可以使用栈这种数据结构来解决？如判断一个算术表达式中的左右括号正确是否匹配。

图3 一个简单的行编辑程序的流程图

实验三 队列（Queue）

队列是限定只能在表的一端进行插入，而在表的另一端进行删除的线性表。因此队列是一种“先进先出”（First In First Out，缩写为 FIFO）的线性表。队列中没有元素时称为空队列。在队列中，允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列的顺序存储结构称为顺序队列，队列的链式存储结构称为链队列。队列的基本操作有置空队列、判队空、取队头、入队、出队等操作。

一、 实验目的

掌握队列的FIFO的特点，编写循环队列的各种基本操作的函数，掌握循环队列的应用方法，理解队列的重要作用。

二、 实验内容

打印二项式 ( a + b ) i 展开系数，也就是扬辉三角，国外叫做Pascal’s triangle。如下图为扬辉三角的前8行数据。

扬辉三角

1

1 1

1 21

1 33 1

1 46 4 1

1 510 10 5 1

1 615 20 15 6 1

1 721 35 35 217 1

1 828 56 70 56288 1

三、实验原理

我们通过观察可以发现，扬辉三角除了第一行外，在打印第i行时用到了第i–1行的数据。因此，我们在输出第i-1行数据时，同时将其逐个入队，以便输出第i行数据时令其出队，参加运算生成第i行数据。一般地，凡是这类逐行处理的情况都少不了用队列作为其辅助工具。

因此，我们可以画出程序流程图，如图4所示。

四、思考题

循环队列有什么好处？设循环队列的空间为n，是否这n个空间都可以用作队列？

图4 打印扬辉三角程序的流程图

实验四 排序（Sorting）

排序是将一个数据元素（或记录）的无序序列，重新排列成一个按排序关键字递增（或递减）的有序序列的过程。在计算机软件设计中，排序占有相当重要的地位。排序分为内排序和外排序。我们只讨论内排序。内排序主要的排序算法有：插入排序、交换排序、选择排序等。排序算法有稳定和不稳定之分。排序的时间开销主要是指执行算法中关键字的比较次数和记录移动的次数。

一、 实验目的

掌握常用的几种内部排序算法。理解各种内部排序法的基本思想和特点，熟悉内部排序法的排序过程，记住各种算法的是时间复杂度，以便在实际应用中，根据实际问题的要求，选择合适的排序方法。

二、 实验内容

选用直接插入排序算法编写程序对下列记录进行排序。有兴趣的同学可以多选择几种排序算法进行比较。

49 38 65 97 76 13 27 49 55 04

三、实验原理

假设待排序的记录存放在数组R[n]中，初始时R[1]自成为一个有序区，无序区则是R[2]到R[n-1]，然后依次将R[2]，R[3]，…，插入到有序区中，直至i = n-1时，将R[n-1]插入到有序区为止。具体做法是将待插入记录R[i]的关键字依次与有序区中记录R[j]（j = i-1，i-2，…，1）的关键字进行比较，若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。因为关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可。另外，我们将R[0]作为监视哨来减少测试循环条件的时间。

直接插入排序算法的流程图如图9所示。

四、思考题

通过分析，判断直接插入排序算法是稳定的还是不稳定的？

图9 直接插入排序算法流程图

附录1：在Visual C++ 6.0中建立、编译和运行程序 确认系统已经安装Visual C++ 6.0，以下简称VC6.0。

1、启动VC6.0，选取菜单File->New，出现如下图所示的对话框。

2、选取“Project”属性单中的“Win32 Console Application”， 在“”中输入工程要保存的位置为“E:\”（不输入引号，以后同），最后在“Project name”中输入工程名“Graph”（这里假设为Graph），则在“Location”中会显示“E:\Graph”，最后按下“OK”按钮。

3、出现如下图所示的对话框。选取“”， 按下“”按钮。

4、出现如下图所示的对话框，该对话框显示了工程的一些特征。 按下“OK”按钮。

5、按下“OK”按钮，则出下如下图所示的界面。

6、用鼠标单击“Graph classes”左边的“+”号，则出现“Globals”，同样单击“Globals”

左边的“+”号，则出现main()。单击main()，则在右边视图中出现主函数main()。注意：要选取ClassView。如下图所示。

7、在“#include "stdafx.h"”下，输入代码，行，否则编译出现错误。如下图所示。

8、最后按下工具栏中的运行程序，或者选取“Build”菜单中的“Execute Graph.exe”，或者按下“Ctrl+F5”键（按住Ctrl键不放，同时按下F5键）运行程序。如下图所示。