2022年《数据结构》实验辅导 .pdf

1 数据结构实验辅导软件学院胡忠望一、C 语言基本知识（一）基本输入和输出（二）函数与参数传递（三）结构体及运用二、实验的正确步骤2011年 3 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 2 一、C 语言基本知识数据结构不仅具有较强的理论性，更具有较强的实践性。如何选择描述数据结构和算法的语言是十分重要的问题。因此，有必要将数据结构所必须使用的C 语言语法在此做简单介绍。根据多年教学实践，学生上机实验时遇到的主要问题是，不能正确的输入数据，结构体概念陌生，函数的传址调用概念不清，指针与链表难以理解。限于篇幅，这里仅对前三个问题加以介绍。一、基本输入和输出对于重要的数据结构算法，均要求进行上机实验。而上机实践中离不开数据的输入/输出。看起来简单的输入/输出，往往是上机实验最容易出错的地方，尤其是输入。对于一个算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。1 输 入C语言的输入是由系统提供的scanf()等函数实现，在程序的首部一般要求写入：# include 因为标准输入 /输出函数都存在于头文件stdio.h 之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/输出函数。函数 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() 2: char name10, ch ；3: int num；float x ；4: printf(“n 请输入姓名： ”)；scanf(“%s”, name)；5: printf(“n 请输入性别： ”)；scanf(“%c”, &ch)；6: printf(“n 请输入学号和成绩：”)；scanf(“ %d%f”, &n, &x)；100 3.14 100，3.14 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 3 ； 为了方便说明问题程序中加了行号，运行时当然不允许行号。一般情况下在scanf()语句中的变量名之前要加上求地址符& ，上述程序第5， 6行之中就是这样。为什么第4行的 name前面不加&呢？因为 name代表字符串， 即是一维字符数组，一维数组名本身就是一个地址，是该数组的首地址，所以 name前面不加 &。在本程序中把字符串、字符、数值型变量分别写入不同的scanf()语句，输入数据的具体形式如下：请输入姓名：ZhangHua 请输入性别：v 请输入学号和成绩：101 90.5 请考虑如果姓名输入成：Zhang Hua，会出现什么现象？那样只会读入Zhang做姓名，而 Hua被忽略，还会影响后面的输入语句无法正确读入数据。因此，应该充分重视数据的输入技术。2 输 出C语言的输出是由系统提供的printf() 等函数来实现，在程序的首部一般要求写入：# include 因为标准输入 /输出函数都存在于头文件stdio.h 之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/输出函数。输出函数 printf() 的语法一般容易掌握，这里强调的是怎样合理巧妙的使用它。1.在连续输出多个数据时，数据之间一定要有间隔，不能连在一起。int n=10, m=20, p=30；printf(“n %d%d%d ” ,n,m,p)；printf(“n %6d%6d%6d” ,n,m,p) ；/提倡使用的语句第一行输出是：102030 第二行输出是：10 20 30 2.在输入语句 scanf()之前先使用 printf() 输出提示信息， 但是在 printf() 最后不能使用换行符。int x ；printf(“n x=?”)；/句尾不应使用换行符scanf( “ %d ” ,&x)；这样使光标与提示信息出现在同一行上，光标停在问号后边：X=? 。3.在该换行的地方，要及时换行。int i ；printf(“数据输出如下：n”)；/ 需要换行for (i=0 ； i8； i+) printf(“ %6d ” , i )；/ 几个数据在同一行输出，不能换行4. 在调试程序时多加几个输出语句，以便监视中间运行状况。程序调式成功后，再去掉这些辅助输出语句。二、函数与参数传递函数的设计和调用是程序设计必不可少的技能，是程序设计最重要的基础。一些初学者之之所以感到编程难，就是忽视了这个基础。C 语言的源程序是由一个主函数和若干（或零个）子函数构成，函数是组成C 语言程序的基本单位。函数具有相对独立的功能，可以被其他函数调用，也可调用其他函数。当函数直接或间接的调用自身时，这样的函数称为递归函数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 4 是否能够熟练的设计和使用函数，是体现一个人程序设计能力高低的基本条件。1. 函数的设计函数设计的一般格式是：类型名函数名（形参表） 函数体； 函数设计一般是处理一些数据获得某个结果，因此函数可以具有返回值，上面的类型名就是函数返回值的类型，可以是int, float.等。例如：float funx( 形参表 ) 函数体； . 函数也可无返回值，此时类型是void 。例如：void funy(形参表 ) 函数体； 而函数体内所需处理的数据往往通过形参表传送，函数也可以不设形参表，此时写为：类型名函数名（ void） 函数体； 例 1.2 设计一个函数计算三个整数之和，再设计一个函数仅输出一条线。设计主函数调用两个函数。#include int sumx (int a, int b, int c) /* 计算三个整数之和的函数*/ 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= 6 2 2 2 - sum=48 15 16 17 - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 5 2. 关于函数的参数传递函数在被调用时，由主调程序提供实参，将信息传递给形参。在调用结束后，有时形参可以返回新的数据给主调程序。这就是所谓参数传递。各种算法语言实现参数传递的方法通常分为传值和传址两大类。在上例中函数sumx()的设计和主函数对它的调用，就是传值调用。第一、第二次调用，带入的实参均是三个整型变量。调用函数返回后，在主程序中输出实参的值仍与调用之前相同。传值调用的主要特点是数据的单向传递，由实参通过形参将数据代入被调用函数，不论在调用期间形参值是否改变，调用结束返回主调函数之后，实参值都不会改变。在 C 语言中采用指针变量做形参来实现传址。传址调用的主要特点是可以实现数据双向传递，在调用时实参将地址传给形参，该地址中的数据代入被调用函数。如果在调用期间形参值被改变，也即该地址中的数据发生变化，调用结束返回主调函数之后，实参地址仍然不变，但是该地址中的数据发生相应改变。这就是数据的双向传递。现看一例题：例 1.3设计一个函数实现两个数据的交换，在主程序中调用。#include viod swap( int * a, int *b) ； /* 函数原型声明*/ void main( ) int x=100, y=800 ；printf( “ n %6d%6d” , x, y) ；/* 输出原始数据*/ swap(&x, &y) ；/* 调用交换数据的函数swap() */ printf( “ n %6d%6d” , x ,y) ；/* 输出交换后的数据*/ viod swap( int *a, int *b) int c ；c=*a ；*a = *b ；*b=c ； 运行结果：100800 800 100 实践证明x,y 的数据在调用函数前后发生了交换变化。形参是指向整形的指针变量a 和 b，在函数体内需要交换的是指针所指的存储单元的内容，因此使用 *a = *b ； 这样的写法。 在调用时，要求实参个数、类型位置与形参一致。因为实参应该是指针地址，所以调用语句swap(&x, &y)中，实参 &x, 和& y 代入的是整型变量x,y 的地址。 在函数体内交换的是实参地址中的内容，而作为主函数变量x,y 的地址仍然没有改变。从整数交换的角度看，本例题实现了双向数据传递。若从指针地址角度看，调用前后指针地址不变。现在来看 复数 ADT 实现的面向过程C 语言源程序 的创建复数的函数：void creat(complex *c) .； c-x=x1 ；c-y=y1 ； 在函数体中人们容易认识和习惯的写法c.x 和 c.y，也必须写成c-x 和 c-y 。在调用该函数时，还必须将结构体变量a 求地址做实参：creat(&a)。初学者应该特别注意这一点。如果需要在函数体中改变指针的地址，就需要在原指针基础之上再加一级指针：void funz( int *a) /* 改变 *a */ 函数调用返回后*a 仍然不变， 而*a 发生了变化。 由此可以看出C 语言的传址调用比较复杂。不如 PASCAL 的变量参数简便，也不如C+的引用调用方便。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 6 三、 结构体及运用数据结构课程所研究的问题均运用到“结构体”。在 C 语言中结构体的定义、输入/输出是数据结构程序设计的重要语法基础。定义结构体 的一般格式：struct 结构体类型名 类型名 1 变量名 1；/数据子域类型名 2 变量名 2；类型名 n 变量名 n；其中 struct 是保留字。 结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量， 声明创建一个结构体变量的方法是：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 等） ，也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数组。它们也可以称为结构体的数据成员。通过“结构体变量名.数据子域”可以访问数据子域。例 1.6设计 Student 结构体，在主程序中运用。#include #include typedef struct /* 定义结构体Student */ long num；/* 学号*/ int x；/* 成绩*/ char name10；/* 姓名*/ Student ；void main( ) Student s1；/* 声明创建一个结构体变量s1 */ s1.num=1001 ；/* 为 s1 的数据子域提供数据*/ s1. x=83；strcpy( s1.name, “李明” )；printf( “ n 姓名：%s” , s1.name)；/* 输出结构体变量s1 的内容*/ printf( “ n 学号：%d” , s1.num)；printf( “ n 成绩：%d” , s1.x)； 或者使用键盘输入: scanf(“ %d” , s1.num)；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 7 scanf(“ %d” , s1.x)；scanf(“ %s” , s1.name)； 还可以通过“结构体指针-数据子域”来访问数据域。在实际问题中还会使用到指向结构体的指针，通过以下语句段可以说明结构体指针的一般用法。 Student *p；/*声明指针变量p */ p=( Student * )malloc(sizeof( Student) ；/* 分配存储单元，首地址赋给p 指针*/ p-num=101 ；p-x=83；strcpy( p-name, “李明 ”)；printf( “ n %10s%6d%6d” ,p-name,p-num,p-x) ； 设计一个一维数组，每个数组元素是Student 结构体类型，通过以下语句段可以说明结构体数组的一般用法。可以通过“结构体数组名下标 .数据子域”访问数据域。 Student a5；/* 声明创建一个结构体数组a */ int i ；for( i=0, i5, i+) printf( “ n 学号： %d” ,ai.num) ；printf( “ n 姓名： %s” ,ai.name) ；printf( “ n 成绩： %d” ,ai.x) ； 以上是关于结构体的基本概念和简单运用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 8 二、实验的正确步骤数据结构课程具有较强的理论性，同时也具有较强的可应用性和实践性。上机实验是一个重要的教学环节。学生一般能够重视实验，对于编程上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。 需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路，正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体实验步骤如下：1. 问题分析与系统结构设计充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？）。然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。2. 详细设计和编码详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C+语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。3. 上机准备熟悉高级语言用法，如 C语言；熟悉常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。4. 上机调试程序调试最好分块进行，自底向上， 即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。5. 整理实习报告在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析。写出实验报告。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -