알고리즘 서론 11.2 - 4 산 목록 에 사용 되 지 않 은 슬롯 이 자유 링크 로 연결 되 어 있 습 니 다.

제목
산 목록 내부 에서 사용 되 지 않 은 모든 슬롯 체인 을 자유 표 로 만들어 요소 의 저장 공간 을 분배 하고 제거 하 는 방법 을 설명 합 니 다.하나의 슬롯 위 치 를 가정 하면 하나의 표지, 하나의 요소 에 하나 또는 두 개의 지침 을 저장 할 수 있다.모든 사전 작업 과 자유 링크 작업 은 O (1) 의 기대 운행 시간 을 가 져 야 합 니 다.이 자유 링크 는 더 블 링크 입 니까?아니면, 싱글 체인 시계 면 충분 하지 않 을까요?
사고
알 고 있 습 니 다 (1) 모든 사용 되 지 않 은 슬롯 체인 은 자유 링크 (2) 슬롯 즉 slot (3) Hash (x) 로 x 가 속 한 slot 를 되 돌려 줍 니 다.
하나의 slot 는 다음 과 같은 내용 을 저장 합 니 다. 점용 과 점용 되 지 않 았 을 때 나타 내 는 의미 가 다 릅 니 다.

struct node
{
	int key;
	bool flag;//0:free，1:used
	int pre;
	int next;
};

이 slot 가 점용 되 지 않 았 을 때, 값 은 다음 과 같 습 니 다.

struct node
{
	int key;//    ，    -1
	bool flag;//0:free
	int pre;//          slot，    -1
	int next;//          slot，    -1
};

이 slot 가 점용 되 었 을 때, 값 은 다음 과 같 습 니 다.

struct node
{
	int key;//   
	bool flag;//1:used
	int pre;//    Hash       
	int next;//    Hash       
};

 
작업 을 삽입 할 때 자유 링크 에서 남 은 slot 를 꺼 내 키워드 x 를 입력 하고 지침 을 수정 하 며 링크 에 해당 하 는 대기 열 에서 구체 적 으로 다음 과 같은 몇 가지 상황 으로 나 눌 수 있 습 니 다.
(1) x 가 속 한 slot 가 점용 되 지 않 으 면
step 1: 이 slot 를 자유 링크 에서 꺼 냅 니 다.
step 2: 키워드 입력 x
step 3: 포인터 수정, 이 경우 next 와 pre 를 모두 - 1 로 설정 합 니 다.
(2) x 가 속 한 slot 는 이미 점용 되 었 습 니 다. 이 slot 를 점용 하 는 관건 은 y 입 니 다. y 도 이 slot 에 속 합 니 다.
step 1: 자유 링크 에서 남 은 slot 를 꺼 냅 니 다. 이 slot 는 x 가 속 한 slot 가 아 닙 니 다. 가 져 와 서 만 사용 합 니 다.
step 2: 키워드 입력 x
step 3: 포인터 수정, slot 링크 를 "x 에 속 하 는 slot 를 머리 로 하 는 대기 열" 에 넣 습 니 다.
(3) x 가 속 한 slot 는 이미 점용 되 었 습 니 다. 이 slot 를 점용 하 는 관건 은 y 입 니 다. y 는 이 slot 에 속 하지 않 습 니 다. (2) 를 통 해 알 수 있 듯 이 이 상황 은 가능 합 니 다.
step 1: 자유 링크 에서 남 은 slot 를 꺼 냅 니 다. 이 slot 는 x 가 속 한 slot 도 아니 고 y 가 속 한 slot 도 아 닙 니 다. 가 져 와 서 만 사용 합 니 다.
step 2: 새 slot 에 키워드 y 를 입력 하고 지침 을 수정 하여 y 가 이 새 slot 를 사용 하도록 하고 원래 의 slot 를 비 워 x 에 게 돌려 줍 니 다.
step 3: x 가 속 한 slot 에 키워드 x 를 입력 합 니 다.
step 4: "x 소속 slot" 지침 수정, 유사 (1) - step 3
 
삭제 작업 시 삭제 할 키 워드 는 x 입 니 다. x 가 사용 하 는 slot 를 방출 합 니 다. 구체 적 으로 다음 과 같은 몇 가지 상황 으로 나 눌 수 있 습 니 다.
(1) x 가 사용 하 는 slot 는 바로 x 가 속 한 slot 이 고 slot - > next = - 1 입 니 다. 즉, 모든 키워드 에서 x 만 이 slot 에 속 합 니 다. x 가 삭제 되면 slot 는 비어 있 습 니 다.
step 1: 자유 링크 에 slot 방출
(2) x 가 차지 하 는 slot 는 바로 x 가 속 한 slot 이지 만 다른 키워드 중 x 만 이 slot 에 속 합 니 다. 관건 이 속 하 는 slot 를 우선 사용 하고 '자신의 키워드 가 아 닌 임시로 가 져 온' slat 를 방출 해 야 합 니 다.
step 1: slot 를 머리 로 하 는 대기 열 에서 다른 slot 2 를 선택 하 십시오. slot 2 의 키 워드 는 slot 2 에 속 하지 않 고 slot 2 에 속 합 니 다. slot 가 점용 되 었 기 때문에 slot 2 를 사용 합 니 다.
step 2: slot 2 의 내용 을 slot 에 채 웁 니 다.
step 3: 슬롯 2 대신 슬롯 2 가 대기 열 에 존재 하도록 지침 을 수정 합 니 다. 다른 것 은 슬롯 입 니까? 아니면 대기 열 헤드 입 니까?
step 4: 자유 링크 에 slot 2 방출
(3) x 가 사용 하 는 slot 는 x 가 속 한 slot 가 아 닙 니 다. 이 경우 이 slot 는 대기 열 헤더 가 아 닙 니 다. 그리고 다른 키 워드 는 대기 열 에 존재 하고 x 가 속 한 slot 를 사용 합 니 다.
step 1: x 가 사용 하 는 slot 를 "x 가 속 한 slot 를 머리 로 하 는 대기 열" 에서 이동 합 니 다.
step 2: 자유 링크 에 slot 방출
 
검색 작업 은 삽입 과 삭 제 를 이해 하면 검색 작업 이 비교적 간단 합 니 다. 찾 아야 할 키 워드 는 x 이 고 몇 가지 상황 으로 나 눌 수 있 습 니 다.
(1) x 가 속 한 slot 는 점용 되 지 않 았 습 니 다. 즉, x 와 같은 slot 의 키 워드 는 존재 하지 않 습 니 다. 물론 x 도 존재 하지 않 습 니 다.
(2) x 에 속 하 는 slot 가 점용 되 었 으 나, 존재 하 는 관건 은 이 slot 에 속 하지 않 습 니 다. (1) 과 마찬가지 로 x 와 같은 slot 의 키 워드 는 존재 하지 않 습 니 다.
(3) x 가 속 한 slot 가 점용 되 었 고 존재 하 는 관건 은 이 slot 에 속 합 니 다. 즉, x 와 같은 slot 의 키워드 가 존재 합 니 다. 다만 이 키워드 가 x 인지 아 닌 지 는 모 르 겠 습 니 다. 더 찾 아야 합 니 다.
 
삽입 과 삭제 과정 에서 반복 적 으로 언급 한 '자유 링크 에서 남 은 slot 를 꺼 냅 니 다' 와 'slot 를 자유 링크 로 방출 합 니 다' 라 는 두 가지 조작 은 비교적 간단 합 니 다. 코드 에서 설명 한 바 와 같 습 니 다.
 
코드

#include <iostream>
#include <string>
using namespace std;
//slot  
struct node
{
	int key;//   
	bool flag;//0:free，1:used
	int pre;
	int next;
};
int Free = 0;//      slot
//  x   slot
int Hash(int x)
{
	return x % 20;
}
//             slot，        h slot
int RemoveSlotFromFree(node *A, int h)
{
	//   used
	A[h].flag = 1;
	//          
	if(A[h].pre >= 0)
		A[A[h].pre].next = A[h].next;
	else Free = A[h].next;//           slot，      slot   
	if(A[h].next >= 0)
		A[A[h].next].pre = A[h].pre;
	//     slot   
	return h;
}
//    h slot        
void FreeSlotToFree(node *A, int h)
{
	//   free
	A[h].flag = 0;
	//    ，      
	A[h].next = Free;
	A[h].pre = -1;
	A[h].key = -1;
	//        slot
	Free = h;
}
//    
int Search(node *A, int x)
{
	int h = Hash(x);
	//(1)x   slot    ，     x  slot    ，      x 
	//(2)x   slot    ，            slot， (1)  ，    x  slot    
	if(A[h].flag == 0 || Hash(A[h].key) != h)
		return -1;
	//(3)x   slot    ，           slot
	//    x  slot    ，            x，       
	//         slot     
	int p = h;
	while(p >=0 && A[p].key != x)
		p = A[p].next;
	if(A[p].key == x)
		return p;
	else return -1;
}
//     ，            slot，     x，    ，        ，
void Insert(node *A, int x)
{
	//      
	if(Search(A, x) >= 0)
	{
		cout<<"error:exit"<<endl;
		return ;
	}
	//  x   slot
	int h = Hash(x);
	//(1)x   slot    
	if(A[h].flag == 0)
	{
		//step1：   slot        
		int t = RemoveSlotFromFree(A, h);
		//step2：     x
		A[t].key = x;
		//step3：    ，       next pre   -1
		A[t].next = -1;
		A[t].pre = -1;
	}
	//（2）x   slot     ，     slot    y，y     slot
	else if(Hash(A[h].key) == h)
	{
		//step1：             slot，  slot    x   slot，      
		int t = RemoveSlotFromFree(A, Free);
		//step2：     x
		A[t].key = x;
		//step3：    ， slot    “ x   slot       ” 
		A[t].next = -1;
		A[h].next = t;
		A[t].pre = h;
	}
	//（3）x   slot     ，     slot    y，y     slot，
	//  （2）  ，         
	else
	{
		//step1：             slot，  slot    x   slot，   y   slot
		int t = RemoveSlotFromFree(A, Free);
		//step2：  slot      y，    ， y     slot，     slot     x
		A[t] = A[h];
		A[A[h].pre].next = t;
		if(A[h].next >= 0)
			A[A[h].next].pre = t;
		//step3： x   slot      x
		A[h].key = x;
		//step4：  “x   slot”  ，  (1)-step3
		A[h].next = -1;
		A[h].pre = -1;
	}
}
//     ，         x，  x    slot
void Delete(node *A, int x)
{
	//    
	int ret = Search(A, x);
	if(ret < 0)
	{
		cout<<"error:not exit"<<endl;
		return ;
	} 
	//(1)x    slot  x   slot， slot->next=-1
	//         x    slot，x    ，slot    
	if(ret == Hash(x) && A[ret].next == -1)
	{
		FreeSlotToFree(A, ret);
	}
	//(2)x    slot  x   slot，           x    slot
	//            slot，   “       、       ”slat
	else if(ret == Hash(x) && A[ret].next != -1)
	{
		//step1：  slot            slot2
		//slot2      slot    slot2，    slot   ，    slot2
		int next = A[ret].next;//next  slot2   
		//step2： slot2     slot
		A[ret] = A[A[ret].next];
		//step3：    ， slot  slot2      ，    slot     
		A[A[ret].next].pre = ret;
		//step4：  slot2      
		FreeSlotToFree(A, next);
	}
	//(3)x    slot  x   slot,      ，  slot       
	//             ，     x   slot
	else if(ret != Hash(x))
	{
		//step1： x    slot “ x   slot     ”   
		A[A[ret].pre].next = A[ret].next;
		if(A[ret].next >= 0)
			A[A[ret].next].pre = A[ret].pre;
		//step2：  slot      
		FreeSlotToFree(A, ret);
	}
}
//  slot
void Print(node *A)
{
	int i;
	for(i = 0; i < 20; i++)
		cout<<A[i].flag<<' '<<A[i].key<<' '<<A[i].next<<' '<<A[i].pre<<endl;
}
int main()
{
	int i;
	//      20 slot    
	node A[20];
	for(i = 0; i < 20; i++)
	{
		//   ，  slot  free
		A[i].flag = 0;
		if(i == 19)
			A[i].next = -1;
		else A[i].next = i + 1;
		A[i].pre = i - 1;
		A[i].key = -1;
	}
	//test
	string str;
	int x;
	while(1)
	{
		cin>>str;
		if(str == "I")
		{
			x = rand() % 100;
			cout<<x<<endl;
			Insert(A, x);
		}
		else if(str == "D")
		{
			cin>>x;
			Delete(A, x);
		}
		else if(str == "P")
			Print(A);
	}
	return 0;
}