数 据 结 构 实 验 指 导 书
数据结构实验指导书
目录
数据结构实验指导书 .......................................................................................................................1
目录...........................................................................................................................................1 实验指导书概述 ...............................................................................................................................2 上机实验题目 ...................................................................................................................................3
实验一 C语言相关知识复习................................................................................................3
一、实验目的 ...................................................................................................................3
二、实验内容 ...................................................................................................................3 实验二 单链表的插入、删除 ...............................................................................................3
一、实验目的 ...................................................................................................................3
二、实验内容 ...................................................................................................................3
三、实现提示 ...................................................................................................................4 实验三 栈及其应用 .................................................................................................................5
一、实验目的 ...................................................................................................................5
二、实验内容 ...................................................................................................................5 实验四 二叉树的递归算法 .....................................................................................................6
一、实验目的 ...................................................................................................................6
二、实验内容 ...................................................................................................................6 实验五 图的遍历 .....................................................................................................................7
一、实验目的 ...................................................................................................................7
二、实验内容 ...................................................................................................................7 实验六 有序表的查找 .............................................................................................................7
一、实验目的 ...................................................................................................................7
二、实验内容 ...................................................................................................................7 实验七 哈希表 .........................................................................................................................7
一、实验目的 ...................................................................................................................7
二、实验内容 ...................................................................................................................7 实验八 内部排序算法的应用 .................................................................................................8
一、实验目的 ...................................................................................................................8
二、实验内容 ...................................................................................................................8
实验指导书概述
“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因，使得掌握这门课程具有较大难度： 内容多，时间短，给学习带来困难；
贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点； 隐含在各部分的技术和方法丰富，也是学习的重点和难点； 先修课程中所介绍的专业性知识不多，加大了学习难度。
由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。
上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。
为了达到上述目的，本指导书安排了8个实验题目，它们与教科书的各章有紧密的关系，使学生在实验后能加深对课程内容的理解，增强动手能力。
每个实验题目采取了统一的格式，由问题描述、基本要求、测试数据、实现提示等部分组成。
问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；
要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；
测试部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和 严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；
实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实现。
下面带*的题目为选做题目。
2
上机实验题目
实验一 C语言相关知识复习
一、实验目的
复习C语言中函数、数组、结构体、文件等概念，掌握它们的描述与操作方法；熟悉掌握C++中typedef、引用参数调用（&）的概念及使用方法，为理解数据结构课程的后续内容以及算法书写奠定基础。
二、实验内容
1 问题描述：编写一个函数，求一个整数数组中的最大、最小值。
要求：在函数声明中采用引用参数传递方式实现最大、最小值的返回。 测试：在主函数中输入10个数，调用此函数，打印输出最大和最小值。 2 关于指针的使用：
用malloc方式分别申请两个指针，并实现两个指针内容的比较大小操作。 要求：此功能在一个函数内实现，该函数接受两个整数值，存储到两个指针内容中，输出两者中的最大值。
测试：从主函数中输入两个数，调用该函数，打印输出交换后的值。
实验二 单链表的插入、删除
一、实验目的
1、熟悉某种数据结构在计算机上实现的方法。
2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。
3、体会单链表操作、有序表插入、删除的一般方法。
二、实验内容
问题描述：已知递增有序的单链表A，编写算法实现向A中插入或删除一个元素，并保持A的有序性。
实验要求：
1、结点的数据均为整型。
2、若表中已经存在此元素，则不插入
3
三、实现提示
1.在已知的线性表中插入或删除，需要下面的辅助函数：线性表的创建、线性表的遍历
2.在单链表表中插入或删除，需依次实现：
a) 单链表结构的定义
b) 单链表的创建（头插法或尾插法建表） c) 单链表的遍历
d) 单链表的插入、删除（采用顺序查找方法，顺头指针往后，查找插入或删除位置，再修改指针）
//头文件
#include "stdlib.h" //预定义常量 #define NULL 0
//单链表的定义
typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; //单链表的创建
void Create_List(LinkList &L) { int data; LinkList p,q; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;
q=L;
scanf("%d",&data); while(data!=0) {
p=(LinkList)malloc(sizeof(LNode));
p->data=data;
p->next=q->next;
q->next=p;
q=p;
scanf("%d",&data); } }
//单链表的遍历
void TranverseList(LinkList L) {
LinkList p;
p=L->next;
if (p==NULL)
{
printf("nil\n");
return;
}
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n"); }
实验三 栈及其应用
一、实验目的
1、熟悉栈的顺序表示与实现。
2、熟悉栈的应用。
3、理解并掌握递归函数的设计与实现。
二、实验内容
1 问题描述：利用栈实现十进制数n转化为d进制数 要求：
1) 输入一个n和d，打印输出d进制数序列。
2) 利用顺序栈来实现十进制数n转化为其他d进制数。此时，需要同时实现初始化空栈、入栈、出栈、判栈空等辅助功能。 测试数据：
（1） 输入n:1348
d:8 输出：2504 （2） 输入n:9
d:8 输出：11 （3） 输入n:0
d:8 输出：0 2 问题描述：利用栈实现算术表达式求值。 要求：
1) 参与运算的操作数为10以内的数值。 测试数据：
自拟。
实验四 二叉树的递归算法
一、实验目的
1、掌握二叉树的表示与实现。
2、掌握二叉树的定义、创建、遍历等基本操作的实现。
3、熟悉求二叉树深度等递归算法的设计与实现。
二、实验内容
问题描述：已知二叉树t，分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度，并对二叉树分别进行中序遍历。 要求：
1、二叉树分别采用顺序或二叉链表存储。
2、树中的数据类型约定为整型。 测试数据：
1、输入序列：-+aØØ*bØØ-cØØdØØ/eØØfØØ创建二叉树； 输出：深度：5
前序序列：-+a*b-cd/ef
中序序列：a+b*c-d-e/f
后序序列：abcd-*+ef/- T:d / e f
2、t=nil
输入：Ø
输出：深度：0
6 实验五 图的遍历
一、实验目的
熟悉图的基本操作，掌握图遍历的设计与实现。
二、实验内容
问题描述：已知的描述校园景点的图，实现对该图的深度优先和广度优先遍历。 要求：
图采用邻接矩阵存储，顶点信息包括景点的名称和简单描述。
实验六 有序表的查找
一、实验目的
1、理解各种查找方法的基本思想
2、熟悉有序表查找方法的算法实现
二、实验内容
1 已知一有序的序列{1,3,5,7,9}，采用折半法分别查找3和6。
2已知输入一无序的序列{5,1,3,9,7}，创建一棵二叉排序树，然后对其遍历，输出递增有序的序列。
实验七 哈希表
一、实验目的
理解哈希表的概念和基本操作；熟悉哈希表的创建、查找、插入的算法实现。
二、实验内容
问题描述：已知11位好友的名字各不相同，设计并实现一个哈希表，根据好友的名字，可以取得其生日。 要求：
1、好友的信息包含名字和生日两个数据项，其中好友的名字为主键，用汉语拼音形式存放；
2、哈希函数采取：好友名字中所有拼音字母ASCII码值的和 MOD 11(除以1
1 取余)；
3、采取线性探测再散列的方式处理冲突。
实验八 内部排序算法的应用
一、实验目的
理解各种内部排序方法的基本思想；熟悉各种内部排序方法的算法实现
二、实验内容
问题描述：已知一序列{503，087，512，061，908，170，897，275，653，426}，分别采取下列排序方法对其进行排序：
（1）直接插入排序；
（2）简单选择排序；
（3）起泡排序； （4）快速排序； （5）堆排序。
8
