彈吉他寫C++: 2月 2014

2014年2月26日星期三

Rotate an square image by 90 degrees in place

Main idea:

There is a relation between the locations of exchanged

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

after rotation

13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

(i, j) -> (j, n-1-i) -> (n-1-i, n-1-j) -> (n-1-j, i) -> (i, j)

Swapping partial image is enough
Carefully handle the size of image

1   2   3 4
5 6 7   8
9  10 11 12
13 14 15 16

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

C++ code :

#include <iostream>
using namespace std;

class Mat{
public:
    Mat( const int *a, const int size );
    ~Mat();
    void showElement() const;
    void rotate( );
private:
    int **m_image;
    int m_size;
};

Mat::Mat( const int *a, const int size ) : m_image(NULL), m_size(size)
{
    if( m_size <= 0 )   return;
    m_image = new int*[m_size]( );
    for( int i = 0 ; i < m_size ; i++ )
        m_image[i] = new int[m_size]( );

    // assign array value to member variable
    for( int i = 0, p = 0 ; i < m_size ; i++ )
        for( int j = 0 ; j < m_size ; j++ )
            m_image[i][j] = a[p++];

}
Mat::~Mat(){
    if(m_image){
        for( int i = 0 ; i < m_size ; i++ )
            delete [] m_image[i];
        delete [] m_image;
    }
}

void Mat::showElement() const{
    for( int i = 0 ; i < m_size ; i++ ){
        for ( int j = 0 ; j < m_size ; j++ )
            cout << m_image[i][j] << " ";
        cout << endl;
    }
}

void Mat::rotate( ){
    const int final_row = (m_size - 1) / 2;
    const int final_col = (m_size % 2) ? (final_row - 1) : final_row;
    const int final_index = m_size - 1;

    // (i, j) -> (j, final_index-i) -> (final_index-i, final_index-j)
    //  -> (final_index-j, i) -> (i, j)

    for( int i = 0 ; i <= final_row ; i++ ){
        for( int j = 0 ; j <= final_col ; j++ )
        {
            int temp = m_image[final_index-j][i];
            m_image[final_index-j][i] = m_image[final_index-i][final_index-j];
            m_image[final_index-i][final_index-j] = m_image[j][final_index-i];
            m_image[j][final_index-i] = m_image[i][j];
            m_image[i][j] = temp;
        }
    }
}
int main( ){
    const int SIZE = 4;
    int image[SIZE * SIZE] = {1, 2, 3, 4,
                             5, 6, 7, 8,
                             9, 10,11,12,
                             13,14,15,16};
    Mat mat( image, SIZE );

    mat.showElement( );
    mat.rotate( );

    cout << endl;
    mat.showElement( );


    cout << endl;
    const int SIZE2 = 5;
    int image2[SIZE2 * SIZE2] = {1, 2, 3, 4, 5,
                             6, 7, 8, 9, 10,
                             11, 12, 13, 14, 15,
                             16, 17, 18, 19, 20,
                             21, 22, 23, 24, 25};
    Mat mat2( image2, SIZE2 );

    mat2.showElement( );
    mat2.rotate( );

    cout << endl;
    mat2.showElement( );

    return 0;
}

2014年2月25日星期二

初始化動態配置陣列元素值為0

#include <iostream>
using namespace std;

int main(){
    int *a = new int[5];
    int *b = new int[5]();

    int *p = a;
    int *q = a + 5;

    int *r = b;
    int *s = b + 5;

    while( p != q )
        cout << *(p++) << " ";
    cout << endl;

    while( r != s )
        cout << *(r++) << " ";
    cout << endl;

    int c[5];
    static int d[5];
    p = c;
    q = c + 5;

    r = d;
    s = d + 5;
    while( p != q )
        cout << *(p++) << " ";
    cout << endl;

    while( r != s )
        cout << *(r++) << " ";
    cout << endl;

    return 0;
}

Output:

-1819044973 -1819044973 -1819044973 -1819044973 -1819044973 
0 0 0 0 0 
-1081662640 -16121856 -1081662696 134538581 134538432 
0 0 0 0 0

int *b = new int[5]();

只需在後面加上"( )"即可將動態配置的陣列之元素值初始為0, 另外, 因為在此scope的陣列a並非static or extern, 所以並不會自動初始化值為0 (初值為garbage)

int c[5];
static int d[5];

c之初值為garbage, d是static, 會自動初始化其元素值為0

Note:

*(p++)

等同於

*p++

因為++的優先權比*高

Array to vector

#include <iostream>
#include <vector>
using namespace std;

int main(){
    const  int size_array = 4;
    int a[size_array] = {1,2,3,4};
    int *p = a;
    int *q = a + size_array;

    int *c = p;
    while( c != q ){
        cout << *c << " ";
        c++;
    }
    cout << endl;

    vector<int> vec(p, q);
    vector<int>::iterator i = vec.begin( );
    while( i != vec.end() )
    {
        cout << *(i++) << " ";
    }
    cout << endl;

    vector<int> vec2;
    vec2.assign(p, q);
    i = vec2.begin( );
    while( i != vec2.end() )
    {
        cout << *(i++) << " ";
    }

    return 0;
}

int *q = a + size_array;

This is an off-the-end pointer

vector<int> vec(p, q);

Create a vector and use an array to initialize the elements by passing the begin pointer and off-the-end pointer

vector<int> vec2;
vec2.assign(p, q);

Create an empty vector, then using the assign function to assign the elements in an array to it

( Note: if the assign function is used, then the old contents will be wiped out, and replaced by the new contents, meanwhile, the size will be changed )

2014年2月24日星期一

Bubble sort a singly linked list

對一個 singly linked list 做 bubble sort

Method 1 :

void LinkedList::BubbleSortVer1( ){
    if( !head ) return;
    bool change = true;
    while( change ){ //round
        Node *prev = NULL;
        Node *current = head;
        change = false;
        while( current->next != NULL ){
            if( current->value > current->next->value ){
                current = swap(current, current->next);
                change = true;
                if( prev != NULL )
                    // swap is unrelated to head, update prev' s next link
                    prev->next = current;
                else
                    // swap is related to head, change head pointer
                    head = current;
            }
            prev = current;
            current = current->next;
        }
    }
}

Node* LinkedList::swap( Node* p, Node* q){
    Node *temp = q->next;
    q->next = p;
    p->next = temp;
    return q;
}

Main idea:

藉由兩兩swap把最大的丟到最後面
利用一個change flag 來判斷sorting完成否 (可以省略計算目前是第幾round)
獨立的Swap function: 另外提出來做Node的Swap, 回傳Swap後, 前面的node, 如此可以讓iteration繼續下去
利用兩個pointer, 一個是當前指標current, 一個是current的前一個node的指標prev
比較當前node與下一個node的值, 來決定要不要swap
注意head的位置會跑掉, 必須在swap判斷時, 判斷prev的位置; 如果prev的位置是在NULL, 表示目前current是head, 必須更新head, 否則更新prev的next連結位置
前進prev和current

Method 2:

void LinkedList::BubbleSortVer2( ){
    if( !head ) return;
    bool change = true;
    Node *prevHead = new Node(0, head);
    while( change ){
        change = false;
        Node *prev = prevHead;
        Node *current = prev->next;
        while( current->next != NULL ){
            if( current->value > current->next->value ){
                prev->next = current = swap(current, current->next);
                change = true;
            }
            prev = current;
            current = current->next;
        }
    }
    head = prevHead->next;
    delete prevHead;
}

Node* LinkedList::swap( Node* p, Node* q){
    Node *temp = q->next;
    q->next = p;
    p->next = temp;
    return q;
}

Main idea:

與作法1大致相同, 只差在此方法另外開一個新的dummy node去只向head, 此時, 可以在每次swap後, 都更新前一個node的next, 不用擔心前一個是NULL
與作法1相比, 差了一個if的判斷式, 判別前一個node是不是非空, 來決定要不要更新前一個node的next, 或者是更新head

C++ code:

#include <iostream>
using namespace std;

class Node{
public:
    Node() : value(0), next(NULL) {}
    Node( int theValue, Node *theNext ) : value(theValue), next(theNext){}
    int value;
    Node *next;
};

class LinkedList{
public:
    LinkedList( );
    ~LinkedList( );
    void push_front( int value );
    void push_back( int value );
    void delete_front( );
    void show_element( );

    void BubbleSortVer1( );
    void BubbleSortVer2( );
private:
    Node* head;

    Node* swap( Node*, Node* );
};

LinkedList::LinkedList( ) : head(NULL){

}
LinkedList::~LinkedList( ){
    if( head )
        delete_front( );
}

void LinkedList::push_front( int value ){
    Node *newNode = new Node(value, head);
    head = newNode;
}

void LinkedList::push_back( int value ){
    if( !head )
        push_front( value );
    else{
        Node *current = head;
        while( current->next != NULL )
            current = current->next;
        Node *newNode = new Node(value, NULL);
        current->next = newNode;
    }
}

void LinkedList::delete_front( ){
    if( !head )
        return;
    Node *deleteNode = head;
    head = head->next;
    delete deleteNode;
}

void LinkedList::show_element( ){
    Node *current = head;
    while( current ){
        cout << current->value << " ";
        current = current->next;
    }
    cout << endl;
}

void LinkedList::BubbleSortVer1( ){
    if( !head ) return;
    bool change = true;
    while( change ){ //round
        Node *prev = NULL;
        Node *current = head;
        change = false;
        while( current->next != NULL ){
            if( current->value > current->next->value ){
                current = swap(current, current->next);
                change = true;
                if( prev != NULL )
                    // swap is unrelated to head, update prev' s next link
                    prev->next = current;
                else
                    // swap is related to head, change head pointer
                    head = current;
            }
            prev = current;
            current = current->next;
        }
        show_element( );
    }
}

void LinkedList::BubbleSortVer2( ){
    if( !head ) return;
    bool change = true;
    Node *prevHead = new Node(0, head);
    while( change ){
        change = false;
        Node *prev = prevHead;
        Node *current = prev->next;
        while( current->next != NULL ){
            if( current->value > current->next->value ){
                prev->next = current = swap(current, current->next);
                change = true;
            }
            prev = current;
            current = current->next;
        }
    }
    head = prevHead->next;
    delete prevHead;
}

Node* LinkedList::swap( Node* p, Node* q){
    Node *temp = q->next;
    q->next = p;
    p->next = temp;
    return q;
}
int main( ){
    LinkedList list;
    list.push_back( 4 );
    list.push_back( 7 );
    list.push_back( 5 );
    list.push_back( 1 );
    list.push_back( 3 );
    list.push_back( 2 );
    list.push_front( 6 );
    list.push_front( 0 );
    list.show_element( );

    list.delete_front( );
    list.show_element( );

    cout << "sorting list1: \n";
    list.BubbleSortVer2( );
    cout << "After sort: ";
    list.show_element( );

    LinkedList list2;
    list2.push_back( 1 );
    list2.push_back( 2 );
    list2.push_back( 3 );
    list2.push_back( 4 );
    list2.push_back( 5 );
    list2.push_back( 7 );
    list2.push_back( 6 );

    cout << "\nsorting list2: \n";
    list2.BubbleSortVer2( );
    cout << "After sort: ";
    list2.show_element( );
    return 0;
}

結論：

bubble sort將大的往後swap到底端
swap node另外實做一個函數, 回傳swap後前面的node, 非常重要且省事!
round數不需要計算node總個數, 利用change flag來觀察是否已經完成sorting
Maintain 兩個指標, previous及current, 其中previous是要用來更新swap後的鏈結方式, current是用來判斷pari間的大小關係

Reference:

http://www.sal.ksu.edu/faculty/tim/CMST302/study_guide/topic7/bubble.html

2014年2月26日 星期三

Rotate an square image by 90 degrees in place

2014年2月25日 星期二

初始化動態配置陣列元素值為0

Array to vector

2014年2月24日 星期一

Bubble sort a singly linked list

2014年2月26日星期三

2014年2月25日星期二

2014年2月24日星期一