data-structure———查找

注意一下有一个概念：平均查找长度：ASL

顺序查找：
举例如果从一个无序数组a（数组下标从1开始）中找到值为k的元素，查找成功就返回1，不成功就返回0，采用顺序查找的话：

1
2
3
4
5
6
7
8
int Search(int a[] ,int n ,int k)
{
	int i ;
	for(i=1;i<=n;i++)
		if(a[i]==k)
			return 	1;
		return 0;
}

以上是使用顺序表的时候的情况，下面再看一下链式结构的情况：

1
2
3
4
5
6
7
8
9
10
11
LNode* search(LNode* head,int key)
{
	LNode* p = head->next;
	while(p!=NULL)
	{
		if(p->data==key)
			return p;
		p=p->next; //注意一下
	}
	return 0;  //注意一下这个没有找到所要值得情况的位置
}

一个是使用循环递增i数组下标，还有一个是使用p=p->next，一个一个的顺序访问。
折半查找：
折半查找的要求是表中记录是按关键字有序的。用到的是递归的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Bsearch(int R[],int low,int high,int k)
{
	int mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(R[mid]==k)
			return mid;
		else if(R[mid]>k)
			high=mid-1;
		else if(R[mid]<k)
			low=mid+1;
	}
	return 0;
}

这里的low，high，mid是下标，不是值的大小

分块查找：

索引表：

1
2
3
4
5
6
7
8
typedef struct //索引表结构体
{
	int key;  //存放这个表中的最大的关键字
	int low,high; //存放这个块中的第一个和最后一个元素的位置

}indexElem;

indexElem index[maxsize]; //定义索引表

查找过程是先使用二分查找法找到带查找元素在哪一个块中，然后在块中使用顺序查找就好，因为在一个块中的元素的个数就已经很少了。

二叉排序树和平衡二叉树：

二叉排序树的定义：

  1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

  2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

  3. 它的左、右子树也分别为二叉排序树。

二叉排序树的存储结构：采用二叉链表存储

1
2
3
4
5
6
typedef struct BTNode
{
	int key;
	struct BTNode *rchild;
	struct BTNode *lchild;
}BTNode;

二叉排序树中查找关键字的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BTNode *BSTSearch(BTNode *bt,int key)
{
	if(bt==NULL)
		return NULL;
	else
	{
		if(bt->key==key)
			return bt;
		else if(key<bt->key)
			return BSTSearch(bt->lChild,key);
		else if(key>bt->key)  
			return BSTSearch(bt->rchild,key);
	}
}

可以看到这里的查找的过程和折半查找的过程非常相似，其实，实质上折半查找（判定树是二叉排序树）就是二叉排序树的查找过程。

二叉树的插入关键字的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int BSTInsert(BTNode *&bt,int key)
{
	if(bt==NULL) //对应的是空树的情况
	{
		bt=(BTNode *)malloc(sizeof(BTNode));
		bt->rchild=NULL;
		bt->lchild=NULL;
		bt->key=key;
		return 1;
	}
	else
	{
		if(bt->key==key) //对应的是待插入的值已经在树中
			return 0;
		else if(bt->key>key) //这里往后就很像查找算法
			return BSTInsert(lchild,key);
		else
			return BSTInsert(rChild,key);
	}
}

不管什么情况，插入关键字都是在新创建的结点上，最后的递归处理对应的是，找到合适的插入的位置，一层一层的递归，最后还是会创建新结点，将要插入的值插入到新创建的结点处。

二叉树的构造算法：
假设所要构造的值都已经存储在了数组中

1
2
3
4
5
6
7
void CreateBST(BTNode *&bt,int key[],int n)
{
	int i;
	bt=NULL; //将树置空
	for(i=0,i<n,i++)
		BSTInsert(bt,key[i]);
}

这里使用了上面的插入算法。