======Data Structures Journal======
====August 26 & 28, 2014====
This week in class, we spent some time discussing what Data Structures, Algorithms, class expectations, Internet Relay Chat (IRC), and Mecurial.
I learned that there are an infinite amount of data structures, but that we will only learn about a few because they have proven themselves useful over time. We will focus on link lists, list state, and queues. We discussed that data structure involves problem solving. Data structures are used as a way of organizing data in a computer so that the data can be used in the most efficient way possible. Algorithms are made using logic and math. They have step by step procedures for calculating math. They have a run time function of when they are complete.
We used the IRC, which is an ongoing chat room presence. We learned how to switch between different chats while keeping the other's open. I found Wezlbot to be very interesting.
We also spent a significant amount of time setting up our Lab46 Mercurial repository. We identified several different commands and set up a folder in a sub-directory. We also discussed how committing projects allows us to use Mercurial for version control.
===Action or concept of significance:===
I believe that understanding the concepts of adding, committing, and pushing was the most significant concept we discussed. This is significant because we use Mercurial to do these and for version control.
===Questions and Challenges:===
I understand what adding, committing is used for and what they are, but I don't understand how to use Mercurial for version control in the Unix environment yet. I also find that the "lair" is an entirely different learning environment than I am used to. I think with time I will become more comfortable and have a better understanding of different processes.
====September 2 & 4,2014====
===Action or Concept of Significance:===
This week in class we started reviewing **Pointers**.
**Pointers**
* refers to memory (RAM and storage)
* programs exist in RAM
* memory is broken up in bytes (the smallest unit on a computer), predominantly RAM (physical aspect), but all memory is included with the use of pointers
_|0|1|2|3|4|5|6|7|
0|_|_|_|_|_|_|_|_|
1|_|_|_|_|_|_|_|_|
2|_|_|_|X|_|_|_|_| represents 32 byte memory address
3|_|_|_|_|_|_|_|_|
4|_|_|_|_|_|_|_|_|
5|_|_|_|_|_|_|_|_|
6|_|_|_|_|_|_|_|_|
7|_|_|_|_|_|_|_|_|
* 0-7 memory addresses =32 bytes
* 8-16 memory addresses =64 bytes
* Every byte is addressable
* memory is referenced in hexadecimal- base 16
* can reference in decimal but we will want to interpret. We are less prone to interpret when in hexidecimal formation
* 0 x 32 - notated hexadecimal
* 1 byte = 8 bits
* 2⁸ = 256 bits
* 16 x 16 =256
* 32 bit memory system is limited to 4 bytes in addresses
* 64 bit memory systems use 8 bytes in addresses.
* Memory Systems denote the amount of information a processor can obtain for the instruction set to fetch. A 64 bit memory system can grab more information in the same amount of time as a 32 bit memory system
* Unique bytes available 2^8 =256 bytes, 2^16= 65,536 bytes, 2^32= 4.2 billion bytes, 2^64=18,446,744,073,709,551,616
* When allocating a 4 bytes they are consecutive- given in linear order
**Pointers** is a variable that contains memory address, all are the same size, and allocates type
* point at something with a second operator (C = &a; address of)
* doesn't contain a usable number- just an address
* the OS gives an address to work with
* int a; int b; int c; given address
*must point to something significant to make valuable
*c= &a; C contains the address of a. C points to someplace else
*Need to know the type of pointer to know how much memory is needed- Allocated Memory Changes
**4 Element Array**
int g[4];
*translates to-
int *g=(int * )malloc(size of(int) *4);
*since memory is allocated in a linear order, if given the array of
g[2] =13;
*must move address over by two integers.
===Questions and Challenges:===
In class we were given the code as an explanation to using pointers. I'm struggling while learning to navigate around lab46 and with using the terminal. I didn't get the experience using these in C/C++ and I find myself fumbling around. Writing programs while on the terminal is confusing because I don't know the short cuts and because I don't remember all the commands to load, compile, and write. In class, when we were given the code to write for pointers, I still had errors and was unable to compile. While trying to fix them and remember how to navigate within the terminal, I missed explanations that were given in class and didn't get to completely follow what we were learning. I couldn't even see what was returned to know what was being discussed. This is a challenge for me because there are more experienced "lair" students than I. I don't know if I should interrupt to get help or wait until a later time, as I learn with practice.
====writing code using pointers====
====nano pointerfile1.c====
We wrote two programs in class using integer pointers, character pointers, and pointers to the memory address of each of these. Every integer or character has an address given at runtime.
===The following is code that we explored:===
#include
int main()
{
int a;
int *b;
char c;
char *d;
* int a; -is an integer
* int *b; -is calling the address at b
* char c; -is a character pointer
* char *d; -is calling for the address at d
a = 17;
b = &a;
c = 'X';
d = &c;
* a is assigned as 17
* b is assigned as the address of a
*c is assigned as the character X
*d is assigned as the address of c
printf("address of a is: %p\n", &a);
printf("address of b is: %p\n", &b);
printf("address of c is: %p\n", &c);
printf("address of d is: %p\n", &d);
printf("-----------------------------\n");
* printf of the the above code displayes the memory address of the assigned and the address location.
printf("a contains: %d\n", a);
printf("b contains: %p\n", b);
printf("c contains: '%c' (%hhd)\n", c, c);
printf("d contains: %p\n", d);
printf("-----------------------------\n");
* printf of the above code displays what is contained in each of the addresses.
printf("b dereferenced is: %d\n", *b);
printf("d dereferenced is: '%c' (%hhd)\n", *d, *d);
printf("-----------------------------\n");
* When a pointer is dereferenced, the computer will access inside of what the address pointer contains. Printf displayes the derefrenced memory address.
printf("a is %d bytes\n", sizeof(a));
printf("b is %d bytes\n", sizeof(b));
printf("c is %d bytes\n", sizeof(c));
printf("d is %d bytes\n", sizeof(d));
printf("-----------------------------\n");
* These printf statements displays the byte size of each.
return(0);
}
===Then we made the following changes to the code:===
====nano pointerfile2.c====
#include
int main()
{
int 17;
int *b;
char c;
char *d;
a = 17;
b = &a;
c = 'X';
d = &c;
printf("address of a is: %p\n", &a);
printf("address of b is: %p\n", &b);
printf("address of c is: %p\n", &c);
printf("address of d is: %p\n", &d);
printf("-----------------------------\n");
printf("a contains: %d\n", a);
printf("b contains: %p\n", b);
printf("c contains: '%c' (%hhd)\n", c, c);
printf("d contains: %p\n", d);
printf("-----------------------------\n");
printf("b dereferenced is: %d\n", *b);
printf("d defeferenced is: '%c' (%hhd)\n", *d, *d);
printf("-----------------------------\n");
printf("a is %d bytes\n", sizeof(a));
printf("b is %d bytes\n", sizeof(b));
printf("c is %d bytes\n", sizeof(c));
printf("d is %d bytes\n", sizeof(d));
printf("-----------------------------\n");
*b = 32;
*d = 'J' - 6;
* The dereferenced values of the pointers b and d
*The address of b was assigned to 32.
*The address of d was assigned to the character J minus 6
printf("a contains: %d\n", a);
printf("b contains: %p\n", b);
printf("c contains: '%c' (%hhd)\n", c, c);
printf("d contains: %p\n", d);
printf("-----------------------------\n");
printf("b dereferenced is: %d\n", *b);
printf("d defeferenced is: '%c' (%hhd)\n", *d, *d);
printf("-----------------------------\n");
return(0);
}
====September 9th and 11th, 2014====
During class this week we reviewed Structs. **Structs** are considered a scalable variables (heterogeneous) vs an Array which is a composite variable (homogeneous). Structs are like containers that we can use to put things of the same class in, including other structs.
*When we used arrays we used the following code:
int b[4];
*With structs we write the same code as follows:
b=(int*)malloc(sizeof(int)*1);
*These are the same thing and the compiler understands both.
*b is a pointer to the memory malloc. Malloc is a memory allocator that sets aside 4 bytes per integer.
The following code is an example of arrays and structs being used to do the same thing:
b[0]=2; *(b + 0)=2;
b[1]=7; *(b + 1)=7;
b[2]=32; *(b + 2)=32;
b is derefrenced and offset by 0, 1, and 2.
Some facts about structs:
*make new struct definitions global by placing them outside of main
*save struct as struct.h which is a global struct
*they are like nodes
*they make a template for **Linked Lists**- a data structure
*each struct contains a variable
*each has the ability to point to other nodes that contain other values that point to others or to NULL
*structs are computation effective
*they have unending dynamic flexibility while Arrays perform better. However; arrays need to declare memory ahead of time.
====The following is code that we worked on in class:====
**nano struct1.c**
#include,stdio.h>
int main()
{
struct thing{
struct thing is used to declare an array
int a;
char b;
};
we use a **;** after the **}** after the declaration of a struct. **};**
int a; and char b; are variables of the array struct thing.
struct thing stuff;
*creation of a new data type
stuff.c=57;
stuff.b=66;
*not a stand alone variable until we declare the instance of it and then add variables
printf("stuffs a member is: %d\n, stuff.a);
printf("stuffs b member is: '%c'(%hhd)\n", stuff.b, stuff.b);
}
*There were no pointers used.
*Stuff.a allows better organization.
*Variables have common names and are grouped together.
==This will return : 'b' (66)==
**nano struct2.c**
#include
#include
struct node{
*node type- struct
char value;
struct node *next;
};
*struct node data type next is a pointer pointing to another node or NULL
type struct node Node
*merge or shorten struct node stuff by using type code definition
*type code definition is used to create a word and substitute it for something else.
int main()
{
char input;
Node *tmp=Null,*tmp2=NULL;
tmp=(Node*)malloc(sizeof(Node)*1);
*first char was declared as a variable
*declared node points to tmp
*Node is a type cast and Null is a pointer value equivalent to nothing. When not ready to point to anything then point it to NULL.
*malloc requests how many bytes that are needed, gives raw memory and forces it into the node
*tmp is assigning tmp and converting to node while star points to the node and applies the property of the Node.
*tmp2 was added to create a second node and it is assigned NULL
tmp-> value = 12;
tmp-> next = NULL;
*tmp-value is a structure pointer that gives values and points to NULL
tmp->next=(Node*)malloc(sizeof(Node)*1);
*malloc sets aside memory needed for the next node
tmp->next->value=3;
tmp->next->next=NULL;
*assigned value and initialized node
tmp->next->next=(Node*)malloc(sizeof(Node) *1);
tmp->next->next->value=15;
tmp->next->next-next=NULL;
**This code wasn't finished yet**
We ended with adding a second Node (tmp2) when Node and tmp were first used.
===Actions or Concepts of Significance===
Structs are a scalable variable (1 thing) and a composite variable (same elements put together linearly). With the use of structs we are making custom made "containers" aka **Data Types**. This is the same as a Class. We learned how to declare new data types and add values. This allows for better organization. We learned that we make structs Global outside of the main so they can be used throughout the code. A struct is like a Node. Linked lists allow nodes to point to other nodes that contain other values that point to other nodes or NULL. We used Type Code to merge or shorten the type definition (must be a non-reserved word) to make writing code faster. Structs have both pros and cons, but most importantly, when using structs we don't need to declare memory ahead of time.
===Questions and Challenges:===
For me, I'm still learning how to navigate lab46 and the Unix environment. I'm also still learning the commands for committing and pushing code. I don't understand how we are using version control with Lab46 and will need to ask about it and get some hands-on learning with it. I am eager to see what we are doing with struct2.c and how I can apply it in the future.
====September 16th and 18th, 2014====
We learned about the built in automation of using the makefile. At the end, by typing make, this will invokes files in the makefile. This is a script will run, save, and submit our files for us. In the source directory we use "grabit" to get files.
Our Node0 project should have the following sub-directories
inc/
lib/
src/
node/
list/
stack/
queue/
tree/
hash
testing/
node/
app/ write testing applications
unit/ test every library function and make sure it works
list/
app/
unit/
stack/
app/
unit/
*this node directory/ sub-directories contain /bin, /lib, and inc/
There are multiple roles for **Software Developing**
* **Library Developer** programmer creates functions
* **Application Developer** uses functions and support files made by the Library Developer
* **End User** has an experience where they can run programs and find them valuable
*The purpose of using the multi-programming development roles is for us to get used to their functionality of this organization for future protocols as a programmer.
===Node0 Project===
The task for the Node0 Project is to produce an output of the values in each node and include NULL.
7->5->4->73->12->NULL
*These should literally be displayed
*Once the program works and can get it to display the proper text then we can make submit and drive the project
We also learned how to apply updates in the src
cd src/data/node0
ls
fixit
**Types of Lists**
*1. lists
*2. linked lists- putting nodes together to make a linked list
*3. singularly linked lists-node is used as a template. Simply just tmp pointing to a node.
*4. doubly linked list- nodes point to and from one another
*5. ring- nodes form a ring and continue to run deploying multiple values until it runs out
**Three Main Functions of a Linked List**
*1. Insert- insert new node that will point to another node and adjusts the order of the list
*2. Append- insert another node to make another list
*3. Obtain- remove/ disconnect a specified node from the list
The linked list library will include the following functions
include()
mklist()
insert()
append()
obtain()
rmlist()
getpos()
setpos()
displayf()
displayb()
sortlist()
cplist()
When making a node there are 3 steps:
*malloc node
*initialize value
*initialize next (NULL)
When making a list there are 3 steps:
*malloc list
*initialize quantity
*initialize start/ end= NULL
===Action or concept of significance:===
The makefile was a significant concept that was discussed. When used it can save, run and submit code all in one step. I also think that understanding the different roles of software development is important. I didn't know each of these and now I can use this as a guide to areas that I would like to learn more about or focus my education on.
===Questions and Challenges:===
I don't quite understand the use of the directories and sub-directories with the node project. I understand the concept but I'm not clear on how to apply them to the node0 project. I would like to have a better understanding of the library functions we will be using later in our node1 project.
====September 23rd and 25th, 2014====
In class we learned how to update our Node0 file to node1
make update
make help
make upgrade node1
cd ../node1
There are now new files in the following:
*./src/node/
*./testing/node/app/
*./testing/node/unit
==Prototypes - declare the existence of the function in node0==
==The node library functions are in the src==
**cpnode** calls the mknode and passes tmp value
**cpnode**
node *tmp3, *tmp4;
tmp3 = mknode (8);
tmp4 = cpnode (tmp3);
tmp3-> (8) -> null <- (8) <- tmp4
tmp3=rmnode(tmp3);
null <- (8) <- tmp4
tmp3 checks to see if node is null
==malloc allocates==
==free deallocates==
==Code in class for Debugging==
#include
#include
struct node{
char value;
struct node *next;
};
typedef struct node Node;
int main(void)
}
Node *tmp, *tmp2, *start, *end;
tmp = tmp2 = start = end = NULL;
char input;
int i;
while (input != -1)
{
printf("Enter a value(-1 to finalize): ");
scanf ("%hhd",&input);
if(start == NULL)
{
start = end = (Node*)malloc(sizeof(Node));
start->value = input;
start->next = NULL;
}
else
{
end->next = (Node*)malloc(sizeof(Node));
end = end->next;
end->value = input;
end->next = NULL;
}
}
printf("Enter value of new node: ");
scanf ("%hhd",&input);
tmp = (Node*)malloc(sizeof(Node));
tmp->value = input;
tmp->next = NULL;
printf("Enter node value to insert before: ");
scanf ("%hhd",&input);
tmp2 = start;
while(tmp2->next->value != input)
{
tmp2 = tmp2->next;
}
tmp->next = tmp2->next;
tmp2->next = tmp;
//display the list
return(0);
}
====September 30 and October 2, 2014====
==We updated node1 to sll0==
*new include
*new source list
==Code for .h==
**header file** is found in src/inc/ list.h
struct list{
Node *start;
defined starting and **first item**
Node *end;
ending list **last item**
int qty;
}
maintaining running **quantity** of nodes in list
==use while loop for the following:==
*displayf()-display list from beginning to end, takes two arguments-
*insert()
*append()
*cplist()
==node0 used displayf()==
2 -> 7 -> 36 -> 2 -> 6 -> NULL
==node1==
[0]3 -> [1]7 -> [2]36 -> [3]2 -> [4]6 -> NULL
*[] hold position value
==sll0==
Implement:
*insert()- doesn't ask for info, don't need to print, does operation and finishes
*append()- doesn't ask for info, don't need to print, does operation and finishes
*getpos()
*setpos()
*mk and cpy- already created
**AVOID** using any input and output except display when needed
==debugger==
**Step 1:** compile with bug support
gcc -g -0 sll-debug sll-debug.c
**Step 2:** launch debugger (gdb)
gdb ./sll-debug
**Step 3:** Segfault??? Find out where.
run
**Step 4:** Set breakpoints and analyze
break 55
run
**Step 5:** Check variable status
print tmp2 -> next -> value
print tmp -> value
print tmp2
print tmp1
print tmp -> next
**Step 6:** Set up auto display of variable
display tmp2 -> next -> value
display tmp -> value
display tmp2 -> next
display tmp2
display tmp
**Step 7:** Watch it loop
S will follow into function and get message (step by step)
N wont go through the function (next it)
====October 7th and 9th, 2014====
==sllo- 3 new updates==
==unit tests:==
These programs use functions we wrote to determine if program works. Future Assignments will contain functions/assignments that contain aspects of the same code as
*insert()
*append()
*display()
*obtain()
==debugger==
We will increasingly need to use the debugger to assist in finding errors and segfaults
==sll1 functions==
searchlist()
swapnode()
obtain()
==swapnode==
start -> 13 -> 57 -> 21 -> 33 -> 29 -> 12 -> NULL
tmp -> 57 tmp2 -> 33
start -> 13 -> 33 -> 21 -> 57 -> 29 -> 12 -> NULL
==obtain()==
*act of obtaining (removing) a node with the expectation of getting list back and unique node back
*remove node 57 from list
*list operates on and points to tmp remove
==Function prototype of obtain()==
List* obtain(List*, Node**);
myList = obtain(mylist, & tmp);
(*tmp) -> value
int input;
scanf ("%d, & input);
in scanf(const char*, int*);
myList = insert(myList, tmp1, tmp2);
==Form function with following code==
int pos = getpos(myList, *tmp);
node *tmp2;
tmp2 - setpos(myList, pos -1);
tmp2 -> next = tmp -> next;
(*tmp) -> next = NULL;
myList -> qty ;
return (myList);
==A memory address is just another form of data==
==pointer allow flexibility==
====November 11th and 14, 2014====
====dlq0====
===stack===
*Stacks are data structures which apply rules, and organize data. They only have one pointer, which is top. An example of a stack is the card game FreeCell.
{{:notes:stack11-11-14.png}}
===queue===
*Queues are also another form of a data structure. It has two pointers(front and pack). These are used to add to the queue or enter the queue from the back.
==enqueue==
*used when you add nodes to the queue. When doing this it is done from the back of the queue.
==dequeue==
*used to remove nodes from the queue. This is done from the start of the queue.
===Examples of queues===
{{:notes:queue.png}}
==bounded queues==
*there are a fixed amount of positions
*set maximum queue size
***buffer** is storage that is used when the queue every request at one time. Example: music library and a printer
==unbounded queues==
* there is an unlimited amount of positions
==FIFO==
* First in- first out **enqueue**
==LILO==
* Last in - last out **dequeue**
===Enqueue and Dequeue use list functions===
==Conditions==
* When have a bounded queue, with a fixed size (maximum queue size) and try to add more than the maximum allows it is called a **buffer overrun**
* When have an empty queue and try to dequeue(take a node out of the queue) it is called a **buffer under-run**
==Queues are like stacks==
* make use of lists
* can be used to solve problems
* make use of them everyday whether intentional or unintentional
* causes order
==Queues are unlike stacks==
* can orient from front to back
==Potential benefits of queues==
* provides other solutions in many situations
**Can have a stack of queues**
===Functions===
* **enqueue()**add to the queue
* **dequeue()**remove from the queue
* **purge()**way to quickly remove nodes from the queue
* **rmqueue()**quickly remove from queue without worrying about de-allocating and nullifying the queue pointer
===Object Oriented Programming C++===
Is code management.
* **polymorphism**
* **Inheritance** reuse or make use of code
* **Encapsulation** putting something in list/containers
==A function is the simplest form of inheritence.==
Example of Inheritence:
===EOCO Project===
input the following to upgrade at lab46 prompt
grabit
cd src/data/eoce0
cd/src
cd data
cd inc
nano Node.h
==virtual lines are example of polymorphism==
a **virtual function** can be rewritten or override a function. A child can rewrite back end functionality
==examples of inheritance==
* **node.h** is the base
* **singly linked node** is a child
* **doubly linked node** is a child (or grandchild)
====October 23rd & 28th, 2014====
We were given the following code and asked to draw a diagram of it starting with this image:
{{:opus:fall2014:lbelloma:practice_assessment_image.png?200|}}
List *myList, *myList2
int i = 7;
Node * tmp, *tmp2;
for (i =0, i <7, i++)
{
tmp = mknode (i*1);
if((1 %3) == 0)
myList = append(myList -> start, tmp);
else if((1 %3)==1)
myList = insert(myList, myList -> end, tmp);
else
myList = swap(myList, myList -> end, myList -> start);
}
{{:opus:fall2014:lbelloma:practice_assessment_final_image.png?200|}}
====November 4th & 6th,2014====
===dlso===
**stack*
*a set of storage locations that store data in such a wat that the most recently stored item is retrieved first.
====11/18/14 and 11/20/14====
===dlt0===
==trees==
***grabnode** is deleting a node from a tree. When using we are manipulating an existing tree in a non-destructive way
*only applying this to **Binary Search Tree**
*when inserting we use < = node goes to left and >= node foes to the right
*binary search automatically puts the node values in order in the tree
***traversal** gives returns nodes backwards where it finds the lowest value in order
***addnode**is only used one time in grabnode
==Three ways of implementing grabnode==
*recursively
*iterally
*stack based
==other==
We have been given *other to help us connect to where we came from when using addnode
{{:notes:other.png}}
==removing from tree==
*cant use immediate decedents
*must choose 1 of two way and stay with that approach
* - greatest to least value in the sub-tree
* - lowest value in the left sub-tree
* can only have one child when removing a node from the tree
===Example in class===
==Original tree==
{{:notes:original_tree_w_lines.png?400|}}
==grab the node with value 3 in it==
{{:notes:grabnode.png?400|}}
t ->next -> other = t -> other;
t -> other -> prev = t -> next;
t -> next = NULL;
t -> other = NULL;
==the node with the value of 4 is now isolated==
*must make sure node value 4 points to same three destinations as node with value of 3
t -> prev = s -> prev;
t -> next = s-> next;
t -> other -> prev = NULL;
t- > prev -> other = t;
t -> next -> other = t;
t -> prev -> other = t;
t -> next -> other = t
return(s);
==Node with the value of 4 is now in the spot where the node of value 3 was==
{{:notes:final_tree.png?400|}}
===Stack Based Approach===
*get to the left most node in the sub-tree
stack *myStack = mkstack(0);
tmp = mk(node(-1));
tmp -> other = s;
push(&myStack, &tmp);
{{:notes:stack_based_approach1.png?400|}}
s = s -> prev;
*next and prev used for stack connection
*prev and other in tree are preserved
*use push and pop in list
{{:notes:stack_based_approach2.png?400|}}
====12/2/14====
===EOCE===
*this project is open resourced but we may niot communicate with other people
*we are encouraged to ask questions
*Due Thursday the 18th at 5:29:59
===eoce0===
We will use the following classes
*Node
*SinglyLinkedNode
*List
*DoublyLinkedNode
*ListOfSinglyLinkedNodes
*ListOfDoublyLinkedNodes
===0x0===
Discuss the universal implications of data structures
===0x1===
*the reimplementation of eoce0 but in C++
*very similar to eoce0 with the exception that it is Object-Oriented
===0x2 Linked Lists===
==eoce1==
*will be linking separate lists of linked nodes together
Will use the following classes:
*SinglyLinkedListsOfSinglyLinkedNodes
*SinglyLinkedListsOfDoublyLinkedNodes
*DoublyLinkedListOfSinglyLinkedNodes
*DoublyLinkedListOfDoublyLinkedNodes
We can use templates to reorganize inheritance model
===0x3 Meaning===
Of all the concepts explores and work done over the semester, identify something meaningful to you.
What is it?
Why does it stick out in your mind? Explain.
===0x4 Reflection===
How did you feel about this course?
Was it useful/interesting to you?
What was your least favorite aspect, and why?
Any comments and suggestions?
===0x5 Personal Assessment===
What grade do you think you deserve in the course and why?
Justify your answer based on your own perceived performance.