版本1和5间的区别 (跳过第4版)

查找

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. 概念

2. 线性结构的查找

2.1. 顺序查找

2.2. 折半查找

3. 树型结构查找

3.1. 二叉排序树

4. 哈希表

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

== 概念 ==

平均查找长度：

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

== 线性结构的查找 ==

查找结构：

{{{#!cplusplus
typedef struct{ 
    int 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, int key) {
   int i;
   for(i = 0; i < r->size; i++)
      if(r->elem[i].key == key)
         return i;
   return -1;
}
}}}

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

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

=== 折半查找 ===
折半查找要求元素先排序
{{{#!cplusplus
int bin_search(seq_list *r, int 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;
}
}}}

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

== 树型结构查找 ==

=== 二叉排序树 ===

二叉排序树是一棵空二叉树或者满足以下条件的二叉树：
 * 左子树为空树或者左子树上所有结点的值小于根结点的值；
 * 右子树为空树或者右子树上所有结点的值大于根结点的值；
 * 左子树和右子树也是二叉排序树。

二叉排序树表示

{{{#!cplusplus
typedef struct datatype {
   int key;
}datatype;
struct node {
   datatype data;
   struct node *left, *right;
};
}}}

二叉排序树的插入
{{{#!cplusplus
struct node *insert_bst(struct node *root, datatype elem){
    if(root == NULL) {
        root = malloc(sizeof(struct node));
        root->data = elem;
        root->left = root->right = NULL;
        return root;
    }
    if(root->data.key < elem.key)
        root->right = insert_bst(root->right, elem);
    else if(root->data.key > elem.key)
        root->left = insert_bst(root->left, elem);
}
}}}

== 哈希表 ==