查找算法

顺序查找和二分查找

#include <stdio.h>
#include <stdlib.h>
// 栈可用最大容量
#define MAXSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// 查找算法的数据类型定义
typedef char KeyType;

// 数据类型定义
typedef struct {
	KeyType key; // 关键字域
}ElemType;

// 顺序表结构类型定义
typedef struct {
	// 表基地址
	ElemType* R;
	// 表的长度
	int length;
}SSTable;

// 顺序查找算法
int Search_Seq(SSTable ST, KeyType key) {
	// 若找到则返回数据位置，未找到返回0
	for (int i = ST.length; i >= 1; i--) 
	if (ST.R[i].key == key) return i;
	return 0;
}

// 设置监视哨的顺序查找算法
int Search_Seq(SSTable ST, KeyType key) {
	ST.R[0].key = key;
	int i = 0;
	for (i = ST.length; ST.R[i].key != key; i--);
	return i;
}

// 折半查找（二分查找法）递归
// 要求数据是升序排列的
int Search_Bin(SSTable ST, KeyType key) {
	int low = 1, high = ST.length;
	// 如果low 小于等于 high，执行循环操作
	while (low <= high) {
		int mid = (low + high) / 2;
		if (ST.R[mid].key == key) return mid;
		// 中间值大于查找值，改变high值
		else if (ST.R[mid].key > key) high = mid - 1;
		// 反之，改变low值
		else low = mid + 1;
	}
	// 未找到，返回0
	return 0;
}

// 二分查找 非递归
int Search_Bin(SSTable ST, KeyType key, int low, int high) {
	if (low > high) return 0;
	int mid = (low + high) / 2;
	if (ST.R[mid].key == key) return mid;
	// 递归进行
	else if (ST.R[mid].key > key) Search_Bin(ST, key, low, mid - 1);
	else Search_Bin(ST, key, mid + 1, high);
}

int main() {
	return 0;
}

二叉排序树

#include <stdio.h>
#include <stdlib.h>

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// 查找算法的数据类型定义
typedef char KeyType;

// 二叉排序树的存储结构
typedef struct {
	// 关键字域
	KeyType key;
}ElemType;

typedef struct BSTNode{
	// 数据域
	ElemType data;
	// 指针域
	struct BSTNode* lchild, * rchild;
}BSTNode, *BSTree;

// 递归查找二叉排序树上的数据
BSTree SearchBST(BSTree T, KeyType key) {
	// 树为空且根结点的值为key时，返回根节点的位置
	if (!T || T->data.key == key) return T;
	// key<根结点的值，递归查找左子树
	else if (T->data.key > key) return SearchBST(T->lchild, key);
	// 反之，递归查找右子树
	else return SearchBST(T->rchild, key);
}

// 在二叉排序树上插入数据
Status Insert_key(BSTree& T, KeyType key) {
	// 根节点为空，将key插入到根结点 
	if (!T) T->data.key = key;
	// key<根结点的值，递归查找左子树
	else if (T->data.key > key) Insert_key(T->lchild, key);
	// 反之，递归查找右子树
	else Insert_key(T->rchild, key);
	return OK;
}

// 生成二叉排序树
Status Creat_BST(BSTree& T, KeyType key[]) {
	// 循环遍历数组，依次插入到二叉排序树中
	for (int i = 0; key[i] != NULL; i++) Insert_key(T, key[i]);
	return OK;
}

int main() {
	return 0;
}