C의 우선 순위 대기열

Question

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); 
    } 

} 

내가 작성한 우선 순위 대기열이지만 코드를 테스트하면 실제로 함수에 요청하기 전에 대기열이 마지막 색인에 노드를 자동으로 추가합니다.

주 함수에서 노드를 두 개의 값으로 만들었지 만 노드를 우선 순위 큐 배열에 대기열에 넣지 않았습니다. 배열은 자동으로 노드를 마지막 인덱스에 추가합니다. 제발 도와주세요. 사전에

감사합니다. 대기열 initialize_Q(Prio_Q, 11);을 초기화 할 때 당신은 크기 10의 배열을 초기화하는

Answer 1

C;

main()에서 :

struct node Prio_Q[10]; 

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

참고가 size와 initialize_Q()를 호출하는 코드에 특정 문제가있는 범위를 벗어날 언어는 하지 도움 당신은 배열 액세스를 방지 않습니다 11입니다.

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이 변수를 사용한다 : 그것은 당신의 for 루프가 Prio_Q 배열의 끝을 넘어 배열 액세스 의 원인이됩니다 의미. 그러면이 같은 작은 버그를 작성할 확률이 크게 줄어 듭니다.

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의 경우에도 배열의 끝을 넘어 액세스했습니다.

Answer 2

[인덱스는 0,1, ..., 9, 문에 struct node Prio_Q[10];

는하지만 크기 11 초기화 : [0,1 , ..., 10]. 할당 된 배열에서 넘쳐 흐르고 있습니다! 나중에 C 배열에 그 0에서 색인 기억 for(int m = 0; m < size+1; m++)

의 요소를 인쇄 할 때

마찬가지입니다, 그래서 당신은 n 요소가있는 경우, 귀하의 인덱스는 [0,1,...,n-1] 있습니다 - 그래서 당신의 반복 i = 0에서 i < n 동안해야 .