Showing posts with label C. Show all posts
Showing posts with label C. Show all posts

Saturday, July 20, 2013

CPP Vector with Array


Simple Note

Code

#include <iostream> 
#include <vector>

using namespace std;

/** Test basic vector operation with array,
 *
 * From http://www.cplusplus.com/reference/vector/vector/
 *        Vectors are sequence containers representing arrays that can change in size.
 *
 *        Just like arrays, vectors use contiguous storage locations for their elements,
 *        which means that their elements can also be accessed using offsets on regular pointers
 *        to its elements, and just as efficiently as in arrays. But unlike arrays, their size
 *        can change dynamically, with their storage being handled automatically by the container.
 */
void testBasic ();
void testInitialWithArray ();
int main() {
    testBasic();
    testInitialWithArray();
    system("PAUSE");
    return 0;
}

void testBasic () {
    cout << "function testBasic" << endl;
    // declare and init with size and default value
    // first param for size
    // second param for default value
    vector<int> intVector(5, 3);
    // declare and init with another vector
    // the values will be copied from intVector to intVectorTwo
    // change the value of intVectorTwo will not affect intVector
    vector<int> intVectorTwo(intVector);
    // declare int vector
    vector<int> intVectorThree(5);
    intVectorTwo[3] = 5;
    // init
    // vector knows the size itself
    for (int i = 0; i < intVectorThree.size(); i++) {
        intVectorThree[i] = 3*i;
    }
    // output content of vector
    cout << "output initVector: ";
    for (int i = 0; i < intVector.size(); i++) {
        if (i > 0) {
            cout << ", ";
        }
        cout << intVector[i];
    }
    
    cout << endl << "output initVectorTwo: ";
    for (int i = 0; i < intVectorTwo.size(); i++) {
        if (i > 0) {
            cout << ", ";
        }
        cout << intVectorTwo[i];
    }
    cout << endl << "output initVectorThree: ";
    for (int i = 0; i < intVectorThree.size(); i++) {
        if (i > 0) {
            cout << ", ";
        }
        cout << intVectorThree[i];
    }
    cout << endl << endl;
}

void testInitialWithArray () {
    cout << "function testInitialWithArray" << endl;
    int arr[] = {1, 3, 5};
    // declare and init with array
    vector<int> intVector(arr, arr+3);
    // declare and init with partial array
    vector<int> intVectorTwo(arr+1, arr+3);
    // output content of vector
    cout << "output initVector: ";
    for (int i = 0; i < intVector.size(); i++) {
        if (i > 0) {
            cout << ", ";
        }
        cout << intVector[i];
    }
    cout << endl << "output initVectorTwo: ";
    for (int i = 0; i < intVectorTwo.size(); i++) {
        if (i > 0) {
            cout << ", ";
        }
        cout << intVectorTwo[i];
    }
    cout << endl << endl;
}


Result



References

Vector
http://www.cplusplus.com/reference/vector/vector/

Download

https://github.com/benbai123/C_Cplusplus_Practice/blob/master/CPP/CPP_Basic/Vector/vector_with_array.cpp

Thursday, March 21, 2013

C String: startsWith, endsWith, indexOf, lastIndexOf in ANSI C


Introduction

This article describe how to implement several function with respect to the index of string, including startsWith, endsWith, indexOf, indexOf with a shift and lastIndexOf.

The Program

startsWith_endsWith_indexOf_lastIndexOf.c

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
/**
 * 
 * Tested with Dev-C++ 4.9.9.2
 *  
 * Practice of string compare.
 *
 * char * strstr ( const char *, const char * ); 
 *            Locate substring
 *            Returns a pointer to the first occurrence of str2 in str1,
 *            or a null pointer if str2 is not part of str1.
 * bool startsWith (char* base, char* str);
 *            Custom function for detecting whether base is starts with str
 * bool endsWith (char* base, char* str);
 *            Custom function for detecting whether base is ends with str
 * int indexOf (char* base, char* str)
 *            Custom function for getting the first index of str in base
 *            -1 denotes not found
 * int indexOf_shift (char* base, char* str, int startIndex)
 *            Custom function for getting the first index of str in base
 *            after the given startIndex
 *            -1 denotes not found
 * int lastIndexOf (char* base, char* str)
 *            Custom function for getting the last index of str in base
 *            -1 denotes not found
 * References: 
 *        http://www.cplusplus.com/reference/cstring/strstr/
 * 
 */

bool startsWith (char* base, char* str);
bool endsWith (char* base, char* str);
int indexOf (char* base, char* str);
int indexOf_shift (char* base, char* str, int startIndex);
int lastIndexOf (char* base, char* str);
int main () {
    // a char array without '\0'
    char* chArrOne = "abcdefabcdef";

    printf("chArrOne starts with abc?\n%s\n\n", startsWith(chArrOne, "abc")? "true" : "false");
    printf("chArrOne starts with def?\n%s\n\n", startsWith(chArrOne, "def")? "true" : "false");
    printf("chArrOne ends with def?\n%s\n\n", endsWith(chArrOne, "def")? "true" : "false");
    printf("first index of abc in chArrOne?\n%d\n\n", indexOf(chArrOne, "abc"));
    printf("first index of def in chArrOne?\n%d\n\n", indexOf(chArrOne, "def"));
    printf("first index of abc in chArrOne after index 2?\n%d\n\n", indexOf_shift(chArrOne, "abc", 2));
    printf("first index of def in chArrOne after index 5?\n%d\n\n", indexOf_shift(chArrOne, "def", 5));
    printf("last index of abc in chArrOne?\n%d\n\n", lastIndexOf(chArrOne, "abc"));
    printf("last index of def in chArrOne?\n%d\n\n", lastIndexOf(chArrOne, "def"));
    

    system("PAUSE");
    return 0;
}
/** detecting whether base is starts with str
 */
bool startsWith (char* base, char* str) {
    return (strstr(base, str) - base) == 0;
}
/** detecting whether base is ends with str
 */
bool endsWith (char* base, char* str) {
    int blen = strlen(base);
    int slen = strlen(str);
    return (blen >= slen) && (0 == strcmp(base + blen - slen, str));
}
/** getting the first index of str in base
 */
int indexOf (char* base, char* str) {
    return indexOf_shift(base, str, 0);
}
int indexOf_shift (char* base, char* str, int startIndex) {
    int result;
    int baselen = strlen(base);
    // str should not longer than base
    if (strlen(str) > baselen || startIndex > baselen) {
        result = -1;
    } else {
        if (startIndex < 0 ) {
            startIndex = 0;
        }
        char* pos = strstr(base+startIndex, str);
        if (pos == NULL) {
            result = -1;
        } else {
            result = pos - base;
        }
    }
    return result;
}
/** use two index to search in two part to prevent the worst case
 * (assume search 'aaa' in 'aaaaaaaa', you cannot skip three char each time)
 */
int lastIndexOf (char* base, char* str) {
    int result;
    // str should not longer than base
    if (strlen(str) > strlen(base)) {
        result = -1;
    } else {
        int start = 0;
        int endinit = strlen(base) - strlen(str);
        int end = endinit;
        int endtmp = endinit;
        while(start != end) {
            start = indexOf_shift(base, str, start);
            end = indexOf_shift(base, str, end);

            // not found from start
            if (start == -1) {
                end = -1; // then break;
            } else if (end == -1) {
                // found from start
                // but not found from end
                // move end to middle
                if (endtmp == (start+1)) {
                    end = start; // then break;
                } else {
                    end = endtmp - (endtmp - start) / 2;
                    if (end <= start) {
                        end = start+1;
                    }
                    endtmp = end;
                }
            } else {
                // found from both start and end
                // move start to end and
                // move end to base - strlen(str)
                start = end;
                end = endinit;
            }
        }
        result = start;
    }
    return result;
}


The Result



Reference

strstr
http://www.cplusplus.com/reference/cstring/strstr/

Download

startsWith_endsWith_indexOf_lastIndexOf.c at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_StringProcessing/utils/startsWith_endsWith_indexOf_lastIndexOf.c

Monday, March 18, 2013

C String: String Compare (Simple Note)


Simple Note

Code

#include <stdio.h>
#include <string.h>
/**
 * 
 * Tested with Dev-C++ 4.9.9.2
 *  
 * Practice of string compare.
 *
 * int strcmp ( const char * str1, const char * str2 );
 *             Compares the C string str1 to the C string str2.
 *             Returns an integral value indicating the relationship between the strings:
 *             A zero value indicates that both strings are equal.
 *             A value greater than zero indicates that the first character that does
 *             not match has a greater value in str1 than in str2; And a value less than zero
 *             indicates the opposite.
 * size_t strspn ( const char * str1, const char * str2 );
 *            Returns the length of the initial portion of str1 which consists only of characters that are part of str2.
 *            The length of the initial portion of str1 containing only characters that appear in str2.
 *            Therefore, if all of the characters in str1 are in str2,
 *            the function returns the length of the entire str1 string,
 *            if the first character in str1 is not in str2,
 *            the function returns zero.
 *             size_t is an unsigned integral type.
 *
 * References: 
 *         http://www.cplusplus.com/reference/cstring/strcmp/
 *        http://www.cplusplus.com/reference/cstring/strspn/
 * 
 */
int main () {
    // string
    char* chPtr = "abcdwxyz";
    int len;

    /** Compare whether two strings are
     * equal, grater than or less than
     */
    printf("chPtr equals to 'abcdwxyz'? \n%s\n", (strcmp(chPtr, "abcdwxyz") == 0? "true" : "false"));
    printf("chPtr larger than 'abcd'? \n%s\n", (strcmp(chPtr, "abcd") > 0? "true" : "false"));
    printf("chPtr less than or equal to 'abcd'? \n%s\n\n", (strcmp(chPtr, "abcd") <= 0? "true" : "false"));

    /** Use strspn to compare and find the different position
     *
     */
    len = strspn(chPtr, "abcdwxyz");
    printf("Are chPtr and 'abcdwxyz' equal? \n%s\n", (len == strlen(chPtr)? "true" : "false"));
    len = strspn(chPtr, "abcd");
    printf("Are chPtr and 'abcd' equal? \n%s\n", (len == strlen(chPtr)? "true" : "false"));
    printf("What is the first index (start from 0) that 'abcd' different with chPtr? \n%d\n\n", len);

    system("PAUSE");
    return 0;
}


Result



References

strcmp
http://www.cplusplus.com/reference/cstring/strcmp/

strspn
http://www.cplusplus.com/reference/cstring/strspn/

Download

Source code at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_StringProcessing/string_compare.c

C String: String Search (Simple Note)


Simple Note

Code

#include <stdio.h>
#include <string.h>
/**
 * 
 * Tested with Dev-C++ 4.9.9.2
 *  
 * Practice of string compare.
 *
 * char * strstr ( const char *, const char * ); 
 *            Locate substring
 *            Returns a pointer to the first occurrence of str2 in str1,
 *            or a null pointer if str2 is not part of str1.
 *
 * References: 
 *        http://www.cplusplus.com/reference/cstring/strstr/
 * 
 */

int main () {
    // string
    char* chPtr = "abcdwxyz";
    char* pos;

    /** Search a string within chPtr
     *
     */
    // memory address
    pos = strstr(chPtr, "cd");
    printf("Is 'cd' in chPtr? \n%s\n", (pos != NULL? "true" : "false"));
    // start index is pos - chPtr
    if (pos != NULL) {
        printf("What is the first start index (start from 0) of 'cd' in chPtr? \n%d\n\n", (pos - chPtr));
    }

    printf("abcd starts from \n%d\n", strstr(chPtr, "abcd") - chPtr);
    printf("abcd starts from \n%d\n\n", strstr(chPtr, "wxyz") - chPtr);

    system("PAUSE");
    return 0;
}


Result



References

strstr
http://www.cplusplus.com/reference/cstring/strstr/

Download

Source code at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_StringProcessing/string_search.c

Sunday, March 17, 2013

C String: substring Function for ANSI C


Introduction

This article describe how to create a function that get a sub string from source string by start index and end index (similar to Java's String.substring) in ANSI C.

The Program

substring.c

A custom substring function and test program in this file.

#include <stdio.h>
#include <string.h>
/**
 * 
 * Tested with Dev-C++ 4.9.9.2
 *  
 * Practice of string copy and concat.
 *
 * char * strncpy ( char * destination, const char * source, size_t num );
 *         copy first n (the specified num) char
 *         from source to destination
 * void* malloc (size_t size);
 *         Allocate memory block
 *         Allocates a block of size bytes of memory,
 *         returning a pointer to the beginning of the block.
 *         
 *         The content of the newly allocated block of memory is not initialized,
 *         remaining with indeterminate values.
 *         
 *         If size is zero, the return value depends on the particular
 *         library implementation (it may or may not be a null pointer),
 *         but the returned pointer shall not be dereferenced.
 * void free (void* ptr);
 *         A block of memory previously allocated by a call to malloc,
 *         calloc or realloc is deallocated,
 *         making it available again for further allocations.
 *         
 *         If ptr does not point to a block of memory allocated with the
 *         above functions, it causes undefined behavior.
 *         
 *         If ptr is a null pointer, the function does nothing.
 *         Notice that this function does not change the value of ptr itself,
 *         hence it still points to the same (now invalid) location.
 * void * memset ( void * ptr, int value, size_t num );
 *         Fill block of memory
 *         Sets the first num bytes of the block of memory pointed by ptr to
 *         the specified value (interpreted as an unsigned char).
 * 
 * char * substring ( const char * source, int startIndex, int endIndex );
 *         custom function for getting a substring of source string
 *         source: the source string
 *         startIndex: start index (inclusive) of sub string in source string
 *         endIndex: end index (exclusive) of sub string in source string
 *         return: pointer of the sub string, or null if any error occured
 *
 *         NOTE: substring will return malloced pointer,
 *               remember to free it as needed.
 *
 * References:
 * http://www.cplusplus.com/reference/cstring/strncpy/
 * http://www.cplusplus.com/reference/cstdlib/malloc/
 * http://www.cplusplus.com/reference/cstdlib/free/
 * http://www.cplusplus.com/reference/cstring/memset/
 * 
 */
char * substring ( const char * source, int startIndex, int endIndex );
int main () {
    char* chArr = "this is substring";

    // test negitive startIndex
    char* subString = substring(chArr, -1, 8);
    printf("%s\n\n", subString);
    free(subString);

    // test endIndex smaller than or equal to startIndex
    subString = substring(chArr, 17, 8);
    printf("%s\n\n", subString);
    free(subString);

    subString = substring(chArr, 8, 8);
    printf("%s\n\n", subString);
    free(subString);

    // test startIndex out of bound
    subString = substring(chArr, 177, 178);
    printf("%s\n\n", subString);
    free(subString);

    // test endIndex out of bound
    subString = substring(chArr, 17, 178);
    printf("%s\n\n", subString);
    free(subString);

    // get sub string and show it
    subString = substring(chArr, 0, 1);
    printf("%s\n\n", subString);
    free(subString);

    subString = substring(chArr, strlen(chArr)-1, strlen(chArr));
    printf("%s\n\n", subString);
    free(subString);

    subString = substring(chArr, 8, 17);
    printf("%s\n\n", subString);
    free(subString);

    subString = substring(chArr, 14, 17);
    printf("%s\n\n", subString);
    free(subString);

    system("PAUSE");
}
/**
 * custom function for getting a substring of source string
 *         source: the source string
 *         startIndex: start index (inclusive) of sub string in source string
 *         endIndex: end index (exclusive) of sub string in source string
 *         return: pointer of the sub string, or null if any error occured
 *
 *         NOTE: substring will return malloced pointer,
 *               remember to free it as needed.
 */
char * substring ( const char * source, int startIndex, int endIndex ) {
    char* result = NULL;
    if (startIndex < 0) {
        printf("startIndex should be a positive value\n");
    }
    else if (endIndex <= startIndex) {
        printf("endIdnex should larger than startIndex\n");
    } else if (startIndex > (strlen(source))) {
        printf("startIdnex should smaller than source length\n");
    } else if (endIndex > (strlen(source)+1)) {
        printf("endIdnex should smaller than or equal to source length\n");
    } else {
        int len = endIndex - startIndex;
        result = (char*)malloc(sizeof(char)*len+1);
        memset (result, '\0', len+1);
        strncpy (result, source+startIndex, len);
    }
    return result;
}


The Result



Reference

strncpy
http://www.cplusplus.com/reference/cstring/strncpy/

malloc
http://www.cplusplus.com/reference/cstdlib/malloc/

free
http://www.cplusplus.com/reference/cstdlib/free/

memset
http://www.cplusplus.com/reference/cstring/memset/

Get a substring of a char* at stackoverflow
http://stackoverflow.com/questions/4214314/get-a-substring-of-a-char

Download

substring.c
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_StringProcessing/utils/substring.c

Friday, February 22, 2013

C String: String Concat (Simple Note)


Simple Note

Code

#include <stdio.h>
#include <string.h>
/**
 * 
 * Tested with Dev-C++ 4.9.9.2
 *  
 * Practice of string copy and concat.
 * char * strcat ( char * destination, const char * source );
 *         Appends a copy of the source string to the destination string
 *         plus a terminating null-character if source contains null-character.
 * char * strncat ( char * destination, char * source, size_t num );
 *         Appends the first num characters of source to destination,
 *         plus a terminating null-character.
 *
 * Note: 
 * 
 */
int main () {
    // a char array without '\0'
    char chArr[4] = {'a', 'b', 'c', 'd'};
    char chArrTwo[20] = "mnopq";
    char chArrThree[] = "abcd";
    char chArrFour[20] = "wxyz";

    // the source (chArr) doesn't have null-char ('\0')
    // will become wrong value after first concat
    printf("original: %s\n", chArrTwo);
    strcat(chArrTwo, chArr); // <-- the line above
    // change the line above to the line below then everything should be okay.
    // strncat(chArrTwo, chArr, 4); // <-- the line below
    printf("append abcd: %s\n", chArrTwo);
    strncat(chArrTwo, chArr, 2);
    printf("append ab: %s\n\n", chArrTwo);

    // the source (chArrThree) contains null-char ('\0')
    // everything should be okay
    printf("original: %s\n", chArrFour);
    strcat(chArrFour, chArrThree);
    printf("append abcd: %s\n", chArrFour);
    strncat(chArrFour, chArrThree, 2);
    printf("append ab: %s\n\n", chArrFour);

    system("PAUSE");
}

Result



References

strcat
http://www.cplusplus.com/reference/cstring/strcat/

strncat
http://www.cplusplus.com/reference/cstring/strncat/

Download

Source code at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_StringProcessing/string_concat.c

C String: Copy String (Simple Note)


Simple Note

Code

#include <stdio.h>
#include <string.h>
/**
 * 
 * Tested with Dev-C++ 4.9.9.2
 *  
 * Practice of string copy and concat.
 * char * strcpy ( char * destination, const char * source );
 *         copy source to destination
 * char * strncpy ( char * destination, const char * source, size_t num );
 *         copy first n (the specified num) char
 *         from source to destination
 * memset ( void * ptr, int value, size_t num );
 *        Sets the first n (the specified num) bytes of the
 *          block of memory pointed by ptr to the specified value
 *        (interpreted as an unsigned char).
 * 
 */
int main () {
    // a char array without '\0'
    char chArr[4] = {'a', 'b', 'c', 'd'};
    char chArrTwo[6] = "mnopq";
    char chArrThree[6];
    char chArrFour[6];

    // copy chArr to chArrThree
    // will not add '\0' automatically
    strcpy(chArrThree, chArr);
    printf("chArrThree terminate with \\0? %s \n", (chArrThree[4] == '\0'? "true" : "false"));
    // output chArrThree, may contains wrong value since no \0
    printf("%s\n", chArrThree);


    // add \0 manually
    chArrThree[4] = '\0';
    // copy (replace) first Three char of chArrTwo to chArrThree
    strncpy(chArrThree, chArrTwo, 2);
    printf("chArrThree terminate with \\0? %s \n", (chArrThree[4] == '\0'? "true" : "false"));
    // output chArrThree correctly
    printf("%s\n", chArrThree);

    // use memset to preset all chars in chArrFour to \0
    memset(chArrFour, '\0', sizeof(chArrFour));
    // copy chArr to chArrFour
    strncpy(chArrFour, chArr, sizeof(chArr));
    // NOTE:
    // use strncpy will not clear all specified '\0' --> correct
    // use strcpy as below will clear all specified '\0' --> cause wron string
    // strcpy(chArrFour, chArr);
    printf("chArrFour terminate with \\0? %s \n", (chArrFour[4] == '\0'? "true" : "false"));
    // output chArrFour correctly
    printf("%s\n\n", chArrFour);

    system("PAUSE");
}


Result


References

strcpy
http://www.cplusplus.com/reference/cstring/strcpy/

strncpy
http://www.cplusplus.com/reference/cstring/strncpy/

memset
http://www.cplusplus.com/reference/cstring/memset/

Download

Source code at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_StringProcessing/string_copy.c

Sunday, February 17, 2013

C String: Declare, Modify and Length (Simple Note)


Simple Note

Code

#include <stdio.h>
#include <string.h>

int main () {
    /**
     * declare, modify and length
     *
     */
    // declare string
    char* chPtr = "abcdefg";// will add '\0' at the tail automatically
    char chArr[] = "bbcdefg";
    char chArrTwo[] = {'c', 'b', 'c', 'd', 'e', 'f', 'g'}; // will not add '\0' automatically
    char chArrThree[] = {'d', 'b', 'c', 'd', 'e', 'f', 'g', '\0', '\0', '\0'};

    // output string
    printf("chPtr = %s\n", chPtr);
    printf("chArr = %s\n", chArr);
    printf("chArrTwo = %s\n", chArrTwo);
    printf("chArrThree = %s\n", chArrThree);

    // output length by sizeof
    // 4, the size of pointer
    printf ("\nLenbgh of char pointer = %d\n", sizeof(chPtr));
    // 8, the size of whole array
    // including a, b, c, d, e, f, g and '\0' (the terminate char added automatically)
    printf ("Length of char array = %d\n", sizeof(chArr));
    // 7, no terminate char
    printf ("Length of char array two = %d\n", sizeof(chArrTwo));
    // 10, including 3 terminate char
    printf ("Length of char array three = %d\n", sizeof(chArrThree));

    // output length by strlen
    // 7, only count the length before first '\0' or array length
    printf ("\nLenbgh of char pointer = %d\n", strlen(chPtr));
    printf ("Length of char array = %d\n", strlen(chArr));
    printf ("Length of char array two = %d\n", strlen(chArrTwo));
    printf ("Length of char array three = %d\n", strlen(chArrThree));

    // replace first char
    // cannot modify char points by a char pointer
    // this line below cause the runtime error
    // chPtr[0] = 'w';
    chArr[0] = 'x';
    chArrTwo[0] = 'y';
    chArrThree[0] = 'z';

    // output string again
    printf("\nchPtr = %s\n", chPtr);
    printf("chArr = %s\n", chArr);
    printf("chArrTwo = %s\n", chArrTwo);
    printf("chArrThree = %s\n\n", chArrThree);
    
    system("PAUSE");
}


Result



Reference

cplusplus
http://www.cplusplus.com/reference/cstring/strlen/

Thread at SF: Is it possible to modify a string of char in C?
http://stackoverflow.com/questions/1011455/is-it-possible-to-modify-a-string-of-char-in-c

Download

Code at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_StringProcessing/string_declare_modify_and_length.c

Sunday, November 18, 2012

C/C++ Logical and Bitwise Operators



Introduction

A simple note of C/C++ Logical and Bitwise Operators

Code

#include <iostream>
using namespace std;

/** some practice of logical operators
 * and bitwise operators
 */
int main () {

    cout << endl;
    cout << "\tLogical operators" << endl;
    // && (Logical AND)
    // All true -> true
    // Any false -> false
    cout << "\ttrue && true && true\t -> \t" << (true && true && true? "true" : "false") << endl;
    cout << "\ttrue && true && false\t -> \t" << (true && true && false? "true" : "false") << endl;
    // || (Logical OR)
    // Any true -> true
    // All false -> false
    cout << "\tfalse || false || true\t -> \t" << (false || false || true? "true" : "false") << endl;
    cout << "\tfalse || false || false\t -> \t" << (false || false || false? "true" : "false") << endl;
    // ! (Logical NOT)
    // inverse the value
    cout << "\t!true\t\t\t -> \t" << (!true? "true" : "false") << endl;
    cout << "\t!false\t\t\t -> \t" << (!false? "true" : "false") << endl << endl;

    cout << "\tBitwise operators" << endl;
    // & (Bitwise AND)
    // 0 & any -> 0
    // 1 & 1 -> 1
    // 3 & 5 -> 0011 & 0101 = 0001 -> 1
    cout << "\t3 & 5\t\t\t -> \t" << (3 & 5) << endl;

    // | (Bitwise Inclusive OR)
    // 1 | any -> 1
    // 0 | 0 -> 0
    // 3 | 5 -> 0011 | 0101 = 0111 -> 7
    cout << "\t3 | 5\t\t\t -> \t" << (3 | 5) << endl;

    // ^ (Bitwise Exclusive OR)
    // 0 ^ 0 -> 0
    // 1 ^ 1 -> 0
    // 1 ^ 0 -> 1
    // 0 ^ 1 -> 1
    // 3 ^ 5 -> 0011 ^ 0101 = 0110 -> 6
    cout << "\t3 ^ 5\t\t\t -> \t" << (3 ^ 5) << endl;

    // << (Shift Left)
    // 0001 << 1 -> 0010
    // 0001 << 2 -> 0100
    // shift all bits to left side and add 0 to right side,
    // the left side bits will be dropped,
    // e.g., 100...001 << 1 -> 00...010
    // 
    // can use it as *2 operation 
    // 3 << 1 -> 0011 << 1 = 0110 -> 6 (3*2)
    // 3 << 2 -> 0011 << 2 = 1100 -> 12 (3*2*2)
    cout << "\t3 << 1\t\t\t -> \t" << (3 << 1) << endl;
    cout << "\t3 << 2\t\t\t -> \t" << (3 << 2) << endl;

    // << (Shift Right)
    // 0100 >> 1 -> 0010
    // 0100 >> 2 -> 0001
    // shift all bits to right side and
    // add 0 or 1 (depends on system) to left side,
    // the right side bits will be dropped,
    // e.g., ...00011 >> 1 -> ...0001
    // 
    // can use it as /2 operation 
    // 12 >> 1 -> 1100 >> 1 = 0110 -> 6 (12/2)
    // 12 >> 2 -> 1100 >> 2 = 0011 -> 3 (12/2/2)
    cout << "\t12 >> 1\t\t\t -> \t" << (12 >> 1) << endl;
    cout << "\t12 >> 2\t\t\t -> \t" << (12 >> 2) << endl;

    // ~ (Unary complement (bit inversion))
    // 0 -> 1
    // 1 -> 0
    // ~ (char) -128 -> ~10000000 = 01111111 -> 127
    cout << "\t ~(char)-128\t\t -> \t" << ~(char)-128 << endl;
    cout << endl;

    system("PAUSE");
    return 0;
}


Result



Reference

http://www.cplusplus.com/doc/tutorial/operators/
http://en.wikipedia.org/wiki/Bitwise_operation


Download

File at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/CPP/CPP_Basic/logical_and_bitwise_operator.cpp

Saturday, July 28, 2012

ANSI C: N Queens Problem


Introduction

The n queens puzzle is the problem of placing n chess queens on an n*n chessboard so that no two queens attack each other.

The Program

queens_ori.c


#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

/**
 * The n queens puzzle is the problem of
 * placing n chess queens on an n×n chessboard
 * so that no two queens attack each other. 
 */

// define some values to shorten the code

// status message and params
// printf(statmsg, statparam); will become
// printf("there are %d queens in a %d x %d chessboard\n\n answer(s): \n\n", number_of_queens, number_of_queens, number_of_queens);
#define statmsg "there are %d queens in a %d x %d chessboard\n\n answer(s): \n\n"
#define statparam number_of_queens, number_of_queens, number_of_queens
// answer message and params
#define ansmsg "put col[%d] queen to row %d\n"
#define ansparam outIdx, col[outIdx]
int number_of_queens;  // n queens in nxn chessboard
                       // note: don't too large (ex, over 25)
int *col;  // chessboard
FILE *outptr; // output file
int cnt; // result count

// function to solve this problem
void queens( int currentCol );
// function to determing whether the status is valid
bool promising( int currentCol );

int main()
{

  cnt = 0;
  
  printf("please enter the number of queens:\n");
  scanf("%d", &number_of_queens);
  // col[0] not used, start from col[1]
  col = (int*) malloc ((number_of_queens+1)*sizeof(int));
  outptr = fopen("QueenSol.txt", "w" );

  printf(statmsg, statparam);
  fprintf(outptr, statmsg, statparam);
  // call function to solve problem
  // pass 0 into it but it will then start from 1
  queens( 0 );

  if (cnt == 0) {
     printf(" no result\n\n");
     fprintf(outptr, " no result\n\n");
  }
  fclose( outptr );
  free(col);

  system("PAUSE");
  return 0;
}

void queens( int currentCol )
{
 int row;    // row index to test
 int outIdx; // index for output result
 if( promising(currentCol) )  // if valid
 {
   if( currentCol == number_of_queens )  // output if at latest col
   {
     cnt++;
     for( outIdx = 1; outIdx <= number_of_queens; outIdx++ )
     {
       printf(ansmsg, ansparam);
       fprintf(outptr, ansmsg, ansparam);
     }
     printf("\n\n");
     fprintf(outptr, "\n\n");
   }

   // call function recursively if not latest col
   else
   {
     for(row = 1; row <= number_of_queens; row++ )  // test next col from row 1 to row n
     {
       col[currentCol + 1] = row;
       queens( currentCol + 1 );
     }
   }

 }
}

// check whether current stats is valid
bool promising( int currentCol )
{
  int idx = 1; // loop index
  bool isValid = true; // is valid? default to true


  // test whether previous queens will attack current queen
  while( (idx < currentCol) && isValid )
  {
    // found invalid status
    // in the same row
    // or diagonal
    if( (col[currentCol] == col[idx])
        || (abs( col[currentCol] - col[idx]) == currentCol - idx) )
    {
        isValid = false;  // set to invalid, stop loop
    }
    idx++;  // increase index and contiune

  }
  return isValid;
}



The Result




Reference
http://en.wikipedia.org/wiki/Eight_queens_puzzle


Download
The files are at github
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Algorithm/N_Quenes

Sunday, July 22, 2012

ANSI C: Hamiltonian cycle


Introduction

A Hamiltonian path (or traceable path) is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle.

In this post, we will implement an ANSI C program that will display all Hamiltonian cycle of a given graph array.

The Program

hamiltonian.c

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

/**
 * A Hamiltonian path (or traceable path)
 * is a path in an undirected graph that
 * visits each vertex exactly once.
 * A Hamiltonian cycle (or Hamiltonian circuit) is
 * a Hamiltonian path that is a cycle.
 * From wiki: http://en.wikipedia.org/wiki/Hamiltonian_path
 */

// the number of nodes in the test graphic
int node_amount = 12;
// the number of Hamiltonian cycles
int hamiltonian_cycle_amount = 0;

// Graph Representation with nodes
// not use [0][x] and [x][0]
int graph_array[13][13] = {
                 0,0,0,0,0,0,0,0,0,0,0,0,0,
                 0,0,1,0,0,1,0,0,0,0,0,0,0,
                 0,1,0,1,0,0,0,1,1,0,0,0,0,
                 0,0,1,0,1,0,0,0,1,0,0,0,0,
                 0,0,0,1,0,1,0,0,0,1,0,0,0,
                 0,1,0,0,0,0,1,0,0,0,1,0,0,
                 0,0,0,0,0,1,0,1,0,0,0,1,0,
                 0,0,1,0,0,0,1,0,1,0,0,0,0,
                 0,0,1,1,0,0,0,1,0,1,0,0,0,
                 0,0,0,0,1,0,0,0,1,0,1,0,1,
                 0,0,0,0,0,1,0,0,0,0,0,1,0,
                 0,0,0,0,0,0,1,0,0,0,1,0,1,
                 0,1,0,0,0,0,0,0,0,1,0,1,0
                };

// the array store the result through recursive
int result_array[13] = {0};

/**
 * The function that find all Hamiltonian cycle
 * and output to console
 * param node_index: int, nth node in path
 */
void hamiltonian ( int node_index );
/**
 * The function that check whether current node
 * is valid in Hamiltonian cycle.
 */
bool promising ( int node_index );

int main()
{
  printf("\n");
  result_array[1] = 1;  // start from first node
  hamiltonian( 1 );  // start to find all Hamiltonian cycles recursively

  if( hamiltonian_cycle_amount == 0 )  // no Hamiltonian cycles found
   printf("\nThere is no Hamiltonian cycles in this graph\n\n");

  printf("\n");

  system("PAUSE");
  return 0;
}

void hamiltonian ( int node_index )
{
  int j, k;
  if( promising(node_index) )  // current node is valid in a Hamiltonian cycles
  {
     if( node_index == (node_amount) )  // at latest node
     {  hamiltonian_cycle_amount = 1;  // increase hamiltonian_cycle_amount
        printf(" v%d", result_array[1]);  // print out the result
        for( k = 2;k <= node_amount;k ++ )
          printf(" → v%d", result_array[k]);
        printf("\n\n");
     }
     else  // not latest node
     {
        for( j = 2;j <= node_amount;j ++ )  // recursively scan from second node to latest node
        {
           result_array[node_index+1] = j; // store result
           hamiltonian( node_index+1 );  // call function recursively
        }
     }
  }

}

bool promising ( int node_index )
{
  int j, k;
  bool isValid = true; // default to valid

  j = 1;

  if (node_index == 1) // first node, valid
    isValid =  true;
  if( (node_index == (node_amount)) && (!graph_array[result_array[node_index]][result_array[1]]) )
     isValid =  false;  // latest node but not connected to first node, invalid

  else if( ( node_index > 1 ) && (!graph_array[result_array[node_index-1]][result_array[node_index]]) )
     isValid =  false;  // not connected between current node and previous node, invalid

  else
  {
    while( (j < node_index) && isValid)  // check all previous nodes
    {
       if( result_array[node_index] == result_array [j] )
         isValid = false;  // current point already in path, invalid
       j++;
    }
  }
  return isValid;  // return whether current node is valid
}

The Result


Reference
http://en.wikipedia.org/wiki/Hamiltonian_path

Download
The files at github
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Algorithm/Hamiltonian_Cycle

Sunday, July 15, 2012

ANSI C: Coloring Problem


Introduction

The Coloring Problem is coloring the vertices of a graph such that no two adjacent vertices share the same color, in this post, we will try to implement it in ANSI C.

The Program

Coloring_Problem.c

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

/**
 * Graph coloring
 * Coloring the vertices of a graph such that
 * no two adjacent vertices share the same color;
 * Wiki: http://en.wikipedia.org/wiki/Graph_coloring
 */

FILE *res;

// The 2-D array denotes a graph adjacent status,
// For example, [a, b] are adjacent vertices,
// [a, d] are also adjacent vertices.
// the index starts from 1,
// [0][x] and [x][0] are not considered
                           // #,a,b,c,d,e,f
int _adjacentMatrix [7][7] = {0,0,0,0,0,0,0, // not use
               0,0,1,0,1,0,0, // a
               0,1,0,1,0,1,0, // b
               0,0,1,0,0,0,1, // c
               0,1,0,0,0,1,0, // d 
               0,0,1,0,1,0,1, // e
               0,0,0,1,0,1,0  // f
              };

int _verticeAmount = 6;  // six points

// three colors
char _colors[4][20] = { "NULL",
                      "RED",
                      "GREEN",
                      "WHITE"
                      };

// temp store the result
int _result[7] = {0};

void m_coloring( int i );
bool promising( int i );

int main()
{
  res = fopen("result.txt", "w");
  printf("there are %d vertices, the color combinations are as below: \n\n", _verticeAmount);
  fprintf(res, "there are %d vertices, the color combinations are as below: \n\n", _verticeAmount);
  m_coloring( 0 );
  fclose( res );



      system("PAUSE");
      return 0;
}

/**
 * The coloring function that will recursively create different combinations
 * then call promising function to test whether the combination is valid.
 *
 * Three actions:
 *         Output the result if
 *         the current combination is valid and reach the latest vertice.
 *         
 *         Continue add color - vertice to extend combination if
 *         the current combination is valid but not reach the latest vertice.
 *
 *         Terminate the recursive to skip any combination
 *         that starts with the current combination if
 *         the current combination is not valid.
 *
 */
void m_coloring ( int i )
{
  int color; // color index for test
  int j; // index for output result

  if( promising(i) )  // coloring success
  {
    if( i == _verticeAmount ) // is latest vertice
    {
      for( j = 1;j <= _verticeAmount;j ++ )  // output the result
      {
        if (j > 1) {
          printf(",");
          fprintf(res, ", ");
        }
        printf("%s", _colors[_result[j]]);
        fprintf(res, "%s", _colors[_result[j]]);
      }
      printf("\n\n");
      fprintf(res, "\n\n");

    }

    else  // not latest vertice
    {
       for( color = 1;color <= 3;color ++ )  // test each color
       {
          _result[i+1] = color;  // set color to next vertice
          m_coloring(i+1); // recursive to continue combination
       }
    }
  }
}

/**
 * check whether has adjacent virtice share color with current virtice
 * return bool
 * true: no adjacent vertice share the same color, can 
 * continue this combination
 * false: has adjacent vertice share the same color,
 * this combination should be terminated
 */
bool promising( int currentVerticeIndex )
{
   int j = 1; // start from first virtice
   bool sw = true;  // default to success (no two adjacent vertices share the same color)

   while( (j < currentVerticeIndex) && sw)  // scan all previous vertices
   {
      // if found an adjacent vertice share the same color
      if( _adjacentMatrix[currentVerticeIndex][j] && (_result[currentVerticeIndex] == _result[j])) {
        sw = false;  // set to fail (has two adjacent vertices share the same color)
        break;
      }
      j++;
   }

   return sw;  // return the result (success or fail)
}


The promising function will return whether current combination is valid.

The m_coloring function that will recursively create different combinations then call promising function to test whether the combination is valid. It will do three different actions with respect to the different status and the result of promising function:

1. Output the result if the current combination is valid and reach the latest vertice.

2. Continue add color - vertice to extend combination if the current combination is valid but not reach the latest vertice.

3. Terminate the recursive to skip any combination that starts with the current combination if the current combination is not valid.

The Result



Reference
Wiki
http://en.wikipedia.org/wiki/Graph_coloring


Download
Files at github
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Algorithm/Coloring_Problem

Saturday, April 14, 2012

Simple Linked List in ANSI C

Introduction

This post is about how to implement a Linked List in c, can add item to head, tail or any position, get item from head, tail or any position, display all items.

The Program

LinkedList.c

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
/**
 * This sample is about how to implement a queue in c
 *
 * Type of item is int
 * Add item to head, tail or any position
 * Get item from head, tail or any position
 * Get and remove item from head, tail or any position
 * Can get the size
 * Can display all item
 */
/**
 * The Node struct,
 * contains item and the pointers that point to previous node/next node.
 */
typedef struct Node {
    int item;
    // previous node
    struct Node* prev;
    // next node
    struct Node* next;
} Node;
/**
 * The LinkedList struct, contains the pointers that
 * point to first node and last node, the size of the LinkedList,
 * and the function pointers.
 */
typedef struct LinkedList {
    Node* head;
    Node* tail;
    // size of this LinkedList
    int size;

    // add item to any position
    void (*add) (struct LinkedList*, int, int);
    // add item after tail
    void (*addLast) (struct LinkedList*, int);
    // add item before head
    void (*addFirst) (struct LinkedList*, int);

    // insert node
    void (*insertBefore) (struct LinkedList*, Node*, Node*);
    // get item from any position
    int (*get) (struct LinkedList*, int);
    // get last item
    int (*getLast) (struct LinkedList*);
    // get first item
    int (*getFirst) (struct LinkedList*);

    // remove item from any position
    int (*remove) (struct LinkedList*, int);
    // remove last item
    int (*removeLast) (struct LinkedList*);
    // remove first item
    int (*removeFirst) (struct LinkedList*);

    // display all element in the LinkedList
    void (*display) (struct LinkedList*);
    // create a node with item
    Node* (*createNode) (int);
} LinkedList;

/** add item to any position
 */
void add (LinkedList* _this, int item, int position);
/** add item to head
 */
void addFirst (LinkedList* _this, int item);
/** add item to tail
 */
void addLast (LinkedList* _this, int item);
/** insert one node before another,
 * newNdoe, node and node->prev should not be null.
 */
void insertBefore (LinkedList* _this, Node* node, Node* newNode);
/** get item from specific position
 */
int get (LinkedList* _this, int position);
/** get item from head
 */
int getFirst (LinkedList* _this);
/** get item from tail
 */
int getLast (LinkedList* _this);
/** get item and remove it from any position
 */
int _remove (LinkedList* _this, int position);
/** get and remove item from head
 */
int _removeFirst (LinkedList* _this);
/** get and remove item from tail
 */
int _removeLast (LinkedList* _this);
/** display the items in the list
 */
void display (LinkedList* _this);
/** create a LinkedList
 */
LinkedList createLinkedList ();
/** create a Node
 */
Node* createNode (int item);

int main () {
    LinkedList list = createLinkedList();

    // 3
    list.addFirst(&list, 3);
    // 3, 5
    list.addLast(&list, 5);
    // 3, 4, 5
    list.add(&list, 4, 1);
    list.display(&list);

    // 3, 4, 5, 6
    list.addLast(&list, 6);
    // 3, 4, 5, 6, 7
    list.addLast(&list, 7);
    list.display(&list);
    printf("Get item: %d\n", list.get(&list, 2));
    printf("Get item: %d\n", list.get(&list, 4));
    list.display(&list);
    // 4, 5, 6, 7
    printf("Remove item: %d\n", list.removeFirst(&list));
    // 4, 5, 6
    printf("Remove item: %d\n", list.removeLast(&list));
    // 4, 6
    printf("Remove item: %d\n", list.remove(&list, 1));
    list.display(&list);

    system("PAUSE");
}
/** add item to any position
 */
void add (LinkedList* _this, int item, int position) {
     // index out of list size
     if (position > _this->size) {
        printf("LinkedList#add: Index out of bound");
        system("PAUSE");
        exit(0);
    }
    // add to head
    if (position == 0) {
        _this->addFirst(_this, item);
    } else if (position == _this->size) {
        // add to tail
        _this->addLast(_this, item);
    } else {
        // insert between head and tail

        Node* node = _this->head;
        int i = 0;
        // loop until the position
        while (i < position) {
            node = node->next;
            i++;
        }
        // insert new node to position
        Node* newNode = _this->createNode(item);
        _this->insertBefore(_this, node, newNode);
        _this->size++;
    }
}
/** add item to head
 */
void addFirst (LinkedList* _this, int item) {
    Node* newNode = _this->createNode(item);
    Node* head = _this->head;
    // list is empty
    if (head == NULL)
        _this->head = newNode;
    else { // has item(s)
        Node* last = _this->tail;
        if (last == NULL) // only head node
            last = head;
        newNode->next = head;
        head->prev = newNode;
        _this->head = newNode;
        _this->tail = last;
    }

    _this->size++;
}
/** add item to tail
 */
void addLast (LinkedList* _this, int item) {
    Node* newNode = _this->createNode(item);
    Node* head = _this->head;
    Node* tail = _this->tail;
    // list is empty
    if (head == NULL)
        _this->head = newNode;
    else { // has item(s)
        Node* lastNode = tail;
        if (tail == NULL) // only head node
            lastNode = head;
        lastNode->next = newNode;
        newNode->prev = lastNode;
        _this->tail = newNode;
    }
    _this->size++;
}

/** insert one node before another,
 * newNdoe, node and node->prev should not be null.
 */
void insertBefore (LinkedList* _this, Node* node, Node* newNode) {
    Node* prev = node->prev;

    node->prev = newNode;
    newNode->next = node;
    prev->next = newNode;
    newNode->prev = prev;
}
/** get item from specific position
 */
int get (LinkedList* _this, int position) {
    // list is empty
    if (_this->size == 0) {
        printf("LinkedList#get: The list is empty.");
        system("PAUSE");
        exit(0);
    } else if (position >= _this->size) {
        // out of bound
        printf("LinkedList#get: Index out of bound");
        system("PAUSE");
        exit(0);
    }
    // get head item
    if (position == 0) {
        return _this->getFirst(_this);
    } else if (position+1 == _this->size) {
        // get tail item
        return _this->getLast(_this);
    } else {
        Node* node = _this->head;
        int i = 0;
        // loop until position
        while (i < position) {
            node = node->next;
            i++;
        }
        return node->item;
    }
}
/** get item from head
 */
int getFirst (LinkedList* _this) {
    // list is empty
    if (_this->size == NULL) {
        printf("LinkedList#getFirst: The list is empty.");
        system("PAUSE");
        exit(0);
    }
    return _this->head->item;
}
/** get item from tail
 */
int getLast (LinkedList* _this) {
    // list is empty
    if (_this->size == 0) {
        printf("LinkedList#getLast: The list is empty.");
        system("PAUSE");
        exit(0);
    }
    // only head node
    if (_this->size == 1) {
        return getFirst(_this);
    }
    return _this->tail->item;
}
/** get item and remove it from any position
 */
int _remove (LinkedList* _this, int position) {
    // list is empty
    if (_this->size == 0) {
        printf("LinkedList#_remove: The list is empty.");
        system("PAUSE");
        exit(0);
    } else if (position >= _this->size) {
        // out of bound
        printf("LinkedList#_remove: Index out of bound");
        system("PAUSE");
        exit(0);
    }

    // remove from head
    if (position == 0) {
        return _this->removeFirst(_this);
    } else if (position+1 == _this->size) {
        // remove from tail
        return _this->removeLast(_this);
    } else {
        Node* node = _this->head;
        Node* prev;
        Node* next;
        int i = 0, item;
        // loop until position
        while (i < position) {
            node = node->next;
            i++;
        }
        item = node->item;
        // remove node from list
        prev = node->prev;
        next = node->next;
        prev->next = next;
        next->prev = prev;
        free(node);
        _this->size--;
        return node->item;
    }
}
/** get and remove item from head
 */
int _removeFirst (LinkedList* _this) {
    Node* head = _this->head;
    Node* next;
    int item;
    // list is empty
    if (head == NULL) {
        printf("LinkedList#_removeFirst: The list is empty.");
        system("PAUSE");
        exit(0);
    }
    item = head->item;
    next = head->next;
    _this->head = next;
    if (next != NULL) // has next item
        next->prev = NULL;
    free(head);
    _this->size--;
    if (_this->size <= 1) // empty or only head node
        _this->tail = NULL;
    return item;
}
/** get and remove item from tail
 */
int _removeLast (LinkedList* _this) {
    // list is empty
    if (_this->size == 0) {
        printf("LinkedList#_removeLast: The list is empty.");
        system("PAUSE");
        exit(0);
    }
    if (_this->size == 1) { // only head node
        return _this->removeFirst(_this);
    } else {
        Node* tail = _this->tail;
        Node* prev = tail->prev;
        int item = tail->item;
        prev->next = NULL;
        if (_this->size > 1)
            _this->tail = prev;
        _this->size--;
        if (_this->size <= 1) // empty or only head node
            _this->tail = NULL;
        return item;
    }
}
/** display the items in the list
 */
void display (LinkedList* _this) {
     int i, size = _this->size;
     if (size == 0)
        printf("no item\n\n");
     else {
        printf("has %d items\n", size);
        Node* node = _this->head;
        for (i = 0; i < size; i++) {
            if (i > 0)
                printf(", ");
            printf("%d", node->item);
            node = node->next;
        }
        printf("\n\n");
    }
}
/** create a LinkedList
 */
LinkedList createLinkedList () {
    LinkedList list;
    list.head = NULL;
    list.tail = NULL;
    list.add = &add;
    list.addFirst = &addFirst;
    list.addLast = &addLast;
    list.insertBefore = &insertBefore;
    list.get = &get;
    list.getFirst = &getFirst;
    list.getLast = &getLast;
    list.remove = &_remove;
    list.removeFirst = &_removeFirst;
    list.removeLast = &_removeLast;
    list.display = &display;
    list.createNode = &createNode;
    return list;
}
/** create a Node
 */
Node* createNode (int item) {
    Node* node = (Node*) malloc (sizeof(Node));
    node->item = item;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

The Result



Download
The file is available at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_DataStructure/LinkedLsit.c

Reference
http://en.wikipedia.org/wiki/LinkedList

Sunday, April 1, 2012

Simple Queue Data Structure in ANSI C

Introduction

This post is about how to implement a queue in c, can push item to tail, pop item from head, peek item without delete from head, display all items and get its size.

The program

Queue.c


#include <stdio.h>
#include <stdlib.h>
/**
  * This sample is about how to implement a queue in c
  *
  * Type of item is int
  * Add item to tail
  * Get item from head
  * Can get the size
  * Can display all content
  */
/**
 * The Node struct,
 * contains item and the pointer that point to next node.
 */
typedef struct Node {
    int item;
    struct Node* next;
} Node;
/**
 * The Queue struct, contains the pointers that
 * point to first node and last node, the size of the Queue,
 * and the function pointers.
 */
typedef struct Queue {
    Node* head;
    Node* tail;

    void (*push) (struct Queue*, int); // add item to tail
    // get item from head and remove it from queue
    int (*pop) (struct Queue*);
    // get item from head but keep it in queue
    int (*peek) (struct Queue*);
    // display all element in queue
    void (*display) (struct Queue*);
    // size of this queue
    int size;
} Queue;
/**
 * Push an item into queue, if this is the first item,
 * both queue->head and queue->tail will point to it,
 * otherwise the oldtail->next and tail will point to it.
 */
void push (Queue* queue, int item);
/**
 * Return and remove the first item.
 */
int pop (Queue* queue);
/**
 * Return but not remove the first item.
 */
int peek (Queue* queue);
/**
 * Show all items in queue.
 */
void display (Queue* queue);
/**
 * Create and initiate a Queue
 */
Queue createQueue ();
int main () {
    Queue queue = createQueue();
    queue.display(&queue);

    printf("push item 2\n");
    queue.push(&queue, 2);    
    printf("push item 3\n");
    queue.push(&queue, 3);
    printf("push item 6\n");
    queue.push(&queue, 6);

    queue.display(&queue);

    printf("peek item %d\n", queue.peek(&queue));
    queue.display(&queue);

    printf("pop item %d\n", queue.pop(&queue));
    printf("pop item %d\n", queue.pop(&queue));
    queue.display(&queue);

    printf("pop item %d\n", queue.pop(&queue));
    queue.display(&queue);
    printf("push item 6\n");
    queue.push(&queue, 6);

    queue.display(&queue);
    system("PAUSE");
}

/**
 * Push an item into queue, if this is the first item,
 * both queue->head and queue->tail will point to it,
 * otherwise the oldtail->next and tail will point to it.
 */
void push (Queue* queue, int item) {
    // Create a new node
    Node* n = (Node*) malloc (sizeof(Node));
    n->item = item;
    n->next = NULL;

    if (queue->head == NULL) { // no head
        queue->head = n;
    } else{
        queue->tail->next = n;
    }
    queue->tail = n;
    queue->size++;
}
/**
 * Return and remove the first item.
 */
int pop (Queue* queue) {
    // get the first item
    Node* head = queue->head;
    int item = head->item;
    // move head pointer to next node, decrease size
    queue->head = head->next;
    queue->size--;
    // free the memory of original head
    free(head);
    return item;
}
/**
 * Return but not remove the first item.
 */
int peek (Queue* queue) {
    Node* head = queue->head;
    return head->item;
}
/**
 * Show all items in queue.
 */
void display (Queue* queue) {
    printf("\nDisplay: ");
    // no item
    if (queue->size == 0)
        printf("No item in queue.\n");
    else { // has item(s)
        Node* head = queue->head;
        int i, size = queue->size;
        printf("%d item(s):\n", queue->size);
        for (i = 0; i < size; i++) {
            if (i > 0)
                printf(", ");
            printf("%d", head->item);
            head = head->next;
        }
    }
    printf("\n\n");
}
/**
 * Create and initiate a Queue
 */
Queue createQueue () {
    Queue queue;
    queue.size = 0;
    queue.head = NULL;
    queue.tail = NULL;
    queue.push = &push;
    queue.pop = &pop;
    queue.peek = &peek;
    queue.display = &display;
    return queue;
}

The result



Download
The file is available at github
https://github.com/benbai123/C_Cplusplus_Practice/blob/master/C_DataStructure/Queue.c

Reference
http://en.wikipedia.org/wiki/Queue_(data_structure)

Sunday, March 4, 2012

C/C++ Practice: Struct Practice Two, Copy Struct.

Introduction:

This post practice two types of struct copy, Shallow Copy and Deep Copy, in C.

Shallow copy:
copy all member field values, the copied pointer and
the original pointer will point to the same address.

Deep copy:
copy the field values that are not pointer,
create new pointer for pointer value,
and copy the real content from old address to new address.

A simple sample:

#include <stdio.h>
#include <stdlib.h>
/**
  * This sample practice the shallow copy and
  * deep copy of struct in c.
  *
  * Shallow copy:
  *          copy all member field values, the copied pointer and
  *          the original pointer will point to the same address
  * Deep copy:
  *           copy the field values that are not pointer,
  *           create new pointer for pointer value,
  *           and copy the real content from old address to new address.
  */
typedef struct DataStruct {
        int data_one;
        int* data_two;
} DataStruct;
void deepCopy(DataStruct* to, DataStruct* from);
int main () {
    DataStruct dsOne;
    DataStruct dsTwo;
    DataStruct dsThree;

    int data_two = 2;
    // assign the datas to mainsOne
    dsOne.data_one = 1;
    dsOne.data_two = &data_two;

    // shallow copy dsOne to dsTwo
    memcpy(&dsTwo, &dsOne, sizeof(DataStruct));
    // deep copy dsOne to dsThree
    deepCopy(&dsThree, &dsOne);
    // show the value of original data
    printf("original data_one is %d,\noriginal data_two is %d\n\n", dsOne.data_one, *dsOne.data_two);

    // change the data of dsOne
    dsOne.data_one = 3;
    *dsOne.data_two = 4;

    // show the data of dsTwo after dsOne changed
    // actually dsOne.data_two and dsTwo.data_two
    // point to the same address, so the value of
    // *dsTwo->data_two is changed
    printf("data_one in dsTwo is %d,\ndata_two in dsTwo is %d\n\n", dsTwo.data_one, *dsTwo.data_two);
    // show the data of dsThree after dsOne changed
    // the address that dsThree.data_two points to and
    // the address of dsOne.data_two are not the same,
    // so *dsThree.data_two keep the original value.
    printf("data_one in dsThree is %d,\ndata_two in dsThree is %d\n\n", dsThree.data_one, *dsThree.data_two);

    system("PAUSE");
}

void deepCopy(DataStruct* to, DataStruct* from) {
     to->data_one = from->data_one;
     // copy the real value to the address
     // that to->data_two points to
     memcpy(to->data_two, from->data_two, sizeof(int));
}

Result:



Download:
struct_practice_002__copy_struct.c at github:
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Struct

Reference:
http://www.learncpp.com/cpp-tutorial/912-shallow-vs-deep-copying/

Sunday, February 12, 2012

C/C++ Practice: Struct Practice One, Define Data Structure

This is the first practice of C/C++ Struct:

Practice use struct and union to define a 'data' struct that can contains different type of data

Assume we have a code fragment as below:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/** This is the first practice of struct
  * Practice use struct and union to define a 'data' struct
  * that can contains different type of data
  */

// declare a struct that contains
// only a float variable
// define its type as 'first'
typedef struct first {
        float floatData;
} first;
// declare a struct that contains
// an int variable and a char variable
// define its type as 'second'
typedef struct second {
        int intData;
        char charData;
} second;
// declara a struct that contains
// an int variable thet denotes the data type,
// and an union that will be one of the two data type declared above,
// define its type as 'data'
typedef struct data {
        int type;
        union {
              first firstTypeData;
              second secondTypeData;
        };
} data;
// showData function declaration
void showData (data d);
int main () {
    data dataOne;
    data dataTwo;
    first firstData;
    second secondData;

    // set the type of dataOne
    // set the value of firstData
    // assign firstData to dataOne
    dataOne.type = 1; // first type
    firstData.floatData = 1.2;
    dataOne.firstTypeData = firstData;

    // set the type of data two
    // set the values of secondData
    // assign secondData to dataTwo
    dataTwo.type = 2; // second type
    secondData.intData = 3;
    secondData.charData = 'd';
    dataTwo.secondTypeData = secondData;

    // call showData to show the value(s) of dataOne and dataTwo
    showData(dataOne);
    showData(dataTwo);
    system("PAUSE");
}
void showData (data d) {

     switch (d.type) { // check data type by data.type
            case 1: // first type
                 printf ("float data = %.2f \n\n", d.firstTypeData.floatData);
                 break;
            case 2: // second type
                 printf ("int data = %d\nchar data = %c\n\n", d.secondTypeData.intData, d.secondTypeData.charData);
                 break;
     }
}

The result will be:



Download:
The file struct_practice_001.c of this practice is available at github
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Struct

Reference:
http://www.cplusplus.com/doc/tutorial/structures/
http://www.cplusplus.com/doc/tutorial/other_data_types/

Saturday, February 11, 2012

C/C++ Practice: Pointer Practice Four, The Function Pointer

This is the fourth practice of C/C++ pointer:

Practice the Function Pointer.

Assume we have a code fragment as below:


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <conio.h>

/** This is the fourth C/C++ Pointer Practice
  * Practice the Function Pointer
  * store the function and the related key code in a struct
  * execute function based on the input
  */

// declare a structure contains
// function pointer: int (*fp) (int, int);
// key: char, will be '+', '-', '*' or '/'
typedef struct op {
    int (*calc) (int, int);
    char key;
} op;

// the function that do the Plus operation
int doPlus (int a, int b) {
     return a+b;
}
// the function that do the Subtract operation
int doSubtract (int a, int b) {
     return a-b;
}
// the function that do the Multiple operation
int doMultiple (int a, int b) {
     return a*b;
}
// the function that do the Divide operation
int doDivide (int a, int b) {
     return a/b;
}

int main () {
    char ch;
    bool finish = true;
    int i;
    // declare an array of the strcuture op,
    // set the function pointer of operation
    // and the proper key char to it.
    op opList[] = {
         &doPlus, '+',
         &doSubtract, '-',
         &doMultiple, '*',
         &doDivide, '/'
    };

    // an infinite loop
    // will output the value
    // 10 + 2, 10 - 2, 10 * 2 or 10 / 2
    // with respect to the input key +, -, * or /
    for (;;) {
        printf("please enter '+', '-', '*' or '/' \nto calculate 10(op)2, or others to exit\n\n");
        ch = getch();
        for (i = 0; i < sizeof(opList)/sizeof(op); i++) {
            if (opList[i].key == ch) {
               // the opList[i].calc is the function to execute
               printf("10 %c 2 = %d\n", ch, opList[i].calc(10, 2));
               finish = false;
            }
        }
        if (finish)
           break;
        finish = true;
    }
    system("PAUSE");
}

The result will be:




Download:
The file pointer_practice_004.c of this practice is available at github
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Pointer

Reference:
http://www.cplusplus.com/doc/tutorial/pointers/
http://www.newty.de/fpt/index.html