DAY-13 数组与指针

1.整型数组指针的运算

（1）

对指针可以进行加法运算，即p + n。

其结果依旧是一个指针，新的指针是在原来的地址值基础上加上n * （sizeof（基类型））个字节。指针与指针之间不能进行求和运算。两个指针相减必须保持基类型一致，相差为基类型的个数。

eg：

#include int main(void){ int a[] = {1,2,3,4,5,6,7,8,9}; int *p; p = a; printf(\"%d\\n\", *p); printf(\"%d\\n\", *p++); printf(\"%d\\n\", *++p); printf(\"%d\\n\", *(a + 1)); return 0;}

注：p表示首元素的地址，所以*p表示首元素的值；p++表示表达式没加，但是p加了，所以*p++也是首元素的地址；++p表示表达式加了，p也加了，所以*++p就为下一个元素的值；*（a + 1）表示第一个元素的值，*（a + 1）就等于a[1]。

（2）

int *p

p = NULL;                      //不能进行间接访问

 （3）例题

①数组的两数求和函数

int sumOfTheArray(int *a, int len){ int sum = 0; int i; for(i = 0;i < len;++i) { sum += *(a + i); } return sum;}

②数组的逆序函数

void reverse(int *a, int len){ int i; for(i = 0;i < len / 2;++i) { int t; t = *(a + i); *(a + i) = *(a + len - i - 1); *(a + len - i - 1) = t; }}

③交换两数函数

void swap(int *a, int *b){ int t; t = *a; *a = *b; *b = t;}

④数组的选择排序函数

void sort(int *a, int len){ int i, j; for(i = 0;i < len - 1;++i) { for(j = i + 1;j  *(a + j)) { swap(a + i, a + j); } } }}

⑤数组的遍历函数

void printArray(int *a, int len){ int i; for(i = 0;i < len;++i) { printf(\"%d\\n\", *(a + i)); }}

⑥数组的二分查找函数

int binaryFind(int *a, int len, int n){ int begin = 0; int end = len - 1; int mid; while(begin  n) { end = mid - 1; } else if(*(a + mid) < n) { begin = mid + 1; } else { break; } } if(begin <= end) { return mid; } else { return -1; }}

注：上述函数均没有主函数。 

 （4）迭代器

①数组的遍历

#includevoid printArray(int *begin, int *end){ while(begin <= end) { printf(\"%d\\n\", *begin); ++begin; }}int main(void){ int a[] = {1,2,3,4,5,6,7,8,9}; int len = sizeof(a) / sizeof(*a); printArray(a, a + len - 1); return 0;}

②数组的逆序

#include void swap(int *a, int *b){ int t; t = *a; *a = *b; *b = t;}void reverse(int *begin,int *end){ while(begin < end) { swap(begin++, end--); }}int main(void){ int a[] = {1,-2,3,-4,5,-6,7,-8,9}; int len = sizeof(a) / sizeof(a[0]); reverse(a, a + len - 1); printArray(a, a + len - 1); return 0;}

③数组的选择排序 

#include void swap(int *a, int *b){ int t; t = *a; *a = *b; *b = t;}void choiceSort(int *begin, int *end){ int *p = NULL; for(;begin < end;++begin) { for(p = begin + 1;p  *p) { swap(begin , p); } } }}void printArray(int *begin, int *end){ while(begin <= end) { printf(\"%d\\n\", *begin); ++begin; }}int main(void){ int a[] = {1,-2,3,-4,5,-6,7,-8,9,0}; int len = sizeof(a) / sizeof(*a); choiceSort(a, a + len - 1); printArray(a, a + len - 1);}

④数组的二分法查找

#include void swap(int *a, int *b){ int t; t = *a; *a = *b; *b = t;}void choiceSort(int *begin, int *end){ int *p = NULL; for(;begin < end;++begin) { for(p = begin + 1;p  *p) { swap(begin , p); } } }}void *binaryFind(int *begin, int *end, int n){ while(begin  n) { end = mid - 1; } else if(*mid < n) { begin = mid + 1; } else { return mid; } } return NULL;}int main(void){ int a[] = {1,-2,3,-4,5,-6,7,-8,9}; int len = sizeof(a) / sizeof(a[0]); int n; scanf(\"%d\", &n); choiceSort(a, a + len - 1); int *ret = binaryFind(a, a + len - 1, n); if(ret == NULL) { printf(\"not found!\\n\"); } else { printf(\"found! value = %d\\n\", *ret); } return 0;}

（5）函数的递归调用与指针

①数组的遍历

#include void printArray(int *begin, int *end){ if(begin > end) { return ; } else { printf(\"%d\\n\", *begin); printArray(begin + 1, end); }}int main(void){ int a[] = {1,-2,3,-4,5,-6,7,-8,9}; int len = sizeof(a) / sizeof(a[0]); printArray(a, a + len - 1); return 0;}

 printArray(begin + 1, end); printf(\"%d\\n\", *begin);

说明：如果上述代码反过来写，则表明数组的元素反过来看，而不是逆序。

②数组的逆序

#include void swap(int *a, int *b){ int t; t = *a; *a = *b; *b = t;}void reverse(int *begin, int *end){ if(begin >= end) { return ; } else { swap(begin++, end--); reverse(begin, end); }}int main(void){ int a[] = {1,-2,3,-4,5,-6,7,-8,9}; int len = sizeof(a) / sizeof(a[0]); reverse(a, a + len - 1); printArray(a, a + len - 1); return 0;}

(6)快速排序（算法复杂度nlgn）

算法思想：

①从数组中选择一个元素作为基准数。通常选择数组的第一个元素

②自右往左找比基准数小的数。

③自左往右找比基准数大的数。

④交换两数。

⑤当两数的位置重合时，交换该数与基准数。

⑥对基准值左右两侧的子数组分别重复上述步骤（函数的递归）。

eg：

#include void swap(int *a, int *b){ int t = *a; *a = *b; *b = t;}void qSort(int *begin , int *end){ if(begin >= end) { return ; } else { int t = *begin; int *p = begin; int *q = end; while(p < q) { while(p = t) { --q; } while(p < q && *p  end) { return ; } else { printf(\"%d\\n\", *begin); printArray(++begin, end); }}int main(void){ int a[] = {1,-2,3,-4,5,-6,7,-8,9,0}; int len = sizeof(a) / sizeof(*a); qSort(a, a + len - 1); printArray(a, a + len - 1); return 0;}

注：先写出交换两数的函数，再写出快速排序的函数，再写出遍历的函数，最后用主函数调用上述三个函数来实现快速排序。