总结2

算法二分法例子 排序算法数据结构实现升序动态数组

算法

1.暴力法 2.二分法：一次处理筛选一半 3.动态规划 4.回溯法 5.贪婪算法

二分法例子

#include <stdio.h> /* 函数功能：给一个升序的数组，用二分法查找出指定数据的下标 函数参数：int* arr 升序的数组 int len 数组的长度 int data 要查找的数据 函数返回值：找到返回下标，未找到返回-1 */ int selectPos(int* arr, int len, int data) { int l = 0, r = len - 1;//l最左边 r最右边 while(l <= r){ //数组一分为二 int m = (l + r) / 2; //找到就返回 if(arr[m] == data){ return m; } else if(arr[m] > data){ //此时，m往后是不可能有跟data一样的数据 r = m -1; }else{ l = m + 1; } } return -1; } int main(void) { int arr[] = {3,4,5,6,7,8,9}; int val = 0; printf("请输入要查找的数："); scanf("%d", &val); printf("要查找的数在数组中的下标为：%d\n", selectPos(arr, sizeof(arr) / sizeof(int), val)); return 0; }

排序算法

时间复杂度最大次数稳定性冒泡排序n^2n^2稳定选择排序n^2n^2不稳定插入排序n^2n^2稳定快速排序n long(n)n^2不稳定归并排序（链表）n long(n)n long(n)稳定 #include <stdio.h> #include <stdlib.h> #include <time.h> #define N (10) int arr[N]; //冒泡排序 void bubbleSort(int* arr, int len); //选择排序 void selectSort(int* arr, int len); //插入排序 void insertSort(int* arr, int len); //快速排序 void quickSort(int* arr, int len); int main(void) { srand(time(0)); int i; //冒泡排序 for(i = 0; i < N; i++){ arr[i] = rand() % N; } bubbleSort(arr, N); for(i = 0; i < N; i++){ printf("%d ", arr[i]); } printf("\n"); //选择排序 for(i = 0; i < N; i++){ arr[i] = rand() % N; } selectSort(arr, N); for(i = 0; i < N; i++){ printf("%d ", arr[i]); } printf("\n"); //插入排序 for(i = 0; i < N; i++){ arr[i] = rand() % N; } insertSort(arr, N); for(i = 0; i < N; i++){ printf("%d ", arr[i]); } printf("\n"); //快速排序 for(i = 0; i < N; i++){ arr[i] = rand() % N; } quickSort(arr, N); for(i = 0; i < N; i++){ printf("%d ", arr[i]); } printf("\n"); return 0; } void bubbleSort(int* arr, int len) { int i, j; /*外循环为排序躺数，len个数进行len-1趟*/ for(i = 0; i < len - 1; i++){ /*内循环为每趟比较的次数，第i趟比较len-i次*/ for(j = 0; j < len - i - 1; j++){ /*相邻元素比较，若逆序则交换*/ if(arr[j] > arr[j+1]){ int tem = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tem; } } } return; } void selectSort(int* arr, int len) { int i, j; for(i = 0; i < len - 1; i++){ /*查找最小的数*/ int min = i; for(j = i + 1; j < len; j++){ if(arr[min] > arr[j]){ //交换 min = j; } } /*放到前面排序*/ if(i != min){ int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } return; } void insertSort(int* arr, int len) { int i, j; for(i = 1; i < len; i++){ int tmp = arr[i];//记录i的数据 for(j = i -1; j >= 0 && tmp < arr[j]; j--){ arr[j+1] = arr[j]; } arr[j+1] = tmp; } } static void quickSortPrivate(int* arr, int left, int right) { if(left >= right){ return; } int l = left, r = right, key = arr[left]; while(l < r){ //往左遍历 while(l < r && key <= arr[r]){ r--; } arr[l] = arr[r]; while(l < r && key >= arr[l]){ l++; } arr[r] = arr[l]; } //l == r arr[l] = key;//key排序完毕 quickSortPrivate(arr, left, l - 1); quickSortPrivate(arr, r + 1, right); } void quickSort(int* arr, int len) { quickSortPrivate(arr, 0, len - 1); }

数据结构

数据结构：解决多个数据的有效管理->增删改查排 从结构[数据存储结构]上来看，数据结构两种：数组、链表 从功能[数据存储方式]上来看，数据结构两种：线性、关联 结构：1.连续内存存放[数组] 2.不连续内存存放[链表] 特点：数组因为内存连续，因此可以下标访问   链表因为内存不连续，因此增删不需要移动数据 功能：   1.线性数据结构表示插入数据的顺序，直接关系到数据的位置   2.关联数据结构表示插入数据的大小，直接关系到数据的位置

实现升序动态数组

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> typedef struct Array{ int* data;//指向内存 int idx;//存了多少(字节) int capa;//能存多少 }array_t; array_t* arrayInit(void); void arrayFree(array_t* array); int* arrayPushBack(array_t* array, int data); void arrayPopBack(array_t* array); int* arrayIndex(array_t* array, int idx); void arraySort(array_t*, int (*compare)(int, int)); int main() { array_t* arr = arrayInit(); int i; for(i = 0; i < 10; i++){ arrayPushBack(arr, rand() % 10); } arraySort(arr, NULL); for(i = 0; i < 10; i++){ printf("%d\n", *arrayIndex(arr, i)); } arrayFree(arr); arr = NULL; return 0; } array_t* arrayInit(void) { /*开辟一块堆空间存放动态数组*/ array_t* array = (array_t*)malloc(sizeof(array_t)); memset(array, 0, sizeof(array_t)); array->idx = 0;//存放了0个字节数据 array->capa = 1;//能存一个字节的数据 /*申请一个指向数据域的堆空间，堆空间的大小根据capa来决定*/ array->data = malloc(sizeof(int) * array->capa); memset(array->data, 0,sizeof(int) * array->capa); return array; } /*释放堆空间*/ void arrayFree(array_t* array) { /*检查健壮性*/ if(array == NULL)return; free(array->data);//先释放数据域 free(array);//再释放节点域 } int* arrayPushBack(array_t* array, int data) { /*检查健壮性*/ if(array == NULL) return NULL; if(array->idx == array->capa){ /*满了，两倍扩容*/ array->capa *= 2; array->data = (int*) realloc(array->data, sizeof(int) * array->capa); memset(array->data + array->idx, 0, sizeof(int) * array->idx); } array->data[array->idx++] = data; return &array->data[array->idx - 1]; } void arrayPopBack(array_t* array) { if(array == NULL) return; if(--(array->idx) < 0) array->idx = 0; array->data[array->idx] = 0;//覆盖删除的数据 } int* arrayIndex(array_t* array, int idx) { if(array == NULL) return NULL; return &(array->data[idx]); } static void quickSortPrivate(int* arr, int left, int right, int (*compare)(int, int)) { if(left >= right) return; int l = left, r = right, key = arr[left]; while(l < r){ if(compare) while(l < r && compare(arr[r], key) >= 0) r--; else while(l < r && arr[r] >= key) r--; arr[l] = arr[r]; if(compare) while(l < r && compare(arr[l], key) <= 0) l++; else while(l < r && arr[l] <= key) l++; arr[r] = arr[l]; } arr[l] = key; quickSortPrivate(arr, left, l-1, compare); quickSortPrivate(arr, r+1, right, compare); } void arraySort(array_t* array, int(*compare)(int, int)) { if(array == NULL) return; quickSortPrivate(array->data, 0, array->idx - 1, compare); }