Icoding平台第七次作业解析-查找

T1

哈希表创建
哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。哈希表相关定义如下：

typedef enum{
HASH_OK,
HASH_ERROR,
HASH_ADDED,
HASH_REPLACED_VALUE,
HASH_ALREADY_ADDED,
HASH_DELETED,
HASH_NOT_FOUND,
} HASH_RESULT;

typedef struct __HashEntry HashEntry;
struct __HashEntry{
union{
char *str_value;
double dbl_value;
int int_value;
} key;
union{
char *str_value;
double dbl_value;
int int_value;
long long_value;
void *ptr_value;
} value;
HashEntry *next;
};

struct __HashTable{
HashEntry **bucket;
int size;
HASH_RESULT last_error;
};
typedef struct __HashTable HashTable;

// 创建大小为hash_size的哈希表，创建成功后返回HashTable类型的指针，否则返回NULL。
HashTable *create_hash(int hash_size);

当成功插入顶点或边时，函数返回true，否则（如顶点或边已存在、插入边时顶点v或w不存在）返回false。

哈希表相关说明：

HASH_RESULT 类型为相关函数的返回类型
HashEntry 为哈希表所保存元素（即键值对 《key, value》）类型
HashTable 为哈希表，其中 bucket 指向大小为size的、元素类型为 HashEntry*的指针数组
哈希表采用链地址法处理冲突

请实现 create_hash 函数，创建指定大小的哈希表。

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-06-22, Mon, 02:08:46
    * 最高分数：100
    */
   
   
   #include "hash.h"
   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   HashTable* create_hash(int size)
   {
       HashTable* H = (HashTable*)malloc(sizeof(HashTable));
       H->bucket = (HashEntry**)malloc(sizeof(HashEntry**) * size);
       if (!H->bucket) {
           free(H);
           return NULL;
       }
       memset(H, 0, sizeof(HashTable));
       H->size = size;
       return H;
   }

---

T2

哈希表添加

哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。哈希表相关定义如下：

typedef enum{
HASH_OK,
HASH_ERROR,
HASH_ADDED,
HASH_REPLACED_VALUE,
HASH_ALREADY_ADDED,
HASH_DELETED,
HASH_NOT_FOUND,
} HASH_RESULT;

typedef struct __HashEntry HashEntry;
struct __HashEntry{
union{
char *str_value;
double dbl_value;
int int_value;
} key;
union{
char *str_value;
double dbl_value;
int int_value;
long long_value;
void *ptr_value;
} value;
HashEntry *next;
};

struct __HashTable{
HashEntry **bucket;
int size;
HASH_RESULT last_error;
};
typedef struct __HashTable HashTable;

// 向哈希表中添加元素，其中键类型为char*， 元素类型为int。
HASH_RESULT hash_add_int(HashTable * table, const char * key, int value);

哈希表相关说明：

HASH_RESULT 类型为相关函数的返回类型
HashEntry 为哈希表所保存元素（即键值对 《key, value》）类型
HashTable 为哈希表，其中 bucket 指向大小为size的、元素类型为 HashEntry*的指针数组
哈希表采用链地址法处理冲突

请实现 hash_add_int 函数，向哈希表中添加元素，其中键类型为char*， 元素类型为int。在添加过程中，如果要添加的键值key已在哈希表中，且对应的值value也已存在，则函数返回 HASH_ALREADY_ADDED；如果要添加的键值key已在哈希表中，但对应的值value不同，则函数将value值更新到哈希表中，之后返回 HASH_REPLACED_VALUE；如果要添加的键值key不在哈希表中，则函数创建 HashEntry 类型，并将其加入到哈希表中，且函数返回 HASH_ADDED。本题所用的哈希函数如下：

long hash_string(const char str)
{
long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; / hash * 33 + c */
if(hash < 0)
hash *= -1;
return hash;
}

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-06-22, Mon, 02:10:56
    * 最高分数：100
    */
   
   
   #include "hash.h"
   #include "stdlib.h"
   #include <stdio.h>
   #include <string.h>
   
   int Find(HashTable* table, const char* key, int value, long keyhash)
   {
       HashEntry* Head = table->bucket[keyhash];
   
       while (Head && strcmp(Head->key.str_value, key)) {
           Head = Head->next;
       }
   
       if (!Head)
           return -1;
       else if (Head->value.int_value == value)
           return 1;
       else {
           Head->value.int_value = value;
           return 0;
       }
   }
   
   HASH_RESULT hash_add_int(HashTable* table, const char* key, int value)
   {
       int p;
       long keyhash = hash_string(key) % table->size;
       p = Find(table, key, value, keyhash);
   
       if (p == -1) {
           HashEntry* Node = (HashEntry*)malloc(sizeof(HashEntry));
           if (!Node)
               return HASH_ERROR;
           Node->key.str_value = (char*)malloc(100);
           if (Node->key.str_value == NULL) {
               return HASH_ERROR;
           }
           Node->key.str_value = (char*)key;
           Node->value.int_value = value;
           //Node->next = table->bucket[keyhash]; //？
           table->bucket[keyhash] = Node;
           return HASH_ADDED;
       } else if (p == 0)
           return HASH_REPLACED_VALUE;
       else
           return HASH_ALREADY_ADDED;
   }

---

T3

AVL添加

平衡二叉树，是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。现二叉平衡树结点定义如下：

typedef struct node
{
int val;
struct node *left;
struct node *right;
struct node *parent;
int height;
} node_t;

请实现平衡二叉树的插入算法：

//向根为 root 的平衡二叉树插入新元素 val，成功后返回新平衡二叉树根结点
node_t *avl_insert(node_t *root, int val);

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-06-22, Mon, 02:12:15
    * 最高分数：100
    */
   
   
   #include "avl.h"
   #include <stdio.h>
   #include <stdlib.h>
   
   node_t* Insert(node_t* T, int X);
   int GetHeight(node_t* T);
   int Max(int a, int b);
   node_t* SingleLeftRotation(node_t* A);
   node_t* DoubleLeftRightRotation(node_t* A);
   node_t* SingleRightRotation(node_t* A);
   node_t* DoubleRightLeftRotation(node_t* A);
   
   int Max(int a, int b)
   {
       return a > b ? a : b;
   }
   
   int GetHeight(node_t* T)
   {
       if (T)
           return T->height;
       else
           return 0;
   }
   
   node_t* SingleLeftRotation(node_t* A)
   {
       node_t* B;
       B = A->left;
       A->left = B->right;
       B->right = A;
       A->height = Max(GetHeight(A->left), GetHeight(A->right)) + 1;
       B->height = Max(GetHeight(B->left), GetHeight(B->right)) + 1;
       return B;
   }
   
   node_t* DoubleLeftRightRotation(node_t* A)
   {
       A->left = SingleRightRotation(A->left);
       return SingleLeftRotation(A);
   }
   
   node_t* SingleRightRotation(node_t* A)
   {
       node_t* B;
       B = A->right;
       A->right = B->left;
       B->left = A;
       A->height = Max(GetHeight(A->left), GetHeight(A->right)) + 1;
       B->height = Max(GetHeight(B->left), GetHeight(B->right)) + 1;
       return B;
   }
   
   node_t* DoubleRightLeftRotation(node_t* A)
   {
       A->right = SingleLeftRotation(A->right);
       return SingleRightRotation(A);
   }
   
   node_t* avl_insert(node_t* root, int val)
   {
       node_t* parentNode = NULL;
       if (!root) {
           root = (node_t*)malloc(sizeof(node_t));
           root->left = root->right = root->parent = NULL;
           root->val = val;
           root->height = 1;
       } else if (val < root->val) {
           parentNode = root->left;
           root->left = avl_insert(root->left, val);
           if (GetHeight(root->left) - GetHeight(root->right) == 2) {
               if (val < root->left->val)
                   root = SingleLeftRotation(root);
               else {
                   root = DoubleLeftRightRotation(root);
               }
           }
       } else if (val > root->val) {
           parentNode = root->left;
           root->right = avl_insert(root->right, val);
           if (GetHeight(root->right) - GetHeight(root->left) == 2) {
               if (val > root->right->val)
                   root = SingleRightRotation(root);
               else
                   root = DoubleRightLeftRotation(root);
           }
       }
       root->parent = parentNode;
       root->height = Max(GetHeight(root->left), GetHeight(root->right)) + 1;
       return root;
   }

---