版本1和3间的区别 (跳过第2版)

查找

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 }

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 }

"查找"版本比较

查找

1. 概念

2. 线性结构的查找

2.1. 顺序查找

2.2. 折半查找

3. 树型结构查找

4. 哈希表

-  ⇤ ← 于2006-06-05 16:59:43修订的的版本1 → 
  大小: 25
  编辑: czk
  备注:
+   ← 于2006-06-05 18:02:19修订的的版本3 → ⇥
  大小: 1025
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 1:
-在这里详述 查找.
+= 查找 =

== 概念 ==

平均查找长度：

查找成功时的平均查找长度：

== 线性结构的查找 ==

查找结构：

{{{#!cplusplus
typedef int key_type;
typedef struct{ 
    key_type key;
    info_type otherinfo;
}record_type;
typedef record_type elem_type;
typedef struct  {
    elem_type  elem[MAXSIZE];
    int size;
}seq_list;
}}}

=== 顺序查找 ===
{{{#!cplusplus
int seq_search(seq_list *r, key_type key) {
   int i;
   for(i = 0; i < r->size; i++)
      if(r->elem[i].key == key)
         return i;
   return -1;
}
}}}
=== 折半查找 ===
折半查找要求元素先排序
{{{#!cplusplus
int bin_search(seq_list *r, key_type key) {
   int low = 0, high = r->size;
   while(low < high) {
      int mid = (low + high) / 2;
      if(r->elem[mid].key == key)
         return mid;
      else if(r->elem[mid].key < key)
         low = mid + 1;
      else
         high = mid;
   }
   return -1;
}
}}}

== 树型结构查找 ==

== 哈希表 ==