版本7和8间的区别

查找

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 }

二叉排序树的删除结点

3.2. 二叉排序树的平衡

AVL平衡

LL旋转
RR旋转
LR旋转
RL旋转

红黑平衡

-  ⇤ ← 于2006-06-05 19:26:38修订的的版本7 → 
  大小: 2469
  编辑: czk
  备注:
+   ← 于2006-06-12 20:24:01修订的的版本8 → ⇥
  大小: 2521
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 114:
+ * LL旋转
 * RR旋转
 * LR旋转
 * RL旋转

"查找"版本比较

查找

1. 概念

2. 线性结构的查找

2.1. 顺序查找

2.2. 折半查找

3. 树型结构查找

3.1. 二叉排序树

3.2. 二叉排序树的平衡

3.3. B树

4. 哈希表