Falsches Einfügen in die Warteschlange in C

Question

Hallo Ich versuche, eine einfache Warteschlange für verknüpfte Listen Priorität, wo Elemente auf der Grundlage ihrer f-Wert sortiert werden. Wenn ich die Warteschlange nach dem Einfügen einiger Elemente drucke, merke ich, dass immer nur ein Element in der Warteschlange ist (das zuletzt eingefügte). Es enthält nicht die anderen Elemente. Ich bin mir nicht sicher, was ich falsch mache.

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

Die Funktion I die Warteschlange zum Drucken verwenden ist:

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

Code-Auswertung:

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

Der obige Code die folgende Ausgabe erzeugt:

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]