常见的查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
	 *  在s[0]-s[n-1]中顺序查找关键字为Key的记录 ,查找成功时返回该记录的下标序号；失败时返回-1  
	 */
	int SequelSearch(elemtype s[], keytype Key, int n){
		int i;
		i = 0;
		while (i < n && s[i].Key != Key)
			i++;

		if (s[i].Key == Key)
			return i;
		else
			return -1;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
	 * 在下届为low，上界为high的数组a中折半查找数据元素x
	 */
	int binarySearch(elemtype a[], elemtype x, int low, int high) {
		int mid;
		if (low > high)
			return -1;
		mid = (low + high) / 2;
		if (x == a[mid])
			return mid;
		if (x < a[mid])
			return (binarySearch(a, x, low, mid - 1));
		else
			return (binarySearch(a, x, mid + 1, high));
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(elemtype a[], keytype key, int n) {
		int low, high, mid;
		low = 0;
		high = n - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (a[mid].key == key)
				return mid;
			else if (a[mid].key < key)
				low = mid + 1;
			else
				high = mid - 1;
		}
		return -1;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef int keytype;

	typedef struct {
		keytype Key;
	}elemtype;

	typedef struct{
		keytype Key;
		int Link;
	}indextype;

	/**
	 * 分块查找关键字为Key的记录。索引表为ls[0]-ls[m-1],顺序表为s，块长为l
	 */
	int IndexSequelSearch(indextype ls[],elemtypes[],int m,int l,keytype Key){
		int i,j;
		/*在索引表中顺序查找*/
		i=0;
		while(i<m&&Key>ls[i].Key)i++;
	
		if(i>=m)
			return -1;
		else{
		    /*在顺序表中顺序查找*/
		    j=ls[i].Links;
		    while(Key!=s[j].Key&&j-ls[i].Link<l)
		    	j++;
	
		    if(Key==s[j].Key)
		    	return j;
		    else 
		    	return -1; 
		}
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
btree *search(btree *b,int x){
		/*在二叉树b中查找x的过程*/
		if(b=NULL) 
			return(NULL);
	
		else{
		     if(b->data==x) 
		    	 return(b);
		     if(x<b->data) 
		    	 return(search(b->left));
		     else 
		    	 return(search(b->right));
		} 
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bsnodetype *Search(bsnodetype *bt,keytype Key){
		/*在二叉树bt中查找元素为Key的元素*/
		bsnodetype *p;
		if(bt==NULL) 
			return(bt);

		p=bt;
		while(p->Key!=Key){
		    if(Key<p->Key) 
		    	p=p->Lchild;
		    else 
		    	p=p->Rchild;
		    if(p==NULL)
		    	break;
		}
		return(p);
	}

1
2
3
4
5
6
7
8
9
10
11
12
void insert(b,s){
		btree *b,*s;
		
		if(b==NULL) 
			b=s;
		else if(s->data==b->data) 
		       return();
		else if(s->data<b->data)
		       insert(b->left,s);
		else if(s->data>b->data)
		       insert(b->right,s);
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void create(btree *b){
		int x;
		btree 8s;
		b==NULL;
	
		do{
		   scanf("%d",&x);
		   s=(bnode *)malloc(sizeof(bnode));
		   s->data=x;
		   s->left=NULL;
		   s->right=NULL;
		   insert(b,s); 
		}while(x!=-1);
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bsnodetype *Delete(bsnodetype *bt,keytype Key){/*在bt为根结点的二叉树中删除值为Key的结点*/
		
		bsnodetype *p,*q;
		if(bt->Key==Key){
		    /*bt的左右子树均为空*/
		    if(bt->Lchild==NULL&&bt->Rchild==NULL){
		       free(bt); /*删除叶结点*/
		       return(NULL);
		    }else if(bt->Lchild==NULL){ /*bt的左子树为空*/
		       p=bt->Rchild;
		       free(bt);
		       return(p);
		    }else if(bt->Rchild==NULL){/*bt的右子树为空*/
		       p=bt->Lchild;
		       free(bt);
		       return(p); 
		    }else{
		       p=q=bt->Rchild;
		       while(p->Lchild!=NULL)
		    	   p=p->Lchild;
		       p->Lchild=bt->Lchild;
		       free(bt);
		       return(q);
		    }
		}
	
		/*在bt->Lchild为根结点的二叉树中删除值为Key的结点*/
		if(bt->Key>Key&&bt->Lchild!=NULL)
		   bt->Lchild=Delete(bt->Lchild,Key);
	
		/*在bt->Rchild为根结点的二叉树中删除值为Key的结点*/
		if(bt->Key<Key&&bt->Rchild!=NULL)
		   bt->Rchild=Delete(bt->Rchild,Key);
	
		return(bt);
	}