考研C语言复习02(小甲鱼版本)

递归

//递归必须要有结束条件,否则程序将崩溃 void recursion(void); void recursion(void){ static int cpunt = 10; printf("HI\n"); if (--count){ recursion(); }} int main(void){ recursion(); return 0; }

//递归求阶乘 long fact(int num); long fact(int num){ long result; if (num > 0){ result = num * fact(num - 1); } else{ result = 1; } return result; } int main(void){ int num; printf("输入整数:"); scanf("%d",num); printf("%d的阶乘:%d\n", num, fact(num)); return 0; }

实现递归要满足两个基本条件:
①调用函数本身 ②设置了正确的结束条件
汉诺塔
问题描述:
x、y、z三根针,64个圆盘在x针上,需将64个圆盘都移动至z针上,且每次只能移动一个圆盘,移动过程中大的圆盘一定要在小圆盘的下面
解析:
对于游戏的玩法,我们可以简单分解为三个步骤:
①将前63个盘子从X移动到Y上
②将最底下的第64个盘子从X移动到Z上
③将Y上的63个盘子移动到Z上
再拆成两个问题:
(1)问题一:将X上的63个盘子借助Z移动到Y上:
——①将前62个盘子从X移动到Z上
——②将最底下的第63个盘子移动到Y上
——③将Z上的62个盘子移动到Y上
(2)问题二:将Y上的63个盘子借助X移动到Z上:
——①将前62个盘子从Y移动到X上
——②将最底下的第63个盘子移动到Z上
——③将X上的62个盘子移动到Y上
void hanoi(int n, char x, char y, char z); //x, y, z这三个,按顺序可以简单理解为x借助y移动到z void hanoi(int n, char x, char y, char z){ if (n==1)//当只有一个圆盘时 { printf("%c --> %c\n", x, z); } else{ //把除了最下面那一层的其他所有圆盘(n-1)层借助z移动到y hanoi(n-1, x, z, y); //手动移动最底下的大圆盘到z printf("%c --> %c\n", x, z); //剩下的圆盘从y借助x移动到z hanoi(n-1, y, x, z); } } int main(void){ int n; printf("汉诺塔层数:"); scanf("%d", &n); hanoi(n, 'X', 'Y', 'Z'); return 0; }

分治法
快速排序
快速排序算法的基本思想是:通过一趟排序将待排序数据分割成独立的两部分,其中一部分的所有元素均比另一部分的元素小,然后分别对这两部分继续进行排序,重复上述步骤直到排序完成。
void quick_sort(int array[], int left, int right){ int i = left, j = right; int temp; int pivot; pivot = array[(left + right) / 2]; while (i <= j){ //从左到右找到大于等于基准点的元素 while (array[i] < pivot){ i++; } //从右到左找到小于等于基准点的元素 while (array[j] > pivot){ j--; } //如果i <= j,则互换 if (i <= j){ temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } } if (left < j){ quick_sort(array, left, j); } if (i < right){ quick_sort(array, i, right); } }int main(void){ int array[] = {73, 108, 111, 118, 101, 70, 115, 104, 67, 46, 99, 111, 109}; int i, length; length = sizeof(array) / sizeof(array[0]); quick_sort(array, 0, length-1); printf("排序后:") for (i = 0; i < length; i++){ printf("%d", array[i]); } putchar('\n'); return 0; }

更灵活的内存管理方式
malloc:申请动态内存空间
free:释放动态内存空间
calloc:申请并初始化一系列内存空间
realloc:重新分配内存空间
malloc
函数原型:void *malloc(size_t size);
malloc函数向系统申请分配size个字节的内存空间,并返回一个指向这块空间的指针
如果函数调用成功,返回一个指向申请的内存空间的指针,由于返回类型是void 指针 (void *),所以它可以被转换成任何类型的数据;如果函数调用失败,返回值是NULL。另外,如果size参数设置为0,返回值也可能是NULL,但这并不意味着函数调用失败。
#include int main(){ int *ptr; ptr = (int *)malloc(sizeof (int)); if (ptr == NULL){ printf("分配内存失败\n"); exit(1); }printf("输入一个整数"); scanf("%d", ptr); printf("输入的整数是:%d\n", *ptr); return 0; }

malloc还可以申请一块任意尺寸的内存空间
#include int main(void){ int *ptr = NULL; int num, i; printf("请输入带录入整数的个数:"); scanf("%d", &num); ptr = (int *)malloc(num * sizeof(int)); for (i = 0; i < num; i++){ printf("请录入第%d个整数:", i+1); scanf("%d", &ptr[i]); }printf("你录入的整数是:"); for (i = 0; i < num; i++){ printf("%d", ptr[i]); } putchar('\n'); free(ptr); return 0; }

free
函数原型:void free(void *ptr);
free函数释放ptr参数指向的内存空间。该内容空间必须是由malloc、calloc或realloc函数申请的。否则,该函数将导致未定义行为。如果ptr参数是NULL,则不执行任何操作。注意:该函数并不会修改ptr参数的值,所以调用后它仍然指向原来的地方(变为非法空间)。
#include int main(){ int *ptr; ptr = (int *)malloc(sizeof (int)); if (ptr == NULL){ printf("分配内存失败\n"); exit(1); }printf("输入一个整数"); scanf("%d", ptr); printf("输入的整数是:%d\n", *ptr); free(ptr); printf("输入的整数是:%d\n", *ptr); return 0; }/*输入520 输入的整数是:520 输入的整数是:0 */

内存泄漏
导致内存泄漏主要有以下两种情况:
①隐式内存泄漏(即用完内存块没有及时使用free函数释放)
②丢失内存块地址
初始化内存空间
mem开头的函数被编入字符串标准库,函数的声明包含在string.h这个头文件中:
memset——使用一个常量字节填充内存空间
memcpy——拷贝内存空间
memmove——拷贝内存空间
memcmp——比较内存空间
memchr——在内存空间中搜索一个字符
#include #include #deifne N 10 int main(void){ int *ptr = NULL; int i; ptr = (int *)malloc(N * sizeof(int)); if (ptr == NULL){ exit(1); }memset(ptr, 0, N * sizeof(int)); for (i = 0; i < N; i++){ printf("%d", ptr[i]); } putchar('\n'); free(ptr); return 0; } //输出:0000000000

calloc
(1)函数原型:void *calloc(size_t nmemb, size_t size);
(2)calloc函数在内存中动态地申请nmemb个长度为size的连续内存空间(即申请的总空间尺寸为nmemb * size),这些内存空间全部被初始化为0.
(3)calloc函数与malloc函数的一个重要区别是:
—calloc函数在申请完内存后,自动初始化该内存空间为0.
(4)所以下面两种写法是等价的:
//calloc() 分配内存空间并初始化 int *ptr = (int *)calloc(8, sizeof(int));

//malloc() 分配内存空间并用memset()初始化 int *ptr = (int *)malloc(8 * sizeof(int)); memset(ptr, 0, 8 * sizeof(int));

realloc
函数原型:void *realloc(void *ptr, size_t size):
以下几点是需要注意的:
(1)realloc函数修改ptr指向的内存空间大小为size字节
(2)如果新分配的内存空间比原来的大,则旧内存块的数据不会发生改变;如果新的内存空间大小小于旧的内存空间,可能会导致数据丢失,慎用
(3)该函数将移动内存空间的数据并返回新的指针
(4)如果ptr参数为NULL,那么调用该函数就相当于调用malloc(size)
(5)如果size参数为0,并且ptr参数不为NULL,那么调用该函数就相当于调用free(ptr)
(6)除非ptr参数为NULL,否则ptr的值必须由先前调用malloc、calloc或realloc函数返回
#include #include int main(void){ int i, num; int count = 0; int *ptr = NULL; //注意,这里必须初始化为NULLdo{ printf("请输入一个整数(输入-1结束):"); scanf("%d", &num); count++; ptr = (int *)realloc(ptr, count * sizeof(int)); if (ptr == NULL){ exit(1); }ptr[count-1] = num; }while(num != -1); printf("输入的整数分别是:"); for (i = 0; i < count; i++){ printf("%d", ptr[i]); } putchar("\n"); free(ptr); return 0; }

C语言地内存布局规律
#include #include int global_uninit_var; int global_init_var1 = 520; int global_init_var2 = 880; void func(void); void func(void){ ; }int main(void){ int local_var1; int local_var2; static int static_uninit_var; static int static_init_var = 456; char *str1 = "I love FishC.com"; char *str2 = "You are right!"; int *malloc_var = (int *)malloc(sizeof(int)); printf("addr of func -> %p\n", func); printf("addr of str1 -> %p\n", str1); printf("addr of str2 -> %p\n", str2); printf("addr of global_init_var1 -> %p\n", global_init_var1); printf("addr of global_init_var2 -> %p\n", global_init_var2); printf("addr of static_init_var -> %p\n", static_init_var); printf("addr of static_uninit_var -> %p\n", static_uninit_var); printf("addr of global_uninit_var -> %p\n", global_uninit_var); printf("addr of local_var1 -> %p\n", local_var1); printf("addr of local_var2 -> %p\n", local_var2); return 0; }

代码段
代码段(Text segment)通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定,并且内存区域通常属于只读。在代码段中,也有可能包含一些只读的常数变量,例如字符串常量等
数据段
数据段(Initialized data segment)通常用来存放已经初始化的全局变量和局部静态变量
BSS段
BSS段(Bss segment/Uninitialized data segment)通常是指用来存放程序中未初始化的全局变量的一块内存区域。BSS是英文Block Started by Symbol的简称,这个区段中的数据在程序运行前将被自动初始化为数字0.

堆是用于存放进程运行中被动态分配的内存段,它的大小并不固定,可动态扩展或缩小。当进程调用malloc等函数分配内存时,新分配的内存就被动态添加到堆上;当利用free等函数释放内存时,被释放的内存从堆中被剔除

栈是函数执行的内存区域,通常和堆共享同一片区域。
堆和栈的区别
(1)申请方式:
——堆由程序员手动申请
——栈由系统自动分配
(2)释放方式:
——堆由程序员手动释放
——栈由系统自动释放
(3)生存周期:
——堆的生存周期由动态申请到程序员主动释放为止,不同函数之间均可自由访问
——栈的生存周期由函数调用开始到函数返回时结束,函数之间的局部变量不能相互访问
#include #include int *func(void){ int *ptr = NULL; ptr = (int *)malloc(sizeof(int)); if (ptr == NULL){ exit(1); }*ptr = 520; return ptr; }int main(void){ int *ptr = NULL; ptr = func(); printf("%d\n", *ptr); free(ptr); return 0; } /*输出 520*/

(4)发展方向
——堆和其他区段一样,都是从低地址向高地址发展
——栈则相反,是由高地址向低地址发展
#include #include int main(void){ int *ptr1 = NULL; int *ptr2 = NULL; ptr1 = (int *)malloc(sizeof(int)); ptr2 = (int *)malloc(sizeof(int)); printf("stack: %p -> %p\n", &ptr1, &ptr2); printf("heap: %p -> %p\n", ptr1, ptr2); ptr1 = (int *)realloc(ptr1, 2 * sizeof(int)); printf("heap: %p -> %p\n", ptr1, ptr2); ptr1 = (int *)realloc(ptr1, 20 * sizeof(int)); printf("heap: %p -> %p\n", ptr1, ptr2); return 0; } /*输出 stack: 0xbfdea78c -> 0xbfdea788 heap: 0x9e5c008 -> 0x9e5c018 heap: 0x9e5c008 -> 0x9e5c018 heap: 0x9e5c028 -> 0x9e5c018

高级宏定义
预处理:文件包含、宏定义、条件编译
不带参数的宏定义
例:#define PI 3.14
(1)为了和普通的变量进行区分,宏的名字通常我们约定是全部由大写字母组成
(2)宏定义只是简单地进行替换,并且由于预处理是在编译之前运行,而编译工作的任务之一就是语法检查,所以编译器不会对宏定义进行语法检查。
(3)宏定义不是说明或语句,在末尾不必加分号
(4)宏定义的作用域是从定义的位置开始到整个程序结束
(5)可以用#undef来终止宏定义的作用域
(6)宏定义允许嵌套
#define PI 3.14 #define R 6371 #define V PI * R * R * R * 4 / 3int main(void){ int r; float s; printf("请输入圆的半径:"); scanf("%d", &r); s = PI * r * r; printf("圆的面积是:%.2f\n", s); printf("%.2f\n", V); /* #undef PI s = PI * r * r; printf("圆的面积是:%.2f\n", s); */ return 0; }

带参数的宏定义
#define MAX(X, Y) (((x) > (y)) ? (x) : (y))
#define MAX(X, Y) (((x) > (y)) ? (x) : (y)) int main(void){ int x, y; printf("输入两个整数:"); scanf("%d%d", &x, &y); printf("%d 是最大的那个数\n", MAX(x,y)); return 0; }

内联函数
引入内联函数来解决程序中函数调用的效率问题,优化编译过程,函数定义前加inline
#include inline int square(int x); inline int square(int x){ return x * x; }int main(void){ int i = 1; while (i <= 100){ printf("%d 的平方是 %d\n", i-1, square(i++)); }return 0; }

内联函数虽然节省了函数调用的时间消耗,但由于每一个函数出现的地方都要进行替换,因此增加了代码编译的时间。另外,并不是所有的函数都能够变成内联函数
现在的编译器就算不写inline,它也会自动将一些函数优化成内联函数
###
###是两个预处理运算符
在带参数的宏定义中,#运算符后面应该跟一个参数,预处理器会把这个参数转换为一个字符串
#define STR(s) # sint main(void){ printf("%s\n", STR(FISHC)); printf(STR(Hello%s num = %d), STR(FishC), 520); return 0; } /*输出 FISHC Hello FishC num = 520*/

##运算符被称为记号连接运算符,比如我们可以使用##运算符连接两个参数
#define together(x, y) x ## yint main(void){ printf("%d\n", together(2, 50)); return 0; } /*输出 250*/

可变参数
带参数的宏定义也是可以使用可变参数的:
#define SHOWLIST(...) printf(#__VA_ARGS__)
其中...表示使用可变参数,__VA_ARGS__在预处理中被实际的参数集所替换
#define SHOWLIST(...) printf(#__VA_ARGS__) #define PRINT(format,...) printf(# format, ##__VA_ARGS__)int main(void){ SHOWLIST(FishC, 520, 3.14\n); PRINT(num = %d\n, 520); PRINT(Hello FishC!\n); return 0; /*输出 FishC, 520, 3.14 num = 520 Hello FishC!*/

结构体
结构体声明:
struct 结构体名称{ 结构体成员1; 结构体成员2; 结构体成员3; ... };

例如:
struct Book{ char title[128]; char author[40]; float price; unsigned int date; char publisher[40]; };

定义结构体类型变量:struct 结构体名称 结构体变量名
struct Book{ char title[128]; char author[40]; float price; unsigned int date; char publisher[40]; }; /*下面这种方法也可,那么在后面的代码中就无需再定义book结构体 struct Book{ char title[128]; char author[40]; float price; unsigned int date; char publisher[40]; } book; */ int main(void){ struct Book book; return 0; }

访问结构体变量
要访问结构体成员,我们需要引入一个新的运算符——点号**.**运算符。比如book.title就是引用book结构体的title成员,它是一个字符数组;而book.price则是引用book结构体的price成员,它是一个浮点型的定量
struct Book{ char title[128]; char author[40]; float price; unsigned int date; char publisher[40]; } book; int main(void){ printf("书名"); scanf("%s", book.title); //字符串数组,可不加& printf("作者"); scanf("%s", book.author); printf("售价"); scanf("%f", &book.price); printf("出版日期"); scanf("%d", &book.date); printf("出版社"); scanf("%s", book.publisher); printf("======数据录入完毕======"); printf("书名:%s\n", book.title); printf("作者:%s\n", book.author); printf("售价:%.2f\n", book.price); printf("出版日期:%d\n", book.date); printf("出版社:%s\n", book.publisher); return 0; }

初始化结构体变量
(1)初始化一个变量和数组:
int a = 520; int array[5] = {1, 2, 3, 4, 5};

(2)初始化一个结构体变量:
struct Book book = { "《带你学C带你飞》", "小甲鱼", 48.8; 20171111, "清华大学出版社" };

初始化结构体的指定成员值
其语法和数组指定初始化元素类似,不过结构体指定初始化成员使用点号**.**运算符和成员名
比如我们可以让程序只初始化Book的price成员:
struct Book book = {.price = 48.8};
还可以不按结构体声明的成员顺序进行初始化:
struct Book book = { .publisher = "清华大学出版社", .price = 48.8, .date = 20171111 };

int main(void){ struct A{ char a; int b; char c; }a = {'x', 520, '0'}; printf("size of a = %d\n", sizeof(a)); return 0; } //理论上输出的应该为6(两个char两个字节,加上一个int4个字节),但是编译器会进行内存对齐,每一个元素填充为4个字节,如果改变顺序 /*struct A{ char a; char c; int b; }a = {'x', '0', '520'}; 则输出8个字节,通过改变顺序改变内存分配*/

结构体嵌套
struct Date{ int year; int month; int day; }; struct Book{ char title[128]; char author[40]; float price; struct Date date; char publisher[40]; } book = { "《带你学C带你飞》", "小甲鱼", 48.8, {2017, 11, 11}, "清华大学出版社" }; int main(void){printf("书名:%s\n", book.title); printf("作者:%s\n", book.author); printf("售价:%.2f\n", book.price); printf("出版日期:%d-%d-%d\n", book.date.year, book.date.month, book.date.day); printf("出版社:%s\n", book.publisher); return 0; } /*输出 书名:《带你学C带你飞》 作者:小甲鱼 售价:48.80 出版日期:2017-11-11 出版社:清华大学出版社*/

结构体数组
第一种方法是在声明结构体的时候进行定义:
struct 结构体名称{ 结构体成员; } 数组名[长度];

第二种方法是先声明一个结构体类型(比如上面Book),再用此类型定义一个结构体数组:
struct 结构体名称{ 结构体成员; }; struct 结构体名称 数组名[长度];

初始化结构体数组
struct Book book[3] = { {"《入门学习1》", "小甲鱼", 49.5, {2016, 11, 11}, "清华大学出版社"}, {"《入门学习1》", "小甲鱼", 49.5, {2016, 11, 11}, "清华大学出版社"}, {"《入门学习1》", "小甲鱼", 49.5, {2016, 11, 11}, "清华大学出版社"} };

结构体指针
通过结构体指针访问结构体成员有两种方法:
①用于对象(成员名)(*结构体指针).成员名
②用于指针(成员名)结构体指针->成员名
例:
struct Date{ int year; int month; int day; }; struct Book{ char title[128]; char author[40]; float price; struct Date date; char publisher[40]; } book = { "《带你学C带你飞》", "小甲鱼", 48.8, {2017, 11, 11}, "清华大学出版社" }; int main(void){ struct Book *pt; pt = &book; printf("书名:%s\n", (*pt).title); printf("作者:%s\n", (*pt).author); printf("售价:%.2f\n", (*pt).price); printf("出版日期:%d-%d-%d\n", (*pt).date.year, (*pt).date.month, (*pt).date.day); printf("出版社:%s\n", (*pt).publisher); printf("书名:%s\n", pt->title); printf("作者:%s\n", pt->author); printf("售价:%.2f\n", pt->price); printf("出版日期:%d-%d-%d\n", pt->date.year, pt->date.month, pt->date.day); printf("出版社:%s\n", pt->publisher); return 0; } /*输出 书名:《带你学C带你飞》 作者:小甲鱼 售价:48.80 出版日期:2017-11-11 出版社:清华大学出版社 书名:《带你学C带你飞》 作者:小甲鱼 售价:48.80 出版日期:2017-11-11 出版社:清华大学出版社 */

传递结构体变量
int main(void){ struct Test{ int x; int y; }t1, t2; t1.x = 3; t1.y = 4; t2 = t1; printf("t2.x = %d, t2.y = %d", t2.x, t2.y); return 0; } /*输出 t2.x = 3, t2.y = 4*/

struct Date{ int year; int month; int day; }; struct Book{ char title[120]; char author[40]; float price; struct Date date; char publisher[40]; }; struct Book getInput(struct Book book); struct Book getInput(struct Book book){ printf("请输入书名:"); scanf("%s", book.title); printf("请输入作者:"); scanf("%s", book.author); printf("请输入售价:"); scanf("%f", &book.price); printf("请输入出版日期:"); scanf("%d-%d-%d", &book.date.year, &book.date.month, &book.date.day); printf("请输入出版社:"); scanf("%s", book.publisher); return book; } void printBook(struct Book book); void printBook(struct Book book){ printf("书名:%s\n", book.title); printf("作者:%s\n", book.author); printf("售价:%.2f\n", book.price); printf("出版日期:%d-%d-%d\n", book.date.year, book.date.month, book.date.day); printf("出版社:%s\n", book.publisher); } int mian(void){ struct Book b1, b2; printf("请录入第一本书的信息...\n"); b1 = getInput(b1); putchar('\n'); printf("请录入第二本书的信息...\n"); b2 = getInput(b2); printf("打印第一本书的信息..."); printBook(b1); putchar('\n'); printf("打印第二本书的信息..."); printBook(b2); return 0; }

传递指向结构体变量的指针
struct Date{ int year; int month; int day; }; struct Book{ char title[120]; chat author[40]; float price; struct Date date; char publisher[40]; }; void getInput(struct Book *book); void printBook(struct Book *book); void getInput(struct Book *book){ printf("请输入书名:"); scanf("%s", book->title); printf("请输入作者:"); scanf("%s", book->author); printf("请输入售价:"); scanf("%f", &book->price); printf("请输入出版日期:"); scanf("%d-%d-%d", &book->date.year, &book->date.month, &book->date.day); printf("请输入出版社:"); scanf("%s", book->publisher); return book; }void printBook(struct Book *book){ printf("书名:%s\n", book->title); printf("作者:%s\n", book->author); printf("售价:%.2f\n", book->price); printf("出版日期:%d-%d-%d\n", book->date.year, book->date.month, book->date.day); printf("出版社:%s\n", book->publisher); } int mian(void){ struct Book b1, b2; printf("请录入第一本书的信息...\n"); b1 = getInput(&b1); putchar('\n'); printf("请录入第二本书的信息...\n"); b2 = getInput(&b2); printf("打印第一本书的信息..."); printBook(&b1); putchar('\n'); printf("打印第二本书的信息..."); printBook(&b2); return 0; }

动态申请结构体
使用malloc函数为结构体分配存储空间
#include//为了exit(1)struct Date{ int year; int month; int day; }; struct Book{ char title[120]; chat author[40]; float price; struct Date date; char publisher[40]; }; struct Book getInput(struct Book book); struct Book getInput(struct Book book){ printf("请输入书名:"); scanf("%s", book.title); printf("请输入作者:"); scanf("%s", book.author); printf("请输入售价:"); scanf("%f", &book.price); printf("请输入出版日期:"); scanf("%d-%d-%d", &book.date.year, &book.date.month, &book.date.day); printf("请输入出版社:"); scanf("%s", book.publisher); return book; } void printBook(struct Book book); void printBook(struct Book book){ printf("书名:%s\n", book.title); printf("作者:%s\n", book.author); printf("售价:%.2f\n", book.price); printf("出版日期:%d-%d-%d\n", book.date.year, book.date.month, book.date.day); printf("出版社:%s\n", book.publisher); }int mian(void){ struct Book *b1, *b2; b1 = malloc((struct Book *)sizeof(struct Book)); b1 = malloc((struct Book *)sizeof(struct Book)); if (b1 == NULL || b2 == NULL){ printf("内存空间分配失败!\n"); exit(1); }printf("请录入第一本书的信息...\n"); getInput(b1); putchar('\n'); printf("请录入第二本书的信息...\n"); getInput(b2); printf("打印第一本书的信息..."); printBook(b1); putchar('\n'); printf("打印第二本书的信息..."); printBook(b2); free(b1); free(b2); return 0; }

【考研C语言复习02(小甲鱼版本)】作业:尝试构建一个图书馆

    推荐阅读