7.1 数组
7.1.1 数组运算
先用C语言做最简单的搜索：在一组给定的数据中，如何找出某个数据是否存在？
int search(int key, int a[], int length);
int main() {
int a[] = {2, 4, 6, 7, 8, 9, 10, 32, 57, 81, 0, 77};
int x;
int result;
scanf("%d", &x);
result = search(x, a, sizeof(a)/sizeof(a[0]));
if(result!=-1) {
printf("你要查找的%d，它的位置是%d", x, result);
} else {
printf("你所要查找的元素不存在");
}
return 0;
}
int search(int key, int a[], int length) {
int ret=-1;
int i;
for(i=0;i<length;i++) {
if(key==a[i]) {
ret = i;
break;
}
}
return ret;
}
数组的集成初始化
int a[] = {2, 4, 6, 7, 8, 9, 10, 32, 57, 81, 0, 77};
//也可以int a[] = {2, 4, 6, 7, 8, 9, 10, 32, 57, 81, 0, 77,};这是一种古老的习惯方式
-
另一种初始化方式
int a[10] = {0}//这样会将数组的初始值全变为0 //原理:int a[12] = {2}, 这样的话，除了a[0]=2以外，其它的都会变为0 -
直接用大括号给出数组的所有元素的初始值
-
不需要给出数组的大小，编译器替你数
集成初始化时的定位（C99 only）
int a[10] = {
[0]=2, [2]=3, 6
}
-
用[n]在初始化数据中给出定位
-
没有定位的数据接在前面的位置后面
-
其它位置的值补零
-
也可以不给出数组的大小，让编译器算（也就是在最大下标的定位数据+1就是数组的元素数量）
-
特别适合初始数据稀疏的数组
-
案例：
-
案例一
int a[13]={ [1]=2, 4, [5]=6 }; { int i; for(i=0;i<13;i++) { printf("%d\t", a[i]); } } -
案例二
int a[]={ [1]=2, 4, [5]=6 }; { int i; for(i=0;i<6;i++) { printf("%d\t", a[i]); } }
-
数组的大小
-
sizeof给出整个数组所占据的内容的大小，单位是字节
sizeof(a)/sizeof(a[0])
-
sizeof(a[0])给出数组中的单个元素的大小，于是相除就得到了数组的单元个数
-
这样的代码，一旦修改数组中初始的数据，不需要修改遍历的代码
数组的赋值
-
int a[] = {2, 4, 6, 7, 8, 9, 10, 32, 57, 81, 0, 77}; int b[] = a; //上面的代码是否能将数组a赋给b？ -
数组变量本身不能被赋值，上面的代码是不对的
-
要把一个数组的所有元素交给另一个数组，必须采用遍历
for(i=0;i<length;i++) { b[i]=a[i]; }
数组的遍历
数组为传参
7.1.2 数组例子：素数
怎么判断是不是素数呢？
int isPrime(int x) {
int ret = 1;
int i;
if(x==1) ret = 0;
for(i=2;i<x;i++) {
if(x%i==0) {
ret = 0;
break;
}
}
return ret;
}
- 从2到x-1测试是否可以整除
- 对于n要循环n-1遍
- 当n很大时就是n遍
算法二：去掉偶数后，从3到x-1，每次加2
int isPrime(int x) {
int ret = 1;
int i;
if(x==1||(x%2==0&&x!=2)) ret=0;
for(i=3;i<x;i+=2) {
if(x%1==0;) {
ret=0;
break;
}
}
return ret;
}
- 如果x是偶数，立刻返回0；
- 否则要循环（n-3）/2+1遍
- 当n很大时就是n/2遍
算法三：无须到x-1，到sqrt（x）就够了
int isPrime(int x) {
int ret = 1;
int i;
if(x==1||(x%2==0&&x!=2)) ret=0;
for(i=3;i<sqrt(x);i+=2) {
if(x%1==0;) {
ret 0;
break;
}
}
return ret;
}
- 只需要循环sqrt(x)遍
7.2 搜索
7.2.1 线性搜索
搜索
- 在一个数组中找到某数的位置，或确认是否存在
- 基本方法：遍历
int search(int key, int a[], int len) {
int ret = -1;
for(int i=0; i<len; i++) {
if(key==a[i]) {
ret = i;
break;
}
}
return ret;
}
- 我们要具备“单一出口原则”
7.2.2 搜索的例子
利用哈希表
struct {
int amount;
char *name;
} coins[] = {
{1, "penny"},
{5, "nickel"},
{10, "dime"},
{25, "quarter"},
{50, "half-dollar"}
};
int key;
scanf("%d", &key);
int i;
for(i=0; i<sizeof(coins)/sizeof(coins[0]); i++) {
if(key==coins[i].amount) {
printf("%s", coins[i].name);
break;
}
}
7.2.3 二分查找法
#include <stdio.h>
int search(int key, int arr[], int len);
int main() {
int a[] = {2, 5, 7, 8, 9, 10, 16, 17, 19, 20, 29, 35, 36};
int key;
printf("%d", search(key, a, sizeof(a)/sizeof(a[0])));
return 0;
}
int search(int key, int arr[], int len) {
int left = 0;
int right = len - 1;
while(right>left) {
int mid = (left+right)/2;
if(arr[mid]>key) {
right = mid - 1;
} else if(arr[mid]==key) {
return mid;
} else {
right = mid + 1;
}
}
}
搜索效率是log2 x
7.3.1 排序算法
选择排序（我的版本）
#include <stdio.h>
void make(int a[], int len);
int main() {
//int a[] = {7, 8, 3, 4, 9, 1, 0, 2, 5};
int a[] = {7, 8, 3, 4, 9, 1};
make(a, sizeof(a)/sizeof(a[0]));
return 0;
}
void make(int a[], int len) {
int min;
int i, j;
for(i=0;i<len-1;i++) {
min = a[i+1];
for(j=i+1;j<len;j++) {
if(min>a[j]) {
min = a[j];
a[j] = a[i];
a[i] = min;
}
}
{
int c;
printf("第%d次：", i);
for(c=0;c<len;c++) {
printf("%d\t", a[c]);
}
printf("\n");
}
}
for(i=0;i<len;i++) {
printf("%d\t", a[i]);
}
}
-
上面这个代码会存在着问题，问题就是：“它会排成1，3，4，7，9，8”
-
解决方案是：
for(i=0;i<len-1;i++) { min = a[i];//修改了这里 for(j=i+1;j<len;j++) { if(min>a[j]) { min = a[j]; a[j] = a[i]; a[i] = min; } } { int c; printf("第%d次：", i); for(c=0;c<len;c++) { printf("%d\t", a[c]); } printf("\n"); } }
选择排序（第二版）
#include <stdio.h>
int main() {
int a[] = {7, 8, 3, 4, 9, 1};
int len = sizeof(a)/sizeof(a[0]);
int i, max, j;
for(i=len-1;i>0;i--) {
max = a[i];
for(j=0;j<=i;j++) {
if(max<a[j]) {
max = a[j];
a[j] = a[i];
a[i] = max
}
}
}
for(i=0;i<len;i++) {
printf("%d ", a[i]);
}
return 0;
}
8.1 指针
8.1.1 取地址运算
sizeof
- 是一个运算符，给出某个类型或变量在内存中所占据的字节数
- sizeof(int)
- sizeof(i)
- 输出：printf("%ld", sizeof(double))
- ld是长整数型
运算符&
-
scanf("%d", &i);里的&
-
获得变量的地址，它的操作数必须是变量
int i=0; printf("0x%x", &i);//不对 printf("%p, &i");//得到一个地址 //但是 int i = 0; int p; p=(int)&i;//int是强制转化 printf("0x%x", p); -
还有另一个事情，在不同位数的架构下，地址也不一样
-
地址的大小是否与int相同取决与编译器
- int i; printf("%p", &i);
内存存储
- i和p都存在一个叫堆栈里的地方，是从自顶向下来排
- 先写的会更高
试试这些&
-
变量的地址
-
相邻变量的地址
-
&的结果的sizeof
-
数组的地址
-
数组的单元的地址
-
相邻的数组单元的地址
-
试验代码
int i[10]; printf("%p\n", &i);//0xbff8dd44 printf("%p\n", i);//0xbff8dd44 printf("%p\n", i[0]);//0xbff8dd44 printf("%p\n", i[1]);//0xbff8dd48
8.1.2 指针
scanf
- 如果能够将取得的变量的地址传递给一个函数，能否通过这个地址咋那个函数内访问这个变量？
- scanf("%d", &i);就是一个例子
- scanf()的原型应该是怎样的？我们需要一个参数能保存别的变量的地址，如何表达能够保存地址的变量？
- 是否可以运用到赋值数组呢？
指针
-
就是保存地址的变量
int i; int* p = &i;//p是一个指针，*表示了出来，表示指向了是一个int，用来存储i的地址 //可以说“p指向了i”，也就是p得到了i的地址了 int* p, q;//这里，p是指针，但q是一个普通的int类型变量 int *p, q;//可以靠近也可以不靠近，这个*不是给int的 //想表达q也是指针怎么写？ int *p, *q;
指针变量
- 变量的值是内存的地址
- 普通变量的值是实际的值
- 指针变量的值是具有实际值变量的地址
作为参数的指针
- void f(int *p);
- 在被调用的时候得到了某个变量的地址：
- int i=0; f(&i);
void f(int *p);
int main() {
int i = 6;
printf("%p\n", &i);
f(&i);
return 0;
}
void f(int *p) {
printf("%p\n", p);
}
- 在函数里面可以通过这个指针访问外面的这个i
- 但不知道它叫做i，只知道地址
- 不像和普通函数一样只能传值进去而无法做到访问那个函数外面的变量
- 而当我们可以访问这个地址的时候，这就意味着我们可以读，可以写了
访问那个地址上的变量
- *是一个单目运算符，用来访问指针的值所表示的地址上的变量
- 可以做右值也可以做左值
- int k = *p;
- *p = k+1;
#include <stdio.h>
void f(int *p);
void g(int k);
int main() {
int i = 6;
printf("%p\n", &i);
f(&i);
g(i);
return 0;
}
void f(int *p) {
printf("%p\n", p);
printf("%d\n", *p);//输出值
*p=36; //改变了外面变量的值了
}
void g(int k) {
printf("%d\n", k);
}
传入地址
- 为什么？
- int i; scanf("%d", i);
- 编译没有报错？
- 但运行会出错
传入函数的数组成了什么？
- 函数参数表中的数组实际上是指针
- sizeof(a) == sizeof(int*)
- 但是可以用数组的运算符[]进行运算
数组参数
-
以下四种函数原型是等价的
int sum(int *ar, int n); int sum(int *, int); int sum(int ar[], int n); int sum(int [], int);
访问函数外数组案例
#include <stdio.h>
int maxmin(int a[], int len, int *max, int *min);
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 18, 11, 10};
int max, min;
maxmin(a, sizeof(a)/sizeof(a[0]), &max, &min);
printf("%d %d", max, min);
return 0;
}
int maxmin(int a[], int len, int *max, int *min) {
int i;
*max = *min = a[0];
for(i=0;i<len;i++) {
if(a[i]>*max) *max=a[i];
if(a[i]<*min) *min=a[i];
}
printf("%d", sizeof(a));
printf("%d", sizeof(int*));
}
数组变量是特殊的指针
-
数组变量本身表达地址，所以
- int a[10]; int*p=a;//无需用&取地址
- 但是数组的单位表达式变量，需要用&取地址
- a==&a[0]
-
[]运算符可以对数组做，也可以对指针做；
-
p[0]<==>a[0]
int *p = &min; printf("%d\n", *p); printf('%d\n', p[0]);
-
-
*运算符可以对指针做，也可以对数组做
- *a=25;
-
数组变量是const的指针，所以不能被赋值
- int a[] <==> int * const a = ...
int b[];=====int * const b;//所以数组是个常量指针，所以不能被赋值 b=a;//这样的赋值数组是错误的 int *q = a;//这个可以
