网站规划与设计一千字,通辽做网站,怎么建自己的摄影网站,晋中品牌网站建设建设实验十四 查找算法的实现
一、【实验目的】
1、掌握顺序排序#xff0c;二叉排序树的基本概念
2、掌握顺序排序#xff0c;二叉排序树的基本算法#xff08;查找算法、插入算法、删除算法#xff09;
3、理解并掌握二叉排序数查找的平均查找长度。
二、【实验内容】
…实验十四 查找算法的实现
一、【实验目的】
1、掌握顺序排序二叉排序树的基本概念
2、掌握顺序排序二叉排序树的基本算法查找算法、插入算法、删除算法
3、理解并掌握二叉排序数查找的平均查找长度。
二、【实验内容】
1、已知如下11个元素的有序表: { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 }
请设计完成二分查找法查找关键字为64的数据元素的程序。
2、已知一个个数为12的数据元素序列为 { “Dec”, “Feb”, “Nov”, “Oct”, “June”, “Sept”, “Aug”, “Apr”, “May”, “July”, “Jan”, “Mar” }, 要求:
1按各数据元素的顺序字母大小顺序构造一棵二叉排序数并中序打印排序结果。
2查找数据”Sept”是否存在。
三、【实验源代码】 CPP版
#include iostream
#include string
using namespace std;class Node // 定义二叉树节点
{
public:string data; // 存储节点的数据Node* left; // 指向左子节点Node* right; // 指向右子节点Node(string data) // 构造函数{this-data data; // 初始化数据this-left nullptr; // 左子节点指向空this-right nullptr; // 右子节点指向空}
};// 在长度为 n 的 a 数组中找 x找到返回下标找不到返回 -1
int binarySearch(int a[], int x, int n)
{int l 0; // 左端点int r n - 1; // 右端点while (l r) // 当左端点小于右端点时循环{int mid (l r) 1; // 取中间点右移一位相当于除以2if (x a[mid]) // 如果要查找的数在中间点的右边l mid 1; // 左端点移到中间点的右侧elser mid; // 右端点移到中间点或中间点的左侧}if (a[l] x) // 如果查到了要找的数return l; // 返回下标cout 没找到 x endl; // 否则输出没找到的消息return -1; // 返回-1
}void insert(Node* root, string s) // 向二叉搜索树中插入一个节点
{if (root nullptr) // 如果根节点为空{root new Node(s); // 创建一个新节点作为根节点return;}Node* t root; // 定义指针t指向根节点while (t ! nullptr) // 循环直到找到合适的位置插入新节点{int com s.compare(t-data); // 比较节点的数据与要插入的数据的大小关系if (com 0) // 如果相等说明已经存在该节点return; // 直接返回else if (com 0) // 如果要插入的数据大于节点的数据说明要插入右子树{if (t-right nullptr) // 如果右子树为空t-right new Node(s); // 创建一个新节点作为右子节点elset t-right; // 否则继续向右子树查找}else if (com 0) // 如果要插入的数据小于节点的数据说明要插入左子树{if (t-left nullptr) // 如果左子树为空t-left new Node(s); // 创建一个新节点作为左子节点elset t-left; // 否则继续向左子树查找}}
}Node* initBiTree(string ss[], int n) // 初始化二叉搜索树
{Node* root new Node(ss[0]); // 创建根节点for (int i 1; i n; i) // 循环插入其余的节点insert(root, ss[i]);return root; // 返回根节点
}void inOrder(Node* root) // 中序遍历二叉搜索树
{if (root ! nullptr) // 如果节点不为空{if (root-left ! nullptr) // 如果有左子节点先中序遍历左子树inOrder(root-left);cout root-data ; // 输出节点的数据if (root-right ! nullptr) // 如果有右子节点后中序遍历右子树inOrder(root-right);}
}void search(Node* root, string s) // 在二叉搜索树中查找一个节点
{while (root ! nullptr) // 如果节点不为空{int com s.compare(root-data); // 比较节点的数据与要查找的数据的大小关系if (com 0) // 如果相等说明找到了{cout 找到了 s endl; // 输出找到的消息return;}else if (com 0) // 如果要查找的数据大于节点的数据说明要查找右子树root root-right; // 继续向右子树查找else // 否则要查找左子树root root-left; // 继续向左子树查找}cout 没找到 s endl; // 输出没找到的消息
}int main()
{int a[] { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 }; // 定义一个有序数组int x 64; // 要查找的数int idx binarySearch(a, x, sizeof(a) / sizeof(a[0])); // 在数组中查找要查找的数if (idx ! -1) // 如果找到了cout x 在数组中的下标是 idx endl; // 输出结果string ss[] { Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar }; // 定义一个字符串数组Node* root initBiTree(ss, sizeof(ss) / sizeof(ss[0])); // 初始化二叉搜索树cout 中序遍历序列为;inOrder(root); // 中序遍历二叉搜索树cout endl;string s Sept; // 要查找的字符串search(root, s); // 在二叉搜索树中查找节点return 0;
}java版
class Main
{static class Node{String data;Node left;Node right;Node(String data){this.data data;}}// 在长度为 n 的 a 数组中找 x找到返回下标找不到返回 -1static int binarySearch(int[] a, int x, int n){int l 0;int r n - 1;while (l r){int mid (l r) 1;if (x a[mid]) // x在 mid 的右边l mid 1;elser mid;}if (a[l] x)return l;System.out.println(没找到 x);return -1;}static void insert(Node root, String s){if (root null){root new Node(s);return;}Node t root;while (t ! null){int com s.compareTo(t.data);if (com 0)return;else if (com 0)// 右子树{if (t.right null)t.right new Node(s);elset t.right;} else if (com 0){if (t.left null)t.left new Node(s);elset t.left;}}}static Node initBiTree(String[] ss, int n){Node root new Node(ss[0]);for (int i 1; i n; i)insert(root, ss[i]);return root;}static void inOrder(Node root){if (root ! null){if (root.left ! null)inOrder(root.left);System.out.print(root.data );if (root.right ! null)inOrder(root.right);}}public static void main(String[] args){int[] a { 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 };int x 64;int idx binarySearch(a, x, a.length);if (idx ! -1)System.out.println(x 在数组中的下标是 idx);String[] ss { Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar };Node root initBiTree(ss, ss.length);inOrder(root);System.out.println();String s Sept;boolean search search(root, s);if (search)System.out.println(找到了 s);else{System.out.println(没找到 s);}}private static boolean search(Node root, String s){while (root ! null){int com s.compareTo(root.data);if (com 0)return true;else if (com 0)root root.right;else{root root.left;}}return false;}
}四、【实验结果】
64在数组中的下标是6
中序遍历序列为Apr Aug Dec Feb Jan July June Mar May Nov Oct Sept
找到了Sept五、【实验总结】
