Monday, January 30, 2012

Proxy -- Hiding Implementation Details From Interface (C++)

"Separating interface from implementation and hiding implementation details"是我閱讀OOP到現在不斷提到的概念,基於一層層往上架構、每階層對上密封,只提供使用界面(interface),至於內部如何完成則加以密封,不需要也不該讓使用的人看到。

Write C++ Code in Multi-files提到把C++程式分到不同檔案,來使得implementation和interface分離,然而會發現到在interface中仍然可以看到private variables之類應該密封的程式碼,所以我們透過"Proxy Class"來近一步把該密封的東西分到不同檔案中。

我們把應該密封的東西都先寫到另一個header裡面(這裡稱Implementation.h)
Implementation.h
class Implementation{
 public:
  Implementation(int new_value)
   :value(new_value){
  }

  void setValue(int new_value){
   value = new_value;
  }

  int getValue(){
   return value;
  }

 private:
  int value;
};

然後透過"forward class declaration"的方式去連結原本的interface,即我們在原本的header(這裡稱Interface.h)中定義了Implementation的prototype,然後用pointer的方法將原本class定義中該密封的東西指向到Implementation,達到密封的效果。
Interface.h
class Implementation;//forward class declaration for Implementation.h

class Interface{
 public:
  Interface(int);
  ~Interface();
  void setValue(int);
  int getValue();
 private:
  Implementation *ptr;
};

至於Inferface.cpp中需要透過pointer指向的方式返回呼叫Implementation中密封的functions。
#include "Interface.h"
#include "Implementation.h"

Interface::Interface(int value)
 : ptr(new Implementation(value)){
}

Interface::~Interface(){
 delete ptr;
}

void Interface::setValue(int value){
 ptr->setValue(value);
}

int Interface::getValue(){
 ptr->getValue();
}

這些過程對於上一層的使用者(main)是沒有差別的。
#include <iostream>
#include "Interface.h"

using namespace std;

int main(){

 Interface a(19);

 cout << "Value >> " << a.getValue() << endl;

 a.setValue(13);

 cout << "Value >> " << a.getValue() << endl;

 return 0;
}

Output:
Value >> 19
Value >> 13

Static Members in Class

經static修飾的變數定義在Class中時,由於他的生命期是整份程式,並非單一個物件中,所以可以用來對於不同的class instance(物件)做運算,例如計算有多少個class instance:


myClass.h
class MyClass{
 public:
  //constructor
  MyClass();
  //destructor
  ~MyClass();
  //get the amount value
  static int getAmount();
 private:
  static int amount;
};

myClass.cpp
#include <iostream>
#include "myClass.h"

using namespace std;

int MyClass::amount = 0;

MyClass::MyClass(){
 amount++;
 cout << "no." << amount << " object built." << endl;
}

MyClass::~MyClass(){
 cout << "no." << amount << " object deleted." << endl;
 amount--;
}

int MyClass::getAmount(){
 return amount;
}

main.cpp
#include <iostream>
#include "myClass.h"

using namespace std;

void displayAmount();

int main(){

 if(1){
  MyClass a1;
  MyClass a2;
  displayAmount();

  MyClass b[2];
  displayAmount();
 }

 displayAmount();

 return 0;
}

void displayAmount(){
 cout << "Amount >> " << MyClass::getAmount() << endl;
}

Output
no.1 object built.
no.2 object built.
Amount >> 2
no.3 object built.
no.4 object built.
Amount >> 4
no.4 object deleted.
no.3 object deleted.
no.2 object deleted.
no.1 object deleted.
Amount >> 0

Friend Function and Friend Class

我們可以定義一個某一class相關的friend function,這個friend function定義在class的外部,卻有權限可以讀取或修改該對應class的private members。

這個函式的prototype需要寫在class裡面,且在前面加上friend的修飾詞,如:
friend void setValue( MyClass &, int );
該prototype可以放在class裡的任何一處,他與private/public無關,不會影響,但是建議放在最前面會是比較清楚的方法。

friend function有個物件的參數,所以我們才知道要針對的是哪個class instance。

myClass.h
class MyClass{
 friend void setDoctor(MyClass &, int);
 public:
  //constructor
  MyClass(int = -1);
  void displayHowManyDoctor();
 private:
  int doctor;
};

myClass.cpp
#include <iostream>
#include "myClass.h"

using namespace std;

MyClass::MyClass(int doctor){
 this->doctor = doctor;
}

void MyClass::displayHowManyDoctor(){
 cout << "The Number of Doctor is " << this->doctor << endl;
}

// friend function
void setDoctor(MyClass &myClass, int new_doctor){
 cout << "grabbing private variable >> " << myClass.doctor << endl;
 myClass.doctor = new_doctor;
}

main.cpp
#include <iostream>
#include "myClass.h"

using namespace std;

int main(){

 // define an apple instance
 MyClass apple;

 // set the doctor value by using friend function
 setDoctor(apple, 1);

 // print out
 apple.displayHowManyDoctor();

 return 0;
}

"this" (C++)

this是一個被C++保留的詞彙,即他有特殊意義,不能拿來當作變數的名字。

  • 用在:某個class裡面
  • 意義:指向自己這個物件的指標
  • 注意:他是指標,並非說該物件中又包含該物件自己的遞迴,而只是儲存自己的記憶體位置
故讀取自己class中的變數,有以下幾種方法:
  1. 直接讀取;如Class (C++)中的studentName
  2. 讀取指標內的值;如this->studentName
  3. 先讀取指標指向的物件,再找尋物件中的值;如(*this).studentName
第1種方法是最簡單的,然而在遇到以下列舉的情況時,我們必須透過第2或3的方法才能解決:
  • local variable、function argument variable通常優先權高於class variable,即有同名的local variable、function argument variable出現時,就沒辦法用該名字讀到class variable,此時,可以加寫this找尋回class variable
  • 串列寫法,如果我們需要回傳物件自己,就會需要用到return *this。
    • 串列寫法:myClass.setA(1).setB(2).setC(3)
    • setA, setB, setC需要回傳*this方可以讓下一個"."符號串起來


myClass.h
class MyClass{
 public:
  MyClass(int = -1, int = -1, int = -1);
  // Return the reference of this object
  MyClass &setA(int);
  MyClass &setB(int);
  MyClass &setC(int);
  void display();
 private:
  int a;
  int b;
  int c;
};

myClass.cpp
#include <iostream>
#include "myClass.h"

using namespace std;

// constructor
MyClass::MyClass(int new_a, int new_b, int new_c){
 a = new_a;
 b = new_b;
 c = new_c;
}

// setA
MyClass &MyClass::setA(int new_a){

 cout << "function argument new_a = " << new_a << endl;

 a = new_a;
 return *this;
}

// setB
MyClass &MyClass::setB(int b){

 cout << "function argument b = " << b << endl;
 cout << "this.b = " << this->b << endl;

 this->b = b;
 return *this;
}

// setC
MyClass &MyClass::setC(int c){

 cout << "function argument c = " << c << endl;
 cout << "this.c = " << (*this).c << endl;
 // *this.c is a wrong usage since "this.c" isn't a pointer

 (*this).c = c;
 return *this;
}

// display the member values(a, b, c)
void MyClass::display(){
 cout << "a=" << a << "\tb=" << b << "\tc" << c << endl;
}

main.cpp
#include <iostream>
#include "myClass.h"

using namespace std;

int main(){

 // create a new class instance
 MyClass myClass;

 // setup
 myClass.setA(10).setB(3).setC(2);

 // display it
 myClass.display();

 return 0;
}

Thursday, January 26, 2012

Destructor for Class

Class (C++)提過,Class在定義一個新的instance時候,會執行Constructor,而Destructor則是相反的,當一個instance要結束的時候,會執行Destructor。

Destructor結束可能是:

  • Automatic Class(定義時沒有額外加敘述者多為這個),該所屬Function(也可以是main)跑完,表示結束,會執行該Class的Destructor。
  • Static Class,當整個程式跑完,才會結束、執行Destructor。
  • Global Class,定義在任何一個Function外面,當所有函式的事情處理完之後,才被結束、執行Destructor。
Destructor定義方式與Constructor類似,為與Class名字相同的Function,但在最前方加"~"符號,不接受任何argument或是回傳值:
~Myclass();

MyClass.h
#include <string>

using namespace std;

class MyClass{
 public:
  MyClass(int new_id, string new_message);
  ~MyClass();
 private:
  int id;
  string message;
};

MyClass.cpp
#include <iostream>
#include <cstring>
#include "MyClass.h"

using namespace std;

MyClass::MyClass(int new_id, string new_message){
 id = new_id;
 message = new_message;

 cout << "Object no." << id << " constructor runs " << message << endl;
}

MyClass::~MyClass(){
 cout << "Object no." << id << " destructor runs " << message << endl;
}

Destructor.cpp
#include <iostream>
#include <cstring>
#include "MyClass.h"

using namespace std;

void create();

MyClass myclass_1( 1, "(global before main)" );

int main(){

 cout << "\nMain Function: start------" << endl;

 MyClass myclass_2( 2, "(local automatic in main)" );
 static MyClass myclass_3( 3, "(local static in main)" );

 create();

 cout << "\nMain Function: resumes----" << endl;
 MyClass myclass_4( 4, "(local automatic in main)" );
 cout << "\nMain Function: ends-------" << endl;

 return 0;
}

void create(){
 cout << "\nCreate Function: start----" << endl;

 MyClass myclass_5( 5, "(local automatic in create)" );
 static MyClass MyClass_6( 6, "(local static in create)" );
 MyClass myclass_7( 7, "(local automatic in create)" );

 cout << "\nCreate Function: ends-----" << endl;
}

Output:
Object no.1 constructor runs (global before main)

Main Function: start------
Object no.2 constructor runs (local automatic in main)
Object no.3 constructor runs (local static in main)

Create Function: start----
Object no.5 constructor runs (local automatic in create)
Object no.6 constructor runs (local static in create)
Object no.7 constructor runs (local automatic in create)

Create Function: ends-----
Object no.7 destructor runs (local automatic in create)
Object no.5 destructor runs (local automatic in create)

Main Function: resumes----
Object no.4 constructor runs (local automatic in main)

Main Function: ends-------
Object no.4 destructor runs (local automatic in main)
Object no.2 destructor runs (local automatic in main)
Object no.6 destructor runs (local static in create)
Object no.3 destructor runs (local static in main)
Object no.1 destructor runs (global before main)

Default Arguments and Copy Classes

接續Class (C++)之後,來談論Constructor的arguments預設值,假設有一個Class叫做Number,他的Constructor Prototype長這樣:
Number(int = -1, int = -1, int = -1);
當我們使用時,若給予參數:
Number num1(1, 2, 3);
Constructor得到的參數會依序為1, 2, 3;然而如果不給予參數:
Number num2;

Constructor就會讀取到預設的參數-1, -1, -1(被定義在Prototype裡面)


Function Pointer

變數有pointer,函式也有!

#include <iostream>

using namespace std;

int bigger(int, int);
int smaller(int, int);
int find(int, int, int(*)(int, int));

int main(){

 int a, b;
 cout << "a=";
 cin >> a;
 cout << "b=";
 cin >> b;

 // find the bigger one
 cout << find(a, b, bigger) << endl;

 // find the smaller one
 cout << find(a, b, smaller) << endl;

 return 0;
}

int find(int a, int b, int(*compare)(int a, int b)){
 return (*compare)(a, b);
}

int bigger(int a, int b){
 return (a>b)?a:b;
}

int smaller(int a, int b){
 return (a<b)?a:b;
}

Wednesday, January 25, 2012

Vector Template (C++)

使用C語言中的array之後,會發現有幾件常做的事情,卻是很不方便:
(假設a1, a2為兩個array)

  1. 比較兩個array是否相同
    • 不能直接a1==a2, a1!=a2
    • 應該要用for/while loop掃描一次,看看是否全部相同
  2. 複製array
    • 不能直接a1=a2
    • 應該要用for/while loop掃描一次,一個一個element複製
  3. array大小
    • 沒有快速的方法
    • 應該要用sizeof(a1)/sizeof(a1[0])
因為array的名字只是array起點的記憶體位置,所以往往不能直覺的把他當作普通變數運算。

C++中有一個新東西要作vector,是一種template,定義在<vector>標頭檔裡面。宣告方式:
vector<type> name(size);
example:
vector<int> v1(10); 
讀取裡面elements的方式和array相同,使用中括號[ ],此外,上述的三件事情他可以簡易的完成:
(假設v1, v2為vector)

  1. v1==v2, v1!=v2
  2. v1 = v2
  3. v1.size(), v2.size()
Here's a simple example:

#include <iostream>
#include <vector>

using namespace std;

int main(){

 //variables
 int i;

 //vector definition
 vector<int> v1(10);
 vector<int> v2(10);

 //input
 for(i=0 ; i<v1.size() ; i++){
  cin >> v1[i];
 }

 //output
 for(i=0 ; i<v1.size() ; i++){
  cout << v1[i] << "\t";
 }
 cout << endl;

 //copy
 v2 = v1; // copy v1 to v2
 //output v2
 for(i=0 ; i<v1.size() ; i++){
  cout << v1[i] << "\t";
 }
 cout << endl;

 //compare
 if(v1 == v2) cout << "same." << endl;
 else cout << "different." << endl;

 //do some change and compare again
 v2[0] = -1;
 if(v1 == v2) cout << "same." << endl;
 else cout << "different." << endl;

 return 0;
}

Tuesday, January 24, 2012

Few Things about Makefile

I read through this article, http://www.opussoftware.com/tutorial/TutMakefile.htm, today. And wrote down some notes.

target : sources
"The target depends on the sources."
: colon are called dependency lines.

The last-changed time is the time as it appears in the file-system directory = timestamp
if timestamp(target) is earlier than timestamp(sources) then build a new one.

include hearder
main.o : main.c def.h
io.o : io.c def.h
or
main.o io.o : def.h

Shell Lines

  • the  indented lines that follow each dependency line are called shell lines, which tell Make how to build the target.
  • Make checks the shell line exit status. If the first shell line returning a non-zero exit status, it will stop.
  • adding "-" prefix let Make ignore the exit status and continue.
Macros
  • macro definition: name = value
  • expressions form: $(name) or ${name}
  • if the name is a single letter, the parentheses or braces are optional, ex. $X
  • defining on the command line:
    • make CFLAGS=-ms
    • (including spaces) make "CFLAGS=-ms -z -p"
  • run-time macros
    • .TARGET is the name of the current target
    • .SOURCES is the name of the inferred source
  • macro modifiers
    • $(name, modifier[,modifier ...]), ex. SRCS = $(OBJS,.o=.c)
    • filename components, if PATH = /home/heron/test.txt
      • D, directory, $(PATH, D) = /home/heron
      • E, extensions, $(PATH, E) = .txt
      • F, file name, $(PATH, F) = test.txt
Conditional Directives
ex.
%if $(CC) == gcc
        CC = g++
%elif $(CC) == g++
        CC = gcc
%else
        echo "haha"
%endif


For More Info : http://unixhelp.ed.ac.uk/CGI/man-cgi?make

Saturday, January 21, 2012

變數生命期

變數又可以分為很多種,有不同的作用範圍和生命期,先分為

  • 廣域變數 Global Variable
    • 定義在所有函式的外面
  • 區域變數 Local Variable
    • 定義在某一函式裡面
其中,當遇到Local Variable和Global Variable同名時,會讀取到Local Variable的數值,直到Local
Variable的生命結束,才可用該名字讀Global Variable,而以下作法則是當兩者同名時,欲讀到Global Variable的作法:

#include <iostream>

using namespace std;

int x = 1;

int main(){

 int x = 2;

 cout << x << endl;
 cout << ::x << endl;

 return 0;
}

這程式會輸出"2 1"。

此外,Local Variable又有很多種Storage Classes,我會解釋為該資料型態的形容詞,這個形容詞敘述了它的生命期和作用範圍,以下列舉幾個介紹:

  • register:生命期是所屬的函式。建議程式把這變數放到較快的記憶體裡面,因為該變數可能要反覆讀取
  • auto:生命期是所屬的函式
  • static:生命期為整份程式
  • extern:生命期為整份程式
static會使得該變數在一份程式中只定義一次,之後就重複使用同一個變數。
#include <iostream>
using namespace std;

void print_num(int a){
 int num = 0;
 num += a;
 cout << num << endl;
}

void print_num_static(int a){
 static int num = 0;
 num += a;
 cout << num << endl;
}

int main(){

 int a=1;

 print_num(a);
 print_num_static(a);

 cout << endl;

 print_num(a);
 print_num_static(a);

 return 0;
}

output:

1
1

1
2

Friday, January 20, 2012

inline

inline可以加在函式定義的最前面,像是形容詞,作用是「建議」compiler,可以在每回呼叫該函式的點直接把函式內文貼過去,不需要讓程式程序跳來跳去的。

使用inline是因為:

  • 有些函式的內文很少
  • 呼叫、回傳等程序的成本相對高
然而,compiler若是發現該函式的內文很多或其他情形,是會忽略inline的。

#include <iostream>

using namespace std;

inline int max(int a, int b){
 return (a>b)?a:b;
}

int main(){

 int a=3, b=4;

 cout << "max(a,b) = " << max(a,b) << endl;

 return 0;
}

Recursion遞迴

Google總是幫助我們很多,對於了解遞迴也是,把"recursion"打入Google Search,會得到:

一個可以繼續搜尋recursion的按鍵,然後你就有跑到另一個頁面,同樣出現recursion的按鍵,按下去又跑到...不斷地下去,這就是recursion!

Windows 8 on VirtualBox


Host: Fedora14,在Virtual Box底下裝Windows 8 Developer Preview(http://windows.microsoft.com/en-US/windows-8/preview),





這是登入後的停滯畫面,與我們印象中的Windows Destop差很多
但還是有我們常見的Windows Destop可以用,點右下角的Windows Logo回到上一張的歡迎畫面
File Browser變得有點不一樣
控制台也變得跟現在多數的新平台一樣「簡潔」
稍微玩了一下之後發現大部分的功能好像都還不能用,畢竟這是Developer Preview,很想看看到時候Final Release之後大家的評價如何。

Wednesday, January 18, 2012

Wikipedia Blacked Out


今日本來要上Wikipedia找資料,卻直接導進這個畫面,閱讀一下得知:
Wikipedia is protesting against SOPA and PIPA by blacking out the English Wikipedia for 24 hours, beginning at midnight January 18, Eastern Time.
看來Wikipedia在反對美國的SOPA, PIPA法案,所以關閉以示抗議,雖然沒有深入去了解這兩個法案,只知道是關於侵權的問題,也會影響Wikipedia的運作。

Enumeration(列舉)

這樣他會自動以0為起點,印出3
#include <iostream>

using namespace std;

enum Numbers{ZERO, ONE, TWO, THREE};

int main(){

 Numbers num;
 num = THREE;

 cout << num << endl;

 return 0;
}
這樣則從自訂的1為起點,所以印出4
#include <iostream>

using namespace std;

enum Numbers{ZERO=1, ONE, TWO, THREE};

int main(){

 Numbers num;
 num = THREE;

 cout << num << endl;

 return 0;
}

Write C++ Code in Mutli-files

接續Class (C++)

在程式系統架構上有一個很重要的概念,我們會一層層的封裝,然後讓某一層的使用者不需要真的知道該層內部的如何運作,但只需要怎麼用即可,如此一來我們可以受益:

  • 有效率的建立大型程式系統,不用全部混在一起
  • 需要更改時,使用界面是相同的,修改內部程式,並不需要使用者也修改他的程式
拿影像處理的軟體舉例,一位藝術工作者只需要怎麼在上面按按鈕,不需要真的知道程式背後怎麼運作,而該軟體的工程師只要把使用界面保留相同樣子,內部功能怎麼優化、修改,並不會影響到使用者。把層級加大去思考,我們身邊很多的系統都是這樣疊加起來的。

所以,在寫C++程式碼的時候,把所有的code都放在同一個file並不是一個好主意,你可能到處修改,搞不定哪些已經完成,哪些還沒有,又說不定你想要跟別的程式共用這份code中的class,所以我們將自訂的class寫在不同的檔案,然後封裝,往後自己撰寫主程式(main)時候,不要去管class裡面怎麼運作,只要能拿來使用即可,如此才能有效率的完成較大的程式系統。

此外,我們把自訂class寫在header(.h檔)裡面,主程式只要呼叫該header就可以用自訂的class了(#include "student.h"),但是注意,這個header對於使用者(寫main,用include呼叫的人)來說,他不會想知道,也沒有必要讓他知道class內部怎麼寫,只需要讓他知道這class有什麼member data or function,所以我們只定義了名字在header:

student.h
#include <string>

using namespace std;

class Student{
 public:
  Student(string name);// you can write "string" without name as argument, but it's more clear if you write it.
  string getName();
  void setName(string name);
 private:
  string studentName;
};

然後把class裡面的那些functions定義在同名的.cpp檔裡面,如下:

student.cpp
#include <iostream>
#include "student.h"

using namespace std;

Student::Student(string name){
 studentName = name;
}

string Student::getName(){
 return studentName;
}

void Student::setName(string name){
 studentName = name;
}

注意這裡要:

  • include student.h,程式才知道原本的class定義在哪裡
  • 每一個function前面要加所屬的class::,不然compiler會當作這是普通的函式定義
我們稱這裡的header為interface,.cpp檔為implementation。

最後是使用者的程式:

main.cpp
#include <iostream>
#include <string>
#include "student.h"

using namespace std;

int main(){

 string name;
 cout << "Insert Student Name >> ";
 cin >> name;
 
 Student a(name);
 cout << "His name is " << a.getName() << endl;

 a.setName("Heron Yang");
 cout << "His name became " << a.getName() << endl;

 return 0;
}

在compiler的時候需要把student.cpp和main.cpp的.o檔都產生之後,透過linker連結成一個執行檔,所以Makefile用下列的方法寫(Windows底下多半不用自己寫):
CC = g++
#main : main.cpp student.cpp
all:
g++ main.cpp -c -o main.o
g++ student.cpp -c -o student.o
g++ main.o student.o -o main
rm *.o

被註解的main : main.cpp student.cpp是比較簡易的方法,下方all:裡面只是比較清楚的實作過程。 

Tuesday, January 17, 2012

Class (C++)

Class(類別)在具有物件導向概念的程式語言中有的,類似於C語言中的structure(結構),但是最大的差異是Class可以在其中放入function,而structure不行。

一個Class中的element可以分為public和private:

  • public:當外部欲操控某個class instance(被定義為某一class的物件),只能讀取其中為private的變數(在此我們叫他屬性,attribute)或函式
  • private:指有class內部的statement可以使用的變數或是函式
被定義為某一class的物件,我們稱作instance,每一個物件都有可能有他的屬性、函式可以讀取、呼叫。例如一個被定義為學生的物件,他就可能有他的名字、成績、年級等為他的屬性,而修改他的成績、印出他的成績、更改他的名字則是他有可能的函式。

程式設計過程中我們盡可能把一個class物件包裝的好好的,不需要也不該讓使用該物件的人看到的東西就隱藏起來(設成private),而要更改的話就呼叫set程式,如a.setName("Heron"),讀取private變數的話,a.getName()。

最後,每一個class都會有一個constructor(如果自己沒有定義,則系統會使用預設的,即沒有做什麼事),constructor的功能為初始化class裡面的變數,當有任何一個instance被定義為該class的時候constructor就會被執行,注意以下兩點:
  • constructor是class裡面的一個function,但是他不會回傳值,所以沒有資料型態
  • constructor的function name要跟class名稱一樣,compiler才知道這個是constructor
  • 當有任何一個instance被定義為該class的時候constructor就會被執行

#include <iostream>
#include <string>

using namespace std;

class Student{
 public:
  // constructor
  Student(string name){
   studentName = name;
  }

  // set funtion
  void setName(string name){
   studentName = name;
  }

  // get funtion
  string getName(){
   return studentName;
  }

 private:
  string studentName;
};

int main(){

 Student a("Heron Yang");
 cout << "Student a's name is " << a.getName() << "." << endl ;

 a.setName("A Smart Guy");
 cout << "Student a's name is " << a.getName() << "." << endl ;

 // we can not access the private attribute of the class, like:
 // cout << a.studentName;

 return 0;
}

Monday, January 16, 2012

C++ "using" Directives

A Simple C++ Program文中,我們使用std::cin, std::cout, std::cerr,然而若是整個程式都只會用到Standard Input/Output的話,可以使用"using"讓我們不必每次都要指定到std::,方法如下:

於#include之後緊接著打:
using std::cout;
using std::cin;
using std::endl;
如此可以直接使用cout, cin, endl,且指定到std::。

又若是整個程式都要使用std的命名空間(namespace)的話,可以打這行:
using namespace std;

完整的範例如下:
#include <iostream>

using namespace std;

int main()
{
 int a;

 cout << "Hello Heron!" << endl;
 cout << "a >> ";
 cin >> a;
 cout << "a = " << a << endl;

 return 0;
}

Sunday, January 15, 2012

A Simple C++ Program

這是一個C++的Hello World程式。
#include <iostream>

int main()
{
 std::cout << "Hello Heron!\n";

 return 0;
}

其中跟C語言不同的地方有:
  • 輸入輸出標頭檔,"iostream"(input/output stream,非沒有C語言中的.h檔)
  • std::是一個namespce(命名空間),被定義在"iostream",std為standard的意思,包含了
    1. cout:輸出
    2. cin :出入
    3. cerr:處理錯誤
  • << 運算子表示把右邊運算元插入(insert)到左邊的stream,如上面程式中,把右邊的字串放入到基本輸出(std::cout)
Reference: C++ How to Program

Thursday, January 12, 2012

Longest Common Substring

Longest Common Substring (LCS)是用來找尋兩字串中最長共同子字串的長度。此方法運用動態規劃(Dynamic Programming, DP)。

我們必須先開一個二維陣列來儲存到某一狀況時的最長共同子字串的長度為多少。動態規劃即是隨時會紀錄下最新的狀況,往後要用時直接找尋該資料來拿運算,算出一筆新資料之後再記錄下來,以待往後使用... 如此循環運作。此方法可以省下許多時間複雜度,但卻要付出額外的記憶體空間紀錄,我個人會解讀這樣的方法是用空間去換取時間

此外,若是只要判斷某字串是否為另外一個字串的子字串,只需判斷LCS的長度是否跟比較短的那字串長度相同即可。


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

// 2D map
int map[100][100];

/* 
 * Function : max
 * This return the bigger number of the two input variables.
 */
int max(int a, int b){
 return (a>b)?a:b;
}

/*
 * Function : LCS
 * Longest Common Substring function here.
 * This function return the length of their longest common
 * substings.
 */
int lcs(char str1[], char str2[]){

 int i, j;
 int m=strlen(str1), n=strlen(str2);

 for(i=1 ; i<=m ; i++){
  for(j=1 ; j<=n ; j++){
   if(str1[i] == str2[j])
    map[i][j] = map[i-1][j-1]+1;
   else
    map[i][j] = max(map[i][j-1], map[i-1][j]);
   printf("%d ",map[i][j]);
  }
  printf("\n");
 }

 return map[m][n];
}

int main(void){

 // variable declarations
 char str1[100], str2[100];

 // input two strings
 printf("String1 >> ");
 scanf("%s",str1);
 printf("String2 >> ");
 scanf("%s",str2);

 // print out result
 printf("LCS >> %d\n", lcs(str1, str2));

 // by checking whether the length of lcs is same as the string1,
 // we would know whether string1 is the substring of string2 or not.
 if(lcs(str1, str2) == strlen(str1))
  printf("String1 is a substring of String2!\n");
 else
  printf("String1 is NOT a substring of String2!\n");

 return 0;
 // end
}

參考資料:
http://en.wikipedia.org/wiki/Longest_common_substring_problem

Friday, January 6, 2012

Sorting Using Link List With Bubble Sort

一般我們用陣列做bubble sort時,使用兩個變數指向陣列的某個位置,即兩個array index的變數,而使用link list時,則改用struct node指標。

int i, j v.s. struct node*

link list和陣列都是呈現「一串有序資料」的方法,於是可以做出的功能應該是相近的,在撰寫Bubble Sort之前,歸納下列三個所需的功能,並找出兩者的作法:
  • 掃描過整串資料
    • 陣列
for(i=0 ; i<len ; i++)  arr[i]...
    • link list
now = top;
while(now){
 now->data... ;
 now = now->next;
}
  • 交換資料(swap)
    • 陣列
int t;
t = a[i];
a[i] = a[j];
a[j] = t;

    • link list:直接個別交換structure中的elements或是交換node指標
  • 指向某項資料與判斷
    • 陣列:用int變數當作儲存特定位置的index
    • link list:用struct node指標當作儲存特定位置的方法
[範例]
有一份檔案grades.txt,存有一串資料,格式是[名字 分數],例如:
Heron 99
Apple 89
Nobody 100
我們將這串資料讀到link list之後排序,再把結果印出到sorted_grades.txt。

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

// structure defination
struct node{
 char name[100];
 int grade;
 struct node *next;
};

// a node pointer pointing to the top of linklist
struct node *top;

int main(void){

 // initialize file pointers fin, fout
 FILE *fin = fopen("grades.txt" ,"r");
 FILE *fout = fopen("sorted_grades.txt","w");

 // malloc top node
 top = (struct node *)malloc(sizeof(struct node));

 // define "now" node pointer, and pointer to top
 struct node *now;
 now = top;
 now->next = NULL;

 // define some variables to store new data temporarily
 char new_name[100];
 int new_grade;

 // scan in the data from file and build into linklist
 while(fscanf(fin, "%s%d", new_name, &new_grade)!=EOF){

  // copy the temporary data to linklist node
  strcpy(now->name, new_name);
  now->grade = new_grade;

  // create a new node "new" and store the new data
  struct node *new;
  new = (struct node *)malloc(sizeof(struct node));
  new->next = NULL;

  // let "now->next" point to new
  now->next = new;
  // let "now" point to now->next
  now = now->next;

 }


 // sorting here, using bubble sort

 // define last node pointer "last" pointing to last node
 struct node *last = now; // last node is empty
 
 // while the last pointer doesn't come the top one
 while(last != top){

  now = top;

  // while now pointer doesn't come to the end
  while(now->next != last){

   // if the grade in now is greater than the grade in now->next
   // then swap
   if(now->grade > now->next->grade){

    // swap grade
    int t;
    t = now->grade;
    now->grade = now->next->grade;
    now->next->grade = t;

    // swap name
    char tN[100];
    strcpy(tN, now->name);
    strcpy(now->name, now->next->name);
    strcpy(now->next->name, tN);

   }


   // if now is about to the last
   // then let last point to the previous node
   // something like, "last--", if we use array index
   if(now->next->next == last){
    last = now;
    break;
   }

   // let now point to the next one,
   // things like, "now++", if we use array index
   now = now->next;
  }
 }


 // print out the whole link list
 now = top;
 while(now->next){
  //printf("%s\t%d\n", now->name, now->grade);
  fprintf(fout, "%s\t%d\n", now->name, now->grade);
  now = now->next;
 }
 
 // end
 return 0;
}