《数据结构实验手册修订版》由会员分享，可在线阅读，更多相关《数据结构实验手册修订版（39页珍藏版）》请在金锄头文库上搜索。
1、1第一部分第一部分 C C 语言基本知识语言基本知识数据结构是计算机专业及相关专业的核心基础课。上机实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活” ，起到深化理解和灵活掌握教学内容的目的。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节。多年的教学实践表明，学生的程序设计基础并不一致，相当一部分人基础较为薄弱，对上机实验感到
2、非常困难。存在的主要问题是：不能正确的输入数据，结构体概念陌生，函数的传址调用概念不清，有关指针的内容理解不深。因此，有必要将数据结构所必须使用的 C 语言语法在此做简单介绍。如果学生基础好，可以跳过这一部分内容不看。一、基本输入和输出基本输入和输出看起来简单的输入/输出，往往是上机实验最容易出错的地方，尤其是输入。对于一个 算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。1 输入输入C语言的输入是由系统提供的scanf( )等函数实现， 在程序的首部一般要求写入：# include 因为标准输入/输出函数都存在于头文件 stdio.h 之中，现将其包含进来方可使用这些 常用的输
3、入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/输出 函数。 函数scanf()的功能很丰富，输入格式也是多种多样，这是大家较为熟悉的知识，这里 不做详细介绍。在使用中需要注意以下几个问题。（1）一条scanf( )语句有多个变量、并且都是数值型（int, float, double）时，在输入 数据时应该在一行之内键入多个数据，数据之间空格分隔。例如： int n; float x; scanf (“%d %f ” , 正确的输入应是：整数 空格 实数 回车。例如：就是在两个数据之间使用空格键为分隔符，最后打回车键。 如果语句中在%d 和%f 之间有一个逗号： scanf
4、 (“%d ，%f ” , 正确的输入应是：整数 逗号 实数 回车。例如：（2）在需要字符型变量或字符串输入时，要单独写一条输入语句，这样不易出错。 如果在同一条scanf( )语句中将字符型和数值型混合输入常常会出错。因为键盘输入时在 数值型数据之间空格键起分隔符作用，但是在字符或字符串之间， 空格会被当100 3.14 100，3.14 2做一个字符，而不能起到分隔符的作用。所以将它们混在一起容易出错。（3）在scanf( )语句中变量写法应该是该变量的地址，这一点常被忽视。例例1 请看下列程序： 1: viod main() 2: char name10, ch ; 3: int num
5、; float x; 4: printf(“n 请输入姓名：”); scanf(“%s”, name); 5: printf(“n 请输入性别：”); scanf(“%c”, 6: printf(“n 请输入学号和成绩：”); scanf(“ %d%f”, ; 为了方便说明问题程序中加了行号，运行时当然不允许行号。一般情况下在scanf( ) 语句中的变量名之前要加上求地址符printf(“n %d%d%d”,n,m,p);printf(“n %6d%6d%6d”,n,m,p); /提倡使用的语句 第一行输出是： 102030 第二行输出是： 10 20 30 （2）在输入语句scanf( )
6、之前先使用printf( )输出提示信息，但是在printf( )最后不 能使用换行符。int x;printf(“n x=?”); /句尾不应使用换行符scanf( “%d”, 这样使光标与提示信息出现在同一行上，光标停在问号后边：X=? 。（3）在该换行的地方，要及时换行。3int i;printf(“数据输出如下：n”); / 需要换行for (i=0; iint sumx (int a, int b, int c) /* 计算三个整数之和的函数 */ int s;s=a+b+c;return s; void display( ) /* 输出一条线的函数 */ printf(”-n“);
7、 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); printf(“n“); display( ); x=15; y=16; z=17;4sa=sumx(x, y, z); /* 在赋值语句中调用函数 sumx( ) */ printf(“n “ sum=%d”,sa); printf(“n %6d%6d%6dn”,x,y,z); display( )
8、; /* 程序结束 */运行结果：运行结果： - sum= 62 2 2 -sum=4815 16 17 -2. 关于函数的参数传递关于函数的参数传递函数在被调用时，由主调程序提供实参，将信息传递给形参。在调用结束后，有时形 参可以返回新的数据给主调程序。这就是所谓参数传递。各种算法语言实现参数传递的方 法通常分为传值和传址两大类。在上例中函数 sumx( )的设计和主函数对它的调用，就是传值调用。第一、第二次调 用，带入的实参均是三个整型变量。调用函数返回后，在主程序中输出实参的值仍与调用 之前相同。传值调用的主要特点是数据的单向传递，由实参通过形参将数据代入被调用函 数，不论在调用期间形参
9、值是否改变，调用结束返回主调函数之后，实参值都不会改变。在不同的算法语言中，传址调用的语法有所不同。在 PASCAL 语言中用变参实现传址。 在 C 语言中采用指针变量做形参来实现传址。传址调用的主要特点是可以实现数据双向传 递，在调用时实参将地址传给形参，该地址中的数据代入被调用函数。如果在调用期间形 参值被改变，也即该地址中的数据发生变化，调用结束返回主调函数之后，实参地址仍然 不变，但是该地址中的数据发生相应改变。这就是数据的双向传递。现看一例题：例例 3 设计一个函数实现两个数据的交换，在主程序中调用。 #include viod swap( int *a, int *b) ； /*
10、函数原型声明 */ void main( ) int x=100, y=800; printf(“n %6d%6d”, x, y); /* 输出原始数据 */swap( /* 调用交换数据的函数 swap() */printf(“n %6d%6d”, x ,y); /* 输出交换后的数据 */ viod swap( int *a, int *b) int c; c=*a; *a = *b; *b=c; 运行结果：运行结果：100 800800 100 实践证明 x,y 的数据在调用函数前后发生了交换变化。形参是指向整形的指针变量 a5和 b，在函数体内需要交换的是指针所指的存储单元的内容，因此
11、使用*a = *b;这样的写法。 在调用时，要求实参个数、类型位置与形参一致。因为实参应该是指针地址，所以调用语 句 swap(printf(“在函数 fa 中: a=%dn“,a);void fb(int printf(“在函数 fb 中: a=%dn“,a); void fc(int *a) /a 为指针类型，数据双向传递，在函数中改变*a 的值，其结果将带 回主调函数 (*a)+;printf(“在函数 fc 中: *a=%dn“,*a); void main( ) int n=1,*p;p=printf(“在主程中，调用函数 fa 之前: n=%dn“,n);fa(n);printf(
12、“在主程中，调用函数 fa 之后，调用函数 fb 之前: n=%dn“,n);fb(n);printf(“在主程中，调用函数 fb 之后，调用函数 fc 之前: n=%dn“,n);fc(p);printf(“在主程中，调用函数 fc 之后: n=%dn“,n); 运行结果：运行结果： 在主程中，调用函数 fa 之前：n=1 在函数 fa 中：a=2 在主程中，调用函数 fa 之后，调用函数 fb 之前: n=1 在函数 fb 中：a=26在主程中，调用函数 fb 之后，调用函数 fa 之前: n=2 在函数 fc 中：*a=3 在主程中，调用函数 fc 之后，n=3需要进一步说明的是，C 语
13、言的传址调用比较复杂，不如 C+的引用调用方便。因此 建议大家采用 Visual C+作为编译环境，在此环境下可以兼容 C 程序，并且可以直接使用 引用参数，算法变为程序的过程就会容易很多。三、三、 结构体及运用结构体及运用数据结构课程所研究的问题均运用到“结构体” 。在 C 语言中结构体的定义、输入/输 出是数据结构程序设计的重要语法基础。定义结构体的一般格式： struct 结构体类型名 类型名 1 变量名 1； /数据子域 类型名 2 变量名 2； 类型名 n 变量名 n； ； 其中 struct 是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的 结构体类型的变量，声明创
14、建一个结构体变量的方法是： struct 结构体类型名 结构体变量名； 例如： struct ElemType /* 定义结构体 */ int num; char name10; ; struct ElemType x； /* 声明结构体变量 x */ 另外有一种方法使用 typedef 语句定义结构体，在声明结构体变量时可以不写 struct， 使得书写更加简便。例如：typedef struct int num;char name10; ElemType； ElemType 就是一个新的类型名，并且是结构体类型名。声明变量 x 的语句是：ElemType x; 一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型（int char 等） ，也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是 数组。它们也可以称为结构体的数据成员。 通过“结构体变量名.数据子域” 可以访问数据子域。例例 5 设计 Student 结构体，在主程序中运用。 #include #include typedef struct /* 定义结构体 Student */ long num; /* 学号 */int x; /* 成
