======Data Structures Journal====== ====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? =====Week 1:===== ====August 28, 2013==== Today was the first day of class. First, we went over the syllabus and possible projects we may have to implement in C. Then we went over some basic usage of lab46. After all that, Matt started reviewing data types, structs, and pointers (I came to the realization that I am __**rusty**__ with C).\\ **[[http://lab46.corning-cc.edu/haas/fall2013/common/data|Data Structures Assignments Page]]** **[[http://lab46.corning-cc.edu/wiki/syntax|Wiki Commands]]** ====August 29, 2013==== Went over some more lab46 usage (using screen, the class IRC channel, Mercurial version control, etc.). \\ \\ Screen allows you to stay logged into the IRC channel.\\ * Start a screen session: lab46:~$ screen * View screen sessions: lab46:~$ screen -ls * Re-attach to a screen session: lab46:~$ screen -r * Start IRSSI: lab46:~$ irssi * Connect to the IRC server: /server irc * Join/Leave a channel: /join lab46 /leave lab46 /join csci /leave csci * Quit IRSSI: /quit * Detach from the screen session: ctrl-a -> d \\ Other IRC commands:\\ * roll: * flip: * define: * weather: **Using Typescript to capture and save a terminal session to a text file:** * Start capturing the terminal: lab46:~$ script Script started, file is typescript lab46:~$ * Perform the compile commands and run the code. * Stop capturing the terminal: lab46:~$ exit exit Script done, file is typescript lab46:~$ * There will now be a file called "typescript" in the current directory. Rename the typescript file by moving it to a different file. If this is not done, the file will be overwritten the next time Typescript is run: lab46:~$ mv typescript NewFileName lab46:~$ * Now the typescript file can be sent in an email or displayed in an opus all pretty like. Matt then informed us of our final project; programming one of the card games "FreeCell", "Forty Thieves", "Eight Off", or "Baker's Game". The project page is [[http://lab46.corning-cc.edu/haas/fall2013/common/data/cardgame|here]]. Matt also wrote a small program to review C pointers and to show a pointers various effects on the system's memory. The first version only uses one value. #include #include int main() { int a, *b; a = 12; b = &a; fprintf(stdout, "[a] address is: 0x%X\n", &a); fprintf(stdout, "[a] contains: %d\n", a); fprintf(stdout, "[a] dereferences to: %d\n", a); fprintf(stdout, "[b] address is: 0x%X\n", &b); fprintf(stdout, "[b] contains: %X\n", b); fprintf(stdout, "[b] dereferences to: %d\n", *b); return(0); } **Result:** RESULT OF RUNNING Matt then altered the program so the initial values would change: #include #include int main() { int a, *b; a = 12; b = &a; fprintf(stdout, "[a] address is: 0x%X\n", &a); fprintf(stdout, "[a] contains: %d\n", a); fprintf(stdout, "[a] dereferences to: %d\n", a); fprintf(stdout, "[b] address is: 0x%X\n", &b); fprintf(stdout, "[b] contains: %X\n", b); fprintf(stdout, "[b] dereferences to: %d\n", *b); a = 137; fprintf(stdout, "[a] address is: 0x%X\n", &a); fprintf(stdout, "[a] contains: %d\n", a); fprintf(stdout, "[a] dereferences to: %d\n", a); fprintf(stdout, "[b] address is: 0x%X\n", &b); fprintf(stdout, "[b] contains: %X\n", b); fprintf(stdout, "[b] dereferences to: %d\n", *b); *b = 2600; fprintf(stdout, "[a] address is: 0x%X\n", &b); fprintf(stdout, "[a] contains: %d\n", b); fprintf(stdout, "[a] dereferences to: %d\n", *b); fprintf(stdout, "[b] address is: 0x%X\n", &b); fprintf(stdout, "[b] contains: %X\n", b); fprintf(stdout, "[b] dereferences to: %d\n", *b); return(0); } **Result:** RESULT OF RUNNING ***Edit:** The video "Pointer Fun with Binky" should be viewed **__the first day class__**.\\ http://www.youtube.com/watch?v=m2n-LCb6Cvg **Binky's Three Pointer Rules:** - A Pointer and it's Pointee are separate. Initially pointers don't point to anything, so don't forget to set up the pointee. - Dereference a pointer to store or access a value at its pointee. - Assignment operator (%%=%%) between pointers makes them point to the same pointee, it doesn't touch the pointee's value. This is sometimes called "sharing". ====August 30, 2013==== Today we reviewed data types and there sizes. We also wrote a program that prints the sizes and bounds of the data types.\\ **Common C Data Types:** ^ Signed/Unsigned ^ Data Type ^ Bytes ^ | Signed | char | 1 | | Unigned | char | 1 | | Signed | short int | 2 | | Unigned | short int | 2 | | Signed | int | 4 | | Unigned | int | 4 | | Signed | long int | 8 | | Unigned | long int | 8 | | Signed | long long int | 8 | | Unigned | long long int | 8 | | No sign | float | * | | No sign | double | * | | No sign | long double | * | //*Using the program, I discovered that the float, double, and long double data types are not signed. Also, a signed/unsigned long int and a signed/unsigned long long int have the same size of 8 bytes. This could be a system property of lab46. An important thing I learned was the size of the data types is dependent on the system that the code is being ran on. This can cause the data type ranges to be different from system to system.// \\ \\ ** String Modifiers: ** ^ String Modifier ^ Data Type ^ | %d | Signed Int. | | %u | Unsigned Int. | | %hu | Half (Short) Unsigned Int. | | %hhu | Half half (Half Short goes to char) | | %lu | Long | | %llu | Long Long | | %f | Float | | %lf | Long Float (Double) | Matt then wrote a program that prints the sizes and bounds of 2 of the data types. /* Nick Brimmer Data Structures Mathew Haas Spring 2013 Explore C Data types, there sizes in bytes, and ranges. */ #include #include int main() { // Program Variables. /* Quantity variable: Stores the maximum unique values the data type can hold. The maximum number of unique values is 1 less than 0; 0 - 1 causes quantity to "roll-over" to its maximum value. */ unsigned long long int quantity = 0; unsigned char uc = 0; signed char sc = 0; // Aesthetics, heading for the output table with a divider. printf("\nData Type Sizes (in bytes) and Ranges:\n"); printf("----------------------------------------\n"); // unsigned char: printf("An unsigned character is: %u bytes.\n", sizeof(uc)); quantity = (unsigned char) (uc - 1); printf("The range of an unsigned character is %hhu to %hhu.\n", uc, (uc - 1)); printf("An unsigned character can store %llu unique values.\n\n", quantity); // Signed char: printf("A signed character is: %d bytes.\n", sizeof(sc)); quantity = (unsigned long long int)pow(2, (sizeof(sc) * 8)); printf("The range of a signed character is %hhd to %hhd.\n", (sc - (quantity / 2)), (sc + (quantity / 2) - 1)); printf("A signed character can store %llu unique values.\n\n", quantity); printf("\n"); return(0); } \\ For homework, complete the program for the other data types. Also, attempt to determine the bounds using a logical solution. The logical solution is something I remember from my first semester while learning binary: To get the max value for a number, subtract 1 from 0 (0 - 1). This causes the lowest value (0) to "roll-over" like an odometer to its maximum value. While Google'ing data types, I found out that bitwise operations can also be used:\\ //(http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B) and (http://www.cs.mun.ca/~michael/c/op.html)//\\ ** Bitwise Operators ** ^ Symbol ^ Bitwise Operator ^ | ~ | NOT | | & | AND | | %%|%% | OR | | %%^%% | XOR | | << | Left Shift | | >> | Right Shift | Another interesting discovery was "Digraphs" and "Trigraphs": (http://en.wikipedia.org/wiki/Digraphs_and_trigraphs#C)\\ **Digraphs and Trigraphs:** ^ Digraph ^ Trigraph ^ Equivalent ^ | <: | ??( | [ | | :> | ??) | ] | | <% | ??< | { | | %> | ??> | } | | %: | ??= | # | | -- | ??/ | \ | | -- | ??' | %%^%% | | -- | ??! | %%|%% | | -- | ??- | ~ | **C++ adds additional "tokens":** ^ Token ^ Equivalent ^ | %:%: | ## | | AND | && | | Bitwise OR | %%|%% | | OR | %%||%% | | XOR | %%^%% | | compl | ~ | | Bitwise AND | & | | AND_EQ | &= | | OR_EQ | != | | XOR_EQ | %%^=%% | | NOT | ! | | NOT_EQ | != | **Note:** %:%: is treated as a single token, rather than two occurrences of %:. \\ \\ These "Digraphs" and "Trigraphs" reminded me of the "Brainfuck" programming language (http://en.wikipedia.org/wiki/Brainfuck). An important thing that I learned was that the stack and heap are both data structures, which makes sense. I also learned that there are different types of stacks. This is significant because almost everything that computes data has both a stack and heap, and one goes up in address space while the other goes down. This might be something important to remember for later on in the semester. Since this is the first week, it is more of a review. CURRENTLY everything makes sense. I do know that this will end very soon. I expect a few challenges with respect to the course; hopefully nothing that Google cannot solve. =====Week 2:===== ====September 4, 2013==== Today in lecture we created a review program. In it we went over structs, arrays, for loops, and while loops. Today in class we reviwed structs, arrays, for loops, and while loops. A **Struct** is used to store multiple data types (unlike an array which can only store 1 data type). You can also use //typedef// to make your structs easier and faster to use (and using less code). This example defines the //structure person// as //Person//: typedef struck person Person; // Without typedef: struct person People[8]; // With typedef: Person People[8]; Two important things to remember are the end of a struct requires a '**;**' and whenever memory is allocated, it is important to de-allocate that memory when it is no longer needed to prevent [[http://en.wikipedia.org/wiki/Memory_leak|Memory Leaks]]. We then wrote an example program: #include #include int main() { struct person{ char *name; int age; long int id; }; typedef struct person Person; Person People[8]; int i=0; for(i=0; i<8; i++) { fprintf(stdout, "Enter person #%d's name: ", (i+1)); People[i].name=(char*)malloc(sizeof(char)*20); fscanf(stdin, "%s", People[i].name); fprintf(stdout, "Enter %'s age: ", People[i].name); fscanf(stdin, "%d", &People[i].age); fprintf(stdout, "Enter %s's id number: ", People[i].name); fscanf(stdin, "%ld", &People[i].id); } i=-1; while(i == -1) { fprintf(stdout, "Look up date for person #: "); fscanf(stdin, "%d", &i); if(! ( (i >= 0) && ( i <= 7) ) ) { fprintf(stdout, "Invalid person #, Try Again!\n"); i=-1; } } i--; fprintf(stdout, "Name: %s\n", People[i].name); fprintf(stdout, "Age: %d\n", People[i].age); fprintf(stdout, "ID: %ld\n", People[i].id); return(0); } ====September 5, 2013==== Today we started learning about lists. Lists are useful because they are dynamic arrays that grow and shrink as needed. The list grows and shrinks by adding and deleting nodes. The code was messing up my Opus formatting so I put it [[user:nbrimme1:portfolio:Sept05|here]]. ====September 6, 2013==== Today Matt started class with checking everyone's opus and first project (datatyperanges.c). Then we talked more about linked lists by writing a function to insert a node. It looks pretty simple when Matt draws pretty pictures on the board; and it's easier to erase/see the changes made to the values and nodes. I might want to invest in a whiteboard and markers so I can draw pretty pictures, maybe things will be easier to implement. Googleing "Single Linked List in C" produces some examples; but most are too cryptic. The Single Linked List has been building on our "struct" function that we wrote in class. We've done some code in class and it seems simple enough. I am still having difficulty with the Order of Operations and the combinations of "()"'s. Guess I'm still a bit rusty. Also, I finally managed to join the class mailing list. =====Week 3:===== ====September 11, 2013==== We started class fixing a problem with our insert function. Matt noticed that there was a problem when inserting a node before the first node. We then spent the class fixing our code. if(input == 0) { fprintf(stdout, "Enter value for new node: "): fscanf(stdin, "%d", &input); tmp2=(Node*malloc(sizeof(Node)); tmp2->value=input; tmp2->next=NULL; tmp2->next=tmp; list=tmp2; } ====September 12, 2013==== Today we wrote the append and the remove functions of the Singly Linked List program: **appendNode:** fprintf(stdout, "Node to append after: "); fscanf(stdin, "%d", &input); int behind; tmp = list; Node*tmp3 = NULL; for(behind = 0; behind < input; behind++) { tmp = tmp->next; } fprintf(stdout, "Node to append: "); fscanf(stdin, "%d", &input); tmp3 = (Node *)malloc(sizeof(Node)); tmp3->value = input; tmp3->next = tmp->next; tmp->next = tmp3; tmp = list; input = 0; while(tmp != NULL) { fprintf(stdout, "[%d] %d -> ", input, tmp->value); tmp = tmp->next; input = input++; } fprintf(stdout, "NULL\n"); **removeNode:** tmp = list; int remove; fprintf(stdout, "Node to remove?: "); fscanf(stdin, "%d", &input); for(remove = 0; remove < (input - 1); remove++) { tmp = tmp->next; } if(input == 0) { tmp2 = tmp->next; tmp->next = NULL; list = tmp2; } else { tmp2 = tmp->next; tmp->next = tmp2->next; tmp2->next = NULL; } tmp = list; input = 0; while(tmp != NULL) { fprintf(stdout, "[%d] %d -> ", input, tmp->value); tmp = tmp->next; input = input++; } fprintf(stdout, "NULL\n"); ====September 13, 2013==== Today we started the Doubly Linked List program. It's the same as a Singly Linked List but instead of a *next pointer; there's a *next and a *prev pointer. This makes the traversing the list MUCH easier. #include #include struct node { int value; struct node *next; struct node *prev; }; typedef struct node Node; struct list { struct node *start; struct node *end; }; List *build(); void displayForward(List *); void displayBackward(List *); int main() { List *myList; myList=build(); displayForward(myList); displayBackward(myList); return(0); } List *build() { Node *tmp = NULL; List *myList = (List*)malloc(sizeof(List)); myList->start = myList->end = NULL; int input = 0; fprintf(stdout, "Enter a value (-1 to quit): "); fscanf(stdin, "%d", &input); while(input !=-1) { if(myList->start == NULL) { myList->start = myList->end = (Node *)malloc(sizeof(Node)); myList->start->value = input; myList->end->prev = myList->start->next = NULL; } else { myList->end->next = (Node *)malloc(sizeof(Node)); myList->end->next->value = input; myList->end->next->next = NULL; myList->end->next->prev = myList->end; myList->end = myList->end->next; } fprintf(stdout, "Enter another value(-1 to quit): "); fscanf(stdin, "%d", &input); } return(myList); } Also, a display forward function was written for our doubly linkedlist: void displayforward(List *myList) { Node *tmp=myList->start; int input=0; while(tmp !=NULL) { fprintf(stdout, "[%d] %d -> ", input, tmp->value); tmp=tmp->next; input=input++; } fprintf(stdout, "NULL\n"; } The same logic can be used to write a displayBackward function. =====Week 4:===== ====September 18, 2013==== Today was a general work day. I worked on both the Singly and Doubly Linked Lists implementing the functions described in the course project pages. ====September 19, 2013==== Today we discussed the insert function for the Doubly Linked List. We also need to start separating the our single Doubly Linked List file into separate files. Joe Oppenheim's tip was to separate interaction from implementation. This means moving the user interaction (menu choices, etc) from the functions themselves. This makes debugging easier and the code can be used with other projects. For example, this is the insert function: List *insert(List *myList, Node *place, Node *newNode) { if(place == myList->start) { newNode->next = place; place->prev = newNode; newNode->prev = NULL; myList->start = newNode; } else { newNode->next = place; place->prev->next = newNode; newNode->prev = place->prev; place->prev = newNode; } return(myList); } There is NO user input. The code where the user inputs the data is inside the menu: // Insert node. case 5: tmp=myList->start; fprintf(stdout, "Node to insert: "); fscanf(stdin, "%d", &choice); // Seeker value. for(seeker=0; seeker<(choice-1); seeker++) { tmp=tmp->next; } // make new node (tmp2) // put choice in new node's value Node * tmp2 = (Node *)malloc(sizeof(Node)); fprintf(stdout, "Value to insert: "); fscanf(stdin, "%d", &choice); tmp2->value = choice; myList = insert(myList, tmp, tmp2); break; ====September 20, 2013==== Today in class we wrote the removeNode function for the Doubly Linked List: List *removeNode(List *myList, Node **place) { if(myList->start->next == NULL) { myList->start = NULL; } else if(*place == myList->start) { myList->start = myList->start->next; myList->start->prev = NULL; (*place)->next = NULL; } else if(*place == myList->end) { myList->end = myList->end->prev; myList->end->next = NULL; (*place)->prev = NULL; } else { (*place)->prev->next = (*place)->next; (*place)->next->prev = (*place)->prev; (*place)->prev = (*place)->next=NULL; } return(myList); } The remove function was then added to the menu: // Append node. case 6: tmp = myList->start; fprintf(stdout, "Node to remove: "); fscanf(stdin, "%d", &choice); for(seeker = 0; seeker < choice; seeker++) { tmp = tmp->next; } myList = getNode(myList, &tmp); break; =====Week 5:===== ====September 25, 2013==== Today we learned how to split up our C programs into multiple, smaller object files. This can both help in programming, debugging, and code collaboration because of the smaller amount of code. We split our Doubley Linked List program into 4 separate files: - **dll.h**: This is the header file. Everything before main() is included in the header file. Examples are #include's, #defines, struct definitions, and function prototypes. - **main.c**: This is the main C program. It only includes everything between int main(){ }. - **listOps.c**: This C file contains only the list operations (insert(), append(), remove(), sort(), clear(), build(), and create()). - **display.c**: This C file contains only the display functions (displayF() and displayB()). This was accomplished by first copying the dlinklist.c file into 4 separate files, then editing them: - $ cp dlinklist.c dll.h - $ cp dlinklist.c main.c - $ cp dlinklist.c listOps.c - $ cp dlinklist.c display.c Now edit all the files: Add #include <"dll.h"> to the top of all C files, but NOT the header file. This tells the compiler to include the written header file. No ""'s means the header file is in the system directory. ""'s means the header file is in the local directory. Next, make the 3 C files into "object" files (The header file is NOT included): - $ gcc -c listOps.c produces //listOps.o// - $ gcc -c display.c produces //display.o// - $ gcc -c main.c produces //main.o// Now compile the program into 1 executable: - $ gcc -o dlinklist main.o listOps.o display.o The order of the object files can sometimes be important. You do not include the header file at compile time, it is included in the 3 C files. ====September 26, 2013==== Today was a Lab work day. I Google'd for about information about sorting algorithms, knowing absolutely nothing about them. I discovered that there are a number of different ways to sort a list. **__Edit: 9/27__** I am no longer using anything from Google. Drank some beers, put the logic on paper, and found the answer simple. No beer isn't the answer, it just helped in FINDING the answer. ====September 27, 2013==== Today in class we learned how to make libraries. **ar** is the "object file archiver". Main.c isn't included in the library because main.c is the main program and main() uses the library. - $ gcc -c listops.c - $ gcc -c display.c - $ ar -rcs libdlinklist.a listops.c display.c Once the library is made, the program can be compiled. (at compile time, the compiler drops lib and .a from the dlinklist library): * $ gcc -o main main.c -l dlinklist We also learned about the GNU Debugger (gdb). This can be an indispensable tool when fixing bugs. Compiling with the debugger option is a good habit to start. It is invoked using the -g option: * $ gcc -g -o main main.c -l dlinklist It can also be called from the command line: - $ gdb ./main - (gdb) run This opens the main executable inside of gdb. Some useful gdb commands are: * list 120: List's line 120 of the program. * list var: List's all the variables. * break 120: Breaks at line 120. * break append: Skips the append function. * s: single step - Steps through the program 1 instruction at a time, even inside functions. * n: single next - Just like single step but skips function calls. It will only step into its own functions. * c: continue - Continue until a break point is hit. slinklist.c program FINALLY COMPILES! Now I have to write the sortList() and clearList() functions. After 7 hours of meditation with the almighty Google; got down to 3 problems. They were all typos. As always; Matt was once again able to fix with 2 keystrokes. Now the only functions that aren't written are sort() and clearList(). clearList() is only a matter of calling removeNode() over and over with a while( node->next != NULL); node->next == NULL at the end of the list. I hope this looks better worked out on paper. The paper (.pdf) "[[http://www.cs.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf|A Comparative Study of Linked List Sorting Algorithms]]" (from the almighty Google) helped very little. It basically compared the speeds of different algorithms on different types and sizes of lists, but did "spark" in my brain on what I might have to do. After putting the sort function on paper the solution hit me in the face like a brick. I will have to keep in mind that pen and paper was a huge help. Looking at that horrid if/elseif/else statement; I realized that if (tmp->nextValue > tmp->value) **__OR__** if (tmp->nextValue == tmp->value), the list will remain unchanged. The only condition that needs to be checked is (tmp->nextValue < tmp->value). This changed that trash nasty if/elseif/else statement into a beautifully simple while statement; reducing the complexity of the program and the amount of code. =====Week 6:===== ====October 2, 2013==== Today was a knowledge assessment. It tested our knowledge of pointers, structs, and functions. Also, Matt (again) fixed my program with 2 keystrokes: The problem was in the sortList() function. I was passing the integer value instead of the pointer address. The singly linked list program is almost complete. It compiles but hangs when sorting and clearing the list. This means there is a logic error in there somewhere... Once the singly linked list program is complete, the doubly linked list should be almost the same code; except with the extra pointer *prev. ====October 3, 2013==== Today, we started class with a sample program from Matt so he could gently walk us through a doubly linked list (Matt was worried with some of the assessments from the day before). After walking the class through the sample program, we were given more time to worked on our knowledge assessments. I drew a unicorn. **Matt's Program:** Node *h, *j; Node *tmp, *tmp2; j = tmp = NULL; tmp2 = j; h = tmp; tmp = tmp2 = create(); tmp2->next = create(); tmp->prev = create(); tmp = tmp2 = next; h = tmp->prev; tmp->prev = tmp2->prev; j = tmp2->prev->prev->create(); j->prev = tmp; tmp->next = j->prev; \\ After lab, I changed (Matt/Shawn Meas; I did nothing but curse the C language) the remove function so it would work correctly in clearList(). The solution was to put the prompt outside of the If/Else loop. The //im_so_rusty_at_c_i_need_a_tetanus_shot// lesson of the day is: First you declare a variable, then you initialize the variable to a value, then the variable can be used. SortList() is still an infinite loop; the fix is probably similar to the fix for clearList(). ====October 4, 2013==== Started the 2nd part of the knowledge assessment. Matt was so inspired by my awe-inspiring, perfect, lifelike rendition of a unicorn that he included one in the assessment. For the knowledge assessment lists, the provided code: - Create a doubly linked list: * *next is initialized in the function. * *prev is initialized in the function. - The *prev pointer (in most of the cases) is not used and can be left pointing to NULL. - Example list: // Initialize a doublee linked list. struct list *listName = (struct list *) malloc (sizeof(struct list)); // Pointers *next and *prev are initialized in the list() function. *next = NULL; *prev = NULL; // To start a list: // Initialize *tmp to NULL: tmp = NULL; // Create a node at the beginning of a list: tmp = create(); // Insert a value into the created node: tmp->value = 0; // Create a new node after the first node: tmp->next = create(); // Advance *tmp by 1 to the next node: tmp = tmp->next; // Create a new node: tmp = create(); // Insert a value into the newly created node: tmp->value = 0; // Create a new node after the newly created node: tmp->next = create(); // Advance *tmp by 1 to the next node: tmp = tmp->next; ... etc. \\ Went back to my e-mail regarding sortList(). Need to re-write my sortList() function using the appendNode() and removeNode() functions:\\ /* If next value is less than value, call appendNode() then removeNode(). No other conditions need to be checked. */ if (tmp->next->value < tmp->value) { appendNode(*tmp, *tmp->next) removeNode(*tmp) *tmp = *tmp->next; } \\ **Video to watch:** "[[http://www.youtube.com/watch?v=m2n-LCb6Cvg|Pointers Fun with Binky]]". **Str8 __WISDOM__** and should be shown the first day of class. =====Week 7:===== ====October 9, 2013==== {{ http://upload.wikimedia.org/wikipedia/commons/thumb/2/29/Data_stack.svg/391px-Data_stack.svg.png |Stack}} Was in the hospital a few days. Matt went over "**stacks**" while I was gone and there was a lot of information. To keep my Opus a reasonable size, I put everything [[user:nbrimme1:portfolio:Oct09|Here]]. ====October 10, 2013==== Can't drive anymore so I was super late to class. The class went over the "Lack of Knowledge" assessments (apparently they were bad). The rest of the class time was a work period. Started to write the sortList() functgion using appendNode() and removeNode(). The removeNode() function needed to be changed by putting the user input into the case statement; just like the appendNode() function. This was done to fix the sortList() function. ====October 11, 2013==== Today Matt wrote a stack testing program. #include #include "stack.h" int main() { Node *tmp; Stack *myStack; myStack = mkstack(0); tmp = create(); // Second fgetc eliminates the naturally occuring \n char. tmp->value = fgetc(stdin); fgetc(stdin); while (tmp->value != "\n") { myStack = push(myStack, tmp); tmp = create(); // Second fgetc eliminates the naturally occuring \n char. tmp->value = fgetc(stdin); fgetc(stdin); } printf("Linked List has %d nodes.\n", myStack->data->qty); printf("String is: "); do { tmp = pop(&myStack); if (tmp != NULL) { printf("%c", tmp->value); } } while (tmp != NULL); printf("\n") return (0); } \\ A clever [[http://www.youtube.com/watch?v=0bLFO4ZV0i4|video]] to "explain" stacks (I sing this exact song when my stack doesn't work). \\ \\ I also had the logic of my sortList() function backwards; I changed it from append->remove to remove->append. Wondering if it is easier to swap the values instead of playing with the pointers. Moving the values (using paper logic) does seem easier. \\ \\ **__Edit: 10/16__** I re-wrote my sortList() function to swap the pointers and not the values. Since we are working with lists, Matt "suggested" playing with the pointers and not the values inside the nodes. =====Week 8:===== ====October 16, 2013==== Today is a work day. We need to get both the singly and doubly linked lists working so the stack will work. Once the stack works, we will start to work on queues. For compiling the stack, Matt is working on a custom makefile to make compiling the separate files easier. ====October 17, 2013==== 8-) 8-) 8-) 8-) \\ \\ Alot was covered today. To keep my Opus a reasonable size, I put everything [[user:nbrimme1:portfolio:Oct17|Here]]. ====October 18, 2013==== {{ http://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/405px-Data_Queue.svg.png |Queue}} Today we started Queues. A Queue, sometimes called a "buffer", is another type of stack (A Queue is considered FIFO/LILO while a Stack is considered FILO/LIFO). It has a front and back pointer, "Enqueue" is pushing a value to the back of the queue, and "dequeue" is popping a value from the front of the queue. Queue's also have a fixed size (the "buffer size" or "boundary"), and this can cause some problems. A //Buffer Overflow// or //Buffer Overrun// result when a value is pushed onto a full stack; overwriting data in adjacent memory addresses. //Buffer Underflows// or //Buffer Underruns// result when a value is popped from an empty stack; returning unwanted data in adjacent memory addresses. This problem occurs because a Stack starts at the top of memory and iterates down in memory addresses and a Queue (or Heap) starts at the bottom of memory and iterates up in memory addresses. Matt's code to start Queue. struct queue{ List *data; Node *front; Node *back; int bufsize; }; typedef structqueue Queue; Queue *mkqueue(bufSize); Queue *enqueue(Queue *, Node *); Node *dequeue(Queue **); \\ Matt also added the header file queue.h for the Queue in /var/public/data/fall2013/stacks/. To copy it into the source directory, at a lab46 prompt: \\ $ cd /var/public/data/fall2013/linkedlistimp/inc $ cp queue.h ~/src/datas/linkedlistimp/inc \\ **queue.h** #ifndef _QUEUE_H #define _QUEUE_H #include "list.h" struct queue { List *data; Node *front; Node *back; int bufsize; }; typedef struct queue Queue; Queue *mkqueue(int); Queue *enqueue(Queue *, Node *); Node *dequeue(Queue **); #endif \\ Matt informed me the command alias **gcc='gcc -g'** (automatically compile with debug symbols) would not cause problems, so I made an alias: * lab46:~/$ nano .bashrc * Scroll down to **#Aliases** * Add **alias gcc='gcc -g'** to the bottom of the list. * Save and exit. Tweaked my sortList() function pseudocode: - Declare variables *tmp, *tmp2, *tmpList, & *tmpList2. (*tmp and *tmp2 are the 2 values from *tmpList & *tmpList2 to be compared and sorted, *tmpList is the unsorted list, and *tmpList2 is the sorted list.) - Pass entire unsorted list to *tmpList. - Create *tmpList2 to store the sorted values. This ensures *tmpList and *tmpList2 are the same size. - Set *tmpList2 equal to *tmp to point *tmpList2 to the beginning of the unsorted list. - Iterate through *tmpList and find the lowest value. - Assign the lowest value in *tmpList to *tmp2. - Remove *tmp2 from *tmpList. - Append *tmp2 to *tmpList2. - Repeat steps 5 to 8 until *tmpList is empty. - Print *tmpList2. if (*tmpList->next == NULL) {print *tmpList2} This also led to a Eureka moment of traversing a singly linked list using only 1 pointer (*tmp). Knowing this should make implementing it with a doubly linked list easier, *tmp = *next and *tmp2 = *prev: // Initialize *tmp to NULL: *tmp = NULL; // Create a node at the beginning of a list: *tmp = create(); // Insert a value into the first node: *tmp->value = 0; // Create a new node after the first: *tmp->next = create(); // Advance *tmp (by 1) to the next node: *tmp = *tmp->next; =====Week 9:===== ====October 23, 2013==== Today was a general work day. Matt wants the Singly Linked List, Doubly Linked List, Stack, and Queue programs working so we can start the final card game project. Worked on the code for the new "Quantity" *qty() function; it is a modified function from the Knowledge Assessment (func4() with a counter variable): // Display Quantity of List. node nodeQty(int *i) { // Counter variable: Counts the iterations of the while loop, returning the size of the list. int i = 0; // Initialize pointer tmp to NULL. Node *tmp = NULL; // Reset tmp to list; points to the beginning of the list. tmp = list; while (tmp->next != NULL) { // Iterate through the entire list. tmp = tmp->next; // Increment i after every iteration. i++; } // Return counter variable. return(i); } \\ Next are the mklist() and mkstack() functions. These functions should return an empty list and an empty stack. ====October 24, 2013==== Started on the mklist() and mkstack() functions. These functions should return an empty list and an empty stack. For the mkList() function: Call createList() to make an empty list (*start && *end == NULL;, value inside the node will be nothing). For the mkStack() function: Call createList() to make an empty stack. Since the stack is an empty and push()/pop() only works with the top of the stack, set the pointer at the top of the stack to NULL. (set top = NULL;). I Changed my sortList() function AGAIN (This is version 6 or 7). I always seem to find another condition where it WON'T work and then need to adjust things. Pretty close to the final pseudo code steps: - Declare variables *tmp, *tmp2, *tmpList, & *tmpList2. *tmp and *tmp2 are the 2 values to be compared. If *tmp > *tmp2, *tmp is then inserted into *tmpList. *tmpList is the unsorted list and *tmpList2 is the sorted list. - Pass entire unsorted list to *tmpList. - Pass *tmpList to *nodeQty to return the size of the list. - Create *tmpList2 to store the sorted values, making the size of the list equal to *nodeQty. This ensures *tmpList and *tmpList2 are the same size. - Set *tmp2 equal to *tmpList2 so *tmp2 points to the beginning of the unsorted list. - Assign the first value from *tmpList to *tmp2 and insert *tmp2 into *tmpList2. The first value of the unsorted list will be the lowest value of the sorted list. - Assign the next lowest value in *tmpList to *tmp. - Compare *tmp and *tmp2. while (tmp->value > tmp2->value) { /* Want to remove node from list first, then append the node. Removing the node removes the pointers while leaving the node. Appending first adds an extra step and there will be duplicate values in the list. */ removeNode(tmp, tmpList); // append the node to the list. appendNode(tmp, tmpList2); } - Repeat steps 7 and 8 until *tmpList2 is empty. while (nodeQty(tmpList) != 0) { while (tmp->value > tmp2->value) { removeNode(tmp, tmpList); appendNode(tmp, tmpList2); } } - Print *tmpList2 when *tmpList is empty. while (nodeQty(tmpList) != 0) { while (tmp->value > tmp2->value) { removeNode(tmp, tmpList;); appendNode(tmp, tmpList2); } } else { print tmpList2 } \\ The above code uses 2 lists and 2 pointers. I went back to my original email to Matt and realized I could do this with 1 list and 2 pointers; here comes version 8 :-| :-/ :-\ :-? 8-O :-X. I was thinking about doublee linked lists when I wrote it, which is why I decided to use 2 lists. Maybe it will be useful in that program. This will remove a few steps from the current sortList() function pseudo code. \\ \\ I also found a sortArray() function from last semester that I'm going to try and change to work with lists (I removed some of unneeded comments. It uses the built-in C function compare 'cmp'). It shouldn't be that difficult, I can see some similarities between a singlee linked list and an array: \\ **Pseudo code:** /* 'sortArray()' code. Inserts numbers into an array. 'A' is the name of the array. 'n' is the maximum size of the array. */ sortArray(A) { for (i = 1, n-1, i++) { /* Inserts the value of the iterator into array 'A'. Starts at 1, ends at maximum array size - 1. */ insert(A, i, A[i]); } } /* 'insert' code. Inserts values into the array. Also iterates through the array. 'A' is the name of the array. 'pos' is the position in the array. 'value' is the value being inserted into the array. */ insert(A, pos, value) // Set both the iterator and position to 1. i = pos = 1; /* While the iterator is >= to 0 ----AND---- The value inside array 'A' is > value */ while (i >=0 && A[i] > value) { /* Insert the iterator + 1 into array A. The next value in the array becomes A[i]. A[i+1] = A[i]; // increment i. i = i+1; } /* The iterator + 1 becomes 'value'. The next value to be inserted into the array. */ A[i+1] = value; \\ //Joe Oppenheim said/suggested that the above code can be done using a recursive function. This is probably a better solution, but I am too rusty with C.// ====October 25, 2013==== Today was another work day. I worked on VERSION 9 of my sortList() function. // sortList() function. Node *sortList (Node *list) { // 1st value to compare. Node *tmp; // 2nd value to compare. Node *tmp2; // Iterator, also equals the number of SORTED nodes. int i = 0; // Point *tmp to the beginning of the list. tmp = list; return(list); } =====Week 10:===== ====October 30, 2013==== Today we started binary trees (sometimes called a "Binary Search Tree" or a "Ordered Binary Search Tree"). The binary tree is very similar to a doubly linked list; it's actually a triply linked list: instead of *next and *prev, there is *root, *left, and *right (//*root always points to the "root" or top of the binary tree//). There are 3 ways to "traverse" the tree "depth-first": - **Pre-order traversal**: Do the "left" (*prev) side of the tree, do the "parent" node of the tree, do the "right" (*next) side of the tree. - **In-order traversal**: Do the "parent" node of the tree, do the "left" (*prev) side of the tree, do the "right" (*next) side of the tree. - **Post-order traversal**: Do the "right" (*next) side of the tree, do the "parent" node of the tree, do the "left" (*prev) side of the tree. Binary trees can also be: * [[http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree|Unbalanced Binary Tree]]: Can be "left heavy" (more values on the left side) or "right heavy" (more values on the right side). * [[http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree|Balanced Binary Tree]]: Both sides of the tree are equal. Binary trees are primarily used because of there inherent efficiency over linked lists. A binary tree automatically sorts on retrieval of the tree (Pre-order = Least to Greatest/Post-order = greatest to least). It is also a guaranteed way of finding the highest/lowest value: the left most child is the lowest number in the tree, the right most child is the highest number in tree. Binary Trees can be represented as [[http://cs.lmu.edu/~ray/notes/binarytrees/|Strings]]. Also has information on counting the number of nodes in a tree using [[http://en.wikipedia.org/wiki/Catalan_numbers|Catalan Numbers]]. There are 3 simple rules: - Write the empty tree as: () - Write a non empty tree as: (leftSubtree root rightSubtree): %%((()%% **leftSubtree** %%())%% **root** %%(()%% **rightSubtree** %%()))%%, or just %%((%%**leftSubtree**%%)%% **root** %%(%%**rightSubtree**%%))%% - An empty subtree can be, and usually is, omitted. - 4 Ways to traverse a tree: * **Pre-order:** root, left, right. {{http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Sorted_binary_tree_preorder.svg/220px-Sorted_binary_tree_preorder.svg.png|Pre-order}}\\ **Pre-order:** F, B, A, D, C, E, G, I, H * **In-order:** left, root, right. {{http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Sorted_binary_tree_inorder.svg/220px-Sorted_binary_tree_inorder.svg.png|In-order}}\\ **In-order:** A, B, C, D, E, F, G, H, I * **Post-order:** left, right, root. {{http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/Sorted_binary_tree_postorder.svg/220px-Sorted_binary_tree_postorder.svg.png|Post-order}}\\ **Post-order:** A, C, E, D, B, H, I, G, F * **Level-order:** top (1st) level of the tree, 2nd level of the tree, 3rd level of the tree, etc. {{http://upload.wikimedia.org/wikipedia/commons/thumb/d/d1/Sorted_binary_tree_breadth-first_traversal.svg/220px-Sorted_binary_tree_breadth-first_traversal.svg.png|Level-order}}\\ **Level-order:** F, B, G, A, D, I, C, E, H **Traversing a Binary Tree: [[http://en.wikipedia.org/wiki/Tree_traversal|Examples]] for pretty Tree Traversal pictures:** * A tree with one element **'A'** is: %%(()%% **A** %%())%%, or just %%(%%**A**%%)%% * A tree with **'A'** as the root and **'B'** as the left subtree is: %%((()%% **B** %%())%% **A** %%())%%, or just %%((%%**B**%%)%% **A**%%)%% * A tree with **'A'** as the root and **'B'** as the right subtree is: %%(()%% **A** %%(()%% **B** %%()))%%, or just %%(%%**A** %%(%%**B**%%))%% * A tree with **'A'** as the root, **'B'** as the left subtree, and **'C'** as the right subtree is: %%((()%% **B** %%())%% **A** %%(()%% **C** %%()))%%, or just %%((%%**B**%%)%% **A** %%(%%**C**%%))%% * [[http://en.wikipedia.org/wiki/Catalan_numbers|Catalan Numbers]]: Calculate the number of distinct binary trees (**//C//**) with (**//n//**) nodes: {{http://cs.lmu.edu/~ray/images/catalan2.png|Catalan numbers}} ^ %%#%% of Nodes ^ %%#%% of Unique Binary Trees ^ | 00 | 1 | | 01 | 1 | | 02 | 2 | | 03 | 5 | | 04 | 14 | | 05 | 42 | | 06 | 132 | | 07 | 429 | | 08 | 1430 | | 09 | 4862 | | 10 | 16796 | Numbers are also represented differently in a binary tree: * In order (**Infix Notation**) uses [[http://en.wikipedia.org/wiki/Infix_notation|Infix Notation]]: Is human readable; follows the Order of Operations. Ex: (1+2)+3); Add 1 and 2, add the result and 3. * Pre order (**Prefix Notation**) uses [[http://en.wikipedia.org/wiki/Polish_notation|Polish Notation]]: Computes and reads data using a stack. Expressions are pushed first, then values are pushed: (+12)+3) would read as Add 1 and 2, add the result and 3. * Post order (**Postfix Notation**) uses [[http://en.wikipedia.org/wiki/Reverse_Polish_notation|Reverse Polish Notation]]: Also computes and reads data using a stack. Values are pushed first, then expressions are pushed next: (34+)6+) would read as 3 and 4 added, the result and 6 added. * //[[http://en.wikipedia.org/wiki/Shunting_yard_algorithm|Shunting-yard algorithm]]//: Something I found while Google'ing Polish/Reverse Polish Notation. It is a method for parsing mathematical expressions specified in infix notation. It can be used to produce output in Reverse Polish Notation (RPN) or as an Abstract Syntax Tree (AST). For the conversion there are two text variables (strings), the input and the output. There is also a stack that holds operators not yet added to the output queue. To convert, the program reads each symbol in order and does something based on that symbol. The **Shunting-yard Algorithm** has been later generalized into Operator-Precedence Parsing. **Casey's Quote of the Day**: Why did the Polish need to screw up numbers? They just need to learn PEMDAS. The rest of the class was spent working on the buildTree() function or any other projects. The logic was worked out on a whiteboard and paper for the binary tree code; and as I don't have a scanner I can't include the images. I took Matt's advice and stopped working on the sortList(); function for the singly linked list for awhile. I worked on my doubly linked list and got the displayForward();, displayBackward();, and clearList(); functions, and menu working. I thought about using a recursive function called displayList(), but Matt said it would cause problems with the other functions and is an easy fix. This time I decided to use chars for the case statement in the doubly linked list menu instead of ints. The only change is to use char input = 0 instead of an int input = 0. Then, put single quotes in the case's (' '): // Doubly Linked List Menu. int main() { /* Main Menu. Initialize "Node" to NULL. The i = input for the switch statement. */ Node *list = NULL; int input = 0; while (input != 'Q') { printf("\n"); printf("Generate a Doubley Linked List.\n"); printf("What would you like to do?\n"); // While loop for menu. while (input != 'Q') { printf("\n"); printf("N: Create a node.\n"); printf("D: Build a List.\n"); printf("A: Append a Node.\n"); printf("I: Insert a Node.\n"); printf("R: Remove a Node.\n"); printf("S: Sort a List (Least to Greatest).\n"); printf("L: List Quantity.\n"); printf("C: Clear a List.\n"); printf("F: Display a List Forward.\n"); printf("B: Display a List Backward.\n"); printf("Q: Quit.\n"); printf("Selection: "); scanf("%d", &input); printf("\n"); // Create a node. case 'N': list = createNode(); // Build a list. case 'D': list = buildList(list); break; // Append a Node. case 'A' list = appendNode(list); break; // Insert a Node. case 'I' list = insertNode(list); break; // Remove a Node. case 'R' list = removeNode(list); break; // Sort a List (Least to Greatest). case 'S' list = sortList(list); break; // List Quantity. case 'L' list = displayListf(list); break; // Clear a List. case 'C' list = clearListf(list); break; // Display a List Forward. case 'F' list = displayListf(list); break; // Display a List Backward. case 'B' list = displayListb(list); break; // Quit case. case 'Q': // Print prompt on next line. printf("/n"); break; // When nothing matches case statement. default: printf("Invalid choice. Please choose again."); printf("/n"); break; } } return(0); } ====October 31, 2013==== [[http://www.youtube.com/watch?v=AxcM3nCsglA|Groovy Goolies]]\\ [[http://www.youtube.com/watch?v=KvkKX035484|Who ya' gonna call?]]\\ [[http://www.youtube.com/watch?v=sOnqjkJTMaA|And of course...]] Today was a work day. I asked Matt what our Binary Tree should do with duplicate values. Duplicate values need to omitted by exiting the insertNode(); function (if node->value = newNode->value) {exit insertNode();}). There also needs to be a function to compare the values in the nodes to insert them in the correct places. Tree values are ints, but could include chars since char includes ints. First, I worked on the logic code for the binary tree. Then I read through the "rules" for the 4 card games, copied them to the project page, and played some FreeCell. (This is no longer the final exam program...I don't know if that's good news or bad): struct node { // *root only needed for first node; always points to top of tree. Ignored/Not used for other nodes. struct node *up; struct node *prev; struct node *next; int input; }; typedef struct node Node; struct tree { struct node *root; // The "height" of the tree, not the quantity of nodes. int height; } // Function calls. Node *createNode(Node *); Node *createTree(Node *); Node *displayListF(List *); Node *displayListB(List *); Node *clearList(List *); Node *createTree(Node *root) { if (*root = NULL) { root = createNode(); root -> up = NULL; *prev = NULL; *next = NULL; // Insert first value of list into node, iterate to next value in list. } // At least one node in tree. While loop to stop when no more values to insert into tree. else { *up = node->prev. *prev = createNode(); *next = createNode(); // Insert a value from the list into node, iterate to next value in list. while (listQty != 0) insertNode(); // Insert next value into node. node->value = input; // Iterate to the next value node->next = node; // Decrement listQty. listQty = listQty-- } } \\ I also worked on and tweaked my doubly linked list some more. I wrote the displayListF();, displayListB();, and clearList();. I had the idea of assigning *beg and *end pointers in the list. This will make the sortListF(); and sortListB(); functions easier to implement. displayListF(); can be set to *beg and incremented forwards and displayListB(); can be set to *end and decremented backwards. \\ \\ /* Set the pointers *beg and *end for displayListF(); and displayListB();. Both pointers point to the beginning and end of the list. */ // Set tmp to the *beg pointer. tmp = *beg; // Iterate through the list for *end. while (tmp != NULL) { tmp = tmp->next; // Set the *end pointer. if (tmp == NULL) { tmp = *end } } \\ // Display List Forward: Set to *tmp to *beg of the list and increment to the end displaying values. // NOTE: Print "NULL" at beginning and end of the list, DLL = NULL <=> list <=> NULL? Node *displayListF(Node *list) { int input = 0; // Initialize pointer tmp to NULL. Node *tmp = NULL; // Set tmp to the beginning of the list. Node *tmp = beg; printf("Nodes in ascending order: "); // Print "NULL" at beginning of list. printf("NULL\n"); // Set *tmp to *beg of list; iterate forward. while (tmp != end) { printf("[%d] %d -> ", input, tmp->value); tmp = tmp->next; } // Print "NULL" at end of list. printf("NULL\n"); return (list); } \\ // Display List Backward: Set to *tmp to *end of the list and decrement to the beginning displaying values. // NOTE: Print "NULL" at beginning and end of the list, DLL = NULL <=> list <=> NULL? Node *displayListB(Node *list) { int input = 0; // Initialize pointer tmp to NULL. Node *tmp = NULL; // Set tmp to the end of the list. Node *tmp = end; printf("Nodes in descending order: "); // Print "NULL" at end of list. printf("NULL\n"); // Set *tmp to *end of dll; iterate backward; while (tmp != *beg) { printf("[%d] %d <- ", input, tmp->value); // Decrement *tmp. tmp = tmp->prev; } // Print "NULL" at beginning of list. printf("NULL\n"); return (list); } \\ // Clear List: Set to *tmp to *beg of the list and increment to the end removing nodes. // NOTE: Print "NULL" at beginning and end of the list, DLL = NULL <=> list <=> NULL? Node *clearList(Node *list) { // Set *tmp to *beg of list; iterate forward; removing nodes. Node *tmp = beg; while(tmp != end) { removeNode(Node *); tmp = tmp->next; } // Reset *beg and *end to NULL. beg = NULL; end = NULL; } ====November 1, 2013==== Today was another work day. sortList(); problem solved; sort of. The problem was in the appendNode(); function and not the sortList(); function. Both the appendNode(); and removeNode(); functions are used in the sortList(); function. I re-wrote working code 9 times because I was looking in the wrong function...:-X This would have been fixed earlier but I was using "**next**" (single step the program; step **OVER** functions) instead of "**step**" (single step the program; step into functions) when running the program in GDB. The doubly linked list is almost complete, only 2 or 3 functions to write. Having prior knowledge of Stacks and Queues, writing them should not be a problem. I can re-use the same code for setting the beginning and end pointers from my doubly linked list for my queue: Since the Queue is a FIFO/LILO it needs a *beg and *end pointer. values are enqueue'd (pushed) to the back of the queue values are dequeue'd (popped) from the front of the queue. /* Set the pointers *beg and *end. Both pointers point to the beginning and end of the list. Enqueue: Dequeue: */ // Set tmp to the *beg pointer. tmp = *beg; // Iterate through the list for *end. while (tmp != NULL) { tmp = tmp->next; // Set the *end pointer. if (tmp == NULL) { tmp = *end } } **GDB Cheat Sheets:**\\ [[http://web.cecs.pdx.edu/~jrb/cs201/lectures/handouts/gdbcomm.txt|Simple GDB Cheat Sheet]]\\ [[http://www.yolinux.com/TUTORIALS/GDB-Commands.html|YoLinux GDB Cheat Sheet]] =====Week 11:===== ====November 6, 2013==== Inserting/Removing nodes in a Binary Tree; 3 ways: - Iterative Binary Tree Insert: Using loops to traverse the list. I need to remember that arrays start counting at 0. - Recursive Binary Tree Insert (shorter) - Stack Based Binary Tree Insert: Stack handles traversal through binary tree. Make one modification to Node struct: Add a Node *data; member. Also write a displayTree(); function: - Display Value: Display trees in sorted order. - Display Tree: Display the entire Tree. Also contemplate the removeNode(); function for the Binary Tree. I worked on the menu for my Queue: /* Nick Brimmer Data Structures Mathew Haas Spring 2013 A Queue using a DLL: A Queue is a First-In-First-Out (FIFO) or a Last-In-Last-Out (LILO) data structure. Nodes are inserted from the back (Enqueue) and deleted from the front (Dequeue). **There is no project page.** */ #include struct node { struct node *next; struct node *prev; int data; }; typedef struct node Node; // Pointers to the front and back of the Queue. node *frnt; node *back; // Push value to Queue. node enQueue(int); // Pop value from Queue. node deQueue(int); // Display Queue. node disQueue(list); main() { // Clears the screen. clrscr(); // opn = option for case statement menu; elem is element inside node. int opn, elem; // *frnt and *back pointers initialized to NULL; frnt = back = NULL; /* Set the *frnt and *back pointers. Enqueue: Insert from the *back Dequeue: Delete from the *frnt */ // Set front pointer to tmp. Queue = *frnt; // Iterate through the list for *end. while (tmp != NULL) { tmp = tmp->next; // Set the *end pointer. if (tmp->next == NULL) { tmp = *end } } while (opn != 4) { printf("A Queue using Doubly Linked Lists:\n"); printf("1. Enqueue a Node from the back.\n"); printf("2. Dequeue a Node from the front.\n"); printf("3. Display the Queue.\n"); printf("4. Exit\n"); printf("Selection: "); scanf("%d", &opn); switch (opn) { case 1: printf("Enqueue Node: "); scanf("%d", &elem); Insert(elem); break; case 2: elem = deQueue(); if (elem != -1) printf("Node Dequeued with the Data: %d\n", elem); break; case 3: printf("Display Queue:\n"); Display(); break; case 4: printf("\n"); break; default: printf("Invalid Option. Please choose again.\n"); break; } } } ====November 7, 2013==== Work day. Matt has taught everything he's going to teach; so the rest of the semester will most likely be work days. ====November 8, 2013==== A work day. I worked on entering code into my opus. =====Week 12:===== ====November 13, 2013==== Another work day. I worked on entering more code into my opus. ====November 14, 2013==== Another work day. I started my Binary Tree. I asked Matt how the tree should be display; since there is no project page. The displayTree function should display the tree in a directory tree format and also display the VALUES in the nodes in sorted order; and don't display the nodes. ====November 15, 2013==== Matt gave us a preview of the **EoCE** ('End of Course Experience'); it is located in: lab46:~$ cd /var/public/data/fall2013/EoCE/ll_oop_reimp lab46:/var/public/data/fall2013/EoCE/ll_oop_reimp$ To copy the code into your **/home** directory (from **Lab46**; **make copy** copies to //~/src/data/EoCE/ll_oop_reimp///): lab46:/var/public/data/fall2013/EoCE/ll_oop_reimp$ make copy mkdir -p ~/src/data/EoCE/ll_oop_reimp cp -av /var/public/data/fall2013/EoCE/ll_oop_reimp/* ~/src/data/EoCE/ll_oop_reimp/ `/var/public/data/fall2013/EoCE/ll_oop_reimp/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/inc/list.h' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/inc/list.h' `/var/public/data/fall2013/EoCE/ll_oop_reimp/inc/queue.h' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/inc/queue.h' `/var/public/data/fall2013/EoCE/ll_oop_reimp/inc/stack.h' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/inc/stack.h' `/var/public/data/fall2013/EoCE/ll_oop_reimp/inc/node.h' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/inc/node.h' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/append.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/append.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/display.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/display.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/insert.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/insert.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/sort.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/sort.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/destroy.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/destroy.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/size.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/size.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/getnode.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/getnode.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/list/create.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list/create.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/stack/push.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack/push.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/stack/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/stack/destroy.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack/destroy.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/stack/size.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack/size.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/stack/create.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack/create.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/stack/peek.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack/peek.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/stack/pop.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack/pop.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/queue/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/queue/destroy.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue/destroy.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/queue/size.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue/size.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/queue/dequeue.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue/dequeue.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/queue/create.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue/create.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/queue/enqueue.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue/enqueue.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/btree/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/btree/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/prev.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/prev.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/destroy.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/destroy.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/create.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/create.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/next.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/next.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/data.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/data.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/copy.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/copy.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/src/node/value.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node/value.cc' `/var/public/data/fall2013/EoCE/ll_oop_reimp/testing/Makefile' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/testing/Makefile' `/var/public/data/fall2013/EoCE/ll_oop_reimp/testing/stacktest.cc' -> `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/testing/stacktest.cc' lab46:/var/public/data/fall2013/EoCE/ll_oop_reimp$ Currently; Everything compiles according to function prototypes, but Matt MIGHT change the code so I won't start this yet (like adding comments...). In the code provided by Matt, the stack and queue do not include a list; they inherit a list. Matt provided the OOP-List-Insert function as an example; but *next and *prev are private so other functions are going to need to inherit them (only the OOP-List can directly access them). Matt also added another element to node; a data element node pointer that points to the data inside the node. Matt also ported the stacktest code to test the Object Oriented Stack. The **EoCE** will consist of a re-implementation of previous code (everything but binary tree; just the node, list, stack, and queue) in Object-Oriented C++ and some questions. Matt also wants to meet with everyone separately to see that you have a conscious idea of what your code does and also that your code works. =====Week 13:===== ====November 20, 2013==== Matt went over the End of Course Experience (hereby referred to as the EoCE). It will appear at the bottom of our opus. Then it was a work Day. ====November 21, 2013==== Started/looked at parts of the EoCE C++ reimplementation. Matt's skeleton code looks simple enough but I'm super rusty at C++. ====November 22, 2013==== node / \ list binary tree / \ stack queue =====Week 14:===== ====November 27-29, 2013==== No Class, **Thanksgiving Break**. Noticed Matt made some changes to the EoCE; recopied the code: lab46:/var/public/data/fall2013/EoCE/ll_oop_reimp$ make copy I also added a node quantity function to my SLL and DLL code; which TARFU'ed my code. This in turn TARFU'ed my header files, which TARFU'ed the rest of my programs that rely on the header file. Important lesson of the day: **COMMIT MORE OFTEN**. **Current Status: SNAFU** **__To Do List:__** * SLL: sortList broken; compiled clean. Added nodeQty and now its TARFU'ed. * DLL: FUBAR'ed. Need to split up main.c, fix createNode, appendNode, sortList (maybe), and clearList. * Stack: Will work when I fix the header file. * Queue: Will work when I fix the header file. * Card Game: Lost Cause * EoCE: Brushing up on my C++. =====Week 15:===== ====December 4, 2013==== Fixed the SLL; sort still seg. faults. ====December 5, 2013==== Still working on the EoCE reimplementation. ====December 6, 2013==== Matt made some more changes to the EoCE C++ Re-Implementation. Still working on that. =====Week 16:===== ====December 11, 2013==== Worked on the reimplementation files. Almost all the C++ files in EoCE/ll_oop_reimp/src/node are complete. The only one left to write is **copy.cc**. I'm going to skip it for now and work on the other files. I also started working on the C++ files in //EoCE/ll_oop_reimp/src/list//. ====December 12, 2013==== I've been working on the C++ OOP Reimplementation of the DLL, Stack, and Queue. All C++ files in //EoCE/ll_oop_reimp/src/node// are finally complete. I was having trouble with **copy.cc**, but after getting it on paper the answer jumped out at me. I Haven't tried to compile anything yet; going to work more on the rest of the reimplementation files. I'm almost done with the C++ files in //EoCE/ll_oop_reimp/src/list//. Next is the Stack and Queue. To copy a node; 2 tmp variables are needed (*tmp is the node to copy and *tmp2 is the resulting empty node). Functions in create.cc, next.cc, prev.cc, value.cc, and data.cc "get" values from *tmp and "set" values to *tmp2. For Example: * Call **create.cc** to declare tmp and create tmp2, an empty node. Node *tmp; Node *tmp2 = new Node; * Call **next.cc** to get tmp's next pointer and set tmp2's next pointer (Node::getNext(tmp); -> Node::setNext(tmp2);) tmp = this -> getNext(); tmp2 -> setNext(tmp) * The same thing is done using **prev.cc**, **value.cc**, and **data.cc** to get and set the new nodes values. tmp = this -> getPrev(); tmp2 -> setPrev(tmp); tmp = this -> getValue(); tmp2 -> setValue(tmp); tmp = this -> getData(); tmp2 -> setData(tmp); * Return the copy of the node tmp return(tmp2); ====December 13, 2013==== **D-Day** has arrived. Showed Matt my code. This is the result of running make: lab46:~/src/data/EoCE/ll_oop_reimp/src$ make make[1]: Entering directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/btree' [L] ... SUCCESS make[1]: Leaving directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/btree' make[1]: Entering directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list' [B] append.cc ... append.cc: In member function 'void List::append(Node*, Node*)': append.cc:8: error: a function-definition is not allowed here before '{' token append.cc:38: error: expected '}' at end of input FAIL [B] create.cc ... OK [B] destroy.cc ... ../../inc/node.h: In destructor 'List::~List()': ../../inc/node.h:22: error: 'Node* Node::next' is private destroy.cc:10: error: within this context FAIL [B] display.cc ... display.cc: In member function 'void List::displayb()': display.cc:28: error: ISO C++ forbids comparison between pointer and integer FAIL [B] end.cc ... end.cc: In member function 'Node* List::getEnd()': end.cc:6: error: expected ')' before ';' token end.cc:6: error: expected primary-expression before ')' token end.cc:6: error: expected ';' before ')' token FAIL [B] getnode.cc ... getnode.cc: In member function 'Node* List::getNode(Node*)': getnode.cc:9: warning: no return statement in function returning non-void OK [B] insert.cc ... OK [B] size.cc ... OK [B] sort.cc ... sort.cc: In member function 'void List::sort()': sort.cc:5: error: 'list' was not declared in this scope sort.cc:6: error: 'list' is not a class or namespace sort.cc:6: error: 'i' was not declared in this scope sort.cc:9: error: 'cout' is not a member of 'std' sort.cc:11: error: request for member 'begin' in 'this', which is of non-class type 'List* const' sort.cc:11: error: request for member 'end' in 'this', which is of non-class type 'List* const' sort.cc:18: error: 'cout' is not a member of 'std' sort.cc:20: error: return-statement with a value, in function returning 'void' sort.cc: At global scope: sort.cc:34: error: expected declaration before '}' token FAIL [B] start.cc ... start.cc: In member function 'Node* List::getStart()': start.cc:6: error: expected ')' before ';' token start.cc:6: error: expected primary-expression before ')' token start.cc:6: error: expected ';' before ')' token FAIL [L] ... ar: append.o: No such file or directory FAIL make[1]: Leaving directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/list' make[1]: Entering directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node' [B] copy.cc ... copy.cc: In member function 'Node* Node::copy()': copy.cc:14: error: expected ';' before 'tmp' copy.cc:18: error: invalid conversion from 'int' to 'Node*' copy.cc:19: error: invalid conversion from 'Node*' to 'int' copy.cc:19: error: initializing argument 1 of 'void Node::setValue(int)' FAIL [B] create.cc ... OK [B] data.cc ... OK [B] destroy.cc ... OK [B] next.cc ... OK [B] prev.cc ... OK [B] value.cc ... OK [L] ... ar: copy.o: No such file or directory FAIL make[1]: Leaving directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/node' make[1]: Entering directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue' [B] create.cc ... OK [B] dequeue.cc ... dequeue.cc: In member function 'Node* Queue::dequeue()': dequeue.cc:6: warning: no return statement in function returning non-void OK [B] destroy.cc ... OK [B] enqueue.cc ... OK [B] size.cc ... size.cc: In member function 'int Queue::getBufferSize()': size.cc:6: warning: no return statement in function returning non-void OK [L] ... SUCCESS make[1]: Leaving directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/queue' make[1]: Entering directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack' [B] create.cc ... create.cc: In constructor 'Stack::Stack(int)': create.cc:18: error: returning a value from a constructor FAIL [B] destroy.cc ... destroy.cc: In destructor 'Stack::~Stack()': destroy.cc:11: error: lvalue required as left operand of assignment FAIL [B] peek.cc ... peek.cc: In member function 'Node* Stack::peek()': peek.cc:5: error: 'stack' was not declared in this scope peek.cc:6: error: expected ';' before '}' token FAIL [B] pop.cc ... pop.cc: In member function 'Node* Stack::pop()': pop.cc:6: warning: no return statement in function returning non-void OK [B] push.cc ... OK [B] size.cc ... ../../inc/list.h: In member function 'int Stack::getSize()': ../../inc/list.h:21: error: 'Node* List::start' is private size.cc:15: error: within this context size.cc:15: error: cannot convert 'Node*' to 'List*' in assignment size.cc:23: error: 'class List' has no member named 'getNext' size.cc:26: error: invalid conversion from 'List*' to 'int' size.cc:27: error: expected ';' before '}' token FAIL [L] ... ar: create.o: No such file or directory FAIL make[1]: Leaving directory `/home/nbrimme1/src/data/EoCE/ll_oop_reimp/src/stack' lab46:~/src/data/EoCE/ll_oop_reimp/src$ ls ../lib/ libbtree.a libqueue.a lab46:~/src/data/EoCE/ll_oop_reimp/src$ ls ../lib/ -l total 16 -rw-r--r-- 1 nbrimme1 lab46 8 Dec 13 10:24 libbtree.a -rw-r--r-- 1 nbrimme1 lab46 8828 Dec 13 10:24 libqueue.a They seem like simple errors; I need to add the corrections **AND** code to the bottom of my Opus in the EoCE section.