C语言程序设计

一、基础知识

在命令行中进行编译运行

~/project ls -l #执行命令ls，用于列出当前所在计算机存储位置中的文件和目录，并为其配置参数-l
-rw-r--r-- 1 user user 112 Aug 25 20:48 main.c 
~/project gcc -o program main.c 
#gcc为编译器名称，用该命令告诉gcc，将main.c的代码文件编译成名为program的可执行文件
~/project ls -l
-rw-r--r-- 1 user user  112 Aug 25 20:48 main.c                                                   
-rwxrwxr-x 1 user user 8512 Aug 25 21:35 program  #目录中新增了program的可执行文件
./program #执行程序

变量相关

变量名：由大、小写字母，下划线，数字组成；数字不能开头；不能是有特定含义的保留字。

作用域：

变量声明语句之后，包裹了它声明语句的最内一层{}中，且一个变量在其作用域内仅能声明一次，但能够赋值多次，只要是在其作用域内的赋值，均起作用。

这些在结构化语句的内部的变量的作用域为结构化语句内部。注意，对于switch中在case内部定义的变量的作用域就是在当前case。我们可以简单理解为在大括号内部定义的变量，其作用域就是在当前大括号中，在当前大括号外部无效。对于循环嵌套和分支嵌套程序来说都是一样的。关于这一点不再赘述。

注意，当一个嵌套结构中出现两个不同作用域的变量时，变量的名称可以相同，在使用时以其小作用域为准。

与局部变量相对的就是全局变量，我们把定义在函数外部的变量称为全局变量，这些变量的作用域为整个程序，也就是所有的函数和结构化语句都能使用它们。

甚至多个源文件一起编译时，全局变量在其他文件中也能够生效需要用extern关键字在函数外部声明一个文件外部变量。

递归问题

在头递归的实现中，我们在进行下一层的调用前，没有进行计算，只有在下一层的返回之后，我们才完成了这一层的运算。

在尾递归的实现中，我们在进行下一层的调用前，会先进行计算，而在最终一般条件满足时，会将计算的结果逐层直接返回。

声明与实现分离

如果采用直接定义的方式来创造函数，则需要时刻关注它们之间依赖关系，并正确排序，不现实。需要进行声明与实现的分离，从而简化这一过程。

只需要在需要用到该函数前进行声明即可，定义可放在执行程序的后面位置，函数声明时可以不写函数参数名，只写参数类型。

变量地址做函数参数

swap函数中，由于该函数定义的形式参数a,b作用域有限，因此swap函数内的交换并不会影响main函数中x，y大的值。此时，需修改成传入参数x、y的地址，直接对其地址进行操作。

void swap(int *a, int *b);
int main(){
    int x,y;
    swap(&x, &y);
}

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

函数地址做函数参数

C语言中函数与变量类似，也有其自己的内存地址，但函数不能像变量一样可以进行值传递，在想要将函数作为另一个函数的参数进行传递时，需要传递它的地址。

1
2
3

int g(float (*f)(int), int a){
    return f(a);
}

上面这种情况，函数g需要有一个形式参数来接收函数地址，其第一个参数需要一个返回值类型为float且有一个int类型参数的函数；第二个参数就是普通的int类型值

其实直接写f(a)和float (*f)(int)来调用其地址本质上是一样的。因此声明时需要如上所示去取函数的地址，而调用时，直接函数名与变量一起传入也是可以的。g(f(x), a)。

有关代码风格的空格

哪些使用空格的地方：

1、+、-、>、==、|、&&等双目运算符前后；

2、if、switch、for、while等关键字，函数名和之后的左小括号之间；

3、不在行尾的逗号、分号之后，例如for循环中的分号之后；

4、必须加空格的情况：如return后面不加空格就会报语法错误的情况。

数组

相当于定义了一系列地址相邻的元素，与取变量地址的方式一致，可以通过&radius[1]的方式取得数组radius在索引位置1元素的地址。在C语言中，对一个元素的地址加上位移值n得到的就是这个元素往后数n后所在元素的地址。

且一般来说，在地址上进行运算的方式访问数组的效率比利用索引更快，例如：你只希望访问数组中每一个元素一次时，可用while循环内使用地址上运算的方式，使用数组中每一个元素的值，而无需关心数组的索引是谁。

1
2
3

int *p_radius;
p_radius = &radius[0];
//这里*(p_radius + 1)或者（&radius[0] + 1）都会得到radius[1]元素的地址。

字符串的本质是数组

字符串实际上是一个元素为字符的数组，例如“Hello”由五个字母字符与一个空字符\0组成；任何字符串的内部表示都会以空字符‘\0’作为结尾，故可以以此方式找到字符串结尾。

同样，在C中提供字符数组初始化的简化方式：

1	char string[] = "Hello";

字符串更严谨应该被称为字符串字面量，其表现为一对双引号包裹的0个或者多个字符；字面量并非仅包含字符串常量

int a;
a = 1234;
//语句中的1234其实就是一个整数型字面量，其实是将一个整数型字面量的值放入了变量中作为值。在字面量后往往需要增加一个后缀标记类型。L：长类型；U：无符号类型；F：浮点类型。
//除了十进制，也可用其他进制表示字面量。

除了用字符数组存储字符串，也可声明一个用于存储字符地址的变量操作字符串

#include <stdio.h>
//string的地址是内存栈区的地址；string2则是直接关联到"Hello"字符串字面量在内存中字面量池的地址。
int main() {
    char string[] = "Hello";
    printf("%s\n", string);
    char *string2 = "Hello";
    printf("%s\n", string2);
    printf("%p\n", &string); //0x7fff09dd0480
    printf("%p\n", string2);//0x4allc4
    printf("%p\n", &"Hello");//0x4allc4
    return 0;
}

按位运算

结构体

使用struct定义完结构体后，每当我们需要使用结构体时都需要写一次struct关键字，而其实C语言中提供了一种为某一已知类型添加别名的方式：typedef；typedef 原类型类型别名

typedef struct point Point;
//完成设置别名后再进行变量声明时，可以不写struct point point1;
Point point1;
//也可以在定义结构体时同时在前面加上typedef，这样可以把两步合二为一
typedef struct point{
    float x;
    float y;
} Point;

函数的返回值也可以通过结构体的方式来进行返回，同样传入参数也可以以结构体的形式传入，但若以结构体变量值的形式进行传递参数，这种传值的效率相对来说是低的（特别是结构体内成员特别多时），当vector_add函数不会改变传入参数的值时，没有必要采用会使用额外内存并需要赋值传入值到额外内存的“传值”作参数的方式，可将传入的参数改成指针的形式。

同时这样修改后调用函数参数时，也要加上取地址符号&。

#include <stdio.h>
#include <math.h>

typedef struct point {
    float x;
    float y;
} Vector;

Vector vector_add(Vector *v1, Vector *v2) {
    Vector v_result;
    v_result.x = v1->x + v2->x;
    v_result.y = v1->y + v2->y;
    return v_result;
}

int main() {
    Vector v1 = { 2.4f, 2.5f };
    Vector v2 = { 3.7f, 4.4f };
    Vector v_result;
    v_result = vector_add(&v1, &v2);
    printf("(%f, %f)\n", v_result.x, v_result.y);
    return 0;
}

以后再用到(*结构体指针名).结构体成员元素名形式的代码时，都可以将其写为：结构体指针名->结构体成员元素名。

用结构体构建一个简单链表的方法如下图：

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int number;
    struct node*next;
}Node;

Node *create_node(int new_number){
    Node *temp_node;
    temp_node = (Node *) malloc(sizeof(Node));
    temp_node->number = new_number;
    temp_node->next = NULL;
    return temp_node;
}

int main() {
    Node *head;
    head = create_node(1);
    head->next = create_node(2);
    head->next->next = create_node(3);
    printf("%d\n", head->next->number);
    return 0;
}

约瑟夫环问题

N个同学围成圆圈，每个人被顺序地编了一个序号，从编号为K的人开始报1，之后按顺序增长，直至报数字M的人出列，出列人的下一个人从1继续开始报数，重复该过程直至所有人均出列。

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int data;
    struct node *next;
} Node;

Node *circle_create(int n);
void count_off(Node *head, int n, int k, int m);

int main() {
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    Node *head = circle_create(n);
    count_off(head, n, k, m);
    return 0;
}

Node *circle_create(int n) {
    Node *temp, *new_node, *head;
    int i;

    // 创建第一个链表节点并加数据
    temp = (Node *) malloc(sizeof(Node));
    head = temp;
    head->data = 1;

    // 创建第 2 到第 n 个链表节点并加数据
    for(i = 2; i <= n; i++) {
        new_node = (Node *) malloc(sizeof(Node));
        new_node->data = i;
        temp->next = new_node;
        temp = new_node;
    }

    // 最后一个节点指向头部构成循环链表
    temp->next = head;

    return head;
}

void count_off(Node *head, int n, int k, int m) {
    int i, j;
    Node *newNode, *beginNode;
    for (i = 0; i < n - 1; i++){
        beginNode = head->next;
    }
    newNode = head->next;
    for (i = 0; i < k - 1; i++){
        beginNode = head;
        head = newNode;
        newNode = head->next;
    }
    for (i = 0; i < n; i++){
        for (j = 1; j < m ; j++){
            beginNode = head;
            head = newNode;
            newNode = head->next;
        }
if (m == 2 && i == n - 1) head = newNode;
        printf("%d", head->data);
        if (i != n - 1)
            printf(" "); 
        head = newNode;
        newNode = head->next;
        beginNode->next = head;
      }
    return;
}

共用体

结构体的特性解决了一系列不同类型变量可以怎么放在一起组织的问题，而共用体则使多种不会同时出现的变量共用一块内存成为了可能，关键字union，共用体所占用的内存空间是被公用的，可通过两种或多种不同类型描述成员进行访问，且无论通过哪种方式进行访问，访问的是同一块内存空间。共用体类型变量的成员在内存中地址相同。

枚举enumeration

枚举由一系列的整数成员，表示这一数据类型的变量可以取的所有可能值，但是这些值都不直接以字面量形式存在，每个值都被单独给予一个名字，同样也可以给多个枚举成员进行显性的编号。

声明一个该枚举类型的变量时，只能取定义过的枚举类型中的成员名作为值，枚举类型的成员不能有结构体和共用体变量。

二、简单算法

牛顿迭代法

多数方程不存在求根方式，因此用牛顿法寻找方程的近似跟，时间复杂度为log n。

步骤：1、确定迭代变量；2、建立迭代关系式；3、对迭代过程进行控制。

#include <stdio.h>
#include <math.h>
#define EPSILON 1e-6

double f(double x) {
    return 2 * pow(x, 3) - 4 * pow(x, 2) + 3 * x - 6;
}

double f_prime(double x) {
    return 6 * pow(x, 2) - 8 * x + 3;
}

double h(double x){
    return pow(x,3) - 4 * pow(x,2) + 3 * x - 6;
}

double h_prime(double x){
    return 3 * pow(x,2) - 8 * x + 3;
}

double newton(double (*fp)(double), double(*fp_prime)(double)) {
    double x = 1.5;
    while (fabs(fp(x)) > EPSILON){
        x = x - fp(x) / fp_prime(x);
    }
    return x;
}

int main() {
    printf("%g\n", newton(f, f_prime));
    printf("%g\n", newton(h, h_prime));
    return 0;
}

二分法

二分法同样是一个求方程近似跟的方法，在使用二分法近似求解时，先设定一个迭代区间，且区间两边自变量x对应的F(X)是异号的，之后计算两端中点位置x对应的f(x)，再更新迭代区间，并确保迭代区间两端x对应的函数值还是异号，重复过程直至中点x对应的f(x)小于某个值。

#include <stdio.h>
#include <math.h>
#define EPSILON 1e-7

double bisection(int p, int q, double (*func)(int, int, double));
double f(int p, int q, double x);
int main() {
    int p;
    int q;
    scanf("%d%d", &p, &q);
    printf("%.4f\n", bisection(p, q, f));
    return 0;
}

double bisection(int p, int q, double (*func)(int, int, double)) {
    int forward, backward;
    if(func(p, q, 20) > 0){
        forward = 20;
        backward = -20;
    }
    else{
        forward = -20;
        backward = 20;
    }
    int x = 0;
    while(fabs(f(p, q, x)) > EPSILON){
        if(f(p, q, x) > 0){
            forward = x;
        }
        else backward = x;
        x = (backward + forward)/2;
    }       
}

double f(int p, int q, double x) {
    return p * x + q;
}

质数筛法

与之前的对每一个数依次判断是否为质数的方式不同，筛法的思想是“标注出所有非质数，输出所有没被标记的数字”，声明了一个mark数组，用于标记所有质数。

#include <stdio.h>
#include <math.h>
int main() {
    printf("2\n");
    int digit;
    int divisor;
    for (digit = 3; digit <= 15; digit += 2) {
        for (divisor = 3; divisor < sqrt(digit); divisor += 2) {
            if (digit % divisor == 0){
                break;
            }
        }
        if (divisor == digit){
            printf("%d\n", digit);
        }
    }
    return 0;
}

质数筛法的逻辑：对于n以内的筛选来说，如果n为合数，c为n的最小因数，1< C*C < n；故只要找到了c就可以确定n是合数，并将n进行标记，通过这样的一个个筛选，将容易得到的合数均筛选出去。

#include <stdio.h>

int main() {
    int n = 15;
    int mark[16] = {
        1, 1, 0, 0,
        0, 0, 0, 0,
        0, 0, 0, 0,
        0, 0, 0, 0
    };
    int c;
    int j;

    for (c = 2; c * c <= n; c++) {
        if(mark[c] != 1){
            for(j = 2; j <= n / c;j++){
                mark[c * j] = 1;
            }
        }
    }
    for (c = 2; c <= n; c++){
        if(mark[c] != 1){
            printf("%d\n", c);
        }
    }
    
    return 0;
}

折半查找

#include <stdio.h>
int BinSearch(int arr[], int len, int key)
{
    int low = 0;
    int high = len - 1;
    int mid;
    while(low <= high){
        mid = (low + high) / 2;
        if(key == arr[mid])
            return mid + 1;
        else if(key > arr[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0;
}

int main() {
    int n;
    int k;
    int numbers[1000001];
    int m;
    int i;
    int j;

    // 反复读入数字和查找数字的数量
    while (scanf("%d%d", &n, &k) != EOF) {
        
        // 读入给定的数字
        for (i = 0; i < n; i++) {
            scanf("%d", &numbers[i]);
        }

        for (j = 0; j < k; j++) {
            // 读入待查找的数字，
            scanf("%d", &m);
            printf("%d",BinSearch(numbers, n, m));
            // 请在下面完成查找读入数字的功能 
            if(j < k-1)
                printf(" ");
        }

    }
    return 0;
}

递归问题

有时候递归会使时间复杂度过高，是因为使用了多次的重复计算，可以用数组来存储之前计算的值，从而避免简单的运算重复进行。经典的爬楼梯问题代码如下：

#include <stdio.h>

int main() {
    int n, a, i;
    scanf("%d", &n);
    int arr[n];
    arr[0] = 0;arr[1] = 0;arr[2] = 1;arr[3] = 1;
    for(i = 4; i <= n; i++){
        arr[i] = arr[i-2] + arr[i-3];
    }
    printf("%d", arr[n]);
    
    return 0;
}

冒泡排序

基本思想：将数组中每个相邻元素进行两两比较，按照较小元素在前的原则决定是否进行交换，这样每一轮执行之后，最小元素就被换至了最后一位。完成第一轮后，我们从头进行第二轮的比较，直至倒数第二位（因为最后一位是已经被排序好的），依次进行直至所有元素被排列成预期的顺序为止。

//当有5个数待排序时，可写出如下的程序。
for (j = 0; j < 5; j++){
    for (i = 0; i < 4 - j; i++){
        swap(a[i], a[i+1]);
    } 
}

#include <stdio.h>

int main() {
    int n = 10;
    int m;
    int numbers[10];
    int i, j;

    // 读入给定的数字
    for (i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }
    for (i = 0; i < n; i++)
        for (j = 0; j < n - 1 - i; j++){
            if(numbers[j] < numbers[j+1]){
                m = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = m;
            }
        }
    
    for(i = 0; i < n; i++){
        printf("%d", numbers[i]);
        if(i != n-1){
            printf(" ");
        }
    }
    return 0;
}

选择排序

核心思想：根据从小到大的排序需求，它每一次从到排序的数据元素中选择出最小的元素，移动至序列的起始位置，然后在剩余的待排序元素中进行排序。

用两层循环来实现：1、寻找最小的元素需要一层循环；2、逐个被选出也需要一层循环。

螺旋输出矩阵

对任意的给定m行、n列的矩阵，按顺时针螺旋的顺序输出矩阵中所有的元素.

找规律，由外向内一层层进行for循环打印，最外层循环控制有多少层，每层分为（上方、右侧、下方、左侧）四个递增的循环，直至最后一层打印完；如果输出N为奇数，将会有N/2 + 1层

优化后的螺旋矩阵

当然它的规律很简单，直接的方法就是先申请一个矩阵，然后按螺旋方向填入相应的元素，填充完毕后再打印出来。它的时间按复杂为O(n2)，已经是最优的（为什么？）。空间复杂度也为O(n2）。似乎已经很好了。但是还不够好。

按照矩阵规律填充元素时，我们是随机访问矩阵元素的（如果可以按顺序访问，根本不用先存起来再打印）。随机访问内存，效率当然不高。所以即使时间复杂度已为最优，但那只是理论上的最优，在实践中表现并不一定就好。

假如能根据行列号直接计算出对应的矩阵元素就好了。当n给定后，这个矩阵就已经唯一确定了，那么每一个元素也是确定的。也就是说，每一个位置放什么元素仅仅取决于n。因此我们可以找到一个函数element(i, j)，将行号i和列号j映射成对应这个行列号的元素。当然这个函数肯定不是一个简单的函数，不是一眼就可以看出来的，但也并不是不可能。

现在我们就来考查一下这个矩阵有什么特点。注意观察一下螺旋矩阵的最外层，它的左上角的元素是最小的，然后沿顺时针方向递增，就如同一个环一样（比如n为4时，1, 2, …, 12就是最外面一层环）。再注意一下里面一层，也是一样，顺时针方向递增的一个环（比如n为4时，13, 14, 15, 16就是里面一层环）。以此类推，环里面还有一层环（n为4时有2层环，n为5时有3层环，最里面一层只有一个元素25），实际上是一个圆环套圆环结构。每一圆环最关键的元素就是左上角的那一个元素。只要知道了这个元素，再加上这个正方形环的边长就可以计算出剩下的元素。设左上角元素为a，边长为l（ell），也就是边上有几个元素，并假设左上角的行号和列号均为0，其它元素的行号和列号都以它作参考，计算方法如下所示：

1、若i == 0，element(i, j) = a + j;

2、否则若j == 0，element(i, j) = a + 4(l-4) - (i-1) - 1;

3、否则若i == l-1，element(i, j) = a + 4(l-4) - (l-2) - 1 - j;

4、否则element(i, j) = a + l - 1 + i;


#include<iostream>
using namespace std;
 
int a[10][10];
 
void Fun(int n)
{
    int m=1;
    int i,j;
    for(i =0;i<n/2;i++){
        for(j=0;j<n-i;j++){
            if(a[i][j] ==0)
                a[i][j] = m++;
        }
        for(j=i+1;j<n-i;j++){
            if(a[j][n-1-i] ==0)
                a[j][n-1-i] = m++;
        }
        for(j=n-i-1;j>i;j--){
            if(a[n-i-1][j] ==0)
                a[n-i-1][j] = m++;
        }
        for(j=n-i-1;j>i;j--){
            if(a[j][i] ==0)
                a[j][i] = m++;
        }
    }
    if(n%2==1)
        a[n/2][n/2]=m;
}
 
int main(void)
{
    int n,i;
    cout<<"请输入螺旋矩阵维数： "<< endl;
    cin>>n;
    cout<<"显示螺旋矩阵数值： "<< endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j]=0;
        }
    }
    Fun(n);
    for(i=0;i<n;i++){
        for( int j=0;j<n;j++){
            cout<<a[i][j]<< "\t";
        }
    cout<<endl;
    }
}

螺旋队列

问题描述：设1的坐标是（0，0），x方向向右为正，y方向向下为正，例如，7的坐标为（-1，-1），2的坐标为（1，0）。编程实现输入任意一点坐标（x，y），输出所对应的数字.


#include "stdafx.h"
#include <iostream>
#define max(a,b) ((a)<(b)?(b):(a))
#define abs(a) ((a)>0?(a):-(a))
 
using namespace std;
 
int foo(int x,int y)
{
    int t = max(abs(x),abs(y));
    int u = t+t;
    int v = u-1;
    v= v*v+u;
    if(x == -t)
        v+=u+t-y;
    else if(y==-t)
        v+=3*u+x-t;
    else if(y ==t)
        v+= t-x;
    else
        v+=y-t;
    return v;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int x ,y;
    int N;
    cout<<"请输入螺旋队列数字： "<<endl;
    cin>>N;
    cout<<"显示螺旋队列数值： "<<endl;
    for(y=-N;y<=N;y++)
    {
        for(x=-N;x<=N;x++)
            cout<<"\t"<<foo(x,y);
        cout<<endl;
    }
    while(scanf("%d%d",&x,&y)==2)
        //printf("%d\n",foo(x,y));
        cout<<"\t"<<foo(x,y);
    return 0;
}

双螺旋矩阵

#include <stdio.h>
int main() {
    int matrix[100][100];
    int m;
    int i;
    int j;
    int n;
    scanf("%d%d", &m, &n);
    
    for (i = 0; i < m; i++){
        for (j = 0; j < n; j++){
            scanf("%d", &matrix[i][j]);
        }
    }
    
    int rowBegin = 0;
    int rowEnd = m - 1;
    int colBegin = 0;
    int colEnd = n - 1;
    while (rowBegin <= rowEnd && colBegin <= colEnd){
        //先向右走
        for (int i = colBegin; i <= colEnd; i++){
            printf("%d", matrix[rowBegin][i]);
            if (rowBegin == rowEnd && i == colEnd);
            else printf(" ");
        }
        rowBegin++;
        //向下走
        for (int i = rowBegin; i <= rowEnd; i++){
            printf("%d", matrix[i][colEnd]);
            if (colBegin == colEnd && i == rowEnd);
            else printf(" ");
        }
        colEnd--;
        //向左走前先判定条件
        if (rowBegin <= rowEnd){
            for (int i = colEnd; i >= colBegin; i--){
                printf("%d", matrix[rowEnd][i]);
            if (rowBegin == rowEnd && i == colBegin);
            else printf(" ");
            }

            rowEnd--;
        }
        if (colBegin <= colEnd){
            for (int i = rowEnd; i >= rowBegin; i--){
                printf("%d", matrix[i][colBegin]);
            if (colBegin == colEnd && i == rowBegin);
            else printf(" ");
            }

            colBegin++;
        }
    }
    return 0;
}

三、深入探究语言逻辑

动态分配内存

1、栈区：C语言程序在编译时会被分配到内存上一篇有限的连续区域，这部分内存会被用于存储局部变量的值，这部分内存区域被称为栈区；

2、堆区：这部分内存是我们通过程序手动地向系统申请的，栈区内存带下编译时就已经被限制，如果使用超过限制的内存就会出现“溢出”的情况，而堆区的内存可以被一直申请使用，直至操作系统的有效内存无法再被申请位置；堆区被申请后，在使用的过程中若不释放就可能会出现内存泄漏；需要使用free(arr)；

3、全局区（静态区）：程序中的全局变量和静态变量都被存储在这块内存区域中；

如果需要使用堆上内存，需要将malloc.h，stdlib.h引入到程序中来。

1 2	int p; p = (int ) malloc(sizeof(int));

声明一个整数型的指针并向系统申请堆区上sizeof(int)的一块内存空间，并将指针p赋值为这片空间所在的起始地址；

malloc函数的返回值类型为void* ，这是一种特殊的指针类型，任何一个其他指针变量都可以直接被赋值给void*类型的指针，但如果反过来将无类型指针付给一个其他类型的指针变量，则必须要在前面加上被赋值指针变量的类型，如：(int *)，进行强制类型转换