数组导图笔记

本导图梳理的知识点有一维数组的定义和初始化、二维数组的定义和初始化、向函数传递一堆数组、排序和查找等。

数组和算法基础

• 一维数组的定义和初始化
  • 把数组长度用宏常量或const常量来定义
  • C89规定不用使用变量定义数组大小，C99可
  • 定义但未进行初始化的数组幸元素的值仍是随机数
  • 省略长度，会自动确定数组大小（进行了初始化）
  • 当数组在所有函数外定义，或用static定义，元素自动初始化为0
  • 类型 数组名[元素个数]
• 二维数组的定义和初始化
  • 数组第二维的长度声明永远都不能省略！
    • 类型 数组名[第一维长度][第二维长度]
• 向函数传递一维数组
  • 不带方括号的数组名作为函数实参调用函数
  • 形参与实参数组占用的是同一段存储空间 而用简单变量作为函数实参，传递的是变量的内存
  • 数组作函数形参时，数组的长度可以不出现在方括号内，用另一个整形变量来指定数组长度
    • 方括号内的数字并不能真正表示接收的数组大小
• 排序和查找
  • 排序
    • 交换法排序
      • for(i=0;i<n-1;i++) { for(j=i+1;j<n;j++) { if(a[j]>a[i]) 交换....; } }
    • 选择法排序
      • for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) { if(a[j]>a[k]) k=j; } if(k!=i) 交换...... }
  • 查找
    • 线性查找
      • 无序
    • 折半查找
      • int low=0,high=n-1,mid; while(low<=high) { mid=(high+low)/2; if(x>num[mid]) low=mid+1; else if(x<num[mid] high=mid-1; else return mid; } return -1;
        • 有序
        • mid=low+(high-low)/2
• 向函数传递二维数组
  • 数组元素在存储器中都 是按行的顺序连续存储的 必须知道一行有多少元素（列长）