알고리즘 서론 11.1 - 4 대 배열 의 직접 주소 지정 표

제목
우 리 는 매우 큰 배열 에서 직접 주 소 를 찾 는 방식 으로 사전 을 실현 하 기 를 바란다.처음에는 이 배열 에 폐기물 이 포 함 될 수 있 지만 전체 배열 을 초기 화 하 는 것 은 현실 적 이지 않다. 이 배열 의 규모 가 너무 크기 때문이다.큰 배열 에서 직접 주소 지정 사전 을 실현 하 는 방안 을 제시 하 십시오.저 장 된 대상 마다 O (1) 의 공간 을 차지 합 니 다.search, insert, delete 를 조작 하 는 시간 은 O (1) 입 니 다.데이터 구조 초기 화 시간 은 O (1) 입 니 다.(알림: 다른 스 택 을 이용 할 수 있 습 니 다. 크기 는 사전 에 저 장 된 키워드 수 와 같 습 니 다. 대형 배열 에서 주어진 항목 이 효과 적 인지 확인 하 는 데 도움 이 됩 니 다)
사고
배열 이 너무 커서 초기 화 할 수 없 기 때문에 본 문 제 는 배열 을 초기 화 할 수 없 는 상황 에서 배열 의 값 이 효과 적 인 키 인지 아 닌 지 를 어떻게 판단 하 느 냐 하 는 것 이다.
실제 삽 입 된 데 이 터 를 하나의 스 택 으로 저장 합 니 다. 삽입 할 때 스 택 은 위로 공간 을 확장 합 니 다. 삭제 할 때 스 택 상단 요소 로 삭 제 된 요소 의 위 치 를 보충 하고 스 택 은 아래로 공간 을 회수 합 니 다. 방법 은 P127 - 11.3 - 4 와 유사 합 니 다.
이 매우 큰 배열 은 데 이 터 를 직접 저장 하지 않 고 Stack 에 데 이 터 를 저장 하 는 위치 입 니 다.
하나의 요소 p 에 대해 만약 에 H [p] < 창고 에 있 는 총 요소 의 개수 & & p = Stack [H [p]] 를 저장 하면 존재 하지 않 습 니 다.
코드

#include <iostream>
#include <string>
using namespace std;

//  ，            
int Search(int *Hash, int *Stack, int value)
{
	int p = Hash[value];
	//     ：1.H[p]         2.     Stack    3.          
	if(p > 0 && p <= Stack[0] && Stack[p] == value)
		return p;
	return 0;
}
//  
int Insert(int *Hash, int *Stack, int value)
{
	int ret;
	//         
	if(ret = Search(Hash, Stack, value))
	{
		cout<<"error:already in "<<ret<<endl;
		return 0;
	}
	//      
	Stack[0]++;
	//              
	Stack[Stack[0]] = value;
	//               
	Hash[value] = Stack[0];
	return Stack[0];
}
//      
int Delete(int *Hash, int *Stack, int value)
{
	//         
	int ret = Search(Hash, Stack, value);
	if(ret == 0)
	{
		cout<<"error:not fount"<<endl;
		return 0;
	}
	//         
	int v = Stack[Stack[0]];
	//               ，     
	Hash[v] = ret;
	Stack[ret] = v;
	//    -1
	Stack[0]--;
	return ret;
}
//        
void Print(int *Stack)
{
	int i;
	for(i = 1; i <= Stack[0]; i++)
		cout<<Stack[i]<<' ';
	cout<<endl;
}
int main()
{
	string str;
	int x;
	int Hash[10000];
	int Stack[100] = {0};
	while(1)
	{
		cin>>str;
		if(str == "I")
		{
			x = rand() % 100;
			cout<<x<<endl;
			Insert(Hash, Stack, x);
		}
		else if(str == "D")
		{
			cin>>x;
			Delete(Hash, Stack, x);
		}
		else if(str == "P")
		{
			Print(Stack);
		}
	}
	return 0;
}