黑马程序员技术交流社区
标题:
第九天笔记
[打印本页]
作者:
895928691
时间:
2015-7-24 21:30
标题:
第九天笔记
基础班第九天学习笔记
作者:
895928691
时间:
2015-7-24 21:32
第9天总结
1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。
在这一点,最后的元素应该会是最大的数。
3)针对所有的元素重复以上的步骤,除了最后一个。
4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
for (int i=0; i<len-1; i++)
//每趟排序都会确定一个数,所以需要再循环len-i次,但因为每次都是 //相邻的两个数进行比较,为了a[j+1]不越界,让j循环到len-i-1时停止。
for (int j=0; j<len-i-1; j++) {
//若arr[j]>arr[j+1] 若前一位比后一位元素大,则交换顺序
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
//------------------选择排序思想
外层 len-1 里层 j=i+1 j<len
int a[10]={23,12,4,67,20,100,21,45,3,28};
假设a[0]为最小,分别与a[1] a[2] ... 比较, 在比较过程中,如果有元素的值比a[0]小,交换值
第一种方法
//每一趟都是拿着一个元素与后面其他元素进行比较,找出最小值
void selectSort1(int array[],int len){
// 1、确定需排序趟数
for (int i = 0 ; i < len - 1; i++) { // 2、每一趟怎么处理
for (int j = i + 1; j < len; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
temp = arr[i];
arr[i]=arr[min];
arr[min] = temp; }
}
//打印数组
for (int i=0; i<len; i++) {
printf("%d\t",arr[i]); }
}
//----- 冒泡:
外层for (int i=0; i<len-1; i++)
内层for (int j=0; j<len-i-1; j++)
//----- 选择排序:
外层for (int i=0; i<len - 1; i++)
内层for (int j=i+1; j<len; j++)
//------------------折半查找思想
思路: 先划分空间,再在其空间查找,取中间点,中间点往左,元素的值一定比中间值小,右边的值一定比中间值大.
判断关键点 if (key>arr[mid]) {low = mid+1;} //右半区查找
if (key<arr[mid]){high = mid - 1;} //左半区查找
找12
low high
0 1 2 3 4 5 6 7 8 9
// 3412202123284567100
--------------------------------------------
1 low mid high
2 low mid high
3 low high
mid = (low + high) / 2 = 4;
a[4] = 21 > 12 --> high = mid - 1 ---> 4 - 1 = 3
mid = (low + high)/2 = 1;
a[1] = 4 < 12 --> low = mid + 1 --> 1+1 = 2
mid = (2+3)/2 --> 2
a[2] = 12 == 12
//折半查找
int searchItem(int arr[],int len,int key){
//先要定义变量
int low=0,high=len-1,mid;
//循环
while (low<=high) {
// 计算 mid的位置
mid = (low+high)/2;
printf("mid = %d",mid);
// 判断 key a[mid],右半区查找
if (key>arr[mid]) {
// key > a[mid] low = mid +1;
low = mid+1;
}elseif (key<arr[mid]){
// key < a[mid] high = mid -1;
high = mid - 1;
}else{
// key == a[mid] //return mid;
return mid;
}
}
// 下面是查找不到的情况
return -1;
}
int insertItemLoc(int arr[],int len,int key){
//先要定义变量
int low=0,high=len-1,mid;
//循环
while (low<=high) {
// 计算 mid的位置
mid = (low+high)/2;
// 判断 key a[mid],右半区查找
if (key>arr[mid]) {
// key > a[mid] low = mid +1;
low = mid+1;
}elseif (key<arr[mid]){
// key < a[mid] high = mid -1;
high = mid - 1;
}else{
// key == a[mid] //return mid;
return mid + 1;
}
}
// 下面是查找不到的情况
return low;
}
//---------------------二维数组
回顾://----------------------一维数组
如果一个数组的所有元素都不是数组,那么该数组称为一维数组
二维数组定义的一般形式是:
类型说明符数组名[常量表达式1][常量表达式2]
二维数组定义注意事项:
1)数组名严格遵守标识符命名规范
2)二维数组名不能和变量同名int a;
int a[2][3];
3)数组长度可以是常量,也可以是常量表达式
int a[2+1][3+3]; //相当于定义了int a[3][5];
4)二维数组长度可以是宏定义
5)xcode编译器支持,C99标准不允许的写法
int x=3,y=4;
int a[x][y]; //相当于定义了int a[3][4];
6) 只定义不初始化,不可以省略长度
int arr[2][3] = {1,2,3, ---> {{第一行元素(一维数组)}
4,5,6} 第二行元素(一维数组)}}
2行3列
/*
| a[0] a[1] a[2] 第二维
-----------------------
a[0] | 1 2 3
a[1] | 4 5 6
第一维
*/
//--------------------二维数组初始化
二维数组可:
1)按行分段赋值
2)也可按行连续赋值。
1、定义同时初始化
2、先定义后初始化
数组名[行][列]
int a[5][6];
部分初始化,其余自动初始化为0
二维数组可以看作是由一维数组的嵌套而构成的。
二维数组初始化,不能省略第二维
int a[4][3] = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
/*
| a[0] a[1] a[2] 第二维
-----------------------
a[0] | 1 2 3
a[1] | 4 5 6
a[2] | 7 8 9
a[3] | 10 11 12
第一维
*/
//--------------------二维数组遍历
二维数组的元素也称为双下标变量
数组名[第一维下标][第二维下标]
数组名[行][列]
for外层循环控制行数
for内层循环控制列数
int score[5][3] = {{80,75,92},
{80,75,92},
{80,75,92},
{80,75,92},
{80,75,92}};
//--------------------二维数组存储
存储方式:
1)计算机会给二维数组分配一块连续的存储空间
2)数组名代表数组的首地址,从首地址位置,依次存入第1行、第2行、.....
3)每一行存储方式,从行首地址还是,依次存储行的第1个元素、第2个元素、第3个元素......
4)每个元素占用相同的字节数(取决于数组类型)
5)并且数组中元素之间的地址是连续。
arr == &arr[0] == arr[0] == &arr[0][0]
arr (数组名 指向第一行元素的地址)
&arr[0](第一行元素的地址)
arr[0](指向第一行第一个元素的地址)
&arr[0][0](第一个元素的地址)
int arr[3][4] = {{第一行3个元素(第一行一维数组)}, ----> arr[0]
{第二行4个元素(第二行一维数组)}, ----> arr[1]
{第三行4个元素(第三行一维数组)}}; ----> arr[2]
arr是一个二维数组
总计占用字节数: sizeof(arr);
每行占用字节数: sizeof(arr[0]);
行数: 总字节数/每行字节数 --> sizeof(arr)/sizeof(arr[0]);
列数: 行数/每个类型 --> sizeof(arr[0])/sizeof(int)
//应用:求多人多门课平均成绩
//找最大值
//-------------------二维数组做函数参数
1、二维数组元素作为函数参数
二维数组元素作为函数参数,相当于变量的值传递过程。
2、二维数组名作为函数参数
二维数组名作为函数参数,相当于地址传递。
1)在被调用函数中对形参数组定义时可以指定所有维数的大小,也可以省略第一维的大小说明,
如:
void Func(int array[3][10]);
void Func(int array[][10]);
注意: 二者都是合法而且等价,但是不能把第二维或者更高维的大小省略,
不合法的:
void Func(int array[][]);
void Func(int array[3][]);
一定不能省略第二维
2)实参数组维数可以大于形参数组
形参数组只取实参数组的一部分,其余部分不起作用。
3)类型长度要一致
//---------------------从键盘接收数据构成二维数组
输出
void printArray(int m,int n,int a[m][n]){
for (int i = 0; i<m; i++) {
for (int j=0; j<n; j++) {
printf("%d\t",a[i][j]);
}
printf("\n");
}
}
输入
void initArray(int m,int n,int a[m][n]){
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
printf("请输入第%d行第%d列元素赋值\n",i,j);
scanf("%d",&a[i][j]);
}
}
}
//---------------------《迷宫》
/*
| a[0] a[1] a[2] 第二维
-----------------------
a[0] | 1 2 3
a[1] | 4 5 6
a[2] | 7 8 9
a[3] | 10 11 12
第一维
######
#O##
# ## #
# # #
## #
######
*/
判断下一个位置是否是路,是路就让这两个值交换
假设往下走
//核心要知道小人的下一个位置是否是路
if (map[currentX-1][currentY]==street) {
//让小人开始移动，移动的核心：小人和路交换
char temp;
// map[currentX][currentY]; 小人当前位置
// map[currentX-1][currentY];小人的下一个位置
temp = map[currentX][currentY];
map[currentX][currentY] = map[currentX-1][currentY];
map[currentX-1][currentY] = temp;
//重新记录小人的当前位置
currentX--;
}
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2