第五章知识点总结
数组
数组的定义：
之前在定义数据的时候，大部分都是用变量来存储数据如果我们的程序中出现大量的数据怎么办 ？
连续输入多个数字，连续输入多个坐标点，-般而言会创建多个变量存储这些数据，显得比较麻烦。
这些变量基本上类型是共通的，那我们就可以用一个容器将所有的数字进行管理。类似于字符串，
字符串其实就是若干个字符的容器而已，abc"可以通过索引/角标来获取其中某一个字符。
[1,2,3.4.5]类似字符串能够也可以通过索引/角标来获取其中某一个数字呢?那么这个容器我们称之为数组。
数组的用处：
数组主要解决多变量多数据的存储问题，方便程序后期统一维护操作数据
数组的本质：
数组的本质是什么呢?数组就是一系列空间大小相等目地址连续的一片存储空间 为什么空间大小是相等
的呢?就是为了方便统一维护我们的数据，必须得保证数据之间的类型是样的。 (多个同类型的变 量空间连在
一起组成的结构叫数组)
为什么变量空间的地址是连续的呢?就是为了方便统一操作我们的数据
数组的性质总结：
- 数组就是一片地址连续且空间大小一致的存储空间(但是每个空间存的还是其他数据的地址)
- 数组存在于堆内存中.但凡在堆中存储的数据都称之为对象但凡在堆内存中创建的对象都会有默认初始值
- 整数类型默认0
- 浮点类型默认0.0
- 布尔类型默认false
- 引用数据类型(对象)默认nut
3.数组提供角标来访问数组当中的元素
4.数组变量存的就是数组在堆内存中首元素的地址
5.数组通过角标来访问元素的具体计算方式是所要访问数据的地址=首元素地址+角标*数据类型大小
6.数组一旦定义下来，其长度不可改变;数组中有几个地址?就看数组有几个元素空间<==>数组的长度
7.创建数组时必须明确规定大小或内容
- 数据类型[]数组名= new数据类型[长度]; 创建数组只指定长度但不指定内容
- 数据类型[]数组名= new数据类型01,2,3,4,5}; 创建数组指定内容（指定长度）
- 数据类型0数组名={1,2,3,4.5); 创建数组指定内容（指定长度）
- []表示一维数组
- [] []表示二维数组
数组常见的错误
Array Index Out Of Bounds Exception 数组角标越界
Null Pointer Exception 空指针异常
基本数组操作
遍历
所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树（或图）中每个节点均做一次访问。访问结点所做的操作依赖于具体的应用问题， 具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。当然遍历的概念也适合于多元素集合的情况，如数组。
C#提供了foreach语句来遍历数组的所有元素
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace shuzhu2
{
class Program
{
static void Main(string[] args) {
int[] pins = { 1, 2, 4, 5 ,9,7,13};
foreach (int pin in pins)
{ Console.WriteLine(pin);
}
}
}
运行结果：1
2
4
5
9
7
13赋值
初始化赋值的一般形式为：static类型说明符数组名[常量表达式]={值，值……值}； 其中static表示是静态存储类型， C语言规定只有静态存储数组和外部存储数组才可作初始化赋值（有关静态存储，外部存储的概念在第五章中介绍）。
在{ }中的各数据值即为各元素的初值， 各值之间用逗号间隔。例如：static int a[10]={ 0,1,2,3,4,5,6,7,8,9 }; 相当于a[0]=0;a[1]=1...a[9]=9;
最大值最小值
数组中查找最大值和最小值 （两种方法）
//获取数组中元素的最大值，方法一
public static int getMax(int[] arr){
int max = arr[0];
for(int x=1; x<arr.length; x++){
if(arr[x]>max){
max = arr[x];
}
}
return max;
}
//获取数组元素中的最大值，方法二
public static int getMax_2(int[] arr){
int max = 0;
for(int x=1; x<arr.length; x++){
if(arr[x]>arr[max]){
max = x;
}
}
return max;
}
//获取数组元素中的最小值。
public static int getMin(int[] arr){
int min=arr[0];
for(int x = 1;x<arr.length;x++){
if(min>arr[x]){
min=arr[x];
}
}
return min;
}
//方法重载，具有相同的功能，不同的函数名。
public static double getMax(double[] arr){
return 0;
}
//求最小值的输出语句
public static void main(String[] args) {
int[] arr={4,5,2,6,8,3,7,3};
int max = getMax(arr);
int min = getMin(arr);
System.out.println(max);
System.out.println(min);
boolean[] ar = new boolean[4];
System.out.println(ar[2]);
}
}
//此处为求最大值的输出语句。
/*
public static void main(String[] args) {
int[] arr = {1,4,6,3,7,3,9,2};
int max = getMax_2(arr);
//System.out.println(max);
System.out.println(arr[max]);
}
}
学习测试代码
import java.util.Scanner;
class Test05{
public static void main(String[] args){
//遍历操作
// bianli();
//赋值操作
// fuzhi();
//最大值/最小值
maxormin();
}
public static void maxormin(){
//计算最大值或最小值的 值
//计算最大值或最小值的 角标
//需求 获取最大的值10 获取最小值的角标4
int[] arr={10,2,8,3,1,6,4,7,9,5};
int max=arr[0];
int min_index=0;
for(int i=0;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
if(arr[i]<arr[min_index]){
min_index=i;
}
}
System.out.println("最大值"+max);
System.out.println("最小值角标"+min_index);
}
public static void fuzhi(){
Scanner scanner=new Scanner(System.in);
// System.out.print("请输入10个数字：");
int[] arr2=new int[10];
for(int i=0;i<arr2.length;i++){
System.out.print("请输入1个数字：");
arr2[i]=scanner.nextInt();
}
for(int i=0;i<arr2.length;i++){
System.out.print(arr2[i]+" ");
}
}
public static void bianli(){
int[] arr={1,2,3,4,5,6,7,8,9};//[0,8]
//数组只有一个唯一的属性 length 数组的长度
System.out.println(arr.length);
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
}查找操作
线性查找
线性算法顾名思义就是从头找到尾的查找，实现起来还算是非常简单的，例如for循环就能搞定。
import java.util.Arrays;
class Xianxing{
public static void main(String [] args){
int[] array = new int[] {2,3,5,6,9,23,4,0}//要查找的数组
int targetData = 9; //要查找的数据
//要查找的数据所在的位置，如果最后大于-1，说明找到了，等于-1说明没找到
int index = -1;
for(int i=0;i<array.length;i++){
if(targetData == array[i]){ //如果相等说明找到了
index= i; //把位置赋值给index
break; //找到了就跳出循环
}
}
System.out.println("查找的下标是："+ index);
}
}
二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
算法要求：
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。
class Test06{
public static void main(String[] args){
//线性查找
//linearSearch();
//二分查找
binarySearch();
}
public static void binarySearch(){
//二分查找有个前提 数组必须有序
/*
最好情况 查46 1次就出来了
最坏情况 查12/60 O(logn)
*/
int[] arr={12,17,21,32,38,41,46,49,50,50,51,59,60};
int key=46;
int index=-1;
int min_index=0;
int max_index=arr.length-1;
int mid_index=(min_index+max_index)/2;
while(arr[mid_index]!=key){
if(key<arr[mid_index]){
max_index=mid_index-1;
}
if(arr[mid_index]<key){
min_index=mid_index+1;
}
if(min_index>max_index){
index=-1;
break;
}
mid_index=(min_index+max_index)/2;
}
System.out.println(mid_index);
}
public static void linearSearch(){
/*
最好情况 查10 1次就出来了
最坏情况 查5 10次才出来
当数组的长度越大的话 最坏情况越差
时间复杂度(最坏情况) O(n) 线性阶
*/
int[] arr={10,2,8,3,1,6,4,7,9,5};
int key=11;
int index=-1; //key元素不存在
for(int i=0;i<arr.length;i++){
if(arr[i]==key){
index=i;
break;
}
}
System.out.println(index);
}
}
斐波那契查找
斐波那契搜索(Fibonacci search) ，又称斐波那契查找，是区间中单峰函数的搜索技术。
斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
原理
斐波那契搜索是一种有限区间中单峰函数的搜索技术。为简单起见，设此区间为L1=[0，1]，记{Fi}为斐波那契数，
第一次估值点为：
和
其中，1/Fn应等于或小于搜索的预期精度。若f(x1)>f(x2)，则删去(x2，1]，反之删去[0，x1)。以L1记删去的区间，再对留下的区间L2取：
其中，
为
的长度。对L2重复上述步骤。如此反复直到：
已经证明，斐波那契搜索是一种函数估值次数最少的最优搜索方法
上一篇： Nginx配置中的if判断
下一篇： 利用分页和模糊查询技术实现一个App接口