目录

1.查找

1.查找的基本概念

1.在哪里找？

 2.什么查找？

3.查找成功与否？ 

4.查找的目的是什么？ 

5.查找表怎么分类？ 

6.如何评价查找算法？ 

7.查找的过程中我们要研究什么？ 

2.线性表的查找 

1.顺序查找 

代码示例：

 1.顺序查找的改进

代码示例：

2.顺序查找的性能分析与特点 

2.折半查找 

代码示例：

1.折半查找的性能分析与特点 

3.分块查找（索引顺序查找） 

1.分块查找性能分析与优缺点 

3.树表的查找 

1.二叉排序树 

1.二叉排序树的存储结构

代码示例：

2.二叉排序树的递归查找 

代码示例： 

3.二叉排序树的查找分析 

平衡二叉树 

4.二叉排序数的操作-插入 

5.二叉排序树的操作-删除 

4.总的代码

1.查找

1.查找的基本概念

1.在哪里找？

 2.什么查找？

3.查找成功与否？ 

4.查找的目的是什么？ 

5.查找表怎么分类？ 

6.如何评价查找算法？ 

7.查找的过程中我们要研究什么？ 

2.线性表的查找 

1.顺序查找 

代码示例：

typedef struct { 	int key; }elem;  typedef struct { 	elem *r; 	int len; }sstable;  sstable st;  int search_seq(sstable st,int key) { 	for(int i = st.len; i >= 1; --i) { 		if(st.r[i].key == key) return i; 		return 0; 	} }

 1.顺序查找的改进

代码示例：

int Search_seq(sstable st,int key) { 	st.r[0].key = key;     int i; 	for(i = st.len; st.r[i].key != key; --i); 	return i; }

2.顺序查找的性能分析与特点 

2.折半查找 

代码示例：

int search_bin(sstable st,int key) { 	int low = 1; 	int high = st.len; 	while(low <= high) { 		int mid = (low + high) / 2; 		if(st.r[mid].key == key) return mid; 		else if(key < st.r[mid].key) 			high = mid - 1; 		else low = mid + 1; 	} 	return 0; }

1.折半查找的性能分析与特点 

3.分块查找（索引顺序查找） 

1.分块查找性能分析与优缺点 

3.树表的查找 

1.二叉排序树 

1.二叉排序树的存储结构

代码示例：

typedef struct { 	int key; }elemtype;  typedef struct bstnode { 	elemtype data; 	struct bstnode *lchild, *rchild; }bstnode,*bstree;  bstree t;

2.二叉排序树的递归查找 

代码示例： 

bstree searchbst(bstree t,int key) { 	if((!t) || key == t -> data.key) return t; 	else if(key < t -> data.key) 		return searchbst(t -> lchild,key); 	else return searchbst(t -> rchild,key); }

3.二叉排序树的查找分析 

平衡二叉树 

4.二叉排序数的操作-插入 

5.二叉排序树的操作-删除 

4.总的代码

#include using namespace std;  typedef struct { 	int key; }elem;  typedef struct { 	elem *r; 	int len; }sstable;  sstable st;  int search_seq(sstable st,int key) { 	for(int i = st.len; i >= 1; --i) { 		if(st.r[i].key == key) return i; 		return 0; 	} }  int Search_seq(sstable st,int key) { 	st.r[0].key = key; 	int i; 	for(i = st.len; st.r[i].key != key; --i); 	return i; }  int search_bin(sstable st,int key) { 	int low = 1; 	int high = st.len; 	while(low <= high) { 		int mid = (low + high) / 2; 		if(st.r[mid].key == key) return mid; 		else if(key < st.r[mid].key) 			high = mid - 1; 		else low = mid + 1; 	} 	return 0; }  typedef struct { 	int key; }elemtype;  typedef struct bstnode { 	elemtype data; 	struct bstnode *lchild, *rchild; }bstnode,*bstree;  bstree t;  bstree searchbst(bstree t,int key) { 	if((!t) || key == t -> data.key) return t; 	else if(key < t -> data.key) 		return searchbst(t -> lchild,key); 	else return searchbst(t -> rchild,key); }  int main() { 	 	return 0; }