Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I would prefer if more experienced users could give pointers on how I can optimize and think better when writing code.

Using Homework Questions as reference, as this is a homework related question. This should fall into the second category. I know the code is working and that no memory is leaking. The implementation nor the queue.h can not be changed.

queue.h:

#define MAX_PRIO 100
typedef const char Datatyp;

#ifndef QUEUE_H
#define QUEUE_H

struct Qelement {                           // type of a queue
    struct Qelement *next;                  // pointer to next element
    int prio;                               // order in queue
    Datatyp *dataptr;                       // pointer to data
}; 

typedef struct Qelement *Queue;

queue.c: (This is were feedback is wanted)

// creating an empty queue
Queue new_queue ()
{
    Queue q = (Queue)malloc(sizeof(struct Qelement));
    q->next = NULL;
    q->prio = MAX_PRIO;
    q->dataptr = NULL;  
    return q;
}

// adding a new element to queue based on priority
// higher priority means earlier in queue
void add (Queue q, int priority, Datatyp *d)
{
    // initiation
    Queue previous = q;
    Queue element = (Queue)malloc (sizeof(struct Qelement));
    Queue tmp = NULL;

    while (priority <= previous->prio)
    {
        if (previous->next != NULL)
        {
            tmp = previous;
            previous = previous->next;
        }
        else if (tmp != NULL)
        {
            tmp = previous;
            previous = previous->next;
            break;
        }
        else
        {
            break;
        }       
    }

    element->prio = priority;
    element->dataptr = d;

    if (tmp == NULL)
    {
        element->next = NULL;
        previous->next = element;
    }
    else
    {
        element->next = previous;
        tmp->next = element;
    }
}

The code is then used along these lines. (This part can not be changed)

int main () {
    const char *daniel = "Daniel";
    const char *lisa = "Lisa";
    const char *a[] = {"Kalle", "Olle", "Eva", lisa, "Stina", 
                      "Peter", "Anna", daniel, "Johan", "Maria"};

    Queue q = new_queue();
    int i;

    for (i=0; i<10; i++) {
        add(q, i%4, a[i]); 
    }
}
share|improve this question
    
typedef const char Datatyp; Datatyp... is that a typo, or something you can't change? –  Corbin Feb 12 at 21:17
    
Something I can't change. I can't see any reason for having it. My teachers word is my law. –  Emz Feb 12 at 21:20
3  
Just a tiny note -- by convention, the method to add items to a queue is typically called enqueue and to remove is called dequeue. These are analogous to the push and pop conventions of a stack. –  Roger Feb 12 at 21:27
    
Tell me about it, if I could change them, I would. Wasn't easy finding material on the topic because of this standard. –  Emz Feb 12 at 21:49
    
typedef struct Qelement *Queue; To hide a pointer behind a typedef is considered very bad practice, because it makes the program bug-prone and hard to read. If this comes from your teacher, be aware that they are teaching you bad programming practice... –  Lundin Feb 13 at 8:50

1 Answer 1

up vote 5 down vote accepted
  1. Your variable's names confused me; I'd suggest renaming 'previous' to 'current', and 'tmp' to 'previous'.

  2. You don't do anything sensible if malloc fails.

  3. The following ...

    else if (tmp != NULL)
    {
        tmp = previous;
        previous = previous->next;
        break;
    }
    else
    {
        break;
    }       
    

    ... could be rewritten as ...

    else
    {
        if (tmp != NULL)
        {
            tmp = previous;
            previous = NULL;
        }
        break;
    }
    
  4. IMO you should ignore the alleged priority assigned to the head q element (because you never want to put anything in front of it).


1st version

In summary you could rewrite it to be something like this:

bool add (Queue q, int priority, Datatyp *d)
{
    // initiation
    Queue element = (Queue)malloc (sizeof(struct Qelement));
    if (element == NULL)
        return false;
    element->prio = priority;
    element->dataptr = d;

    // loop until end of list or higher priority than next item
    for (; (q->next != NULL) && (q->next->prio >= priority); q = q->next)
    { } // an empty statement

    // insert element
    element->next = q->next;
    q->next = element;
    return true;
}

Advantages of this version over your implementation:

  • No danger of adding in front of the first, passed-in q element, even if the passed-in priority is greater than MAX_PRIO
  • No extra local variables (you have 2: tmp and previous)
  • No if or else statements (you have 5)
  • It's obvious what the algorithm is (search the list after the first node until you find the right spot, then insert into the list there)

2nd version

It's not clear whether your Queue new_queue() is part of the code which we're allowed to review.

Assuming that we are allowed to review/change that, I would add, "**Don't create "first element" which represents (contains a first pointer to) the queue: instead the queue should be represented by a pointer to the first real element."

Your first node (allocated using new_queue) might be what's called a "sentinel node" (see references here and here). It's also possible to create a queue without using a sentinel node: the "queue" is simply a pointer to the first node (instead of being a pointer to a node which contains a pointer to the first real node).

void add (Queue* qptr, int priority, Datatyp *d)
{
    // initiation
    Queue element = (Queue)malloc (sizeof(struct Qelement));
    element->prio = priority;
    element->dataptr = d;

    // get first element of queue
    Queue q = *qptr;
    if ((q == NULL) // queue was empty
        || (priority > q->prio)) // higher priority than first queue item
    {
        // insert at front of queue
        element->next = q;
        // caller's qptr now points to the new first node
        *qptr = element;
        return;
    }

    // else insert later in the queue using the same code as above    
    for (; (q->next != NULL) && (q->next->prio >= priority); q = q->next)
    { }

    // insert element
    element->next = q->next;
    q->next = element;
}

... used like this ...

int main () {
    const char *daniel = "Daniel";
    const char *lisa = "Lisa";
    const char *a[] = {"Kalle", "Olle", "Eva", lisa, "Stina", 
                      "Peter", "Anna", daniel, "Johan", "Maria"};

    // not q = new_queue()
    // instead let q be pointer to first real node
    // and q is null represent an empty list
    Queue q = NULL;

    for (int i=0; i<10; i++) {
        // pass Queue* qptr = &q (address of queue)
        // so that add can modify the value contained in q
        // (i.e. modify the node to which q is pointing)
        add(&q, i%4, a[i]); 
    }

    // q is now a pointer to the first element
}

Sadly, I can not change add to be a bool either. Is there any other way of handling it (except of very obscured ones) without changing add to a bool?

Some C conventions are:

  • return int (often 0 for success and -1 for failure)
  • return something useful like 'Queue' (the most recently-added element) or 0 (if a new element couldn't be created
  • throw an exception (if it's C++)
  • Include <stdbool.h>
  • Ignore the fact that malloc might fail.

Tell me about it, that is how I did it at first, and it turned out that the main function gave me a billion errors because apparently the first element of the queue should only be a pointer to the first real element.

I tested the above code by adding the following statement to the end of main:

// q is now a pointer to the first element

for (;q;q=q->next)
{
    printf(q->dataptr);
    printf("\r\n");
}

It generated the following output (which I think is correct):

Lisa
Daniel
Eva
Anna
Olle
Peter
Maria
Kalle
Stina
Johan
share|improve this answer
    
I will be trying this tomorrow. Sadly, I can not change add to be a bool either. Is there any other way of handling it (except of very obscured ones) without changing add to a bool? I almost want to show the teacher your first comment. –  Emz Feb 12 at 23:39
    
Tell me about it, that is how I did it at first, and it turned out that the main function gave me a billion errors because apparently the first element of the queue should only be a pointer to the first real element. My getFirstelement function is sexy... return q->next->next; regarding the add by reference part, I was told that on numerous different places now... makes one wonder what I am being taught in school. –  Emz Feb 12 at 23:43
    
@Emz I updated my answer with various options for a return code, and some test results. –  ChrisW Feb 12 at 23:55
    
As I thought, I have to ignore it. Last question! Can you provide some reliable source which I can reference to when I talk to the teacher about the structure of how to implement a more standard queue? So the teacher might share that with the other students. I now know how it is supposed to be done, but the other students do not. Must just want to get done with the exercise and get on to the next. –  Emz Feb 13 at 9:41
    
Rereading your code again I see you added "add at front" which according to the specifics of the exercise should never happen, as the first queue element is initialized with the MAX_PRIO –  Emz Feb 13 at 10:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.