A project for Data Structures and Systems programming by Brandon Kennedy during the Fall 2011 Semester.

This project was begun on 12-15-2011 and is anticipated to take 3 hours.

The point of this project is to demonstrate my knowledge of command-line arguments, queue based data structures, and selection sorting algorithms.

In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

• man page for atoi
• previous projects reguarding queues
• wikipedia on selection sorting

Through this project I am pursuing a greater knowledge of how to integrate a queue structure into any program, and combine it with powerful sorting algorithms if needed. I was hoping to throw a bunch of random concepts together, and come out with something pretty sweet that demonstrated my knowledge of those concepts.

This project will take integers from the command-line or from stdin, and sort them via a selection sort. They will then be loaded into a queue by use on enqueueing as they are sorted, and then printed from that queue by dequeueing.

State and justify the attributes you'd like to receive upon successful approval and completion of this project.

• attribute1: sorts → this program will use a selection sort algorithm
• attribute2: queue → this program will implement a queue to hold and print the sorted data.
• attribute3: command-line arguments: this is for systems programming → this program will be able to bring in data via the command line.

The first step I took was to figure out how to accept command line arguments and cast them to integer values via the atoi function.

value[i] = atoi(argv[i+1]);

After that i put in a simple stdin loop to give me my needed values.

for(i=0;i<size;i++)
{
   printf("enter value for slot %d", i)
   scanf("%d", value[i]);
}

Then i could do my processing via the value[] array whether they entered via command-line or stdin. After that i moved into my sorting algorithm that you can find in the code section below. Once i had the program running, I slipped in a queue to show how they can be used in many different circumstances. Of course i didn't need to use the queue, but it was fun to put it in. Maybe one day i'll write a swap() for linked lists so that i can write sorting algorithms for linkedlists.

1

#include<stdio.h>
#include<stdlib.h>
#include"quelist.h"
 
int main(int argc, char **argv)
{
        int i = 0;
        int j = 0;
        int size = 5; //size of the array being loaded, changes whole program to size 10, 20, 100, etc...
        int position = 0; //position of lowest value in the array
        int temp = 0; //temp variable for switching values around
        int lowval = 0; //lowest value in the array bounds
        int value[size]; //my array
        Queue *myque; //queue structure being used from a previous project, pulled with ehader file "quelist.h"
        myque = (Queue *) malloc (sizeof(Queue)); //malloc the queue
        myque -> head = myque -> tail = myque -> tmp = NULL; //initialize all parts to NULL so i know what they are doing and where they are
        if(argc < size+1) //if there isn't enough command-line arguments entered
        {
                for(i=0;i<size;i++)
                {
                        printf("Enter a value for slot %d: ", i);
                        scanf("%d", &value[i]);
                }
        }
        else //if there is enough command-line arguments
        {
                for(i=0;i<size;i++)
                        value[i] = atoi(argv[i+1]); //load the arguments into the array so that the processing for the stdin and command-line arguments
        }                                           //is the same. casted to an int via atoi().
        i = 0;
//meat of the selection sort
        while(j < size)
        {
                lowval = value[j]; //set the low value to be the first element in the array bounds
                for(i=j;i<size-1;i++)
                {
                        if(lowval > value[i+1])
                        { //if lowval is greater than the next value in the array
                                lowval = value[i+1]; //lowvalue is now the next value in an attempt to find the lowest value
                                position = i+1; //save the position of that low value
                        }
                }
                if(lowval != value[j]) //if lowvalue isnt the first position of the array bounds
                {
                        temp = value[j];
                        value[j] = lowval;
                        value[position] = temp; //bring the low value to the front
                }
                enqueue(myque, lowval); //start loading that queue!
                j++;
        }
 
        printf("This array is now sorted via a selection sort");
        for(i=0;i<size;i++)
                printf(" . %d", (dequeue(myque) -> value)); //dequeue returns a node, so we need to point to its value
        printf("\n");
        return 0;
}

</code> /* This is a simple function to enqueue a node to a queue. Accepts: A que struct containing the head, tail and a tmp node of the queue, and a character value. Returns: nothing Requires the “linkedlist.h” header file, which is in “quelist.h” */ #include“quelist.h”

void enqueue(Queue *que, char val) {

      Node *tmp1;
      tmp1 = (Node *) malloc (sizeof(Node));
      tmp1 -> value = val;

      if(que -> head == NULL)
      {
              que -> head = que -> tail = tmp1;
      }
      else
      {
              que -> head -> prev = tmp1;
              tmp1 -> next = que -> head;
              que -> head = que -> head -> prev;
      }

} </code>

/*
Deueue is a simple program to dequeue a node from a list.
Node *dequeue(Queue *)
Accepts: a queue struct
Returns: the dequeued node
*/
#include"quelist.h"
 
Node *dequeue(Queue *que)
{
        que -> tmp = que -> tail;
        if(que -> tail != que -> head)
        {
                que -> tail = que -> tail -> prev;
                que -> tmp -> prev = NULL;
                que -> tail -> next = NULL;
        }
        return (que -> tmp);
}

#ifndef QUE_LIST_H
#define QUE_LIST_H
#include"linkedlist.h"
 
struct queue{
        struct node *head;
        struct node *tail;
        struct node *tmp;
};
typedef struct queue Queue;
 
Node *dequeue(Queue *);
void enqueue(Queue *, char);
 
#endif

contains the node structure

Again, if there is associated code with the project, and you haven't already indicated how to run it, provide a sample run of your code:

lab46:~/src/DataS$ ./selsort
Enter a value for slot 0: 1
Enter a value for slot 1: 3
Enter a value for slot 2: 6
Enter a value for slot 3: 4
Enter a value for slot 4: 2
This array is now sorted via a selection sort . 1 . 2 . 3 . 4 . 6
lab46:~/src/DataS$

lab46:~/src/DataS$ ./selsort 4 8 9 5 1
This array is now sorted via a selection sort . 1 . 4 . 5 . 8 . 9
lab46:~/src/DataS$

I think i am getting the hang of this coding thing. I am learning at least 2 new powerful functions a week, and many other tiny ones. And I am able to implement them in a program when i need them without much trouble, like the atoi(). I used it here to cast command-line arguments saved as char ** to integers saved in a regular integer array, heck yes! that way i was able to save stdin or command line args to an array and then do the same processing reguardless of the way i got the data.

In performing this project, the following resources were referenced:

• previous queue projects/libraries
• the c programming quide
• my mind
• man page for atoi()