查找
1. 概念
平均查找长度：
查找成功时的平均查找长度：
2. 线性结构的查找
查找结构：
1 typedef struct{
2 int key;
3 info_type otherinfo;
4 }record_type;
5 typedef record_type elem_type;
6 typedef struct {
7 elem_type elem[MAXSIZE];
8 int size;
9 }seq_list;
2.1. 顺序查找
1 int seq_search(seq_list *r, int key) {
2 int i;
3 for(i = 0; i < r->size; i++)
4 if(r->elem[i].key == key)
5 return i;
6 return -1;
7 }
查找成功时的平均查找长度：(n+1)/2
查找不成功时的平均查找长度：n
2.2. 折半查找
折半查找要求元素先排序
1 int bin_search(seq_list *r, int key) {
2 int low = 0, high = r->size;
3 while(low < high) {
4 int mid = (low + high) / 2;
5 if(r->elem[mid].key == key)
6 return mid;
7 else if(r->elem[mid].key < key)
8 low = mid + 1;
9 else
10 high = mid;
11 }
12 return -1;
13 }
查找成功时的平均查找长度
3. 树型结构查找
3.1. 二叉排序树
二叉排序树是一棵空二叉树或者满足以下条件的二叉树：
- 左子树为空树或者左子树上所有结点的值小于根结点的值；
- 右子树为空树或者右子树上所有结点的值大于根结点的值；
- 左子树和右子树也是二叉排序树。
二叉排序树表示
1 typedef struct datatype {
2 int key;
3 }datatype;
4 struct node {
5 datatype data;
6 struct node *left, *right;
7 };
二叉排序树的插入
1 struct node *insert_bst(struct node *root, datatype elem){
2 if(root == NULL) {
3 root = malloc(sizeof(struct node));
4 root->data = elem;
5 root->left = root->right = NULL;
6 return root;
7 }
8 if(root->data.key < elem.key)
9 root->right = insert_bst(root->right, elem);
10 else if(root->data.key > elem.key)
11 root->left = insert_bst(root->left, elem);
12 }
二叉排序树的查找
1 struct node *search(struct node *root, int key) {
2 if(root == NULL)
3 return NULL;
4 else if(root->data.key < key)
5 return search(root->right, key);
6 else
7 return search(root->left, key);
8 }
4. 哈希表