avatar

目录
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 函数,创建指定大小的哈希表。

  1. 解析
    Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /*
    * 完成人 :岳昕峰(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;
}

  1. 解析
    Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    /*
    * 完成人 :岳昕峰(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);

  1. 解析
    Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    /*
    * 完成人 :岳昕峰(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;
    }

文章作者: Cosmos_F
文章链接: http://fengxinyue.cn/post/420a3e9e.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 学习心得
打赏
  • 微信
    微信
  • 支付寶
    支付寶