Data Structures Journal

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.

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.

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.

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.

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.

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.

        #include <stdio.h>
        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);
             }

             #include <stdio.h>
             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);
              }

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.

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.

nano struct2.c

#include<stdio.h>
#include<stdlib.h>
 
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.

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.

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.

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.

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

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.

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.

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

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

#include <stdio.h>
#include <stdlib.h>
 
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);
}

• new include
• new source list

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

• displayf()-display list from beginning to end, takes two arguments-
• insert()
• append()
• cplist()

2 → 7 → 36 → 2 → 6 → NULL

[0]3 → [1]7 → [2]36 → [3]2 → [4]6 → NULL

• [] hold position value

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

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)

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()

We will increasingly need to use the debugger to assist in finding errors and segfaults

searchlist() swapnode() obtain()

start -> 13 -> 57 -> 21 -> 33 -> 29 -> 12 -> NULL
tmp -> 57  tmp2 -> 33
 
start -> 13 -> 33 -> 21 -> 57 -> 29 -> 12 -> NULL

• 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

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);

int pos = getpos(myList, *tmp);
node *tmp2;
 
tmp2 - setpos(myList, pos -1);
tmp2 -> next = tmp -> next;
(*tmp) -> next = NULL;
myList -> qty  ;
return (myList);

• 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.

• 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.

• used when you add nodes to the queue. When doing this it is done from the back of the queue.

• used to remove nodes from the queue. This is done from the start of the queue.

• 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

• there is an unlimited amount of positions

• First in- first out enqueue

• Last in - last out dequeue

• 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

• make use of lists
• can be used to solve problems
• make use of them everyday whether intentional or unintentional
• causes order

• can orient from front to back

• provides other solutions in many situations

Can have a stack of queues

• 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

Is code management.

• polymorphism
• Inheritance reuse or make use of code
• Encapsulation putting something in list/containers

Example of Inheritence:

input the following to upgrade at lab46 prompt

grabit
cd src/data/eoce0
cd/src
cd data
cd inc
nano Node.h

a virtual function can be rewritten or override a function. A child can rewrite back end functionality

• node.h is the base
• singly linked node is a child
• doubly linked node is a child (or grandchild)

We were given the following code and asked to draw a diagram of it starting with this image:

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);
}

• *stack*
• a set of storage locations that store data in such a wat that the most recently stored item is retrieved first.

• 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
• addnodeis only used one time in grabnode

• recursively
• iterally
• stack based

We have been given *other to help us connect to where we came from when using addnode

• 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

t ->next -> other = t -> other;
t -> other -> prev = t -> next;
t -> next = NULL;
t -> other = NULL;

• 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);

• get to the left most node in the sub-tree

stack *myStack = mkstack(0);
tmp = mk(node(-1));
tmp -> other = s;
push(&myStack, &tmp);

s = s -> prev;

• next and prev used for stack connection
• prev and other in tree are preserved
• use push and pop in list

• 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

We will use the following classes

• Node
• SinglyLinkedNode
• List
• DoublyLinkedNode
• ListOfSinglyLinkedNodes
• ListOfDoublyLinkedNodes

Discuss the universal implications of data structures

• the reimplementation of eoce0 but in C++
• very similar to eoce0 with the exception that it is Object-Oriented

• 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

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.

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?

What grade do you think you deserve in the course and why? Justify your answer based on your own perceived performance.