C + + 코드 산 목록
7588 단어 데이터 구조
(Hash 표를 배 운 적 이 없 는 친구 입 니 다. 저 는 강 좌 를 추천 합 니 다. http://www.cnblogs.com/jiewei915/archive/2010/08/09/1796042.html
전에 배 운 데이터 구 조 를 회상 하고 표를 작성 하여 Hash 표 와 비교 합 시다 (표 에서 c 는 상수).
삽입 시간
삭제 시간
찾기 시간
프로 그래 밍 복잡 도
정보 분석 도
무질서 배열
1
N
N
☆
☆
순서 배열
N
N
logN
☆
☆
무질서 링크
1
N
N
☆☆☆
☆
밸 런 스 트 리
logN
logN
logN
☆☆☆☆☆
☆
Hash 표
상수
상수
상수
☆☆
☆☆☆
이 표 에서 앞의 4 열 은 이해 하기 쉽다.
예 를 들 어 N 개의 요소 에 대해 무질서 한 구 조 를 쓰 고 아무 생각 없 이 저장 하면 된다.질서 있 는 구 조 를 쓰 는 것 도 두 요소 간 에 크기 를 어떻게 비교 하 는 지 생각해 야 한다 (예 를 들 어 3 < 5, "ab", "aca"). 우 리 는 이 N 개 수 자체 의 정 보 를 매우 적 게 분석 했다.따라서 이런 정보 분석 도가 낮은 데이터 구 조 는 기본적으로 아무 생각 없 이 가 져 오 면 코드 를 쓸 수 있다.
그러나 Hash 표 는 그렇지 않 습 니 다. 우 리 는 데 이 터 를 더욱 깊이 분석 해 야 합 니 다. (예 를 들 어 숫자 가 정수 인지, 문자열 이 얼마나 긴 지) 그렇지 않 으 면 당신 의 Hash 표 가 틀 릴 수 있 습 니 다.따라서 데 이 터 를 분석 하 는 습관 을 들 여야 구체 적 인 문제 에서 산 목록 을 사용 할 수 있 는 지, 산 목록 을 어떻게 사용 할 수 있 는 지 알 수 있다.
자, 이렇게 많아마지막 으로 제 가 Hash 표 의 프로 그래 밍 복잡 도 는 두 개의 별 밖 에 없다 고 말 한 이상 다음 에 제 코드 를 드 리 겠 습 니 다. (Hash 표 는 여러 가지 가 있 습 니 다. 제 가 가장 자주 사용 하 는 것 은 바로 대수 Hash + 링크 의 존 중 입 니 다. 코드 가 간단 하고 적용 성 이 강 합 니 다)
제목: sjtuoj 1224
시원 판: Hash 표 의 코드, 시원 판 은 초보 자 에 게 는 쉽게 흐 트 러 지기 때문에 클래스 만 제공 합 니 다.
클래스:
1. 누 드 Hash 시계 (본 문 제 는 메모리 가 충분 하기 때문에 넘 을 수 있 습 니 다)
2. 모 대소 수 + 지퍼 (본 문제 에 있어 NC 의 방법 을 비교 하고 HQ 학생 들 의 제시 에 감 사 드 립 니 다. 누 드 Hash 표 AC 를 직접 사용 할 수 있 습 니 다)
1 #include <cstring>
2
3 // Hash
4 class Hash
5 {
6 int H[4000000];
7 int k(int num) { return num+2000000; }
8 int num(int k) { return k-2000000; }
9 public:
10 Hash() { memset(H,0,sizeof(H)); } // ， Hash ， ，
11 void in(int num) { ++H[k(num)]; }
12 int count(int num) { return H[k(num)]; }
13 };
14
15 // +
16 class Hash
17 {
18 struct hash
19 {
20 int num;
21 hash *next;
22 }*H[250000],New[250000];
23 int L;
24 hash* make(int num) { New[L].num=num; return New+L++; }
25 int k(int num) { return (num+2000000)%249989; }
26 public:
27 Hash():L(0) { memset(H,0,sizeof(H)); } // ， Hash ， ，
28 void in(int num)
29 {
30 hash *u=make(num);
31 u->next=H[k(num)]; H[k(num)]=u;
32 }
33 int count(int num)
34 {
35 int s=0;
36 for(hash *u=H[k(num)];u;u=u->next)
37 if(u->num==num) ++s;
38 return s;
39 }
40 };좋은 웹페이지 즐겨찾기
