Thread: Fixing my program

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    5

    Fixing my program

    Hey guys. Recently I had a homework assignment, to essentially make a stack of queues. I did complete it a couple weeks ago, and just got 100% on the assignment, but I am curious as to how I could improve my work. IE: streamline the program, so it does what it does in a "cleaner" way.

    For example, in order for me to modify the queue on the top of the stack, I had to pop it, enqueue it, and re-push it with a special push function that only works for queues popped from the stack. I was wondering if there is a way to bypass this.

    Anyway, please take a look, and have fun with it. I will post the assignment details, and the actual assignment code. I hope this can be a good learning experience for me. Thanks!

    Code:
    #include <stdio.h>
    #include <string.h>
    #define SIZE 256    // Size of the filename and event strings
    
    // Instances of this structure represent a train staion
    struct stack
    {
        struct queue* store;    // An array of queues, used to store trains
        int top;                // Index value of store.  Where the top of the stack is
        int size;               // Size of the array of queues (store)
    };
    
    // Instances of this structure represent a train
    struct queue
    {
        int* store;     // Array of integers.  Used to store the car numbers
        int front;      // Indicates where the front of the queue is 
        int back;       // Indicates where the back of the queue is
        int size;       // Size of the store array
    };
    
    // Function prototypes! Arranged by type for your convenience!
    void push(struct stack* s, struct queue item);
    void expand_stack(struct stack* s);
    void print_stack(struct stack* s);
    void print_queue(struct queue q);
    void enqueue(struct queue* q, int data);
    void dequeue(struct queue* q);
    void expandqueue(struct queue* q);
    void welcome_msg();
    
    int is_queue_empty(struct queue* q);
    int is_stack_empty(struct stack* s);
    
    struct queue* new_queue(int initsize);
    struct stack* new_stack(int initsize);
    struct queue* new_top(struct queue top);
    struct queue pop(struct stack* s);
    
    int main(void)
    {
        FILE* fin;                            // Typical file pointer
        char filename[SIZE], event[SIZE];     // The filename and event strings;  Retrived from user and file input respectively
        struct stack* station;                // The station (stack) used throughout the program
        struct queue* train;                  // The train(s) used throughout the program;  Represents the newest one to be created  
        struct queue* toptrain;               // The train on the top of our stack of trains
        int totnum, num, choice;              // Total number of events, number of cars / car number, and while loop condition, respectively
        
        welcome_msg();      // Probably the coolest welcome message ever
        
        do  // Will execute program until user chooses to quit!
        {
            printf("Enter input filename: ");
            scanf("%s", &filename);
            printf("\n");
        
            fin = fopen("input.txt", "r");      // Reads input file
        
            // Checks first value of the file.  This is used to determine how many 
            // events are scheduled, and also the initial size of the stack
            fscanf(fin, "%d", &totnum);         
        
            station = new_stack(totnum);    // Initialize a new stack;  Holds totnum elements
        
            int i; // Loop index
            for(i = 0; i < totnum; i ++)            // Reads each event in the file; Number of events specified by totnum
            {
                fscanf(fin, "%s", &event);  // Reads the event
            
                if(strcmp(event, "new_train") == 0)     // Checks to see if the event is new_train
                {
                    fscanf(fin, "%d", &num);            // Scans the number of cars, so we know how big our new queue needs to be
                
                    train = new_queue(num);             // Initializes our queue; Initially it can hold num elements
                
                    int k; // Loop index
                    for(k = 0; k < num; k++)            // Reads in each car number and adds it to the train
                    {
                        int qnum;
                        fscanf(fin, "%d", &qnum);
                        enqueue(train, qnum);           // Adds cars onto train queue; FIFO
                    }
                
                    push(station, *train);              // Pushes our new queue (train) onto the stack
                    printf("ADDED TRAIN: ");
                    print_queue(*train);                // Prints a representation of the current queue
                    printf("\n");
                    print_stack(station);               // Prints a representation of the current stack
                }
                else if(strcmp(event, "train_departs") == 0)   // If a train departs...
                {
                    if(is_stack_empty(station))     // Checks to see if stack is empty; That is, no trains can depart
                    {
                        printf("The station is EMPTY! No train departed!\n\n");
                    }
                    else
                    {
                        printf("Train departed: ");
                        print_queue(pop(station));      // Pops the stack; Prints the train that departed
                        printf("\n");
                        print_stack(station);
                    }
                }
                else if(strcmp(event, "add_car") == 0)  // If a car is to be added...
                {
                    if(is_stack_empty(station))  // An empty station means no trains to add cars to!
                        printf("The station is empty! No trains to add cars to!\n");
                    else
                    {
                        fscanf(fin, "%d", &num);
                        printf("ADD CAR: %d\n", num);
                
                        // Initializes our top train;  Pop returns the queue at the top, so it is copied to
                        // toptrain, enqueded with the car specified, and re-pushed onto the stack as toptrain
                        toptrain = new_top((pop(station)));     
                        enqueue(toptrain, num);
                
                        push(station, *toptrain);
                        print_stack(station);
                    }
                }
                else if(strcmp(event, "remove_car") == 0)   // If a car is to removed...
                {
                    if(is_stack_empty(station))     // An empty station means no trains to remove cars from!
                        printf("The station is empty! No trains to remove cars from!\n");
                    else
                    {
                        int dnum;   // The number of the car to be removed
                        
                        // Once again, pop returns the queue at the top of the stack, so we pop, copy
                        // the top queue to toptrain, dequeue toptrain, and push it back onto the stack
                        toptrain = new_top((pop(station)));
                        dnum = toptrain->store[toptrain->front];
                
                        printf("REMOVING CAR: %d\n", dnum);
                        dequeue(toptrain);
                        push(station, *toptrain);
                        print_stack(station);
                    }
                }
            }      
            
            fclose(fin);
            free(train->store);
            free(train);
            free(toptrain->store);
            free(toptrain);
            free(station->store);
            free(station);
            
            printf("Load another file? (1 = yes || 0 = no): ");
            scanf("%d", &choice);
            printf("\n");
                    
            while(choice != 1)  // Shall we go again?
            {
                if(choice == 0)
                    break;
                else
                {
                    printf("Invalid selection! Please choose again!\n");
                    printf("Load another file? (1 = yes || 0 = no): ");
                    scanf("%d", &choice);
                    printf("\n");
                }
            }
            
        }while(choice != 0);
        
        printf("Train station abandoned! Goodbye!\n");
        
        system("PAUSE");  // Pauses the shell (WINDOWS ONLY)
        return 0;
    }
    
    // Typical stack expansion function.  Makes our store array bigger.  This is here because
    // store could get filled.  Specifically, this function doubles the size of the store array.
    void expand_stack(struct stack* s)
    {
        struct queue* oldstore = s->store;  // Pointer to our store array of queues
    
        s->store = calloc(s->size * 2, sizeof(struct queue));  // Doubles the size, essentially
        
        int i;  // Loop index; Copies the store array to our new, double sized one.
        for(i = 0; i < s->size; i++)
        {
            s->store[i] = oldstore[i];
        }
        
        s->size *= 2;
        free(oldstore);
    }
    
    // Standard stack constructor.  Initsize is the size of the store array.
    struct stack* new_stack(int initsize)
    {
        struct stack* s;
        
        s = malloc(sizeof(struct stack));   // Allocate memory
        
        s->store = calloc(initsize, sizeof(struct queue));  // Create our store array
        s->top = 0;
        s->size = initsize;     // Size is same as array
        
        return s;
    }
    
    // Pushes data onto the top of the stack; LIFO; The data is a queue (train)
    void push(struct stack* s, struct queue item)
    {
        if(s->top == s->size)   // If we run out of space in the array, we need to expand
            expand_stack(s);
    
        s->store[s->top] = item;    // Top of the array becomes our item. Top is increased
        s->top++;
    }
    
    // Standard stack pop.  Removes the item on the top of the stack and returns it;
    struct queue pop(struct stack* s)
    {
        s->top--;
        return s->store[s->top];
    }
    
    // Returns 1 if the stack is empty.
    int is_stack_empty(struct stack* s)
    {
        return s->top == 0;   
    }
    
    // Prints a current representation of the stack
    void print_stack(struct stack* s)
    {
        if(is_stack_empty(s))   
        {
            printf("The station is EMPTY!\n\n");    
            return;
        }
        
        printf("Station current state: ");
        
        int i; // Loop index
        for(i = 0; i < s->top; i++)
        {
            print_queue(s->store[i]);   // Prints each train within the stack
            printf("  ");
        }
        printf("\n\n");   
    }
    
    // Standard queue initialization.  Basically the same as new_stack.  Initisize is
    // the size of the store array
    struct queue* new_queue(int initsize)
    {
        struct queue* q;
        
        q = malloc(sizeof(struct queue));       // Make some space
               
        q->store = calloc(initsize, sizeof(int));   // Store array is initsize big
        q->front = 0;
        q->back = 0;
        q->size = initsize;
        
        return q;
    }
    
    // Works similar to expandstack and for the same reasons.  The store array could
    // become full, thus it needs to be expanded.  This also doubles the size of the array.
    void expandqueue(struct queue* q)
    {
        int* oldstore = q->store;
        
        q->store = calloc(q->size * 2, sizeof(int));    // The new, double-sized store array
        
        int i;  // Loop index
        for(i = 0; i < q->size; i++)
        {
            q->store[i] = oldstore[(i+q->front) % q->size];     // Copies data to new array.  Allows for an odd number of spaces
        }
        
        q->front = 0;
        q->back = q->size;
        q->size = q->size * 2;      // Twice the size.  This makes sure size value supports the actual size
        free(oldstore);
    }
    
    // Technially, this does not check if the queue (train) is empty, but works under the same
    // principle.  What it does is check to see if the queue has only one object.  This is because
    // you can't have a train with 0 cars.  To check if the queue is truely empty, just remove the 
    // -1 from q->back.
    int is_queue_empty(struct queue* q)
    {
        return q->front == q->back-1;   
    }
    
    // Adds data to the back of the queue.  If its full, it calls expandqueue to make
    // it bigger.
    void enqueue(struct queue* q, int data)
    {
        q->store[q->back] = data;           // Object at the back becomes our data
        q->back = (q->back + 1) % q->size;  // Move the back up one position.  Also makes sure we don't exceed the size of the array
    
        if(q->front == q->back) // Is it full?  If so, double the size
        {
            expandqueue(q);   
        }   
    }
    
    // Removes the item at the front of the queue.
    void dequeue(struct queue* q)
    {
        if(is_queue_empty(q) == 1)  // Is our queue "empty" (according to Bob)? If so, theres nothing to dequeue
        {
            printf("ERROR! Car not removed because there is only ONE car left on the train!\n");
            return;
        }
        else
        {
            q->front = (q->front + 1) % q->size;    // Removes item from the front.  Makes sure we don't exceed the size of array.
            return;
        }
    }
    
    // Prints out a representation of the train.  Prints each value in the queue at the time its called.
    void print_queue(struct queue q)
    {
        int i;
        
        printf("[ ");
        for(i = q.front; i < q.back; i++)
            printf("%d ", q.store[i]);
        printf("]");
    }
    
    // Exactally the same as new_queue, but this is used when pop returns a queue, and not a pointer.
    // Function is used when we need to create and edit the train currently at the top of the stack.
    // For a more detailed explanation, see function new_queue
    struct queue* new_top(struct queue top)
    {
        struct queue* q;
        
        q = malloc(sizeof(struct queue));
        q->store = calloc(top.size, sizeof(int));
        q->front = top.front;
        q->back = top.back;
        q->size = top.size;
        
        int i;
        for(i = top.front; i < top.back; i++)
        {
            q->store[i] = top.store[i];
        }
        return q;  
    }
    
    // By far the coolest welcome message ever
    void welcome_msg()
    {
        printf("                                         (@@@)     (@@@@@)          \n"); 
        printf("                               (@@)     (@@@@@@@)        (@@@@@@@)  \n");
        printf("                         (@@@@@@@)   (@@@@@)       (@@@@@@@@@@@)    \n");
        printf("                    (@@@)     (@@@@@@@)   (@@@@@@)             (@@@)\n");
        printf("               (@@@@@@)    (@@@@@@)                (@)              \n");
        printf("           (@@@)  (@@@@)           (@@)                             \n");
        printf("        (@@)              (@@@)                                     \n");
        printf("       .-.                                                          \n");
        printf("       ] [    .-.      _    .-----.                                 \n");
        printf("     .\"   \"\"\"\"   \"\"\"\"\"\" \"\"\"\"| .--`                                  \n");
        printf("    (:--:--:--:--:--:--:--:-| [___    .------------------------.    \n");
        printf("     |C&O  :  :  :  :  :  : [_9_] |'='|.----------------------.|    \n");
        printf("    /|.___________________________|___|'--.___.--.___.--.___.-'|    \n");
        printf("   / ||_.--.______.--.______.--._ |---\\'--\\-.-/==\\-.-/==\\-.-/-'/--  \n");
        printf("  /__;^=(==)======(==)======(==)=^~^^^ ^^^^(-)^^^^(-)^^^^(-)^^^     \n");
        printf("~~~^~~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~^~~~\n");
        printf("                  Welcome to Bob's Train Station!                   \n\n");
    }

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    1. Make it portable, ie no system() calls. It's not needed.
    2. Abstract the queue to a different file, likewise for the stack. You'll see a huge code clean-up, and it will also allow you to use them in other projects / assignments.
    3. Check the result of malloc()/calloc() etc, they can fail.
    4. use size_t when dealing with string sizes / memory instead of int
    5. Don't read strings with fscanf(), scanf() etc, ie
    Code:
    fscanf(fin, "&#37;s", &event);
    Is a potential buffer overflow, try enter something larger than sizeof(event).

    There is more, but fix those first

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    5
    Thanks zacs.

    These are definitely helpful, but I am more referring to the way the program actually executes, rather than the handling.

    Different / Less clunky ways of doing what the program is supposed to do. For example, and I am curious about this: should my push function be able to work for all queues, pointers and structures alike. This way I only need one push function.

    Also, is there a way to return a pointer to the structure on top of the stack, rather than the actual structure?

    Thanks

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    To be honest, since you are now (I believe) the fourth person to post a solution (in some stage of development) to that exact same problem within the last two or three weeks, I'm tired of looking at it, so I won't get very specific. But you did say this:
    should my push function be able to work for all queues, pointers and structures alike. This way I only need one push function.
    This is really the difference between a library function and "something that gets the job done". If you want to reuse the code in another project where your stack is storing something other than a queue, then yes you will need to make it general. If your assignment had been to "create a stack ADT", then yes you would need to make in general. But to solve the problem at hand, no you don't need to make it general.

    It's a step up. It's something to consider doing (both for the benefit of having the code around the next time you need a stack, and also for the benefit of learning about handling generic data). But your immediate job is to make sure the program you turn in does what it's supposed to do.

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    5
    Quote Originally Posted by tabstop View Post
    To be honest, since you are now (I believe) the fourth person to post a solution (in some stage of development) to that exact same problem within the last two or three weeks, I'm tired of looking at it, so I won't get very specific. But you did say this:

    This is really the difference between a library function and "something that gets the job done". If you want to reuse the code in another project where your stack is storing something other than a queue, then yes you will need to make it general. If your assignment had been to "create a stack ADT", then yes you would need to make in general. But to solve the problem at hand, no you don't need to make it general.

    It's a step up. It's something to consider doing (both for the benefit of having the code around the next time you need a stack, and also for the benefit of learning about handling generic data). But your immediate job is to make sure the program you turn in does what it's supposed to do.
    Point noted. Just to make it clear, this isn't for class. Like I said, it has been submitted, and graded. Just for me to "learn." God forbid students do such a thing these days.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You should also have a function for each of stack and queue to clean up, instead of individual calls to free at the end of your main loop.

    Edit: Additionally. gcc with "-Wall -Wextra -O2" gives the following warnings:
    train.c: In function `main':
    train.c:54: warning: char format, different type arg (arg 2)
    train.c:68: warning: char format, different type arg (arg 3)
    train.c:144: warning: implicit declaration of function `free'
    train.c:172: warning: implicit declaration of function `system'
    train.c: In function `expand_stack':
    train.c:182: warning: implicit declaration of function `calloc'
    train.c: In function `new_stack':
    train.c:199: warning: implicit declaration of function `malloc'
    train.c: In function `main':
    train.c:45: warning: 'train' might be used uninitialized in this function
    train.c:46: warning: 'toptrain' might be used uninitialized in this function

    Most of this is caused by not including <stdlib.h> [Although it may be that you don't get those warnings because of other include files including the stdlib.h header file - but you REALLY should be doing that].


    --
    Mats
    Last edited by matsp; 11-05-2008 at 04:00 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  2. Can someome help me with a program please?
    By WinterInChicago in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 10:58 PM
  3. Replies: 2
    Last Post: 05-10-2002, 04:16 PM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM