데이터 구조 - 산 목록

산 목록 은 해시 표 라 고도 부른다.산 목록 역시 비교적 신기 한 데이터 구조 로 그 기본 사상 은 무한 집합 을 고정 집합 에 투사 하여 빠 른 검색 을 실현 하 는 데 있다.여기 서 간단 한 산 목록 을 실현 합 니 다. 삽입 요소 가 모두 다르다 고 가정 하고 지정 한 요소 유형 은 int 입 니 다.
구조

//      
class Hash {
    int capacity; // hash      
    Node* data; //               
}

함수 구현
초기 화

//       
Hash()
{
    this->capacity = 100019; //      ，          ，         
    this->data = new Node[this->capacity];
}

증가시키다

//        hash ，       
int hash(int value)
{
    value = (value + this->capacity) % this->capacity;
    return value;
}

//            
void insert_elem(int value)
{
    int index = hash(value);
    Node* pre = this->data + index,*p = pre->next;
    while(p)
    {
        if(p->value == value)
            break;
        pre = p;
        p = p->next;
    }
    if(!p) // p  ，          
        pre->next = new Node(value);
}

삭제

//            
void delete_elem(int value)
{
    int index = hash(value);
    Node* pre = this->data + index,*p = pre->next;
    while(p)
    {
        if(p->value == value)
            break;
        pre = p;
        p = p->next;
    }
    if(p) // p  ，        
    {
        pre->next = p->next;
        delete p;
    }
}

//       
void clear_chain(Node* head)
{
    Node* p = head->next;
    while(p)
    {
        Node* tmp = p->next;
        delete p;
        p = tmp;
    }
}

//      
void clear()
{
    for(int i = 0;i < this->capacity;i++)
    {
        clear_chain(this->data + i);
        this->data[i].next = NULL;
    }
}

수정 하 다.
요 소 를 삽입 하 는 것 이 키워드 이기 때문에 수정 작업 은 언급 되 지 않 습 니 다.
찾다

//          
bool contains(int value)
{
    int index = hash(value);
    Node* p = this->data + index;
    while(p)
    {
        if(p->value == value)
            return true;
        p =p->next;
    }
    return false;
}

소각 하 다

//     
~Hash()
{
    for(int i = 0;i < this->capacity;i++)
        clear_chain(this->data + i);
    delete[] this->data;
}