======Data Structures Journal====== ====September 3, 2014==== ====The Beginning==== In the beginning of class we went over the new notes system, and point give-away system. From that point we moved to attaching to the class chat. Class Chat: screen -l uf "No Socket" -->Screen irssi /server irc /join #csci (Class chat) /join lab46 (Bot talk) to disconnect: ctrl-a then d to reconnect from this point onward: screen -r Then we moved on to The Great C Review. Pointers (Supposedly we will see the true power behind these in data structures) Pointers are what give C its incredible cosmic power. it is very small, yet very powerful. Pointers refer to memory (RAM, Storage) int a; In memory, represented as a square. The square is broekn up into units called bytes. (1 Byte is 8 bits...some machines actually used to be 7 bits to a byte.) We use Hexedecimal digits to show the memory address such as: 0x32 (1 Byte Address) and 0xdeadbeef (Which is a 4 byte address) int *c; *- dereferencing operator ------------------------------- int a=5; int *c; c=&a; ====09/11/2014 (Week 3)==== We started the day from a program unfinished from Tuesday \\ The first node is a variable without the "variable" \\ Data is then stored inside of the first node via a struct pointer \\ pointer->member = something; \\ tmp ---> Null \\ tmp ---> balloon (12) ---> Null \\ tmp ---> balloon (12) ---> balloon \\ tmp ---> balloon (12) ---> balloon (3) ---> Null \\ The code that we worked on throughout class: \\ #include \\ #include \\ struct node { \\ char value; //value bucket \\ struct node *next; \\ }; \\ typedef struct node Node; //for us to make typing easier \\ int main() \\ { \\ char input; \\ Node *tmp = NULL, *tmp2 = NULL; \\ tmp = (Node*)malloc(sizeof(Node)); \\ tmp->value = 12; \\ tmp->next = (Node*)malloc(sizeof(Node)); \\ tmp->next->value = 3; \\ tmp->next->next = (Node*)malloc(sizeof(Node)) \\ tmp->next->next->value = 42; \\ tmp->next->next->next = NULL; \\ tmp2 = tmp; \\ tmp = tmp->next; \\ For Unix: Relative Reference \\ Linked List | Array \\ -------------------------------------------- \\ unending, dynamic | performance \\ space-time <-- solutions are bounded by these \\ Looking forward to these topics in the future! : \\ Hashtables \\ Que's \\ Mixtures of Array's and Linked lists \\ =====09/30/2014===== We went over the sll0 project. More information can be obtained from the projects page on the wiki. We also learned a little bit about the debugger. To compile with debugger support you type in gcc -g -o executable "name" "file_name" To run the program with the debugger you type gdb ./"file_name" You can also run the program normally without debugger support ==A few commands for the debugger are:== *run : runs the program Reading symbols from ./sll...done. (gdb) run *break : sets a break point so the program will run all lines up until the line that the break point was set (gdb) break 55 Breakpoint 1 at 0x4008e8: file sll-debug.c, line 55. *list : lists the first 10 of the program(with line #) (gdb) list 6 struct node *next; 7 }; 8 typedef struct node Node; 9 void display(Node *); 10 int main() 11 { 12 Node *start, *end, *tmp, *tmp2; 13 char input; 14 15 start = end = tmp = tmp2 = (Node *) malloc (sizeof(Node)*1); (gdb) *display : displays the value of the specified variable and it is updated each step in the program (gdb) display tmp2->value 1: tmp2->value = 1 '\001' (gdb) (gdb) s 56 tmp2 = tmp2 -> next; 1: tmp2->value = 1 '\001' (gdb) s 55 while (tmp2 -> next -> value != input)//used to be tmp -> value) 1: tmp2->value = 2 '\002' (gdb) s 56 tmp2 = tmp2 -> next; 1: tmp2->value = 2 '\002' (gdb) *print : prints what value the variable holds at that moment (gdb) print tmp2->next->value $1 = 3 '\003' (gdb) *[s]tep : runs the next step of the program (will step inside function calls) Breakpoint 1, main () at sll-debug.c:15 15 start = end = tmp = tmp2 = (Node *) malloc (sizeof(Node)*1); (gdb) s 16 tmp -> value = 0; (gdb) s 17 tmp -> next = NULL; (gdb) s 19 fprintf(stdout, "Enter a value (-1 to complete): "); (gdb) s 20 fscanf(stdin, "%hhd", &input); (gdb) *[n]ext : runs the next step of the program (does not step inside function calls (will treat a function call as a single line) *[c]ontinue : runs the program normally from the last stoping point Starting program: /home/mb006142/src/data/classtest/sll Enter a value (-1 to complete): 1 Enter a value (-1 to complete): 2 Enter a value (-1 to complete): 3 Enter a value (-1 to complete): 4 Enter a value (-1 to complete): -1 1 -> 2 -> 3 -> 4 -> NULL Enter value for new node: 5 Enter value of node you want to insert new node before: 4 Breakpoint 1, main () at sll-debug.c:55 55 while (tmp2 -> next -> value != input)//used to be tmp -> value) (gdb) c Continuing. 1 -> 2 -> 3 -> 5 -> 4 -> NULL [Inferior 1 (process 11161) exited normally] (gdb) *quit : exits debugger *help : get additional details about the commands (gdb) help List of classes of commands: aliases -- Aliases of other commands breakpoints -- Making program stop at certain points data -- Examining data files -- Specifying and examining files internals -- Maintenance commands obscure -- Obscure features running -- Running the program stack -- Examining the stack status -- Status inquiries support -- Support facilities tracepoints -- Tracing of program execution without stopping the program user-defined -- User-defined commands Type "help" followed by a class name for a list of commands in that class. Type "help all" for the list of all commands. Type "help" followed by command name for full documentation. Type "apropos word" to search for commands related to "word". Command name abbreviations are allowed if unambiguous. (gdb) =====10/02/2014===== We continued with the debugger, learning some new commands as well as stepping through the sll-debug program to see where the segmentation fault problem is. A few more commands for the debugger: *whatis "variable name" - shows the data type of the specified variable *x "variable name" - prints the variable value in hex *set var "var name"="new value" will set the specified variable to the new value that you type in. *disas /m "function name" - disassembles the given function and displays it in assembly code Step by step guide to debugging sll-debug.c: step 1: compile with debug support gcc -g -o sll-debug sll-debug.c step 2: launch the debugger (gdb) gdb ./sll-debug step 3: gdb run this will run the program and tell what line the seg fault occured step 4: set breakpoints and analyze (gdb) break 55 (this is where the seg fault occured) (gdb) run step 5: check variable status print tmp2 -> next -> value print tmp -> value print tmp2 print tmp print tmp -> next step 6: setup auto display of variables display tmp2 -> next -> value display tmp -> value display tmp2 -> next display tmp2 display tmp step 7: watch it loop [s]tep or [n]ext as we loop through the program we see that the line while(tmp2->next->value != tmp->value) is the problem: we should be looking for the input that we had just typed in, and not tmp's value. =====10/07/2014===== ===swap node=== {{:opus:fall2014:mgardne8:1.bmp|}} ==Bad!== Node *tmp3 = mknode(tmp->value); tmp->value=tmp2->value; tmp2->value=tmp3->value; free(tmp3); ==good!== {{:opus:fall2014:mgardne8:2.bmp|}} ===Obtain node=== Pulls node from list, patches hole in list, keeps pulled node. {{:opus:fall2014:mgardne8:3.bmp|}} myList = obtain(myList, &tmp) { int pos = getpos(myList, &tmp); Node *tmp2; tmp2 = setpos(myList, pos-1); tmp2->next = tmp->next; *(tmp)->next = NULL; myList->qty--; return(myList); } myList = obtain(myList, &tmp) { Node *tmp = setpos(myList, getpos(myList, tmp)-1); tmp2->next = tmp->next; *(tmp)->next = NULL; myList->qty--; return(myList); } {{:opus:fall2014:mgardne8:4.bmp|}} myList = obtain(mylist, &tmp); ==Implementation tips== (*tmp)->value ===Misc. Notes=== Obtain is the only function in our linkedlist library where we will pass by value; ==Passing variables== -Pass by value *Passes copy *myList=insert(myList,tmp,tmp2); -Pass by address/reference *changes happen outside of the function *pointers! =====10/27-10/30===== Most of our focus was on preparing for the assessment. This was simply what I had worked on to prepare for it. ===Creation=== struct thing { char value; int num; struct thing *up; struct thing *down; }; typedef struct thing Thing; Thing *mkthing(char zebra, int dog) { Thing *tmp = (Thing *)malloc(sizeof(Thing)); tmp -> value = zebra; tmp -> num = dog; tmp -> up = NULL; tmp -> dowm = NULL; return(tmp); } //Thing *tmp = mkthing('c', 42); //makes tmp point to a thing that has the character 'c' and the integer 42 inside of it. ===Destruction=== Thing *rmthing(Thing *oldThing) { if(oldThing != NULL) { oldThing -> value = NULL; oldThing -> num = NULL; oldThing -> up = NULL; oldThing -> down = NULL; free(oldThing); } return(NULL); } //tmp = rmthing(tmp); //Unallocates tmp and sets tmp equal to NULL ===Duplication=== Thing *cpthing(Thing *something) { if( something != NULL) { Node *copiedthing = mkthing( something -> value, something -> num); copiedthing -> up = something -> up; copiedthing -> down = something -> down; return(copiedthing); } else { return(NULL); } } //randomthing = cpthing(tmp); //Copies tmp into randomthing. sruct stuff { char name; struct stuff *bottom; struct stuff *top; }; typedef struct stuff Stuff; ===Stuff Creation=== mklist.c Stuff *mkstuff(char bob) { Stuff *newStuff = (Stuff *)malloc(sizeof(Stuff)); newStuff -> name = bob; newStuff -> top = NULL; newStuff -> bottom = NULL; return(newStuff); } //Stuff *zebras = mkstuff('z'); //This makes zebras point to a stuff that contains character 'z'. ===Place Thing Above This (Append)=== Stuff *appendthing(Stuff *myStuff, Thing *place, Thing *newThing) { if(myStuff == NULL) { myStuff -> bottom = newThing; myStuff -> top = newThing; } else { place -> up = newThing; newThing -> down = place; if(place == myStuff -> top) { myStuff -> top = newThing; } } return(myStuff); } //zebras = appendthing(zebras, zebra1, newZebra); //This puts newZebra after zebra1 in zebras. ===Place Thing Below This (Insert)=== Stuff *insertthing(Stuff *myStuff, Thing *place, Thing *newThing) { if(myStuff == NULL) { myStuff -> bottom = newThing; myStuff -> top = newThing; } else { place -> down = newThing; newThing -> up = place; if(place == myStuff -> bottom) { myStuff -> bottom = newThing; } } } =====11/3-11/6===== for(i=1; i<=96; i+=7) { if((i % 6)==3) { status=push(&s, mknode(i+1)); if(status==0) { n1=peek(s); push(&s,mknode(n1->data)-1)); } else if(status = -1) { pop(&s, &n1); if((i%2)==0) pop(&s, &n2); =====11/11-11/13===== Think: Stopping at a red light in an order, instead of mass chaos...not just the common sense but 'Why?' ====11/18 Trees==== A **tree** is a data structure associated with the visualization of a parent-child relationship. The set up is similar to the vertical structure of a stack except the nodes branch out from a root instead of being stacked on top of each other. The root has a next and prev to a node, in which the next branches a node to the right and the prev branches a node to the left. The node struct contains the same as before except with an added **other** pointer. Specifically, the **other** pointer will be used for iterative and stack-based operations like trying to traverse back up the tree. We can traverse through the list in a stack-based, iterative, or recursive manner. We'll use an **addnode** function to add a given node to a tree. With the root being at height zero, each added layer of branched nodes adds to the height. The **max_height** places a limit on the number of nodes you can put into the tree. {{:notes:tree_diagram.jpg?900 |}} {{:notes:unbalanced_tree.jpg?900 |}} {{:notes:balanced_tree.jpg?900 |}} {{:notes:node_tree.jpg?900 |}}