C++ Pointer 與 Array 的相關範例筆記

觀念：

指標是用來指向記憶體位址的，可用*設指標變數跟取指向位址的值。&就是取變數記憶體位址。

陣列宣告

資料型態 陣列名稱[陣列長度];

int A[10];

程式名稱：

程式碼：

資料來源：
1.C++ Array of Pointers

2.[C/C++] char s[]和char *s的差別

3.C++指標與陣列

4.陣列

C++ Class 的範例筆記

程式名稱：ClassRectangle01.cpp
程式內容：

#include <iostream>

using namespace std;

class CRectangle {

int x,y;

  public:

     void set_values (int a,int b) {

        x = a;

y = b;

}

     int area(void){

      return x*y;

}

};

int main() {

  CRectangle rect;

  rect.set_values(3,4);

  cout << " area： " << rect.area();

}

建構子

建構子 constructor， 它透過一個與 class 同名的函數來定義。當且僅當要生成一個 class 的新的物件的 時候或給該 class 的一個物件分配記憶體的時候，這個建構子將自動被調用。。一個建構子永遠沒有返回值，也不用宣告成 void。

程式名稱：ClassRectangle02.cpp
程式內容：

#include <iostream>

using namespace std;

class CRectangle {

int width,height;

public:

CRectangle (int a, int b) {

width = a;

height = b;

}

int area(void) {

return width*height;

} 

};

int main() {

CRectangle rect01 (3,4),rect02 (5,6);

        cout << " rect01 area：" << rect01.area()<< endl;

        cout << " rect02 area：" << rect02.area()<< endl;

}

解構子

解構子 destructor 完成相反的功能。它在 objects 被從記憶體中釋放的時候被自動 調用。釋放可能是因為它存在的範圍已經結束了（例如，如果 object 被定義為一 個函數內的 local (區域) 物件變數，而該函數結束了）；或者是因為它是一個動 態分配的物件，而被使用運算子 delete 釋放了。 解構子必頇與 class 同名，加上水波號 tilde (~) 首碼，一樣必頇無返回值。

程式名稱：ClassRectangle03.cpp
程式內容：

#include <iostream>

using namespace std;

class CRectangle {

int *width,*height;

public:

CRectangle (int a, int b) {

width = new int;

height = new int;

*width = a;

*height = b;

}

~CRectangle (){

delete width;

delete height;

}; 

int area(void) {

return *width * *height;

} 

};

int main() {

CRectangle rect01 (3,4),rect02 (5,6);

    cout << " rect01 area：" << rect01.area()<< endl;

    cout << " rect02 area：" << rect02.area()<< endl;

}

資料來源： 
1.C++物件導向及增進效率程式技巧

資料結構關於堆疊Stack例題、佇列Queue例題筆記

堆疊Stack

觀念：
LIFO(last in first out) 後進先出

常用方法：

stack<int> sk 建立一個int型別的stack

sk.size()         堆疊元素數量

sk.empty() 判斷堆疊是否為空

sk.push(x) 從堆疊「頂端」加入一個元素x

sk.pop()         刪除堆疊頂端元素

sk.top()         取得堆疊頂端元素

題目：

EX_01：10進位轉2進位(以STL stack實作)。11->1011

程式碼：

#include <iostream>

#include <stack>

using namespace std;

int main() {

    stack<int> sk;   

    int n;

    cin >> n;

    while (n>0) {                     // n大於0 

    sk.push(n%2);               // 將n除以2的餘數push進堆疊 

    n=n/2;                           // 將n除以2 

}

while (!sk.empty()) {    // 堆疊內還有元素 

cout << sk.top();   // 印出堆疊頂端元素 

sk.pop();                // 將堆疊頂端元素移除 

}

cout <<endl;

}

佇列Queue

觀念：

FIFO(first in first out) 先進先出

常用的方法

queue<int> qe        建立一個int型別的queue

qe.size()                佇列元素數量

qe.empty()        判斷是否為空

qe.push(x)        從佇列「後端」加入一個元素x

qe.pop()                從「前端」刪除一個元素

qe.front()                取得前端元素

qe.back()                取得後端元素

題目：

EX_02：ZeroJudge e183: 10940 - Throwing cards away II  

給你一疊有1~n編號的牌(1在最上面，n在最下面)，在牌數大於1的時候執行以下操作：「丟掉最上面的牌，並把現在最上面的的牌放到最下面。」

求最後剩下的那張牌編號為?(7->6、10->4)

程式碼：

#include <iostream>

#include <queue>

using namespace std;

int main() {

queue<int> q;

int i,n,p;

cin >> n;

for(i=1;i<=n;i++) {

q.push(i);           // 將牌的編號(1 2 3 …)依序push入佇列

}

while(q.size() > 1) {   // 當佇列size>1時繼續執行

q.pop();            // 將最上面的牌丟掉

q.push(q.front());  // 將次張牌重新放入佇列尾端

q.pop();            // 將次張牌丟掉

}

cout << q.front();      // 印出剩下的那張牌

}

資料來源：
1.資料結構與演算法(使用C++)

Z 字型編排問題

 問題描述：8X8的矩陣，有著如下編排：

今天要將編排的方式寫成C++的程式碼，分析如下：

下方圖片內容檔：Z 字型編排問題

換句話說，只有四種動作。

資料來源：

1.算法：Z字型（Zigzag）編排

C++標準函式庫_第五章Standard Template Library標準模板庫_讀後心得與重點整理

容器(圖片摘錄至資料來源1的P.104)

檔名：vector1.cpp

檔案內容：

#include <iostream>

#include <vector>

using namespace std;

int main() {

   vector<int> col1;

   int i;

   for (i=1;i<=6;++i) {

    col1.push_back(i);

   }

   cout << col1.size() <<endl;

   for(i=0;i<col1.size();++i) {

    cout << col1[i] <<' ';

   }

   cout << endl;

}

檔名：deque1.cpp

檔案內容：

#include <iostream>

#include <deque>

using namespace std;

int main() {

deque<int> col1;

int i;

    for (i=1;i<=6;i++) {

    col1.push_front(i);

}

for (i=0;i<col1.size();i++) {

cout << col1[i] <<' ';

}

cout << endl;

}

檔名：list1.cpp

檔案內容：

#include <iostream>

#include <list>

using namespace std;

int main() {

   list<char> coll;

   for (char c='a';c<='z';c++) {

    coll.push_back(c);

   }

   while(!coll.empty()) {

    cout << coll.front() <<' ';

    coll.pop_front();

    }

    cout << endl;

   for (char c='a';c<='z';c++) {

    coll.push_back(c);

   }

   while(!coll.empty()) {

    cout << coll.back() <<' ';

    coll.pop_back();

    }

    cout << endl;

}

檔名：list2.cpp

檔案內容：

#include <iostream>

#include <list>

using namespace std;

int main() {

   list<char> coll;

   list<char>::const_iterator pos;

   for (char c='a';c<='z';c++) {

    coll.push_back(c);

   }

   for (pos=coll.begin();pos!=coll.end();pos++) {

    cout << *pos <<' ';

   }

   cout<<endl;

}

檔名：set1.cpp

檔案內容：

#include <iostream>

#include <set>

using namespace std;

int main() {

    set<int> coll;

    set<int>::const_iterator pos;

    for (int a=1;a<10;++a) {

    coll.insert(a);

}

    coll.insert(1);

    coll.insert(3);

    coll.insert(5);

    for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos <<' ';

}

cout << endl;     

}

檔名：mmap1.cpp

檔案內容：

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

   typedef multimap<int,string> IntStringMMap;

   IntStringMMap coll;

   coll.insert(make_pair(5,"tagged"));

   coll.insert(make_pair(2,"a"));

   coll.insert(make_pair(1,"this"));

   coll.insert(make_pair(4,"of"));

   coll.insert(make_pair(6,"strings"));

   coll.insert(make_pair(1,"is"));

   coll.insert(make_pair(3,"multimap"));

   IntStringMMap::iterator pos;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << pos->second <<' ';

   }

   cout << endl;

   

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << (*pos).second <<' ';

   }

   cout << endl;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << pos->first <<' ';

   }

   cout << endl;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << (*pos).first <<' ';

   }

   cout << endl;

}

檔名：map1.cpp

檔案內容：

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

   typedef map<string,float> StringFloatMap;

   StringFloatMap coll;

   coll["VAT"]=0.15;

   coll["Pi"]=3.1415;

   coll["an arbitrary number"] = 4983.223;

   coll["Null"]=0;

   StringFloatMap::iterator pos;

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << "key: \"" << pos->first << "\" "

    << "value: " << pos->second << endl;

   }

}

檔名：algo1.cpp

檔案內容：

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

   vector<int> coll;

   vector<int>::iterator pos;

   

   coll.push_back(2);

   coll.push_back(5);

   coll.push_back(4);

   coll.push_back(1);

   coll.push_back(6);

   coll.push_back(3);

   

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos << ' '; 

   }

   cout << endl;

   

   pos = min_element(coll.begin(),coll.end());

   cout << "min: " << *pos << endl;

   cout << "min: " << *min_element(coll.begin(),coll.end()) << endl;

   pos = max_element(coll.begin(),coll.end());

   cout << "max: " << *pos << endl;

   cout << "max: " << *max_element(coll.begin(),coll.end()) << endl;

   

   sort(coll.begin(),coll.end());

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos << ' '; 

   }

   cout << endl;

   

   pos = find(coll.begin(),coll.end(),3);

   cout << *pos << endl;

   

   reverse(pos,coll.end());

   for (pos=coll.begin();pos!=coll.end();++pos) {

    cout << *pos << ' '; 

   }

   cout << endl;

}

檔名：find1.cpp

檔案內容：

#include <iostream>

#include <list>

#include <algorithm>

using namespace std;

int main() {

  list<int> coll;

  list<int>::iterator pos;

  

  for (int i=20;i<=40;++i) {

  coll.push_back(i);

  }

  pos = find(coll.begin(),coll.end(),3);

  cout << "pos = "<<*pos <<endl;

  reverse(pos,coll.end());

  for (pos = coll.begin();pos!=coll.end();++pos) {

  cout << *pos <<' ';

  }

  cout << endl;

  

  list<int>::iterator pos25,pos35,pos30;

  

  pos25 = find(coll.begin(),coll.end(),25);

  cout << "pos25: " << *pos25 << endl;

  pos35 = find(coll.begin(),coll.end(),35);

  cout << "pos35: " << *pos35 << endl;

  

  cout << "max: " << *max_element(pos25,pos35) << endl;

  cout << "max: " << *max_element(pos25,++pos35) << endl;

  

  ++pos35;

  pos30 = find(pos25,pos35,30);

  cout << "pos30 = " << *pos30 << endl;

}

檔名：copy2.cpp

檔案內容：

#include <iostream>

#include <vector>

#include <list>

#include <deque>

#include <algorithm>

using namespace std;

int main() {

   list<int> coll1;

   list<int>::iterator pos1;

   vector<int> coll2;

   vector<int>::iterator pos2; 

   

   for (int i=1;i<=9;++i) {

    coll1.push_back(i);

   }

   cout <<"coll1： " << endl;

   for(pos1=coll1.begin();pos1!=coll1.end();++pos1) {

    cout << *pos1 <<' ';

   }

   cout << endl;

   

   coll2.resize(coll1.size());

   

   copy(coll1.begin(),coll1.end(),coll2.begin());

   

   cout <<"coll2： " << endl;

   for(pos2=coll2.begin();pos2!=coll2.end();++pos2) {

    cout << *pos2 <<' ';

   }

   cout << endl;

   

   deque<int> coll3(coll1.size());

   deque<int>::iterator pos3;

   

   copy(coll1.begin(),coll1.end(),coll3.begin());

   

   cout <<"coll3： " << endl;

   for(pos3=coll3.begin();pos3!=coll3.end();++pos3) {

    cout << *pos3 <<' ';

   }

   cout << endl;

}

檔名：vector101.cpp

檔案內容：

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <iterator>

using namespace std;

int main() {

   vector<string> sentence;

   sentence.reserve(5);

   sentence.push_back("Hello,");

   sentence.push_back("how");

   sentence.push_back("are");

   sentence.push_back("you");

   sentence.push_back("?");

   

   copy (sentence.begin(),sentence.end(),ostream_iterator<string>(cout," "));

   cout << endl;

   cout << "max_size()： " << sentence.max_size() << endl;

   cout << " size()： " << sentence.size() << endl;

   cout << " capacity()： " << sentence.capacity() << endl;

   

   swap (sentence[1],sentence[3]);

   sentence.insert( find(sentence.begin(),sentence.end(),"?"),"always");

   

   copy (sentence.begin(),sentence.end(),ostream_iterator<string>(cout," "));

   cout << endl;

   cout << "max_size()： " << sentence.max_size() << endl;

   cout << " size()： " << sentence.size() << endl;

   cout << " capacity()： " << sentence.capacity() << endl;

}

檔名：deque101.cpp

檔案內容：

#include <iostream>

#include <deque>

#include <string>

#include <algorithm>

#include <iterator>

using namespace std;

int main() {

deque<string> col1;

col1.assign(3,string("string"));

col1.push_back("last string");

col1.push_front("first string");

copy(col1.begin(),col1.end(),ostream_iterator<string>(cout,"\n"));

cout << endl;

col1.pop_front();

col1.pop_back();

copy(col1.begin(),col1.end(),ostream_iterator<string>(cout,"\n"));

cout << endl;

cout << col1.size();

cout << endl;

for (int i=1;i<col1.size();++i) {

col1[i] = "another " + col1[i]; 

}

col1.resize(4,"resized string");

copy(col1.begin(),col1.end(),ostream_iterator<string>(cout,"\n"));

}

檔名：map1.cpp

檔案內容：

檔名：map1.cpp

檔案內容：

資料來源：
1.C++標準函式庫(The C++ Standard Library by Josuttis)

CPP關於資料結構Stack堆疊的資料

         目前發現CPP對於理解資料結構，真的很好用。此外，還有很多文章能夠促進理解資料結構。因此，闢一個文章，來收集各家對資料結構Stack的解說。如果可以，甚至節錄程式碼。

玩玩看Stack

一、用陣列Array 來寫

01檔名：StackArray01.cpp

內容：

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#define MAX_SIZE 10

void push(int);

void pop(void);

int stack[MAX_SIZE];

int top = 0;

using namespace std;

int main(void) {

    push(0);

    push(1);

    push(2);

    pop();

    pop();

    push(3);

    push(4);

    pop();

    pop();

    pop();

    push(5);

    push(6);

    push(7);

    pop();

    pop();

    pop();

    system("pause");

}

void push(int data) {

if (top == MAX_SIZE) {

cout <<"The Stack is full "<<endl;

} else {

stack[top]=data;

top++;

}

}

void pop(void) {

if (top == 0) {

cout <<"The Stack is empty "<<endl;

} else {

cout <<stack[--top]<<endl;

}

}

輸出結果

02檔名：StackArray02.cpp

內容：

#include <iostream>

using namespace std;

int stack[105],stack_top;

int main() {

string cmd;

int i,j;

stack_top = 0;

cout <<"When the command is 'push 3' We push 3 into the stack!\n";

cout <<"When the command is 'pop' ,we get a element from the stack!\n";

cout <<"When the command is 'All' ,we will get all elements of the stack!\n";

cout <<"When the command is 'exit' ,we will quit the program!\n";

while(cin >> cmd) {

if(cmd == "push") {

cin >> i;

stack[stack_top]=i;

cout <<"stack["<<stack_top<<"]= "<<stack[stack_top]<<endl;

stack_top++;

} else if (cmd == "pop"){

if(stack_top==0) {

cout << "pop: nothing in stack"<<endl;

} else {

cout << "pop: " <<stack[stack_top-1] <<endl;

stack_top--;

}

}

if(cmd == "exit") {

break;

}

if(cmd == "All") {

   for(j=stack_top-1;j>=0;j--) {

    cout <<"stack["<<j<<"]="<<stack[j]<<endl;

   }

}

}

return 0;

}

03檔名：StackArray03.cpp

內容：

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

typedef struct stack {

int top;

int maxTop;

int *data;

}stack_t;

void create_stack(stack_t *st,int size) {

st->top=-1;

st->maxTop=size-1;

st->data=(int *)malloc(sizeof(int)*size);

}

int isEmpty(stack_t *st) {

if (st->top==-1) {

return 1;

}

return 0;

}

int isFull(stack_t *st) {

if (st->top==st->maxTop) {

return 1;

}

return 0;

}

void push(stack_t *st,int num) {

if (isFull(st)==1) {

printf("The stack is full.\n");

} else {

st->top++;

st->data[st->top] = num;

//printf(" st->top is %d\t",st->top);

//printf("st->data[st->top] is %d\n",st->data[st->top]);

}

}

int pop(stack_t *st) {

int TempInt;

if (isEmpty(st)==1) {

printf("The stack is empty.\n");

} else {

TempInt = (st->data[st->top]);

st->top--;

}

return TempInt;

}

void print(stack_t *st) {

if (isEmpty(st)==1) {

printf("The stack is empty.\n");

} else {

for(int i=0;i<=st->top;i++) {

printf(" %d",st->data[i]);

}

printf("\n");

}

}

int main() {

stack_t *s = (stack_t *)malloc(sizeof(stack_t));

printf("Create a stack which size is 5.\n");

create_stack(s,5);

printf("Push:1,2,3,4,5\n");

for(int i=1;i<6;i++) {

push(s,i);

}

print(s);

printf("1st pop,the top is %d.\n",pop(s));

print(s);

printf("2nd pop,the top is %d.\n",pop(s));

print(s);

return 0;

}

04檔名：StackArray04.cpp

內容：

#include <stdio.h>

#include <stdlib.h>

#include <conio.h> 

#define MAX 10

void push_f(void);

void pop_f(void);

void list_f(void);

char item[MAX][20];

int top = -1;

int main() {

char option;

while(1) {

printf("\n ----------------------------------\n");

printf(" (1) insert (push)\n");

printf(" (2) delete (pop)\n");

printf(" (3) list\n");

printf(" (4) quit\n");

printf("\n ----------------------------------\n");

printf(" Please enter your choice...");

option = getche();

switch(option) {

case '1':

push_f();

break;

case '2':

pop_f();

break;

case '3':

list_f();

break;

case '4':

printf("\n");

return 0;

}

}

}

void push_f(void) {

if (top>=MAX-1) {

printf("\nStack is full !\n");

} else {

top++;

printf("\n Please enter item to insert: ");

gets(item[top]);

}

}

void pop_f(void) {

if (top<0) {

printf("\nNo item,stack is empty!\n");

} else {

printf("\n Item %s deleted \n",item[top]);

top--;

}

}

void list_f(void) {

int count = 0,i;

if (top < 0) {

printf("\nNo item,stack is empty!\n");

} else {

printf("\n Item\n");

printf("---------------------\n");

for(i=0;i<=top;i++) {

printf(" %-20s\n",item[i]);

count++;

if(count % 20 ==0) getch();

}

printf("---------------------\n");

printf("Total item: %d\n",count);

getch();

}

}

二、用鏈結串列LinkedList 來寫

檔名：StackLinkedList001.cpp

內容：

題目練習

Q673: Parentheses Balance 

Q514: Rails 

Q271: Simply Syntax 

資料來源：

1.堆疊(stack) 資料結構

2.【演算】堆疊 - Stack

3.堆疊(Stack)

4.Stack (Array Implementaion)

5.C++ 程式語言堆疊 stack 用法教學與範例

6.<C語言> Stack By Array And Linked List - 資料結構

7.以連結串列 (Linked List) 為基礎的堆疊 (Stack)