|
大小: 1025
|
大小: 1164
|
| 删除的内容标记成这样。 |
加入的内容标记成这样。 |
| 行号 36: |
行号 36: |
|
查找成功时的平均查找长度：(n+1)/2
查找不成功时的平均查找长度：n
|
| 行号 54: |
行号 59: |
|
查找成功时的平均查找长度
|
查找
1. 概念
平均查找长度：
查找成功时的平均查找长度：
2. 线性结构的查找
查找结构：
1 typedef int key_type;
2 typedef struct{
3 key_type key;
4 info_type otherinfo;
5 }record_type;
6 typedef record_type elem_type;
7 typedef struct {
8 elem_type elem[MAXSIZE];
9 int size;
10 }seq_list;
2.1. 顺序查找
1 int seq_search(seq_list *r, key_type 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, key_type 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. 树型结构查找
4. 哈希表
查找 (2008-02-23 15:35:52由localhost编辑)