目的
Java 的原生基本資料型態共有 8 個，比如 int、short….。當我們想要建立一個叫 Student 的資料型態，裏面有名字、英文成績、數學成績，此時就必需把這三項型態組合成一個自訂的資料型態。
語法
自訂的資料型態在 C 語言使用 struct 指令，在 Java 裏直接改成 class。請注意如下 class Student 是寫在 public class Test 之外，也就是外部類別。
要產生一個新的 Student，使用 new 關鍵字。這跟 C 語言調用 malloc() 函數一樣，都是跟系統要求某一區塊的記憶體。產生出來的 s1 稱為物件 (Object)。要存取 s1 裏的 name、eng 就直接在 s1後面加上「.」。 「.」 就是「的」, 比如 s1.name 即「s1 的 name」。
public class Test {
public static void main(String[] args){
Student s1=new Student();
s1.name="Thomas";
s1.eng=100;
s1.math=80;
}
}
class Student{
String name;
int eng, math;
}
上面的代碼可以簡略下一個定論 : 什麼是類別 (class) ? 類別就是一個自訂的資料型態。
預設值
產生出來的 s1，裏面的變數會被系統自動初始化， String 初始化為 null，int 初始化為 0，小數初始化為 0.0。
public class Test {
public static void main(String[] args){
Student s1=new Student();
System.out.printf("namd : %s, eng : %d, math : %d\n", s1.name, s1.eng, s1.math);
}
}
class Student{
String name;
int eng, math;
}
結果 :
namd : null, eng : 0, math : 0
單向連結
陣列的限制
使用陣列時，必需先宣告，如
int[] array=new int[10];
a 是一個長度為10 個元素的陣列，一經宣告長度就不能改變。重點在於一開始我們怎麼知道是要宣告為 10 或 100 呢?
比如要記錄每個客人消費的金額，打從一開門，到底是要宣告有幾個客人? 因為無法預測，所以無法定長度。
解決方案
上述的問題很明顯使用陣列是無法解決，所以必需另想辦法。下圖即是資料結構課程裏頂頂有名的單向連結。先產生一個 root 及 index，並產生一個節點 @f1。
當需要記錄某數字比如50，就將 50 放入 @f1中，然後再產生一個節點 @f2，此 @f2 記錄在 @f1 的 next 變數中。當要再次記錄另一個數字，就放入最後的節點，然後再產生一個新的節點 stand by。
如此就可以無限的擴充長度，只要記憶體不要爆掉就好。就算記憶體爆了，還是可以寫個網路連結的方法，將別台電腦的記憶體納入自已來使用。
程式代碼
上述的每一個節點都有二個值，一個是記錄數字用的，另一個是記錄下一個節點。所以節點的自訂資料格式為
class Node{
int d;
Node next;
}
上面的 Node next，是說 class 裏有一個變數，而這個變數是指向一個新的 Node ，完整代碼如下。
public class SingleLink {
public static void main(String[] args){
Node root=new Node();
Node index=root;
Scanner in=new Scanner(System.in);
int x=0;
while(true){
System.out.print("請輸入數字(-1離開) : ");
x=in.nextInt();
if(x==-1)break;
index.d=x;
index.next=new Node();
index=index.next;
}
index=root;
while(index.next!=null){
System.out.printf("%d ", index.d);
index=index.next;
}
System.out.println();
}
}
class Node{
int d;
Node next;
}
結果 :
請輸入數字(-1離開) : 10
請輸入數字(-1離開) : 50
請輸入數字(-1離開) : 60
請輸入數字(-1離開) : 70
請輸入數字(-1離開) : 80
請輸入數字(-1離開) : 90
請輸入數字(-1離開) : -1
10 50 60 70 80 90
雙向連結
單向連結的缺點
前一章所提及的單向連結可以無限的擴充長度，只要記憶體不要爆掉就好。但有一個缺失就是無法反向列印。
解決方案
單向連結無法反向列印，其實是可以用其他演算法解決。但這演算法實在是太耗費時間，所以才會有如下的結構。下面每個節點又多一個記錄前一個節點的變數 prev，如果就可以正反向列印。
代碼
public class DoubleLink {
public static void main(String[] args){
Node root=new Node();
Node index=root;
Scanner in=new Scanner(System.in);
int x=0;
while(true){
System.out.print("請輸入數字(-1離開) : ");
x=in.nextInt();
if(x==-1)break;
index.d=x;
index.next=new Node();
index.next.prev=index;
index=index.next;
}
//正向列印
index=root;
System.out.println("正向列印......");
while(index.next!=null){
System.out.printf("%d ", index.d);
index=index.next;
}
System.out.println();
//反向列印
index=root;
while(index.next!=null)index=index.next;
System.out.println("反向列印......");
while(index.prev!=null){
System.out.printf("%d ", index.prev.d);
index=index.prev;
}
System.out.println();
}
}
class Node{
Node prev;
int d;
Node next;
}
結果 :
請輸入數字(-1離開) : 10
請輸入數字(-1離開) : 20
請輸入數字(-1離開) : 30
請輸入數字(-1離開) : 40
請輸入數字(-1離開) : 50
請輸入數字(-1離開) : -1
正向列印......
10 20 30 40 50
反向列印......
50 40 30 20 10
二元樹排序法
規則
二元樹排序(Binary Sort)又有人稱為黑紅樹，它是所有高科技的開端，沒有這個演算法就不會有現今這個世界。其規則如下
1. 左邊小, 右邊大 2. 左中右, 中間取值
架構圖
程式架構
下面的代碼依序執行如下動作
1. 產生n 個元素的陣列
2. 將亂數填入陣列中
3. 將陣列列印出來
4. 建立二元樹
5. 排序
6. 列印排序後的陣印
package binarytree;
public class BinaryTree {
static int[]array;
static int index=0;
public static void main(String[] args) {
//產生陣列並填入亂數
int n=10;
array=new int[n];
for (int i=0;i<array.length;i++){
array[i]=(int)(Math.random()*10000);
}
//列印未排序的陣列
printData(array);
//建立二元樹
Node root=null;
for (int i=0;i<array.length;i++){
root=bt(root, array[i]);
}
//排序
sort(root);
//列印排完序後的陣列
printData(array);
}
public static void printData(int[] array){
//todo
}
//bt : buildTree的縮寫
public static Node bt(Node node, int value){
//todo
}
public static void sort(Node node){
//todo
}
}
//節點資料結構
class Node{
Node left;
Node right;
int value;
public Node(int value){
this.value=value;
}
}
完整代碼
package binarytree;
public class BinaryTree {
static int[]array;
static int index=0;
public static void main(String[] args) {
/*
1. n=10;
2. 產生陣列 array
3. 填入亂數
4. 列印
5. 建立二元樹
6. 排序
7. 列印
*/
int n=10;
array=new int[n];
for (int i=0;i<array.length;i++){
array[i]=(int)(Math.random()*10000);
}
printData(array);
Node root=null;
for (int i=0;i<array.length;i++){
root=bt(root, array[i]);
}
sort(root);
printData(array);
}
public static void printData(int[] array){
for (int i=0;i<array.length;i++){
System.out.printf("%d ", array[i]);
}
System.out.println();
}
public static Node bt(Node node, int value){
//進入點沒東西, 就產生節點
if (node==null)node=new Node(value);
//否則就判斷是往左邊走, 或往右邊走
else if (value<node.value)node.left=bt(node.left, value);
else node.right=bt(node.right, value);
return node;
}
public static void sort(Node node){
//左中右, 中間取值
//底下為往左邊走
if (node.left!=null)sort(node.left);
//中間取值
array[index++]=node.value;
//接下來, 往右邊走
if (node.right!=null)sort(node.right);
}
}
class Node{
Node left;
Node right;
int value;
public Node(int value){
this.value=value;
}
}
結果 :
29 154 252 349 411 447 462 543 734 982