網頁

2016年11月18日 星期五

Optimal binary search tree

Application: We could perform translating text from English to French with n English words as keys and their French equivalents as satellite data  by building binary search tree.

Goal: How to organize a binary search tree so as to minimize the number of nodes visited in all searches.

The feature of optimal binary search tree:
1. the overall height is not necessarily smallest
2. greatest search probability of any key isn't put at the root

solve dynamic programming:

step1: The structure of an optimal binary search tree
 
1. if an optimal binary search tree T has a subtree T', then T' must be optimal as well
2. select kr (i <= r <= j) as the root, the left subtree contains the keys ki, ..., kr-1 (and dummy keys di-1, ..., dr-1) and
3.

step 2: A recursive solution


2016年11月17日 星期四

Introduction to C++ Standard Library Class Template vector

Creating vector Objects

By default, all elements of each vector object are set to 0.

ex.
  vector< int > integer1( 7 );

vector Member Function size; Function outputVector

every container except forward_List

ex.
  cout << "Size of vector integers1 is " << integer1.size()
    << "\nvector after initialization:" << endl;
  outputVector( integers1 );

Function outputVector

ex.
 inputVector( integers1 );

Comparing vector Objects for Inequality

ex.
if ( integers1 != integers2 )
  cout << "integers1 and integers2 are not equal " << endl;

Initializing One vector with Contents of Another

ex.
vector< int > integers3( integers1 );

Assigning vectors and comparing vectors for Equality

ex.
integers1 = integers2
integers1 == integers2

Using the [] Operator to Access and Modify vector Elements

Standard class template vector provides bounds checking in its member function at()

ex.
cout << "\nintegers1[5] is " << integers1[ 5 ] = 1000;
cout << integers1.at( 15 ) << endl;

Changing the Size of a vector

other than array and forward_list

integers3.push_back( 1000 );

vector Member Function capacity

specific to vector and deque

ex.

cout << "\nThe initial capacity of integers is: " << integers.capacity();

Outputting vector Contents with Iterators

ex.
1. C++11

for ( auto constIterator = integers2.cbegin(); constIterator != integers2.cend(); ++constIterator  )
  cout << *constIterator << ' ';

could have been replace with the following range-based for statement:

for ( auto const &item : integers2 )
  cout << item << '';

2. prior to C+11

vector<int>::const_iterator

Displaying the vector's Content in Reverse with const_reverse_iterators

for ( auto reverseIterator = integers2.crbegin(); reverseIterator != integers2.crend(); ++reverseIterator  )
  cout << *reverseIterator << ' ';

C++11: shrink_to_fit

std::vector<int> myvector (100); 
  cout << "1. capacity of myvector: " << myvector.capacity() << '\n'; 
myvector.resize(10); 
  cout << "2. capacity of myvector: " << myvector.capacity() << '\n'; 
myvector.shrink_to_fit()
  cout << "3. capacity of myvector: " << myvector.capacity() << '\n';

vector Element-Manipulation Functions

vector< int > integers{ 1, 2, 3, 4, 5, 6 };
or
vector< int > integers = {1, 2, 3, 4, 5, 6 };

using an overloaded vector constructor that takes two as arguments to initialize integers

array< int, SIZE > value = { 1, 2, 3, 4, 5, 6 }
vector< int > integers( value.cbegin(), values.cend() );














Class Templates array

Introduction 

data structure-collection: array and vector
1. array: fix-size collection and same type
2. vector: collections grow and shrink dynamically and  same type

Declaring

array< type, arraySize > arrayName;

1. arraySize must be  an unsigned integer
2. type string can be used

advantage: bound check for array subscripts

ex.
array< int, 5 > n;
for ( size_t i = 0; i < n.size(); ++i )
  n[ i ] = 0;

size_t (unsigned integral type): 在32位元系統中size_t是4位元組的,而在64位元系統中,size_t是8位元組的。C++ head file <cstddef>、C head file <stddef.h> 。

application: 增強程式的可攜性。

Initializing

ex.
array< int, 5 > n = {};
array< int, 5 > n = { 1, 2, 3, 4, 5 };

Constant variable

ex.
const size_t arraySize = 5; // must initialize in declaration
array< int, arraySize > s;

Summing the Element of an array

ex.
for ( size_t i = 0; i < a.size(); ++i )
  tatal += a[ i ];

Using Bar Charts to Display array Data Graphically

ex.
array< unsigned int, arraySize > n={ 0, 0, 0, 0, 0, 0, 1, 2, 4, 2, 1 }

for ( size_t i = 0; i < n.size(); ++i )
  for ( unsigned int stars = 0; stars < n.size(); ++stars )
    cout << '*' ;

Using the Elements of an array as Counters

default_random_engine engine( static_cast< unsigned int >( time(0) ) );
uniform_int_distribution< unsigned int  > randomInt( 1,6 );

const size_t arraySize = 7;
array < unsigned int, arraySize > frequency = {};

for ( unsigned int roll <= 6000000; ++roll )
  ++frequency[ randomInt( engine )];

Using arrays to Summarize Survey Results

const size_t responseSize = 10;
const size_t frequencySize = 6;

const array< unsigned int, responseSize > responses = { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 };
array < unsigned int, frequencySize > frequency = {};

for ( size_t answer =0; answer < responses.size; ++answer )
  ++frequency[ responses[ answer ] ];

Static Local arrays and Automatic Local arrays

1. The static local array is initialized to zero by the compiler the first time the function is called.
2. The second time the function is called, the static array contains the modified values stored during the first function call

ex.
static array< int, arraySize > array1;

Range-Based for Statement

1.for ( rangeVariableDeclaration : expression )
  statement

2. int reference (&) can change the corresponding element value in the array

ex.
array< int, 5 > items = { 1, 2, 3, 4, 5 };
for (int item : items)

array< int, 5 > items = { 1, 2, 3, 4, 5 };
for (int &itemRef : items)
  itemRef * = 2;

Sorting and Searching arrays

ex.
1. Standard library class templates

array < string, arraySize > colors = { "red", "orange", "yellow", "green", "blue", "indigo" }

sort( colors.begin(), colors.end() ); // sort contents of colors

bool found = binary_search( colors.begin(), colors.end(), "indigo" );
  cout << "\n\n\"indigo\" << ( found ? "was" : "was not" ) << " found in colors" << endl;
found = binary_search( colors.begin(), colors.end(), "cyan" );
  cout << "\n\n\"cyan\" << ( found ? "was" : "was not" ) << " found in colors" << endl;

2. Built-in Arrays

#include< iterator >

int n[5] = { 50, 20, 30, 10, 40 };

sort( begin( n ), end( n ) ); // sort contents of built-in array n ( type arrayName[ arraySize ] )

Multidimension arrays

ex.
array< array< int, columns >, rows > array1 = { 1, 2, 3, 4, 5, 6 }

1. Nested Range-Based for Statements

void printArray( const array< array< int, columns >, rows > & a )
{
  for ( auto const &row : a )
  {
     for ( auto const &element : row )
    {
       cout << element << ';
     cout << endl;
    }
  }
}

2. Nest Counter-Controlled for statements

for ( size_t row = 0; row < a.size(); ++row )
{
  for ( size_t column = 0; column < a[row].size(); ++column )
    cout << a[ row ][ column ] << ' ';
  cout << endl;
}

3. Other Common array Manipulations

for ( size_t row = 0; row < a.size(); ++row )
  for ( size_t column = 0; column < a[row].size(); ++column )
    total += a[ row ][[ column ];

for ( auto row : a )
  for ( auto column : row )
    total += column;

Outputting Built-in Array Contents with Pointers

ex.

#include< iterator >

int value[ SIZE ] = { 1, 2, 3, 4, 5, 6 }

for ( const int *ptr = begin( values ); ptr != end( values ); ++ptr )
  cout << *ptr << ' ';


2016年11月14日 星期一

Template part6

#include <iostream>
using namespace std;

template <class Type> class MyClass{
Type p1;

public:
    MyClass(Type p){
        cout << "from the generic class conbstructor"<<endl;
    p1 = p;

    }
    void whatYouGot(){
    cout << p1<<endl;
    }
};

template <> class MyClass <int>{
int p1;
public:

    MyClass(int p){
    p1 = p;
     cout << "from the specific integer version class conbstructor"<<endl;
    }
    void whatYouGot(){
    cout << p1<<endl;
    }
};

int main()
{
    MyClass <string> ob1("anil");
    MyClass <int> ob2(22);
    ob1.whatYouGot();
    ob2.whatYouGot();
    return 0;
}

Template part5

#include <iostream>
using namespace std;

template <class Type1 = string, class Type2 = int >class MyClass{

Type1 p1;
Type2 p2;

public:
    MyClass(Type1 x, Type2 y){
    p1 = x;
    p2 = y;
    }
    void whatYouGot(){
    cout << "i got "<<p1<<" and "<<p2<<endl;
    }
};

int main()
{
    MyClass <> ob1("anil",24);
    MyClass <float> ob2(22.36,55);
    MyClass <int,string> ob3(21,"anjali");
    ob1.whatYouGot();
    ob2.whatYouGot();
    ob3.whatYouGot();
    return 0;
}


#include <iostream>
using namespace std;

template <class Type1 , class Type2 = int >class MyClass{

Type1 p1;
Type2 p2;

public:
    MyClass(Type1 x, Type2 y){
    p1 = x;
    p2 = y;
    }
    void whatYouGot(){
    cout << "i got "<<p1<<" and "<<p2<<endl;
    }
};

int main()
{
    MyClass <string> ob1("anil",24);
    MyClass <float> ob2(22.36,55);
    MyClass <int,string> ob3(21,"anjali");
    ob1.whatYouGot();
    ob2.whatYouGot();
    ob3.whatYouGot();
    return 0;
}

Template part4

#include <iostream>
using namespace std;

template <class Type1, class Type2> class MyClass{
Type1 p1;
Type2 p2;
int counter;

public:
    MyClass(Type1 x, Type2 y){
    p1 = x;
    p2 = y;
    counter = 100;
    }

    void whatYouGot(){
    cout << "i got p1 = "<<p1<<" and p2 = "<<p2<<" and counter is "<<counter<<endl;
    }
};

int main()
{
    MyClass <int,string> ob1(24,"anil");
    MyClass <float,float> ob2(22.36,66.241);
    ob1.whatYouGot();
    ob2.whatYouGot();
    return 0;
}

Template part3

#include <iostream>
using namespace std;

template <class MYTYPE> class MyClass{
MYTYPE p1;
MYTYPE p2;

public:
    MyClass(MYTYPE x, MYTYPE y){
    p1 = x;
    p2 = y;
    }
    void whatYouGot(){
    cout << "i got p1 = " << p1 <<" and p2 = "<< p2 <<endl;
    }
};

int main()
{
    MyClass<int> intObject(22,55);
    MyClass <string> stringObj("anil","anjali");
    intObject.whatYouGot();
    stringObj.whatYouGot();
    return 0;
}

Template part2

Explicitly Overloading Generic Functions with Normal Functions

#include <iostream>
using namespace std;
template <typename T> void whatYouGot (T x);
template <> void whatYouGot<int> (int x);
void whatYouGot (int x); //normal function
template <> void whatYouGot <int> (int x); //normal function進階
template <typename T> void whatYouGot (T x);

int main()
{
    whatYouGot (22.546); //generic function
    whatYouGot (23); //normal function and explicitly overloading generic function
    whatYouGot ("anil shetty"); //generic function
    return 0;
}

template <typename T> void whatYouGot (T x)
{
    cout << "inside whatYouGot generic function" << endl;
}

void whatYouGot (int x)
{
    cout << "inside whatYouGot normal function" << endl;
}

template <> void whatYouGot<int> (int x)
{
    cout << "inside whatYouGot explicitly overloading generic function" << endl;
}

Pointer

指標和指位運算子: 指標是變數存放記憶體位址。指位運算子(*)在宣告時表示變數為指標變數,在一般statement中代表傳回變數指標的值

應用: sizeof(ptr) 所得到的是該指標本身的大小,而 sizeof (*ptr) 所得到的是,指標指向的記憶體區塊之第一個 item 之型態大小。

char array[1024];

sizeof(array) 為 1024 個 char 的大小,
sizeof(*array) 為一個 char 的大小 
( *array 會被 compiler 視為 *(array+0),等同於 array[0],代表 array 中的第一個 item 的 size)

指標陣列: 構成陣列的元素都是指標

char *p[3];
p[0] = "abc";
p[1] = "12345";
p[2] = "xy";

應用: 陣列可以儲存"字串"。

陣列指標:宣告指標指向具有4個element一維陣列的記憶體空間,也就是二維陣列

char (*str)[4] (char [][4])

應用: 只要知道"字元"的存放位置,就可以找出它的element。

指標函式 (function return a pointer): 將函式宣告成指標,此函式回傳值是位址

int *func()

應用: 傳回字串或陣列(多個變數)而不再只傳回一個變數。

函式指標 (function pointer):  宣告指標指向函式的記憶體位址,此函式回傳值是一個整數型態

int (*ptr)()

應用: 可指向具有相同型態的函式,也就是具有相同傳回值型態和參數列的函式。


2016年11月13日 星期日

Templates part1

定義函式(function)或類別(class)時,可以先不指定參數、變數或者是資料成員的型別。

優點: 為了讓函式或者類別不要一直重複宣告,可以利用template去簡化code。

Complication:

#include <iostream>
using namespace std;

int max(int x, int y)
{
    return (x > y) ? x : y;
}
int max(int x, int y)
{
    return (x > y) ? x : y;
}

int main()
{
 cout << max(1.22,2.11);
    return 0;
}

Template:

#include <iostream>
using namespace std;

//define a function template not a general function
template < typename T >  void display(T, T);
template < typename T >  void display(T xint y);
template < typename T1typename T2 >  void display(T1 xT2 y);
template <class T> T maxi(T x, T y);

int main()
{
    cout << maxi(20,30) << endl;
    cout << maxi(20.56,3.897) << endl;

    display(20,30);
    display("anil","anjali");
    display(12.36,56.78);
}

template <typename T>  void display(T x, T y)
{
    cout << x << "and" << y << endl;
}

template <typename T>  void display(T x, int y)
{
    for (int i = 1; int <= y; i++){
    cout << x << endl;
    }
}

template <typename T1typename T2>  void display(T1 x, T2 y)
{
    cout << x << "and" << y << endl;
}

p.280

template < class T > T maxi(T x, T y) 
{
    return ( x >= y ) ? x : y;


}

Crontabs

sudo vi /etc/crontab

** *** toor sh /var/java/checker.sh > /tmp/test

第一欄為m,表示到幾分執行,*號為每分鐘執行

第二欄為h,表示到幾時執行

第三欄為dom,為每個月到了日期為幾號執行

第四欄為mon,為每年到了幾月執行

第五欄為dow,為每週

第六欄為user,誰執行

第七欄為 command,則執行甚麼指令