查找及其相关算法

爱被打了一巴掌 2022-10-08 13:29 193阅读 0赞

### 文章目录 ###

*  一、静态查找表
 *   *  1.1 顺序表查找
     *  1.2 有序表查找
     *   *  1.2 .1折半查找（二分查找）
 *  二、动态查找表
 *  三、哈希表

# 一、静态查找表 #

## 1.1 顺序表查找 ##

## 1.2 有序表查找 ##

### 1.2 .1折半查找（二分查找） ###

优点：查找的效率高  
缺点：已排好序，只适用于顺序存储

例题：  
随机产生80 个整数构成的递增序列，  
使用折半查找算法查找指定的整数，并统计比较次数。  
提示：可用 a\[i\] = a\[i-1\] + rand() % 10 + 1 产生递增序列。 (1,10-1+1)

/*
    * 
    
    
    rand() % n +a;
     其中的a是起始值，n-1+a是终止值，n是整数的范围
    	
    	
    	*/
    
    #include <iostream>
    using namespace std;
    
    int c=0;
    
    //折半查找
    int Search_bin(int *a, int key) {
        
    	int low = 1;
    	int high = 80;
    	while (low<=high)
    	{
        
    		c++;
    		int mid=(low + high) / 2;
    		if (key==a[mid]) {
        
    			return mid;
    			
    		}
    		else if(key<a[mid]){
        
    			high = mid - 1;
    
    		}
    		else {
        
    			low = mid + 1;
    		}
    		
    
    	}
    	return -1;
    }
    
    
    int main() {
        
    	int a[80];
    	
    	for (int i = 1; i <= 80; i++) {
        
    		if (i == 1) {
        
    			a[i] = rand() % 10 + 1;
    		}
    		else {
        
    			a[i] = a[i - 1] + rand() % 10 + 1;
    		}
    	}
    	for (int i = 1; i <= 80; i++) {
        
    		cout << a[i] << "\t";
    		if (i % 10 == 0) {
        
    			cout << endl;
    		}
    	}
    	cout << endl;
    
    	int k;
    	cout << "请输入你要查找的元素的值:";
    	cin >> k;
    
    	if (Search_bin(a,k)) {
        
    		cout << k << "在a[]中位置为：" << Search_bin(a, k) << endl;
    		cout << "比较次数为：" << c << endl;
    	}
    	else {
        
    		cout << "不在a中";
    	}
    
    	return 0;
    }

1.2.2 索引顺序表

# 二、动态查找表 #

二叉排序树（二叉查找树）

/*
    输入10 个不同整数，依次插入到一颗初始为空的二叉排序树中，
    并对其进行中序遍历，以验证树的正确性
    */
    #include <iostream>
    using namespace std;
    
    
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 10 //存储空间分配增量
    
    //栈存储结构
    typedef struct {
        
    	int* base; //栈构造之前和销毁之后，值都为NULL
    	int* top; //栈顶指针
    	int stacksize; //当前已分配的存储空间，以元素为单位
    }SqStack;
    
    /*初始化*/
    int InitStack(SqStack& S) {
        
    	S.base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
    	if (!S.base) //存储分配失败
    		exit(OVERFLOW);
    	S.top = S.base;
    	S.stacksize = STACK_INIT_SIZE;
    	return 1;
    
    }
    /*判断栈是否为空*/
    int StackEmpty(SqStack S)
    {
        
    	if (S.base == S.top)
    		return 1;
    	else
    		return 0;
    }
    
    /*插入*/
    int Push(SqStack& S, int e) {
        
    	//e 新的栈顶元素
    	if (S.top - S.base >= S.stacksize) {
        
    		S.base = (int*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(int));
    		if (!S.base)
    			exit(OVERFLOW);
    		S.top = S.base + S.stacksize;
    		S.stacksize += STACKINCREMENT;
    	}
    	*S.top++ = e;
    	return 1;
    }
    /*删除栈顶元素并返回其值*/
    int Pop(SqStack& S, int& e) {
        
    	if (S.top == S.base)
    		return 0;
    	e = *--S.top;
    	return 1;
    }
    
    /*二叉链表存储结构*/
    typedef struct BiTNode {
        
    	int data;
    	struct BiTNode* lchild, * rchild;
    }BiTNode, * BiTree;
    
    int SearchBST(BiTree T, int key, BiTree f, BiTree& p)
    //查找成功，参数p指向查找到的结点，f指向它的双亲；否则p指向key应插入的父结点或指向空（当T为空时）
    {
        
    	if (!T)
    	{
        
    		p = f;
    		return 0;
    	}
    	else if (key == T->data)
    	{
        
    		p = T;
    		return 1;
    	}
    	else if (key < T->data)
    		return (SearchBST(T->lchild, key, T, p));
    	else
    		return (SearchBST(T->rchild, key, T, p));
    }
    
    
    int InsertBST(BiTree& T, int e)
    //在二叉排序树中插入值为elem的元素，T指向二叉排序树根结点
    {
        
    	BiTree p = NULL, f = NULL;
    	if (!SearchBST(T, e, f, p)) // 如果查找不成功
    	{
        
    		BiTree s = (BiTree)malloc(sizeof(BiTNode));
    		s->data = e;
    		s->lchild = s->rchild = NULL;
    		if (!p) // 若二叉树为空被插结点作为树的根结点
    			T = s; 
    		else if (e< p->data) //被插结点插入到p的左子树中
    			p->lchild = s;
    		
    		else  //被插结点插入到p的右子树中
    			p->rchild = s; 
    		return 1;
    	}
    	else // 查找成功,不插
    		return 0; 
    }
    
    /*非递归中序遍历*/
    void InOrderTraverse(BiTree t)
    {
        
    	SqStack S;
    	InitStack(S);
    	BiTree p = t;
    	while (p || !StackEmpty(S))
    	{
        
    		if (p) {
        
    			Push(S, (int)p);
    			p = p->lchild;
    		}
    		else {
        
    			Pop(S, (int&)p);
    			cout << p->data;
    			p = p->rchild;
    		}
    	}
    
    
    }
    
    int main() {
        
    	int a[10];
    	cout << "输入10 个不同整数:" << endl;
    	for (int i = 0; i < 10; i++) {
        
    		cin >> a[i];
    	}
    
    	BiTree t;
    
    
    	for (int i = 0; i < 10; i++) {
        
    		InsertBST(t,a[i]);
    	}
    	InOrderTraverse(t);
    
    	return 0;
    }

# 三、哈希表 #