Beginner 구조체 배열에서 첫 번째 요소 제거 (C)

Question

구조체 배열이 있습니다 (실제로는 우선 순위별로 정렬 된 힙 배열입니다).

typedef struct { 
    char name[MAX_CHARACTERS+1]; 
    int priority; 
} person; 
person p[MAX_HEAPSIZE+1]; 

그리고 배열의 첫 번째 요소를 제거하려고합니다. 어떻게 또는 어떤 명령을 사용해야할지 모르겠습니다.

지금까지 내가

void remove(){ 
    swap(0, heapsize-1); 
    strcpy(p[heapsize-1].name, p[MAX_HEAP_SIZE+1].name); 
    p[heapsize-1].priority = p[MAX_HEAP_SIZE+1].priority; 
} 

을 해왔이 배열의 첫 번째와 마지막 비어 있지 않은 요소를 교환합니다. 그런 다음 빈 요소의 데이터를 배열에서 마지막 비어 있지 않은 요소 (제거하려는 요소)로 복사하려고 시도합니다.

하지만 메모리 위치 만 복사한다고 생각합니다. 내가 할 수있는 곳에서 간단한 것이 있습니까?

p [0] = NULL?

Answer 1

배열은 연속적인 메모리 블록입니다. 당신이 첫 번째 요소를 제거하려는 경우, 당신은 하나 개의 요소에 의해 시작 대한 다음의 모든 요소를 ​​이동해야합니다 : 이것은 매우 비효율적이다

void remove(void) 
{ 
    memmove(&p[0], &p[1], (MAX_HEAPSIZE - 1) * sizeof(person)); 
} 

. 첫 번째 요소를 팝하는 것은 힙을 사용하는 일반적인 작업이므로 일반적으로 다른 방법으로 배열의 마지막 요소를 제거합니다. 이는 배열의 다른 요소가 영향을받지 않기 때문에 매우 빠릅니다.

void remove(void) 
{ 
    heapsize--; 
} 

heapsize

다음 힙의 최상위 요소의 인덱스로 사용할 수 있습니다 (당신은 물론, 힙 속성을 유지 가정).

당신이 마지막으로 배열의 첫 번째 요소를 덮어 더 이상 사용되지 않는 마지막 요소의 메모리를 제로하려는 경우, 당신이 사용할 수있는 방어 적이기와 memset 함수 :

void remove(void) 
{ 
    memcpy(&p[0], &p[heapsize - 1], sizeof(person)); 
    memset(&p[heapsize - 1], 0x00, sizeof(person)); 
} 

영점 마지막 요소의 메모리를 꺼내는 것은 꼭 필요한 것은 아닙니다. 왜냐하면 처음부터 액세스하지 않아야하기 때문입니다. memcpy를 사용하여 첫 번째 요소를 마지막 요소로 덮어 쓰는 대신 strcpy을 사용하고 우선 순위를 할당 할 수도 있습니다 (예 : remove). memcpy를 사용하는 것이 간단합니다.

Answer 2

힙 정렬을 구현하려는 것 같습니다. 실제로 힙의 첫 번째 요소 또는 마지막 요소까지 "제거"할 필요는 없습니다.

대신 알고리즘은 출력을 위해 첫 번째 요소 (우선 순위가 가장 높은 요소)의 값을 복사 한 다음 배열의 "끝"에서 첫 번째 위치로 노드를 복사하여 버블을 준비합니다 올바른 위치에 내려 놓으십시오. 배열의 "끝"은 현재 힙 크기로 표시됩니다.

내가 막연하게 아래로 버블 링하는 이동 항목에 아이들의 우선 순위를 확인하고 교환하여 수행됩니다 리콜 배열의 마지막 항목, 그냥 1

하여 heap_size을 줄이기 "제거"하기 우선 순위가 가장 높은 것을 선택하십시오. 항목이 하위 항목보다 우선 순위가 높거나 같을 때까지 이동 된 항목에서이 작업을 반복하십시오.

항목의 하위 항목을 찾는 방법은 간단합니다. 2 * i 및 2 * i + 1에있는 노드로, 배열은 0 대신 1에서 시작합니다.0 기반 어레이의 경우 2 * (i + 1) -1 및 2 * (1 + 1)이 될까요? 수학을 확인하십시오. 또는 간단히 배열의 한 요소를 낭비하여 수학을 간단하게 유지하십시오.)