DAY-13 数组与指针

1.整型数组指针的运算

（1）

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

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

eg：

#include <stdio.h>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 < len;++j){if(*(a + i) > *(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 <= end){mid = (begin + end) / 2;if(*(a + mid) > n){end = mid - 1;}else if(*(a + mid) < n){begin = mid + 1;}else{break;}}if(begin <= end){return mid;}else{return -1;}
}

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

 （4）迭代器

①数组的遍历

#include<stdio.h>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};int len = sizeof(a) / sizeof(*a);printArray(a, a + len - 1);return 0;
}

②数组的逆序

#include <stdio.h>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 <stdio.h>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 <= end;++p){if(*begin > *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 <stdio.h>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 <= end;++p){if(*begin > *p){swap(begin , p);}}}
}void *binaryFind(int *begin, int *end, int n)
{while(begin <= end){int *mid = (end - begin) / 2 + begin;if(*mid > 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 <stdio.h>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 <stdio.h>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 <stdio.h>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 < q && *q >= t){--q;}while(p < q && *p <= t){++p;}swap(p, q);}swap(begin,p);qSort(begin, p - 1);qSort(p + 1, end);}
}void printArray(int *begin, int *end)
{if(begin > 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;
}

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