《数据结构(C语言版)》
上机指导
目录
第1章 绪论 1
实验1-1 起泡排序 1
实验1-2 三元组 4
实验1-3复数 7
实验1-4 时间复杂度 11
第2章 线性表 13
实验 2-1 顺序表 13
实验 2-2 单链表 30
实验 2-3 静态链表 46
实验 2-4 有序链表 46
第3章 栈和队列 47
实验 3-1 链栈 47
实验 3-2 顺序栈 51
实验 3-3 链队列 60
实验 3-4 循环队列 60
第6章 树和二叉树 69
实验 6-1 二叉树的顺序存储 69
实验 6-2 二叉链表 69
实验 6-3 遍历二叉树及其应用 69
实验 6-4 线索二叉树及其应用 75
实验 6-5树和森林及其应用 75
实验 6-6 赫夫曼树及其应用 75
第7章 图 80
实验 7-1 图的遍历 80
实验 7-2最短路径 85
实验 7-3关键路径 89
第9章 查 90
实验 9-1 顺序查和折半查 90
实验 9-2 二叉排序树 95
实验 9-3 哈希表 95
第10章 内部排序 96
实验 10-1 插入排序 96
实验 10-2 快速排序 96
实验 10-3 选择排序 101
实验 10-4 堆排序 101
实验 10-5 归并排序 102
第1章 绪论
实验1-1 起泡排序
[题目] 把起泡排序的算法（课本P16）改写成C语言程序，并编写程序进行调试。
[目的] 把类C语言书写的算法改写成C语言程序，并进行调试。
[步骤]
1. 起泡排序算法（类C语言）
（略）参考课本P16。
2. 改写成C语言程序
（略）。
3. 测试程序
1）准备测试数据，存放在数组中；
2）打印排序前的数据
3）进行起泡排序
4）打印排序后的数据
4. 测试数据和结果
包括：准备好的测试数据，期望结果，实际运行结果（运行程序后填写，并与期望结果对照）。
5. 总结
考虑：1）怎样将类C语言算法改写成C语言程序？如：怎样处理局部变量，怎样处理符号常量等。2）怎样书写程序才能提高代码的可读性？如：文件的格式，函数声明的位置，主函数的位置，函数具体实现的位置，采用缩进格式等。3）还遇到那些问题？如：应当熟悉开发环境，应当熟练使用各种调试工具等。
[源程序]
/****************************************************
@Title: 数据结构实验
@Name: <；实验1-1> 起泡排序
@Object:
[实验目的]
把起泡排序的算法改写成C语言程序，并编写程序
进行调试。掌握如何把类C语言书写的算法改写成
C语言程序。
[实验提示]
1）怎样将类C语言算法改写成C语言程序？
如：怎样处理局部变量，怎样处理符号常量等。
2）怎样书写程序才能提高代码的可读性？
如：文件的格式，函数声明的位置，主函数的位置，
函数具体实现的位置，采用缩进格式等。
@Usage:
请查看"TO-DO列表"，根据要求完成代码
@Copy
right: BTC 2004
@Author: Zhuang Bo
@Date: 2004
@Description:
*****************************************************/
///////////////////////////////////////////////////////////
// 包含头文件
#include <stdio.h>
c编程步骤///////////////////////////////////////////////////////////
// 对主函数中调用的函数进行声明
// 对数组-1]进行起泡排序，使数据从小到大有序
/
/-------------------------------------
// TODO (#1#): 这里插入函数bubble_sort()的声明
//-------------------------------------
// 顺序打印数组a中的元素 
void print_out(int a[],int n);
///////////////////////////////////////////////////////////
// 起泡排序 主程序
int main()
{
// 测试数据
int a[]={82,47,29,74,91,53,82,62,98,51};
printf("起泡排序\n");
// 打印排序前的数据
printf("排序前:\n");
print_out(a,10);
// 进行起泡排序
//-------------------------------------
// TODO (#1#): 这里调用bubble_sort()对数组a排序
//-------------------------------------
// 打印排序后的数据
printf("排序后:\n");
print_out(a,10);
}
///////////////////////////////////////////////////////////
// 函数的实现定义在下面
#define  TRUE  1
#define  FALSE  0
// 对数组-1]进行起泡排序，使数据从小到大有序
void bubble_sort(int a[],int n)
{
//-------------------------------------
// TODO (#1#): 这里定义函数中用到的变量
//-------------------------------------
for( i=n-1,change=TRUE; i>=1 && change; --i ) {
change = FALSE;
for( j=0; j<i; ++j)
if( a[j] > a[j+1] ) {
//-------------------------------------
// TODO (#1#): 这里交换 a[j] 和 a[j+1]
//-------------------------------------
change = TRUE;
}
}
} // bubble_sort
/
/ 顺序打印数组a中的元素
void print_out(int a[],int n)
{
int i;
for(i=0; i<n; i++)
printf(" %d",a[i]);
printf("\n");
}
实验1-2 三元组
[题目] 用C语言实现三元组ADT，并编写测试程序。
[目的] 把三元组ADT（课本P9,11-13）用C语言实现；学习使用模块结构；学习编写调试程序。
[步骤]
1. 三元组类型的ADT定义。
（略）。
2. 三元组类型的实现。
1）类型描述（略）。
2）基本操作的声明（略）。
3）基本操作的实现（略）。
3. 模块设计
主程序：测试三元组模块的程序。
三元组模块：实现三元组类型的程序。
类C通用模块：包含类C中的预定义常量和类型。
模块的组织：
主程序 CXX0102.CPP
#include <stdio.h>
#include "triplet.h"
void ShowMainMenu();
int GetChoice();
void main()
{
...
}
void ShowMainMenu()
{
...
}
int GetChoice()
{
...
}
三元组模块 TRIPLET.H
// 防止重复包含
#ifndef _TRIPLET_H_
#define _TRIPLET_H_
#include "ds.h"
ty
pedef int ElemSet; // 用户自定义类型
// 三元组类型描述
typedef ElemSet Triplet[3];
// 基本操作的实现
Status InitTriplet( Triplet& T, ElemSet v1, ElemSet v2, ElemSet v3);
...
Status InitTriplet( Triplet& T, ElemSet v1, ElemSet v2, ElemSet v3)
{
...
}
...
#endif // _TRIPLET_H_
类C通用模块
#ifndef _DS_H_
#define _DS_H_
// 函数结果状态代码
const int TRUE      = 1;
const int FALSE    = 0;
const int OK        = 1;
const int ERROR    = 0;
const int INFEASIBLE    = -1;
const int OVERFLOW      = -2;
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
#endif  // _DS_H_
4. 测试程序的设计
测试程序采用菜单命令的方式根据用户输入的命令反复测试。
程序开始显示菜单提示，根据用户输入进行相应的测试，然后再显示菜单，直到用户选择退出测试程序。
while ( TRUE ) {
ShowMainMenu();
cmd = GetChoice();
switch ( cmd ) {
case 1: // 创建三元组
...
break;
case 2: // ...
...
case 0: // 退出
return ;
default: // 错误命令
}
}
显示菜单的程序：
// 显示主菜单
void ShowMainMenu()
{
static char *menu[]={
"三元组类型测试程序",
"1 创建三元组",
"2 ...",
...
"0 退出程序"
};
int i;
for(i=0; i < sizeof(menu)/sizeof(char *); i++)
printf("%s\n", menu[i]);
}
选择菜单的程序：
// 得到用户选择的菜单项
int GetChoice()
{
int i;
printf("请输入您的选择:");
scanf("%d",&i);
return i;
}
5. 录入源程序
参见所附源程序。
6. 测试数据和结果
包括：准备好的测试数据，期望结果，实际运行结果（运行程序后填写，并与期望结果对照）。
7. 总结
考虑：1）怎样将类C语言算法改写成C语言程序？ 2）怎样书写程序才能提高代码的可读性？如：模块划分，函数声明的位置，主函数的位置，函数具体实现的位置，采用缩进格式等。3）编写头文件的技巧。如何防止重复包含。 4）还遇到那些问题？
[源程序]
文件：DS.H 类C中通用的常量和类型
（略）。
文件：TRIPLET.H 三元组的定义和实现
（略）。
文件：CXX0102.CPP  测试程序（C代表班级，XX代表学号，0102代表实验1-2）
（略）。
实验1-3复数
[题目] 用C语言实现复数ADT，并编写测试程序。
[目的] 用C语言实现复数ADT；学习使用模块结构；学习编写调试程序。
[步骤]
1. 复数类型的ADT定义。
ADT Complex
{
数据对象: D={r,i| r,i∈R}
数据关系: R1={<r,i>| r是复数的实部,i是复数的虚部}
基本操作:
CreateComplex ( &z, r, i )
GetRealPart (z)
GetImagePart (z)
AddComplex ( &z, z1, z2 )
SubComplex ( &z, z1, z2 )
MulComplex ( &z, z
1, z2 )
DivComplex ( &z, z1, z2 )
} ADT Complex;
2. 复数类型的实现。
1）类型描述。
// 复数类型描述
typedef struct Complex {
double realpart;
double imagepart;
} Complex ;
2）基本操作的声明。
// 复数基本操作
Status CreateComplex ( Complex &z, double r, double i );
double GetRealPart ( Complex z );
double GetImagePart ( Complex z )
Status AddComplex ( Complex &z, Complex z1, Complex z2 );
Status SubComplex ( Complex &z, Complex z1, Complex z2 );
Status MulComplex ( Complex &z, Complex z1, Complex z2 );
Status DivComplex ( Complex &z, Complex z1, Complex z2 );
3）基本操作的实现。
// 复数基本操作的实现
Status CreateComplex ( Complex &z, double r, double i )
{
z.imagepart = i;
return OK;
}
double GetRealPart ( Complex z )
{
alpart;
}
double GetImagePart ( Complex z )
{
return z.imagepart;
}
Status AddComplex ( Complex &z, Complex z1, Complex z2 )
{
z.imagepart = z1.imagepart + z2.imagepart;
return OK;
}
Status SubComplex ( Complex &z, Complex z1, Complex z2 )
{
z.imagepart = z1.imagepart - z2.imagepart;
return OK;
}
Status MulComplex (  Complex &z, Complex z1, Complex z2 )
{
z.imagepart = z1.realpart*z2.imagepart + z1.alpart;
return OK;
}
Status DivComplex (  Complex &z, Complex z1, Complex z2 )
{
double b;
b = z2.alpart-z2.imagepart*z2.imagepart;
if( b == 0 )
return ERROR;
else {
+ z1.imagepart*z2.imagepart)/b;
z.imagepart = (-z1.realpart*z2.imagepart
+ z1.alpart)/b;
return OK;
}
}
3. 模块设计
主程序：测试复数模块的程序。
复数模块：实现复数类型的程序。
类C通用模块：包含类C中的预定义常量和类型。
模块的组织：
主程序 CXX0103.CPP
#include <stdio.h>
#include "complex.h"
void ShowMainMenu();
int GetChoice();
void main()
{
...
}
void ShowMainMenu()
{
...
}
int GetChoice()
{
...
}
复数模块 COMPLEX.H
// 防止重复包含
#ifndef _COMPLEX_H_
#define _COMPLEX_H_
#include "ds.h"
// 复数类型描述
typedef struct Complex {
double realpart;
double imagepart;
} Complex ;
// 基本操作的声明
Status CreateComplex ( Complex &z, double r, double i );
double GetRealPart ( Complex z );
double GetImagePart ( Complex z )
Status AddComplex ( Complex &z, Complex z1, Complex z2 );
Status SubComplex ( Complex &z, Complex z1, Complex z2 );
Status MulComplex (  Complex &z, Complex z1, Complex z2 );
Status DivComplex (  Complex &z, Complex z1, Complex z2 );
////////////////////////////
// 基本操作的实
现
Status CreateComplex ( Complex &z, double r, double i )
{
z.imagepart = i;
return OK;
}
double GetRealPart ( Complex z )
{
alpart;
}
...(以下省略)
#endif // _COMPLEX_H_
类C通用模块
#ifndef _DS_H_
#define _DS_H_
// 函数结果状态代码
const int TRUE      = 1;
const int FALSE    = 0;
const int OK        = 1;
const int ERROR    = 0;
const int INFEASIBLE    = -1;
const int OVERFLOW      = -2;
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
#endif  // _DS_H_
4. 测试程序的设计
测试程序采用菜单命令的方式根据用户输入的命令反复测试。
程序开始显示菜单提示，根据用户输入进行相应的测试，然后再显示菜单，直到用户选择退出测试程序。
while ( TRUE ) {
ShowMainMenu();
cmd = GetChoice();
switch ( cmd ) {
case 1: // 创建复数
...
break;
case 2: // ...
...
case 0: // 退出
return ;
default: // 错误命令
}
}
显示菜单的程序：
// 显示主菜单
void ShowMainMenu()
{
static char *menu[]={
"复数类型测试程序",
"1 创建复数",
"2 ...",
...
"0 退出程序"
};
int i;
for(i=0; i < sizeof(menu)/sizeof(char *); i++)
printf("%s\n", menu[i]);
}
选择菜单的程序：
// 得到用户选择的菜单项
int GetChoice()
{
int i;
printf("请输入您的选择:");
scanf("%d",&i);
return i;
}
5. 录入源程序
参见所附源程序。
6. 测试数据和结果
包括：准备好的测试数据，期望结果，实际运行结果（运行程序后填写，并与期望结果对照）。
7. 总结
考虑：1）怎样将类C语言算法改写成C语言程序？ 2）怎样书写程序才能提高代码的可读性？如：模块划分，函数声明的位置，主函数的位置，函数具体实现的位置，采用缩进格式等。3）编写头文件的技巧。如何防止重复包含。 4）还遇到那些问题？
[源程序]
文件：DS.H 类C中通用的常量和类型
（略）。
文件：COMPLEX.H 复数的定义和实现
（略）。
文件：CXX0103.CPP 测试程序（C代表班级，XX代表学号，0103代表实验1-3）
（略）。
实验1-4 时间复杂度
[题目] 分析和测试不同程序段的时间复杂度。
[目的] 通过统计不同算法中指定语句的执行频度，分析算法的时间复杂度。
[步骤]
[源程序]
文件：FREQ.H  用于统计执行频度的算法（程序段）
////////////////////////////
// File:    freq.h
// For:    统计语句执行频度
/
/ Author:
// Date:
////////////////////////////
#ifndef _FREQ_H_
#define _FREQ_H_
////////////////////////////
// 函数声明
int freq1 (int n);
int freq2 (int n);
int freq3 (int n);
////////////////////////////
/
/ 函数实现
int freq1 (int n)
{