数据结构
1、数据是最基本的数据结构；是一张表，线性表（数据元素之间是一对）
除了第一个元素和最后一个之外，其余元素都是首尾链接
2、链表
3、树
写程序的思路：
1、先完成需求要求的功能
2、根据程序运行的结果进行优化处理
3、代码重构
4、提升效率
查找算法：
线性查找：简单，便于理解
练习1：
找出一个数在数组中的位置
?在数组中是否存在，如果存在，返回下标，如果不存在，返回-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 sc = new Scanner(System.in);
System.out.println("请输入一个数：");
int num = sc.nextInt(); int index = -1;
for (int i = 0;i < arr.length; i++) {
if(arr[i] == num) {
index = i;
break;
}
if(index != -1) {
System.out.println("你要找的数是：" + num + "，在目标数组中的下标是：" + index);
}else {
System.out.println("你要找的数是：" + num + "，在目标数组中不存在");
}
}
}
二分法查找：如果要使用二分法查找数字，前提是这个数组必须有顺序
? ? ? ? ?
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 sc = new Scanner(System.in);
System.out.println("请输入要查找的数字：");
int target = sc.nextInt();
// 最左边的下标
int left = 0;
// 最右边的下标
int right = arr.length - 1;
if(target < arr[left] || 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;
// left = arr.length;
break;
}else if(arr[middle] > target){
// 说明我们要找的数在数组的前半区
/*
如果在前半区
维护left和right
left是不需要动的
right应该移位到中间位置
*/
right = middle - 1;
}else {
// 条件实际上就是arr[middle]<target
/*
说明在后半区
right是不需要动的
left应该向右移位到中间位置
*/
left = middle + 1;
}
}
System.out.println(target + "在目标数组中的下标是：" + res);
}
}
}
排序算法：（不懂）
1、冒泡
思路分析：先拿第一个数和后面的数一一比较大小
? ? ? ? ? ?冒泡排序需要两层循环嵌套：for
? ? ? ? ? ? 外层for循环控制的是需要各个数之间比较几轮
? ? ? ? ? ? 内层的for循环控制的是每个数的真正的比较
? ? ? ? ? ?
ublic class Ch03 {
public static void main(String[] args) {
int [] arr = new int[]{1,58,460,-33,10,5,-8};
for (int i = 0; i < arr.length - 1; i++) {
//已经控制好了比较的次数
// 比较的次数 = 数组的长度 - 1
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j] < arr[j+1]){
// 如果前面的比后面的大，换位
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.print("第" + (i + 1) + "轮的比较结果是：");
for (int i1 : arr) {
System.out.print(i1 + "、");
}
System.out.println();
}
}
}
2、快速排序
3、插入排序
public class Ch02 {
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;
// 当上一个数的下标有效不能小于0
// 并且还要保证当前的数比他上一个数小，
// 这时候，才能让当前数向前移位
while(preIndex >= 0 && current < arr[preIndex]){
// 移位
// 前面的数后移一位
arr[preIndex + 1] = arr[preIndex];
//
preIndex--;
}
arr[preIndex + 1] = current;
}
for (int i : arr) {
System.out.print(i + "、");
}
}
}
4.选择排序
ublic class Ch01 {
public static void main(String[] args) {
int [] arr = new int[]{1,25,48,12,10,-8,127,56};
for (int i = 0; i < arr.length; i++) {
// 假设最小数的下标
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[minIndex]>arr[j]){ // 找到了最小值
minIndex = j; //保存最小值的下标
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
System.out.print("第" + (i+1) + "次比较结果是：");
for (int i1 : arr) {
System.out.print(i1 + "、");
}
System.out.println();
}
}
5、希尔排序
6、堆排序
7、归并排序
8、插排序
排序的简便操作：
import java.util.Arrays;
public class Ch04 {
public static void main(String[] args) {
int [] arr = new int[]{1,58,460,-33,10,5,-8};
// 从小到大
Arrays.sort(arr);
for (int i : arr) {
System.out.println(i);
}
}
}
数组的反转
方法一：交换元素
import java.util.Arrays;
public class Ch03 {
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));
}
}
数组的扩容
/**
* 数组的扩容
*/
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));
}
}
|