java 私塾第五章笔记整理

左右

java 私塾第五章笔记整理

数组是由相同类型的若干项数据组成的一个数据集合，也就是说数组是用来集合相同类型的对象并通过一个名称来引用这个对象。
可以声明任何类型的数组-----原始类型或类类型。
当数组声明的方括号在左边时，该方括号可以用于所有位于其右边的变量：char [] s,y。
数组一旦被创建，在内存里占用连续的内存地址。
数组的静态性：数组一旦被创建，就不能更改数组的长度。

        Point [] p = new Point[3];
        new int[][4]是非法的。

数组的复制
        System.arraycopy(myArray,0,hold,0,myArray.length);
数组排序
        Arrays.sort(a);

定义一个一维的int数组，先创建它，并初始化它，给它赋值，然后输出其中的一个值

1. public class Arr{
   
2.      public static void main(String args[]){
   
3.         int a[] = new int[5];
   
4.         a[0]=1;
   
5.         a[1]=2;
   
6.         System.out.println(a[0]);
   
7.      }
   
8.   }

复制代码

定义一个一维的A类型数组，直接定义并赋值，然后输出其中的一个值

1. 
   
2. public class A{
   
3.      public static int i;
   
4.      public static void main(String args[]){
   
5.         A aa = new A();
   
6.         A bb = new A();
   
7.         A a[] = {aa,bb};
   
8.         a[0].i=2;
   
9.         System.out.println(a[0]);
   
10.      }
    
11. }

复制代码

把上面的数组改成2维的数组

1. 
   
2. public class A{
   
3.     public static int i;
   
4.     public static void main(String args[]){
   
5.         A a[][] = new A[5][5];
   
6.         a[0][0].i=2;
   
7.         System.out.println(a[0][0]);
   
8.     }
   
9. }

复制代码

举例说明数组拷贝方法的使用：arraycopy方法，

1. 
   
2. public class A{
   
3.     public static void main(String args[]){
   
4.         int a[] = new int[5];
   
5.         int b[] = new int[5];
   
6.         System.arraycopy(a[5],0,b[5],0,a.length);
   
7.         System.out.println(b[0]);
   
8.     }
   
9. }

复制代码

常见的排序算法

1. 
   
2. public class SortAll {   
   
3.     public static void main(String[] args) {   
   
4.         int[] i = { 1, 5, 6, 12, 4, 9, 3, 23, 39, 403, 596, 87 };   
   
5.         System.out.println("----冒泡排序的结果：");   
   
6.         maoPao(i);   
   
7.         System.out.println();   
   
8.         System.out.println("----选择排序的结果：");   
   
9.         xuanZe(i);   
   
10.         System.out.println();   
    
11.         System.out.println("----插入排序的结果：");   
    
12.         chaRu(i);   
    
13.     }
    
14.   
    
15.     // 冒泡排序   
    
16.     public static void maoPao(int[] x) {   
    
17.         for (int i = 0; i < x.length; i++) {   
    
18.             for (int j = i + 1; j < x.length; j++) {   
    
19.                 if (x[i] > x[j]) {   
    
20.                     int temp = x[i];   
    
21.                     x[i] = x[j];   
    
22.                     x[j] = temp;   
    
23.                 }   
    
24.             }   
    
25.         }   
    
26.         for (int i : x) {   
    
27.             System.out.print(i + " ");   
    
28.         }   
    
29.     }   
    
30.     // 选择排序
    
31.     public static void xuanZe(int[] x) {   
    
32.         for (int i = 0; i < x.length; i++) {   
    
33.             int lowerIndex = i;   
    
34.             // 找出最小的一个索引   
    
35.             for (int j = i + 1; j < x.length; j++) {   
    
36.                 if (x[j] < x[lowerIndex]) {   
    
37.                     lowerIndex = j;   
    
38.                 }   
    
39.             }   
    
40.             // 交换
    
41.             int temp = x[i];   
    
42.             x[i] = x[lowerIndex];   
    
43.             x[lowerIndex] = temp;   
    
44.         }   
    
45.         for (int i : x) {   
    
46.             System.out.print(i + " ");   
    
47.         }   
    
48.     }  
    
49. 
    
50.     // 插入排序   
    
51.     public static void chaRu(int[] x) {   
    
52.         for (int i = 1; i < x.length; i++) {// i从一开始，因为第一个数已经是排好序的啦   
    
53.             for (int j = i; j > 0; j--) {   
    
54.                 if (x[j] < x[j - 1]) {   
    
55.                     int temp = x[j];   
    
56.                     x[j] = x[j - 1];   
    
57.                     x[j - 1] = temp;   
    
58.                 }   
    
59.             }   
    
60.         }   
    
61.         for (int i : x) {   
    
62.             System.out.print(i + " ");   
    
63.         }   
    
64.     }   
    
65. }

复制代码

二分法查找

1. 
   
2. package com.sghlwxf.binarySoft;
   
3. 
   
4. public class TestBinarySoft{
   
5.    public static void main(String args[]){
   
6.       int[] array= new int[]{4, 12, 23, 33, 45, 53, 65, 78, 88, 90 };
   
7.       //定义要查找的数
   
8.       int seek = 76;
   
9.       //定义下标
   
10.       int index = 0;
    
11.       //定义起始位置
    
12.       int start = 0;
    
13.       //定义结束位置
    
14.       int end = 0;
    
15.       //定义计数器
    
16.       while(true){
    
17.          count ++;
    
18.          //int index = (start + end)/2;
    
19.          //为了防止start+end溢出,所以写成start+((end - start)/2)
    
20.          int index =  start + ((end - start)/2);
    
21.          if(array[index] <seek){
    
22.             start = index;
    
23.          }else if(array[index]>seek){
    
24.             end = index;
    
25.          }else{
    
26.             break;
    
27.          }
    
28.      }
    
29.      System.out.pritln("所运行的次数是"+count+"地址为"+index);
    
30.    }
    
31. }

复制代码

【此处有二叉树图片，可以到java 私塾官网下载完整笔记：www.javass.cn】

1. 
   
2. /** 二叉树节点 */
   
3. public class BTNode {
   
4.     private char key;
   
5.     private BTNode left, right;
   
6.     public BTNode(char key) {
   
7.         this(key, null, null);
   
8.     }
   
9.     public BTNode(char key, BTNode left, BTNode right) {
   
10.         this.key = key;
    
11.         this.left = left;
    
12.         this.right = right;
    
13.     }
    
14.     public char getKey() {
    
15.         return key;
    
16.     }
    
17.     public void setKey(char key) {
    
18.         this.key = key;
    
19.     }
    
20.     public BTNode getLeft() {
    
21.         return left;
    
22.     }
    
23.     public void setLeft(BTNode left) {
    
24.         this.left = left;
    
25.     }
    
26.     public BTNode getRight() {
    
27.         return right;
    
28.     }
    
29.     public void setRight(BTNode right) {
    
30.         this.right = right;
    
31.     }
    
32. }

复制代码

1. /** 二叉树遍历 */
   
2. public class BinTree {
   
3.     protected BTNode root;
   
4.     public BinTree(BTNode root) {
   
5.         this.root = root;
   
6.     }
   
7.     public BTNode getRoot() {
   
8.         return root;
   
9.     }
   
10.     /** 构造树 */
    
11.     public static BTNode init() {
    
12.         BTNode a = new BTNode('A');
    
13.         BTNode b = new BTNode('B', null, a);
    
14.         BTNode c = new BTNode('C');
    
15.         BTNode d = new BTNode('D', b, c);
    
16.         BTNode e = new BTNode('E');
    
17.         BTNode f = new BTNode('F', e, null);
    
18.         BTNode g = new BTNode('G', null, f);
    
19.         BTNode h = new BTNode('H', d, g);
    
20.         return h;// root
    
21.     }
    
22.     /** 访问节点 */
    
23.     public static void visit(BTNode p) {
    
24.         System.out.print(p.getKey() + " ");
    
25.     }
    
26.     /** 递归实现前序遍历 */
    
27.     protected static void preorder(BTNode p) {
    
28.         if (p != null) {
    
29.             visit(p);
    
30.             preorder(p.getLeft());
    
31.             preorder(p.getRight());
    
32.         }
    
33.     }
    
34.     /** 递归实现中序遍历 */
    
35.     protected static void inorder(BTNode p) {
    
36.         if (p != null) {
    
37.             inorder(p.getLeft());
    
38.             visit(p);
    
39.             inorder(p.getRight());
    
40.         }
    
41.     }
    
42.     /** 递归实现后序遍历 */
    
43.     protected static void postorder(BTNode p) {
    
44.         if (p != null) {
    
45.             postorder(p.getLeft());
    
46.             postorder(p.getRight());
    
47.             visit(p);
    
48.         }
    
49.     }
    
50.     /** 非递归实现前序遍历 */
    
51.     protected static void iterativePreorder(BTNode p) {
    
52.         Stack<BTNode> stack = new Stack<BTNode>();
    
53.         if (p != null) {
    
54.             stack.push(p);
    
55.             while (!stack.empty()) {
    
56.                 p = stack.pop();
    
57.                 visit(p);
    
58.                 if (p.getRight() != null)
    
59.                     stack.push(p.getRight());
    
60.                 if (p.getLeft() != null)
    
61.                     stack.push(p.getLeft());
    
62.             }
    
63.         }
    
64.     }
    
65.     /** 非递归实现后序遍历 */
    
66.     protected static void iterativePostorder(BTNode p) {
    
67.         BTNode q = p;
    
68.         Stack<BTNode> stack = new Stack<BTNode>();
    
69.         while (p != null) {
    
70.             // 左子树入栈
    
71.             for (; p.getLeft() != null; p = p.getLeft())
    
72.                 stack.push(p);
    
73.             // 当前节点无右子或右子已经输出
    
74.             while (p != null && (p.getRight() == null || p.getRight() == q)) {
    
75.                 visit(p);
    
76.                 q = p;// 记录上一个已输出节点
    
77.                 if (stack.empty())
    
78.                     return;
    
79.                 p = stack.pop();
    
80.             }
    
81.             // 处理右子
    
82.             stack.push(p);
    
83.             p = p.getRight();
    
84.         }
    
85.     }
    
86.     /** 非递归实现中序遍历 */
    
87.     protected static void iterativeInorder(BTNode p) {
    
88.         Stack<BTNode> stack = new Stack<BTNode>();
    
89.         while (p != null) {
    
90.             while (p != null) {
    
91.                 if (p.getRight() != null)
    
92.                     stack.push(p.getRight());// 当前节点右子入栈
    
93.                 stack.push(p);// 当前节点入栈
    
94.                 p = p.getLeft();
    
95.             }
    
96.             p = stack.pop();
    
97.             while (!stack.empty() && p.getRight() == null) {
    
98.                 visit(p);
    
99.                 p = stack.pop();
    
100.             }
     
101.             visit(p);
     
102.             if (!stack.empty())
     
103.                 p = stack.pop();
     
104.             else
     
105.                 p = null;
     
106.         }
     
107.     }
     
108.     public static void main(String[] args) {
     
109.         BinTree tree = new BinTree(init());
     
110.         System.out.print(" Pre-Order:");
     
111.         preorder(tree.getRoot());
     
112.         System.out.println();
     
113.         System.out.print("  In-Order:");
     
114.         inorder(tree.getRoot());
     
115.         System.out.println();
     
116.         System.out.print("Post-Order:");
     
117.         postorder(tree.getRoot());
     
118.         System.out.println();
     
119.         System.out.print(" Pre-Order:");
     
120.         iterativePreorder(tree.getRoot());
     
121.         System.out.println();
     
122.         System.out.print("  In-Order:");
     
123.         iterativeInorder(tree.getRoot());
     
124.         System.out.println();
     
125.         System.out.print("Post-Order:");
     
126.         iterativePostorder(tree.getRoot());
     
127.         System.out.println();
     
128.     }
     
129. }

复制代码

输出结果
Pre-Order:H D B A C G F E
  In-Order:B A D C H G E F
Post-Order:A B C D E F G H
Pre-Order:H D B A C G F E
  In-Order:B A D C H G E F
Post-Order:A B C D E F G H