문자열을 이진 검색하는 데 ASCII 문자 합을 사용합니까?

나는 첫 번째 학기의 일부로 연결된 목록을 사용하는 학생 데이터베이스 인 미니 프로젝트를하고 있습니다. 명세는 사용자가 구조에서 char [4] 인 이름 이니셜을 사용하여 레코드를 검색 할 수 있어야한다는 것입니다.문자열을 이진 검색하는 데 ASCII 문자 합을 사용합니까?

이니셜을 검색하는 두 가지 방법이 있습니다. 하나는 사실상 비효율적 인 선형 검색입니다 (실제로 이것에 대해서는 신경 쓰지 않습니다. 왜냐하면 이것이 어떤 회사의 기본 정보가 될 수 없기 때문입니다) 또는 바이너리 수색.

이진 검색에는 정렬 된 배열이 필요하므로 문자열의 ASCII 합계를 사용하여 검색하는 것이 의미가 있다고 생각합니까?

예를 들어 레코드 1에는 초기 = "AB"가 있고 레코드 2에는 "CD"가 있습니다. 65 + 66 = 131 & 67 + 68 = 135이고 목록은 이니셜을 사용하여 정렬됩니다 (strcmp 사용).

그래서 사용자가 "AB"를 입력하면 131이라는 번호를 찾고 해당하는 경우 레코드를 표시합니까?

이것은 매우 나쁜 생각 일 수 있습니다. 나에게 불꽃을 보내지 말고 왜 나쁜지 설명하십시오.

출처

2011-10-08 Nilesh

2011 년에는 사용자 이름을 ASCII로 표현할 수 있다고 가정하면 안됩니다. 우리는 오랫동안 유니 코드를 가졌습니다. –

나에게 좋은 출발처럼 보입니다. "TON"과 "NOT"을 어떻게 구별 할 것입니까? 그들은 같은 값 ('충돌')을가집니다. 2 단계 접근 방식을 제안 하시겠습니까? 첫 번째는 ascii-sum 검색이고 두 번째는 충돌을 분류하는 방법입니다. 여기에 해싱에 대한 좋은 정보가있는 것 같습니다 : http://burtleburtle.net/bob/hash/index.html

출처

2011-10-08 03:34:18

예. 두 단계 검색을 생각하고있었습니다. 해싱은 우리 수준에서 너무 발전했습니다. 실제로는 해시와 관련된 내용을 아직 가르쳐 보지 않았습니다. 인터넷에서 알고있는 프로그래밍의 대부분을 배웠다해도 문제가되지 않습니다. – Nilesh

정확하게 이해했다면 이니셜을 찾는 것이 매우 잘못되었습니다. 내가 처음 보는 문제는 다음과 같습니다.

AD = 65+68 = 133 
BC = 66+67 = 133

실제로는 구별 할 수 없습니다. 하지만 두 글자를 비교하는 데는 무엇이 잘못 되었습니까? ASCII 값을 연결하는 것만으로도 어떨까요?

AD = 65.68 = 6568 
BC = 66.67 = 6667

많이 잤지 않았는데, 내가 쓴 것이 전부 꺼져 있습니다.

출처

2011-10-08 03:38:06 ath88

@Mystical에 의해 이전에 말했듯이, 나는 2 단계 검색을 할 것입니다. 그래서 이것은 문제가되어서는 안됩니다. 같은 수의 두 요소를 감지하면 문자를 비교합니다. 연속 검색은 더 좋은 생각인데, 이진 검색이 적용 가능한지 여부는 모르지만 (계속 증가하고 있으므로 예라고 생각합니다.) – Nilesh

많은 충돌이 있습니다. 확장 가능 해싱을 위해 이동

Wikipedia

Algorithm explained

출처

2011-10-08 04:16:50

어쨌든 정렬 된 배열을 구성 위하여려고하는 경우에,이 (손실, 바이어스) 해시 값과에서 해당 검색을 계산 이유가 없다 정렬 된 목록 - 이니셜을 직접 목록에서 이진 검색하는 것만 큼 빠릅니다.

출처

2011-10-10 00:54:18