不正确的插入队列C

Question

您好我想制作一个简单的链表优先级队列，其中的元素是根据它们的f值进行排序的。当我在插入几个元素后打印队列时，我注意到队列中总是只有一个元素（最近插入的元素）。它不包含其他元素。我不确定我做错了什么。

int insertPriorityQueue(struct queueNode* head, struct randomNode* e) 
{ 

struct queueNode* newNode = (struct queueNode*)malloc(sizeof(struct queueNode)); 

newNode->element = e; 

newNode->next = NULL; 

if(head==NULL) 
{ 
    head = newNode; 
} 

else if(head->element->f > e->f)  
{ 
     newNode->next = head; 
     head = newNode; 
} 

else 
{   
     struct queueNode* temp1 = head; 
     struct queueNode* temp2 = NULL; 

     while(temp1!= NULL) 
     { 
      if (temp1->element->f > e->f)    
     { 
        newNode->next = temp1; 
        temp2->next = newNode; 
      } 
      temp2 = temp1; 
      temp1 = temp1->next; 
     } 

     if(temp2==NULL) 
     { 
     head->next = newNode; 
    } 

     else if(temp1==NULL) 
    { 
     temp2->next = newNode; 
    } 
} 

printQueue(head); 
return 1; 
} 

我用于打印队列的功能是：

void printQueue(struct queueNode* head) 
{ 
    struct queueNode* temp = head; 
    printf("\n Queue: "); 
    while(temp!=NULL) 
    { 
    printf("[%0.2f]”,temp->element->f); 
     temp = temp->next; 
} 
} 

Answer 1

代码评价：

// It is appreciated by answerers if question code is a complete 
// program that can be compiled and executed to demonstrate the 
// problem. In this case, I will assemble a complete program as 
// the answer... 
#include <stdio.h> // printf(); 
#include <stdlib.h> // malloc(); 
#include <string.h> // memset(); 
#include <errno.h> // errno 

// In the future, the question should provide referenced structures. 
// I'll guess at it for demonstration purposes: 
typedef struct randomNode 
    { 
    double f; 
    } randomNode_t; 

typedef struct queueNode 
    { 
    struct queueNode *next; 
    randomNode_t  *element; 
    } queueNode_t; 

void printQueue(struct queueNode* head) 
    { 
    struct queueNode* temp = head; 

    printf("Queue: "); 
    while(temp!=NULL) 
     { 
     printf("[%0.2f]",temp->element->f); 
     temp = temp->next; 
     } 
    printf("\n"); 
    } 

//int insertPriorityQueue(struct queueNode* head, struct randomNode* e) 
// In order for this function to be able to change the head, 
// it must be supplied the address of head when called. 
// Example: rc = insertPriorityQueue(&head,... 
// Hence, a chage is required to the function definition: 
int insertPriorityQueue(struct queueNode **head, struct randomNode *e) 
    { 
// struct queueNode* newNode = (struct queueNode*)malloc(sizeof(struct queueNode)); 
// It is not nessisary to cast the void pointer value returned by malloc(). 
    struct queueNode *newNode = malloc(sizeof(struct queueNode)); 
    struct queueNode* temp1 = *head; 
    struct queueNode* temp2 = NULL; 

// Always check to see if malloc() failed. 
    if(!newNode) 
     { 
     fprintf(stderr, "malloc() reports: %d %s\n", errno, strerror(errno)); 
     goto CLEANUP; 
     } 

// The malloc() function does not "zero-out" the allocated memory, 
// so the following line will wipe the entire structure to zeros. 
    memset(newNode, 0, sizeof(*newNode)); 

// Flaw here if e changes from each call to this function. 
// newNode->element = e; 
// This is better... 
    newNode->element = malloc(sizeof(newNode->element)); 
    if(!newNode->element) 
     { 
     fprintf(stderr, "malloc() reports: %d %s\n", errno, strerror(errno)); 
     goto CLEANUP; 
     } 

    memcpy(newNode->element, e, sizeof(newNode->element)); 

// newNode->next is already NULL, due to the above memset(). 
// newNode->next = NULL; 

    /* Check for empty list. */ 
// if(head==NULL) 
//  Since head is now a pointer to a pointer, I would change this line to: 
    if(*head == NULL) 
     { 
// head = newNode; 
//  Now, given you have a pointer to the head value (outside this function)... 
//  you can actually change where the head is pointing. 
     *head = newNode; 
//  Now that there is nothing more to do, just bug-out. 
     goto CLEANUP; 
     } 

    /* Check for head replacement. */ 
// else if(head->element->f > e->f) 
// Now you can simplify the code by removeing the "else" statement. 
// ...and don't forget to dereference **head... 
    if((*head)->element->f > e->f) 
     { 
     newNode->next = *head; 
     *head = newNode; 
//  Again, here you are finished. Remove some complexity by just bugging-out. 
     goto CLEANUP; 
     } 

    /* Determine where this node belongs in the list, and place it there. */ 
// Now you can further simplify the code by removing this "else" statement.  
// else 
    while(temp1!= NULL) 
     { 
     if(temp1->element->f > e->f) 
     { 
     newNode->next = temp1; 
     temp2->next = newNode; 
// Flaw in question code; should have "bugged-out" here.   
     goto CLEANUP;   
     } 

     temp2 = temp1; 
     temp1 = temp1->next; 
     } 

    if(temp2==NULL) 
     { 
     (*head)->next = newNode; 
// Just bug-out, and eliminate the else below. 
     goto CLEANUP; 
     } 

    if(temp1==NULL) 
     { 
     temp2->next = newNode; 
     goto CLEANUP; 
     } 

CLEANUP: 

    printQueue(*head); 
    return 1; 
    } 

int main(void) 
    { 
    int rCode = 0; 
    queueNode_t *head = NULL; 
    randomNode_t e; 

    e.f = 8; 
    insertPriorityQueue(&head, &e); 

    e.f = 5; 
    insertPriorityQueue(&head, &e); 

    e.f = 4; 
    insertPriorityQueue(&head, &e); 

    e.f = 3; 
    insertPriorityQueue(&head, &e); 

    e.f = 7; 
    insertPriorityQueue(&head, &e); 

    e.f = 6; 
    insertPriorityQueue(&head, &e); 

    return(rCode); 
    } 

上面的代码产生以下输出：

Queue: [8.00] 
Queue: [5.00][8.00] 
Queue: [4.00][5.00][8.00] 
Queue: [3.00][4.00][5.00][8.00] 
Queue: [3.00][4.00][5.00][7.00][8.00] 
Queue: [3.00][4.00][5.00][6.00][7.00][8.00]