初學者從結構數組中刪除第一個元素（C）

我有一個結構數組（實際上它是一個按優先級排序的堆數組）。初學者從結構數組中刪除第一個元素（C）

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？

來源

2011-08-14 coril

是的，如果你的數組允許有空元素，你可以簡單地做p [0] = NULL。請澄清你的意思是「刪除」。就像現在這樣，你的remove（）函數索引超出了數組的邊界並拷貝垃圾。 –

當我做p [0] = NULL;從類型'void *'分配類型'person'時出現錯誤：不兼容類型。通過刪除，我基本上想通過與最後一個交換來擺脫我的數組的第一個元素。 – coril

如果使用C99編譯器進行編譯，可以使用'p [0] =（person）{「anonymous」，42};'或者更喜歡：'p [0] =（person）{ 「」，0};否則你需要分別設置每個結構成員：'p [0] .name [0] = 0; p [0] .priority = 0;' – pmg

數組是連續的內存塊。所以，如果你想刪除的第一個元素，你有一個元素，將所有對開始下列元素：

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

這是非常低效的。彈出第一個元素是一個堆的常見操作，所以你通常會這樣做 - 刪除數組的最後一個元素 - 這非常快，因爲數組的其他元素不受影響。

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簡單得多。

來源

2011-08-14 21:54:13 Antti

我的老師提到這就是爲什麼我用最後一個非空元素交換第一個元素，然後相應地修復堆。但在修復之前，我不知道如何「清除」最後一個元素的位置，以便它是「空的」。 – coril

我編輯了我的答案。 – Antti

這聽起來像你正在嘗試實施堆排序。您實際上並不需要「移除」堆的第一個元素，甚至是最後一個元素。

相反，該算法是複製第一個元素（具有最高優先級的元素）的值以輸出，然後將節點從數組的「結尾」複製到第一個位置以準備冒泡它進入正確的位置。數組的「結尾」由當前heap_size指示。

要「刪除」數組的最後一個項目，只需1

減少heap_size我依稀記得，向下冒泡通過檢查在移動項目的孩子們的優先級，然後交換完成它與優先級最高的一個。對移動的項目重複此操作，直到項目與其子項的優先級相同或更高。

找到項目的子項的訣竅很簡單：它們是2 * i和2 * i + 1處的節點，其中數組從1開始而不是0。（對於基於0的陣列，它會是2 *（i + 1）-1和2 *（1 + 1）嗎？請檢查我的數學，或者只是浪費陣列中的一個元素來保持數學簡單。）

來源

2011-08-15 00:50:34 UncleO

初學者從結構數組中刪除第一個元素（C）

回答

相關問題