跳到主要内容

搜索算法

【仍在更新中，尚未完成】

顺序搜索​

顺序搜索是运用枚举法的思想。

顺序搜索法 (Linear Search)从搜索表的一端开始顺序扫描，依次将搜索表中的结点关键字和键值进行比较，若两者相等，则搜索成功；若扫描结束后，还没有找到与键值相等的关键字，则搜索失败。

算法​

采用for循环进行遍历

void LinearSearch(int* data, int key)
{
	int flag = 0;//flag=0表示搜索失败
	for (int i = 0; i < n; i++)
		if (data[i] == key)//判断搜索是否成功
		{
			cout << "在第" << i << "个位置,找到" << key << endl;
			flag = 1;//标志成功
		}
	if (flag == 0)//如果搜索失败
		cout << "没有找到" << key << endl;
}

二分搜索​

二分搜索法(Binary Search)只适用于搜索数据已被排序的情况。假设搜索数据是升序的，二分搜索法是将数据分成两等份，再比较键值与中间值的大小，如果键值小于中间值，可确定要搜索的数据为前半部分，否则为后半部分。如此进行下去，直到搜索成功或搜索不成功为止。

算法​

void BinarySearch(int *data,int key,int n)
{	int z,mid,y,flag;//左中右下标,标识变量
	z=0;y=n-1;
	if(key<data[z]||key>data[y])
	{	cout<<"键值超界,无法找到"<<key<<endl;
		return;//什么都不做
	}
	flag=0;//假设未搜索到key
	while(z<=y)
	{	mid=(z+y)/2;//两分
		if(key<data[mid])
		{	y=mid-1;
			if(z<=y)
				cout<<"搜索左半部分,下标"
					<<setw(2)<<z<<setw(2)<<"-"<<setw(2)<<y<<endl;
			else
				break;
		}
		else if(key>data[mid])
		{	z=mid+1;
			if(z<=y)
				cout<<"搜索右半部分,下标"
					<<setw(2)<<z<<setw(2)<<"-"<<setw(2)<<y<<endl;
			else
				break;
		}
		else
		{	cout<<"在第 "<<mid<<" 个位置,搜索到"<<key<<endl;
			flag=1;//搜索到key
			break;
		}
	}
	if(flag==0)
		cout<<"没有搜索到"<<key<<endl;
}

二叉搜索树​

二叉搜索树就是排序二叉树。在树的数据结构段中，函数Create()是通过逐个结点插入的方式来创建排序二叉树的。因此，可以将此函数看作是二叉搜索树的插入函数Insert()。向二叉搜索树中插入一个新元素，应保持二叉树仍为二叉搜索树。

搜索​

二叉搜索树的搜索算法使用while循环，从根结点开始搜索，将键值key与当前结点值进行比较。若key等于该结点的值，则搜索以成功而终止；若key小于该结点的值，则继续搜索左子树；否则继续搜索右子树。只有搜索到达空子树时，搜索以失败而终止。 搜索函数的代码如下：

void Search(BinTree T,int key)
{	Node *p=T.root;//定义探测指针p并指向根结点   
	while(p)//当p不指向空值时
	{	if(key==p->data)//如果键值等于父结点值
		{	cout<<"找到"<<key<<endl;//输出找到信息
			return;//什么都不做
		}
		else if(key<p->data)//如果键值小于父结点值
			p=p->lChild;//搜索左子树
		else if(key>p->data)//如果键值大于父结点值
			p=p->rChild;//搜索右子树
	}
	cout<<"没有找到"<<key<<endl;//输出未找到信息
}

删除​

二叉搜索树上删除一个结点，需保证删除后的二叉树仍然是二叉搜索树。为了讨论方便，假定被删除结点为p，其父结点为f。删除过程可按下述两种情况分别处理：

  1. 如果被删除的结点 没有左子树，则只需把结点f指向p的指针，改为指向p的右子树，然后，再删除结点p。
  2. 如果被删除的结点 有左子树，则从结点p的左子树中选择结点值最大的结点 （它就是 的左子树中最右下角的结点，该结点 可能有左子树，但一定无右子树(如果有右子树，说明s不是最大，矛盾)），把结点s的值复制到结点p中，再将指向s的指针改为指向结点s的左子树，然后，再删除结点s。

代码实现如下：

void Delete(BinTree T,int key)
{	Node *f,*p,*q,*s;
	p=T.root;f=NULL;//p指向根结点,f是p的双亲结点(直接前驱结点)
	//搜索值为key的结点p
	while(p&&p->data!=key)//当p不为空且p的值不等于键值时
	{	f=p;
		if(p->data>key)//如果p的值大于键值
			p=p->lChild;//p向左子树下移
		else//如果p的值不大于键值
			p=p->rChild;//p向右子树下移
	}
	if(p==NULL)//如果删除结点不存在
	{	cout<<"结点"<<key<<"不存在,无法删除"<<endl;
		return;//什么都不做
	}
	if(p->lChild==NULL)//如果删除结点没有左子树
	{	if(f==NULL)//如果删除结点为根结点
			T.root=p->rChild;//树根结点右移
		else if(f->lChild==p)//如果双亲结点的左孩子为删除结点
			f->lChild=p->rChild;
		else
			f->rChild=p->rChild;
		delete p;
	}
	else//如果删除结点有左子树
	{	q=p;s=p->lChild;
		while(s->rChild)
		{	q=s;
			s=s->rChild;
		}
		if(q==p)
			q->lChild=s->lChild;
		else
			q->rChild=s->lChild;
		p->data=s->data;
		delete s;
	}
}

算法​

#include<iostream>
using namespace std;
//二叉树结点定义
struct Node
{	int data;//数据域
	Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{	Node *root;};
//创建空二叉树
void Create(BinTree &T)
{	T.root=NULL;}
//判空
int IsEmpty(BinTree T)
{	if(T.root==NULL) return 1;
	else return 0;
}
//插入
void Insert(BinTree &T,int x)
{	Node *NewNode,*p;
	NewNode=new Node; //创建新结点
	NewNode->data=x;
	NewNode->lChild=NULL;
	NewNode->rChild=NULL;
	int flag=0;//新结点入树标识,flag=0表示未入树
	if(IsEmpty(T))//如果二叉树为空
		T.root=NewNode;
	else//如果二叉树非空
	{	p=T.root;//探测指针指向根结点
		while(!flag)//当新结点未入树时
		{	if(x<p->data)//如果新结点的值小于双亲结点的值
			{//进入左子树 
				if(p->lChild==NULL)//如果左子树为空		体会此处的选择结构
				{	p->lChild=NewNode;//新结点成为左子树
					flag=1;//新结点入树
				}
				else//如果左子树非空
					p=p->lChild;//探测指针向左下移
			}
			else//如果新结点的值大于双亲结点的值
			{  //进入右子树
				if(p->rChild==NULL)//如果右子树为空
				{	p->rChild=NewNode;//新结点成为右子树
					flag=1;//新结点入树
				}
				else
					p=p->rChild;//探测指针向右下移
			}
		}
	}
}
//前序遍历
void PreOrder(Node *p)
{	if(p!=NULL)
	{	cout<<p->data<<" ";//访问树根
		PreOrder(p->lChild);//遍历左子树
		PreOrder(p->rChild);//遍历右子树
	}
}
//中序遍历
void InOrder(Node *p)
{ if(p!=NULL)
	{	InOrder(p->lChild);//遍历左子树
		cout<<p->data<<" ";//访问树根
		InOrder(p->rChild);//遍历右子树
	}
}
//搜索
void Search(BinTree T,int key)
{	Node *p=T.root;//探测指针指向根结点
	while(p)//当p不指向空值时
	{		if(key==p->data)//如果键值等于父结点值
		{		cout<<"找到"<<key<<endl;//输出找到信息
			return;//什么都不做
		}
		else if(key<p->data)//如果键值小于父结点值
			p=p->lChild;//搜索左子树
		else if(key>p->data)//如果键值大于父结点值
			p=p->rChild;//搜索右子树
	}
	cout<<"没有找到"<<key<<endl;//输出未找到信息
}
//删除
void Delete(BinTree T,int key)
{	Node *f,*p,*q,*s;
	p=T.root;f=NULL;//p指向根结点,f是p的父结点(直接前驱结点)
	//搜索值为key的结点p
	while(p&&p->data!=key)//当p不为空且p的值不等于键值时
	{	f=p;
		if(p->data>key)//如果p的值大于键值
			p=p->lChild;//p向左子树下移
		else//如果p的值不大于键值
			p=p->rChild;//p向右子树下移
	}
	if(p==NULL)//如果删除结点不存在
	{	cout<<"结点"<<key<<"不存在,无法删除"<<endl;
		return;//什么都不做
	}
	if(p->lChild==NULL)//如果删除结点没有左子树
	{	if(f==NULL)//如果删除结点为根结点
			T.root=p->rChild;//树根结点右移
		else if(f->lChild==p)//如果父结点的左孩子为删除结点
			f->lChild=p->rChild;
		else
			f->rChild=p->rChild;
		delete p;
	}
	else//如果删除结点有左子树
	{	q=p;s=p->lChild;
		while(s->rChild)
		{	q=s;
			s=s->rChild;
		}
		if(q==p)
			q->lChild=s->lChild;
		else
			q->rChild=s->lChild;
		p->data=s->data;
		delete s;
	}
}
//主函数
int main()
{	int i,data[9]={9,3,12,2,5,11,16,8,18};
	BinTree T;//定义二叉树
	Create(T);//创建空二叉树
	for(i=0;i<9;i++)
		Insert(T,data[i]);//创建二叉搜索树	
	cout<<"前序遍历 ";PreOrder(T.root);cout<<endl;
	cout<<"中序遍历 ";InOrder(T.root);cout<<endl;
	Delete(T,3);Delete(T,4);Delete(T,11);//删除3,4,11
	cout<<"前序遍历 ";PreOrder(T.root);cout<<endl;
	cout<<"中序遍历 ";InOrder(T.root);cout<<endl;
	Insert(T,4);Insert(T,7);Insert(T,15);//插入4,7,15
	cout<<"前序遍历 ";PreOrder(T.root);cout<<endl;
	cout<<"中序遍历 ";InOrder(T.root);cout<<endl;
	Search(T,4);//搜索4
	return 0;
}

广度优先搜索算法​

概述​

广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。

广度优先搜索让你能够找出两样东西之间的最短距离,其中包括：

  1. 计算象棋，跳棋等最少获胜所需的步数
  2. 找到关系网中最近的目标
  3. 找到到达中心网关最近的链路

图​

图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为G(V,E)，其中，G标示一个图，V是图G中顶点的集合，E是图G中边的集合。

无边图：若顶点Vi到Vj之间的边没有方向，则称这条边为无项边（Edge），用序偶对(Vi,Vj)标示。

对于下图无向图G1来说，G1=(V1, {E1})，其中顶点集合V1={A,B,C,D}；边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}:

![image-20221031105851802](/Users/cat/Library/Application Support/typora-user-images/image-20221031105851802.png)

有向图：若从顶点Vi到Vj的边是有方向的，则成这条边为有向边，也称为弧（Arc）。用有序对（Vi，Vj）标示，Vi称为弧尾，Vj称为弧头。如果任意两条边之间都是有向的，则称该图为有向图。

有向图G2中，G2=（V2,{E2}），顶点集合（A,B,C,D）,弧集合E2={<A,D>,{B,A},<C,A>,<B,C>}.

权：有些图的边和弧有相关的数，这个数叫做权。这些带权的图通常称为网。