版本2和4间的区别 (跳过第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 }

查找成功时的平均查找长度：(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 }

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

"查找"版本比较

查找

1. 概念

2. 线性结构的查找

2.1. 顺序查找

2.2. 折半查找

3. 树型结构查找

4. 哈希表

-  ⇤ ← 于2006-06-05 17:17:46修订的的版本2 → 
  大小: 179
  编辑: czk
  备注:
+   ← 于2006-06-05 18:13:05修订的的版本4 → ⇥
  大小: 1164
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 7:
+查找成功时的平均查找长度：
-行号 9:
+行号 11:
+查找结构：

{{{#!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;
}}}
-行号 10:
+行号 27:
+{{{#!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;
}
}}}

查找成功时的平均查找长度：(n+1)/2

查找不成功时的平均查找长度：n
-行号 12:
+行号 42:
+折半查找要求元素先排序
{{{#!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;
}
}}}

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