数据结构实验与习题.doc

数据结构实验与习题 内 容 简 介数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结构实验与习题”。本参考书包括C语言基础知识、上机实验习题和书面作业练习题三部分。在C语言基础知识部分，主要介绍了输入/输出、函数及参数传递和结构体的概念应用。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。在实验部分，包括有完整的C语言源程序例题，介绍了一些设计数据结构题目所需的C语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。由于时间仓足、水平有限，书中难免存在错误和不妥之处，敬请读者指正。目 录第一部分 C语言基本知识一 基本输入和输出-1二 函数与参数传递-3三 结构体及运用 -5第二部分 上机实验习题上机实验要求及规范- 8实习一 复数ADT及其实现-10实习二 线性表-12实习三 栈和队列-20实习四 串-28实习五 数组-30实习六 树与二叉树-32实习七 图-34实习八 查找-40实习九 排序-42第三部分 书面作业练习题习题一 绪论-48习题二 顺序表示（线性表、栈和队列）-51习题三 链表（线性表、栈和队列）-54习题四 串-57习题五 数组-58习题六 树与二叉树-60习题七 图-69习题八 查找-75习题九 排序-78第一部分 C语言基本知识如何选择描述数据结构和算法的语言是十分重要的问题。传统的方法是用PASCAL语言，由于该语言语法规范、严谨，非常适用于数据结构课程教学。在Windows 环境下涌现出一系列的功能强大、面向对象的程序开发工具，如：Visual C+, Borland C+, Visual Basic, Visual Foxpro等。由于Visual Delphi的出现，使PASCAL仍不失为一种优秀的算法描述工具。 近年来在计算机科学研究、系统开发、教学以及应用开发中，语言的使用越来越广泛。因此，本教材采用类C语言进行算法描述。按照传统的数据结构教材写法，只是注重算法思想和方法。并不关心具体使用何种语言工具来实现，默认学生已经能够具备扎实的程序设计基础和能力。随着计算机科学的发展、教学改革的深化，数据结构的开课时间各个高校有所不同，普遍有所提前。大学生入学起点就存在一定的差异，即使在大学一年级学习了某种程序设计语言，学生中能力和水平的差异依然存在。实践表明在数据结构教学过程中，如果学生的程序设计语言基础薄弱，就会影响正常教学进度。数据结构不仅具有较强的理论性，更具有较强的实践性。当前国内、国外一些优秀的数据结构教材已经是兼顾理论和实践两个方面。因此，有必要将数据结构所必须使用的C语言语法在此做简单介绍。根据多年教学实践，学生完成上机实验练习时遇到的主要问题是，不能正确的输入数据，结构体概念陌生，函数的传址调用概念不清，指针与链表有的没有学过。由于篇幅所限，这里仅对前三个问题加以介绍。如果学生基础好，可以越过这一部分内容不看。一、基本输入和输出对于重要的数据结构算法，均要求进行上机实验。而上机实践中离不开数据的输入/输出。看起来简单的输入/输出，往往是上机实验最容易出错的地方，尤其是输入。对于一个算法程序，如果数据不能正确输入，算法设计得再好也无法正常运行。1 输入C语言的输入是由系统提供的scanf()等函数实现， 在程序的首部一般要求写入： # include 因为标准输入/输出函数都存在于头文件 stdio.h 之中，现将其包含进来方可使用这些常用的输入/输出函数。有的系统允许不使用上述包含语句，可以直接使用标准输入/输出函数。函数scanf()的功能很丰富，输入格式也是多种多样，这是大家较为熟悉的知识，这里不做详细介绍。在使用中需要注意以下几个问题。（1） 一条scanf()语句有多个变量、并且都是数值型（int, float, double）时，在输入数据时应该在一行之内键入多个数据，数据之间空格分隔。例如：int n; float x;scanf (“%d %f ” , &n, &x);正确的输入应是：整数 空格 实数 回车。例如：100 3.14 就是在两个数据之间使用空格键为分隔符，最后打回车键。如果语句中在%d 和%f 之间有一个逗号：scanf (“%d ，%f ” , &n, &x);正确的输入应是：整数 逗号 实数 回车。例如：100，3.14 （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); 为了方便说明问题程序中加了行号，运行时当然不允许行号。一般情况下在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 302. 在输入语句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. 在调试程序时多加几个输出语句，以便监视中间运行状况。程序调式成功后，再去掉这些辅助输出语句。二、函数与参数传递函数的设计和调用是程序设计必不可少的技能，是程序设计最重要的基础。一些初学者之之所以感到编程难，就是忽视了这个基础。在传统的面向过程的程序设计中，往往提倡模块化结构化程序设计，不论BASIC、 FONFTRAN、PASCAL还是其他高级语言，最终要涉及到子函数的设计和使用。C语言的源程序是由一个主函数和若干（或零个）子函数构成，函数是组成C语言程序的基本单位。函数具有相对独立的功能，可以被其他函数调用，也可调用其他函数。当函数直接或间接的调用自身时，这样的函数称为递归函数。是否能够熟练的设计和使用函数，是体现一个人程序设计能力高低的基本条件。因此有必要回顾和复习C语言函数的基本概念。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-2. 关于函数的参数传递 函数在被调用时，由主调程序提供实参，将信息传递给形参。在调用结束后，有时形参可以返回新的数据给主调程序。这就是所谓参数传递。各种算法语言实现参数传递的方法通常分为传值和传址两大类。 在上例中函数sumx()的设计和主函数对它的调用，就是传值调用。第一、第二次调用，带入的实参均是三个整型变量。调用函数返回后，在主程序中输出实参的值仍与调用之前相同。传值调用的主要特点是数据的单向传递，由实参通过形参将数据代入被调用函数，不论在调用期间形参值是否改变，调用结束返回主调函数之后，实参值都不会改变。 在不同的算法语言中，传址调用的语法有所不同。在PASCAL语言中用变参实现传址。在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; 运行结果：100 800 800 100实践证明x,y 的数据在调用函数前后发生了交换变化。形参是指向整形的指针变量a和b，在函数体内需要交换的是指针所指的存储单元的内容，因此使用*a = *b;这样的写法。在调用时，要求实参个数、类型位置与形参一致。因为实参应该是指针地址，所以调用语句swap(&x, &y)中，实参&x,和& y代入的是整型变量x,y的地址。在函数体内交换的是实参地址中的内容，而作为主函数变量x,y的地址仍然没有改变。从整数交换的角度看，本例题实现了双向数据传递。若从指针地址角度看，调用前后指针地址不变。现在回过头来看P5页复数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+的引用调用方便。三、 结构体及运用数据结构课程所研究的问题均运用到“结构体”。在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);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) ; 以上是关于结构体的基本概念和简单运用。第二部分 上机实验习题上机实验要求及规范数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。在上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体实习步骤如下：1.问题分析与系统结构设计充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？）。然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。2.详细设计和编码详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C+语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。3.上机准备熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。4.上机调试程序调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。5.整理实习报告 在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析。写出实验报告。一、实验报告的基本要求： 一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。（1） 姓名 班级 学号 日期（2） 题目：内容叙述（3） 程序清单（带有必要的注释）（4） 调试报告：实验者必须重视这一环节，否则等同于没有完成实验任务。这里可以体现个人特色、或创造性思维。具体内容包括：测试数据与运行记录；调试中遇到的主要问题，自己是如何解决的；经验和体会等。二、实验习报告的提高要求：阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。（1） 需求和规格说明描述问题，简述题目要解决的问题是什么。规定软件做什么。原题条件不足时补全。（2） 设计a. 设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。b. 设计表示：每个函数的头和规格说明；列出每个函数所调用和被调用的函数，也可以通过调用关系图表达。c. 实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。（3） 用户手册：即使用说明。（4） 调试报告：调试过程中遇到的主要问题是如何解决的；设计的回顾、讨论和分析；时间复杂度、空间复杂度分析；改进设想；经验和体会等。实习一 复数ADT及其实现一、实验目的1. 了解抽象数据类型（ADT）的基本概念，及描述方法。 2. 通过对复数抽象数据类型ADT的实现，熟悉C语言语法及程序设计。为以后章节的学习打下基础。二、实例 复数抽象数据类型ADT的描述及实现。 复数ADT的描述 ADT complex 数据对象：D= c1,c2 c1,c2FloatSet 数据关系：R= c1 c2 基本操作：创建一个复数 creat(a); 输出一个复数 outputc(a); 求两个复数相加之和 add(a,b); 求两个复数相减之差 sub(a,b); 求两个复数相乘之积 chengji(a,b); 等等; ADT complex; 复数ADT实现的源程序#include #include /* 存储表示，结构体类型的定义 */typedef struct float x; /* 实部子域 */ float y; /* 虚部的实系数子域 */ comp;/* 全局变量的说明 */comp a,b,a1,b1;int z;/* 子函数的原型声明 */void creat(comp *c);void outputc(comp a);comp add(comp k,comp h);/* 主函数 */main() creat(&a); outputc(a); creat(&b); outputc(b); a1=add(a,b); outputc(a1); /* maijn */* 创建一个复数 */void creat(comp *c) float c1,c2; printf(输入实部real x=?);scanf(%f,&c1); printf(输入虚部xvpu y=?);scanf(%f,&c2); (*c).x=c1; c -y=c2; /* creat */* 输出一个复数 */void outputc(comp a) printf(n %f+%f i nn,a.x,a.y); /* 求两个复数相加之和 */comp add(comp k,comp h) comp l; l.x=k.x+h.x; l.y=k.y+h.y; return(l); /* add */三、实习题首先将上面源程序输入计算机，进行调试。运行程序，输入下列两个复数的实部域虚部，记录两个复数相加的输出结果。 原始数据：2.0 + 3.5i ，3.0 6.3i 然后在上面程序的基础上，增加自行设计的复数减、复数乘的两个子函数，适当补充必需的语句（例如函数原型声明、主函数中的调用等）。提示：/ 求两个复数相减之差的函数 comp sub(comp k,comp h) / 求两个复数相乘之积的函数 comp chengji(comp k,comp h) 再次调试运行程序。输入数据，记录结果，最后完成实验报告。实习二 线性表一、实验目的1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。 2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。二、实例 1. 线性表的顺序存储表示（结构）及实现。阅读下列程序请注意几个问题：（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含动态分配一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含静态一维数组和线性表长的结构体： typedef struct ElemType aMAXSIZE; /* 一维数组 子域 */ int length; /* 表长度子域 */ SqList; /* 顺序存储的结构体类型 */ （2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。 源程序#include #include #define MAXSIZE 20 /* 数组最大界限 */typedef int ElemType; /* 数据元素类型 */typedef struct ElemType aMAXSIZE; /* 一维数组 子域 */ int length; /* 表长度子域 */ SqList; /* 顺序存储的结构体类型 */SqList a,b,c;/* 函数声明 */void creat_list(SqList *L);void out_list(SqList L);void insert_sq(SqList *L,int i,ElemType e);ElemType delete_sq(SqList *L,int i);int locat_sq(SqList L,ElemType e);/* 主函数 */main() int i,k,loc; ElemType e,x; char ch; do printf(nnn); printf(n 1. 建立线性表 ); printf(n 2. 在i位置插入元素e); printf(n 3. 删除第i个元素，返回其值); printf(n 4. 查找值为 e 的元素); printf(n 6. 结束程序运行); printf(n=); printf(n 请输入您的选择（1，2，3，4，6）); scanf(%d,&k); switch(k) case 1: