해시표의 기초 조작 총결산(삽입, 찾기, 삭제 등)

typedef int HTKeyType;
typedef char HTValueType;
//                
typedef enum State
{
    EMPTY,// 
    EXITST,//    
    DELETE//    
}State;
//          
typedef struct HashData
{
    State _state;//  
    HTKeyType _key;//key-value
    HTValueType _value;//key-value
}HashData;
//        
typedef struct HashTable
{
    HashData* _table;//      
    int _len;//  
    int _size;//       
}HashTable;

//       
void HashTableInit(HashTable* ht, size_t len);
//     (malloc     )
void HashTableDestroy(HashTable* ht);
//          
int HashTableInsert(HashTable* ht, HTKeyType key, HTValueType value);
//          
int HashTableRemove(HashTable* ht, HTKeyType key);
//          
HashData* HashTableFind(HashTable* ht, HTKeyType key);
//         (   0，    1)
int HashTableEmpty(HashTable* ht);
//          
int HashTableSize(HashTable* ht);
//         
void PrintHashTable(HashTable* ht);

#include "HashTable.h"

//       
void HashTableInit(HashTable* ht, size_t len)
{
    assert(ht);
    //        
    ht->_table = (HashData*)malloc(sizeof(HashData)*len);
    if (ht->_table == NULL)
    {
        perror("use malloc to create");
    }
    //               (EMPTY)
    for (int i = 0; i < ht->_len; i++)
    {
        ht->_table[i]._state = EMPTY;
    }
    ht->_len = len;//      
    ht->_size = 0;//       
}
//     (malloc     )
void HashTableDestroy(HashTable* ht)
{
    assert(ht);
    free(ht->_table);
    ht->_table = NULL;
    ht->_size = 0;
    ht->_len = 0;
}
//    ，            (       )
int GetPosition(HashTable* ht, HTKeyType key)
{
    assert(ht);
    return key % (ht->_len);
}
//             (   0.7)，      ，        
void CheckCapacity(HashTable* ht)
{
    assert(ht);
    //  ：         ，         ，              
    //        ，                  
    HashTable newht;
    int len = 2 * ht->_len;//    (  2        ，       )
    if ((ht->_size * 10) / ht->_len > 7)//      (             ，         ，      10 )
    {
        HashTableInit(&newht, len);
        //        ，              
        for (int i = 0; i < ht->_len; i++)
        {
            if (ht->_table[i]._state == EXITST)
            {
                HashTableInsert(&newht, ht->_table[i]._key, ht->_table[i]._value);
            }
        }
        //    
        HashTableDestroy(ht);
        //                
        ht->_table = newht._table;
        ht->_size = newht._size;
        ht->_len = newht._len;
    }
}
//          
int HashTableInsert(HashTable* ht, HTKeyType key, HTValueType value)
{
    assert(ht);
    //              ，     
    CheckCapacity(ht);
    //1.       
    int index = GetPosition(ht, key);
    //2.     ，    (       )
    while (ht->_table[index]._state == EXITST)
    {
        //           ，     
        if (ht->_table[index]._key == key)
        {
            return 0;
        }
        //       ，        
        else
        {
            ++index;
        }
    }
    //3.      ，    
    ht->_table[index]._state = EXITST;
    ht->_table[index]._key = key;
    ht->_table[index]._value = value;
    ht->_size++;
}
//          
int HashTableRemove(HashTable* ht, HTKeyType key)
{
    assert(ht);
    //1.          
    HashData* ret = HashTableFind(ht, key);
    //2.      ，        ，      1
    if (ret)
    {
        ht->_size--;
        ret->_state = DELETE;
        return 1;
    }
    //      0
    return 0;
}
//          
HashData* HashTableFind(HashTable* ht, HTKeyType key)
{
    assert(ht);
    //1.             
    int index = GetPosition(ht, key);
    //2.     ，             
    while (ht->_table[index]._state != EMPTY)
    {
        if (ht->_table[index]._key == key)
        {
            //                  
            if (ht->_table[index]._state == EXITST)
            {
                return &ht->_table[index];
            }
            //       ，            ，    
            else
            {
                return NULL;
            }
        }
        //                 
        else
        {
            ++index;
        }
    }
    //         
    return NULL;
}
//     (    )
void PrintHashTable(HashTable* ht)
{
    assert(ht);
    for (int i = 0; i < ht->_len; i++)
    {
        if (ht->_table[i]._state == EXITST)
        {
            printf("[%d](%d:%c)
", i, ht->_table[i]._key, ht->_table[i]._value);
        }
    }
    printf("
");
}
//         (   0，    1)
int HashTableEmpty(HashTable* ht)
{
    assert(ht);

    return ht->_size == 0 ? 0 : 1;
}
//          
int HashTableSize(HashTable* ht)
{
    assert(ht);

    return ht->_size;
}

#include "HashTable.h"

void TestHashTable()
{
    HashTable ht;
    HashTableInit(&ht, 5);
    HashTableInsert(&ht, 15, 'f');
    HashTableInsert(&ht, 24, 't');
    HashTableInsert(&ht, 56, 's');
    HashTableInsert(&ht, 71, 's');
    HashTableInsert(&ht, 23, 's');
    HashTableInsert(&ht, 46, 's');
    HashData* ret = HashTableFind(&ht, 71);
    printf("state:%d,key;%d,value:%c
", ret->_state, ret->_key, ret->_value);
    printf("      ：%d
", HashTableSize(&ht));
    HashTableRemove(&ht, 15);
    printf("      ：%d
", HashTableSize(&ht));
    HashTableInsert(&ht, 59, 's');
    HashTableInsert(&ht, 31, 's');
    printf("      ：%d
", HashTableSize(&ht));
    PrintHashTable(&ht);
    HashTableDestroy(&ht);
}
int main()
{
    TestHashTable();
    return 0;
}