数据结构实验与习题
杨秀金 汪沁 编
浙江万里学院计算机系
1
内 容 简 介
数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结构实验与习题”。
本参考书包括C语言基础知识、上机实验习题和书面作业练习题三部分。
在C语言基础知识部分，主要介绍了输入/输出、函数及参数传递和结构体的概念应用。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。
在实验部分，包括有完整的C语言源程序例题，介绍了一些设计数据结构题目所需的C语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。
在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。
由于时间仓足、水平有限，书中难免存在错误和不妥之处，敬请读者指正。
杨秀金 汪沁
2004年2月 修订
于浙江万里学院钱湖校区
目 录
2
第一部分 C语言基本知识
一 基本输入和输出---------------------------------------------------------------------------1 二 函数与参数传递---------------------------------------------------------------------------3 三 结构体及运用 ----------------------------------------------------------------------------5
第二部分 上机实验习题
上机实验要求及规范------------------------------------------------------------------- 8
实习一 复数ADT及其实现--------------------------------- ----------------------------10 实习二 线性表
-----------------------------------------------------------------------------12
实习三 栈和队列
--------------------------------------------------------------------------20 实习四 串
-----------------------------------------------------------------------------------28 实习五 数组
--------------------------------------------------------------------------------30
实习六 树与二叉树
-----------------------------------------------------------------------32 实习七 图
-----------------------------------------------------------------------------------34 实习八 查找
--------------------------------------------------------------------------------40 实习九 排序
-----------------------------------------------------------------------------
3
---42
第三部分 书面作业练习题
习题一 绪论
--------------------------------------------------------------------------------48
习题二 顺序表示（线性表、栈和队列）
--------------------------------------------51 习题三 链表（线性表、栈和队列）
--------------------------------------------------54 习题四 串
-----------------------------------------------------------------------------------57- 习题五 数组
--------------------------------------------------------------------------------58
习题六 树与二叉树
-----------------------------------------------------------------------60 习题七 图
-----------------------------------------------------------------------------------69 习题八 查找
--------------------------------------------------------------------------------75 习题九 排序
--------------------------------------------------------------------------------78
4
第一部分 C语言基本知识
如何选择描述数据结构和算法的语言是十分重要的问题。传统的方法是用PASCAL语言，由于该语言语法规范、严谨，非常适用于数据结构课程教学。在Windows 环境下涌现出一系列的功能强大、面向对象的程序开发工具，如：Visual C++, Borland C++, Visual Basic, Visual Foxpro等。由于Visual Delphi的出现，使PASCAL仍不失为一种优秀的算法描述工具。 近年来在计算机科学研究、系统开发、教学以及应用开发中，Ｃ语言的使用越来越广泛。因此，本教材采用类C语言进行算法描述。
按照传统的数据结构教材写法，只是注重算法思想和方法。并不关心具体使用何种语言工具来实现，默认学生已经能够具备扎实的程序设计基础和能力。随着计算机科学的发展、教学改革的深化，数据结构的开课时间各个高校有所不同，普遍有所提前。大学生入学起点就存在一定的差异，即使在大学一年级学习了某种程序设计语言，学生中能力和水平的差异依然存在。实践表明在数据结构教学过程中，如果学生的程序设计语言基础薄弱，就会影响正常教学进度。数据结构不仅具有较强的理论性，更具有较强的实践性。当前国内、国外一些优秀的数据结构教材已经是兼顾理论和实践两个方面。因此，有必要将数据结构所必须使用的C语言语法在此做简单介绍。根据多年教学实践，学生完成上机实验练习时遇到的主要问题是，不能正确的输入数据，结构体概念陌生，函数的传址调用概念不清，指针与链表有的没有学过。由于篇幅所限，这里仅对前三个问题加以介绍。如果学生基础好，可以越过这一部分内容不看。
一、基本输入和输出
对于重要的数据结构算法，均要求进行上机实验。而上机实践中离不开数据的输入/输出。看起来简单的输入/输出，往往是上机实验最容易出错的地方，尤其是输入。对于一个算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。
1． 输入
C语言的输入是由系统提供的scanf()等函数实现， 在程序的首部一般要求写入： # include
因为标准输入/输出函数都存在于头文件 stdio.h 之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/输出函数。
函数scanf()的功能很丰富，输入格式也是多种多样，这是大家较为熟悉的知识，这里不做详细介绍。在使用中需要注意以下几个问题。
（1） 一条scanf()语句有多个变量、并且都是数值型（int, float, double）时，在输入
数据时应该在一行之内键入多个数据，数据之间空格分隔。例如： int n; float x;
scanf (“%d %f ” , &n, &x);
正确的输入应是：整数 空格 实数 回车。例如：
100 3.14
就是在两个数据之间使用空格键为分隔符，最后打回车键。
5