C中的優先級隊列

struct node 
{ 
    int id; 
    float weight; 
}; 

int find_last(struct node Prio_Q[]) 
{ 
    int i = 1; 
    while (Prio_Q[i].id != -1) 
    { 
     i += 1; 
    } 
    return i; 
} 

void initialize_Q(struct node Prio_Q[], int size) 
{ 

    int i; 

    for (i = 0; i < size; i ++) 
    { 
     Prio_Q[i].id = -1; 
     Prio_Q[i].weight = -1; 

    } 
    //printf("The queue is %f", Prio_Q[3].weight); 
} 

void enque_Q(struct node Prio_Q[], struct node node, int size) 
{ 
    int i = find_last(Prio_Q); 

    Prio_Q[i].id = node.id; 
    Prio_Q[i].weight = node.weight; 
    printf("The last index is %d\n", i); 
    heapify_up(Prio_Q, i); 
} 

void heapify_up(struct node Prio_Q[], int i) 
{  

    if (Prio_Q[i/2].weight > Prio_Q[i].weight) 
    { 
     swap_node(Prio_Q,i/2, i); 
     heapify_up(Prio_Q, i/2); 
    } 
} 

void swap_node(struct node Prio_Q[], int i, int j) 
{ 
    struct node temp; 
    temp = Prio_Q[i]; 
    Prio_Q[i] = Prio_Q[j]; 
    Prio_Q[j] = temp; 
    //printf("smething has been swapped.\n"); 
} 

int main(int argc, char *argv[]) 
{ 
    struct node node; 
    struct node Prio_Q[10]; 

    int size = 10; 
    initialize_Q(Prio_Q, 11); 

    node.id = 5; 
    node.weight = 11; 

    for(int m = 0; m < size+1; m++) 
    { 
     printf("The %dth element in Que is %d with weight %f.\n", m, Prio_Q[m].id, Prio_Q[m].weight); 
    } 

}

這是我構建的優先級隊列，但如果您測試代碼，您會看到該隊列會自動將節點添加到其最後一個索引，然後才實際詢問函數。C中的優先級隊列

在主函數中，我只讓節點有兩個值，但我並沒有將節點排入優先級隊列數組。該數組將自動添加節點到最後一個索引，任何人都可以幫助我嗎？

在此先感謝。

來源

2012-03-28 led

我發現你在函數'initialize_Q'中傳遞值11作爲大小的參數。您應該使用值10，因爲它是隊列向量的大小。主函數末尾的最後一個循環相同。 – rbelli 2012-03-29 00:11:14

歡迎來到C;漢語是不幫助你避免數組訪問外的界限，這是你的代碼的一個特殊問題：

從main()：

struct node Prio_Q[10]; 

int size = 10; 
initialize_Q(Prio_Q, 11);

注意你與size調用initialize_Q()的11。這意味着您的for循環將導致數組訪問超出你Prio_Q陣列結束：

void initialize_Q(struct node Prio_Q[], int size) 
{ 

    int i; 

    for (i = 0; i < size; i ++) 
    { 
     Prio_Q[i].id = -1;  /* BUG when i == 10 */ 
     Prio_Q[i].weight = -1;

你應該使用一個#define，enum，或const變量的數組的大小存儲在一個位置。這將大大減少寫這樣的小錯誤的機會。

你的find_last()例程應該做一些邊界檢查數組的大小。此代碼應該正常工作IFF其餘的代碼沒有錯誤。你也可以重寫這個函數，以確保它沒有走出數組的末尾。（它將如何處理完全滿陣提示：不良:)

int find_last(struct node Prio_Q[]) 
{ 
    int i = 1; 
    while (Prio_Q[i].id != -1) 
    { 
     i += 1; 
    }return i; 
}

而且爲你輸出（這應該是在它自己的功能，讓您可以在整個程序灑寬鬆）：

for(int m = 0; m < size+1; m++) 
{ 
    printf("The %dth element in Que is %d with weight %f.\n", m, Prio_Q[m].id, Prio_Q[m].weight); 
}

再次，您訪問超出陣列的末尾，當m == 10。

來源

2012-03-29 00:13:48 sarnold

要初始化大小爲10的數組[索引0,1，...，9]，在聲明中struct node Prio_Q[10];

但是當你初始化隊列initialize_Q(Prio_Q, 11);你有大小11初始化：0,1 ，...，10]。你正從分配的數組溢出！

同樣的情況，當你在以後打印元素for(int m = 0; m < size+1; m++)

請記住，C數組索引爲0，所以如果你有n元素，你的索引[0,1,...,n-1] - 讓你的迭代應該從i = 0而i < n 。

來源

2012-03-29 00:09:49 amit

啊，謝謝，這真是一個愚蠢的錯誤。 – led 2012-03-29 00:14:09

C中的優先級隊列

回答

相關問題