It is our first week. We learnt how to log into lab46, and familiarize ourselves with the features of lab46. We also learnt how to open up a terminal and log into the terminal. We also learnt how to set up our mercurial repository in the terminal. We learnt how to create an empty directory to store everything we do, how to create files within this directory, how to add and submit our files into the repository, how to pull files from the repository and so on. Basically this week we learnt how to navigate through the terminal and lab46 wiki page. All in all it was a good week. It will take some time for me to fully familiarize myself with everything as I don't have the advantage my colleagues have of having done the lab portion of C++ last semester. I will, however catch up in due time.

It has been a good couple of weeks. However, I still feel as though I am walking in the dark, like a baby taking its first steps. Unlike many of my class mates who had the pleasure and the advantage of taking the lab portion of C++ last semester, I was not so lucky. therefore, I have the disadvantage of not being as comfortable with navigating through the terminal as my colleagues do. However, I am not discouraged. I am here to learn and I am, as always determined to do just that.

I spent the last two weeks learning to navigate through the terminal. I learned how to create a directory. Now I need to master how to

  create files
  Save them in the directory
  Access them when I need them
  Push them to my repository and so on.
 

We also have been talking about variables and pointers and the importance of using pointers, and we will continue to work more with pointers.

We also touched a little bit on how to compile and run a program.

I am still fumbling around in the terminal. Not as lost as last week but still a little uncertain.

This week we talked about composite variables. We talked about homogeneous composite data types and heterogeneous composite data types.

What is a composite data type: Composite datatypes are the datatypes which can be constructed with in a program by using primitive datatypes and other composite types.the act of constructing a composite data type is called composition

What is a structure or struct? A container with data inside it. This is also classified as a class.

Wrote a small program containing a struct.

#include<stdio.h>

int main( ) {

 struct thing{
   int a;
   char b;

};

   stuct thing stuff;
   stuff.a = 57;
   stuff.b = 66;
   

Program continues…..

We talked about nodes and how to manipulate them.

What is a list? A list is a data structure that lets us have a list that would let us allocate data as we go.

A few points that we talked about in class this week.

- INC = {I} - can be given to the compiler to look for header files. - CCFLAGS = -wall (No errors when compiling) - Using 'makefile', we can just submit projects and assignments - LIBS = src source to library functions - LIBS = testing

src - this is where you will have the library to functions

- All the functions that we write is stored in the library - Application developer uses the functions in the library - BIN - Is reserved for rules - The debugger will be used a lot and there are rules set-up for it.

- testing:libs - When you are testing you have to have the library built up. - 'make' will be used a lot

 make debug
 make libs
 make testing
 

- make clean: make will erase all compiled stuff. Make clean should be followed by make - make save: This is like making a snapshot - make submit: before you submit, it will require you to save it first, and you will have to make clean to

save it. This will submit the project.

Discussion about Linked List

mklist( )
insert( )
append( )
displayf( )
displayb( )
cplist( )
rmlist( )
search( )
getpos( )
setpos( )
sortlist( )
swap( )

- Make a node

malloc node
initialize value( )
initialize next(NULL)

- Make a list

malloc list
initialize qty
initialize start, end

This week we started off talking about our second project which is Node_01. We discussed about

      mknode - allocates new node containing value
      mknode - It makes a duplicate node, just by calling cpnode, it makes a duplicate. 
      rmnode - Frees the node/ de-allocates it. All contents of the node gets reset and it gets de-allocate
               it.

Link List

Link list insertions

insert/append - to put something in a list Insert - Inserting has to be done before Append - Appending is done after.

A small example of an insertion

tmp2→next = temp;

            tmp = start;

while(tmp2→next != tmp2→next);

            tmp = tmp->next;
      tmp->next = tmp2; 

We started this week discussing about the next project sll0 Since we have been working on insert, we are now going to be learning how to append. That is what we will be working on in sll0

Some other points that we talked about in class were:

-Everything in the list relies upon node.

       Struct list{
          Node *srart;
          Node*end;
          int qty;

-We can rely on start to point at the beginning of the list -It is a node pointer that points to the start of the list -end is a pointer that points to the end of the list -qty : How many nodes get added to the list

-displayf : It specifically displays the list from start to end

-Welearnt of two modes.

-Mode0

 3 -> 7 -> 36 -> 2 -> 6 -> NULL
 

This is the format of mode0

-Mode1

 [0]3 -> [1]7 -> [2]36 -> [3]2 -> [4]6 -> NULL
  ^ 
  |
 This is the position

You pass it two values. The value you want to print and the position.

The Debugger

In order to use the debugger you have to:

Step 1- Compile with debug support

gcc -g -o sll-debug sll-debug.c

Step 2- Launch the debugger

gdb./sll-debug

Step 3 - segfaulting? Find out where?

(gdb) run (It will display the line where the segfault occurred.

step 4 - Set breakpoints where segfault occurred.

(gdb) - break 55 (The program will run until the break point)

Some things we talked about in class this week.

Use unit tests : These programs use functions to determine if the programs we wrote work

Debugger : will be used increasingly to find errors and segfaults in the programs we write

sll1 functions

search list swap node obtain ( ) - remove node from list

Link list

mylist start –> 13 –> 37 –> 26 –> 52 –> NULL end [0]13 [1]37 [2]26 [3]52 qty

tmp2 = tmp = setpos(myList, 2); myList = obtain(muList, &tmp); myList = insert(myList, myList → start, tmp); tmp = mknode(7); tmp2 = tmp; tmp = setpos(myList,3); myList = append(myList,tmp,tmp2);

This week we talked about doubly linked lists and our next project sll2.

What is a doubly linked list? It is a list of nodes where each node references to the next and the previous node. Each node has pointers to next and previous nodes.

A doubly linked list must not be used unless it is necessary, because one must use the right tool for the right job.

A small sample code for a doubly linked list:

myList → end → next = newNode; myLisy → end → next → prev = myList → end; myList → end = myList → end → next

Another Code for a doubly linked list

List *myList, *myList2; int i = 7; Node *tmp, *tmp2; myList = mklist();

{
   for = mknode (i * 1);
   if ((i%3) == 0)
       myList = append(myList, myList -> srat, tmp);
   else if ((i%3) == 1)
       myList = insert(myList -> end, tmp);
   else
       myList = swap(myList, myList -> end, myList -> start);
}

This week was spend discussing about the doubly linked list project. Some changes were made to the dll0 project.

-qty from sll has been removed -value is now data -In sll we only had to deal with next, in dll we now have next and prev. Pointing to the next and previous nodes in the list

We also had a test. A knowledge assessment test, which went very well.

This week, we discussed about dls0. In this project we will be dealing with stacks. Stacks are also similar to linked lists with a few exceptions. With stacks, the only node one can remove is the last node placed, and that is also the only one that can be removed.

We learnt a few terms regarding stack

Push: The act of placing something on a stack is called pushing.

Pop: The act of removing the last node you placed on the stack is called 'pop'.

Peak: It lets you take a look at the last element on the stack without popping it. It remains on the stack.

*Always, the last thing you put on a stack is the first you pop. If you need to access the one before the last, then you have to pop the last one first.

Unbounded stack: Is when you keep pushing forever, without any bounds. The stack can keep growing.

Bounded stack: You have to specify how many elements you want in the stack, and that will be the maximum it can hold. If you try to add more, it will give you an error.

Stack overflow: If the stack is a bounded stack and you try to push over the capacity, this will cause an error and that is called a “stack overflow”

Stack underflow: If you try to pop from an empty stack, this is called an underflow.

-When push & pop is executed, it has to send back a message to let you know if the push or the pop was successful.

This week we talked about our next project, which is “Queues.”

-“Queue” is like a line. You enter the line from the back. So you add yourself to the queue from the back. New elements keep adding to the back.

-“Dequeue” from the queue. So the dequeue happens from the front, just like at a stop sign. The person at the front of the line drives off first.

-“Unbounded” (unlimited): A queue that has no restrictions.

-“Bounded” is when you set a maximum size to a queue, then that will be the maximum size.

-“Buffer” is a storage.Queuing up something that you want to watch or listen to. Storing values that you want to use. Temporary memory storage to be used later.

In queue: FIFO - First in last out LILO - Last in last out

“enqueue” from the back “dequeue” from the front

This week we talked about a new data structure, “Trees.”

The Tree data structure is similar to a tree except the “root” of the data structure “tree” is at the very top. The very first node, the starting point of the tree.

A tree contains nodes that connects to other nodes. It is a non linear data structure (more like branching).

Nodes will be placed in the tree according to the value stored in them. The lesser values goes to the left, and the greater values go to the right.

-The “root” is where we start our tree. -The root will contain a next and a prev pointer.

A tree can have many levels or tiers, but the most basic is the binary tree.

What is a binary tree? -It is a data structure in which a record is linked to two successive records, usually referred to as the left branch and right branch.

Much like stacks and queues, trees too have bounded and unbounded trees

A bounded tree is when the maximum height of the tree is specified An unbounded tree is when the height is unspecified, therefore, it is unlimited.

Walking tree or traversal tree: Means, stepping through the items of a tree, by means of connections through parents and children.

-Ways to traverse a tree

in-order method: 
First, a node's left sub-tree, then the node itself, and finally its right sub-tree are traversed.

pre-order method: 
Each parent node is traversed before the child is called.

post-order method: 
Children nodes are traversed before their respective parent nodes are traversed.

This is week concludes all the lectures for this course. From this point util final week the class will be working on the last “data structure” we learnt about, which is “trees” Also we will be working on our grand finale.. which is the end of class experience, also known as “eoce”

We will be writing this program in an object oriented approach. For this project we will be concentrating on nodes and lists.

Singly linked nodes

Doubly linked nodes

List of singly linked nodes

List of doubly linked nodes

Singly linked list of singly linked nodes

Doubly linked list of doubly linked nodes