本文共 13305 字，大约阅读时间需要 44 分钟。

数据结构与算法

1.数组是最基本的数据结构，是一张表，线性表（数据元素之间是一对一的关系，除了第一个和最后一个之外，其余的元素都是首尾相连）

链表

树

图    深度遍历和广度遍历

2.写程序的思想：

1.先完成需求要求的功能

2.根据程序运行的结果进行优化处理

3.代码重构

4.提升效率

例题.

找出一个数在数组中位置： 在数组中是否存在，如果存在，返回下标，如果不存在，输出-1

如果找到了，把下标i保存起来，显示你要找的数是xxx，在目标数组中的下标是xxx

如果没找到，则显示你要找的数是xxx，在目标数组中不存在

import java.util.Scanner;public class Ch01 {    public static void main(String[] args) {        int[] arr = new int[]{1, 58, 46, 33, 10, 5, -8};        Scanner s = new Scanner(System.in);        System.out.println("请输入一个数：");        int num = s.nextInt();        int index=-1;        for (int i = 0; i < arr.length; i++) {            if (arr[i] == num) {                System.out.println("你要找的数是：" + num + ",在目标数组的下标是" + i);                index=1;                break;            }            if(index!=-1){                System.out.println("你要找的数是：" + num + ",在目标数组的下标是" + i);            } else {                System.out.println("你要找的数是：" + num + ",在目标数组中是不存在的");            }        }    }}

3.查找算法

线性查找：简单，便于理解

下面是二分法查询：

import java.util.Scanner;public class Ch02 {    public static void main(String[] args) {        int [] arr= new int[]{1,2,3,4,5,6,7};        Scanner s=new Scanner(System.in);        System.out.println("请输入要查找的数字：");        int target =s.nextInt();        int left=0;        int right=arr.length-1;        if (target
   
    arr[right]){            System.out.println(target+"在目标数组中不存在");        }else{            //用来保存找到的下标的值            int res=-1;            while(left<=right){                  int middle=(left+right)/2;                  if (arr[middle]==target){                      //中间的数恰巧是我们要找的数                      res=middle;                      break;                  }else if(arr[middle]>target){                      right =middle-1;                  }else{                      left =middle+1;                  }            }System.out.println(target+"在目标数组中的位置是："+res);        }    }}
   

4.八大排序

排序算法：

1.冒泡排序

2.快速排序

3.插入排序

4.选择排序

5.希尔排序

6.堆排序

7.归并排序

8.桶排序

 重点：冒泡排序

public class Ch03 {    public static void main(String[] args) {        int []arr=new int[]{1, 58, 46, 33, 10, 5, -8};        for(int i=0;i
   
    arr[j+1]){                    int temp=arr[j];                    arr[j]=arr[j+1];                    arr[j+1]=temp;                }            }            System.out.println("第"+(i+1)+"轮的比较结果：");            for (int i1 : arr) {                System.out.print(i1+"、");            }            System.out.println();        }    }}
   

运行结果：

 简便的从小到大排序数组方法：

import java.lang.reflect.Array;import java.util.Arrays;public class Ch04 {        /*            排序的简便写法（只能从小到大）             */        public static void main(String[] args) {            int [] arr = new int[]{1,52,47,56,85,-4};            Arrays.sort(arr);            for (int i : arr){                System.out.println(i);            }        }    }

运行结果：

5.选择排序

   代码：

public class Ch05 {    public static void main(String[] args) {        int []arr=new int[]{1,25,48,12,10,-8,127,56};        for(int i=0;i
   
    arr[j]){                    minIndex=j;                }            }            int temp=arr[minIndex];            arr[minIndex]=arr[i];            arr[i]=temp;            System.out.println("第"+(i+1)+"次比较结果是：");        for (int i1 : arr) {            System.out.print(i1+"、");        }            System.out.println( );        }    }}
   

       

过程分析：（前两轮）

第一轮

                i=0,minIndex=0，里层的for循环int j = 1;j < 7;                 if(arr[0] > arr[1]){}。由于if不满足，则继续下一次的比较。                 j = 2,if(arr[0] > arr[2]){}。由于if不满足，则继续下一次的比较。                 j = 3,if(arr[0] > arr[3]){}。由于if不满足，则继续下一次的比较。                 j = 4,if(arr[0] > arr[4]){}。由于if不满足，则继续下一次的比较。                 j = 5,if(arr[0] > arr[5]){}。由于if满足条件，执行了minIndex = 5.                 j = 6,if(arr[5] > arr[6]){}。由于if不满足，则继续下一次的比较。                 j = 7,if(arr[5] > arr[7]){}。由于if不满足，则继续下一次的比较。                 到此为止，里层的for循环执行完毕。minIndex = 5。执行的                 int temp = arr[5];                 arr[5] = arr[0];                 arr[0] = temp;                 i=0的这次外层循环执行完毕。                 数组变成了-8、25、48、12、10、1、127、56              第二轮                 i=1,minIndex = 1,                 j = 2,if(arr[1] > arr[2]){}。由于if不满足，则继续下一次的比较。                 j = 3,if(arr[0] > arr[3]){}。由于if满足，minIndex = 3;                 j = 4,if(arr[3] > arr[4]){}。由于if满足，minIndex = 4;                 j = 5,if(arr[4] > arr[5]){}。由于if满足，minIndex = 5;                 j = 6,if(arr[5] > arr[6]){}。由于if不满足，则继续下一次的比较。                 j = 7,if(arr[5] > arr[7]){}。由于if不满足，则继续下一次的比较。                 到此为止，里层的for循环执行完毕。minIndex = 5。执行的                 int temp = arr[5];                 arr[5] = arr[1];                 arr[1] = temp;                 数组变成了-8、1、48、12、10、25、127、56

6.选择查询

public class Ch06 {    public static void main(String[] args) {        int []arr=new int[]{1,25,48,12,10,-8,127,56};        int current;        for (int i = 0; i < arr.length-1; i++) {            current=arr[i+1];            int preIndex =i;            while(preIndex>=0&&current

运行结果：

思想流程：（前四轮为例）

第一轮：

                i=0,current=arr[1],int preIndex=0,                 while(0 >= 0 && 25 < arr[0]){}不成立，while循环不启动                 arr[0+1] = arr[0+1]             第二轮：                 i=1,current=arr[2]=48,int preIndex=1                 while(1 >= 0&&48<25){}不成立，while循环不启动                 arr[1+1] = arr[1+1]             第三轮：                 i=2,current=arr[3]=12,int preIndex=2                 while(2 >=0 && 12 < 48){                     arr[3] = arr[2]                     2--;                 }                 preIndex=1;                 while(1 >=0 && 12 < 25){                     arr[2] = arr[1];                     1--;                 }                 preIndex = 0;                 while(0 >=0 && 12 < 1){}不成立，while完事                 arr[1] = 12;                 1,12,25,48,10,-8,127,56              第四轮：                 i=3,current = arr[4] = 10,int preIndex = 3,                 while(3>=0 && 10 < 48){                     arr[4] = arr[3];                     1,12,25,48,48,-8,127,56                     3--;                 }                 preIndex = 2;                 while(2>=0 && 10 < 25){                     arr[3] = arr[2];                     1,12,25,25,48,-8,127,56                     2--;                 }                 preIndex = 1;                 while(1>=0&& 10 < 12){                     arr[2] = arr[1];                     1,12,12,25,48,-8,127,56                     1--;                 }                 preIndex = 0;                 while(0>=0&&10 < 1){}不成立，while完事                 arr[1] = current = 10;                 1,10,12,25,48,-8,127,56

6.

import java.util.Arrays;public class Ch04 {    public static void main(String[] args) {        int [] nums = new int[]{3,4,6};        // 定义一个新的临时数组        int [] temp = new int[6];        for (int i = 0; i < nums.length; i++) {            temp[i] = nums[i];        }        nums = temp;        System.out.println(Arrays.toString(nums));    }}

数组的反转的两种方式：

 思路1：

                public static void main(String[] args) { //        int [] arr = new int[]{1,25,48,12,10,-8,127,56}; //        for (int i = arr.length - 1; i >= 0 ; i--) { //            System.out.println(arr[i]); //        }         /*             思路1：                 创建一个等长的数组                 把当前数组的每一个元素倒着添加到新数组里                 新数组赋值给老数组                 int [] newArr = new int[arr.lenth];          */ //        int [] newArr = new int[arr.length]; //        for (int i = arr.length - 1; i >= 0 ; i--) { //            newArr[i] = arr[arr.length - 1 - i]; //        }         // 新数组赋值给老数组 //        arr = newArr; //        for (int i : arr) { //            System.out.println(i); //        }

  /*

            思路2：             利用交换的方式          */         int [] arr = new int[]{1,25,48,12,10,-8,127,56}; //        for (int i = 0; i < arr.length / 2; i++) { //            // temp存储的时最后一位 //            int temp = arr[arr.length - 1 - i]; //            arr[arr.length - 1 - i] = arr[i]; //            arr[i] = temp; //        } //        for (int i : arr) { //            System.out.println(i); //        } //        Arrays是操作数组的一个工具类         System.out.println(Arrays.toString(arr));     } }

import java.util.Arrays;

7.  数组的扩容

代码：

public class Ch04 {    public static void main(String[] args) {        int [] nums = new int[]{3,4,6};        // 定义一个新的临时数组        int [] temp = new int[6];        for (int i = 0; i < nums.length; i++) {            temp[i] = nums[i];        }        nums = temp;        System.out.println(Arrays.toString(nums));    }}

结果：

8.普通员工管理系统

public class G1 {    /*                    员工信息要保存到数组里。                    1.工号（不能输入，自动生成的自动递增的一个数字1001）                    2.员工姓名                    员工的工号和姓名都是保存到数组里                    int [] nos = new int[2];                    String [] names = new String[2];                    要考虑扩容问题                 */            case "2":                /*                    根据工号查询                    如果有能力的同学。可以去做根据姓名查询，姓名可以重名（选坐）                 */                /*                    排序，根据工号从大到小排序                 */                    case "3":                /*                    修改两个操作：                    先输入员工号，先查询员工号在不在，如果不在，                    员工号输入有误，                    如果在，先显示出原有信息，请输入新的名字，                    修改信息。1002 nos[1] names[1]=                 */                    case "4":                /*                    数组删除元素；                    10个元素，5个，移位的问题                    int[] 0                    String[] null                 */    default:}import java.util.Arrays;import java.util.Scanner;/** * 字符串拼接，提示: */public class ManageSystem1 {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        System.out.println("欢迎使用员工管理系统:");        int id = 1001;        int index = 0;        int[] nos = new int[2];        String[] names = new String[2];        system:        while (true) {            System.out.println("************员工管理系统***********");            System.out.println("1.添加新员工信息");            System.out.println("2.根据工号查询员工信息");            System.out.println("3.根据姓名查询员工信息");            System.out.println("4.修改员工信息");            System.out.println("5.删除员工信息");            System.out.println("6.按其他键退出系统");            System.out.println("7.反向输出");            System.out.println("***********************************");            System.out.println("请输入要进行的操作：");            String flag = sc.next();            switch (flag) {                case "1":                    System.out.println("请输入员工姓名");                    String name = sc.next();                /*                1.工号（自动生成自动递增）                2.员工姓名                工号和姓名保存到数组                int [] nos = new int[2];                String [] names = new String[2];                要考虑扩容问题                 */                    if (nos.length - 1 <= index) {                        int[] nosTemp = new int[nos.length * 2];                        String[] namesTemp = new String[names.length * 2];                        for (int i = 0; i < nos.length; i++) {                            nosTemp[i] = nos[i];                            namesTemp[i] = names[i];                        }                        nos = nosTemp;                        names = namesTemp;                    }                    nos[index] = id;                    names[index] = name;                    System.out.println("添加员工成功！");                    System.out.println("员工信息为：工号-" + nos[index] + " 姓名-" + names[index]);                    index += 1;                    id += 1;                    break;                case "2":                /*                根据工号查询                如果有能力，可以根据姓名查询，姓名可以重名                 */                    System.out.println("请输入工号进行查询：");                    int selection = sc.nextInt();                    for (int i = 0; i < nos.length; i++) {                        if (selection == nos[i]) {                            System.out.println("该员工的姓名为：" + names[i]);                            break;                        } else if (i == nos.length - 1) {                            System.out.println("您要查询的员工不存在，请确认输入是否正确。");                        }                    }                    break;                case "3":                    System.out.println("请输入姓名进行查询：");                    String selection1 = sc.next();                    for (int i = 0; i < nos.length; i++) {                        if (selection1.equals(names[i])) {                            System.out.println("该员工的姓名为：" + names[i]);                            break;                        } else if (i == nos.length - 1) {                            System.out.println("您要查询的员工不存在，请确认输入是否正确。");                        }                    }                    break;                case "4":                /*                修改两个操作：先输入员工号，查询员工号存在性，若不再，员工号输入有误，在，                先显示原有信息，再修改。                 */                    System.out.println("请输入要修改的员工号：");                    selection = sc.nextInt();                    for (int i = 0; i < nos.length; i++) {                        if (selection == nos[i]) {                            System.out.println("该员工原来的姓名为：" + names[i]);                            System.out.print("请输入要更改的姓名： ");                            name = sc.next();                            names[i] = name;                            System.out.println("修改成功，修改后的姓名为：" + names[i]);                            break;                        } else if (i == nos.length - 1) {                            System.out.println("您要修改的员工不存在，请确认输入是否正确。");                        }                    }                    break;                case "5":                /*                数组删除元素:                10个元素删除第五个                int [] = 0                String [] = null                 */                    System.out.println("请输入要删除的员工号：");                    selection = sc.nextInt();                    for (int i = 0; i < nos.length; i++) {                        if (selection == nos[i]) {                            System.out.println("该员工的姓名为：" + names[i] + " 是否要删除？\n输入1删除，其他键退出");                            int delete = sc.nextInt();                            if (delete == 1) {                                nos[i] = 0;                                names[i] = null;                                index -= 1;                                id -= 1;                                System.out.println("删除成功！");                            } else break;                            break;                        } else if (i == nos.length - 1) {                            System.out.println("您要查询的员工不存在，请确认输入是否正确。");                        }                    }                    break;                case "7":                    System.out.println("员工逆序输出");                    int tempNum;                    String tempStr;                    for (int i=0;i

转载地址：http://wxvduy.baihongyu.com/