Начинающий Удаление первого элемента из массива структур (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));
}

Это довольно неэффективно.Выделение первого элемента - это обычная операция с кучей, поэтому вы обычно делаете это наоборот - удаляете последний элемент массива - что очень быстро, потому что другие элементы массива не затрагиваются. *Затем можно использовать 1004 *

void remove(void)
{
    heapsize--;
}

heapsize в качестве индекса верхнего элемента кучи (разумеется, при условии сохранения свойства кучи).

Если вы хотите перезаписать первыйЭлемент массива с последним и обнулением памяти последнего элемента, который больше не используется, можно использовать memcpy и 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

Похоже, вы пытаетесь реализовать кучу сортировки. На самом деле вам не нужно «удалять» первый элемент кучи или даже последний.

Вместо этого алгоритм должен скопировать значения из первого элемента (элемента с наивысшим приоритетом) для вывода, а затем скопировать узел из «конца» массива в первую позицию при подготовке к его всплытию вниз в правильное положение. «Конец» массива указывается текущим размером кучи.

Чтобы «удалить» последний элемент массива, просто уменьшите heap_size на 1.

Я смутно припоминаю, что всплывание происходит путем проверки приоритетов дочерних элементов на движущемся элементе, а затем замены его на элемент с наивысшим приоритетом. Повторяйте это для перемещенного элемента, пока элемент не будет иметь равный или более высокий приоритет для своих дочерних элементов.

Уловка, чтобы найти потомков элемента, проста: это узлы в 2 * i и 2 * i + 1, где массив начинается с 1 вместо 0. (Было бы 2 * (i + 1) ) -1 и 2 * (1 + 1) для массивов на основе 0? Проверьте мою математику, пожалуйста. Или просто пропустите один элемент массива, чтобы упростить математику.)