数据结构实验指导书(1) 联系客服

发布时间 : 星期五 文章数据结构实验指导书(1)更新完毕开始阅读

数据结构试验指导书

实验09 二叉排序树的基本操作

实验学时:2学时

实验类型:上机

背景知识:树表查找。

目的要求:

掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。

实验内容:

(1) 随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树,然后删除某一指定关

键字元素。

(2) * 建立AVL树并实现删除某一指定关键字元素。 (3) *综合训练: 树种统计

随着卫星成像技术的应用,自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量,计算每种树占总数的百分比。首先输入正整数N(≤105),随后N行,每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成(不区分大小写)。按字典序递增输出各种树的种类名称及其所占总数的百分比,其间以空格分隔,每种树的信息占一行。

实验说明: 1.存储定义

参见实验05二叉链表的存储。

2.各种关键字数据输入可利用随机函数自动产生,以便节省上机时间。

注意问题:

1.注意建立二叉排序树时相同元素的处理。

2.注意理解动态查找概念。

31

数据结构试验指导书

实验10 哈希表的生成

实验学时:2学时

实验类型:上机

背景知识:哈希查找。

目的要求:

掌握哈希存储结构的思想,能选择合适的哈希函数,实现不同冲突处理方法的哈希表的查找、建立。

实验内容:

(1)设计哈希函数及处理冲突的方法;

(2)键盘输入数据,利用设计的哈希函数及线性探测法生成哈希表; (3)用同样的输入数据和哈希函数,用链地址法处理冲突生成哈希表; (4)在主函数中设计一个简单的菜单,分别调试上述算法; (5)分析两种方法的平均查找长度。 (6)*综合训练:QQ帐户的申请与登陆

首先输入一个正整数N(≤105),随后给出N行指令。每行指令的格式为:“命令符(空格)QQ号码(空格)密码”。其中命令符为“N”(代表New)时表示要新申请一个QQ号,后面是新帐户的号码和密码;命令符为“L”(代表Login)时表示是老帐户登陆,后面是登陆信息。QQ号码为一个不超过10位、但大于1000(据说QQ老总的号码是1001)的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。

针对每条指令,给出相应的信息:

1)若新申请帐户成功,则输出“New: OK”;

2)若新申请的号码已经存在,则输出“ERROR: Exist”; 3)若老帐户登陆成功,则输出“Login: OK”;

4)若老帐户QQ号码不存在,则输出“ERROR: Not Exist”; 5)若老帐户密码错误,则输出“ERROR: Wrong PW”。

实验说明:

各种关键字数据输入可利用随机函数自动产生,以便节省上机时间。

注意问题:

1.注意建立哈希表时相同元素的处理。

2.注意理解哈希查找思想。

32

数据结构试验指导书

33

数据结构试验指导书

实验11 常用的内部排序算法

实验学时:2学时 实验类型:上机

背景知识:各种排序方法

目的要求:

1.掌握常见的内部排序算法的思想及其适用条件。 2.掌握常见的内部排序算法的程序实现。

实验内容:

输入一组关键字序列分别实现下列排序:

(1) 实现简单选择排序、直接插入排序和冒泡排序。 (2) 实现希尔排序算法。 (3) 实现快速排序算法。 (4) 实现堆排序算法。 (5) * 快速排序的非递归算法。 (6) * 实现折半插入排序。

(7) 在主函数中设计一个简单的菜单,分别测试上述算法。

(8) * 综合训练:采用几组不同数据测试各个排序算法的性能(比较次数和移动次数)。

实验说明:

1.类型定义

#define MAXSIZE 100 /*参加排序元素的最大个数*/ typedef int KeyType; typedef struct { KeyType key;

InfoType otherinfo; // 其他字段 }RedType; typedef struct {

RedType r[MAXSIZE+1];

int length; /*参加排序元素的实际个数*/ }SqList;

34