C语言阵列回顾 C语言以连续的记忆体空间来表达阵列，多维阵列的地址运算采用row major的方式。这种 做法的好处是索引运算速度快，甚至能用pointer来逐一检视其内容。但这种实作方法在 传递阵列参数时, 就有一些问题产生了 int sum(int x[]) { // x的长度到底是多少? 不知道的话程式要怎麽写? // 如果宣告成 int sum(int x[100])则此函数就只能接受长度为100的阵列 } int main() { int x[100]; int y[200]; sum(x); sum(y); } 假设有一函数sum(int x[])可用来将阵列内的函数全部加总起来，则仅靠传递阵列开头地 址是不够的，还必须传递该阵列的长度才行。如 int sum(int x[], int len) { int i, total = 0; for (i = 0; i < len; i++) { total += x[i]; } return total; } int main() { int x[100]; int y[200]; sum(x, 100); sum(y, 200); } 由於长度的资讯并不在阵列内，必须靠设计者另外告知才行，不小心的话容易发生不一致 的情形。 另一种方法是规范该阵列必须以某个特殊的数值当作结尾，函数必须自行检查该数值，以 确保程式正确。C语言的字串就是利用以0结尾的阵列来表达。 Java阵列的特性 Java的阵列并不以一块连续的记忆体空间来表达，而是把阵列视为特殊的物件。此物件不 但可存放资料，还利用object variable length记录着该阵列的长度。 public class ArrayExample { public static void main(String[] argv) { int[] x; // x is a reference to int[] x = new int[10]; // 利用new指令产生物件 for (int i = 0; i < x.length; i++) { // 此物件有一个object variable length，用以纪录该阵列的长度 x[i] = i; } } } length变数宣告为final，因此阵列物件产生後，就不能再变更其长度了 public class ArrayExample { public static void main(String[] argv) { int[] x; // x is a reference to int[] x = new int[10]; // 利用new指令产生物件 x.length = 1; // Compile Error } } 在阵列变数的宣告中，要注意和C语言特别不同的地方是: []没有数字。因为阵列是一种物件，必须以new指令产生物件，int[] x只是宣告x是一个 reference to int[]物件而已。 []在变数的左边，而不是右边。[]属於宣告型态的一部份，不牵扯空间分配，也不像C语 言有和pointer,function混合运用的情况，因此语法要把[]放在变数左边，方便判读。 我们也可以在变数宣告或是new阵列时就给定初始值: public class Arrays { public static void main(String[] args) { int[] a1 = { 1, 2, 3, 4, 5 }; Object[] a2 = new Object[] { new Integer(47), new Long(10), new Float(3.14), new Double(11.11) }; } } 多维阵列 Java阵列物件是只能储存基本资料型态或reference的一维阵列，二维以上的阵列是透过 reference指到其他的一维阵列物件来达成。 public class ArrayExample2 { public static void main(String[] argv) { int[][] x; x = new int[10][20]; for (int i = 0; i < x.length; i++) { for (int j = 0; j < x[i].length; j++) { x[i][j] = i + j; } } } } 上述的范例中，x宣告为reference to int[][],x[i][j]事实上是先找出reference x[i] ，再找x[i]所指到的阵列物件内的第j个元素。由於Java采用这种机制，因此下面的有趣 情形就发生了: public class ArrayExample3 { public static void main(String[] argv) { int[][] x; x = new int[10][]; // 先产生x阵列 for (int i = 0; i < x.length; i++) { x[i] = new int[i]; // 再分别产生x[i]所指到的阵列 } for (int i = 0; i < x.length; i++) { for (int j = 0; j < x[i].length; j++) { x[i][j] = i + j; } } } } 上述范例有两点要注意 阵列的长度可以为0 由於以一维阵列来模拟二维阵列，因此透过第一个阵列的reference所找到的阵列，其长 度不必然相同 阵列索引的检查 C语言不会对阵列的索引进行任何检查，保证索引值在阵列的合法范围内，是设计者的责 任。像是下列的范例就很可能产生Segmentation Fault。 int main() { int i; int x[10]; for (i = 0; i <= 10; i++) { x[i] = i; } } 由於这类的疏忽很难完全避免，而且不容易找出错误，因此Java在执行期间会对阵列的索 引做检查，如果超出来合法范围，就会产生ArrayIndexOutOfBoundException的例外。若 程式设计时没有指定这种例外的处理方式，则整个程式会终止，并於萤幕上印出相关的错 误讯息。例如执行下面的程式: public class ArrayExample4 { public static void main(String[] argv) { int[] x = new int[10]; for (int i = 0; i <= 10; i++) { x[i] = i; } } } 就会产生如下的错误讯息，并且终止该程式 java.lang.ArrayIndexOutOfBoundsException: 10 at ArrayExample4.main(ArrayExample4.java:5) Exception in thread "main" 上面讯息的意义是: java.lang.ArrayIndexOutOfBoundsException: 10告诉我们索引值是10的时候引起了此问 题 at ArrayExample4.main(ArrayExample4.java:5)告诉我们呼叫ArrayExample4.main时在 ArrayExample4.java的第五行产生错误 对於写过C语言的人来说，第一次看到这样的讯息都会很兴奋，因为JVM明明白白的告诉我 们哪一行出了甚麽错误，要除错就简单多了。 当然这样的便利性是用效能换来的。如果你的应用需要大量存取阵列，而且速度非常重要 ，连几个machine cycle都要计较,那才要考虑不用Java了。 阵列范例 费氏数 public class Fab { private static long[] rel = {0,1,1,2,3,5,8,13,21,34,55,89}; public static void main(String[] argv) { val(10); } public static long val(int n) { if (rel.length <= n) { long[] tt = new long[n+1]; int i; for (i = 0; i < rel.length; i++) { tt[i] = rel[i]; } for (; i <= n; i++) { tt[i] = tt[i-1] + tt[i-2]; } rel = tt; } return rel[n]; } } Selection sort public class SelectionSort { public static void main(String[] argv) { int[] data = {6, 3, 7, 1, 4, 8}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); } } public static void sort(int[] data) { for (int i = 0; i < data.length - 1; i++) { // find minimun in i ~ data.length - 1 int mim = i; for (int j = i + 1; j < data.length; j++) { if (data[min] > data[j]) { min = j; } } // swap data[i] with data[min] int tmp = data[i]; data[i] = data[min]; data[min] = tmp; } } } Insertion Sort public class InsertionSort { public static void main(String[] argv) { int[] data = {4, 1, 7, 8, 9, 3, 2}; sort(data); for (int i = 0; i < data.length; i++) { System.out.println(data[i]); } } public static void sort(int[] data) { int j, pivot; // insert data[i] to sorted array 0 ~ i - 1 // begins from i = 1, because if the array has only one element then it must be sorted. for (int i = 1; i < data.length; i++) { pivot = data[i]; for (j = i - 1; j >= 0 && data[j] > pivot; j--) { // shift data[j] larger than pivot to right data[j+1] = data[j]; } data[j+1] = pivot; } } } Pascal Triangle 下图为n=6的情况 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 其规则是最外层是1, 里面每个数字都是上方两个数字的和. Pascal Triangle是(x + y)n 每个项次的系数. 提示: 如果把上图左边的空白拿掉则会变成下面的图形, 除了最左边和最右边的数字是1 以外, 里面的每一个数字都是其正上方和左上方数字的和. 你可以用阵列来计算和储存这 些数字, 然後再以上图的格式印出来. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 所以只要你能回答下面问题, 程式就写完了: 如果要用*号印出这种形状的三角形, 该怎麽写? (回圈范例里已经练习过了) 最左边和最右边如何表达? 内部每一个数字都是正上方和左上方数字, 请问正上方和左上方这两个位置的阵列索引如 何表达? 以下是程式的范例: /** * Program Name: Pascal.java * Purpose: print pascal triangle on screen * Author: Shiuh-Sheng Yu, Department of Information Management * National ChiNan University * Since: 2006/01/23 */ public class Pascal { public static void main(String[] argv) { int n, i, j; int[][] tri = new int[51][51]; n = Integer.parseInt(argv[0]); if (n < 0 || n > 50) { System.out.println("I can only print Pascal triangle between 0 and 50.\n"); } else { for (i = 0; i <= n; i++) { for (j = 0; j <= i; j++) { System.out.print(" "+(tri[i][j] = (j==0 || j==i) ? 1 : tri[i-1][j-1]+tri[i-1][j])); } System.out.println(); } } } } 列出整数阵列所有n个数字的排列 public class Example { /* 列出由at左边所有的排列 */ private static void permutation(int data[], int n, int got) { // 如果已经排到最後了,印出结果 if (n == got) { for (int i = 0; i < n; i++) { System.out.print(data[i]+" "); } System.out.println(); return; } int tmp; for (int i = got; i < data.length; i++) { // swap data[i] and data[at] tmp = data[i]; data[i] = data[got]; data[got] = tmp; // 然後递回呼叫,以找出got+1右边的所有排列 permutation(data, n, got + 1); // swap back data[i] and data[got] tmp = data[i]; data[i] = data[got]; data[got] = tmp; } } public static void permutation(int data[], int n) { permutation(data, n, 0); } public static void main(String[] argv) { int data[] = {1,2,3,4,5,6}; permutation(data, 4); } } 列出整数阵列所有n个数字的组合 public class Example { /* 由data.length取n个 */ private static void combination(int[] data, int n, int got, int from) { int tmp; if (n == got) { for (int i = 0; i < n; i++) { System.out.print(data[i] + " "); } System.out.println(); return; } for (int i = from; i < data.length; i++) { // 选第i个, by swap data[i] and data[got] tmp = data[i]; data[i] = data[got]; data[got] = tmp; combination(data, n, got + 1, i + 1); // swap back data[i] and data[got] // two swaps make data original tmp = data[i]; data[i] = data[got]; data[got] = tmp; } } // data里找出所有n个数字组合 public static void combination(int data[], int n) { combination(data, n, 0, 0); } public static void main(String[] argv) { int[] data = {1,2,3,4,5}; combination(data, 3); } } 反转阵列 public class Example { public static void main(String[] argv) { char[] data = {'1', '2', '3', '4'}; reverse(data); for (int i = 0; i < data.length; i++) { System.out.print(data[i]+" "); } } public static void reverse(char[] data) { char tmp; for (int i = 0, j = data.length - 1; i < j; i++, j--) { tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } } Using array to implement Stack public class Stack { private Object[] data; private int top; public Stack() { // constructor data = new Object[1024]; } public void push(Object obj) { if (top >= data.length) { Object[] tmp = new Object[data.length*2]; System.arraycopy(data, 0, tmp, 0, data.length); data = tmp; } data[top++] = obj; } public Object pop() { return data[--top]; } public Object peek() { return data[top-1]; } public int size() { return top; } } --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.58.22.74