# 陣列 在 [E-game 打寇島](https://www.egame.kh.edu.tw/) 中，並沒有直接提供陣列相關的操作，因此這篇要來探討如何實作陣列。 ## 資料的儲存 我以字串表示陣列，並使用變數儲存字串，使大量的資料得以放入單一變數中，方便操作。 利用顏色積木（字串）與資料（數字）相加，可以把所有資料放入字串中。 ![image](https://hackmd.io/_uploads/S1i8caXO1g.png) 儲存 `1` 到 `9` 的陣列，其值為 `'#000000123456789'`（黑色積木是 `'#000000'`）。 ## 資料的讀取 ### 取得第一個值 假設我們要取得 `array` 最前面的值（`array[0]`），我們可以透過比大小的方式： | 表達式 | 值 | | ---------------------- | ------- | | `array` < `'#0000001'` | `false` | | `array` < `'#0000002'` | `true` | | `array` < `'#0000003'` | `true` | 可以看到我們在 `'#000000'` 後面加上比 `array[0]` 更大的數字時，表達式會不成立。 換句話說，我們只要嘗試至多 `9` 次，就能取得 `array[0]` 的值。 :::info 也可以使用二分搜進行優化，但因為只有 `10` 種可能，效能不會有顯著提升，因此我選擇積木較少的線性搜尋。 ::: ### 取得第二個以後的值 假設我們要取得 `array` 的第 $n+1$ 個值（`array[n]`），我們可以透過同樣的方式（假設 $n=1$）： | 表達式 | 值 | | ----------------------- | ------- | | `array` < `'#00000011'` | `false` | | `array` < `'#00000012'` | `false` | | `array` < `'#00000013'` | `true` | 可以看到我們在取得 `array[n]` 時，手上需要有 `prefix` 儲存 `array[0 ~ n-1]` 的值（此範例中 `prefix` 為 `#0000001`）。 這意味著此陣被隨機訪問的時間複雜度為 $O(n)$。 ### 資料讀取的實作 做一個輔助函數 `array_next()`，回傳 `array` 比 `prefix` 多出的第一個數字。 ![image](https://hackmd.io/_uploads/Hkrx5RQ_Jg.png) > 例如 `array_next('#00000097531', '#000000975')` 會得到 `3`。 然後做一個介面函數 `array_get()`，回傳 `array[index]`。 ![image](https://hackmd.io/_uploads/By7h50mdJe.png) > 例如 `array_get('#00000087654', 1)` 會得到 `7`。 ## 資料的修改 ### 修改陣列中的一個資料 假設要修改 `array[index]` 的值為 `value`，可以宣告一個新陣列 `result`，記錄修改後的陣列。 則 `result` = `array[0 ~ index-1]` + `value` + `array[index+1 ~ 結尾]`。 最後把新陣列 `result` 回傳。 直接上程式碼（積木）： ![image](https://hackmd.io/_uploads/HJSvCCXu1g.png) > 例如 `array_set('#00000087654', 1, 2)` 會得到 `'#00000082654'`。 積木中可以看到，判斷陣列結尾的方式是檢查 `array_next()` 的回傳值是否小於 0，因此還需要一個初始化陣列的函數，幫助我們建立指定長度的陣列。 ## 初始化陣列 ### 初始化一個指定長度的陣列 非常簡單，只要在初始前綴 `'#000000'` 後面補上相應數量的 `'0'` 即可。 ![image](https://hackmd.io/_uploads/rk8PxkNdJl.png) > 例如 `array_init(5)` 會得到 `'#00000000000'`。 ## 使用範例 ### 範例積木 ![image](https://hackmd.io/_uploads/Bke5YkE_Jx.png) ### 範例解釋 ```txt 建立陣列 my_array，大小為 10 將 my_array 的第 2 個元素設為 7 從 my_array 取得第 2 個元素的值，放入變數 value ``` ## 其他事項 ### 複雜度 | 操作 | 時間複雜度 | 空間複雜度 | | ------ | ---------- | ---------- | | 初始化 | $O(n)$ | $O(n)$ | | 遍歷 | $O(n)$ | $O(n)$ | | 存取 | $O(n)$ | $O(n)$ | | 修改 | $O(n)$ | $O(n)$ | ### 限制 * 只能存入數字 0 到 9。 * 遍歷時必須與 `array_next()` 配合，否則時間複雜度將上升為 $O(n^{2})$。 ## 積木 ### array_init ```xml <block type="procedures_defreturn" id="u!_pY}FUDeF[UuXkA0Y!" collapsed="true"><mutation><arg name="size"></arg><arg name="_result"></arg></mutation><field name="NAME">array_init</field><comment pinned="false" h="80" w="160">描述此函數...</comment><statement name="STACK"><block type="variables_set" id="!=T+G3S,i?h(t,)g`N/N"><field name="VAR">_result</field><value name="VALUE"><block type="colour_picker" id="1)i~^M*#wU;N=O^i?)dm"><field name="COLOUR">#000000</field></block></value><next><block type="controls_repeat_ext" id="ktWVM2~JhOP:tM=JmMo1"><value name="TIMES"><block type="variables_get" id="^A#ZLGXQ,{a91f!Xu`5v"><field name="VAR">size</field></block></value><statement name="DO"><block type="variables_set" id="{KCDyiWZ/.erck.F3FP%"><field name="VAR">_result</field><value name="VALUE"><block type="math_arithmetic" id="[(Uawoc~lUj4Mv-u6*1r"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="2@t/Xx/~FrTnj]GO2Xc|"><field name="VAR">_result</field></block></value></block></value></block></statement></block></next></block></statement><value name="RETURN"><block type="variables_get" id="^k~9s75Nvv5,!]60Cz0M"><field name="VAR">_result</field></block></value></block> ``` ### array_next ```xml <block type="procedures_defreturn" id="a%RnJ[E7pwb[|L[.a-3h" collapsed="true"><mutation><arg name="array"></arg><arg name="prefix"></arg><arg name="_i"></arg></mutation><field name="NAME">array_next</field><comment pinned="false" h="80" w="160">描述此函數...</comment><statement name="STACK"><block type="procedures_ifreturn" id=",ONh5~!niZ@J?NnN:bJ="><mutation value="1"></mutation><value name="CONDITION"><block type="logic_compare" id="%=ncJm3liN:9qAZX2shY"><field name="OP">EQ</field><value name="A"><block type="variables_get" id="]I(Zs,~0XHU`R}6g,SD;"><field name="VAR">prefix</field></block></value><value name="B"><block type="variables_get" id="8RtAV:6xt?d1#X_]EknI"><field name="VAR">array</field></block></value></block></value><value name="VALUE"><block type="math_number" id="y0UrksZP#pg;,G-=8R-7"><field name="NUM">-1</field></block></value><next><block type="controls_for" id="/i9Vp*Tg#3qkax`ikxNW"><field name="VAR">_i</field><value name="TO"><block type="math_number" id="%5;,cPOX5KrtC[hiagCq"><field name="NUM">8</field></block></value><statement name="DO"><block type="controls_if" id="d8OChXl9FX-%u5VP9h:w"><value name="IF0"><block type="logic_compare" id="eDb#.FE[_ZZM`ko`SGCM"><field name="OP">GT</field><value name="A"><block type="math_arithmetic" id="J(@E-b7s*:jQ9CJ*R=L;"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="Rsq9[)CI*a!E0iS}5RcM"><field name="VAR">prefix</field></block></value><value name="B"><block type="math_arithmetic" id="sMhUl#5Jkm/Lzznd1vAt"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="]e#pn[A:98XYenLfhlk-"><field name="VAR">_i</field></block></value><value name="B"><block type="math_number" id="uj6As@MV{{15VTy4wjs2"><field name="NUM">1</field></block></value></block></value></block></value><value name="B"><block type="variables_get" id="Eb-,fyMkUhpj])K1.RfJ"><field name="VAR">array</field></block></value></block></value><statement name="DO0"><block type="controls_flow_statements" id="gorS+L4`7uA3(JzuPh2."><field name="FLOW">BREAK</field></block></statement></block></statement></block></next></block></statement><value name="RETURN"><block type="variables_get" id="[)FDlN0?Z|Rg`PkHkir2"><field name="VAR">_i</field></block></value></block> ``` ### array_get ```xml <block type="procedures_defreturn" id="Paq,?jsiTgC2lX=mAXNF" collapsed="true"><mutation><arg name="array"></arg><arg name="index"></arg><arg name="_prefix"></arg></mutation><field name="NAME">array_get</field><statement name="STACK"><block type="variables_set" id="C`oFy%c;#frQiHs:]ONj"><field name="VAR">_prefix</field><value name="VALUE"><block type="colour_picker" id="(q4Ucrkr:7;0asVca^{f"><field name="COLOUR">#000000</field></block></value><next><block type="controls_repeat_ext" id="A8)~!m+.FB#T[bed+GU,"><value name="TIMES"><block type="variables_get" id="WISkD4ZdpKKvBgS_|V#C"><field name="VAR">index</field></block></value><statement name="DO"><block type="variables_set" id="Y}bm%mtqijc6R8qr^=~W"><field name="VAR">_prefix</field><value name="VALUE"><block type="math_arithmetic" id="WdZysV1qLuogES^bI`OD"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="dMmg[[*o5)bxK}OTh,7z"><field name="VAR">_prefix</field></block></value><value name="B"><block type="procedures_callreturn" id="XHd1Z+exW^PV:AL~JPEt"><mutation name="array_next"><arg name="array"></arg><arg name="prefix"></arg><arg name="_i"></arg></mutation><value name="ARG0"><block type="variables_get" id=";[oD*QTP;-iAh;qG(^f7"><field name="VAR">array</field></block></value><value name="ARG1"><block type="variables_get" id="zCHVCW`[s`?P}`l]_P:e"><field name="VAR">_prefix</field></block></value></block></value></block></value></block></statement></block></next></block></statement><value name="RETURN"><block type="procedures_callreturn" id="o6/a=[otBll[TfEa67|0"><mutation name="array_next"><arg name="array"></arg><arg name="prefix"></arg><arg name="_i"></arg></mutation><value name="ARG0"><block type="variables_get" id="S(3Ctg@,@0M}8fV!4=Ew"><field name="VAR">array</field></block></value><value name="ARG1"><block type="variables_get" id="{SfT!is64%7(_p~2pvz|"><field name="VAR">_prefix</field></block></value></block></value></block> ``` ### array_set ```xml <block type="procedures_defreturn" id="vDN3-{WFa6V26|w5Vl{1" collapsed="true"><mutation><arg name="array"></arg><arg name="index"></arg><arg name="value"></arg><arg name="_result"></arg><arg name="_prefix"></arg><arg name="_index"></arg><arg name="_i"></arg></mutation><field name="NAME">array_set</field><comment pinned="false" h="80" w="160">描述此函數...</comment><statement name="STACK"><block type="variables_set" id="IDO+(0R+|#YIO7PBY+mZ"><field name="VAR">_prefix</field><value name="VALUE"><block type="colour_picker" id="B!A^EiEg*D?U2*?t%O=a"><field name="COLOUR">#000000</field></block></value><next><block type="variables_set" id="C^6Y=xJc*%;94q1ZWert"><field name="VAR">_result</field><value name="VALUE"><block type="colour_picker" id="}w2Sh{2Y:l@^M2ceVV_]"><field name="COLOUR">#000000</field></block></value><next><block type="controls_for" id="^E-eB79P%l8r}!@5[]}_"><field name="VAR">_index</field><value name="TO"><block type="math_number" id="(j~/%6iJ*AV`hV]pNJ[}"><field name="NUM">Infinity</field></block></value><statement name="DO"><block type="variables_set" id=",kcjD+ZU~i;Ad!}hRa0s"><field name="VAR">_i</field><value name="VALUE"><block type="procedures_callreturn" id="^q()|CG_}u{Lqy![)uT;"><mutation name="array_next"><arg name="array"></arg><arg name="prefix"></arg><arg name="_i"></arg></mutation><value name="ARG0"><block type="variables_get" id="m#.DLBpR,GhJiOca3+(E"><field name="VAR">array</field></block></value><value name="ARG1"><block type="variables_get" id="}y#UxsXfo4M3_f`ThPWr"><field name="VAR">_prefix</field></block></value></block></value><next><block type="procedures_ifreturn" id="dP@hKZn0,d1@v|qY+k_6"><mutation value="1"></mutation><value name="CONDITION"><block type="logic_compare" id="Ae_tk:D]P6s~n[MqRGqU"><field name="OP">LT</field><value name="A"><block type="variables_get" id="ac*xLHzG)|GpZyo]Q?c2"><field name="VAR">_i</field></block></value></block></value><value name="VALUE"><block type="variables_get" id="^Mi/S~fIf6MJLf}HDGux"><field name="VAR">_result</field></block></value><next><block type="variables_set" id="KgS@P%}K@yap,IYxYk#G"><field name="VAR">_prefix</field><value name="VALUE"><block type="math_arithmetic" id="ll=2-n#(}d@;Nt(kx~0q"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="Qf/?Y]0ANkx^MF3*v7td"><field name="VAR">_prefix</field></block></value><value name="B"><block type="variables_get" id="zTo~YVTnB{/FJxQMVx8*"><field name="VAR">_i</field></block></value></block></value><next><block type="controls_if" id="|8%.]*v1[evdU[jd*#@F"><value name="IF0"><block type="logic_compare" id="|_Kz4+-Iy7i+pj_sUANX"><field name="OP">EQ</field><value name="A"><block type="variables_get" id="QYZePZ5v}k7n;UT21B^!"><field name="VAR">_index</field></block></value><value name="B"><block type="variables_get" id="#;DMcSd8yby]a{@R3=[e"><field name="VAR">index</field></block></value></block></value><statement name="DO0"><block type="variables_set" id="3ai#+QYAhecG+XZi;#s?"><field name="VAR">_i</field><value name="VALUE"><block type="variables_get" id="Saq!}mQup.yNjRoSLSJV"><field name="VAR">value</field></block></value></block></statement><next><block type="variables_set" id="4~5HXYrINo3H+Z*aF7Yo"><field name="VAR">_result</field><value name="VALUE"><block type="math_arithmetic" id="={p14n+jE)Twx`PcgHgi"><field name="OP">ADD</field><value name="A"><block type="variables_get" id="avjVq,V3~]IJZMlPTW4|"><field name="VAR">_result</field></block></value><value name="B"><block type="variables_get" id="OaXq7%VB?7kXJtwm+cb="><field name="VAR">_i</field></block></value></block></value></block></next></block></next></block></next></block></next></block></statement></block></next></block></next></block></statement></block> ```