---
title: C++教室第三節社課
slideOptions: # 簡報相關的設定
theme: blood # 顏色主題
transition: 'slide' # 換頁動畫
#parallaxBackgroundImage: 'https://c.wallhere.com/photos/a5/a8/Neon_Genesis_Evangelion_mech_EVA_Unit_13-1319035.jpg!d'
---
C++教室教學講義
===
>[name=Howard] [time=october 25th] [color=#333]
###### tags:`tcirc` `社課`
---
第三節社課
===
[TOC]
---
## 複習時間
----
### 字元與字串
我們說
字串是多個字元集合體
----
字元用單引號('')包住
字串用雙引號("")刮住
----
字元有搭配的資料型態char
那字串有沒有?
----
要知道這個問題的答案
先讓我們來看看另一個概念
---
## 陣列(array)
----
陣列是一群由相同資料型態的變數所組合成的資料型態(有點拗口)
----
### 一維陣列(1-dimensional array)
----
一維陣列中的內容像車廂般串接起來
要找到其中的個別元素(element)，就要根據索引(index)標示
就像要搭車時所看到的車廂號碼
----
### 一維陣列陣列的宣告
```cpp
資料型態 陣列名稱[元素個數];
```
----
資料型態就是你要在陣列裡除儲存什麼樣的資料，
接著決定這個陣列的名稱，
中括號([])放入你要儲存的元素個數
----
```cpp=
#include<iostream>
using namespace std;
int main()
{
int b[4] = {1,2,3,4};
}
```
----
### 輸出其中元素
```cpp=
cout<<b[1];
```
----
恩?
怎麼第一格元素是2而不是1
```
/*OUTPUT---
2
------------*/
```
----
### 陣列的索引從零開始(這次沒有梗)
----
### 這樣就對了
```cpp=
cout<<b[0]<<b[1]<<b[2]<<b[3];
```
```
/*OUTPUT---
1234
------------*/
```
<span>但是很哭<!-- .element: class="fragment" data-fragment-index="1" --></span>
----
眼尖的各位應該發現我們可以用迴圈來輸出整個陣列
----
```cpp=
#include<iostream>
using namespace std;
int main()
{
int b[4] = {1,2,3,4};
for(int i=0;i<4;i++)
{
cout<<b[i]<<" ";
}
}
```
----
```
/*OUTPUT---
1 2 3 4
------------*/
```
<span>你說沒差多少?<!-- .element: class="fragment" data-fragment-index="1" --></span>
<span>c[100000]做給我看，現在你知道迴圈的重要了<!-- .element: class="fragment" data-fragment-index="2" --></span>
----
### 初始化
方法：宣告後面加上等號，在\{\}之間填入想要的元素，以逗號區隔。
如果有做初始化，則[]內可以不放元素數量，屆時編譯器會依元素數量設定陣列大小，這部分之後會做說明。
* 注意:初始化只能在宣告時使用!!!
----
全0的陣列：
```cpp=
int s[5] = {};
```
不用自己數的陣列：
```cpp=
int s[] = {1,5,6,7,-1,2,-88};
```
初始化的時機：
```cpp=
int s[5] = {1,2,3,4,5}; //OK
s = {1,2,3,4,5}; //NO
```
----
## 太長的困擾
太長真的會去到不該去的地方
<span>我是說陣列(哭阿)<!-- .element: class="fragment" data-fragment-index="1" --></span>
----
### 索引值超過陣列大小
```cpp=
#include<iostream>
using namespace std;
int main()
{
int b[4] = {1,2,3,4};
for(int i=0;i<10;i++)
{
cout<<b[i]<<" ";
}
}
```
----
奇怪的東西出現了 要戰鬥嗎?(X
```
/*OUTPUT---
1 2 3 4 489975456 32767 0 0 4196320 0
------------*/
```
c++並不會檢查索引值的大小，當索引超出陣列長度之後可能會其他記憶體位置的資料給覆蓋或輸出
這種錯誤發生在執行時(run-time error)，而不是編譯時(compile-time error)，故編譯氣無法提供任何警告。
----
### 二維陣列
何謂二維陣列？表示一個陣列中的每個元素都是一個陣列。應該很好理解？
思考一下二維陣列如何存取、宣告、即初始化吧！
----
宣告：
```cpp=
int two_d_array[9][5];
//表示這個陣列有9個元素，每一個元素都是一個長度為5的陣列
```
----
初始化：
```cpp=
char x[3][4] = {
{'a','3','6','7'},
{'6','1','0','8'},
{'X','\t','W','n'}
};
```
----
存取：
```cpp=
#include<iostream>
using namespace std;
int main()
{
char x[3][4] = {
{'a','3','6','7'},
{'6','1','0','8'},
{'X','\t','W','n'}
};
for(int a = 0;a < 3;a++){
for(int b = 0;b < 4;b++){
cout << x[a][b];
}
cout << endl;
}
}
```
```
/*OUTPUT---
a367
6108
X Wn
------------*/
```
----
三維陣列？四維陣列？十維陣列？不用擔心，這些都存在喔。
只要把他們想成一個陣列其中每個元素都是一個少一維的陣列就好了，不用害怕~
N維陣列的宣告：
```
(data_type) arr_name[dim1][dim2].....[dimN]
= {(array with[dim2][dim3]...[dimN]),,,...(*dim1)};
OR
= {} //全零的初始化適用所有維度的陣列
```
---
## 字串
----
我們學完了array
也就是說，字串是字元陣列4吧
----
### 關於字串的兩個分類
兩者的用法不盡相同
1. C型態字串(C-style string)
指字元陣列
2. C++型態字串(C++-style string)
指string
----
### 字元陣列
```cpp
char 字串名稱[字串長度];
```
----
可以直接做設定並輸出喔
直接做設定變數內容[]內可以省略(編譯器會判斷大小)
```cpp=
#include<iostream>
using namespace std;
int main()
{
char i[] = "abcdefgh";
cout<<i<<'\n';
}
```
----
```
/*OUTPUT---
abcdefgh
------------*/
```
----
### 看一下字元陣列有多大
sizeof()函數簡單來說就是看變數佔多少空間
```cpp=
#include<iostream>
using namespace std;
int main()
{
char i[] = "34";
cout<<sizeof(i)<<'\n';
}
```
----
靠杯，怎麼3跟4兩個元素會佔3個空間
難道說我們證明出3跟4之間還有另一個整數bleem的存在
已經要穿越時空了嗎
```
/*OUTPUT---
3
------------*/
```
----
{%youtube 7jlSUUjVG3Y %}
----
### 空字元(\0)
空字元的概念超重要
字串儲存在記憶體十，會在最後面加上字串結束字元'\0'做結尾
<span>現在你知道為什麼我們還沒穿越了(x <!-- .element: class="fragment" data-fragment-index="1" --></span>
----
### string
```cpp
#include<cstring> //要先引入<cstring>才能使用
using namespace std; //這個也要
string 字串名稱;
```
----
放入內容
```cpp
string b;
b = "hello world";
```
----
快速用法
| string 字串名稱("字串內容") | string str1("瑞斯一打三! ") |
| -------- | -------- |
| string 字串名稱(n,'要重複n次的字元') | string str2(5,'A') |
```CPP=
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str1("瑞斯一打三! ");
string str2(5,'A');
cout<<str1<<str2<<endl;
}
```
----
```
/*OUTPUT---
瑞斯一打三! AAAAA
------------*/
```
<span><!-- .element: class="fragment" data-fragment-index="1" --></span>
----
字串也可以用加號達到串接的效果
```c++=
string str3 = str1 + str2;
cout<<str3<<endl;
```
---
## 量長度(我都用兩把尺)
----
### sizeof()
----
sizeof()函數可以拿來檢查變數佔的記憶體空間大小
```cpp=
#include <iostream>
#include<string>
using namespace std;
int main() {
char c='1';
cout<<sizeof(c)<<'\n';
int i=1;
cout<<sizeof(i)<<'\n';
double d=1;
cout<<sizeof(d)<<'\n';
string s="1";
cout<<sizeof(s)<<'\n';
}
```
----
這些數字很熟悉ㄝ，是不是講過?
雖然變數內放的都是1，但是因為資料型態不同，記憶體大小自然不一樣
```
/*OUTPUT---
1
4
8
32
------------*/
```
<span>就算裡面沒有東西，在宣告的時候編譯器也會先給變數配置記憶體所以結果也會一樣<!-- .element: class="fragment" data-fragment-index="1" --></span>
----
腦力激盪
```cpp=
#include <iostream>
#include<string>
using namespace std;
int main() {
char i[3];
cout<<sizeof(i)<<'\n';
cout<<sizeof(i[3])<<'\n';
}
```
----
Oh faker what was that?
```
/*OUTPUT---
3
1
------------*/
```
----
### .length()
.length用來取得字串的長度
----
```cpp=
#include <iostream>
#include<string>
using namespace std;
int main()
{
string i="12345";
cout<<i.length()<<'\n';
}
```
----
注意: .length()是string專用喔
```
/*OUTPUT---
5
------------*/
```
----
#### 阿如果不放東西勒
```cpp=
#include <iostream>
#include<string>
using namespace std;
int main()
{
string s="";
cout<<s.length()<<'\n';
char c[] = "";
cout<<sizeof(c)<<'\n';
}
```
----
#### 太玄了
```
/*OUTPUT---
0
1
------------*/
```
----
### .size()
.size()同.length()用來取得字串的長度
<span>小預告<!-- .element: class="fragment" data-fragment-index="1" --></span>
<span>.size()也可以拿來找vector裡面元素的個數<!-- .element: class="fragment" data-fragment-index="2" --></span>
----
### 附註
關於string還有很多相關的函式用法，就交給各位自行研究
---
## cin的相關(奇怪)用法
前方高能預警
前方高能預警
前方高能預警
不知道要從何講起(請看程式碼註解)
----
雖然看起來很複雜，但我認為把他們全部放在一起才能最快的體會各自的功用
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a;
char b[100];
string jj;
cin >> a >> b; //接受一个字串or數字，遇“空格”、“TAB”、“Enter”都结束
cout << a <<" " << b << "\n";
char c;
cin.get(c); //cin.get(字元名)可以用来接收字元
cout << c << "\n";
cin.get(b,5); //cin.get(字串名,接收字元数目)用來接收一行特定數量的字串,可以接收空格
cin.get(); //cin.get()没有参數主要是用於捨棄输入流中的不需要的字元,或者捨棄Enter
cout << b << "\n";
cin.getline(b,10); //cin.getline()實際上有三个參數，cin.getline(接受字串名,接受數量,结束字元)
cout << b << "\n";
getline(cin,jj); //getline()用於string , cin.getline()用於字元陣列
cout << jj << endl;
}
```
---
## 補充：指標
指標(pointer)是C++裡面一個指標性的功能(~~拍手~~)
甚麼是指標？
我們知道每一個變數都是一塊記憶體，對吧？而既然如此，他們就有所謂的**記憶體位址**，代表記憶體在電腦中的位置，而指標是用來指向每個記憶體位址，並對其進行存取。
你可以把變數想像成盤子上的食物，我們一般取用時都是用手抓，而指標就相當於筷子，能夠較靈活的存取變數。(~~大概吧~~)
----
### 宣告： ＊
```cpp=
int* pt;
char* x;
double* qqq;
```
----
### 位址運算子：＆
在變數前面加上＆，就可以取得該變數的位址。
```cpp=
#include<iostream>
using namespace std;
int main(){
int x = 77;
cout << &x;
}
```
```
/*OUTPUT---
0x6ffe1c
------------*/
```
### 指標的各種含義
* 指標的值是一個位址，或者說一個指標指向一個位址。
* 利用取值運算子「*」可以存取一個指標指向的東西。
* 陣列名稱本身是該陣列的開頭(元素0)的位址
* x[k] 等價於 *(x+k)
* 沒錯指標可與整數作加減，表示往前後移動幾個位址，使用指標時請盡量確保指標指向的記憶體位址有經過申請(有宣告過)，否則不保證會發生甚麼。
```cpp=
#include<iostream>
using namespace std;
int main(){
int x[] = {5,0,7,9,11};
int* pt = &x[2]; //assign address to pointer
cout << pt << ' ' << *pt << '\n';//output address and value
int* pt2 = x; //array name is same as &x[0]
cout << pt2 << ' ' << *pt2 << '\n';
pt = pt2; //pointers can be assigned too
for(int a = 0;a < 5;a++){
cout << (pt+a) << ' ' << *(pt+a) << '\n';
// adding pointer = moving pointer forward/backward
}
//this can behave very badly, don't use it in any situation
//this is just a demo
*(pt+20) = 77;
*(pt-5) = 3033;
cout << x[20] << ' ' << x[-5];
}
```
----
```
/*OUTPUT---
0x6ffde8 7
0x6ffde0 5
0x6ffde0 5
0x6ffde4 0
0x6ffde8 7
0x6ffdec 9
0x6ffdf0 11
77 3033
------------*/
```
----
## 補充：reference
```cpp=
#include<iostream>
using namespace std;
int main()
{
using namespace std;
//reference : makes 2 names attach to the same variable
int c = 50;
int & d = c; //this is how you define reference
//"reference must be intialized when defined"
//ex:int d;
// int & c;
// c = d //not allowed
cout << "c = " << c << "\td = " << d <<endl;
d++; //so now c is basically d
c++;
cout << "c = " << c << "\td = " << d <<endl;
cout << "&c = " << &c << "\t&d = " << &d <<endl;
int e = 100;
d = e; //what happens if we change reference?
cout << "c = " << c << "\td = " << d << "\te = " << e <<endl;
cout << "&c = " << &c << "\t&d = " << &d << "\t&e = " << &e <<endl;
}
//so clearly, once initialized, cannot be assigned to a different referance again
```
----
```
/*OUTPUT---
c = 50 d = 50
c = 52 d = 52
&c = 0x6ffdf4 &d = 0x6ffdf4
c = 100 d = 100 e = 100
&c = 0x6ffdf4 &d = 0x6ffdf4 &e = 0x6ffdf0
------------*/
```
----
以上的東西競賽中很少用到，不過在某些時刻還是個不錯的工具。對他們有興趣的同學可以自己研究。:)
---
練習題：
[c029.螺旋丸](https://judge.tcirc.tw/ShowProblem?problemid=c026) - 字串與二維陣列的應用
[c020.遞迴縮寫](https://judge.tcirc.tw/ShowProblem?problemid=c020) - 字串基本
[b037.破譯密碼](https://judge.tcirc.tw/ShowProblem?problemid=b037) - 本題為進階資料結構**map**的題目，但是可以用陣列實作看看~
[b053.正確的數字](https://judge.tcirc.tw/ShowProblem?problemid=b053) - 陷阱重重的字串題
[b057.古老的審判](https://judge.tcirc.tw/ShowProblem?problemid=b057) - 有點眼熟...
[d033.最多色彩帶](https://judge.tcirc.tw/ShowProblem?problemid=d033) - 需要一點技巧的陣列題目
----
## 題解：
----
[c029.螺旋丸](https://judge.tcirc.tw/ShowProblem?problemid=c026)
本題稍微有點複雜，如果用數學硬幹應該是解的出來，但是很複雜，我們可以用一個二維陣列去模擬「搓」的過程。
首先我們先設一個足夠大的二維陣列，題目的長度不超過10000，可以設200*200(初始化為0)。
我們訂我們目前所在位置於pos(x,y)，則第一次我們往右走1格，接著往上1格，往下左2格，往下2格.......。很容易找出規律，我們可以儲存以下資訊：
1. 目前字原是字串中第幾字元(i)
2. 目前要往前走的步數(step)
3. 移動的方向(dir)
用一個for迴圈包住，遞增i，每次移動時用for迴圈把第i字元放入二微陣列的pos中，改變pos(往dir方向)，做step次，對於不同方向的移動可以用switch(dir)然後放不同迴圈，當移動完成後，修改step及dir，然後繼續迴圈。記得如果i已經超過字串長度就該跳開while。
然後為了輸出需要，可以在放字元時記錄上、下、左、右界(up,down,left,right)
接下來要輸出：
雙層for，令外層變數為a，內層為b，a = up ~ down，b = left ~ right。
如果發現(a,b)為0，輸出空白，否則就輸出。
注意本題不允許行末空白，每次輸出空白前放一個for檢查到該行的right，如果全是空白就直接換行，否則輸出。
本題稍微有點複雜，需要注意的細節不少。是個有挑戰性的題目。
所以我就把code丟上來方便理解。
註1：memset的用法為memset(指標，元素，大小)
此函數會把指標後面一定大小的記憶體以某元素填充。
註2：min(a,b)回傳a,b之間較小者，max則相反。
code:
```cpp=
#include<iostream>
#include<cstring>
#include<memory>
using namespace std;
int main(){
char maze[200][200];
memset(maze,' ',40000*sizeof(char));
int x = 100,y = 100;
string k;
cin >> k;
int dir = 0;
int step_size = 1;
int nowstepped = 0;
int u = 0,d = 199,l = 199,r = 0;
for(int a = 0;a < k.length();a++){
u = max(y,u);
d = min(y,d);
l = min(x,l);
r = max(x,r);
maze[x][y] = k[a];
if (nowstepped == step_size){
nowstepped = 0;
dir = (dir+1)%4;
if (dir%2 == 0)step_size++;
}
switch(dir){
case 0:{
x++;
break;
}
case 1:{
y++;
break;
}
case 2:{
x--;
break;
}
case 3:{
y--;
break;
}
}
nowstepped++;
}
for(int a = u;a >= d;a--){
for(int b = l;b <= r;b++){
if (maze[b][a] == ' '){
bool doneline = 1;
for(int c = b;c <= r;c++){
if (maze[c][a] != ' '){
doneline = 0;
break;
}
}
if (doneline) break;
else{
for(int c = b;c <= r;c++){
if (maze[c][a] == ' ') cout << ' ';
else{
b = c-1;
break;
}
}
}
}
else cout << maze[b][a];
}
cout << '\n';
}
}
```
----
[c020.遞迴縮寫](https://judge.tcirc.tw/ShowProblem?problemid=c020)
已有題解，不再詳述。至於大寫換小寫的方法請看下一題。
----
[b037.破譯密碼](https://judge.tcirc.tw/ShowProblem?problemid=b037)
本題有考到ASCII的觀念，首先以陣列儲存26個字元的出現次數(初始化為0)，以while依序讀入一個char，令他 = X，一個重要的觀念：英文字母的ASCII實際上是連續的，而且大寫在小寫前面，所以很好得到以下算式：
1. X不是英文字：'A' > X or 'z' < X
2. X是大寫： 'A' <= X and 'Z' >= X
3. 大寫轉小寫： Y = X - 'A' + 'a'
4. 對應index：I = X - 'a'(X為小寫)
只要對不同case執行不同動作(如上)：
case 1: 忽略
case 2: 轉小寫，轉case 3
case 3: 得到index，增加該index的值
最後輸出即可。
----
[b053.正確的數字](https://judge.tcirc.tw/ShowProblem?problemid=b053)
首先用多點側資while，迴圈裡用 getline(cin,str) 取得字串
本題陷阱粉多，以下依序做討論。(以下以NO代替"格式錯誤")
1. 空行 - 直接輸出NO
2. 開頭有"-" - 若size = 1輸出NO
3. 開頭有"0"且不接"."且size > 1 - 輸出NO
4. 從頭掃過字串，若存在非數字，超過一個小數點，或是不在開頭的"-" - break， output NO
5. 若有"."且以"0"結尾，輸出NO
6. 沒有問題則輸出原字串 + 換行
註：0~9的ASCII也是連續的
----
[b057.古老的審判](https://judge.tcirc.tw/ShowProblem?problemid=b057)
[溫習一下~](https://hackmd.io/@JLUgiCEHQH-MmhnsbLJv6A/ByHqnKn8v#)
----
[d033.最多色彩帶](https://judge.tcirc.tw/ShowProblem?problemid=d033)
讀入整條陣列後建一個陣列(cnt)紀錄每個元素的出現次數，先數L個，並紀錄
1. 答案(ans)
2. 目前的顏色數(col)
之後一直將左邊減掉右邊加入直到結束。
注意如果每次做都掃過一次cnt數有多少元素太慢了，會TLE。
只要在每次有元素從0 -> 1，1 -> 0時修改col即可，而ans就是每個col的最大值，可用ans = max(ans,col)更新。
Sign in with Wallet
Connect another wallet