tubao.cpp

此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,并实现了平衡二叉树中的结点删除 Boyer_Moore算法的串模式匹配 Horspool算法的串模式匹配 Grap

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

static int x[10]={-2,-1,0,1,2,3,4,3,2,0};//x横坐标 
static int y[10]={0,3,2,3,4,2,0,-2,-1,-2};//y纵坐标
static int type[10]={0,0,0,0,0,0,0,0,0,0};//各个点的初始状态，初始值均为0.
                     //将经过测试之后能进入凸包的type=1,不能进凸包的type=-1


int comput(int x1,int x2,int x3,int y1,int y2,int y3){
	//计算行列式的值(包括符号),需传递三个点的坐标信息
		 
		 int result; //存放行列式的计算结果
		 result=x1*y2+x3*y1+x2*y3-x3*y2-x2*y1-x1*y3;
		 return result;	 
}

int count_type(){
		 //返回type里为0的元素个数
		int i=0;
		for(int j=0;j<10;j++){
			if(type[j]==0) i++;
		}
//	printf("go count_type %d\n",i);
		 return i;
}

int dis_max(int a,int b){//对上包中求距离线段最大的点的下标
		//a:第一个点的下标，b:第二个点的下标；
		//下标a,b端点构成线段line,返回到距离线段line最大的点（x,y）的下标
	    //并把该点的状态type元素设置为1

		int dis=0;    //dis中存储最大距离
		int dis_id=-1;//返回距离最大的点的下标,初始值表示未找到
		if(a!=-1&&b!=-1){//当a,b有效时查找
		for(int i=0;i<10;i++){
			if(type[i]==0){
				//对不在凸包里的点进行判断	
				int rs=comput(x[a],x[b],x[i],y[a],y[b],y[i]);//计算行列式的值
				
				if(rs<0&&y[i]>0){//rs<0,表示以i为下标的点在线段右侧
					//对于处于上包，并且在右边,不能放进凸包的点设置为-1
					type[i]=-1;
					printf("point %d rejected!\n",i);
				}				
				else if(rs>0&&rs>dis){	//对线段左侧中距离大于最大距离dis时,修改dis的值
					dis=rs;
					dis_id=i;
				}
				
			}
		}
	}
		if(dis_id>0)
		{
			type[dis_id]=1; //距离最大的点的状态type元素设置为1
		    printf("point %d permitted\n",dis_id);
		}
		return dis_id;
}

int dis_max2(int a,int b){//对下包中求距离线段最大的点的下标		

		int dis=0;    //dis中存储最大距离
		int dis_id=-1;//返回距离最大的点的下标,初始值表示未找到
		if(a!=-1&&b!=-1){//当a,b有效时查找
		for(int i=0;i<10;i++){
			if(type[i]==0){
				//对不在凸包里的点进行判断	
				int rs=comput(x[a],x[b],x[i],y[a],y[b],y[i]);//计算行列式的值
				
				if(rs>0&&y[i]<0){//rs>0,表示以i为下标的点在线段左侧
					//对于处于下包，并且在左边,不能放进凸包的点设置为-1
					type[i]=-1;
					printf("point %d rejected!\n",i);
				}
				else if(rs<0&&-rs>dis){	
					dis=-rs;
					dis_id=i;
				}				
			}
		}
	}
		if(dis_id>0)
		{
			type[dis_id]=1;//距离最大的点的状态type元素设置为1
		    printf("point %d permitted\n",dis_id);
		}
		return dis_id;
}

void testup(int a,int b){//构造上包
	
//	 printf("go testup\n");
		int test_id=dis_max(a,b);//求距离线段距离最大的点的下标值
		if(count_type()>0){
			if(test_id>0){
				testup(a,test_id);//递归构造上包
				testup(test_id,b);
			}
		}
}

void testdown(int a,int b){//构造下包
		
		int test_id=dis_max2(a,b); //求距离线段距离最大的点的下标值
		if(count_type()>0){
			if(test_id>0){
				testdown(a,test_id);//递归构造下包
				testdown(test_id,b);
			}
		}
}
void main() {
	
//递归找出集合的凸包（包括上包和下包）
		
	    //x坐标最左边和最右边的点一定包含在凸包内
		type[0]=type[6]=1;	
		printf("point 0 permitted\n");
		printf("point 6 permitted\n");
		//下面是构造出上包,//以x坐标最左边和最右边的点开始构造
		testup(0, 6);
		//下面是构造出下包,主要是针对纵坐标为负的值
	    printf("======================\n");
		testdown(0,6);
		printf("======================\n");
		printf("最后构成凸包的点有：\n");
		for(int i=0;i<10;i++)
			if(type[i]==1)
				printf("%3d",i);
		printf("\n");

		system("PAUSE");


	}