Thread: queues and linked lists

  1. #1
    Registered User
    Join Date
    May 2012
    Posts
    210

    queues and linked lists

    Okay I am lost. I have to do simple implementation of insertion and deletion of queue. The Q.h file was given to me and I have to work on that to build my code. I probably have a gazillion mistakes but please guide me. Here is my code. It is separate compilation, so:

    Q.h (HEADER FILE)
    Code:
    struct Queue_struct;
    typedef struct Queue_struct Q_type;
    
    
    /* Allocate a new Queue and initialize it to be empty. */
    Q_type *Q_new();
    
    
    /* Deallocate a Queue and free the memory */
    void Q_free(Q_type *);
    
    
    /* Print the Queue in an attractive fashion */
    void Q_print (Q_type *);
    
    
    /* error codes for errorflag returned by Q_add and Q_delete */
    #define ERROR_FULL_QUEUE 0
    #define ERROR_EMPTY_QUEUE -1
    #define EVERYTHING_OK 1
    
    
    /* add an item at the end of the Queue */
    void Q_add(Q_type *, int, int *errorflag);
    
    
    /* remove an item from the front of the Queue */
    int Q_delete(Q_type *, int *errorflag);
    
    
    /* note errorflag is passed by reference so values can change */
    Q.c FILE:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include .Q.h"
    
    
    /*********************************************************
    Implementation of the Queue ADT using a fixed size array.
    *********************************************************/
    
    
    /* Queue size must be an array of size 10 */
    #define Q_MAX_SIZE 10
    
    
    
    
    struct Q_struct
    {
      /* Pointer to the array of list elements.
         Each element is a generic pointer.
      */
      void **elements;
    
    
      /* The number of elements in the list. */
      int length;
    };
    static void _list_extend(Q_type *Q)
    {
      if (Q->elements == NULL) {
        Q->elements = malloc(sizeof(void*));
      }
      else {
        Q->elements = realloc(Q->elements,
                                 sizeof(void*) * (Q->length + 1));
      }
      if (Q->elements == NULL) {
        fprintf(stderr, "list_insert: out of memory.\n");
        exit(1);
      }
    }
    
    
    Q_type *Qnew()
    {
      Q_type *Q;
      Q = (Q_type *)malloc(sizeof(Q_type));
      Q->elements = NULL;
      Q->length = 0;
      return Q;
    }
    
    
    void Q_insert(Q_type *Q, void *data)
    {
      int i;
     _list_extend(Q);
      for (i = Q->length - 1; i >= 0; i--) {
        Q->elements[i + 1] = Q->elements[i];
      }
      Q->elements[0] = data;
      (Q->length)++;
    }
    main.c FILE:

    Code:
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include "Q.h"    /* Queue header file */
    
    
    typedef struct student {
      //  char lastName[16];
      int id;
      // float gpa;
      // char major[5];
    } student;
    
    
    
    
    
    
    
    
    void showcommands()
    {
      printf("Queue Processing Commands:\n");
      printf("==========================\n");
      printf("n : \n");
      printf("p : \n");
      printf("a : \n");
      printf("d : \n");
      printf("v : \n");
      printf("e : \n");
      printf("f : \n");
    }
    main(void)
    {
      Q_type *myQ;
      myQ = Q_new();
     char command;   // store current command
      int errorcode;      // possible error code
      int value;          // value to be inserted or returned
      float avg;          // average of queue values
    
    
      show_commands();
      printf("Queue command? ");
      scanf("%c", command);
    
    
      while (command != 'q')
        {
          switch (command)
            {
            case 'n': free(myQ);
              myQ = Q_new();
              break;
            case 'p': Q_print(myQ);
              break;
            case 'a': printf("Enter value to insert: ");
              scanf("%d", value);
              Q_add(myQ, value, &errorflag);
              if (errorflag == ERROR_FULL_QUEUE)
              printf("Queue full -- insert failed.\n");
              break;
            case 'd': value = Q_delete(myQ, &errorflag);
              if (errorflag != ERROR_EMPTY_QUEUE)
              printf("Removed value [%d]\n",value);
              else
              printf("Queue empty -- delete failed.\n");
              break;
            default: printf("Command not recognized\n");
              show_commands();
            }
          printf("Queue command? ");
          scanf("%c",command);
        }
    
    
      Q_free (myQ);
      return 0;
    }
    Last edited by kiwi101; 12-05-2012 at 06:14 PM.

  2. #2
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Nearly 150 posts - You should know what the first question we ask you is...

    What is your attempt?
    Fact - Beethoven wrote his first symphony in C

  3. #3
    Registered User
    Join Date
    May 2012
    Posts
    210
    I edited my first post there is my attempt

  4. #4
    Registered User
    Join Date
    May 2012
    Posts
    210
    I obviously need to make a print too. But I know my function prototypes in the header file do not match what is in Q.c because I don't know what the error thing is meant to be

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Code:
    #include .Q.h"
    Fact - Beethoven wrote his first symphony in C

  6. #6
    Registered User
    Join Date
    May 2012
    Posts
    210
    I've worked on it for a while and well this is what I have. So for starters, what is wrong with my insert function?
    If I get my insert function, the print one will hopefully become more clearer for me. So please forget my previous code and help me work with this new implementation of it. Thanks!

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include <string.h>
    
    
    #define MAXSIZE 10
    #define fullq 0
    #define emptyq -1
    #define ok 1
    
    
    
    
    void insertion(Q_type *,int, int *errorflag);
    void deletion();
    void display();
    
    
    struct node
    {
      int info;
      struct node *link;
    }*new,*temp,*p,*front=NULL,*rear=NULL,*errorflag;
    typedef struct node N;
    int main(void)
    {
      int ch,item;
    do
      {
        printf("\n\t\t\tLinked queue");
        printf("\n 1.Insertion");
        printf("\n 2.Deletion");
        printf("\n 3.Display");
        printf("\n 4.Exit");
        printf("\n Enter your choice : ");
        scanf("%d",&ch);
        switch(ch)
          {
          case 1:
            printf("Enter value to insert: ");
            scanf("%d", item);
            insertion(N, item, &errorflag);
            if (errorflag == fullq)
              printf("Queue full -- insert failed.\n");
    
    
            //      insertion();
            break;
          case 2:
     deletion();
            break;
          case 3:
            display();
            break;
          default:
            break;
          }
      }while(ch<=3);
    }
    void insertion(N *,int item)
    {
      // int item;
      new=(N*)malloc(sizeof(N));
      // printf("\nEnter the item : ");
      // scanf("%d",&item);
      new->info=item;
      new->link=NULL;
      if(front==NULL)
        front=new;
     else
        rear->link=new;
      rear=new;
    }
    void deletion()
    {
      if(front==NULL)
        printf("\nQueue is empty");
      else
        {
          p=front;
          printf("\nDeleted element is : %d",p->info);
          front=front->link;
          free(p);
        }
    }
    void display()
    {
      if(front==NULL)
        printf("\nQueue is empty");
      else
        {
          printf("\nThe elements are : ");
          temp=front;
          while(temp!=NULL)
            {
              printf("%d",temp->info);
              temp=temp->link;
            }
        }
    }

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Maybe?
    Code:
    void insertion(N *new,int item)
    Fact - Beethoven wrote his first symphony in C

  8. #8
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Why are you not starting the your linked list code you had the other week?
    Fact - Beethoven wrote his first symphony in C

  9. #9
    Registered User
    Join Date
    May 2012
    Posts
    210
    My last weeks linked list wasn't demonstrating queue.
    I am still getting 2 errors I dont know what they mean;

    error:expected expression before 'N' WHAT expression?
    Code:
    insertion(N *, item, &errorflag);
    error: expected ) before * token I dont even know what bracket?

    Code:
    void insertion(Q_type *,int, int *errorflag);

  10. #10
    Registered User
    Join Date
    May 2012
    Posts
    210
    do you think I could use my last weeks linked list and implement queue in their?
    Would that be easier?

  11. #11
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    Code:
    /* function declaration */
    void insertion(Q_type *,int, int *errorflag);
    What exactly is "Q_type"?

    Code:
    /* function definition */
    void insertion(N *,int item)
    {
        // ...
    }
    The number of parameters is different from your declaration. Also, "Q_type" seems to have turned into 'N'.

    And if your function declaration requires type 'N', it should probably go after you define what 'N' is.

    Code:
    /* function call */
    insertion(N, item, &errorflag);
    'N' is defined as a type - you do not provide a data type in a function call, just the variable of that type. Oh, and look up one line:

    Code:
    scanf("%d", item);
    This should be "&item".

    ---

    How much code did you write before you tried to compile it? I'm guessing all of it. This observation would also imply that things were not tested along the way, so the bugs compounded until it became the brilliant jumble we see here.

  12. #12
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Reread your notes on a queue - I think that you'll be happy to know you have already done most of the hard work with your linked list code.
    Fact - Beethoven wrote his first symphony in C

  13. #13
    Registered User
    Join Date
    May 2012
    Posts
    210
    Okay then last weeks code it is.
    I can't use my brain power on the same thing twice.
    Do you think you could change a bit of the insert function of that code (last weeks), so I could get a visual of how it looks when I implement queue, if you don't mind.
    Or else I am also doing it but I just need a clear image right now

  14. #14
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    From memory, you had a printList function?...
    Fact - Beethoven wrote his first symphony in C

  15. #15
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Oh, I understand your question now - No, I'm not doing your homework for you.
    Fact - Beethoven wrote his first symphony in C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. Replies: 8
    Last Post: 03-15-2010, 01:23 PM
  3. Replies: 1
    Last Post: 05-04-2009, 07:54 PM
  4. linked lists, stacks and queues
    By aniramg69 in forum C Programming
    Replies: 10
    Last Post: 11-29-2008, 11:58 AM
  5. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM