查找
第一题：二叉排序树
[问题描述]
编写程序实现下面运算：在二叉排序树中查找关键字为key的记录。
[输入]
无序数的个数5，一串无序数：1，99，34，56，77。关键字key的值。
[输出]
若存在key则返回“二叉排序树中存在key”，若不存在key则返回“二叉排序树中不存在key”，
[存储结构]
采用二叉链表存储。
[算法的基本思想]
创建二叉排序树：先实现二叉排序树插入元素的函数insertBST()，在创建规模为n的二叉排序树时，调用n次insertBST()函数便可以实现。查找元素：若比根结点的key小则递归左子树，若比根结点的key大则递归右子树。
#include<stdio.h> #include<malloc.h> #define NULL 0 typedef struct BTNode{ int key; //因为是二叉排序树，命名为key struct BTNode *lchild; struct BTNode *rchild; }BTNode, *node; int insertBST(node &bt, int key){ //单个插入元素，使得仍然满足二叉排序树的性质 //因为要改变bt指针，所以使用&引用型，也可以是BTNode *&bt if(bt == NULL){ //当前指针为空，满足插入条件 bt = (node)malloc(sizeof(BTNode)); bt->lchild = bt->rchild = NULL; bt->key = key; return 1; } else{ //若结点不为空，寻找插入位置 if(key == bt->key){ //相同元素不插入 return 0; //通过返回值0，1可以判断是否插入 } else if(key < bt->key){ //往左子树插 return insertBST(bt->lchild, key); } else{ //往右子树插 return insertBST(bt->rchild, key); } } } void createBST(node &bt, int n){ //创建二叉排序树 int i; int key; for(i = 0; i < n; i++){ //n个元素，就是调用n次插入函数 //第一个创建的结点，就是根结点 printf("请输入二叉树元素："); scanf("%d", &key); insertBST(bt, key); } } void searchBST(node &bt, int key){ //二叉排序树中，寻找key if(bt == NULL){ printf("二叉排序树中不存在key"); } else{ if(bt->key == key){ printf("二叉排序树中存在key"); } else if(bt->key > key){ searchBST(bt->lchild, key); } else{ searchBST(bt->rchild, key); } } } int main(){ printf("请输入二叉排序树规模："); int n; //记录二叉树元素个数 scanf("%d", &n); node bt; //bt就为根结点 createBST(bt, n); printf("请输入要查找的元素key："); int key; scanf("%d", &key); searchBST(bt, key); }
结果演示：
结果与分析：
优点：成功创建了二叉排序树。缺点：并没有平衡二叉排序树，再查找时不能使得二叉排序树的查找时间效率发挥最好。时间复杂度：O(n)，空间复杂度：O(n)，因为创建二叉排序树的n个结点需要n次插入insertBST()函数。
第二题：递归折半
[问题描述]
编写程序试将折半查找的算法改写成递归算法。
[输入]
无序数的个数5，一串无序数：1，99，34，56，77。关键字key的值。
[输出]
若存在key则返回“存在key元素”，若不存在key则返回“不存在key元素”，
[存储结构]
顺序存储。
[算法的基本思想]
将输入数据存入数组，对数组进行冒泡排序，再对输入的key值进行折半查找
#include<stdio.h> void sort(int num[], int n){ //对n数组进行排序 int i, j, temp; for(i = 1; i < n; i++){ for(j = 0; j < n - i; j++){ if(num[j] > num[j + 1]){ temp = num[j]; num[j] = num[j + 1]; num[j + 1] = temp; } } } } int flag = 0; //flag用于记录是否存在key int search(int num[], int key, int low, int high){ //折半查找法，递归实现 if(low > high){ return -1; } else{ int mid; mid = (low + high) / 2; if(num[mid] == key){ flag = 1; return 1; } else{ if(num[mid] < key){ return search(num, key, mid + 1, high); } else{ return search(num, key, low, mid - 1); } } } } int main(){ printf("请输入数组num的规模："); int n; scanf("%d", &n); int i; int num[n]; for(i = 0; i < n; i++){ printf("请输入第%d个元素：", i + 1); scanf("%d", &num[i]); } sort(num, n); printf("请输入key的值："); int key; scanf("%d", &key); search(num, key, 0, n); if(flag == 1){ printf("存在key元素"); } else{ printf("不存在key元素"); } }
结果演示：
结果与分析：
优点：实现了递归的折半查找法。缺点：在折半查找前，使用了冒泡排序，增加了时间复杂度。时间复杂度：O(n²)，空间复杂度O(n)因为使用了冒泡排序，时间复杂度增加
心得
- 二叉排序树的创建：先实现单个子结点的插入时，如何去使其仍满足二叉排序树的性质，创建就是调用结点个数次的插入。
- &引用型参数，因为在插入时，要对结点进行改变，所以使用&
