[데이터 구조] 주소록 조회 시스템 의 디자인 과 실현 (산 목록 (해시 표)

1. 문제 설명:
어떤 부서 에 직원 주소록 관리 시스템 을 구축 하면 모든 직원 의 전화 와 주 소 를 편리 하 게 조회 할 수 있다.산 목록 저장 소 를 설계 하고 주소록 검색 시스템 을 설계 하고 실현 합 니 다.
 
2. 기본 요구
(1) 각 기록 에는 다음 과 같은 데이터 항목 이 있다. 전화번호, 사용자 이름, 주소.
(2) 키보드 에서 각 기록 을 입력 하고 각각 전화 번 호 를 키워드 로 하여 산 목록 을 작성 한다.
(3) 2 차 탐측 재 산열 법 으로 충돌 을 해결한다.
(4) 주어진 전화번호 의 기록 을 찾 아 표시 합 니 다.
(5) 주소록 정보 파일 저장.
 
원리
1. 해시 표 는 키 코드 값 에 따라 직접 방문 하 는 데이터 구조 입 니 다.즉, 키 코드 값 을 표 의 한 위치 에 비 추어 기록 에 접근 함으로써 검색 속 도 를 빠르게 하 는 것 이다.이 매 핑 함 수 는 해시 함수 라 고 하 는데 기록 을 저장 하 는 배열 을 산 목록 이 라 고 합 니 다.주어진 표 M, 함수 f (key) 가 존재 합 니 다. 주어진 키워드 값 key 를 함수 에 대 입 한 후 이 키 워드 를 포함 하 는 표 에 기 록 된 주 소 를 얻 을 수 있다 면 표 M 을 해시 표 라 고 하고 함수 f (key) 를 해시 함수 라 고 합 니 다.2. 2 차 탐지 재 산열 법: 충돌 이 발생 하면 + 1²，-1²，+2²，-2²…방식 을 탐지 하여 재 산열 하 는 방법.
 
사고
 
이 문 제 는 기본적으로 해시 표 의 간단 한 응용 이 라 고 할 수 있다.
①   해시 테이블 구축 (해시 함 수 를 만들어 충돌 처리 에 적합 한 방법 을 확인 해 야 합 니 다)
②   전화번호 에 따라 찾 아 출력 하 다.
③   해시 표를 파일 출력 에 순서대로 저장 합 니 다.
 
코드
 

#include
#include
#include
#include
#define MAXSIZE 50
using namespace std;
int Czy=1;
typedef struct record 
{
	char Number[20];
	char Name[20];
	char Address[20];
}Record;
 
typedef struct Hash
{
	Record *data;
	int cnt;
	int size;
}*HashTable,HashElem;

//    ，           
int GetHashKey(char ar[])
{
	int len=strlen(ar);
	int key=0;
	for(int i=0;idata[(key+(Czy/2)*(Czy/2))%MAXSIZE].Name[0]==0)
		 		return (key+(Czy/2)*(Czy/2))%MAXSIZE;
		} 
		else if(Czy%2!=0) {
			if((key-(Czy/2)*(Czy/2))<0) continue;//     ，          
			if(table->data[(key-(Czy/2)*(Czy/2))%MAXSIZE].Name[0]==0)
		 		return (key-(Czy/2)*(Czy/2))%MAXSIZE;
		}
	}
	//return -1;
}

//      
void CreateHashTable(HashTable &table,Record *record,int n)
{
	int key;
	for(int i=0;idata[key].Name[0]!=0)
			key=HandleCollision(table,key);
			
		strcpy(table->data[key].Number,record[i].Number);
		strcpy(table->data[key].Name,record[i].Name);
		strcpy(table->data[key].Address,record[i].Address);
	}	
}

//         
int SerchKey(HashTable table,char PhoneNumber[])
{
	int key=GetHashKey(PhoneNumber);
	if(strcmp(table->data[key].Number,PhoneNumber)){
		for(Czy=1;Czydata[(key+(Czy/2)*(Czy/2))%MAXSIZE].Number)){
		 		key= (key+(Czy/2)*(Czy/2))%MAXSIZE;
		 		break;
		 	}
		} 
		else if(Czy%2!=0) {
			if((key-(Czy/2)*(Czy/2))<0) continue;//     ，          
			if(!strcmp(PhoneNumber,table->data[(key-(Czy/2)*(Czy/2))%MAXSIZE].Number)){
		 		key= (key-(Czy/2)*(Czy/2))%MAXSIZE;
				break;
		 	}
			}
		}
	} 
	//if(flag) cout<data[key].Name<data[key].Number<data[key].Address<data[i].Name[0]!=0)
			fprintf(fp,"%s %s %s
",table->data[i].Name,table->data[i].Number,table->data[i].Address);	
			//printf("%s %s %s
",table->data[i].Name,table->data[i].Number,table->data[i].Address);	
		fclose(fp);	
}
 
int main(){
	//       
	Record record[50];
	HashElem table;
	HashTable numbertable;
	numbertable = & table;
	numbertable->data=(Record*)malloc(sizeof(record[0])*MAXSIZE);
	memset(numbertable->data,0,sizeof(record[0])*MAXSIZE);
	numbertable->size=MAXSIZE;
	numbertable->cnt=0;
	int k;
	//              
    //freopen("Data.txt","r",stdin);
	cin>>k;
	for(int i=0;i>record[i].Number>>record[i].Name>>record[i].Address;
	//      
	CreateHashTable(numbertable,record,k);
	//      
	GoToFile(numbertable);
	//     PhoneNumber（      ） 
	char PhoneNumber[20];
	cin>>PhoneNumber;
	cout<

 
 
 
5. 주석:
 
 
1. 해시 함수 가 key 를 구 할 때 모드 MAXSIZE 를 가 져 와 야 합 니 다. 그렇지 않 으 면 key 가 배열 을 넘 을 수 있 습 니 다!2. 2 차 탐지 재 산열 시 하나의 변수 Czy 만 정의 하면 됩 니 다. 패 리 티 를 구분 할 수도 있 고 이동 크기 (+ x) 를 계산 할 수도 있 습 니 다.²，-x²） 3. 정수 만 모드% 를 취 할 수 있 으 므 로 if (key - (Czy / 2) * (Czy / 2))) < 0 을 추가 해 야 합 니 다.