数据结构(C语言版)实验指导书

电 子 工 程 学 院

据 构 实 验 指

耿建平 蒋艳红 编

书数 结 导

前 言

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

数据结构作为一门独立的课程在国外是从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'）表示输入结束。…… 此处隐藏：2190字，全部文档内容请下载后查看。喜欢就下载吧 ……