Tuesday, November 24, 2015

c++ makefile

C++ Makefile

C++ is object orient programming.
Each object file can be created by its own .cpp and .h file.

For instance, If you have the following files

main.cpp   -----------------> main.cpp uses a object, called person
person.cpp -----------------> person object source file
person.h. -------------------> person object header file

You need to compile these three files at once.

If you would like to compile using a terminal(linux, mac os), you can type it like following
         g++ main.cpp person.cpp

It is pretty simple. right?

But how about this??
You have 100 object files that are need to be comfile.

it would be  like
       g++ main.cpp a.cpp b.cpp c.cpp d.cpp ...................
It would be really painful.. YOU need to type it every file for every compiling.

Fortunately, there is a better option, you can use Makefile

Makefile tells make, a UNIX command, to communicate with c++ compiler to link and compile a program.
If you do not know UNIX, it is ok. Think it as the father of all operacting system(window, linux, mac os and many more....). To be honest, I do not know it well either hahahaha

If you use Makefile, you need to type the compiling command just onece.
After you create Makefile, you just need to type "make" in the terminal.

Format

target : dependency
    system command

Actually, it is really simple. If you remember these two lines, you can make Makefile pretty much.
One thing you need to remember is that this file is space sensitive. make sure you tab for the second line

Example

output: main.o Person.o                         3)
    g++ main.o Person.o -o output
main.o: main.cpp                                   1)
    g++ -c main.cpp
Person.o: Person.cpp Person.h              2)
    g++ -c Person.cpp
clean:                                                      4)
    rm *.o output


1) "g++ -c main.cpp" creates "main.o"

2) "g++ -c Person.cpp" create "Person.o". Person is an object, so you need to add .h and .cpp for depedency

3) after 1) and 2) are done, Makefile will work on making output. "-o output" makes the excutable's name "output"

4) it is optional feature. It is deletion of excutable  and other .o file. After you compile, and want to delete all .o files and output. You can type "make clean". It will do the job for you.

 *excutable = file that runs progream (it is like ".exe" for window and ".jar" for java)

---------------------------------------------------------------------------------------------------------------------------
 The following is practice code. If you have suggestion or correction, please feel free to leave comment.

To compile

make

To delete .o files and output(excutable)

make clean
 

There are four files


1) MakeFile

output: main.o Person.o
    g++ main.o Person.o -o output
main.o: main.cpp
    g++ -c main.cpp
Person.o: Person.cpp Person.h
    g++ -c Person.cpp
clean:
    rm *.o output

2) main.cpp

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>


#include "Person.h"

using namespace std;

int main( int argc, char *argv[])
{
    Person a("Tom", "Jang");

    a.printInfo();


}

3) Person.h

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>

using namespace std;

class Person
{
    private:
        string firstName;
        string lastName;
    public:
    Person();
    Person( string fName, string lName );
    void printInfo();

};

4) Person.cpp

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>

#include "Person.h"

using namespace std;

Person :: Person()
{
    firstName = "empty";
    lastName = "empty2";
}

Person :: Person ( string fName, string lName )
{
    firstName = fName;
    lastName = lName;
}

void Person :: printInfo()
{
    cout << "firstName is " << firstName << endl;
    cout << "lastName is " << lastName << endl;
}




   

 

Saturday, November 21, 2015

c++ hashtable with linked list

C++ hashTable with linked list


Hash table is a data structure that allows use to search, edit, delete data nearlyO(1).
If you do not know what the O(1), it is ok.. keep it in you mind that it is super efficient.

Lets dive in with real example!!

let's say that you have list (you can think it as array).
Every element of this list contain name of person.
If you want to search Jane from the start of the list, you have to check every element.
Above example, we just need to check 100000 names.
Technically, it is quite fast if you are searching for 100000 names.
However, if the each elements contain lots of inforamtion, and the number of element is goes up to extrememly large numer, it is a different story. It wil take mintue, hour or more than that.

Let's look at the following.




This time, before we put names in the list, we use a function called hash function.
What the function does is that it takes name as input and return integer number.
This number is going to be the index of name in the list.

If we use this way, search can be done extremely fast!!

How?
If you want to know whether "john" is in the list, you can use hash function to the name. You will get the index, and you will get the result instantly, without looking at other names in the list.

It does not matter how many elements are in the list, you will get what you want from the list instantly

However, this hashfunction has problem...


The above example show that two different name ends with same index number.
If your list can handle onely one name, you are in trouble...
This is called hash collision.

There are severy way to avoid this.

My way is using linked list

There are different implimenation in using hash function with linked list.
My way is following...
    1) The very first element of list is empty
    2) get the hash val
    3) use hash val as index of list
    4) make linked list.

This way, it is not O(1)... but it is still close to O(1).


In the real world, there is no way that we can build hash function without hash collision.
It is like you are predict lottery number correctly every week..

Depend on number of data, field, culture and many other aspects, we  design the hash function differently; there is no right answer.

Lots of smart computer people, professors write research papers to find the best way of builiding hash function.


I made some sample coding for this topic.
---------------------------------------------------------------------------------------------------------------------------


The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>

using namespace std;

typedef struct student
{
    int id;
    string fName;
    string lName;
    student * nextStudent;
}Student;

void initTable (Student *table, int len);
void addStudent(int studentId, string firstName, string lastName, Student *table);
int hashFunction(int id);
void searchAndPrint(int studentId, Student *table);
void deleteStudent(Student *table, int len);

int main()
{
    Student * table = new Student [10];
    int len = 10;

    initTable(table, len);


    // insert
    addStudent(12345, "tony", "stark", table);
    addStudent(55555, "bruce", "wayne", table);

    // search and print
    searchAndPrint(55555, table);
    searchAndPrint(34524, table);


    cout << endl;
    // all students info are stored in dynamic memory
    // therefore you have to visit every single student info for the deletion
    // for those student info by the linked listed are deleted by the deleteStudent function
    // the table array is delete by delete []
    // pointers for table and pointers for student info are different pointer type.
    deleteStudent(table, len);

    delete []  table;


}

void initTable (Student *table, int len)
{
    for (int i = 0; i < len; ++i)
    {
        table[i].nextStudent = NULL;
    }
}

void addStudent(int studentId, string firstName, string lastName, Student *table)
{
    // using hash function, convert the id into hashed id
    int hashedID = hashFunction( studentId );   

        Student * pointer = &table[hashedID];

        while(pointer->nextStudent !=NULL){
            pointer = pointer->nextStudent;
        }

        // once we reach to the student who has NULL in nextStudent
        // add student
        Student *tmp = new Student;
        tmp->id = studentId;
        tmp->fName = firstName;
        tmp->lName = lastName;
        tmp->nextStudent = NULL;

        // link
        pointer->nextStudent = tmp;

}

int hashFunction(int id)
{
    int tmp = id;
    int ans =0;

        // add each digit's number ex) 12345 -> 1+2+3+4+5 = 15
        while( tmp != 0 ){
            ans += (tmp % 10);
            tmp /=10;
        }
        // the loop does not handle the last one
        // one more addition is required
        ans += (tmp % 10);
       
        // make the addtion into range of 0 to 9
        ans %= 10;

        return ans;
}

void searchAndPrint(int studentId, Student *table)
{
    // get the hashed id
    int hashedId = hashFunction(studentId);

    Student * tmp = &table[hashedId];

    // search for student
    while ( tmp -> nextStudent !=NULL){
        if (studentId == tmp->id){
            cout << "* found * " << studentId <<endl;
            cout << tmp -> fName << endl;
            cout << tmp -> lName << endl;
            return;
        }
        else{
            tmp = tmp -> nextStudent;
        }
    }

    // check the last one in the hash
    if (tmp ->id == studentId){
            cout << "* found * " << studentId << endl;
            cout << tmp -> fName << endl;
            cout << tmp -> lName << endl;
            return;
    }

    // if you cannot find even at the end
    // there is no such student in the hash
    else{
        cout << "* id is not found * " << studentId <<endl;
        return;
    }

}

void deleteStudent(Student *table, int len)
{

    for (int i = 0; i < len; i++)
    {
        Student* tmp = &table[i];
       
        // delete student info except the last one
        while ( tmp -> nextStudent != NULL){
            Student* tmp2 = tmp->nextStudent;
            tmp->nextStudent = tmp2->nextStudent;
            delete tmp2;
        }
    }



    cout << "deletrion successful" << endl;
   
}










Thursday, November 12, 2015

c++ char pointer array

c++ char pointer array

In this post, I am going to talk about char pointer array.
Some people might say that they prefer use string instead of char pointer array.
I was like that.
If you string object
     You do not have to worry about the memory allocation and deletion.
     When you want to concatinate two strings, you just  need + operator.

If you are dealing with small amount of strings, go ahead of string.

But if you are dealing with large amout of string( I am talking about severy giga byte of string file), you btter use char pointer array.

It is faster.
It is based on my experience, believe me hahaha

 Whenever you are using char pointer array, you have to make sure that you allocate enough space for each pointer. Technically, you can use char array pointer with out memory allocation

function a()
{
char * arr[5];
arr[0] = "test";
arr[1] = "test2";
arr[2] = "test3";
arr[3] = "test4";
arr[4] = "test5";
 }
The above can be represent the following image
The problem is that once the array leave the function a, those value "test","test2".."test4" will be gone. In addtion, I cannot use string funtion such as strlen, substr etc....

In order to keep the values, you have to put those values in to special memory.
It is called heap .
If values are stored heap, they will stay until you delete.
If you do not use them, you have to delete.(If you don't, it is memory leak)

allocatiing memory
char * a [3];
    a[0] = new char[5];
    a[1] = new char[5];   --> each array can contain 5 character of array
    a[2] = new char[5];

delete
    delete [] a[0];
    delete [] a[1];     --------> make sure you add []
    delete [] a[2];

It would be like following
    * the first image is 1d char * array
    * the second image is 2d char * array






----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string.h>


using namespace std;

void oneDfunction(char* arr[], int len);
void printOneDfunction(char* arr[], int len);
void deleteArray(char* arr[], int len);

// it is quite similar to first dimentional array
// one thing that you have to keep in mind is that you can only ...
// leave blank the first component of array. you have to specify ....
// the length
void twoDfunction(char* arr[][3], int row, int col);
void printTwoDfunction(char* arr[][3], int row, int col);
void deleteTwoDArray(char* arr[][3], int row, int col);

int main()
{
    // one dimentional example

    cout << "one dimetional char pointer array" << endl;
    char * array[5];
    int length = 5;

    oneDfunction(array, length);
    printOneDfunction(array, length);
    deleteArray(array, length);

    cout << endl;

    // two dimentional example

    cout << "two dimentional char pointer array << endl" << endl;
    char * array2[3][3];
    int row = 3;
    int col = 3;

    twoDfunction(array2, row, col);
    printTwoDfunction(array2, row, col);
    deleteTwoDArray(array2, row, col);
}

void oneDfunction(char* arr[], int len)
{
    for (int i=0; i< len; i++){

        // you have to allocate memory for your pointer
        // otherwise your pointer do not point any
        arr[i] = new char[10];
        strcpy(arr[i], "input");

       
        char * tmpP = new char[1];
        *tmpP = (i+'0');

        strcat(arr[i],tmpP);

          delete (tmpP);
    }
}

void printOneDfunction(char* arr[], int len)
{
    for (int i = 0; i < len; ++i)
    {
        cout << arr[i] << endl;
    }
}

void deleteArray(char* arr[], int len)
{
    for (int i =0; i < len; i++){

        // you have to put [], otherwise, you are not deleting your array entirely
        delete [] arr[i];
    }
}


void twoDfunction(char* arr[][3], int row, int col)
{
    int num = 0;
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            arr[i][j] = new char [10];
            strcpy(arr[i][j], "input");
            char * tmpP = new char[1];
            *tmpP = (num+'0');
            num++;
            strcat(arr[i][j],tmpP);
              delete (tmpP);
        }
    }
}
void printTwoDfunction(char* arr[][3], int row, int col)
{
    for (int i = 0; i < row; ++i)
    {
        cout << "row " << i << endl;
        for (int j = 0; j < col; ++j)
        {
            cout << arr[i][j] << endl;
        }
        cout << endl;
    }
}
void deleteTwoDArray(char* arr[][3], int row, int col)
{
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            delete [] arr[i][j];
        }
    }
}









Wednesday, November 11, 2015

c++ passing array to functions

c++ passing array to functions

Whenever I work on c++ project, I alway get confused of passing an array to fuction.

I thought that it would be nice to have reference of passing array to function.

There are several ways to work on this issue.
I just have made only some of them, but they always do the job!!

One thing I and you have to keep in mind is that whenever you pass the array, it is call by referece.
Which means that if you change any element of array in the funtion, the changes are remained even the array is out of th funtion.

----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std

using namespace std;

// 1d array functions
void printArray( int arr[], int len);
void add1( int arr[], int len);
void printArray2( int *array, int len);

// 2d array function
// for the array parameter, you can leave blank for the first one
void print2Darray(int array[][3], int len);

// 3d array function
// do you see the pattern?? you can alway make the first one blank
void print3Darray(int array[][2][2], int len);

int main()
{
    int length = 5;

    // 1d array example
    // initialize array to 1
    int array [5] = {1,2,3,4,5};

    // this function's array parameter is array
    cout << "the parameter of array is array" << endl;
    printArray( array, length);

    // this function prove that any function send array as parameter, is call by reference
    // which means that if you change stuff in array in function, the changes are remaind even the array is out of that function
    // when you pass the array to the function, keep it in your mind.
    add1( array, length);

    // this function's array parameter is pointer
    cout << "the parameter of array is pointer; \n due to function add1 all elements are incremented by one" << endl;
    printArray( array, length);
    // this function's array parameter is array
    cout << "the parameter of array is array\n due to function add1 all elements are incremented by one" << endl;
    printArray( array, length);   


    // 2d array example
    int array2d [3][3] = {{1,2,3},{4,5,6},{7,8,9}};

    length=3;
    // this function's array parameter is array
    // i could not use pointer to pass the array
    // if you know how, please let me know
    cout << "2d example" << endl;
    print2Darray(array2d,length);

    // 3d array example
    int array3d [2][2][2]={};
    length =2;
    cout << "3d example" << endl;
    print3Darray(array3d,length);

}

void printArray ( int arr[], int len)
{
    for (int i=0; i<len; i++){
        cout << arr[i] << endl;
    }
}

void add1( int arr[], int len)
{
    for (int i=0; i<len; i++){
        arr[i] += 1;
    }
}

void printArray2 ( int *arr, int len)
{
    for (int i=0; i<len; i++){
        cout << arr[i] << endl;
    }
}

void print2Darray(int array[][3], int len)
{
    for(int i=0; i<len; i++){
        cout << "row "<< i << endl;
        for(int j=0; j<len; j++){
            cout << array[i][j] << " ";
        }
        cout << endl;
    }
}

void print3Darray(int array[][2][2], int len)
{
    for(int i=0; i<len; i++){
        cout << "x "<< i << endl;
        for(int j=0; j<len; j++){
            cout <<  "\ty " << j << endl;
            for(int k=0; k<len; k++){
                cout << "\t\tz " << k << endl;
             }
        }
        cout << endl;
    }
}

Friday, November 6, 2015

c++ call by reference vs call by value

c++ call by reference vs call by value

 lets say that you create a int variable call "a".
 you store a value 1.

In c++ syntax, it would be  " int a = 1 "
For sake of simplity, lets think that your code will stay in memory (RAM) when you run it (I think it is true ).
In one section of memory, your int a is like below

 Your int can be any where in the memory (not true... but let's make it simple. It is almost true), there is gotta be some way to keep tract where your a is in the memory. Otherwise, you do not grab the variable when you need it.
For this reason, when you create a variable, you are actually create two thing. One is what you assign to the variable. The other one is address which is create by the computer ( i think it is by compliler or operating system.. not sure hahahah).

That strange number, 0x7ff58d72bac is the address.

Using these two information, we can do call by reference and call by variable.

Call by value function uses the value of variable.
Call by reference function uses the address of variable.

How can I get the address of variable, there are couple ways...
One way is using operator &.

after declare and initialize the variable, put & ahead of variable name like below

int a =1;
cout << &a << endl;

In below coding I made simple programming that can show you call by value and call by reference.

----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>

using namespace std;

// call by value
int callByVal( int a )  ;

// call by reference
void callByRef( int & a );

int main()
{
     int a = 1;
     cout << "original a : "<< &a << endl;    
   
     // call by value
     // the function make a copy of a in main
     // the coped value is stored a in callByVal function
     // the function do the calculation
     // return the calculate value to a in main
     // a copy the value
     // a in main and a in callByVal are different
     // if you see the addresses of these two, you can see that they are different
     a = callByVal( a );

     // call by referenece
     // the function takes main a's address
     // by having the a's address, calByRef function knows where the a is in the memory
     // callByRef function uses the main's a to do calculation
     // a in main and a in callByRef are identical
     // if you see the address of these two, you can see that they are same
     callByRef( a );

     // a = 1 + 1 + 2
     cout << "1+1+2 = " << a << endl;
}

int callByVal( int a )
{
    cout << "address of a in call by value " << &a << endl;
    return a + 1;
}

void callByRef( int &a )
{
    cout << "address of a in call by reference" << &a << endl;
    a +=  2;
}




Thursday, November 5, 2015

c++ linked list

C++ Linked list

Linked list is a data structure.
It is pretty much like an array that change its sizes.
Each componet of linked list is called a node.
Nodes are linked pointers.

Building linked list is a really good pointer practice. You need to very familiar with pointers to bulid it.

Whenever you are stuck with it, draw it like following.
I think it is the best way to solve any problem with linked list.


          head node                                                                                                                   last node

Every node has next pointer which points to the next node.
The last node's next is null; null indicates the last node of the linked list
----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.


 #include <iostream>

using namespace std;

struct Node {
    int data;
    Node * next;
};

// initialize linked list
void initNode( struct Node * node, int val )
{
    node -> data = val;
    node -> next = NULL;

}
// add node
void addNode ( struct Node * node, int val)
{
    // create new node
    // this node will be placed at the end of node
    // that's why newNode -> next is NULL
    Node * newNode = new Node;
    newNode -> data = val;
    newNode -> next = NULL;

    Node * tmp = node;
    //move to the end of linked list
    while ( true ) {
        // when program gets to the end of linked list add new node
        // this new node become the end of linked list
        if ( tmp -> next == NULL ){
            tmp -> next = newNode;
            return;
        }
        tmp = tmp -> next;
    }

}

// add node at the beginning of linked list
void addNodeAtFirst ( struct Node * node, int val)
{
    // make a copy of the first node
    Node * newNode = new Node;
    newNode -> data = node -> data;
    newNode -> next = node -> next;

    // change the fist node of linked lisk to the val
    // point the head of node to new node
    node -> data = val;
    node -> next = newNode;
  

}

// delete all node
void deleteAllNode ( struct Node * node)
{
    Node * tmp = node;

    // delete all node
    // loop stop when it reaches to the last node
    while (tmp -> next != NULL){
        Node * helper = tmp;
        tmp = tmp-> next;
        delete helper;
    }

    // delete the last node
    delete tmp;
}

// print all node
void printNode( struct Node * node)
{
    // case when there is no item in the linked list
    if(node == NULL){
        cout << "there is no item" << endl;
    }
    // print node until the program reaches to the last node
    else{
        Node * tmp = node;
        while ( tmp -> next != NULL){
            cout << tmp -> data << endl;
            tmp = tmp ->next;
        }

        // print last node
        cout << tmp -> data << endl;
    }
}

// seach for specific node
bool searchNode ( struct Node * node, int val)
{
    Node * tmp = node;
    //checking everything except last one

    while( tmp -> next != NULL){
        if (tmp -> data == val){
            return true;
        }
        tmp = tmp-> next;
    }

    //checking the last one
    if( tmp -> data == val)
        return true;
    else
        return false;
}

// delete certain node
void deleteNode ( struct Node * node, int val)
{
    Node * tmp = node;
    Node * tmp2 = node;

    // seach for node
    // tmp and tmp2 point same node for the first node of the linked list
    // after that
    // tmp points the current node
    // tmp2 points the previous node
    while ( tmp -> next != NULL){
        if (tmp -> data == val){
            tmp2 -> next = tmp-> next;
            cout << "delete " << tmp -> data << endl;
            delete tmp;
            return;
        }
        tmp2 = tmp;
        tmp = tmp ->next;
    }

    // after the loop, tmp points the last node of linked list
    // you do not have to worry about tmp2 at this point.
    // becuase tmp already checked it.
    if (tmp -> data == val){
        cout << "delete "  << tmp -> data << endl;
        delete tmp;
        return;
    }

    else{
        cout << "there is no such val, cannot delete the request val" << endl;
    }

}


int main()
{
    // If node is empty, you cannot print the linked list ( you will get the error)
    // other than that, feel free to play with it

    Node * head = new Node();
    initNode( head, 10);
    addNode( head,  6);
    addNode( head, 3);
    addNode( head, 67);
    addNodeAtFirst (head, 99);
    printNode( head );
    deleteAllNode( head );

    cout << "new start" << endl;
    head = new Node();
    initNode( head, 5 );
    addNode ( head, 65);
    addNode ( head, 75);
    printNode( head );

    cout << "search 6. Since there is no 6 in the linked list, the following funtion return 0" << endl;
    cout << searchNode( head, 6) << endl;
    cout << "search 5. the following function return 1" << endl;
    cout << searchNode( head, 5) << endl;

    deleteNode( head, 65);
    deleteNode( head, 75);
    deleteNode( head, 5);

    printNode( head );
  

}