《数据结构实验指导》由会员分享，可在线阅读，更多相关《数据结构实验指导（50页珍藏版）》请在金锄头文库上搜索。
1、1数 据 结 构 实 验 指 导李英龙 编湖南科技大学数学与计算科学学院2内 容 简 介数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系
2、实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结构实验指导” 。本参考书包括 C 语言基础知识和上机实验习题两部分。在 C 语言基础知识部分，主要介绍了输入/ 输出、函数及参数传递和结构体的概念应用。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。在实验部分，包括有完整的 C 语言源程序例题，介绍了一些设计数据结构题目所需的 C 语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。由于时间仓足、水平有限，书中难免存在错误和不妥之处，敬请读者指正。李英龙2007 年 3 月 编订于湖
3、南科技大学北校区3目 录第一部分 C 语言基本知识一 基本输入和输出 -4二 函数与参数传递 -6三 结构体及运用 -8第二部分 上机实验习题上机实验要求及规范 - 11实习一 复数ADT及其实现 -13实习二 线性表 -15实习三 栈和队列-23实习四 串 -31实习五 数组 -33实习六 树与二叉树 -35实习七 图 -37实习八 查找 -43实习九 排序 -454第一部分 C 语言基本知识如何选择描述数据结构和算法的语言是十分重要的问题。传统的方法是用 PASCAL语言，由于该语言语法规范、严谨，非常适用于数据结构课程教学。在 Windows 环境下涌现出一系列的功能强大、面向对象的程序
4、开发工具，如：Visual C+, Borland C+, Visual Basic, Visual Foxpro 等。由于 Visual Delphi 的出现，使 PASCAL 仍不失为一种优秀的算法描述工具。 近年来在计算机科学研究、系统开发、教学以及应用开发中，语言的使用越来越广泛。因此，本教材采用类 C 语言进行算法描述。按照传统的数据结构教材写法，只是注重算法思想和方法。并不关心具体使用何种语言工具来实现，默认学生已经能够具备扎实的程序设计基础和能力。随着计算机科学的发展、教学改革的深化，数据结构的开课时间各个高校有所不同，普遍有所提前。大学生入学起点就存在一定的差异，即使在大学一年
5、级学习了某种程序设计语言，学生中能力和水平的差异依然存在。实践表明在数据结构教学过程中，如果学生的程序设计语言基础薄弱，就会影响正常教学进度。数据结构不仅具有较强的理论性，更具有较强的实践性。当前国内、国外一些优秀的数据结构教材已经是兼顾理论和实践两个方面。因此，有必要将数据结构所必须使用的 C 语言语法在此做简单介绍。根据多年教学实践，学生完成上机实验练习时遇到的主要问题是，不能正确的输入数据，结构体概念陌生，函数的传址调用概念不清，指针与链表有的没有学过。由于篇幅所限，这里仅对前三个问题加以介绍。如果学生基础好，可以越过这一部分内容不看。一、基本输入和输出对于重要的数据结构算法，均要求进行
6、上机实验。而上机实践中离不开数据的输入/输出。看起来简单的输入/输出，往往是上机实验最容易出错的地方，尤其是输入。对于一个算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。1 输入C语言的输入是由系统提供的scanf() 等函数实现， 在程序的首部一般要求写入：# include 因为标准输入/输出函数都存在于头文件 stdio.h 之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/ 输出函数。函数scanf()的功能很丰富，输入格式也是多种多样，这是大家较为熟悉的知识，这里不做详细介绍。在使用中需要注意以下几个问题。（1）
7、 一条scanf()语句有多个变量、并且都是数值型（int, float, double）时，在输入数据时应该在一行之内键入多个数据，数据之间空格分隔。例如：int n; float x;scanf (“%d %f ” , 正确的输入应是：整数 空格 实数 回车。例如：100 3.14 5就是在两个数据之间使用空格键为分隔符，最后打回车键。如果语句中在%d 和%f 之间有一个逗号：scanf (“%d ，%f ” , 正确的输入应是：整数 逗号 实数 回车。例如：（2） 在需要字符型变量或字符串输入时，要单独写一条输入语句，这样不易出错。如果在同一条scanf()语句中将字符型和数值型混合输入
8、常常会出错。因为键盘输入时在数值型数据之间空格键起分隔符作用，但是在字符或字符串之间， 空格会被当做一个字符，而不能起到分隔符的作用。所以将它们混在一起容易出错。（3）在scanf()语句中变量写法应该是该变量的地址，这一点常被忽视。请看下列程序：1: viod main()2: char name10, ch ;3: int num; float x;4: printf(“n 请输入姓名：”); scanf(“%s”, name);5: printf(“n 请输入性别：”); scanf(“%c”, 6: printf(“n 请输入学号和成绩：”); scanf(“ %d%f”, ;为了方便
9、说明问题程序中加了行号，运行时当然不允许行号。一般情况下在scanf()语句中的变量名之前要加上求地址符& ，上述程序第5，6行之中就是这样。为什么第4行的name前面不加&呢？因为name 代表字符串，即是一维字符数组，一维数组名本身就是一个地址，是该数组的首地址，所以name前面不加&。在本程序中把字符串、字符、数值型变量分别写入不同的scanf()语句，输入数据的具体形式如下：请输入姓名：ZhangHua 请输入性别：v请输入学号和成绩：101 90.5请考虑如果姓名输入成：Zhang Hua，会出现什么现象？那样只会读入Zhang做姓名，而Hua被忽略，还会影响后面的输入语句无法正确读
10、入数据。因此，应该充分重视数据的输入技术。2 输出C语言的输出是由系统提供的printf()等函数来实现， 在程序的首部一般要求写入：# include 因为标准输入/输出函数都存在于头文件 stdio.h 之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/ 输出函数。100，3.14 6输出函数printf()的语法一般容易掌握，这里强调的是怎样合理巧妙的使用它。1. 在连续输出多个数据时，数据之间一定要有间隔，不能连在一起。int n=10, m=20, p=30;printf(“n %d%d%d”,n,m,p);printf(“n
11、 %6d%6d%6d”,n,m,p); /提倡使用的语句第一行输出是： 102030第二行输出是： 10 20 302. 在输入语句scanf()之前先使用printf()输出提示信息，但是在 printf()最后不能使用换行符。int x;printf(“n x=?”); /句尾不应使用换行符scanf( “%d”, 这样使光标与提示信息出现在同一行上，光标停在问号后边：X=? 。3. 在该换行的地方，要及时换行。int i;printf(“数据输出如下：n”); / 需要换行for (i=0; iint sumx (int a, int b, int c) /* 计算三个整数之和的函数 *
12、/ int s;s=a+b+c;return s; void display(void) /* 输出一条线的函数 */ printf(”-n“);void main( ) int x,y, z ,sa;x=y=z=2;display(); /* 画一条线 */printf(“n sum=%d”,sumx(x,y,z); /* 在输出语句中直接调用函数 sumx( ) */printf(“n %6d%6d%6d”,x,y,z);display(); x=5; y=6; z=7;sa=sumx(x, y, z); /* 在赋值语句中调用函数 sumx( ) */printf(“n “ sum=%d”,sa);printf(“n %6d%6d%6d”,x,y,z); display(); /* 程序结束 */运行结果：-sum= 62 2 2-sum=4815 16 17-2. 关于函数的参数传递函数在被调用时，由主调程序提供实参，将信息传递给形参。在调用结束后，有时形参可
