【数据结构】查找算法

/有序表的折半查找/

输入：第一行包括两个数，查找范围的大小n，以及要查找元素的个数m
第二行是n个元素，表示查找范围内的元素
第三行是m个元素，表示要查找的元素
输出：能找到则输出位置，不能找到则输出-1

#include
#include
int zheban(int a[],int n,int m)
{
	int low=0;
	int high=n-1;
	int mid;
	while(low<=high)
	{
		mid=low+(high-low)/2;
		if(m==a[mid])
			return mid;
		else if(m
	int n,m;
	scanf("%d%d",&n,&m);
	int *num1,num2;
	num1=(int *)malloc(n*sizeof(int));
	int i;
	for(i=0;i
		scanf("%d",&num2);
		printf("%d ",zheban(num1,n,num2));
	}
	return 0;
}

/平衡二叉树/

包括ll型节点的调整，rr型节点的调整，节点插入函数，平衡二叉树查找函数。
请按照提示输入。

#include
#include
typedef struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
}BTNode;
int height(struct Node *N)
{//获取当前树的高度 
    if(N==NULL)
        return 0;
    return N->height;
}int max(int a,int b)
{
    if(a>b)
		return a;
	return b; 
}
int getnodeheight(struct Node *N)
{
	return max(height(N->left),height(N->right))+1;
}
BTNode* newNode(int key)
{//新建第一个节点 
    struct Node* node=(BTNode*)malloc(sizeof(struct Node));
    node->key=key;
    node->left=NULL;
    node->right=NULL;
    node->height=1;
    return node;
}
BTNode* ll_rotate(BTNode* p)
{
    BTNode *q =p->left;
    p->left=q->right;
    q->right=p;
    p->height=getnodeheight(p);
    q->height=getnodeheight(q);
    return q;
}//ll型调整 
    
BTNode* rr_rotate(BTNode* p)
{
    BTNode *q=p->right;
    p->right=q->left;
    q->left=p;
    p->height=getnodeheight(p);
    q->height=getnodeheight(q);
    return q;
}//rr型调整
    
int getBalance(BTNode* N)
{
    if(N==NULL)
        return 0;
    return height(N->left)-height(N->right);
}//用于判断树是否是哪种类型 
BTNode* insert(BTNode* node,int key)
{
    if(node==NULL)
        return newNode(key);
    if(keykey)
        node->left=insert(node->left,key);
    else if(key>node->key)
        node->right=insert(node->right,key);
    
    node->height=getnodeheight(node);
    
    int b=getBalance(node);
    if(b>1&&keyleft->key)//ll型
        return ll_rotate(node);
    if(b>1&&key>node->left->key)//lr型
    {
        node->left=rr_rotate(node->left);
        return ll_rotate(node);
    }

    if(b<-1&&key>node->right->key)//rr型
        return rr_rotate(node);
    if(b<-1&&keyright->key)//rl型
    {
        node->right=ll_rotate(node->right);
        return rr_rotate(node);
    }

    return node;
}//插入节点 
void preOrder(struct Node *root)
{
    if (root!= NULL)
    {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}
void inorder(struct Node *root)
{
	if(root!=NULL)
	{
		inorder(root->left);
		printf("%d ",root->key);
		inorder(root->right);
	}
}
int searchBTtree(int n,struct Node *p)
{
	while(p!=NULL)
	{
		if(p->key==n)
			return 1;
		else if(p->key>n)
			p=p->left;
		else if(p->keyright;
	}
	return 0;
}
int main()
{
    BTNode *root=NULL;
    printf("请输入关键字的个数：");
    int n;
    scanf("%d",&n);
	int *a=(int *)malloc(n*sizeof(int));
	int i;
	printf("请输入："); 
	for(i=0;i
		scanf("%d",&a[i]);
		root=insert(root,a[i]);
	}
    printf("前序遍历：n");
    preOrder(root);
    printf("n");
    printf("中序遍历：n");
    inorder(root);
    printf("n请输入您要查找的数：");
    int an;
    scanf("%d",&an);
    if(searchBTtree(an,root)==1)
	{
		printf("OK");
		return 0;
	}
	printf("NO");
	return 0;
}

/哈希表查找/

此程序定义的哈希表长度为10

输入：10个关键字

输出：第一行按哈希表存储的顺序输出10关键字

再输入：要查找的关键字

输出：元素在哈希表中的位置；
如果没有则输出“元素不存在”

#include  
#include 
#define HASHSIZE 10//定义哈希表长度   除留取余法 
#define NULLKEY -32768
typedef struct
{
	int *elem;
	int count;
}HashTable;  
void Init(HashTable *H)
{//初始化哈希表 
	int i;
	H->elem=(int *)malloc(HASHSIZE*sizeof(int));
	H->count=HASHSIZE;
	for(i=0;i
		H->elem[i]=NULLKEY;
	}
}
int Hash(int k)
{//除留余数法找哈希地址 
	return k%HASHSIZE;
}
void Insert(HashTable *H, int k)
{//将元素插入哈希表 
	int addr=Hash(k); 					 
	while(H->elem[addr]!= NULLKEY)
	{
		addr=(addr+1)%HASHSIZE;//开放定址法处理冲突 
	}
	H->elem[addr]=k;
}
int Search(HashTable *H, int k)
{
	int addr=Hash(k);//求哈希地址		
	while(H->elem[addr]!=k)
	{//开放定址法解决冲突
		addr=(addr+1)%HASHSIZE;
		if(H->elem[addr]==NULLKEY||addr==Hash(k))//找到了空或者找了一圈没找到 
			return -1;
	}
	return addr;
}
void Show(HashTable *H)
{//散列表元素显示
	int i;
	for(i=0;icount;i++)
	{
		printf("%d ",H->elem[i]);
	}
	printf("n");
}
int main()
{
	int i,e,addr;
	HashTable H;
	Init(&H);
	int a; 
	for(i=0;i
		scanf("%d",&a);
		Insert(&H,a);
	}
	Show(&H);
	scanf("%d",&e);
	addr=Search(&H,e);
	if(addr==-1)
		printf("元素不存在n");
	else
		printf("元素在表中的位置是:%dn",addr);
}

/二叉排序树的建立插入和查找/
输入
输入的第一行包含2个正整数n和k，分别表示共有n个整数和k次查询。第二行包含n个用空格隔开的正整数，表示n个整数。 第三行包含k个用空格隔开的正整数，表示k次查询的目标。

输出
只有1行，包含k个整数，分别表示每一次的查询结果。如果在查询中找到了对应的整数，则输出1，否则输出0。

#include 
#include 
#define FALSE 0
#define TRUE 1
typedef struct treenode
{
    struct treenode *left;
    int data;
    struct treenode *right;
}BiTreenode, *BiTreep;
typedef struct node
{
	int val;
	struct node *lson,*rson;
}*lnode;
void createBST(lnode &T,int a[],int n,int i)
{
	if(i==n)
		return;
	T=new node;
	T->val=a[i];
	printf("%d ",T->val);
	T->lson=NULL;
	T->rson=NULL;
	i++;
	if(a[i]val)
		createBST(T->lson,a,n,i);
	else
		createBST(T->rson,a,n,i);
}
int searchBST(lnode T,int key)
{
	if(T==NULL)
	{
		return 0;
	}
	if(T->val==key)
	{
		return 1;
	}
	else if(T->vallson,key);
	else 
		searchBST(T->rson,key);
}
void inorder(lnode T)
{
    if(T!=NULL)
	{
		inorder(T->lson);
		printf("%c",T->val);
		inorder(T->rson);
	}
}//中序遍历
int SearchBST(BiTreep &rt, int key, BiTreep father, BiTreep &p)
{
    if(!rt)            //查找不成功
    {
        p=father;
        return FALSE;
    }
    else if(key==rt->data)        //查找成功
    {
        p=rt;
        return TRUE;
    }
    else if(keydata)
        return SearchBST(rt->left,key,rt,p);    //在左子树中继续查找
    else
        return SearchBST(rt->right,key,rt,p);    //在右子树中继续查找
}
//创建二叉树
int InsertBST(BiTreep &rt, int key)
{
    //当二叉排序树T中不存在关键字等于key的数据元素时，插入e并返回TRUE，否则返回FALSE
    BiTreep p,s;
    if(!SearchBST(rt,key,NULL,p))//查找不成功 
    {
        s = (BiTreep)malloc(sizeof(BiTreenode));
        s->data=key;
        s->left=s->right=NULL;
        if(!p)
            rt=s;    //被插的树还是空树，被插节点s做为根节点
        else if(keydata)
            p->left=s;        //被插节点s为左孩子
        else
            p->right=s;        //被插节点s为右孩子
        return TRUE;
    }
    else
        return FALSE;        //树中已有关键字相同的节点，不再插入
}//InsertBST
int seach_tree(BiTreep &rt,int key)
{
    if(rt==NULL)
        return FALSE;
    else
    {
        if(rt->data==key)
            return TRUE;
        else if(keydata)
            return seach_tree(rt->left,key);
        else
            return seach_tree(rt->right,key);
    }
}

int main()
{
    BiTreep root=NULL; 
	int n,m,*a;
	scanf("%d%d",&n,&m);
	a=(int *)malloc(n*sizeof(int));
	int i;
	for(i=0;i
		scanf("%d",&a[i]);
		InsertBST(root,a[i]);
	}
    int key;
    for(i=0;i
	    scanf("%d",&key);
	    if(seach_tree(root,key)==1)
	        printf("1 ");
	    else
	        printf("0 ");
	}
    return 0;
}