数据结构实验指导书

数据结构

实验指导

计算机实验中心

2008-3-1

1

内 容 简 介

数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结构实验与习题”。

本参考书包括C语言基础知识、上机实验习题和书面作业练习题三部分。

在C语言基础知识部分，主要介绍了输入/输出、函数及参数传递和结构体的概念应用。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。

在实验部分，包括有完整的C语言源程序例题，介绍了一些设计数据结构题目所需的C语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。

在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。

由于时间仓足、水平有限，书中难免存在错误和不妥之处，敬请读者指正。

本学期实验任务

2

目 录

第一部分 C语言基本知识

一 基本输入和输出---------------------------------------------------------------------------1 二 函数与参数传递---------------------------------------------------------------------------3 三 结构体及运用 ----------------------------------------------------------------------------5

第二部分 上机实验习题

上机实验要求及规范------------------------------------------------------------------- 8

实习一 复数ADT及其实现-------------------------------------------10 实习二 线性表----------------------------------------------------12 实习三 栈和队列--------------------------------------------------20 实习四 串--------------------------------------------------------28 实习五 数组------------------------------------------------------30 实习六 树与二叉树------------------------------------------------32 实习七 图--------------------------------------------------------34 实习八 查找------------------------------------------------------40 实习九 排序------------------------------------------------------42

第三部分 书面作业练习题

习题一 绪论------------------------------------------------------------48 习题二 顺序表示（线性表、栈和队列）------------------------------------51 习题三 链表（线性表、栈和队列）----------------------------------------54 习题四 串--------------------------------------------------------------57 习题五 数组------------------------------------------------------------58 习题六 树与二叉树------------------------------------------------------60 习题七 图--------------------------------------------------------------69 习题八 查找------------------------------------------------------------75 习题九 排序------------------------------------------------------------78

3

第一部分 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 之间有一个逗号：

4

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

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

100，3.14

（2） 在需要字符型变量或字符串输入时，要单独写一条输入语句，这样不易出错。 如果在同一条scanf()语句中将字符型和数值型混合输入常常会出错。因为键盘输入时在数值型数据之间‘空格键’起‘分隔符’作用，但是在字符或字符串之间，‘空格’会被当做一个字符，而不能起到‘分隔符’的作用。所以将它们混在一起容易出错。 （3）在scanf()语句中变量写法应该是该变量的地址，这一点常被忽视。 请看下列程序： 1: 2: 3: 4:

viod main()

{ char name[10], ch ; int num; float x;

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);

5

printf(“\\n mmm”,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; i<8; i++) printf(“m”, i ); // 几个数据在同一行输出，不能换行

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

二、函数与参数传递

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

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

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

1函数的设计

函数设计的一般格式是：

类型名 函数名（形参表）

{ 函数体；}

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

float funx(形参表){ 函数体；.} 函数也可无返回值，此时类型是void。例如：

void funy(形参表){ 函数体；}

而函数体内所需处理的数据往往通过形参表传送，函数也可以不设形参表，此时写为：

类型名 函数名（void）{ 函数体；}

例1.2 设计一个函数计算三个整数之和，再设计一个函数仅输出一条线。设计主函数调用两个函数。

6

#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 mmm”,x,y,z); display(); x=5; y=6; z=7;

sa=sumx(x, y, z); /* 在赋值语句中调用函数sumx( ) */ printf(“\\n “ sum=%d”,sa); printf(“\\n mmm”,x,y,z); display();

} /* 程序结束 */

运行结果： ---------------------- sum= 6

2 2 2 ---------------------- sum=48

15 16 17

----------------------

2. 关于函数的参数传递

函数在被调用时，由主调程序提供实参，将信息传递给形参。在调用结束后，有时形参可以返回新的数据给主调程序。这就是所谓参数传递。各种算法语言实现参数传递的方法通常分为传值和传址两大类。

在上例中函数sumx()的设计和主函数对它的调用，就是传值调用。第一、第二次调用，带入的实参均是三个整型变量。调用函数返回后，在主程序中输出实参的值仍与调用之前相同。传值调用的主要特点是数据的单向传递，由实参通过形参将数据代入被调用函数，不论在调用期间形参值是否改变，调用结束返回主调函数之后，实参值都不会改变。 在不同的算法语言中，传址调用的语法有所不同。在PASCAL语言中用变参实现传址。

7

在C语言中采用指针变量做形参来实现传址。传址调用的主要特点是可以实现数据双向传递，在调用时实参将地址传给形参，该地址中的数据代入被调用函数。如果在调用期间形参值被改变，也即该地址中的数据发生变化，调用结束返回主调函数之后，实参地址仍然不变，但是该地址中的数据发生相应改变。这就是数据的双向传递。现看一例题： 例1.3 设计一个函数实现两个数据的交换，在主程序中调用。

#include

viod swap( int *a, int *b) ； /* 函数原型声明 */ void main( )

{ int x=100, y=800;

printf(“\\n mm”, x, y); /* 输出原始数据 */

swap(&x, &y); /* 调用交换数据的函数swap() */ printf(“\\n mm”, 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 结构体类型名

8

{ 类型名1 变量名1； //数据子域

类型名2 变量名2；……

类型名n 变量名n； }；

其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是： struct 结构体类型名 结构体变量名； 例如： struct ElemType /* 定义结构体 */

{ int num; char name[10]; } ;

struct ElemType x； /* 声明结构体变量x */

另外有一种方法使用typedef 语句定义结构体，在声明结构体变量时可以不写struct，使得书写更加简便。例如：

typedef struct

{ int num;

char name[10]; } ElemType；

ElemType就是一个新的类型名，并且是结构体类型名。声明变量x的语句是：

ElemType x;

一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型（int char 等），也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数组。它们也可以称为结构体的数据成员。

通过“结构体变量名.数据子域” 可以访问数据子域。 例1.6 设计Student结构体，在主程序中运用。

#include

#include

typedef struct /* 定义结构体Student */

{ long num; /* 学号 */ int x; /* 成绩 */ char name[10]; /* 姓名 */

} 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);

9

}

或者使用键盘输入: { 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 smm”,p->name,p->num,p->x);

}

设计一个一维数组，每个数组元素是Student结构体类型，通过以下语句段可以说明结构体数组的一般用法。可以通过“结构体数组名[下标].数据子域”访问数据域。

{ Student a[5]; /* 声明创建一个结构体数组a */

int i ;

for( i=0, i<5, i++){

printf(“\\n 学号：%d”,a[i].num) ;

printf(“\\n 姓名：%s”,a[i].name) ； printf(“\\n 成绩：%d”,a[i].x) ;

}

}

以上是关于结构体的基本概念和简单运用。

10

第二部分 上机实验习题

上机实验要求及规范

数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。在上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体实习步骤如下：

1.问题分析与系统结构设计

充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表、树还是图？），确定数据的存储结构（是顺序结构还是链表结构？）。然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。

2.详细设计和编码

详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。

编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。

3.上机准备

熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。

4.上机调试程序

调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。

5.整理实习报告

11

在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析。写出实验报告。 一、实验报告的基本要求：

一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。

（1） 姓名 班级 学号 日期 （2） 题目：内容叙述

（3） 程序清单（带有必要的注释）

（4） 调试报告：

实验者必须重视这一环节，否则等同于没有完成实验任务。这里可以体现个人特色、或创造性思维。具体内容包括：测试数据与运行记录；调试中遇到的主要问题，自己是如何解决的；经验和体会等。

二、实验报告的提高要求：

阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。

（1）需求和规格说明

描述问题，简述题目要解决的问题是什么。规定软件做什么。原题条件不足时补全。 （2）设计

a. 设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。 b. 设计表示：每个函数的头和规格说明；列出每个函数所调用和被调用的函数，也可以通过调用关系图表达。

c. 实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。 （3）用户手册：即使用说明。

（4）调试报告：调试过程中遇到的主要问题是如何解决的；设计的回顾、讨论和分析；

时间复杂度、空间复杂度分析；改进设想；经验和体会等。

12

实验一 复数ADT及其实现

一、实验目的

1. 了解抽象数据类型（ADT）的基本概念，及描述方法。

2. 通过对复数抽象数据类型ADT的实现，熟悉C语言语法及程序设计。为以后章节的学习打下基础。

二、实例

复数抽象数据类型ADT的描述及实现。 [复数ADT的描述]

ADT complex{

数据对象：D={ c1,c2 c1,c2∈FloatSet } 数据关系：R={ }

基本操作：创建一个复数 creat(a); 输出一个复数 outputc(a); 求两个复数相加之和 add(a,b); 求两个复数相减之差 sub(a,b); 求两个复数相乘之积 chengji(a,b); 等等;

} ADT complex; [复数ADT实现的源程序] #include #include

/* 存储表示，结构体类型的定义 */

typedef struct

{ float x; /* 实部子域 */ float y; /* 虚部的实系数子域 */ }complex; /* 全局变量的说明 */

comp a,b,a1,b1; int z;

/* 子函数的原型声明与实现 */ void creat(comp *c); void outputc(comp a); comp add(comp k,comp h);

/* 创建一个复数 */ void creat(complex *c)

13

{ float c1,c2;

printf(\输入实部real x=?\ printf(\输入虚部xvpu y=?\ (*c).x=c1; c ->y=c2; } /* creat */

/* 输出一个复数 */

void outputc(complex a)

{ printf(\ }

/* 求两个复数相加之和 */ complex add(complex k,complex h) { complex l;

l.x=k.x+h.x; l.y=k.y+h.y; return(l); } /* add */

/* 主函数 */ main()

{ colplex a,b,a1;

creat(&a); outputc(a); creat(&b); outputc(b); a1=add(a,b); outputc(a1); } /* maijn */

三、实习题

首先将上面源程序输入计算机，进行调试。运行程序，输入下列两个复数的实部域虚部，记录两个复数相加的输出结果。 原始数据：2.0 + 3.5i ，3.0 – 6.3i

然后在上面程序的基础上，增加自行设计的复数减、复数乘的两个子函数，适当补充必需的语句（例如函数原型声明、主函数中的调用等）。提示：

// 求两个复数相减之差的函数

complex sub(complex k,complex h) { ……} // 求两个复数相乘之积的函数

complex chengji(complex k,complex h){ …… }

再次调试运行程序。输入数据，记录结果，最后完成实验报告。

14

实习二 线性表

一、实验目的

1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。 2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。

二、实例

1. 线性表的顺序存储表示（结构）及实现。

阅读下列程序请注意几个问题：

（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体： typedef struct

{ ElemType a[MAXSIZE]; /* 一维数组 子域 */ int length; /* 表长度子域 */

}SqList; /* 顺序存储的结构体类型 */

（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。 [源程序]

#include #include

#define MAXSIZE 20 /* 数组最大界限 */ typedef int ElemType; /* 数据元素类型 */ typedef struct

{ ElemType a[MAXSIZE]; /* 一维数组 子域 */ int length; /* 表长度子域 */ }SqList; /* 顺序存储的结构体类型 */ SqList a,b,c; /* 函数声明 */

void creat_list(SqList *L);

15

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(\

printf(\建立线性表 \

printf(\在i位置插入元素e\ printf(\删除第i个元素，返回其值\ printf(\查找值为 e 的元素\ printf(\结束程序运行\

printf(\ printf(\请输入您的选择（1，2，3，4，6）\ scanf(\ switch(k)

{ case 1:{ creat_list(&a); out_list(a); } break;

case 2:{ printf(\ insert_sq(&a,i,e); out_list(a); } break; case 3:{ printf(\ x=delete_sq(&a,i); out_list(a);

printf(\

} break;

case 4:{ printf(\

loc=locat_sq(a,e);

if (loc==-1) printf(\未找到 %d\

else printf(\已找到，元素位置是 %d\

} break; } /* switch */

}while(k!=6);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */ /* 建立线性表 */

void creat_list(SqList *L) { int i;

16

printf(\

for(i=0;ilength;i++){ printf(\

scanf(\

} } /* creat_list */ /* 输出线性表 */

void out_list(SqList L) { int i; char ch;

printf(\

for(i=0;i<=L.length-1;i++) printf(\ printf(\打回车键，继续。“); ch=getch(); } /* out_list */

/* 在线性表的第i个位置插入元素e */ void insert_sq(SqList *L,int i,ElemType e)

{ int j;

if (L->length==MAXSIZE) printf(\

else if(i<1||i>L->length+1) printf(\

else { for(j=L->length-1; j>i-1; j--) L->a[j+1]=L->a[j]; /* 向后移动数据元素 */

L->a[i-1]=e; /* 插入元素 */ L->length++; /* 线性表长加1 */ }

} /* insert_sq */

/* 删除第i个元素，返回其值 */ ElemType delete_sq(SqList *L, int i)

{ ElemType x; int j;

if( L->length==0) printf(\是空表。underflow !\ else if(i<1||i> L->length){ printf(\ x=-1;} else { x=L->a[i-1];

for(j=i; j<=L->length-1; j++) L->a[j-1]=L->a[j]; L->length--; }

return(x);

} /* delete_sq */

/* 查找值为 e 的元素，返回它的位置 */ int locat_sq(SqList L, ElemType e) { int i=0;

while(i<=L.length-1 && L.a[i]!=e) i++;

17

if(i<=L.length-1) return(i+1); else return(-1); }/* locat_sq */

2. 线性表的链表存储表示（结构）及实现。 阅读下列程序请注意几个问题：

（1）关于线性表的链表存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中可以不相邻,既地址不连续。不同的教材的表示基本是一致的。 typedef struct LNode

{ ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */

}LNode; /* 结点结构类型 */

（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供关于链表操作的资料，供学生参考。可以看到本程序的main()与前一程序的main()函数的结构十分相似。稍加改动还可为其他题目的源程序所用。 [源程序]

#include #include #include

typedef int ElemType;

typedef struct LNode

{ ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ }LNode; /* 结点结构类型 */ LNode *L; /* 函数声明 */ LNode *creat_L();

void out_L(LNode *L);

void insert_L(LNode *L,int i ,ElemType e); ElemType delete_L(LNode *L,int i); int locat_L(LNode *L,ElemType e); /* 主函数 */ main()

{ int i,k,loc; ElemType e,x; char ch; do { printf(\

printf(\建立线性链表 \

printf(\在i位置插入元素e\

printf(\删除第i个元素，返回其值\ printf(\查找值为 e 的元素\ printf(\结束程序运行\

18

printf(\

printf(\请输入您的选择 (1,2,3,4,5)\ switch(k)

{ case 1:{ L=creat_L( ); out_L(L); } break;

case 2:{ printf(\ insert_L(L,i,e); out_L(L); } break; case 3:{ printf(\ x=delete_L(L,i); out_L(L); if(x!=-1) printf(\ } break;

case 4:{ printf(\

loc=locat_L(L,e);

if (loc==-1) printf(\未找到 %d\

else printf(\已找到，元素位置是 %d\ } break;

} /* switch */

printf(\

}while(k>=1 && k<5);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */

/* 建立线性链表 （ 11，22 ，33 ） */ LNode *creat( )

{ LNode *h,*p,*s; ElemType x;

h=(LNode *)malloc(sizeof(LNode)); /* 分配头结点 */ h->next=NULL; p=h;

printf(\输入第一个数据元素 */ while( x!=-111) /* 输入-111，结束循环 */ { s=(LNode *)malloc(sizeof(LNode)); /* 分配新结点 */ s->data=x; s->next=NULL;

p->next=s; p=s;

printf(\输入下一个数据*/ }

return(h);

} /* creat_L */

19

h ∧ h 11 22 建成后的链表h

33 ∧

/* 输出单链表中的数据元素*/ void out_L(LNode *L) { LNode *p; char ch;

p=L->next; printf(\

while(p!=NULL) { printf(\ };

printf(\打回车键，继续。“); ch=getch(); } /* out_link */

/* 在i位置插入元素e */

void insert_L(LNode *L,int i, ElemType e) { LNode *s,*p,*q; int j;

p=L; /* 找第i-1个结点 */

j=0;

while(p!=NULL && jnext; j++; } if(p==NULL || j>i-1) printf(\ else { s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; }

} /* insert_L */

/* 删除第i个元素，返回其值 */ ElemType delete_L(LNode *L,int i) { LNode *p,*q; int j; ElemType x; p=L; j=0;

while(p->next!=NULL && jnext; j++;}

if(p->next==NULL) {printf(\ else { q=p->next; x=q->data;

p->next=q->next; free(q); return(x); }

} /* delete_L */

/* 查找值为 e 的元素, 返回它的位置 */ int locat_L(LNode *L,ElemType e) { LNode *p; int j=1; p=L->next;

while(p!=NULL && p->data!=e) {p=p->next; j++;}

20

if(p!=NULL)return(j); else return(-1); } /* locat_L */

3.约瑟夫问题的一种描述：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数。

方法1．报m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。 方法2. 报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。 [方法1的程序清单] #include

#include

typedef struct node /* 结点的结构定义 */ { int num; /* 编号子域 */ int sm; /* 密码子域 */ struct node *next; /* 指针域 */ }JOS;

/* 函数声明 */ JOS *creat();

void outs(JOS *h, int m); /* 主函数 */ main()

{ int m; JOS *h; h=creat();

printf(“\\n enter the begin secret code, m=（m>1）”); scanf(“%d”,&m); outs(h, m); } /* main */

/* 生成约瑟夫环 */ JOS *creat()

h { int i=0, mi;

JOS *new, *pre, *h;

h=(JOS *)malloc(sizeof(JOS)); /* 为头结点申请空间 */ h->link=h; /* 头结点h形成环 */ pre=h;

printf(“\\n 个人密码 =?”); scanf(“%d”,&mi);

21

while( mi != -111) /* 密码为-111，结束循环 */ { new=(JOS *)malloc(sizeof(JOS)); /* 申请数据元素结点空间 */ i++; new->num=i; new->sm=mi; /* 结点送值 */

new->link=h; pre->link=new;

pre=new; /* 形成循环链表 */ printf(“\\n 个人密码 =?”); scanf(“%d”,&mi); /* 读入下一个密码 */

} /* while */

pre->link= h->link; free(h); /* 删除头结点h */ h=pre->link; return(h); /* 头指针指向第一个数据元素结点 */ } /* JOS *creat , 该约瑟夫环无附加头结点 */ /* 按m被叫出列的顺序，输出结点信息 */ void outs(JOS *h, int m) { int i; JOS *q=h, p;

printf(“\\n “); while (q->link!=q)

{ for(i=1;ilink;} /* 报数到第m个人 */

printf(“m m ”,q->num,q->sm); /* 输出第m个人的编号和密码 */ p->link=q->link; free(q); /* 第m个人出列 */ q=p->link;

}

printf(“m m \\n”,q->num,q->sm); /* 输出最后一个结点的编号值 */ free(q); } /* outs */

本程序用了不带头结点的循环链表，也可以加上头结点，对于本题有头结点会使操作麻烦，（同学们可以试一试，加进头结点如何实现？）并不是任何时候有头结点都能使程序操作简化，要根据实际情况，决定用是否使用头结点。

感兴趣的同学可以设计一个程序实现约瑟夫环的方法2。

在一般情况下默认使用头结点。不论是单向链表还是循环链表，头指针不能丢。

三、实习题(以下题目选做1题)

1. 用顺序存储表示（数组）实现约瑟夫环问题。

2. 一个线性表有n个元素（n

3. 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： （1）指定的值x由键盘输入；（2）程序能处理空链表的情况。 4.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。

22

要求：（1）通讯录是按姓名项的字母顺序排列的； （2）能查找通讯录中某人的信息；

[提示] 可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为‘工作结点’，需从链表的首结点开始比较，如果‘工作结点’的数据比链中的‘当前结点’的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。 5. 超长正整数的加法，设计一个程序实现两个任意长的整数求和运算

[提示] 可采用一个带有头结点的循环链表来表示一个非负的超大整数。从低位 开始每四位组成的数字，依次放在链表的第一个、第二个、……结点中，不足四位的最高位存放在链表的最后一个结点中，表头结点值规定位-1。

例如：大整数“567890987654321”可用如下的头结点的链表表示： head -1 4321 8765 8909 567

按照此数据结构，可以从两个表头结点开始，顺序依次对应相加，求出所需要的进位后，将其代入下一个结点进行运算。

23

实习三 栈和队列

一、实习目的

1. 掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

2. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 3. 了解和掌握递归程序设计的基本原理和方法。 二、实例

在各种教科书中关于栈和队列叙述十分清晰。但是，它们在计算机内的实现介绍不够详细。为了减轻学生上机实验的困难，在此给出几个例题供参考。 1. 栈的顺序存储结构及实现。 #include #include

#define MAXSIZE 20 /* 数组最大界限 */ typedef int ElemType; /* 数据元素类型 */ typedef struct

{ ElemType a[MAXSIZE]; /* 一维数组子域 */ int top; /* 栈顶指针子域 */ }SqStack; /* 栈的顺序结构体类型 */ SqStack s1; /* 函数声明 */

void init_s(SqStack *s); void out_s(SqStack s);

void push(SqStack *s,ElemType e); ElemType pop(SqStack *s); /* 主函数 */

main()

{ int k; ElemType e,x; char ch;

init_s( &s1); /* 初始化一个空栈 */ do { printf(\

printf(\数据元素e进栈 \

printf(\出栈一个元素，返回其值\； printf(\结束程序运行\

printf(\ printf(\请输入您的选择 (1,2,3)\

scanf(\ switch(k) { case 1:{ printf(\进栈 e=?\ push( &s1,e); out_s( s1 );

24

} break;

case 2:{ x= pop( &s1);

out_s( s1 ); } break;

printf(\出栈元素 : %d\

case 3: exit(0); } /* switch */

printf(\

}while(k>=1 && k<3);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */

/* 初始化空栈 * / void init_s(SqStack *s) { s->top=-1; } /* init_s */

/* 输出栈的内容 */

void out_s(SqStack s)

{ char ch; int i; /* 千万不能修改栈顶指针top */ if (s->top==-1) printf(“\\n Stack is NULL. “); else{ i=s->top;

while( i!=-1){ printf(“\\n data=%d”, s->a[i]); i--; } }

printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_c */ /* 进栈函数 */

void push(SqStack *s,ElemType e)

{ if(s->top==MAXSIZE-1)printf(“\\n Sstack is Overflow!”); else{ s->top++ ; s->a[s->top]=e; } }/* push */

/* 出栈函数 */

ElemType pop(SqStack *s)

{ ElemType x;

if(s->top==-1){ printf(“\\n Stack is Underflow!”); x=-1; }

else { x=s->a[s->top];

25

s->top--; } return(x); } /* pop */

2. 循环队列（即队列的顺序存储结构）实现。

#include #include

#define MAXSIZE 20 /* 数组最大界限 */ typedef int ElemType; /* 数据元素类型 */ typedef struct

{ ElemType a[MAXSIZE]; /* 一维数组子域 */ int front,rear; /* 头、尾指针子域 */ }SqQueue; /* 循环队列的结构体类型 */ SqQueue Q1;

/* 函数声明 */

void init_Q(SqQueue *Q); void out_Q(SqQueue Q);

void EnQueue(SqQueue *Q,ElemType e); ElemType DeQueue(SqQueue *Q); /* 主函数 */ main()

{ int k; ElemType e,x; char ch;

init_Q( &Q1); /* 初始化一个空循环队列 */ do { printf(\

printf(\数据元素e进队列 \ printf(\出队一个元素，返回其值\； printf(\结束程序运行\

printf(\ printf(\请输入您的选择 (1,2,3)\ scanf(\

switch(k) { case 1:{ printf(\进队 e=?\ EnQueue(SqQueue &Q1,e); out_Q(Q1);

} break;

case 2:{ x= DeQueue(&Q1);

printf(\出队元素 : %d\ out_Q(Q1 ); } break;

case 3: exit(0);

26

} /* switch */

printf(\

}while(k>=1 && k<3);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */

/* 初始化空队列 * / void init_Q(SqQueue *Q)

{ Q->front=0; Q->rear=0; } /* init_Q */

/* 输出队列的内容 */ void out_Q(SqQueue Q)

{ char ch; int i;

3 2 4 1 5 0 Q1.front Q1.rearr 空循环队列 /* 不能修改队列头、尾指针 */

if (Q->front==Q->rear) printf(“\\n Queue is NULL. “); else{ i=(Q->front+1)% MAXSIZE;

while( i!=Q->rear){ printf(“\\n data=%d”, Q->a[i]);

i=(i+1)%MAXSIZE; } printf(“\\n data=%d”, Q->a[i]); }

printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_Q */ / * 进队函数 */

void EnQueue(SqQueue *Q,ElemType e)

{ if((Q->rear+1)%MAXSIZE==Q->front) printf(“\\n Queue is Overflow!”); else{ Q->rear=(Q->rear+1)% MAXSIZE ; Q->a[Q->rear]=e; }

}/* EnQueue */

Q1.rear 3 4 5 0 12 2 1 11 进队两个数据后

Q1.front /* 出队函数 */

27

ElemType DeQueue(SqQueue *Q) { ElemType x;

if(Q->front==Q->rear)

{ printf(“\\n Queue is NULL!”); x=-1; }

else { Q->front=(Q->front+1)% MAXSIZE ;

x=Q->a[Q->front]; } return(x); } /* DeQueue */

3. 队列的链表储结构及实现。 #include #include #include

typedef int ElemType; typedef struct QNode

{ ElemType data; /* 数据子域 */ struct QNode *next; /* 指针子域 */ }QNode; /* 结点结构类型 */

typedef struct

{ Qnode *front, *rear; /* 头、尾指针子域 */ }L_Queue; /* “头尾”结点结构类型 */ L_Queue Q1;

/* 函数声明 */

void init_Q(L_Queue *Q); void out_Q(L_Queue Q);

void EnQueue(L_Queue Q,ElemType e); ElemType DeQueue(L_Queue Q); /* 主函数 */ main()

{ int k; ElemType e,x; char ch;

init_Q( &Q1); /* 初始化一个空循环队列 */ do { printf(\

printf(\数据元素e进队列 \ printf(\出队一个元素，返回其值\； printf(\结束程序运行\

printf(\

28

printf(\请输入您的选择 (1,2,3)\ scanf(\ switch(k)

{ case 1:{ printf(\进队 e=?\ EnQueue(SqQueue &Q1,e); out_Q(Q1); } break; case 2:{ x= DeQueue(&Q1);

printf(\出队元素 : %d\

out_Q(Q1 ); } break;

case 3: exit(0); } /* switch */

printf(\

}while(k>=1 && k<3);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */

/* 初始化一个空队列 */ void init_Q(L_Queue *Q)

{ QNode *p ;

p=(QNode *)malloc(sizeof(QNode)); p->next=NULL;

Q->fornt=p; Q->rear=p; } /* init_Q */

/* 输出队列的内容 */ void out_Q(L_Queue Q) { QNode *p; char ch; p=Q.front->next;

while(p!=NULL) { printf(“\\n %d”,p->data); p=p->next; }

printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_Q */

/ * 进队函数 */

void EnQueue(L_Queue Q,ElemType e) { QNode p,s;

s=(QNode *)malloc(sizeof(QNode)); s->data=e; s->next=NULL;

29

Q.front Q.rear

空链表队列

∧ Q.rear->next=s; Q.rear=s; } /* EnQueue */

/* 出队函数 */

ElemType DeQueue(L_Queue Q)

{ ElemType x; QNode *p;

if(Q.front==Q.rear) { printf(“\\n Queue is NULL!”); x=-1; }

else { p=Q.front->next; x=p->data;

Q.front->next=p->next; If(Q.rear= =p) Q.rear=Q.fornt; Free(p); } return(x); } /* DeQueue */

Q.front Q.rear

11 ∧ 有一个数据元素的链表队列

三、实习题(以下题目选做1题)

1. 写一个程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M 向N 进制（2或8或16）的转换。 （1）采用顺序存储结构实现栈。

（2）采用链表结构实现栈。

2. 阿克曼函数（Ackermann’s function）定义如下：

akm(m,n)=

n+1 当 m=0 时 akm(m-1,1) 当 m>0,n=0 时 akm(m-1,akm(m,n-1)) 当 m>0,n>0 时

人们之所以研究该函数，是因为m和n值的较小增长都会引起函数值的极快增长。 （1）设计运用递归算法的源程序，上机运行。

（2）写一个非递归算法的源程序，上机运行。并进行比较。

30

3．二项式(a+b)n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。

1

1 1 1 2 1 1 331

3 1

实习四 串

一、实习目的

1. 熟悉串类型的实现方法，了解简单文字处理的设计方法。

2. 熟悉C语言的字符和把字符串处理的原理和方法。下面简单介绍C相关知识： (1) 字符：

char ch; ch是单个字符变量 ch=?a?; ?a? 是字符常量 (2）字符串：

Char s1[10],*s2,s3[2][10];

S1 是一维字符数组，也称它是字符串变量；

S2 是指向字符的指针变量，可以给它分配一批单元存放字符，也称为串； S2=(char )malloc(sizeof(char)*10);

S3 是2行10列的二维字符数组，一般看做含有2个字符串的数组s3[0],s3[1]，每个串最多容10个字符；

下列赋值语句是错误的：

S1= “abcdefghi” ；

应该使用串拷贝函数：

strcpy(S1, “abcdefghi”); strcoy( S2, ”abcdefghi”);

strcpy(S3[0], ”123456789”); strcpy(S3[1], ”jklmnopqr”) ;

用双引号括起来的是字符串常量，在处理字符串常量时，注意总是有一个字符‘\\0’作为字符串常量的结尾 。”123456789”存入S3[0]要占用10个位置，而不是9个。S3[0][0]里是1，……，s3[0][8]里是9,s3[0][9]里是?\\0?（串尾标志）。 (3)常见的字符函数：

int strlen(streing)

string 可以是串变量或常量， 函数结果是串长度（不含‘\\0’）。

strcpy( str ,str2 ); str是串变量，str2可以是串变量或常量。函数的作用是将str2的串拷贝给串变量str。 int strcmp( str1 ,str2 );

str1，str2可以是串变量或常量，函数的作用是将两个串进行比较， 当 str1==str2，函数结果=0； 当 str1>str2， 函数结果>0； 当 str1

char *strcat( str1,str2);

str1，str2可以是串变量或常量，函数的作用是将两个串进行连接，函数结果是连接后的新串。

二、实例

32

实现字符串置换操作。 #include #include

/* 函数声明 */

int index(char *s, char *t,int pos); void replace(char *s,char *t,char *v); /* 主函数 */ main()

{ int k; char *s,t[]=\ s=(char *)malloc(100*sizeof(char));

printf(\ printf(\

replace(s,t,v); /* 调用串置换函数 */ printf(\

} /* main */

/* 串的置换，将主串s中的t串，置换为v串 */ void replace(char *s,char *t,char *v) { int i,j,k,po,sl,tl;

sl=strlen(s); tl=strlen(t); printf(\ po=0;

while( po< sl-tl+1)

{ k=index(s,t,po); /* 调用串匹配函数 */ printf(\ i=k-1;

for(j=0;j<=tl-1;j++) { s[i]=v[j];i++;} po=k+tl;

printf(\ }

} /* replace */

/* 串匹配函数 */

/* 从主串s的第pos个字符开始查找子串t，函数结果是子串t在主串s的pos开始之后首次出现的位置 */

int index(char *s, char *t, int pos) {int i,j,sl,tl;

i=pos; j=1; sl=strlen(s); tl=strlen(t); while(i<=sl && j<=tl)

if(s[i-1]==t[j-1]) {i++; j++; } else { i=i-j+1+1; j=1;}

33

if(j>tl) return(i-tl); else return(-1); } /* index */

三、实习题

1. 将上述实例打入计算机，调试运行。

字符串常量的提供有多种手段。可以在定义串类型同时初始化串值：

char t[]=\

还可以使用语句gets(s)进行输入；也可以用scanf(\进行输入。请你试着用不同的方法修改、调试、运行程序。

2. 设计可以在主串s中第i个位置插入一个子串t的程序。

3. 设计可以在主串s中从第i个位置开始共取m个字符，求子串的程序。

34

实习五 数 组

一、实习目的

熟悉稀疏矩阵的“三元组表”和“十字链表”存储结构，运用它们进行矩阵简单运算处理。

二、实例

稀疏矩阵的十字链表存储与输出。

#include #include #include

typedef int Etype;

typedef struct OLnode

{int i,j; /* 行号、列号域 */ Etype e; /* 数据域 */ struct OLnode *right,*down; /* 行向的、列向的指针域 */ } OLnode; /* 数据元素结点类型 */ typedef struct

{ OLnode *rh[5],*ch[5];

int mu,nu,tu;

}Crosslist; /* 十字链表行、列表头 */ /* 函数声明 */

void creatMatrix(Crosslist *M); void out_M(Crosslist M); Crosslist ma; int z; /* 主函数 */ main()

{ creatMatrix(&ma); out_M(ma); } /* main */

/* 十字链表的输出 */ void out_M(Crosslist M)

{ int i; OLnode *p; char ch；

/* 输出矩阵的总行数、总列数、非零元素总个数 */

printf(\ for(i=1; i<=M.mu; i++)

{ p=M.rh[i]; /* 指向第i行 */ if(p){ printf(\ while(p){ printf(\ p=p->right;

35

} }

printf(\

}

printf(“\\n 打回车键，返回。“); ch=getch(); }

void creatMatrix(Crosslist *M) { int m,n,t,row,col,i,j;

Etype va; OLnode *p,*q,*s;

/* 输入矩阵的总行数、总列数、非零元素总个数 */ printf(\ for(i=1; i<=m;i++) M->rh[i]=NULL; for(j=1; j<=n;j++) M->ch[j]=NULL;

M->mu=m; M->nu=n; M->tu=t; /* 建立成空十字链表 */ /* 以下为非零元素的逐一输入和插入 */ for(i=1;i<=M->tu;i++)

{ printf(\ p=(OLnode *)malloc(sizeof(OLnode)); p->i=row; p->j=col; p->e=va; /* 在第row行上链接 */ q=M->rh[row]; s=q;

while(q!=NULL && q->j < col){ s=q; q=q->right;} p->right=q;

if(q==M->rh[row])M->rh[row]=p; else s->right=p; /* 在第col列上链接 */ q=M->ch[col];

while(q && q->i < row){s=q;q=q->down;} p->down=q;

if(q==M->ch[col]) M->ch[col]=p; else s->down=p; } /* for */

}/* creatMatrix */

三、实习题

1. 编写用“三元组表”存储（参见教科书）稀疏矩阵，进行矩阵处理的程序。（1）

矩阵转置 （2）矩阵加

2. 上机调试上面给出的十字链表的程序，在此基础上增加查找功能：

（1） 给定一个数值 X ，查找确定它的位置（行下标i、列下标j）；

36

（2） 给定一个矩阵元素aij位置(i,j)，求出它的数据值是什么？ 3. 实现迷宫求解程序。

37

实习六 树与二叉树

一、实习目的

1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序递归遍历。

2. 用树解决实际问题，如哈夫曼编码等。

加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。 二、实例

1. 二叉树的建立和遍历。

为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。有一种方法利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：序号 数据元素。结合下图的二叉树数的输入据顺序应该是：1 1，2 2，3 3，4 4，6 5，7 6，11 7，12 8，13 9。 另一种算法是教材P58～P59介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织时先序的顺序，但是另有特点，当某结点的某孩子为空时以数据0来充当，也要输入。结合下图的二叉树数的输入据顺序应该是：

1 2 4 0 0 0 3 5 0 7 0 0 6 8 0 0 9 0 0。

若当前数据不为0，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。

下列程序中的统计二叉树结点的函数，是对二叉树遍历方法的应用，请认真理解然后模仿练习。

/* 二叉树的建立与遍历 */ # include # include

typedef int Etype;

typedef struct BiTNode /* 树结点结构 */ { Etype data;

struct BiTNode *lch,*rch; }BiTNode; /* 函数原形声明 */ BiTNode *creat_bt1(); BiTNode *creat_bt2() void inorder(BiTNode *p); void numb(BiTNode *p);

BiTNode *t; int n,n0,n1,n2,; /* 主函数 */ main()

38

1 2 4 5 7 8 3 6 9 { char ch; int k;

do { printf(\

printf(\建立二叉树方法1 \ printf(\建立二叉树方法2\ printf(\中序递归遍历二叉树\

printf(\计算树中结点个数\ printf(\结束程序运行\

printf(\

printf(\请输入您的选择 (1,2,3,4,5,6)\ switch(k)

{ case 1:t=creat_bt1( );break; /* 调用性质5建立二叉树算法 */ case 2:t=creat_bt2( );break; /* 调用递归建立二叉树算法 */ case 3: { inorder(t); /* 调用中序遍历 */

printf(\打回车键，继续。“); ch=getch(); } break; case 4:{ n=0;n0=0 ; n1=0; n2=0; /* 全局变量置0 */ numb(t);

printf(“\\n 二叉树结点总数 n=%d”,n);

printf(“\\n 二叉树叶子结点数 n0=%d”,n0); printf(“\\n 度为1的结点数 n1=%d”,n1); printf(“\\n 度为2的结点数 n2=%d”,n2);

printf(\打回车键，继续。“); ch=getch(); } break; case 5: exit(0);

} /* switch */

printf(\ }while(k>=1 && k<5);

printf(\再见！\

printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */

/* 利用二叉树性质5 ，借助一维数组V 建立二叉树 */ BiTNode *creat_bt1()

{ BiTNode *t,*p,*v[20]; int i; Etype e; /* 输入结点的序号i 、结点的数据e */

printf(\

while(i!=0 && e!=0) /* 当 i ,e都为0时，结束循环 */ { p=(BiTNode *)malloc(sizeof(BiTNode)); p->data=e; p->lch=NULL; p->rch=NULL; v[i]=p;

39

if (i==1) t=p; /* 序号为1的结点是根 */ else{ j=i/2;

if(i%2==0) v[j]->lch=p; /* 序号为偶数，做左孩子*/ else v[j]->rch=p; /* 序号为奇数，做右孩子*/ }

printf(\ }

return(t);

} /* creat_bt1 */

/* 模仿先序递归遍历方法，建立二叉树 */ BiTNode *creat_bt2() { BiTNode *t;

printf(\

if(e==0) t=NULL; /* 对于0值，不分配新结点 */ else { t=(BiTNode *)malloc(sizeof(BiTNode)); t->data=e; t->lch=creat_bt2(); /* 左孩子获得新指针值 */

t->rch=creat_bt2(); /* 右孩子获得新指针值 */ }

return(t);

} /* creat_bt2 */

/* 中序递归遍历二叉树 */ void inorder(BiTNode *p)

{ if (p) { inorder(p->lch); printf(\

inorder(p->rch); }

} /* inorder */

/* 利用中序递归遍历二叉树的方法，计算树中结点个数 */

/* 读者可以试着运用先序或后序递归遍历二叉树方法重新编写这一段函数 */ void inorder(BiTNode *p)

{ if (p) { inorder(p->lch);

{ printf(\ n++; if(p->lch==NULL && p->lch==NULL) n0++; if((p->lch==NULL && p->lch!=NULL)|| (p->lch!=NULL && p->lch==NULL) n1++; if(p->lch!=NULL && p->lch!=NULL) n2++; } /* 把访问的功能扩大了 */

40

本文来源：https://www.bwwdw.com/article/35d3.html