This obviously is the first real week of class, and we're just getting set. Our first couple classes do not cover anything outrageous, but it is interesting all the same. We're all a little rusty from the summer, so the first thing we go over is pointers in general. Basically, we wrote a simple pointer creating program to show how they work and what syntax needs to be used. An & (ampersand) in front of a variable name will give the address in memory for that variable. An * (asterisk) will give the literal value saved in that variable. For example, if there are two int variable initialized, let's say a and b, and b is initialized as a pointer (done like so: “int *b”), then we can have b point to a so that b will hold the address value of a, and will consequently display the actual value held in a when called as *b in a printf (for example). Here's our short code, for reference:

#include<stdio.h>                                                                                                                                                       

//Note may conatin errors for example purposes

// **Pointer Operators** //
//
//      * -- dereferencing operator, "the value at [x]"
//      & -- address of

int main()
{
        int a; //stores 4 bytes for storage for a
        int *b; //pointer, stores the memory address
        char c;
        a=5;
        printf("a is: %d\n", a); 
        b=&a;
        printf("*b is %d\n", *b);
        *b=123; //This sends the value 123 to a.
        printf("b is 0x%x\n", b); // %x displays hexadecimal value
        printf("&b is 0x%x\n", &b);
        printf("*b is %d\n", *b);
        printf("a is %d\n", a); 
        return(0);
}

I'm glad we spent the time on this, actually, as I was still a bit shaky on pointers from C/C++ last semester, but this certainly clarified things.

This week is where things definitely got interesting. We started to learn about an actual data structure. This data structure is called a linked-list. Basically, it is like a super-array. It is created through the use of structs to create nodes.

//This is a node struct for a singly linked list.
//This can only go forward.

struct node {                                                                   
        int value;
        struct node *next;
};
typedef struct node Node;

We can fill the value variable within the node, and move on to another node to add a new value. A simple implementation of a singly linked list is this:

#include <stdio.h>
#include <stdlib.h>

struct node {
        int value;
        struct node *next;
};
typedef struct node Node;
                                                                                                                                                                        
int main()
{
        int input, input2, i = 0;
        Node *start, *tmp, *tmp2;

        start = tmp = NULL;

        printf("Enter a value (-1 to quit): ");
        scanf("%d", &input);

        do {

                if (input == -1) 
                        break;
    
                if (start == NULL)
                {
                        start = (Node *) malloc (sizeof(Node));
                        start -> value = input;
                        start -> next = NULL;
                        tmp = start;
                }
                else
                {
                        tmp -> next = (Node *) malloc (sizeof(Node));
                        tmp -> next -> value = input;
                        tmp -> next -> next = NULL;
                        tmp = tmp -> next;
                }
         printf("Enter a value (-1 to quit): ");
                scanf("%d", &input);

        } while (input != -1);

        tmp = start;

        while(tmp != NULL)
        {
                printf("[%d] value = %d\n", i, tmp -> value);
                tmp = tmp -> next;
                i++;
        }
        return(0);
}

All this program does is accept a numeric value, add it to the current node, adding numbers until a sentinel value is given, and then display the saved value of each node in order. It might seem like a lot of code now, because it may appear to be little more than a glorified array, but there is increased functionality to be had by using this data structure. Right now, all we can do is go forward in our list, but it looks like we'll be able to fix that with a little manipulation. Matt calls it the doubly linked list. In addition to the above code, we also wrote some code that let us insert a node at a give position and delete a node at a given position.

As promised, Matt showed us how to make a doubly linked list this week. More importantly, he showed us why a doubly linked list is important. As you may imagine, this gives us more control over what we can do with our linked list.

You see, a regular singly linked list looks like this:

[Node 0] → [Node 1] → [Node 2]

Where as a doubly linked list looks like this:

[Node 0] ⇔ [Node 1] ⇔ [Node 2]

In case the imagery was not clear: A singly linked list only connects nodes by whatever node comes after the current node. A doubly linked list connects nodes both ways, meaning it is connected by the node before and after it.

Making this happen is easy enough. One of the data fields within our nodes for the singly linked list was for a node called next. Each node had a next, as seen below:

struct node {
    int value;
    struct node *next;
};

To make a doubly linked list, all we need to do is do the following:

struct node {
    int value;
    struct node *next;
    struct node *prev;
};

Just make sure that every initialized node points to an appropriate next and previous node. Doing this lets us manipulate the list in different ways with more control. For example, we can list node values backwards.

This is the week where we really worked on the first project for the course that Matt provided for us. It's a pretty nice project to start with, I think. Simply put, we're supposed to make our own linked list library implementation. In this, we're supposed to have functions that create, append, insert, copy, delete, remove, display, and search for nodes. Once the library is completed, if it is included in a code, we should be able to call these functions to work as we want.

A pointer “points” to a memory location. It represents the data type and address of the variable that it is pointing to.

[Variable] = [Variable's value]

[Pointer to variable] = [Variable's address]

The dereferencing operator (which is the asterisk, *) has to do with pointers. When used, it refers to the literal value of the thing being pointed to with the pointer.

Say that “a” is our variable and is equal to 5, and “*b” is our pointer. When we have the pointer refer to our variable, and then print out the value contained in *b, one will see that the value of a is output. This is what the dereferencing operator does.

This is another pointer operator. This operator refers to the location in memory of a variable.

Suppose variable a is stored in memory location 1 (this wouldn't be so simple in an actual program, but for the sake of a simple example, this is what is being used), and there is a pointer *b. If we wanted to point *b to a, we would have to set b equal to &a (b=&a;), as this would set the value at b to the memory address of a.

A linked list is a data structure that is a series of nodes in a specific order. Each node contains various values. Typically, it holds a value for the nodes surrounding it, making it a “linked list,” and a general value to be held for various uses. Linked lists are created using structs.

A singly linked list is a linked list that only is linked forward. That is to say that each node only contains a general value and a value referencing the node immediately following it.

[Node 0] → [Node 1] → [Node 2]

struct node {
    int value;
    struct node *next;
};

A doubly linked list is a linked list that has nodes that are connected to the nodes immediately preceding and proceeding it. This means each node contains data that references the nodes before and after it.

[Node 0] ⇔ [Node 1] ⇔ [Node 2]

struct node {
    int value;
    struct node *next;
    struct node *prev;
};

A struct is a record type that consists of a set of member objects that make up one object. Instances of a struct can be initialized, and each member object of the instance of the struct can be filled uniquely.

An object file is typically one part of an overall code that is split up by function, each function being put in to its own object code. A compiler takes each piece of object code along with the corresponding given header file to make the executable file. This makes maintaining code or working on a program in groups easier.

Header files are used to declare variables, functions, classes, etc. in a universal scope so that all programs that use the header file can access these globally declared things. Obviously, it must be included at the beginning of a program, hence the name.

malloc is a function declared in the stdlib.h library. Using malloc allows you allocate a given amount of space for an object. Example:

start = (Node *) malloc (sizeof(Node));
 
/*
From the linked list implementation-- 
this gives the node "start" the size of Node 
as it is defined in the program from which this is excerpted.
*/

sizeof is a function defined in the stdio.h library. It determines the size of a given argument data type in bytes. This is useful when allocating memory using malloc.

The free function deallocates memory previously allocated using functions like malloc, so that it may be used again for allocation. It is good practice to use so that segmentation faults are avoided. For example, if you allocated memory to variable “bob” using malloc, and you are done using that memory location at a certain point in your program, all you would have to do to deallocate it is “free(bob);”

Given that the course is all about the various data structures, it should not be out of the realm of expectation for a student at this stage to be able to create and use at least one type of data structure in a program.

To achieve this objective, I will create a program that implements a singly linked list. Each node in the list should hold a value and data that refers to the node next on the list. To observe whether or not the list of nodes is properly linked, the nodes should be output in order.

The program compiles. It accepts values in new nodes until a sentinel value is given. It prints the values of each node in order of node creation.

I feel as though I have a basic grasp of what a data structure is, and that I can effectively use a data structure in a program in a constructive manner. This knowledge will definitely allow me to complete future course objectives effectively as well.

Do I need to assign a set size to an array when I initialize it? What happens when I set the size of the array to a variable that has only been declared and not yet initialized to any value, and then try to fill the array using scanf()?

Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.

Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment.

State your rationale.

How are you going to test your hypothesis? What is the structure of your experiment?

Perform your experiment, and collect/document the results here.

Based on the data collected:

• was your hypothesis correct?
• was your hypothesis not applicable?
• is there more going on than you originally thought? (shortcomings in hypothesis)
• what shortcomings might there be in your experiment?
• what shortcomings might there be in your data?

What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made.

What is the question you'd like to pose for experimentation? State it here.

Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.

Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment.

State your rationale.

How are you going to test your hypothesis? What is the structure of your experiment?

Perform your experiment, and collect/document the results here.

Based on the data collected:

• was your hypothesis correct?
• was your hypothesis not applicable?
• is there more going on than you originally thought? (shortcomings in hypothesis)
• what shortcomings might there be in your experiment?
• what shortcomings might there be in your data?

What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made.

What is the question you'd like to pose for experimentation? State it here.

Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.

Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment.

State your rationale.

How are you going to test your hypothesis? What is the structure of your experiment?

Perform your experiment, and collect/document the results here.

Based on the data collected:

• was your hypothesis correct?
• was your hypothesis not applicable?
• is there more going on than you originally thought? (shortcomings in hypothesis)
• what shortcomings might there be in your experiment?
• what shortcomings might there be in your data?

What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made.

This week, we were introduced to the concept of the data structure known as a stack, along with the terms of FILO/LIFO and FIFO/LILO. A stack works on a first in, last out basis (FILO), which means that the last node that is sent to the stack is output/deleted first, before any other node is accessed. We wrote an example code in class (gracefully entitled “stax, yo,” or something to that effect) that runs on our doubly linked list library, assuming that it has compatible functions.

In this week, we covered the concept of a queue. It was pretty easy to understand, as as queue is kinda like the opposite of a stack, because the first element in to a queue is the first one out, instead of the last one out like a stack. Matt drew some pictures on the board to help visualize the data structure, just like he did with the linked list and the stack.

This week, we mostly sat on the idea of stacks and queues for a while, so to speak. It allowed us to get a handle on what they are and how they function better, as we were allowed to begin our stack and queue implementations (separate projects, of course!). As is such, it was relatively uneventful. Days to work on programs and understand concepts are always welcomed and useful, however, so it is okay!

This is a sample format for a dated entry. Please substitute the actual date for “Month Day, Year”, and duplicate the level 4 heading to make additional entries.

As an aid, feel free to use the following questions to help you generate content for your entries:

• What action or concept of significance, as related to the course, did you experience on this date?
• Why was this significant?
• What concepts are you dealing with that may not make perfect sense?
• What challenges are you facing with respect to the course?

Remember that 4 is just the minimum number of entries. Feel free to have more.

A function pointer works much like any other type of pointer, except that it deals with functions (as you may have guessed). A function pointer points to another function, so that when it is called, it calls the pointed to function and sends any arguments provided to the pointer function.

//Function pointer prototype
int *pointerFunction(const char *);
 
...
 
pointerFunction=printf;
(*pointerFunction)("Prints this out.");

A null pointer is any pointer with a value of zero. Because all objects used in C have an address that isn't zero, null pointers can be used by functions that return a pointer as a failure condition.

...
 
int *pointer;
pointer=NULL;
 
//That pointer is pretty null right now, I would say.
 
...

A void pointer is a pointer without a given type. In this way, it can point to any given data type when it is needed. The type that is intended to be pointed to must be declared once it is initialize, as will be shown in the example code.

#include<stdio.h>
 
int main()
{
    void *pointer;
    int integer=10;
    pointer=&integer;
    printf("\n %d \n", *(int *)pointer);
    return(0);
}

A stack is a data structure that works on a last-in-first-out basis. Manipulation of nodes (assuming the stack is using a linked list as a basis, like ours) is based on pushing and popping nodes. Nodes can only be added or removed from the top.

//Example stack code from class
 
// Include files                                                                                                                                                        
#include <stdio.h>
#include <stdlib.h>
 
// Create our node structure
struct node {
        int value;
        struct node *next;
        struct node *prev;
};
typedef struct node Node;
 
Node *stack, *top;
 
void push(int);
Node * pop();
int isEmpty();
 
// main function
int main()
{
        Node *tmp;
        int i, input;
        puts("Please enter a value (-1 to stop:): ");
        scanf("%d", &input);
        while(input != -1)
        {
                push(input);
                puts("Please enter a value (-1 to stop:): ");
                scanf("%d", &input);
        }
        while((tmp=pop())!=NULL)
        {
                printf("value: %d\n", tmp->value);
                free(tmp);
        }
 
        return(0);
}

When you push on a stack, it means that you are adding a node to the top of a stack, as that is the only way to add a node to a stack. In stack implementations, push is usually a function rather than just the abstract concept of “pushing.”

//Unconfirmed if working code as of 11/15/11
void push(int value)
{
        if (stack==NULL)
        {
                stack = (Node *) malloc(sideof(Node));
                top=stack;
                stack->next=NULL;
                stack->prev=NULL;
                tmp=stack;
                stack->value=value;
        }
        else if (stack == top)
        {
                tmp= (Node *) malloc(sizeof(Node));
                top->next=tmp;
                tmp->prev=top;
                top=top->next;
                top->value=value;
                top->next=NULL;
        }
        else
        {
                tmp=stack;
                int i=0;
                while(tmp != NULL)
                {   
                        i++;
                        tmp=tmp->next;
                }   
                tmp = (Node *) malloc (sizeof(Node));
                top -> next = tmp;
                tmp -> prev = top;
                top = top -> next;
                top -> value = input;
                top -> next = NULL;
        }
        return(0);
}

Popping is the action of removing a node from a stack. The only way to remove a node is if it is on the top of the stack, as it works on a a first-in-last-out basis, as previously stated. Popping the top node makes the next node the new top of the stack.

//Unconfirmed if working code as of 11/15/11
void pop()
{
        tmp=top;
        tmp->prev->next=NULL;
        top=top->prev;
        tmp->prev=NULL;
        free(tmp);
        return(0);
}

The top of the stack is the last element of the stack. It was put on to the stack last, and must be removed/printed first, as per the FILO/LIFO concept associated with the stack.

//Concept of pushing the old starting node
//of the stack down, with the new node 
//becoming the new top
/* From push function, see above */
 
   else if (stack == top)
        {
                tmp= (Node *) malloc(sizeof(Node));
                top->next=tmp;
                tmp->prev=top;
                top=top->next;
                top->value=value;
                top->next=NULL;
        }

Identification and definition of the chosen keyword. Substitute “keyword” with the actual keyword.

If you wish to aid your definition with a code sample, you can do so by using a wiki code block, an example follows:

/*
 * Sample code block
 */
#include <stdio.h>
 
int main()
{
    return(0);
}

Identification and definition of the chosen keyword. Substitute “keyword” with the actual keyword.

If you want to demonstrate something on the command-line, you can do so as follows:

lab46:~$ cd src
lab46:~/src$ gcc -o hello hello.c
lab46:~/src$ ./hello
Hello, World!
lab46:~/src$ 

A queue is a data structure that is almost the opposite of a stack. A stack is FILO, whereas a queue is FIFO– First in, first out. The concept of a queue is rather easy to grasp, so long as one knows what the word queue means (hint: It means line! As in, a line for food, or a movie, etc.). In a queue of people waiting for any given thing, what happens? The first person in line is dealt with first, and the last person in line has to wait for everyone in front of him to be dealt with. A stack of people waiting for said given thing would result in the last person to show up being dealt with before everyone else who had been there first.

/*
 * Sample code block
 */
#include <stdio.h>
 
int main()
{
    return(0);
}

Identification and definition of the chosen keyword. Substitute “keyword” with the actual keyword.

If you want to demonstrate something on the command-line, you can do so as follows:

lab46:~$ cd src
lab46:~/src$ gcc -o hello hello.c
lab46:~/src$ ./hello
Hello, World!
lab46:~/src$ 

Identification and definition of the chosen keyword. Substitute “keyword” with the actual keyword.

If you wish to aid your definition with a code sample, you can do so by using a wiki code block, an example follows:

/*
 * Sample code block
 */
#include <stdio.h>
 
int main()
{
    return(0);
}

State the course objective; define what that objective entails.

State the method you will use for measuring successful academic/intellectual achievement of this objective.

Follow your method and obtain a measurement. Document the results here.

Reflect upon your results of the measurement to ascertain your achievement of the particular course objective.

• How did you do?
• Room for improvement?
• Could the measurement process be enhanced to be more effective?
• Do you think this enhancement would be efficient to employ?
• Could the course objective be altered to be more applicable? How would you alter it?

Can you use the sizeof() function on a file you have referenced in a program?

Recently, we implemented a couple programs that made use of files. We used sizeof() in one of these programs in order to make a reversed copy of the Lab46 MotD. This made us wonder whether or not you could use sizeof() on an opened file within a program.

Given that the value of the open file (all of its contents) will be referenced with a pointer, sizeof() will return the size of the referenced file.

I will write a simple implementation using various file manipulation functions (fopen, fprintf, etc.) that will open a file (for simplicity's sake, I will use /etc/motd) that will be referenced by a FILE pointer. I will then print the returned value of sizeof() when the FILE pointer is provided as an argument. I will check the size of /etc/motd manually using ls in terminal to verify my results.

/*                                                                
        sizeof() on a file Experiment
Simple implimentation of file functions to determine
if the sizeof() function can be used on a file.
 
        Fall 2011 Data Structures
*/
 
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
        FILE *fPtr; //file pointer
        fPtr = fopen("/etc/motd", "r");
        printf("\nSize of /etc/motd: %lld\n\n", sizeof(*fPtr));
        fclose(fPtr);
        return(0);
}

lab46:~/src/data$ ls -l /etc/motd
lrwxrwxrwx 1 root root 13 Jun 14  2010 /etc/motd -> /var/run/motd
lab46:~/src/data$ ls -l /var/run/motd
-rw-r--r-- 1 root root 1422 Oct 29 00:01 /var/run/motd
lab46:~/src/data$ ./fileexperiment

Size of /etc/motd: 216

lab46:~/src/data$ 

Size of /etc/motd according to ls: 1422 bytes

Size of /etc/motd according to sizeof(): 216 bytes

I do not believe my hypothesis is completely correct. sizeof() did return a value when provided the file, but it did not match the size provided by ls. I think there is quite a bit that I did not realize about the file functions and sizeof() that lead to these results. Out of curiosity, I checked to see what octal 216 is in decimal, and it turns out to be 142, but I think that is coincidence more than anything. Ultimately, it may be an error in the logic or use of these functions that lead to the mismatch, so sizeof may very well be able to do what I thought it would.

My conclusion based on the scope of this experiment is that sizeof will not return an accurate file size of a given file referenced by a FILE pointer.

Which has priority in the condition in a while loop– the assignment operator, or the not-equal-to operator?

While writing a program with the class to demonstrate a concept, we came across an issue with a while loop that had a condition that had both and assignment operator and a not-equal-to operator. After placing some parentheses here and there, the problem was fixed, but I'd like to know which operator has preference in this.

I think that the operator that occurs first in the condition will have precedence. This is how it appears to me most of the time when I am using a while loop.

I will write a small program that will have various while loops in it to demonstrate what happens when each operator occurs first. I will also have versions of these test loops with properly parenthesized conditions as a sort of control. From the results of these loops, I should be able to tell whether or not one has a precedence over the other, and which one has the precedence, if there is one.

/*                                                                                   
 
        "=" vs. "!=" in a while loop experiment
        Fall 2011 Data Structures
 
*/
 
 
 
#include<stdio.h>
 
int main()
{
        int first=1, second, i=6; //variables for use in the loops
        printf("\n\n[Assignment first, no parenthesis.]\n");
        while(second=i-first != first)
        {
                printf("\nSecond is not equal to first. first: %d, second: %d\n", first, second=i-first);
                i--;
        }
        i=6;
        printf("\n\n[Assignment first, parenthesis.]\n");
        while((second=i-first) != first)
        {
                printf("\nSecond is not equal to first. first: %d, second: %d\n", first, second=i-first);
                i--;
        }
        i=6;
        printf("\n\n[Not-equal-to first,  parenthesis.]\n");
        while(first != (second=i-first))
        {
                printf("\nSecond is not equal to first. first: %d, second: %d\n", first, second=i-first);
                i--;
        }
        return(0);
}   

lab46:~/src/data$ ./precedenceexp


[Assignment first, no parenthesis.]

Second is not equal to first. first: 1, second: 5

Second is not equal to first. first: 1, second: 4

Second is not equal to first. first: 1, second: 3

Second is not equal to first. first: 1, second: 2


[Assignment first, parenthesis.]

Second is not equal to first. first: 1, second: 5

Second is not equal to first. first: 1, second: 4

Second is not equal to first. first: 1, second: 3

Second is not equal to first. first: 1, second: 2


[Not-equal-to first,  parenthesis.]

Second is not equal to first. first: 1, second: 5

Second is not equal to first. first: 1, second: 4

Second is not equal to first. first: 1, second: 3

Second is not equal to first. first: 1, second: 2
lab46:~/src/data$ 

Assignment, no parenthesis: operates as expected

Assignment, parenthesis: operates as expected

Not-equal-to first, no parenthesis: Not shown, would not compile, syntactical error

Not-equal-to first, parenthesis: same as assignment

My hypothesis was …correct, in a sense. Maybe? It did not matter what order they appeared in, but the assignment operator could not be to the right of the not-equal-to operator without parenthesis, or else it would not compile. So, in a sense, the assignment operator needs to appear first (as long as there are no parentheses and there is only the need for one assignment operator). The best analysis I can provide is that I did not choose a very good experiment here, despite having learned something.

Well, I've discovered that a part of a condition for a loop featuring an assignment operator without parentheses must be to the left of the not-equal-to (or any other comparison) operator.

What happens when you give a file utilizing program (such as filestuff.c, described here shortly) a directory rather than a text file?

In class, we wrote a file function utilizing program (which I named filestuff.c in my own lab46 directories) that took /etc/motd and displayed it and manipulated it in various ways. The question was raised as to what would happen if we gave our program a directory, and it sounded suspiciously like an experiment. Inquiring minds demand to know.

My hypothesis is that the program will output a lot of meaningless junk characters. An alternate hypothesis would be that the names of all the files contained in the directory will be output, but I am sticking with my first hypothesis.

The experiment is simple: switch the file in the program already (/etc/motd) with a directory, and observe the results.

/*
filestuff.c before.                                                                  
*/
 
#include <stdio.h>
 
int main()
{
        FILE *fPtr; //file pointer
        char value;
        fPtr = fopen("/etc/motd", "r");
        while((value=fgetc(fPtr)) != EOF)
        {
                printf("%c", value);
        }
        fclose(fPtr);
        return(0);
}

/*
filestuff.c after                                                                  
*/
 
#include <stdio.h>
 
int main()
{
        FILE *fPtr; //file pointer
        char value;
        fPtr = fopen("~/src/data", "r");
        while((value=fgetc(fPtr)) != EOF)
        {
                printf("%c", value);
        }
        fclose(fPtr);
        return(0);
}

lab46:~/src/data$ ./fileexp
Segmentation fault
lab46:~/src/data$ 

…Welp.

Well, my hypothesis was not correct. I suppose a segmentation fault is not surprising, given the nature of the program, however. It could be that there is a suitable code using these file functions that could handle a given directory in a way like I predicted, but this program obviously is not suited for it.

filestuff.c is not a suitable program when it comes to trying to use a directory in place of a text file. It results in a segmentation fault.

This week, we covered the concept of the data structure called a tree. I rather like the idea of a tree, and find it to be one of thew simplest data structure concepts we've covered thus far. The idea of a tree follows the general outline of a linked list. The first node in this list holds an initial value, against which all new values will be compared against. Once a new value is entered, if it is greater than the original value, then it is sent to the designated “side” of the tree list, and sent to the other “side” if it is less. These sides, in our examples, are explained to be the “next” and “prev” of the original node. For example– a value is given for the “start” node, and it is 9. The next value is given, and it is 11– this becomes start→next. Another value is given, and it is 8, making it start→prev. One more value is given, and it is 10. This becomes start→next→prev. Some people had trouble with the concept, but it came rather easily to me, I think. It's okay though, there will always be one concept that will be hard to grasp initially regardless of what it is.

In class this week, we went over a program that makes use of the process ids (PIDs) of various programs. In order to work, it needs the unistd.h library included. Basically, it takes the process id of the program and assigns it to one variable, breaks from the function, forks to create a new process id for the first element in an array to be assigned, then assigns a new process id to the remaining array elements while breaking each pid after each iteration. It was a nice exercise to show us how to use the process ids on a system in a program.

#include<unistd.h>                                                                                                                                              
 
#include<stdio.h>
 
/*
 
11/14/11
Process ID examples
 
*/
 
int main()
{
        int i, j;
        pid_t me, them[10];
        me=getpid();
        printf("Parent process ID is %hu\n", me);
        for(i=0;i<10;i++)
        {
                if(getpid()==me)
                {
                        them[i]=fork();
                }
                else
                {
                        break;
                }
        }
        if(me==getpid())
        {   
                sleep(20);
                for(i=0;i<10;i++)
                {   
                        wait(j);
                }   
        }   
        else
        {   
                printf("I am child %d, my PID is %hu\n", i,getpid());
                sleep(i+1*10);                                                                                                                                          
                printf("Child %d is done\n", i);
        }
        return(0);
}

We only had one class this week, as it is the week of Thanksgiving break. As is such, no one was really motivated to do much in class. Unless it had to do with watching Troll 2, which seemed to motivate people enough to do just that. While it was an enjoyable experience to share with everyone as we all laughed, it also caused a bit of an existential crisis– How could something so horrible actually exist? How did this actually get released as an actual motion picture?

On an actual program related note– I've finished (or just about finished) 3 projects– doubly linked list library, stack library and queue library. The portfolio reports just need to be written, is all. The tree library and implementation should be done soon, and I don't anticipate doing the other 3 projects will be much of an issue. I'm going to make the code for a deck of cards for one (I think). I'm also thinking about how the logic for tetris can be done using linked lists, but I'm not sure how I'd get that done in two weeks, all things considered. I'll have to keep them simple, yet effective in terms of being a project.

This week is also relatively uneventful. At this point, I have half of my fourth project done, the binary tree library and minor implementation. The opus is obviously due this week, so that will take up most of my programming work time. In class, though, Matt let us know that the EOCE is released. It appears to be simpler than past EOCEs, probably due to the fact that our opus and projects take a lot of work. Not that I'm complaining! It definitely all seems manageable, and I, for one, am glad to have everything that needs to be done laid before me.

A queue overrun happens when a program is manipulating a queue data structure that is full, and the program tries to add an element to the queue. Since the queue is full, adding another element makes it “overrun,” hence the term “queue overrun.”

A queue underrun is the opposite of an overrun. It occurs when a queue is empty and the program in use attempts to remove another element from the empty queue. Obviously, there is nothing there to remove, so an underrun occurs.

A binary tree is a type of data structure, based off of the concept of a linked-list in our class examples. The tree is dependent on a sorting algorithm that compares a given node with the nodes in the tree already. First, a number is given to the tree. This is the first parent node, the node which all subsequent nodes will be compared to. With the next values, if a value is greater than this node, it goes to one “side” of the tree, and the other side if it is lesser. This process continues for as long as needed. A tree is useful because the algorithm that creates it can be used to search for values, and the creation process leaves a tidy ordered list of values.

A tree node is simply an element in a binary tree style linked list. There are two types of these nodes– parent and child nodes. Each node can have two other nodes attached to it as their “next” and “prev,” to use terminology from our class. The tree nodes make up the body, so to speak, of the tree data structure.

//The code for the node structure of a tree.
 
struct node {
        int value;
        struct node *next;
        struct node *prev;
};
typedef struct node Node;
 
Node *start, *tmp, *tmp2;

A tree parent node is a node in a tree that has one or two children nodes attached to it. The parent node can either have a next, a prev, or a next and a prev, but no more than that, because a binary tree is being used.

/*
 
start -- the original parent node
start->next -- child node to start, greater than start, parent to start->next->next and start->next->prev
start->prev -- child node to start, less than start, parent to start->prev->next and start->prev->prev
 
*/

Identification and definition of the chosen keyword. Substitute “keyword” with the actual keyword.

If you want to demonstrate something on the command-line, you can do so as follows:

/*
 
start -- the original parent node
start->next -- child node to start, greater than start
start->prev -- child node to start, less than start
start->next->next -- child to start->next, greater than parent
start->next->prev -- child to start->next, less than parent
 
*/

Insertion is the process of inserting a node in to an already established instance of a data structure, such as a freshly created linked list within a program. An insertion function takes a given value and places it in a given place. Code for an insertion function may look something like the following–

int insert()
{
        // Insert a new node
        int i=0;
        printf("Enter node position to insert before: ");
        scanf("%d", &input);
 
        tmp = start;
        for(i=0; i<input; i++) //position tmp at node to insert before
        {
                tmp = tmp -> next;
        }
 
        printf("Enter a value for new node: ");
        scanf("%d", &input2);
 
        if (start == NULL) // if our list is empty
        {
                start = (Node *) malloc (sizeof(Node));
                end = tmp = start;
                start -> prev = NULL;
                end -> prev = NULL;
                start -> value = input2;
        }
        else if (start == tmp) // we're inserting before start of list
        {
                tmp2 = (Node *) malloc (sizeof(Node));
                tmp2 -> next = start; // point new node's next at start
                start -> prev = tmp2; // point start's prev at tmp2
                start = start -> prev; // move start to new node
                start -> value = input2; // put value in node
        }
        else // we're inserting before a node in the list
        {
                tmp2 = (Node *) malloc (sizeof(Node));
                tmp2 -> next = tmp; // point new node's next at tmp
                tmp2 -> prev = tmp -> prev; // point new node's prev at tmp's prev
                tmp -> prev -> next = tmp2; // tmp's previous next is new node
                tmp -> prev = tmp2; // tmp's prev is new node
                tmp2 -> value = input2; // put value in node
        }
        return(0);
}

Removal is the process of removing a node from an established instance of a data structure, such as a linked list in a program. A removal function typically takes a node position as input to delete, or it takes a specific value to look for an delete. An example of a removal function is below:

int removeNode()
{
        // Remove a node from the list
        tmp = start;
        int i=0;
        printf("Enter node # to delete: ");
        scanf("%d", &input);
 
        // Move tmp to exact node we wish to delete
        for(i=0; i<input; i++)
        {
                tmp = tmp -> next;
        }
 
        if ((tmp != start) && (tmp != end))
        {
                tmp -> next -> prev = tmp -> prev;
                // The node after points to the node before tmp
                tmp -> prev -> next = tmp -> next;
                // Now, the now before points to the node after tmp
                tmp -> prev = NULL;
                tmp -> next = NULL;
                // tmp is now disconnected from the list
                free (tmp); // deallocate the node tmp is pointing to
        }                                                                                                                                                                                       
        else if (start == end) // list is only a single node
        {
                free(start);
                start=end=tmp=NULL;
        }
        else if (tmp == start)
        {
                tmp -> next -> prev = NULL;
                // The node following tmp is no longer pointing to us
                start = start -> next;
                // Adjust start to point to the new start of the list
                tmp -> next = NULL; // Disconnect tmp from the list
                free(tmp); // deallocate the node tmp is pointing to
        }
        else // tmp is equal to end
        {
                tmp -> prev -> next = NULL;
                // The node preceding tmp is no longer pointing to us
                end = end -> prev;
                // Adjust end to point to the new end of the list
                tmp -> prev = NULL; // Disconnect tmp from the list
                free(tmp); // deallocate the node tmp is pointing to
        }
        return(0);
}

Searching is when a specific node or value is searched for through an established instance of a data structure in a program, via an algorithm. A search function accepts a value as input that represents an initialized value to search for or a given position of a node, then prints out the results of the search (whether or not the search was conclusive, what was found, etc.). An example code can be found below.

int search()
{
        //Find if node exists (search by value)
        printf("Enter a value to search for: ");
        scanf("%d", &input);
        tmp=start;
        int i = 0;
        int found=0; //if found = 0, then no node matches the search.
 
        while (tmp != NULL)
        {
                if(tmp->value == input)
                {
                        printf("Node at position [%d] matches the search value.\n", i); 
                        printf("Node [%d]: %d\nSearch value: %d\n\n", i, tmp->value, input);
                        found=1;
                }
                i++;
                tmp = tmp -> next;
        }
        if (found == 0)
        {
                printf("No node matches the search value.\n");
        }
        return(0);
}

A sorting algorithm takes the elements (in our case, it is most often nodes) of a set or list (data structure), and puts them in a specific order (numerical order, for example). Sorting algorithms are used in the functions for insertion, removal and searching that can be found above. Code for a program that makes use of a couple simple sorting algorithms can be found below.

#include<stdio.h>
 
char concatString(char *, char *);
 
int main()
{
 
	char string1[1000], string2[1000], junk;
	printf("Please enter string 1: ");
	scanf("%s", string1);
	scanf("%c", &junk);
	printf("Please enter string 2: ");
	scanf("%s", string2);
	scanf("%c", &junk);
	concatString(string1, string2);
	return(0);
}
 
char concatString(char *string1, char *string2)
{
	int s1=0, s2=0;
	while (string1[s1] != '\0')
	{
		s1++;
	}
	while (string2[s2] != '\0')
	{
		string1[s1+s2]=string2[s2];
		s2++;
	}
	printf("After concatenating, your string is now '%s.'\n", string1);
	return(0);
};

A selection sort is a sorting algorithm that finds the a lowest value in a list, then puts it in the first position. It does this for each item in the list until it is completely sorted. An animation of a selection sort in action can be found below.

<html> <img src=“http://upload.wikimedia.org/wikipedia/commons/b/b0/Selection_sort_animation.gif”></br> </html> Image source: Wikipedia

A bubble sort is a sorting algorithm that takes compares each item in a given list, and switches the two compared items if they are not correctly ordered. It is also called a sinking sort for this reason, as the lower values will “sink” to the bottom of the list, so to speak. An illustration of how a bubble sort works can be found below.

<html> <img src=“http://upload.wikimedia.org/wikipedia/commons/e/eb/Bubblesort-edited.png”></br> </html> Image source: Wikipedia

From the syllabus: “Write programs that use the following data structures: linked lists, stacks, queues, binary trees, and hash tables.” This means exactly what it says, simply write programs that implement data structures.

This is also simple– I'll just use a data structure we've learned about in a program, run it, and see if it works logically like the data structure is supposed to I will use my stack program to do this.

lab46:~/src/data/stack$ ./stacktest1
Please enter a value (-1 to stop:): 
54
Please enter a value (-1 to stop:): 
23
Please enter a value (-1 to stop:): 
14
Please enter a value (-1 to stop:): 
63
Please enter a value (-1 to stop:): 
-1
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
3

[Top of Stack]
[1]: 63
[2]: 14
[3]: 23
[4]: 54
[Bottom of Stack]
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
2
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
3

[Top of Stack]
[1]: 14
[2]: 23
[3]: 54
[Bottom of Stack]
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
1
Please enter a value (-1 to stop:): 
1
Please enter a value (-1 to stop:): 
-1
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
3

[Top of Stack]
[1]: 1
[2]: 14
[3]: 23
[4]: 54
[Bottom of Stack]
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
0
lab46:~/src/data/stack$ 

Wow, wow, wow. Look at that data structure. It looks like a stack. It functions as a stack. I think it is a stack. It is also in a program! Thereby meeting the objective. Look at how much I have learned! :D This objective is obviously very relevant and applicable to all that we do.

I am going to try to cause a stack underflow on my stack library project implementation. My question, I suppose, would be– is it possible to do with my code? Will it underflow like I expect it to?

My resources would be class lectures and my own stack library.

I think my program will let be pop every element, then attempt to pop in an empty stack, thereby causing a stack underflow. I do not believe that I've set any sort of condition that guards against an underflow, so this should be the result.

How am I going to test it? By running the program of course! I'll try to cause an stack underflow using my user interface.

lab46:~/src/data/stack$ ./stacktest1
Please enter a value (-1 to stop:): 
3 
Please enter a value (-1 to stop:): 
2
Please enter a value (-1 to stop:): 
1
Please enter a value (-1 to stop:): 
-1
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
2
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
2
Please choose a function: [1: Push][2: Pop][3: Display][0: Quit]
2
Segmentation fault
lab46:~/src/data/stack$ 

My hypothesis was not correct. A segmentation fault occurred as the last element of the stack was being popped. I did not expect a segmentation fault then!

Evidently, my program is not yet equipped to fill a stack, then empty it, then allow for further manipulation. This requires further examination.

This is a similar experiment as the last one, except we're trying to cause a queue underrun with my queue library project implementation. Question being– is it possible with my program?

Resources include class lectures and my own queue library implementation.

Based on the results of my last experiment, I think that a segment fault will occur just as the last element of the queue is being dequeued. I think this because this happened with my last program experiment, and this program is very similar, only difference being that it is using a queue.

I'll try to cause a queue underrun using my program and its user interface.

lab46:~/src/data/queue$ ./queue
Please enter a value (-1 to stop:): 
3 
Please enter a value (-1 to stop:): 
2
Please enter a value (-1 to stop:): 
12
Please enter a value (-1 to stop:): 
-1
Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]
3

[Front of queue]
[1]: 3
[2]: 2
[3]: 12
[End of queue]
Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]
2
Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]
3

[Front of queue]
[1]: 2
[2]: 12
[End of queue]
Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]
2
Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]
3

[Front of queue]
[1]: 12
[End of queue]
Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit]
2
Segmentation fault
lab46:~/src/data/queue$ 

My hypothesis was correct. It helps that my last experiment was very similar, but I did not know for sure, as I'm using different data structures.

This program is also not currently equipped to deal with an empty queue, something that also requires further evaluation.

If you're doing an experiment instead of a retest, delete this section.

If you've opted to test the experiment of someone else, delete the experiment section and steps above; perform the following steps:

Whose existing experiment are you going to retest? Prove the URL, note the author, and restate their question.

Evaluate their resources and commentary. Answer the following questions:

• Do you feel the given resources are adequate in providing sufficient background information?
• Are there additional resources you've found that you can add to the resources list?
• Does the original experimenter appear to have obtained a necessary fundamental understanding of the concepts leading up to their stated experiment?
• If you find a deviation in opinion, state why you think this might exist.

State their experiment's hypothesis. Answer the following questions:

• Do you feel their hypothesis is adequate in capturing the essence of what they're trying to discover?
• What improvements could you make to their hypothesis, if any?

Follow the steps given to recreate the original experiment. Answer the following questions:

• Are the instructions correct in successfully achieving the results?
• Is there room for improvement in the experiment instructions/description? What suggestions would you make?
• Would you make any alterations to the structure of the experiment to yield better results? What, and why?

Publish the data you have gained from your performing of the experiment here.

Answer the following:

• Does the data seem in-line with the published data from the original author?
• Can you explain any deviations?
• How about any sources of error?
• Is the stated hypothesis adequate?

Answer the following:

• What conclusions can you make based on performing the experiment?
• Do you feel the experiment was adequate in obtaining a further understanding of a concept?
• Does the original author appear to have gotten some value out of performing the experiment?
• Any suggestions or observations that could improve this particular process (in general, or specifically you, or specifically for the original author).