A B C D E F G H I K J L M N 有向图G的邻接矩阵: 0 5 0 7 0 0 0 0 4 0 0 0 8 0 0 0 0 9 0 0 5 0 0 6 0 0 0 5 0 0 3 0 0 0 1 0 图G的邻接矩阵转换成邻接表: 0: 1 3 1: 2 2: 0 5 3: 2 5 4: 3 5: 0 4 从顶点0开始的DFS: 0 1 2 5 4 3 从顶点0开始的BFS: 0 1 3 2 5 4 第1次查找:在[0,9]中查找到元素R[4]:5 第2次查找:在[5,9]中查找到元素R[7]:8 第3次查找:在[8,9]中查找到元素R[8]:9 元素9的位置是8 12]，哈希函数为H(k)=key%p，（p取
13），并采用线性探查法解决冲突。
（2） 在上述哈希表中查找关键字为29的记录。
（3） 在上述哈希表中删除关键字为77的记录，再将其插入。 【输出结果】
输出结果例子如下：
哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表关键字: 77 54 16 43 31 29 46 60 74 88 90 搜索次数: 2 1 1 1 1 4 1 1 1 1 1 平均搜索长度ASL(11)= ha[6].key=29 删除关键字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表关键字: 54 16 43 31 29 46 60 74 88 90 搜索次数: 1 1 1 1 4 1 1 1 1 1 平均搜索长度ASL(10)= 未找到77 插入关键字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表关键字: 77 54 16 43 31 29 46 60 74 88 90 搜索次数: 2 1 1 1 1 4 1 1 1 1 1 平均搜索长度ASL(11)= 实验19：查找综合实验
一、实验目的
1）熟悉查找的基本操作。
2）掌握二叉排序树的基本运算。
3）加深对查找的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋的计算机。 本次实验共计4学时。
三、实验内容
1、统计字符串中字符出现的次数
编写一个程序，由键盘输入一个字符串，统计该字符串中出现的字符及其次数。然后输出结果。要求用一个二叉树来保存处理结果，字符串中每个不同的字符用树的结点表示，结点应该包含四个域：该字符、该字符出现的次数、左子树指针、右子树指针；其中左子树的字符的ASCII码均小于该字符，右子树的字符的ASCII码均大于该字符。
提示：
从字符串中依次读取字符，在二叉树中查找该字符是否存在。
如果存在，则该字符的出现次数加1；如果不存在，则按照二叉排序树的要求插入该字符结点，同时设置出现次数为1。
全部字符读完以后，调用二叉树的中序遍历，有序的输出每个字符及其出现的次数。
2、二叉排序树
【基本要求】
编写一个程序，实现二叉排序树的基本运算，并在此基础上完成如下功能：
（1） 由{4，9，0，1，8，6，3，5，2，7}创建一棵二叉排序树bt，并以括号表示法输出。 （2） 判断bt是否为一棵二叉排序树。
（3） 采用递归和非递归两种方法查找关键字为6的结点，并输出其查找路径。 （4） 分别删除bt中的关键字为4和5的结点，并输出删除后的二叉排序。
【输出结果】
输出结果例子如下：
创建一棵BST树: 第1步,插入4:4 第2步,插入9:4(,9) 第3步,插入0:4(0,9) 第4步,插入1:4(0(,1),9) 第5步,插入8:4(0(,1),9(8)) 第6步,插入6:4(0(,1),9(8(6))) 第7步,插入3:4(0(,1(,3)),9(8(6))) 第8步,插入5:4(0(,1(,3)),9(8(6(5)))) 第9步,插入2:4(0(,1(,3(2))),9(8(6(5)))) 第10步,插入7:4(0(,1(,3(2))),9(8(6(5,7)))) BST:4(0(,1(,3(2))),9(8(6(5,7)))) bt是一棵BST 查找6关键字(递归): 4 9 8 6 查找6关键字(非递归): 6 8 9 4 删除操作: 原BST:4(0(,1(,3(2))),9(8(6(5,7)))) 删除结点4:3(0(,1(,2)),9(8(6(5,7)))) 删除结点5:3(0(,1(,2)),9(8(6(,7))))
实验指导手册
