数据结构实验与习题精品资料.doc





《数据结构实验与习题精品资料.doc》由会员分享,可在线阅读,更多相关《数据结构实验与习题精品资料.doc(114页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构实验与习题 内 容 简 介数据结构是计算机专业的核心课,是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍,算法描述不拘泥某种语言的语法细节,默认读者已具备扎实的程序设计基础,可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致,相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难,希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度,存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题,一方面巩固基本知识、一方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“
2、数据结构实验与习题”。本参考书包括C语言基础知识、上机实验习题和书面作业练习题三部分。在C语言基础知识部分,主要介绍了输入/输出、函数及参数传递和结构体的概念应用。这部分内容非常重要,掌握的是否熟练会直接影响“数据结构“的学习。在实验部分,包括有完整的C语言源程序例题,介绍了一些设计数据结构题目所需的C语言常用的知识和技巧。在实验题中,既有简单容易的验证题,即验证已经给出的源程序,或者扩充已经给出的源程序,也有需独立思考设计的综合实验题。在习题部分,既有选择题、判断题,也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。由于时间仓足、水平有限,书
3、中难免存在错误和不妥之处,敬请读者指正。目 录第一部分 C语言基本知识一 基本输入和输出-1二 函数与参数传递-3三 结构体及运用 -5第二部分 上机实验习题上机实验要求及规范- 8实习一 复数ADT及其实现-10实习二 线性表-12实习三 栈和队列-20实习四 串-28实习五 数组-30实习六 树与二叉树-32实习七 图-34实习八 查找-40实习九 排序-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语言进行算法描述。按照传统的数据结构教材写法,只是注重算法思想和方法。并不关心具
5、体使用何种语言工具来实现,默认学生已经能够具备扎实的程序设计基础和能力。随着计算机科学的发展、教学改革的深化,数据结构的开课时间各个高校有所不同,普遍有所提前。大学生入学起点就存在一定的差异,即使在大学一年级学习了某种程序设计语言,学生中能力和水平的差异依然存在。实践表明在数据结构教学过程中,如果学生的程序设计语言基础薄弱,就会影响正常教学进度。数据结构不仅具有较强的理论性,更具有较强的实践性。当前国内、国外一些优秀的数据结构教材已经是兼顾理论和实践两个方面。因此,有必要将数据结构所必须使用的C语言语法在此做简单介绍。根据多年教学实践,学生完成上机实验练习时遇到的主要问题是,不能正确的输入数据
6、,结构体概念陌生,函数的传址调用概念不清,指针与链表有的没有学过。由于篇幅所限,这里仅对前三个问题加以介绍。如果学生基础好,可以越过这一部分内容不看。一、基本输入和输出对于重要的数据结构算法,均要求进行上机实验。而上机实践中离不开数据的输入/输出。看起来简单的输入/输出,往往是上机实验最容易出错的地方,尤其是输入。对于一个算法程序,如果数据不能正确输入,算法设计得再好也无法正常运行。1 输入C语言的输入是由系统提供的scanf()等函数实现, 在程序的首部一般要求写入: # include 因为标准输入/输出函数都存在于头文件 stdio.h 之中,现将其包含进来方可使用这些常用的输入/输出函
7、数。有的系统允许不使用上述包含语句,可以直接使用标准输入/输出函数。函数scanf()的功能很丰富,输入格式也是多种多样,这是大家较为熟悉的知识,这里不做详细介绍。在使用中需要注意以下几个问题。(1) 一条scanf()语句有多个变量、并且都是数值型(int, float, double)时,在输入数据时应该在一行之内键入多个数据,数据之间空格分隔。例如:int n; float x;scanf (“%d %f ” , &n, &x);正确的输入应是:整数 空格 实数 回车。例如:100 3.14 就是在两个数据之间使用空格键为分隔符,最后打回车键。如果语句中在%d 和%f 之间有一个逗号:s
8、canf (“%d ,%f ” , &n, &x);正确的输入应是:整数 逗号 实数 回车。例如:100,3.14 (2) 在需要字符型变量或字符串输入时,要单独写一条输入语句,这样不易出错。如果在同一条scanf()语句中将字符型和数值型混合输入常常会出错。因为键盘输入时在数值型数据之间空格键起分隔符作用,但是在字符或字符串之间,空格会被当做一个字符,而不能起到分隔符的作用。所以将它们混在一起容易出错。 (3)在scanf()语句中变量写法应该是该变量的地址,这一点常被忽视。请看下列程序:1: viod main()2: char name10, ch ;3: int num; float
9、x;4: printf(“n 请输入姓名:”); scanf(“%s”, name);5: printf(“n 请输入性别:”); scanf(“%c”, &ch);6: printf(“n 请输入学号和成绩:”); scanf(“ %d%f”, &n, &x); 为了方便说明问题程序中加了行号,运行时当然不允许行号。一般情况下在scanf()语句中的变量名之前要加上求地址符&,上述程序第5,6行之中就是这样。为什么第4行的name前面不加&呢?因为name代表字符串,即是一维字符数组,一维数组名本身就是一个地址,是该数组的首地址,所以name前面不加&。在本程序中把字符串、字符、数值型变量分
10、别写入不同的scanf()语句,输入数据的具体形式如下:请输入姓名:ZhangHua 请输入性别:v请输入学号和成绩:101 90.5请考虑如果姓名输入成:Zhang Hua,会出现什么现象?那样只会读入Zhang做姓名,而Hua被忽略,还会影响后面的输入语句无法正确读入数据。 因此,应该充分重视数据的输入技术。2 输出C语言的输出是由系统提供的printf()等函数来实现, 在程序的首部一般要求写入: # include 因为标准输入/输出函数都存在于头文件 stdio.h 之中,现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句,可以直接使用标准输入/输出函数。
11、输出函数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 302. 在输入语句scanf()之前先使用printf()输出提示信息,但是在printf()最后不能使用换行符。int x;printf(“n x=?”); /句尾不应使用换行符scanf( “%d”,&x); 这样使光标与提示信息
12、出现在同一行上,光标停在问号后边:X=? 。3. 在该换行的地方,要及时换行。int i;printf(“数据输出如下:n”); / 需要换行for (i=0; i8; i+) printf(“%6d”, i ); / 几个数据在同一行输出,不能换行 4. 在调试程序时多加几个输出语句,以便监视中间运行状况。程序调式成功后,再去掉这些辅助输出语句。二、函数与参数传递函数的设计和调用是程序设计必不可少的技能,是程序设计最重要的基础。一些初学者之之所以感到编程难,就是忽视了这个基础。在传统的面向过程的程序设计中,往往提倡模块化结构化程序设计,不论BASIC、 FONFTRAN、PASCAL还是其他
13、高级语言,最终要涉及到子函数的设计和使用。C语言的源程序是由一个主函数和若干(或零个)子函数构成,函数是组成C语言程序的基本单位。函数具有相对独立的功能,可以被其他函数调用,也可调用其他函数。当函数直接或间接的调用自身时,这样的函数称为递归函数。是否能够熟练的设计和使用函数,是体现一个人程序设计能力高低的基本条件。因此有必要回顾和复习C语言函数的基本概念。1函数的设计函数设计的一般格式是: 类型名 函数名(形参表) 函数体;函数设计一般是处理一些数据获得某个结果,因此函数可以具有返回值,上面的类型名就是函数返回值的类型,可以是int, float.等。例如:float funx(形参表) 函数
14、体;.函数也可无返回值,此时类型是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,
15、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-2. 关
16、于函数的参数传递 函数在被调用时,由主调程序提供实参,将信息传递给形参。在调用结束后,有时形参可以返回新的数据给主调程序。这就是所谓参数传递。各种算法语言实现参数传递的方法通常分为传值和传址两大类。 在上例中函数sumx()的设计和主函数对它的调用,就是传值调用。第一、第二次调用,带入的实参均是三个整型变量。调用函数返回后,在主程序中输出实参的值仍与调用之前相同。传值调用的主要特点是数据的单向传递,由实参通过形参将数据代入被调用函数,不论在调用期间形参值是否改变,调用结束返回主调函数之后,实参值都不会改变。 在不同的算法语言中,传址调用的语法有所不同。在PASCAL语言中用变参实现传址。在C语
17、言中采用指针变量做形参来实现传址。传址调用的主要特点是可以实现数据双向传递,在调用时实参将地址传给形参,该地址中的数据代入被调用函数。如果在调用期间形参值被改变,也即该地址中的数据发生变化,调用结束返回主调函数之后,实参地址仍然不变,但是该地址中的数据发生相应改变。这就是数据的双向传递。现看一例题:例1.3 设计一个函数实现两个数据的交换,在主程序中调用。#include viod swap( int *a, int *b) ; /* 函数原型声明 */void main( ) int x=100, y=800;printf(“n %6d%6d”, x, y); /* 输出原始数据 */ sw
18、ap(&x, &y); /* 调用交换数据的函数swap() */ printf(“n %6d%6d”, x ,y); /* 输出交换后的数据 */ viod swap( int *a, int *b) int c; c=*a; *a = *b; *b=c; 运行结果:100 800 800 100实践证明x,y 的数据在调用函数前后发生了交换变化。形参是指向整形的指针变量a和b,在函数体内需要交换的是指针所指的存储单元的内容,因此使用*a = *b;这样的写法。在调用时,要求实参个数、类型位置与形参一致。因为实参应该是指针地址,所以调用语句swap(&x, &y)中,实参&x,和& y代入的


- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构实验与习题 精品资料 数据结构 实验 习题 精品 资料

限制150内