======Part 2====== =====Entries===== ====Week of October 3==== 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. ====Week of October 10==== 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. ====Week of October 17==== 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! ====Month Day, Year==== 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. =====data Topics===== ====Function Pointers==== 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."); ====Null Pointer==== 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. ... ====Void Pointer==== 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 int main() { void *pointer; int integer=10; pointer=&integer; printf("\n %d \n", *(int *)pointer); return(0); } ====Stacks==== 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 #include // 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); } ====Pushing (Stack)==== 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 (Stack)==== 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); } ====Top (Stack)==== 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; } ====Stack Overflow condition==== 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 int main() { return(0); } ====Stack Underflow condition==== 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$ ====Queue==== 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 int main() { return(0); } ====Enqueuing==== 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$ ====Dequeuing==== 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 int main() { return(0); } =====data Objective===== ====Objective==== State the course objective; define what that objective entails. ===Method=== State the method you will use for measuring successful academic/intellectual achievement of this objective. ===Measurement=== Follow your method and obtain a measurement. Document the results here. ===Analysis=== 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? =====Experiments===== ====Use of sizeof() on a File==== ===Question=== Can you use the sizeof() function on a file you have referenced in a program? ===Resources=== 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. ===Hypothesis=== 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. ===Experiment=== 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. ===Data=== /* 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 #include 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 ===Analysis=== 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. ===Conclusions=== 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. ===="=" vs. "!=" in a While loop==== ===Question=== Which has priority in the condition in a while loop-- the assignment operator, or the not-equal-to operator? ===Resources=== 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. ===Hypothesis=== 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. ===Experiment=== 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. ===Data=== /* "=" vs. "!=" in a while loop experiment Fall 2011 Data Structures */ #include 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 ===Analysis=== 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. ===Conclusions=== 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. ====Giving "filestuff.c" a Directory==== ===Question=== What happens when you give a file utilizing program (such as filestuff.c, described here shortly) a directory rather than a text file? ===Resources=== 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. ===Hypothesis=== 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. ===Experiment=== The experiment is simple: switch the file in the program already (/etc/motd) with a directory, and observe the results. /* filestuff.c before. */ #include 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 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); } ===Data=== lab46:~/src/data$ ./fileexp Segmentation fault lab46:~/src/data$ ...Welp. ===Analysis=== 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. ===Conclusions=== 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.