数据结构实验指导

第一部分 c语言基本知识。

一基本输入和输出4

二函数与参数传递6

三结构体及运用8

第二部分上机实验习题。

上机实验要求及规范11

实习一复数adt及其实现13

实习二线性表15

实习三栈和队列23

实习四串31

实习五数组33

实习六树与二叉树35

实习七图37

实习八查找43

实习九排序45

第一部分 c语言基本知识。

如何选择描述数据结构和算法的语言是十分重要的问题。传统的方法是用pascal语言，由于该语言语法规范、严谨，非常适用于数据结构课程教学。在windows 环境下涌现出一系列的功能强大、面向对象的程序开发工具，如：

visual c++,borland c++,visual basic, visual foxpro等。由于visual delphi的出现，使pascal仍不失为一种优秀的算法描述工具。近年来在计算机科学研究、系统开发、教学以及应用开发中，ｃ语言的使用越来越广泛。

因此，本教材采用类c语言进行算法描述。

按照传统的数据结构教材写法，只是注重算法思想和方法。并不关心具体使用何种语言工具来实现，默认学生已经能够具备扎实的程序设计基础和能力。随着计算机科学的发展、教学改革的深化，数据结构的开课时间各个高校有所不同，普遍有所提前。

大学生入学起点就存在一定的差异，即使在大学一年级学习了某种程序设计语言，学生中能力和水平的差异依然存在。实践表明在数据结构教学过程中，如果学生的程序设计语言基础薄弱，就会影响正常教学进度。数据结构不仅具有较强的理论性，更具有较强的实践性。

当前国内、国外一些优秀的数据结构教材已经是兼顾理论和实践两个方面。因此，有必要将数据结构所必须使用的c语言语法在此做简单介绍。根据多年教学实践，学生完成上机实验练习时遇到的主要问题是，不能正确的输入数据，结构体概念陌生，函数的传址调用概念不清，指针与链表有的没有学过。

由于篇幅所限，这里仅对前三个问题加以介绍。如果学生基础好，可以越过这一部分内容不看。

一、基本输入和输出。

对于重要的数据结构算法，均要求进行上机实验。而上机实践中离不开数据的输入/输出。看起来简单的输入/输出，往往是上机实验最容易出错的地方，尤其是输入。

对于一个算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。

1．输入。

c语言的输入是由系统提供的scanf()等函数实现，在程序的首部一般要求写入：

# include <>

因为标准输入/输出函数都存在于头文件之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/输出函数。

函数scanf()的功能很丰富，输入格式也是多种多样，这是大家较为熟悉的知识，这里不做详细介绍。在使用中需要注意以下几个问题。

1）一条scanf()语句有多个变量、并且都是数值型（int, float, double）时，在输入数据时应该在一行之内键入多个数据，数据之间空格分隔。例如：

int n; float x;

scanf (“d %f ” n, &x);

正确的输入应是：整数空格实数回车。例如：

就是在两个数据之间使用空格键为分隔符，最后打回车键。

如果语句中在%d 和%f 之间有一个逗号：

scanf (“d ，%f ” n, &x);

正确的输入应是：整数逗号实数回车。例如：

2）在需要字符型变量或字符串输入时，要单独写一条输入语句，这样不易出错。

如果在同一条scanf()语句中将字符型和数值型混合输入常常会出错。因为键盘输入时在数值型数据之间‘空格键’起‘分隔符’作用，但是在字符或字符串之间，‘空格’会被当做一个字符，而不能起到‘分隔符’的作用。所以将它们混在一起容易出错。

（3）在scanf()语句中变量写法应该是该变量的地址，这一点常被忽视。

请看下列程序：

1: viod main()

为了方便说明问题程序中加了行号，运行时当然不允许行号。一般情况下在scanf()语句中的变量名之前要加上求地址符&，上述程序第5，6行之中就是这样。为什么第4行的name前面不加&呢？

因为name代表字符串，即是一维字符数组，一维数组名本身就是一个地址，是该数组的首地址，所以name前面不加&。

在本程序中把字符串、字符、数值型变量分别写入不同的scanf()语句，输入数据的具体形式如下：

请输入姓名：zhanghua

请输入性别：v

请输入学号和成绩：101 90.5

请考虑如果姓名输入成：zhang hua，会出现什么现象？那样只会读入zhang做姓名，而hua被忽略，还会影响后面的输入语句无法正确读入数据。

因此，应该充分重视数据的输入技术。

2．输出。

c语言的输出是由系统提供的printf()等函数来实现，在程序的首部一般要求写入：

# include <>

输出函数printf()的语法一般容易掌握，这里强调的是怎样合理巧妙的使用它。

1. 在连续输出多个数据时，数据之间一定要有间隔，不能连在一起。

int n=10, m=20, p=30;

printf(“ %d%d%d”,n,m,p);

printf(“ %6d%6d%6d”,n,m,p); 提倡使用的语句。

第一行输出是： 102030

第二行输出是： 10 20 30

2. 在输入语句scanf()之前先使用printf()输出提示信息，但是在printf()最后不能使用换行符。

int x;

printf(“ x句尾不应使用换行符。

scanf( “d”,&x);

这样使光标与提示信息出现在同一行上，光标停在问号后边：x=?□

3. 在该换行的地方，要及时换行。

int i;

printf(“数据输出如下：需要换行。

for (i=0; i<8; i++)printf(“%6d”, i几个数据在同一行输出，不能换行。

4. 在调试程序时多加几个输出语句，以便监视中间运行状况。程序调式成功后，再去掉这些辅助输出语句。

二、函数与参数传递。

函数的设计和调用是程序设计必不可少的技能，是程序设计最重要的基础。一些初学者之之所以感到编程难，就是忽视了这个基础。在传统的面向过程的程序设计中，往往提倡模块化结构化程序设计，不论basic、 fonftran、pascal还是其他高级语言，最终要涉及到子函数的设计和使用。

c语言的源程序是由一个主函数和若干（或零个）子函数构成，函数是组成c语言程序的基本单位。函数具有相对独立的功能，可以被其他函数调用，也可调用其他函数。当函数直接或间接的调用自身时，这样的函数称为递归函数。

是否能够熟练的设计和使用函数，是体现一个人程序设计能力高低的基本条件。因此有必要回顾和复习c语言函数的基本概念。

1函数的设计。

函数设计的一般格式是：

类型名函数名（形参表）

函数设计一般是处理一些数据获得某个结果，因此函数可以具有返回值，上面的类型名就是函数返回值的类型，可以是int, float…..等。例如：

float funx(形参表)

数据结构实验指导

数据结构实验指导

数据结构实验指导

数据结构实验指导

其他用户还读了