Sorting Algorithm Animations | Toptal
Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions.
分類: 課程
專題文章
勾選分類為各專題名稱
Android Arduino Control: RGBLED IoT ESP8266 with NetPie
RGBLED IoT ESP8266 with NetPie This Project you can control RGBLED on the internet we call Internet of Things ( IoT )
【程式設計-C#】流程圖
流程圖用來表示一個演算法，其中使用的符號如下圖所示：
成績分等流程圖：
月曆流程圖：
【程式設計-C#】魔方陣
魔方陣的解法/演算法：
設有奇數方陣，3×3, 5×5…, nxn
要將1~nxn的數值填入此方陣中，使得此方陣的各列、各行、斜行/列上的數值加總為相等。
Step 1: 將1置放於方陣的第1列中間位置
設N= 2 … nxn
Step 2: 往左上角找候選的位置來放入N，此時左上角的位置，會有底下2種狀況
狀況1: 左上角的位置跑出陣列外，此時，我們將左上角位置另一端位置做為新候選位置。
狀況2：若候選位置上已經被佔據了(已有數值)，此時，我們將原本數值位置的下方位置，做為新候選位置。
Step 3: 將數值N放入候選位置/新候選位置 (找到的可放置數值位置)。
Step 4：N加1，重覆Step 2與Step 4，直到N等於nxn。
if & 取餘數循環版
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace WindowsFormsApplication2
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void makeMagicMatrix1(int matrixSize)
{
int[,] Matrix = new int[99, 99];
int row = 0;
int col = matrixSize / 2;
Matrix[row, col] = 1;
for (int stepper = 2; stepper <= matrixSize * matrixSize; stepper++)
{
row--;col--; //往左上角移動，二維陣列行與列索引皆減1
//判斷是否出界，小於0為出界的條件
if (row < 0) row = matrixSize - 1;
if (col < 0) col = matrixSize - 1;
if (Matrix[row, col] != 0) //判斷要放置的位處若不是空的話，需要進行倒退的的動作
{
row = (row + 2);
col = (col + 1);
//倒退後，也有可能出界，大於matrixSize-1為出界的條件
if (row >= matrixSize) row = row - matrixSize;
if (col >= matrixSize) col = col - matrixSize;
}
Matrix[row, col] = stepper;
}
string outStrng = "";
for (int i = 0; i < matrixSize; i++)
{
for (int j = 0; j < matrixSize; j++)
{
outStrng += Matrix[i, j].ToString().PadLeft(2, ' ') + " ";
}
outStrng += "\r\n";
}
label2.Text = outStrng;
label2.Location = new Point((this.panel2.Width - label2.Width) / 2, 0); //置中label2
}
private void makeMagicMatrix2(int matrixSize)
{
int[,] Matrix = new int[99, 99];
int row = 0;
int col = matrixSize / 2;
Matrix[row, col] = 1;
for (int stepper = 2; stepper <= matrixSize * matrixSize; stepper++)
{
row = (row - 1 + matrixSize) % matrixSize;
col = (col - 1 + matrixSize) % matrixSize;
if (Matrix[row, col] != 0)
{
row = (row + 2) % matrixSize;
col = (col + 1) % matrixSize;
}
Matrix[row, col] = stepper;
}
string outStrng = "";
for (int i = 0; i < matrixSize; i++)
{
for (int j = 0; j < matrixSize; j++)
{
outStrng += Matrix[i, j].ToString().PadLeft(2, ' ') + " ";
}
outStrng += "\r\n";
}
label2.Text = outStrng;
label2.Location = new Point((this.panel2.Width - label2.Width) / 2, 0); //置中label2
}
private void button1_Click(object sender, EventArgs e)
{
int matrixSize = Convert.ToInt32(textBox1.Text);
makeMagicMatrix1(matrixSize);
}
}
}
2018/10/24 程式碼
const int n = 5;
int[,] M = new int[n, n];
int row = 0, col = n / 2;
M[row, col] = 1; //將1放入第1列中間位置
for (int N = 2; N <= n * n; N++)
{
//狀況1
row = (row - 1 + n) % n; col = (col - 1 + n) % n;
//狀況2
if (M[row, col] != 0) //要放的位置上已經有數值
{
row = (row + 2) % n; col = (col + 1) % n;
}
M[row, col] = N; //將N放入決定好的位置
}
//輸出魔方陣
for (int r = 0; r < n; r++)
{
for (int c = 0; c < n; c++)
{
Console.Write("{0, 4}", M[r, c]);
}
Console.WriteLine();
}
【資料結構】堆疊
堆疊(Stack)是一種後進先出(Last In First Out, LIFO)的有序串列，亦即資料處理的方式都是在同一邊進行，也就是由相同的一端來進行插入與刪除動作。而我們日常生活中，也有一些是堆疊的例子，例如堆盤子、書本裝箱…等，都是一層一層的堆上去，如果想要取出箱子中某一本書，也只能從最上面開始取出。
【定義】
1.一群相同性質元素的組合，即有序串列(ordered List) 。
2.具有後進先出 (Last In First Out, LIFO) 的特性。
3.將一個項目放入堆疊的頂端，這個動作稱為Push(加入)。
4.從堆疊頂端拿走一個項目，這個動作稱為Pop(取出)。
5.Push/Pop的動作皆發生在同一端，則稱此端為Top(頂端)。
6.要取出資料時，則只能從Top(頂端)取出，不能從中間取出資料。
【堆疊的操作示範】
【堆疊常用的操作】
- Push ：加入新項目到堆疊的頂端。
- Pop ：取出堆疊頂端一個項目。
- TopItem ：查看堆疊頂端的項目內容。
- IsEmpty ：判斷堆疊是否為空，若為空則傳回真(True)，否則傳回假(False)。
- IsFull ：判斷堆疊是否為滿，若為滿則傳回真(True)，否則傳回假(False)。
【C#-Stack類別】
Stack.Push 方法 (Object)
using System;
using System.Collections; //C#的Stack所在的命名空間
public class SamplesStack
{
public static void Main()
{
// Creates and initializes a new Stack. 建立並初始化一個新的堆疊
Stack myStack = new Stack();
myStack.Push("The");
myStack.Push("quick");
myStack.Push("brown");
myStack.Push("fox");
// Displays the Stack. //印出堆疊內容
Console.Write("堆疊元素：:");
PrintValues(myStack, '\t'); //呼叫下方PrintValues方法
// Removes an element from the Stack. 從堆疊裏移除一個元素
Console.WriteLine("(Pop)\t\t{0}", myStack.Pop());
// Displays the Stack. 印出堆疊內容
Console.Write("堆疊元素：:");
PrintValues(myStack, '\t');
// Removes another element from the Stack. 從堆疊裏移除另一個元素
Console.WriteLine("(Pop)\t\t{0}", myStack.Pop());
// Displays the Stack. 印出堆疊內容
Console.Write("堆疊元素：:");
PrintValues(myStack, '\t');
// Views the first element in the Stack but does not remove it.
//檢視堆疊裏的第一個元素，但不移除該元素，注意動作與pop不同
Console.WriteLine("(Peek)\t\t{0}", myStack.Peek());
// Displays the Stack.
Console.Write("堆疊元素：:");
PrintValues(myStack, '\t');
}
public static void PrintValues(IEnumerable myCollection, char mySeparator)
{
foreach (Object obj in myCollection) //對每一個在myCollection集合裏的物件obj
Console.Write("{0}{1}", mySeparator, obj);
Console.WriteLine();
}
}
/*
程式輸出：
堆疊元素：: fox brown quick The
(Pop) fox
堆疊元素：: brown quick The
(Pop) brown
堆疊元素：: quick The
(Peek) quick
堆疊元素：: quick The
請按任意鍵繼續 . . .
*/
【堆疊在運算式上的應用】
在日常生活中，我們所使用的四則運算都屬於中序(infix order)運算式，亦即運算子位於兩個運算元之間的表示法。但是，此種表示法電腦並無法直接的處理，因為中序式可能會含有括號，並且運算子可能有不同的優先順序權。因此，若要使用電腦來處理運算式時，則必須要先將「中序式」轉換成「後序式」(postfix order)。
算術式表示的方式有三種：
- 中序(Infix)表示法： A+B
- 前序(prefix)表示法： +AB
- 後序(postfix)表示法： AB-
【中序(Infix)表示法】
【定義】數學上的表示方式，就是屬於中序式，它是把運算子放在兩個運算元的中間。
【表示式】<運算元1 > <運算子> <運算元2 >
【例如】A+B。
【缺點】電腦無法一次依序讀取運算式，因運算式可能含有括號，且未定義運算子優先順序。
【前序 (prefix)表示法】
【定義】指將中序表示法中的運算子和運算元重新調整順序，只是運算子的順序是在運算元前面。
【表示式】<運算子> <運算元1 > <運算元2 >
【例如】+AB。
【後序 (postfix)表示法】
【定義】後序表示法和前序表示法相類似，使得運算子放於運算元後面的表示法。
【表示式】<運算元1 > <運算元2 > <運算子>
【例如】AB+。
【優點】 不必使用括號，方便電腦使用。
【運算式的轉換】
大部份的運算式(expression)都是由運算元(operand)與運算子(operator)所組成。
【例如】A*B+(C/D)-E 其中： A,B,C,D,E為運算元(operand)， +,-,*,/為運算子(operator)
【運算原則】
- 括號內先處理
- 優先權較高的運算子先執行
- 同優先權者，則由結合性，來決定是由左而右，還是由右而左執行。
【中序式→前序式】
假設有一個中序式為：A×B+C×D，欲轉換成前序式，其步驟如下：
1.先用括號將優先順序分出來
((A×B)＋(C×D))
2.將運算子移到左括號右邊
((×AB)＋(×CD))
(＋(×AB)(×CD))
3.把括弧全部拿掉，即為所得。
＋×AB×CD
【中序式→後序式】
假設有一個中序式為：A×B+C×D，欲轉換成後序式，其步驟如下：
1.先用括號將優先順序分出來
((A×B)＋(C×D))
2.將運算子移到右括號左邊
((AB×)＋(CD×))
((AB×)(CD×)＋)
3.把括弧全部拿掉，即為所得。
AB×CD×＋
練習：
1. A+B*C-D/E
Ans: 依優先順序括上括弧
(A+(B*C))-(D/E))
後序式係將運算子移到右括號左邊
(A(BC*)+)(DE/)-)
去掉括弧：
ABC*+DE/-
2. (A+B)*C/(D-E/F)
Ans: 依優先順序括上括弧
(((A+B)*C)/(D-(E/F)))
後序式係將運算子移到右括號左邊
(((AB+)C*)(D(EF/)-)/)
去掉括弧：
AB+C*DEF/-/
後序式求解：
設A=1, B=2, C=3, D=4, E=5, F=2，求下面後序式的值為何？
1．AB*C-DE**
=(((AB*)C-)(DE*)*)
=(((A*B)-C)*(D*E))
=(((1*2)-3)*(4*5))
=-20
2．ABC*+DE/-
=((A(BC*)+)(DE/)-)
=((A+(B*C))-(D/E))
=((1+(2*3))-(4/5))
=1+6-0.8
=6.2
3．AB+C*DEF/-/
=(((AB+)C*)(D(EF/)-)/)
=(((A+B)*C)/(D-(E/F)))
=(((1+2)*3)/(4-(5/2)))
=3*3/(4-2.5)
=9/1.5
=6
以上方法是我們人員用來進行的中序轉後序/前序的快速方法，應付考試相當快捷，但是，若要用程式來實現轉換方法，需要特定的資料結構來協助，一般來說有二種作法：堆疊與二元樹。
考試時，一般不會考程式，所以不用特別注意堆疊的演算法，大家要記得的是去括弧法與二元樹法。(考試必考！)
【C# – 中序到後序的轉換程式】
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Infix
{
class Program
{
static bool InfixToPostfixConvert(ref string infixBuffer, out string postfixBuffer)
{
int priority = 0;
postfixBuffer = "";
Stack<Char> s1 = new Stack<char>();
for (int i = 0; i < infixBuffer.Length; i++)
{
char ch = infixBuffer[i];
if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
// check the precedence
if (s1.Count <= 0)
s1.Push(ch);
else
{
if (s1.Peek() == '*' || s1.Peek() == '/')
priority = 1;
else
priority = 0;
if (priority == 1)
{
if (ch == '+' || ch == '-')
{
postfixBuffer += s1.Pop();
i--;
}
else
{ // Same
postfixBuffer += s1.Pop();
i--;
}
}
else
{
if (ch == '+' || ch == '-')
{
postfixBuffer += s1.Pop();
s1.Push(ch);
}
else
s1.Push(ch);
}
}
}
else
{
postfixBuffer += ch;
}
}
int len = s1.Count;
for (int j = 0; j < len; j++)
postfixBuffer += s1.Pop();
return true;
}
static void Main(string[] args)
{
string infixBuffer = "";
string postfixBuffer = "";
if (args.Length == 1)
{
infixBuffer = args[0];
InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
System.Console.WriteLine("InFix :\t" + infixBuffer);
System.Console.WriteLine("PostFix:\t" + postfixBuffer);
}
else
{
infixBuffer = "a+b*c";
InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
System.Console.WriteLine("InFix :\t" + infixBuffer);
System.Console.WriteLine("PostFix:\t" + postfixBuffer);
System.Console.WriteLine();
infixBuffer = "a+b*c/d-e";
InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
System.Console.WriteLine("InFix :\t" + infixBuffer);
System.Console.WriteLine("PostFix:\t" + postfixBuffer);
System.Console.WriteLine();
infixBuffer = "a+b*c/d-e+f*h/i+j-k";
InfixToPostfixConvert(ref infixBuffer, out postfixBuffer);
System.Console.WriteLine("InFix :\t" + infixBuffer);
System.Console.WriteLine("PostFix:\t" + postfixBuffer);
System.Console.WriteLine();
}
}
}
}
/* 程式輸出
中序 : a+b*c
後序: abc*+
中序 : a+b*c/d-e
後序: abc*d/+e-
中序 : a+b*c/d-e+f*h/i+j-k
後序: abc*d/+e-fh*i/+j+k-
請按任意鍵繼續 . . .
*/
【程式設計-C#】Array陣列的操作
陣列的排序
Array.Sort() 方法
可用來對指定的一維陣列物件由小而大做遞增排序。
語法1：將一維陣列物件中的元素做由小到大排序 ：將一維陣列物件中的元素做由小到大排序
Array.Sort(陣列物件);
語法2：
用來將 陣列物件1 中的元素做由小到大排序，
且 陣列物件2 的元素會隨著 陣列物件1 的
索引位置跟著做排序的動作。
Array.Sort(陣列物件1, 陣列物件2);
陣列的反轉
Array.Reverse() 方法
用來反轉整個一維陣列的順序。
上例用Array.Sort() 方法對指定陣列由小而大遞增排序。
若希望改由大而小作遞減排序，需再將已做完遞增排序
的陣列再用 Array.Reverse() 方法即可將陣列由大而小
作遞減排序。
Array.Reverse() 語法：
Array.Reverse(陣列物件);
Array.Sort(avg);
Array.Reverse(avg);
若同時有兩個相關陣列 name 和 avg，若以 avg 陣列
為基準由大而小做遞減排序，相關陣列需要同時 ，相關陣列需要同時反轉，
寫法：
Array.Sort(avg,name);
Array.Reverse(avg);
Array.Reverse(name);
陣列的搜尋
.NET Framework 類別程式庫的 Array 類別提供
1. Array.IndexOf()方法
2. Array. BinarySearch() 方法
用來搜尋某個資料是否在陣列物件中。
1. Array.IndexOf()方法
使用 Array.IndexOf 可用來搜尋陣列中是否有相符
資料。
若有找到，則會傳回該陣列元素的註標值。
若沒有找到，會傳回-1。
語法：
Array.IndexOf(陣列名稱 ,查詢資料 [ ,起始註標] [ ,查詢距離] );
{“Jack”,”Tom”,”Fred”,”Mary”,”Lucy”, “Jane” }
共六個陣列元素，觀察下列各陳述式輸出結果：
Array.IndexOf(name,”Tom”);
[結果] 由註標0開始找起，傳回值為1。
Array.IndexOf(name, ”Tom”, 3) ;
[結果] 由註標3開始找起，傳回值為-1。
若str1=”Lucy” , start=1, offset=2
Array.IndexOf(name, str1, start, offset);
[結果] 由註標1開始往下找2個陣列元素的內容是否
有 ”Lucy” 字串。傳回值為-1。
2. Array.BinarySearch()方法
– 用來搜尋陣列中的資料，陣列未經排序 ，陣列未經排序，每次
搜尋資料都由最前面開始，資料量大時，愈後
面的資料查詢所花費的時間愈多，資料平均搜
尋時間不平均。
– 為不管資料前後次序，使得資料平均搜尋時間都
差不多，在 .NET Framework 類別程式庫另提供
此二分化搜尋方法來搜尋資料是否在陣列中。
– 此方法使用前陣列 才可使用
適用於資料量大的陣列。
語法：Array.BinarySearch(陣列名稱, 查詢資料);
陣列的拷貝
將某個陣列複製給另一個陣列時，可用 Array.Copy()
方法進行拷貝陣列。
語法：
Array.Copy (srcAry , srcIndex , dstAry , dstIndex , length );
srcAry ：來源陣列即被拷貝的陣列。
srcIndex：代表 srcAry 來源陣列的註標，由指定的註標開始複製。
dstAry ：接收資料的目的陣列。
dstIndex：代表 dstAry 目的陣列的註標，由指定的註標開始儲存。
length ：表示要複製的陣列元素個數。
陣列的清除
當需要將某個陣列中指定範圍內的陣列元素的內容
清除，可透過 Array.Clear() 方法。語法：
Array.Clear(aryname, startindex, length);
【例1】將 myary 陣列中，註標為 3~4 陣列元素的內容
清除， 寫法：
Array.Clear(myary, 3, 2);
【例2】 將 myary 陣列中所有陣列元素的內容清除，
假設該 陣列共有六個陣列元素。寫法：
Array.Clear(myary, 0, 6);
【資料結構】陣列
陣列的觀念
【定義】陣列是指一群具有相同名稱及資料型態的變數之集合。
【特性】
- 佔用連續記憶體空間。
- 用來表示有序串列之一種方式。
- 各元素的資料型態皆相同。
- 支援隨機存取(Random Access)與循序存取(Sequential Access)。
- 插入或刪除元素時較為麻煩。因為須挪移其他元素。
【優點】
(1)利用註標（Index）可以快速的輸入資料。
輸入：for(i=0;i<5;i++) //利用「迴圈結構」
A[i]=i*2+1; //快速「輸入資料」到「陣列」中
(2) 利用註標（Index）一次可以輸出大批的資料。
輸出：for(i=0;i<5;i++) //利用「迴圈結構」
WriteLine(A[i]); //從「陣列」一次「輸出大批」的資料
【定義】宣告陣列時，其括弧內的「註標」個數，只有一個時稱為「一維陣列」。在一維陣列中，常使用的運算指令有五種。
- 讀取(Read)
- 寫入(Write)
- 插入(Insert)
- 刪除(Delete)
- 複製(Copy)
讀取(Read)
【定義】利用註標（Index）來「讀取」資料。
【例如】將A陣列的第二個元素放到X目的變數中。
【寫法】X= A[1]; //陣列的註標是從0開始
【圖解】
寫入(Write)
【定義】利用註標（Index）來「寫入」資料。
【例如】將數值50寫入到陣列的第二個索引位置中。
【寫法】A[1]=50; //陣列的註標是從0開始
【圖解】
插入(Insert)
【定義】在指定的註標 i 的位置插入一項新元素，原來註標 i 和之後的元素都必須要再往後挪移一個位置。
【例如】將在註標1的位置插入一項新元素(15)。
【演算法】
Procedure ArrayInsert(int A[],int Max,int i ,int value)
Begin
If(i>0 && i<=Max) //判斷欲插入位置i是否存在，如果有，則
{
for(count=Max-1;count>i;count--) //i位置及後面的元素逐一往後挪
A[count]=A[count-1];
A[i]=value; //最後再將新元素插入到第i位置
}
Else //如果欲插入位置i不存在，則
Return 0; //傳回0
End
End Procedure
【圖解】
【說明】
首先將30往後挪移一個位置，再將A[1]的元素20，往後挪移放到A[2]位置中，最後再插入15到A[1]中。
刪除(Delete)
【定義】指刪除指定的註標 i 位置的元素，原來註標 i的元素被刪除，為了避免浪費記憶體空間，因此，之後的元素都必須要再往前挪一個位置。
【例如】將在註標1的位置刪除一項舊元素(20)。
【演算法】
Procedure ArrayDelete(int A[],int Max,int i)
Begin
If(i>0 && i<=Max) //判斷欲刪除元素位置i是否存在，如果有，則
{
for(count=i;count<Max-1;count++) //i位置後面的元素逐一往前挪
A[count]=A[count+1];
A[Max-1]=0; //最後再將0放到最後一個位置
}
Else //如果欲插入位置i不存在，則
Return 0; //傳回0
End
End Procedure
【圖解】
【說明】 首先將A[1]的元素20刪除，再將A[2]的元素30往前挪移一個位置，最後再寫入0到A[2]中。
複製(Copy)
【定義】指將「來源陣列」的元素內含值全部逐一copy到「目的陣列」。
【例如】將A陣列的元素內含值全部逐一copy到B陣列中。
【演算法】
Procedure ArrayCopy(int A[],int B[], int Max)
Begin
If(Max>0) //判斷陣列是否有元素內含值，如果有，則
{
for(count=0;count<Max-1;count++) //A陣列全部逐一copy到B陣列
B[count]=A[count];
}
Else //如果陣列沒有元素，則
Return 0; //傳回0
End
End Procedure
【圖解】
【說明】
A陣列的元素內含值全部逐一copy到B陣列中，例如A[0]元素會被copy到B[0]中，A[1]元素放到B[1]中，以此類推。
陣列的宣告
(1) 變數宣告
int A, B, C; //宣告三個變數(A,B,C)為整數型態
以上三個變數與變數之間都是個別獨立的記憶體空間。
(2) 陣列宣告
int A[3]; //宣告一維陣列A，共有A[0]、A[1]、A[2]三個元素
以上三個記憶體空間，可以讓我們連續儲存多項資料，並且資料與資料之間都是按照順序排列的記憶體空間。
陣列的儲存方式
【定義】陣列名稱之後加上“註標”即可存取陣列元素。
【舉例】宣告一個A[3]的陣列，並分別儲存10,20,30
C#
Procedure ArrayCopy(int A[],int B[], int Max)
Begin
If(Max>0) //判斷陣列是否有元素內含值，如果有，則
{
for(count=0;count<Max-1;count++) //A陣列全部逐一copy到B陣列
B[count]=A[count];
}
Else //如果陣列沒有元素，則
Return 0; //傳回0
End
End Procedure
【實例】請依序輸入六位同學的成績到陣列中，並計算及輸出「總和」
第一種寫法：使用陣列，但未使用for迴圈演算法
int A[6] = {100, 98, 88, 67, 75, 90};
int sum = A[0] + A[1] + A[2] + A[3] + A[4] + A[5];
Console.WriteLine("總和為：" + Sum);
第二種寫法：使用陣列，並且使用for迴圈演算法 (最佳)
int A[6] = {100, 98, 88, 67, 75, 90};
int sum = 0;
for (int i = 0; i < 6; i++) {
sum = sum + A[i];
}
Console.WriteLine("總和為：" + Sum);
二維陣列的觀念
在前面所介紹一維陣列，可以視為直線方式來存取資料，這對於一般的問題都可以順利的處理，但是對於比較複雜的問題時，那就必須要使用二維陣列來處理。否則會增加程式的複雜度。
例如：計算4位同學的5科成績之總分與平均的問題。
【定義】宣告陣列時，其括弧內的「註標」個數，有兩個時稱為「二維陣列」。
【語法】資料型態 陣列名稱[M][N];
【說明】M代表列數，N代表行數
【存取方法】利用二維陣列中的兩個註標來表示。
多維陣列的觀念
【定義】宣告陣列時，其括弧內的「註標」個數，是二個以上時，就稱為「多維陣列」。其中最常見是三維陣列，其圖形為三度空間的立體圖形，並且我們可以將三維陣列視為多個二維陣列的組合。
【語法】資料型態 陣列名稱[L][M][N];
【說明】L代表二維陣列個數，M代表列數，N代表行數
【舉例】設計有某一個大學，3次月考，全班4位同學的5科目成績時。利用三維陣列來存取每人學生的成績。
【說明】
此例子中Score陣列共有三個註標，故Score陣列是一個三維 陣列。
//其中，第一個註標為：二維陣列的個數： 0~2 共有3個二維陣列
第二個註標為：列註標表示範圍： 0~3 共有4列
第三個註標為：行註標表示範圍： 0~4 共有5行
【圖解】
【說明】宣告Score是由3個(0~2)二維陣列，每個二維陣列包含4列 (0~3)，5行(0~4)組合而成的整數三維陣列。並且共計有3×4×5＝60元素。
陣列在記憶體中的表示法
陣列是由一連串的記憶體組合而成，其陣列元素之儲存位址計算，
大致上，可分為一維陣列與二維陣列來說明：
Ⅰ. 一維陣列
[題目1]若陣列A有N個元素，其陣列的起始位址為Lo，並且索引值從0開始，d 為元素大小，則A[i]的起始位置為多少？
令：Lo為起始位址，d為元素大小，則A[i]之位置計算=Lo+i*d。
【舉例】假設每一個整數佔用2個byte，若A陣列的起始位址是100開始，則A[5]的起始位址為多少？
令：起始位址Lo=100
元素大小d=2
則A[5]之位置計算=Lo+i*d =100+5*2=100+10=110
[題目2]若陣列A的索引從L到U，其陣列的起始位址為Lo， d為元素大小，則A[i]的起始位置為多少？
宣告方式：A[L…U]
令：Lo為起始位址，d為元素大小，則A[i]之位置計算=Lo+(i-L)*d
【舉例】假設每一個整數佔用2個byte，若A[10]起始位址是200開始，則A[20]的位址為多少？
令：Lo起始位址=200 ，d元素大小=2
則A[20]之位置計算=Lo+(i-L)*d =200+(20-10)*2=200+10*2=220
二維陣列
宣告方式：A[0…M-1, 0…N-1]， 其中：M代表列數(Row)，橫向，N代表行數(Column)，縱向。所以，共有M*N格。
說明：¡圖的儲存位置：A[1,4]，△圖的儲存位置：A[2,1]，o圖的儲存位置：A[M-1,N-2]
Row-major(以列為主)
【定義】以列為主的二維陣列要轉為一維陣列時，是將二維陣列「由上往下」一列一列讀入一維陣列。亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主記憶體的存儲方式。
【圖解】
【以列為主的儲存公式】
令Lo為起始位址，d為元素大小，則二維陣列A[i,j]位置會儲存到一維陣列的那一個位置呢？
公式=Lo+[i*N+j]*d
Column-major(以行為主)
【定義】以行為主的二維陣列要轉為一維陣列時，必須將二維陣列「由左往右」一行一行讀入一維陣列。亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主記憶體的存儲方式。
【圖解】
【以行為主的儲存公式】
令Lo為起始位址
d為元素大小
則二維陣列A[i,j]位置會儲存到一維陣列的那一個位置呢？
公式=Lo+[j*M+i]*d
多項式(polynomials)
多項式(polynomial)的表示式為
其中Ai為非零項的係數，且多項式的每一項均使用三個欄位來表示(分別為 coef, exp, link) 。其節點的資料結構如下所示：
其中：Coef：表示該變數的係數
Exp：表示該變數的指數
Link：表示指向下一個節點的指標
【表示方法】
【方法一】依照指數高低依序儲存係數
【作法】假設最高指數為n，則準備一個一維陣列A[1..n+2]，
其內容如下：
【練習】假設f(x)=7X4+5X2+3X
因為最高指數為4，則準備一個一維陣列A[1..6]，
【解答】
步驟一：準備一個一維陣列A[1..6]
步驟二：存入最高指數及分別存入Xn, Xn-1,…,X0之係數
【優點】
(1)只要儲存係數，比較節省儲存指數空間。
(2)適用於零項次較少的多項式。
【缺點】
不適用於零項次極多的多項式，儲存時非常浪費空間。
Ex: f(X)=5X100+1
則必須要準備一個一維陣列A[1..102]，在實際使用上只用了3格，因此，會浪費99格。
【方法二】只儲存非零項次的係數與指數
【作法】假設多項式有K個非零項次，則準備一個一維陣列A[1..2K+1]，其內容如下：
【練習】假設f(X)=5X100+1
因為有2個非零項次，則準備一個一維陣列A[1..5]
【解答】
步驟一：準備一個一維陣列A
步驟二：存入K 、係數及指數
【優點】適用於零項次極多的多項式。
【缺點】當非零項次極多時，不適用。
矩陣(Matrices)
【定義】
類似二維陣列，它是利用一個m × n矩陣來表示這個矩陣擁有
m列（Rows）和n行（Columns）。
一般而言，資料結構上常用到的矩陣有四種：
- 矩陣轉置(Matrix Transposition)
- 矩陣相加(Matrix Addition)
- 矩陣相乘(Matrix Multiplication)
- 稀疏矩陣(Sparse Matrix)
矩陣轉置(Matrix Transposition)
【定義】
假設有一個(m × n)矩陣A，則我們可以將A矩陣轉置為(n × m)的B矩陣，並且B矩陣的第j列第i行的元素等於A矩陣的第i列第j行的元素，
以數學式來表示為：Bji=Aij
【假設】A矩陣與B矩陣的m與n都是從1開始計算，因此，A,B矩陣的表示如下：
說明：A矩陣的第i列第j行的元素等於B矩陣的第j列第i行的元素
【演算法】
Procedure Matrix_Transpose(int m, int n, int A[m][n], int B[n][m])
Begin
for(i = 1; i <= m; i++) //外迴圈，先掃瞄第1列到第m列
for(j = 1; j <= n; j++) //內迴圈，再掃瞄第1行到第n行
//將A陣列的第i列第j行的元素放到B陣列的第j列第i行的元素中
B[j][i] = A[i][j];
End
End Procedure
矩陣相加(Matrix Addition)
【定義】
假設A,B都是(m × n)矩陣，則我們可以將A矩陣加上B矩陣以得到一個C矩陣，並且此C矩陣亦為(m × n)矩陣。因此：
在C矩陣上的第i列第j行的元素必定等於A矩陣的第i列第j行的元素加上B矩陣的第i列第j行的元素。
以數學式來表示為：Cij= Aij+Bij
【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩陣相加等於C矩陣，其表示如下：
【演算法】
Procedure Matrix_Add(int m, int n, int A[m][n], int B[m][n], int C[m][n]) Begin for(i = 1; i <= m; i++) //外迴圈，先掃瞄第1列到第m列 for(j = 1; j <= n; j++) //內迴圈，再掃瞄第1行到第n行 /*將A陣列的第i列第j行的元素加上B陣列的第i列第j行的元素之後， 放到C陣列的第i列第j行的元素中 */ C[i][j] = A[i][j] + B[i][j]; End End Procedure
矩陣相乘(Matrix Multiplication)
【定義】
假設A為(m × n)矩陣，而B為(n × p)矩陣，則我們可以將A矩陣乘上B矩陣以得到一個(m × p)的C矩陣，因此，在C矩陣上的第i列第j行的元素必定等於A矩陣的第i列乘上B矩陣的第j行(兩個向量的內積)，以數學式來表示為：
【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩陣相乘等於C矩陣，其表示如下：
【演算法】
Procedure Matrix_Mul(int m, int n, int p, int A[m][n], int B[n][p], int C[m][p])
Begin
for(i = 0; i < m; i++) //外迴圈，先掃瞄第1列到第m列
for(j = 0; j < n; j++) //內迴圈，再掃瞄第1行到第n行
{
C[i][j]=0;
/*將A矩陣的第i列第j行的元素加上B矩陣的第i列第j行的
元素的結果放到C矩陣上的第i列第j行的元素中*/
for(k=0;k<p;k++)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
}
End
End Procedure
C#程式
#include <iostream>
void MultiplyWithOutAMP() {
int aMatrix[3][2] = {{1, 4}, {2, 5}, {3, 6}};
int bMatrix[2][3] = {{7, 8, 9}, {10, 11, 12}};
int product[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
// Multiply the row of A by the column of B to get the row, column of product.
for (int inner = 0; inner < 2; inner++) {
product[row][col] += aMatrix[row][inner] * bMatrix[inner][col];
}
std::cout << product[row][col] << " ";
}
std::cout << "\n";
}
}
void main() {
MultiplyWithOutAMP();
getchar();
}
稀疏矩陣(Sparse Matrix)
【定義】 是指矩陣中大部份元素都沒有使用，元素稀稀落落，所以稱為稀疏矩陣。
【概念】在M × N 的矩陣中，多數的資料值為０。
【處理方法】
【方法一】直接利用M × N的二維陣列來一一對應儲存。
【缺點】
1. 浪費空間：因為多數為０。
2. 浪費時間：因為要處理一些不必要的計算。
【方法二】利用3-tuple結構來儲存非零元素
【作法】假設有一個M*N的稀疏矩陣中共有K個非零元素，則必須要準備一個二維陣列A[0..K,0..2]
【資料結構-題庫】陣列
1.陣列是一組變數的集合，而這些變數：
(A) 具有不同的資料型態，並且分散存在記憶體空間
(B) 具有相同的資料型態，並且分散存在記憶體空間
(C) 具有相同的資料型態，並且線性相鄰的存在記憶體空間
(D) 具有不同的資料型態，並且線性相鄰的存在記憶體空間
2.有關陣列下列那一項敘述有誤？
(A)佔用連續記憶體空間
(B)插入或刪除元素非常容易
(C)各元素的資料型態皆相同
(D)支援隨機存取(Random Access)與循序(Sequential Access)
3.存取陣列中的元素時，需指定要存取元素在陣列中的？
(A)記憶體位址
(B)索引編號
(C)元素值
(D)以上皆可
4.在一維陣列中，常使用的運算指令有五種，下列那一種不是？
(A)讀取(Read)
(B)寫入(Write)
(C)複製(Copy)
(D)貼上(Past)
5.在一維陣列中，那一個運算指令執行時，會往後挪一個位置？
(A)讀取(Read)
(B)寫入(Write)
(C)刪除(Delete)
(D)插入(Insert)
6.假設有n個整數利用陣列(Array)儲存，將存放於最前面及最後面的資料印出時，請問所需之時間複雜度以下列何者表示最為適當？
(A)O(1)
(B)O(log n)
(C)O(n)
(D)O(n2)
7.假設有一陣列A儲存已排序的n個數字資料，刪除最大數值的資料需多少時間？
(A)O(1)
(B)O(log n)
(C)O(n)
(D)O(n2)
8.假設有一陣列A儲存已排序好的資料(a1,a2,…,an)，請問下列何者錯誤？
(A)找第k大的資料需要O(log n)
(B)刪除需要O(n)的時間
(C)插入需要O(n)的時間
(D)以上皆非
9.請問在陣列中「讀取」某一元素的時間複雜度為何？
(A)O(1)
(B)O(log n)
(C)O(n)
(D)O(n2)
7.請問在陣列中「寫入」某一元素的時間複雜度為何？
(A)O(1)
(B)O(log n)
(C)O(n)
(D)O(n2)
8.假設有一陣列A儲存已排序的n個數字資料，請問「插入」某一元素的時間複雜度為何？
(A)O(1)
(B)O(log n)
(C)O(n)
(D)O(n2)
9.假設有一陣列A儲存已排序的n個數字資料，請問「刪除」某一元素的時間複雜度為何？
(A)O(1)
(B)O(log n)
(C)O(n)
(D)O(n2)
10.假設有一陣列A陣列的元素內含值欲全部逐一複製到B陣列中，請問時間複雜度為何？
(A)O(1)
(B)O(log n)
(C)O(n)
(D)O(n2)
11. 關於「變數宣告」與「陣列宣告」的敘述，下列何者有誤？
(A) 變數宣告時，會產生不連續的記憶體空間的配置
(B) 變數宣告時，會產生連續的記憶體空間的配置
(C) 陣列宣告時，會產生連續的記憶體空間的配置
(D) 變數宣告時，變數與變數之間都是個別獨立的記憶體空間。
12.在陣列宣告時，如果宣告int A[10];，請問陣列註標的範圍為多少？
(A) A[0]、A[1]、A[2],…,A[10]
(B) A[0]、A[1]、A[2],…,A[9]
(C) A[1]、A[2],…,A[10]
(D) A[1]、A[2],…,A[11]
13.有一整數陣列int A[0…29] ; （假設int資料型態佔用2個位元組），則此陣列共佔多少位元組？
(A) 40
(B) 30
(C) 4
(D) 60
14.陣列A[註標]中，註標不可為：
(A)整數
(B)運算式
(C)變數
(D)字串
【2-3 二維陣列的觀念，以下不在期中考的範圍內】
1.二維陣列宣告int Score[23]，陣列中含有多少元素：
(A)2
(B)3
(C)6
(D)12
2.若有一個二維陣列A[1..5][2…3]，假設其中存放的每個元素佔2byte，則在記憶體中存放A陣列需要多少bytes？
(A)10
(B)20
(C)30
(D)40
3.在BASIC 語言中宣告陣列為Dim A(5,6)，試問陣列A 中有多少個元素？
(A)42個
(B)36 個
(C)35個
(D)30 個
4.有一整數二維陣列int A[0…29, 0…19]; （假設int資料型態佔用2個位元組）， 則此陣列共佔多少位元組？
(A) 20 (B) 30 (C) 600 (D) 1200
5.執行下列BASIC程式片段時，請問陣列A佔用記憶體多少bytes的儲存空間？
Dim A ( 3 , 4 ) As Double
(A)48 (B)96 (C)80 (D)160
2-4 多維陣列的觀念
1.有一個整數陣列int Score[3][4][5]，假設sizeof(int)=2，請問此陣列共佔多少位元組? (A) 60 (B) 120 (C) 180 (D) 240
2.在我們撰寫程式時，不小心時常發生陣列的「subscript out of range」的錯誤訊息時，它是表示程式執行時遇到那一種狀況？
(A) 語法錯誤
(B) 記憶體存取錯誤
(C) 整數的overflow
(D) 整數的underflow
3.有一個整數陣列int A[8][10][5]，假設sizeof(int)=1，請問此陣列共佔多少位元組?
(A) 112 (B) 400 (C) 800 (D) 1600
2-5 陣列在記憶體中的表示法
1.有一整數陣列int A[0…29]; （假設int資料型態佔用2個位元組），若A[0]在記憶體中的位址為100，則元素A[21] 的起始位址為何？
(A) 84 (B) 100 (C) 120 (D) 142
2.有一整數陣列int A[0…29]; （假設int資料型態佔用2個位元組），若A[5]在記憶體中的位址為100，則元素A[21] 的起始位址為何？
(A) 16 (B) 21 (C) 132 (D) 142
3.有一整數二維陣列int A[0…9, 0…9]; 則第二列第五行的儲存位置如何表示？
(A) A[2,5] (B) A[1,4] (C) A[3,6] (D) A[1,5]
4.若陣列A 之宣告為DIM A(2,3) As Integer，A 之內容如圖所示，執行
Print A(A(1,2)-1,A(2,3)+1)指令後，答案為何？
(A)1 (B)0 (C)3 (D)2
2-5.1 Row-major(以列為主)
1.假設一個二維陣列A[1…5, 1…6]，如果以列為主，則A(3,3)排在第幾個？
(A)13 (B)14 (C)15 (D)16
2.陣列A共有6列8行資料，以列為主儲存在記憶體中，A[1,1]起始位址為20。假設陣列每份資料佔2個記憶單位，則第3列第6行的位址為何？
(A)62 (B)64 (C)66 (D)68
3.陣列A共有6列8行資料，以列為主儲存在記憶體中，A[0,0]起始位址為20。假設陣列每份資料佔2個記憶單位，則第3列第6行的位址為何？
(A)80 (B)82 (C)84 (D)88
4.給予一個二維陣列A[-4..3, -3..2]，Lo=100, d=1，採用Row-major方式，請計算A[2,2]的位置。
(A)140 (B)141 (C)146 (D)143
2-5.2 Column-major(以行為主)
1.假設一個二維陣列A[1…5, 1…6]，如果以行(Column)為主，則A(3,3)排在第幾個？
(A)13 (B)14 (C)15 (D)16
2.陣列A共有6列8行資料，以行為主儲存在記憶體中，A[1,1]起始位址為20。假設陣列每份資料佔2個記憶單位，則第3列第6行的位址為何？
(A)82 (B)84 (C)86 (D)88
3.陣列A共有6列8行資料，以行為主儲存在記憶體中，A[0,0]起始位址為20。假設陣列每份資料佔2個記憶單位，則第3列第6行的位址為何？
(A)90 (B)92 (C)94 (D)98
4.給予一個二維陣列A[-4..3, -3..2]，Lo=100, d=1，採用以行為主方式，請計算A[2,2]的位置。
(A)140 (B)141 (C)146 (D)143
2-6 多項式(polynomials)
1.假設多項式為：f(x)=7X5+5X2+3X+1，請依照指數高低依序儲存係數於一維陣列中，並寫出其內容？
2.假設多項式為：f(x)=7X5+5X2+3X，請儲存非零項次的係數與指數於一維陣列中，並寫出其內容？
2-7 矩陣(Matrices)
1.關於資料結構中的矩陣單元之敘述，下列何者正確？
(A)矩陣類似二維陣列
(B)矩陣是利用一個m × n陣列來表示
(C)矩陣是由m列（Rows）和n行（Columns）所組成。
(D)以上皆是
2.下列何者不是資料結構中所探討的矩陣？
(A)矩陣轉置
(B)矩陣相加
(C)矩陣相乘
(D)矩陣相除
2-7.1 矩陣轉置(Matrix Transposition)
1.假設有一個(m × n)矩陣A，如果將A矩陣轉置為(n × m)的B矩陣時，
其時間複雜度為：
(A) O(m2)
(B) O(m × n )
(C) O(n2)
(D) O(m + n )
- 將原矩陣中的行座標元素與列座標元素相互調換，此現象稱為？
(A) 矩陣轉移
(B) 矩陣轉動
(C) 矩陣交換
(D) 矩陣轉置
3.假設有一個(m × n)矩陣A在轉置之後儲存到B矩陣中，請問在撰寫程式時，其主要的指令為何？(設定i=1~m, j=1~n)
(A) B [j][i] = A [i][j]
(B) A[j][i] = B [i][j]
(C) B [i][j] = A [i][j]
(D) B[j][i] = A[j][i]
2-7.2 矩陣相加(Matrix Addition)
- 將A矩陣內的元素與B矩陣內的元素相加之後，存放到C矩陣，此現象稱為？
(A) 矩陣合併
(B) 矩陣相加
(C) 矩陣結合
(D) 矩陣合成
- 假設A,B都是(m × n)矩陣，則我們可以將A矩陣加上B矩陣以得到一個C矩陣，並且此C矩陣亦為(m × n)矩陣，其主要的指令為何？
(設定i=1~m, j=1~n)
(A) C[i][j] = A[i][j] + B[i][j]
(B) C[i][j] = A[j][i]+B [i][j]
(C) C[i][j] = B [j][j] +A [j][j]
(D) C[i][j] = B[j][i]+A[j][i]
2-7.3 矩陣相乘(Matrix Multiplication)
1.兩個矩陣A: m×n, B: n×p相乘，其時間複雜度為：
(A) O(n3) (B) O(mnp) (C) O(n2) (D) O(n4)
- 假設想要將A矩陣(m × n)內的元素與B矩陣(n × p)內的元素相乘之後，存放到C矩陣，請問C矩陣要提供「幾列幾行」才能存放呢？
(A) (m × n)
(B) (n × p)
(C) (m × n)
(D) (m × p)
2-7.4 稀疏矩陣(Sparse Matrix)
1.假設一矩陣A有12(4×3)個元素，其中只有2個非零元素，請問其矩陣的使用率為何？
(A)1/3 (B)1/4 (C)1/5 (D)1/6
2.假設有一個m×n的整數矩陣，其中有k個非零元素。如果用陣列來儲存這個
稀疏矩陣(Sparse Matrix)的k個非零元素。請問我們需要多少儲存整數的記憶體？
(A)k (B)2k+1 (C)3(k+1) (D)4k
3.假設有一個m×n的整數矩陣，其中有2個非零元素。如果用陣列來儲存這個
稀疏矩陣(Sparse Matrix)的2個非零元素。請問我們需要多少儲存整數的記憶體？
(A)2 (B)5 (C)9 (D)10
4.假設有一個矩陣，其元素大部分都沒有使用，元素稀稀落落，請問在資料結構中，將此矩陣稱為：
(A) 稀疏矩陣
(B) 上三角矩陣
(C) 下三角矩陣
(D) 零矩陣
5.使用二維陣列來儲存稀疏矩陣中的全部元素，下列敘述何者正確？
(A)容易管理
(B)記憶體最佳利用
(C)節省空間
(D)浪費空間
6.在處理稀疏矩陣的方法中，下列那一種方法可以減少記憶體空間的浪費？
(A)一維陣列
(B)二維陣列
(C)2-tuple結構
(D)3-tuple結構
2-8 特殊矩陣
1.除了常見的四種矩陣(矩陣轉置、矩陣相加、矩陣相乘及 稀疏矩陣)之外，在資料結構中尚有一些比較特殊的矩陣，請問下列何者正確？
(A)上三角矩陣
(B)下三角矩陣
(C)對稱矩陣
(D)以上皆是
2-8.1 上三角矩陣(Upper-Triangular Matrix)
1.假設一矩陣A為 n×n的二維矩陣，當對角線以上的元素均為零時稱之為上三角矩陣。欲將此矩陣對映到一個一維陣列，請問需要多大的記憶體空間來儲存？
(A) n (B)n×n (C) (D)
2.假設一矩陣A為 4×4的二維矩陣，當對角線以上的元素均為零時稱之為上三角矩陣。欲將此矩陣對映到一個一維陣列，請問需要多大的記憶體空間來儲存？
(A) 4 (B)8 (C)10 (D)15
3.假設一矩陣A為 n×n的二維矩陣，當對角線以上的元素均為零時稱之為上三角矩陣。請問零元素個數有多少？
(A) n (B)n×n (C) n2– (D) n2–
4.假設一矩陣A為 4×4的二維矩陣，當對角線以上的元素均為零時稱之為上三角矩陣。請問零元素個數有多少？
(A)4 (B)5 (C)6 (D)15
5.假設有一矩陣A為4×4的上三角矩陣，以列為主，請問元素a33對映到一維陣列的位置為何？
(A) 7 (B)8 (C) 9 (D) 10
6.假設有一矩陣A為4×4的上三角矩陣，以行為主，請問元素a33對映到一維陣列的位置為何？
(A) 5 (B)6 (C) 7 (D)8
2-8.2 下三角矩陣(Lower-Triangular Matrix)
1.假設一矩陣A為 n×n的二維矩陣，當對角線以上的元素均為零時稱之為下三角矩陣。欲將此矩陣對映到一個一維陣列，請問需要多大的記憶體空間來儲存？
(A) n (B)n×n (C) (D)
2.假設一矩陣A為 3×3的二維矩陣，當對角線以上的元素均為零時稱之為下三角矩陣。欲將此矩陣對映到一個一維陣列，請問需要多大的記憶體空間來儲存？
(A)3 (B)6 (C)9 (D)12
3.假設一矩陣A為 n×n的二維矩陣，當對角線以上的元素均為零時稱之為下三角矩陣。請問零元素個數有多少？
(A) n (B)n×n (C) n2– (D) n2–
4.假設一矩陣A為 3×3的二維矩陣，當對角線以上的元素均為零時稱之為下三角矩陣。請問零元素個數有多少？
(A)1 (B)2 (C)3 (D)5
5.假設有一矩陣A為4×4的下三角矩陣，以列為主，請問元素a33對映到一維陣列的位置為何？
(A)5 (B)6 (C) 7 (D)8
6.假設有一矩陣A為4×4的上三角矩陣，以行為主，請問元素a33對映到一維陣列的位置為何？
(A) 7 (B)8 (C) 9 (D)10