【数据结构】查找算法和堆栈的应用

查找算法

（1）查找算法分别是顺序查找 mid查找（折半，插入，斐波那契）

前者的操作复杂度都是n，后面三个的操作复杂度是log2n

（2）关于后面三种东西的具体实现

//顺序查找是n，剩下三种最坏的时候都是log2n
//此外，剩下的三种都要求程序已经按顺序排好，区别就在于mid的选取不同
int searchTwo(int *arr,int start,int end,int num){
    if(start>=end){
        return -1;
    }else{
        int mid=(start+end)/2;//另外三种查找方法，区别其实就在于如何获取mid的数值
        if(num==arr[mid]){
            return mid;
        }else if(num<arr[mid]){
            return searchTwo(arr,start,mid-1,num);
        }else if(num>arr[mid]){
            return searchTwo(arr,mid+1,end,num);
        }
    }
}

（折半的函数为）

（start+end）/2

（插差值寻找的函数是）‘

利用了一个概率分布的性质进行寻找的

（start+（num-arr[start]）*(end-start)/(arr[end]-arr[start])）

（斐波那契的查找函数）

斐波那契数的一个性质就是，n越大，（n-1）/n更接近黄金比例0.618.。。。。’

说白了斐波那契还是没事找事。。。。。

例如斐波那契相邻两项是  8  13，又加入现在的范围是（0，12），长度刚好为十三，那么就可以划分为一个长度为8和长度为5的两个部分，mid就是8+0-1=7

不过这个递归方法和上面的不一致，之前的查找都是找到一个分界点，然后分界点前后划分开

（start，mid-1）和（mid+1，end） 

而这个递归方法，为了保证斐波那契数列长度的完整性，需要的递归区间是

（start，mid）和（mid+1，end） 

int F(int k){
    if(k==1){return 1;}
    else if(k==0){return 0;}
    else{return F(k-1)+F(k-2);}
}
int fbnq_mid(int start,int end){//这里保证传进来的数字足够组成斐波那契数列
    int k=0;                             //具体对应实际情况的时候，可能要对数组进行补全操作才行
    int length=end-start+1;              //数组有效长度n到最近的一个斐波那契数字之间，全部填充
    while(length!=F(k)){                 //其实本质上，只是在利用0.618的例子。。。。没啥劲
        k++;
    }
    return F(k-1);
}

堆栈的应用

1.n皇后问题实际上是一种递归回溯问题,其实和树/图结构里面dfs的本质很接近,如果画出图来就可以看出是另一种形式树的延申(离散中的树结构穷举)

2.n皇后的规则:

在一个n*n的矩阵中,每个皇后同行同列,以及对角线位置上不能有其他皇后,写出所有符合条件的皇后排列情况(这里以8皇后的情况为例子)

3.实现思路:

(1)数组的序号代表列,数组arr[x]=y代表第x列的皇后在第y行

(2)递归的时候以列作为参数,每到一个列的时候,遍历0-7每一行,如果有一个位置可行,就沿着这个情况继续递归,当递归结束返回这里的时候,在这一列继续往下找可行的点;

(3)递归结束的条件为当前找到的点就是最后一列,就输出这个图

4.代码实现如下

//n皇后问题
//n皇后问题的原理很简单貌似,其实就是
//这里举个例子,8皇后问题
int  arr[8];
void graph() {
	for (int i = 0; i <= 7; i++) {
		for (int j = 0; j <= 7; j++) {
			if (arr[j] == i) {
				cout << "";
			}
			else {
				cout << "<->";
			}
		}
		cout << endl;
	}
}
//攻击问题的验证方法:
//如果和之前列的某个皇后行数相同
//或者在对角线上(行列差的绝对值相等就是在对角线上)
bool attack(int x,int y) {//x为列数,y为行数
	for (int i = 0; i < x; i++) {
		int offx = abs(i-x);
		int offy = abs(arr[i] - y);
		if (offx == offy || offy == 0) {
			return true;
		}
	}
	return false;
}
//n皇后问题的回溯原理:
//每一列的每一行都尝试一次,如果整个点不被攻击,就往下一行递归
//如果已经是第七列了,则每确定一个点,就可以打印一次
void nQueen(int x) {
	for (int i = 0; i <= 7; i++) {
		if (!attack(x,i)) {
			arr[x] = i;
			if (x == 7) {
				graph();
				system("pause");
			}
			else {
				nQueen(x + 1);
			}
		}
	}
}