======Part 2====== =====Entries===== ====October 20th, 2011==== So I'm a little late making my first entry for this month(okay a lot late) but I have been working on stuff for data structures. What I have done so far this month is complete my doubly linked list library implementation project. I had few hiccups with that but I was able to work through them and move on. Since then I have started two more projects. One of them deals with a stack implementation and the other deals with a queue implementation. The stack project has given me a few small little problems but I am currently working through them and will hopefully get that working soon. I've really been enjoying the stuff that I've been learning and hope to get an even better understanding as the weeks go by. ====October 24th, 2011==== I'm back dating this entry because I forgot to add it on Monday. Today I worked on my Stack project. I was able to work through the problems I was having and got two out of the three main function working. It ended up being stupid compiling mistake that I made and now I have them working. I have also been studying up on the queue library implemetation and hope to have that nearly complete by the end of the month. I'm really enjoying these projects that I'm doing and finding it fun to be able to do a lot of the exploring on my own. ====October 27th, 2011==== SNOW!!!! It snowed today up here on the hill and that was majorly depressing. Nothing like a full day of homework and then snow to brighten up your day. Despite being depressed I was able to make really good progress on my keywords today. I was able to define stacks and all the operation that go along with them. I find that having to write down what you know about the keywords really makes you think about how they actually function. I feel like I have a better understanding of them now that I have been able to write them down. I also found out that the project proposal that I had for my stack library didn't save and all the work I did was for nothing. Oh well, I guess I'll have to write it up again. ====October 28th, 2011==== So far today I have finally written up my project proposal for Matt and got that sent to him. I did it a couple days ago but for some reason it didn't save and I lost all my work. I am also currently working on writing up my queue library implementation and will send that to Matt soon as well. And I learned to always have one of Karl's nuts in your hand at all times! =====Data Topics===== ====Linked lists==== Wikipedia defines a linked list as this,"a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence."Each "node" of a linked list is a struct containing some data value along with a struct pointer to the next node. You may ask yourself, "why would I use a linked list to store data when I could just use an array?". This is a very good question. The advantages to using a linked to store data are as follows. -insertion of data into the data structure -deletion of data from data structure -adding data to list The insertion of data into a specific location in an array would require a lot of work. Deletion is easy but causes vacant spots in memory and hinders optimal performance. Also, when wanting to add data to an array, you would need to reallocate memory which is an expensive operation. You do not have any of these problems with a linked list. All you have to do manipulate a few pointers and bam! You are set. below is an example of the definition of a node structure, creation of a singly linked list and the displaying of a lists contents. The credit for this code goes to Matthew Haas. #include #include struct node { int value; struct node *next; }; typedef struct node Node; int main() { Node *start, *tmp; int input,i; start = tmp = NULL; printf("Enter a value -1 to exit: "); scanf("%d", &input); while( input != -1) { if(start == NULL) { start = (Node *)malloc(sizeof(Node)); start->next=NULL; tmp = start; start->value=input; } else { tmp->next = (Node *)malloc(sizeof(Node)); tmp = tmp->next; tmp->next = NULL; tmp->value=input; } printf("Enter a value -1 to exit: "); scanf("%d", &input); } printf("The list contains the following elements\n"); tmp = start; while (tmp != NULL) { printf("[%d]value = %d\n", i, tmp -> value); tmp = tmp -> next; i++; } return 0; } lab46:~/src/data$ ./linkedlist Enter a value -1 to exit: 1 Enter a value -1 to exit: 2 Enter a value -1 to exit: 3 Enter a value -1 to exit: 4 Enter a value -1 to exit: 5 Enter a value -1 to exit: 6 Enter a value -1 to exit: -1 The list contains the following elements [0]value = 1 [1]value = 2 [2]value = 3 [3]value = 4 [4]value = 5 [5]value = 6 lab46:~/src/data$ **References** [[http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays]] ====Doubly Linked List==== The only difference between a singly linked list and a doubly linked list is that in a doubly linked list, the node structure also has a pointer to the previous node. This slight difference though gives a lot more functionality to the list. Now you are able to traverse the list in either direction where as in a singly linked list you had to start at the beginning. This can be useful in many applications. The code below shows the declaration of a node that has two struct pointers struct node { int value; struct node *next; struct node *prev; }; typedef struct node Node; ====Stacks==== A stack is a last in first out data structure. The type of stacks we covered in class were linked list based. There are also array based stacks but they have their own set of limitations. A stack is simply a linked list that can only be accessed from the top. This is know as a last in first out data structure(more on that later). The following struct "stack" contains the the data needed to implement a stack. Each Stack has a node pointer pointing to the top and bottom of the stack. It also contains a node pointer tmp and an int variable count which can be used for various other needs. struct stack { int count; struct node *top; struct node *data; struct node *tmp; }; typedef struct stack Stack; The creation of a stack is also very similar to that of a linked list. The creation of a stack is typically done the push() function which will be explained below. ====Pushing==== **Pushing** is the operation that is used to add a node to a stack. The function is typically called push() and it allows you to push a node on top of the stack. There is no other way to add a value to a stack but by using this function. The push() function should also be able to initialize a stack if there is not a stack to add the value to. Finally, the push() function should also check for stack overflow. More about that later. the following code demonstrates a push function. /*********************************************************** * Function push() will create a stack if no stack currently* * exists. If a stack does exist, push() will add a node to * * the top of the stack. It will then return the updated * * stack. * * Compile with: gcc -c push.c * * * ***********************************************************/ #include "stack.h" #include #include Stack *push(Stack *start, char input) { Node *tmp; if(start == NULL)// if no stack, create one { start = (Stack *) malloc (sizeof(Stack)); start -> data = malloc(sizeof(Node)); start -> top = malloc(sizeof(Node)); start -> tmp = malloc(sizeof(Node)); start -> top -> value = input; start -> top -> next = NULL; start -> data = start -> top; } else//if there is a stack, add node to top of it { tmp = (Node *) malloc (sizeof(Node)); tmp -> value = input; tmp -> next = start -> top; start -> top = tmp; } return (start); } ====Popping==== **popping** is the opposite of pushing. Popping allows you to remove a node from a stack. It is important to realize that in a stack, you only have access to the top most node. If you would like to remove a node that is not on the top, you have to remove all the nodes on top of the one you want to remove. That may seem stupid but it is the nature of a stack. Typically the function used to pop nodes is called pop(). A good pop function will also check for stack underflow(I'll explain more about that later). The following code demonstrates a pop() functions. /****************************************************************** * Function pop() accepts as an argument a stack. It will then pop * * the node that is currently on the top and make the node under * * that the new top. It will then return the value that from the * * popped node as a character. If the stack that is passed is NULL * * (meaning it does not exist), the function cannot pop a node that* * doesn't exist. Therefore, the function will return the null * * terminating character. * * * * Compile with: gcc -c pop.c * * * **************************************************************** */ #include "stack.h" #include char pop(Stack *start) { char chartmp; start -> tmp = start -> top; if(start -> tmp != start -> data) { start -> top = start -> top -> next; start -> tmp -> next = NULL; chartmp = start -> tmp -> value; } else if(start -> data == NULL) { chartmp = '\n'; } else { chartmp = start -> top -> value; start -> top = start -> tmp = start -> data = NULL; } return(chartmp); } ====Top==== The **top** operation is a very simple one. the top() ( or peek() ) function allows you to view the contents of the node that is currently on top of the stack. That is it. It just returns whatever value that is on the stack. It doesn't manipulate the nodes or change them in any way. The following shows the execution of my stack implementation. lab46:~/src/data/stackProject$ ./stack Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit 2 Enter value for new node: a Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit 3 The top node contains the value: a Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit 2 Enter value for new node: b Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit 3 The top node contains the value: b Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit q lab46:~/src/data/stackProject$ Notice that the most recent node pushed onto the stack becomes the top. If the top node is popped, then the node before that now becomes the top. ====Overflow Condition==== Stack overflow occurs when too much memory is used on the stack. Wikipedia states "The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. When a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack's bounds, which is essentially a buffer overflow), the stack is said to overflow, typically resulting in a program crash"(Wikipedia). Basically stack overflow is not a good thing and your push() function should be able to detect and handle that condition if it comes up. When using a array based stack, the maximum size for your stack is the size of the array. Let say you have an array of 100 elements. example) int testArray[100]; for(int i = 0; i< 200; i++) { testArray[i] = i; } this loop loads values into an array. Execution of this for loop would occur in a stack overflow because you would be accessing values out side of the given space. When you have a linked list based stack, overflow occurs when you run out of memory. ====Underflow condition==== When you use the pop() function on a stack but the stack is empty, you go into what is called a state of underflow. This means that there is no value to pop. If this happens, zombies will come out of the computer monitor and try to eat your soul.... NOT GOOD! Seriouly, a stack underflow will result in a runtime error in your program. Your pop() function should check to see if the stack is empty before trying to pop a node. The following shows what a program should do when trying to pop a node off of a stack when there is no node to pop. lab46:~/src/data/stackProject$ ./stack Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit 2 Enter value for new node: a Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit 1 The value that was pooped is: a Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit 1 The value that was pooped is: Enter - 1 - to pop a Node off of the stack Enter - 2 - to push a Node on the stack Enter - 3 - to peek at the value on top of the stack Enter - q - to quit q lab46:~/src/data/stackProject$ The value 'a' was pushed onto the stack and then popped off. This made the stack contain no value. I then tried to run the pop() function. Instead of getting a segmentation fault the pop() function returned a null value indication that there was no value to pop. ====LIFO==== LIFO stands for "last in, first out". This describes what we have just been talking about in stacks. Here is a picture representing a stack. {{:opus:fall2011:dschoeff:stack.png?nolink&200|}} The red sheet here represents the top of the stack. The red sheet the last sheet added to the stack and will be the first one out if the pop() function were to be run. I hope this helps your understanding of LIFO stack. ====Queue==== A **queue** ( pronounced as the letter 'Q') is a FIFO data structure(more about FIFO later). It is basically a linked list that you can only leave from the end or join from the beginning. Think of a line at the verizon. You go into the store and reserve your spot in line. Doing this places you into a queue. You will not be able to leave the queue until all the people in front of you have been waited on. In the mean time more people have been added to the queue behind you as well. Several hours later you will finally be able to leave the queue and be waited on. Like a linked list, queues are commonly made up of linked nodes. They are identical to singly linked lists and have a number of useful applications. please refer to this link for the basic structure of a queue -> [[http://lab46.corning-cc.edu/opus/fall2011/dschoeff/start?&#linked_lists]] ====Enqueuing==== Like in a stack, only certain operations can be performed on a queue. The first one I will mention is **enqueue**. enqueue() is function that allows you to add a node to the beginning of the queue. This is very similar to a prepend() function for a linked list. This operation takes a node and adds it to the beginning of a queue therefore making that new node the first node in the queue. That node can not be removed until it becomes the last node it the queue. The following code demonstrates a enqueue operation. //compile with: gcc -c enqueue.c // //Function enqueue() enqueues anode to the queue. If there is no queue in existance //it will create one. This function is almost exactly like the insert function in my //doubly linked library. #include "queue.h" #include void enqueue(Node** start, Node** end, int index, char ch) { int i; Node* tmp; Node* tmp2; tmp = *start; if (*start == NULL) // if our queue is empty { (*start) = (Node *) malloc (sizeof(Node)); (*end) = tmp = *(start); (*start) -> prev = NULL; (*end) -> prev = NULL; (*start) -> value = ch; } else// we are enqueing a node { 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 = ch; // put value in node } } ====Dequeuing==== queues would be pretty useless if you could only add nodes to the beginning of the queue. This is where **dequeuing** comes in. dequeue() is a function that allows you to remove the node on the very end of the queue. This is the only way that you can remove a node in a queue. The dequeue() function is very similar to pop() for stacks and removeNode() for linked lists. They operate basically the same way. The following demonstrates the dequeuing operation. //compile with: gcc -c dequeue.c // // Function dequeue() removes a node from a given queue and frees the // memory for that node #include "linkedlist.h" #include char dequeue(Node** start, Node** end, int index) { int i; char ch; Node* tmp; tmp = *start; if((*start) != NULL) { // Move tmp to exact node we wish to delete for( i=0; i next; } ch = tmp -> value; 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 queue free (tmp); // deallocate the node tmp is pointing to } else if (*start == *end) // queue is only a single node { free(tmp); (*start) = (*end) = NULL; } else if (tmp == *start) { tmp -> next -> prev = NULL; // The node following tmp is no longer pointing to us (*start) = (*start) -> next; tmp -> next = NULL; // Disconnect tmp from the queue 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 queue tmp -> prev = NULL; // Disconnect tmp from the queue free(tmp); // deallocate the node tmp is pointing to } } else { ch = '\n'; } return(ch); } =====Data Objective===== ====Write a program that uses stacks==== This course objective is to successfully write a program implementing the use of stacks. ===Method=== To do this successfully, I will have to understand the basic concepts of a stack. This requires a knowledge of pointers, structs, struct pointers, memory allocation and memory deallocation. It also requires a knowledge of linked lists. Success will be measured by the completion of a program that implements these elements efficiently. ===Measurement=== The keywords that I have entered at the top of this page show that I have successfully researched the concepts required to make a working stack. Besides having a knowledge of the concepts, the only other measure of success would be to have a program implementing these concepts. You can find such program here -> [[http://lab46.corning-cc.edu/user/dschoeff/portfolio/libstack]] ===Analysis=== Upon completion of this exercise, I believe I have successfully completed the course objective of creating a program that implements a linked list. -I believe could improve my functions so that they could be more flexible. For example, I currently only allow for each nodes value to be a character. I could change a few things around and allow for each node to hold more information. -Since the measurement process is based upon having a knowledge of the concepts required to build a stack and then to implement them in a program, I don't see to many ways to improve that using the current measurement system. You either have a working program or not. -If you altered the course objective( Write a program that uses stacks)to be implemented in a real life scenario. I can see where that could be a little more applicable. But all that aside, if you have an understanding of stacks you can use that knowledge anywhere whatever the application. =====Experiments===== ====Experiment 1==== ===Question=== How does the system handle unexpected input. Such as a character when an integer is expected. ===Resources=== * [[http://cboard.cprogramming.com/c-programming/16684-declared-int-but-entered-char.html]] * The C Programming Language ===Hypothesis=== I believe that when you enter a character when an integer is expected the program will output an error and terminate. This will happen because the system does not know what to do with the character value. ===Experiment=== I will test my hypothesis by creating a program that excepts as input an int value. I will then input a character value and see if the program will run. ===Data=== Here is the code for my experiment. #include using namespace std; int main() { int num ; cout << "Enter integer: "; cin >> num; cout << " Int is " << num << endl; return 0; } Here is the execution lab46:~/src/data$ ./inttest Enter integer: 1 Int is 1 lab46:~/src/data$ ./inttest Enter integer: q Int is 0 lab46:~/src/data$ ===Analysis=== Based on the data collected: * My hypothesis was not correct. I thought that the program would result in a runtime error but that was not the case. Instead, the program ran to completion without any errors. * is there more going on than you originally thought? Yes, something I did not take into account for was the input method I was using. * what shortcomings might there be in your experiment?In this experiment I used cin to get my input. I did not take into account other ways of getting data(command line, scanf(),fgets,etc...). ===Conclusions=== I can conclude from this experiment that when using cin to get an integer value, and then a character value is entered, the program will still run without error. Though the program will run without error, the output you get will not be correct. I found that when entering a character value when an int value was expected, the value stored in the variable is 0. BE CAREFUL WITH YOUR INPUT! ====Experiment 2==== ===Question=== How much time does the system take to do add up to a billion 1 at a time. ===Resources=== Matthew Haas The man page for clock ===Hypothesis=== I think that it will take 1 minute to add up to a billion. The computer is very powerful and can perform calculation at a crazy fast speed. ===Experiment=== To test this, I will write a function that add one to a variable until it reaches a billion. I will also include the time.h header file so I can measure how long it takes for the program to run. ===Data=== The following program will allow me to test the runtime of the program. #include #include #include int main() { unsigned long int i = 0; unsigned long int abc = clock(); while(i < 1000000000) { i++; } abc = clock(); abc = abc/CLOCKS_PER_SEC; printf("time in seconds = %llu\n",abc); return (0); } The execution of the program. lab46:~/src/data$ ./clock time in seconds = 4 lab46:~/src/data$ ===Analysis=== Based on the data collected: * my original hypothesis was not correct. * I originally stated that it would take one minute to add up to a billion. After execution I found that it only took 4 seconds. * The experiment was pretty straight forward. I don't think too much was going on that I did not account for. ===Conclusions=== After completing the experiment, I feel I have a better understanding of how fast the processor can handle tasks. This experiment also made me become familiar with using the time.h header file with its built-in function clock(). ====Experiment 3==== ===Question=== This semester I am taking Java, a higher level programming language than C, and have learned that with Java there is more "overhead". The question I am posing is this. Does more overhead equate to slower running programs? ===Resources=== * JAVA Programming: D.S. Malik & Robert P. Burton * The C Programming Language: Brian Kernighan * The man page for **time** ===Hypothesis=== I believe that since Java has more overhead and is a higher level language than C, it will take longer to do the same task. ===Experiment=== I will test my hypothesis by writing a program in both C and Java That does the same basic task. I will then compile and run these programs recording how long it took each one to run to completion. I will then compare the results with my original hypothesis. ===Data=== I have written two programs that increment a double variable by .025 until it reaches one billion. In C int main() { double i = 0; while(i < 1000000000) { i = i + .025;; } return (0); } In Java public class Cvsjava { public static void main(String[] args) { double i = 0; while(i < 1000000000) { i = i + .025; } } } Execution of C code lab46:~/src/data$ time ./clock real 4m13.026s user 4m12.956s sys 0m0.036s lab46:~/src/data$ Notice the total time is 4 minutes and 13 seconds Execution of Java code lab46:~/src/data$ time java Cvsjava real 3m47.261s user 3m47.230s sys 0m0.076s lab46:~/src/data$ Notice the total time is 3 minutes and 47 seconds. ===Analysis=== Based on the data collected: * was your hypothesis correct? No. The total runtime of the Java program was shorter than the C program. * was your hypothesis not applicable?No. I don't think so. * is there more going on than you originally thought? I think there may be. I originally equated a higher level programming language with it's more overhead to a slower running program. I don't think this is correct. * what shortcomings might there be in your experiment? I only tested how the languages handle adding numbers. I could've tested a lot more things such as function calls, memory allocation, output,etc... This may have led to a better picture of the differences between the languages. * what shortcomings might there be in your data? I believe the data in itself is fine. ===Conclusions=== According to findings, I think I need to do a lot more research on this topic. I find it very interesting that the Java program(being a higher level language) seemed to run faster than the one written in C. I would also like to find out if other factors are effecting how the programs run(like the JVM or something like that). I would like to investigate this more and get more opinions as to what is going on behind the scenes. As I continue to program in both languages I find pro's and con's to both. I look forward to learning more about these two popular programming languages.