C语言学习笔记之实战篇

0x00 前言概览

学语言基础有了，剩下的就是编程了，没什么可说的，就是不断调试程序，在编程的过程中，一遍又一遍地复习巩固基础知识。此文收集整理了很多案例，能够全部达到独立完成，基本就算是入门了，之后就是尝试一些小项目，进一步提高自己的编程能力，这将是一条学无止境之路……（部分代码有坑，咳咳……）

0x01 切入正题

• 怎么获得一个数的百位，十位和个位

百位数：num/100 因为 int 是整数型，小数部分会省略。比如 765/100 得到7
十位数：num%100/10。比如765%100先得到65，65/10得到6
个位数：num%10。比如765%10得到5

• 利用异或 ^ 来交换两个数的值，且不引入其他变量

#include<stdio.h>
int main( )
{
    unsigned int a=60;         //0011 1100
    unsigned int b=13;         //0000 1101
    printf("a=%d,b=%d",a,b);   //输出a，b的值
    printf("\n");
    a=a^b;                     //a=a^b=0011 0001
    b=a^b;                     //b=a^b=0011 1100 相当于b1=(a^b)^b
    a=a^b;                     //a=a^b=0000 1101 相当于a1=(a^b)^((a^b)^b)
    printf("a=%d,b=%d",a,b);   //输出a，b的值
}

• 利用位与 & 运算，判断一个整数是否为2的整数次幂

二进制数的位权是以2为底的幂，如果一个整数 m 是 2 的 n 次幂，那么转换为二进制之后只有最高位为 1，其余位置为 0，再观察 m-1 转换为二进制后的形式以及 m&(m-1) 的结果，例如：

2 --> 0000 0010        1 --> 0000 0001        2&1 --> 0000 0010 & 0000 0001 = 0
4 --> 0000 0100        3 --> 0000 0011        4&3 --> 0000 0100 & 0000 0011 = 0
8 --> 0000 1000        7 --> 0000 0111        8&7 --> 0000 1000 & 0000 0111 = 0

可以看出所有的 1 完美的错过了，根据位与的特点可知 m&(m-1) 的结果为 0。
如果整数 m 不是 2 的 n 次幂，结果会怎样呢？例如 m=9 时：

9 --> 0000 1001        8 --> 0000 1000        9&8 --> 0000 1001 & 0000 1000 != 0
利用这一特点，即可判断一个整数是否是2的整数次幂。

#include <stdio.h>
int num;
int func(int num)
{
    if ((num>0)&&(num&(num-1))==0)
    {
        printf("%d是2的整数次幂",num);
    }
    else
    {
        printf("%d不是2的整数次幂",num);
    }
    return ((num>0)&&(num&(num-1))==0); //返回值为 1，则输入的正整数为 2 的整数次幂，返回值为 0 则不是。
}

int main()
{
    printf("请输入要查询的数\n");
    scanf("%d",&num);
    func(num);
}

• 打印九九乘法表

/*输出9*9口诀。共9行9列，i控制行，j控制列。*/
#include <stdio.h>
int main(){
    int i,j,result;
    for (i=1;i<10;i++){
        for(j=1;j<10;j++){
        result=i*j;
        printf("%d*%d=%-3d",i,j,result); /*-3d表示左对齐，占3位*/
        }
    printf("\n"); /*每一行后换行*/
    }
}

• 打印三角形星星堆

#include <stdio.h>
int main()
{
    int i, j, k;
    for(i=1; i<5; i++)
    {
        /* 观察每行的空格数量，补全循环条件 */
        for(j=i; j<5; j++)  
        {
            printf(" ");    //输出空格
        }
        /* 观察每行*号的数量，补全循环条件 */
        for( k=0;k<2*i-1;k++) 
        {
            printf("*");   //每行输出的*号
        }
        printf("\n");     //每次循环换行
    }
    return 0;
}

• 用 do while 求算术平方根

#include <stdio.h>
double DoSqrt(double z){
    double a=1;
    double b=0;
    double c=0;
    do{
        if(b*b<z){
            b+=a;
        }
        else{
            c=b;
            b-=a;
            a/=10;
        }
    }while(a>0.000001);

    return (b+c)/2;
}

int main(){
    double x, y;
    printf("请输入一个数字:");
    scanf("%lf", &x);
    if(x<0){
        printf("输入错误。");
    } else {
        y=DoSqrt(x);
        printf("%g 的平方根为: %g.\n", x, y);
    }

    int z=1;
    do{
        main();
        z++;
    }while(z>10);

    return 0;
}

• 使用for循环打印9×9乘法表

#include <stdio.h>
int main() 
{ 
    // 定义相乘数字i,j以及结果result
    int i, j, result;
     for(i=9;i>=1;i--)
     {
        for(j=1;j<=i;j++)
        {
            printf("%d*%d=%d ",i,j,result=i*j);
        }
        printf("\n");
     }
    return 0;
}

• switch与if语句的应用(计算是该年的第几天)

#include <stdio.h>
int main() 
{ 
    /* 定义需要计算的日期 */
    int date = 0;
    int year = 2008;
    int month = 8;
    int day = 8;

    switch(month)
    {
        case 12:date+=30;
        case 11:date+=31;
        case 10:date+=30;
        case 9:date+=31;
        case 8:date+=31;
        case 7:date+=30;
        case 6:date+=31;
        case 5:date+=30;
        case 4:date+=31;
        case 3:

        if((year%4==0&&year%100!=0)||year%400==0)
        {
            date+=29;
        }

        else
        {
            date+=28
        }
        case 2:
        date+=31;

        case 1:
        date+=day;

        printf("%d年%d月%d日是该年的第%d天",year,month,day,date);
        break;

        default:
        printf("error");
        break;
    }
    return 0;
} //continue只能用在循环体内

• 数组查找功能

当我们购物之后，拎着购物袋回到家，会一一检查购物袋中的物品看是否缺少或者都是想购之物。
那么应用到程序中，可以使用数组查找功能，看看是否存在该数据，如果存在并返回该元素的下标。

#include <stdio.h>
int getIndex(int arr[5],int value)
{
    int i;
    int index;
    for(i=0;i<5;i++)
    {
       /* 请完善数组查询功能 */
       if(arr[i]==value)
        {
            index=i;
            break;
        }  
       index=-1;
    }
    return index;
}

int main()
{
    int arr[5]={3,12,9,8,6};
    int value = 8;
    int index = getIndex(arr,value);      //这里应该传什么参数呢？
    if(index!=-1)
    {
        printf("%d在数组中存在，下标为：%d\n",value,index);             
    }
    else
    {
        printf("%d在数组中不存在。\n",value);    
    }
    return 0;    
}

• 分数问题

#include <stdio.h>
#define N 10
//打印分数 
void printScore(int score[])
{
    int i;
    printf("\n");
    for(i=0;i<N;i++)
    {
        printf("%d ",score[i]);               
    }
    printf("\n");     
}
//计算考试总分 
int getTotalScore(int score[])
{
    int sum = 0;
    int i;
    for(i=0;i<N;i++)
    {
        sum+=score[i];                
    } 
    return sum;
}
//计算平均分 
int getAvgScore(int score[])
{
    return getTotalScore(score)/N;   
}
//计算最高分 
int getMax(int score[])
{
    int max = -1;
    int i;
    for(i=0;i<N;i++)
    {
        if(score[i]>max)
        {
            max = score[i];              
        }                
    } 
    return max;
}
//计算最低分 
int getMin(int score[])
{
    int min =100;
    int i;
    for(i=0;i<N;i++)
    {
        if(score[i]< min)
        {
            min = score[i];              
        }                
    } 
    return min;
}
//分数降序排序 
void sort(int score[])
{
    int i,j;
    for(i=N-2;i>=0;i--)
    {
        for(j=0;j<=i;j++)
        {
            if(score[j]<score[j+1])
            {
                int temp;
                temp = score[j];
                score[j] = score[j+1]; 
                score[j+1]=temp;                  
            }                 
        }                   
    }
    printScore(score);     
}

int main()
{
    int score[N]={67,98,75,63,82,79,81,91,66,84};
    int sum,avg,max,min;
    sum = getTotalScore(score);
    avg = getAvgScore(score);
    max = getMax(score);
    min = getMin(score);
    printf("总分是：%d\n",sum);
    printf("平均分是：%d\n",avg);
    printf("最高分是：%d\n",max);
    printf("最低分是：%d\n",min);
    printf("----------成绩排名---------\n");
    sort(score);
    return 0;    
}

• 素数问题

#include<stdio.h>
#include<math.h>
int main(){
    int i,j;
    printf("100以内的素数有：\n");
    for(i=2;i<100;i++){
        for(j=2;j<sqrt(i);j++){
            if(i%j==0){
            break;
            }
        }
            if(j>sqrt(i)){
            printf("%d,\t",i);
            }
    }
}

• 数的阶乘

#include <stdio.h>
double factorial(unsigned int i)
{
   if(i <= 1)
   {
      return 1;
   }
   return i * factorial(i - 1);
}

int  main()
{
    int i = 15;
    printf("%d 的阶乘为 %f\n", i, factorial(i));
    return 0;
}

• 斐波那契数列：

#include <stdio.h>
int fibonaci(int i)
{
   if(i == 0)
   {
      return 0;
   }
   if(i == 1)
   {
      return 1;
   }
   return fibonaci(i-1) + fibonaci(i-2);
}
 
int  main()
{
    int i;
    for (i = 0; i < 10; i++)
    {
       printf("%d\t\n", fibonaci(i));
    }
    return 0;
}

• 猴子吃桃问题

猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就又多吃了一个。第二天又将剩下的桃子吃掉一半，又多吃了一个。以后每天都吃前一天剩下的一半零一个。到第10天在想吃的时候就剩一个桃子了,问第一天共摘下来多少个桃子？并反向打印每天所剩桃子数。

#include <stdio.h>
int getPeachNumber(int n)  
{
    int num;    
    if(n==10)
    {
       return 1;      
    } 
    else
    {
        num = (getPeachNumber(n+1)+1)*2;  
        printf("第%d天所剩桃子%d个\n", n, num); 
    }
    return num;
}

int main()
{
    int num = getPeachNumber(1);
    printf("猴子第一天摘了:%d个桃子。\n", num);
    return 0;
}

• 年龄问题

有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2人大两岁。问第2个人，说比第1个人大两岁。最后 问第1个人，他说是10岁。请问第5个人多大？

程序分析：
利用递归的方法，递归分为回推和递推两个阶段。要想知道第5个人岁数，需知道第4人的岁数，依次类推，推到第1人（10岁），再往回推。

#include <stdio.h> 
int dfs(int n)
{
    return n == 1 ? 10 : dfs(n - 1) + 2;
}
int main() 
{
    printf("第5个人的年龄是%d岁", dfs(5)); 
    return 0;
} 

• 打车问题

北京市出租车打车计费规则如下：
每公里单价计费2.3元
起步价13元(包含3公里)
晚上23点(含)至次日凌晨5点(不含)打车，每公里单价计费加收20%。
每次乘车加收1元钱的燃油附加税。
小明每天上下班都要打车，公司和家的距离为12公里，上午上班时间为9点，下午下班时间为6点。 计算小明每天打车的总费用。

#include <stdio.h>
float taxifee(int clock,int miles)
{
    float money;
    if(miles<=3)
    {
        money=14;
        printf("费用为14\n");
    }
    else
    {
        if(clock>=23 || clock<5)
        {
            money=13+1+2.3*(miles-3)*1.2;
            printf("夜间车费为：%f\n",money);
        }
        else
        {
            money=13+1+2.3*(miles-3);
            printf("日间车费为：%f\n",money);
        }
    }
    return money;    
}

int main()
{
    printf("打的总费用：%.1f\n",taxifee(9,12)+taxifee(18,12));
    return 0;
}

• 冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。

过程演示：

#include <stdio.h>
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}
int main() {
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

以升序排序为例冒泡排序的思想：相邻元素两两比较，将较大的数字放在后面，直到将所有数字全部排序。就像小学排队时按大小个排一样，将一个同学拉出来和后面的比比，如果高就放后面，一直把队伍排好。

#include <stdio.h>
int main()
{
    double arr[]={1.78, 1.77, 1.82, 1.79, 1.85, 1.75, 1.86, 1.77, 1.81, 1.80};
    int i,j;
    printf("\n************排队前*************\n");
    for(i=0;i<10;i++)
    {
        if(i != 9)   
            printf("%1.2f, ", arr[i]);  //%1.2f表示小数点前一位，小数点后精确到两位
        else
            printf("%1.2f", arr[i]);    //%1.2f表示小数点前一位，小数点后精确到两位
    }
    for(i=8; i>=0; i--)
    {
        for(j=0;j<=i;j++)
        {
            if( arr[j]>arr[j+1])      //当前面的数比后面的数大时
            {
                double temp;    //定义临时变量temp
                temp=arr[j];//将前面的数赋值给temp
                arr[j]=arr[j+1];             //前后之数颠倒位置
                arr[j+1]=temp;//将较大的数放在后面    
            }                 
        }                
    }
    printf("\n************排队后*************\n");
    for(i=0;i<10;i++)
    {
        if(i != 9)   
            printf("%1.2f, ", arr[i]);  //%1.2f表示小数点前一位，小数点后精确到两位     
        else
            printf("%1.2f", arr[i]);    //%1.2f表示小数点前一位，小数点后精确到两位
    }
    return 0;    
}

• 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

过程演示：

void swap(int *a,int *b) //交换两个变数
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(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[j] < arr[min])    //找到目前最小值
                min = j;    //记录最小值
           swap(&arr[min], &arr[i]);    //做交换
    }
}

• 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

过程演示：

void insertion_sort(int arr[], int len){
    int i,j,temp;
    for (i=1;i<len;i++){
            temp = arr[i];
            for (j=i;j>0 && arr[j-1]>temp;j--)
                    arr[j] = arr[j-1];
            arr[j] = temp;
    }
}

• 希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

过程演示：

void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap = gap >> 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

• 归并排序

把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾，可从上到下或从下到上进行。

过程演示：

迭代法
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

递归法
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

• 快速排序

在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。

过程演示：

迭代法
typedef struct _Range {
    int start, end;
} Range;
Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; // 避免len等于负值时引发段错误（Segment Fault）
    // r[]模拟列表,p为数量,r[p++]为push,r[--p]为 pop 且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 选取中间点为基准点
        int left = range.start, right = range.end;
        do
        {
            while (arr[left] < mid) ++left;   // 检测基准点左侧是否符合要求
            while (arr[right] > mid) --right; //检测基准点右侧是否符合要求
 
            if (left <= right)
            {
                swap(&arr[left],&arr[right]);
                left++;right--;               // 移动指针以继续
            }
        } while (left <= right);
 
        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}

递归法
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

• 猴子排序（Bogo Monkey）

如果数据稍多的话，几乎是不可能排序好的

#include <time.h>
#include <stdlib.h>
#include <stdbool.h>

void swap(int* x, int* y){
  //交换
  int temporary = *x;
  *x = *y;
  *y = temporary;
}
void randomize(int arr[], int length){
  //打乱数组
  for(int i = 0; i < length; i++){
    srand(time(NULL)+i); //引入i增加随机性
    if(rand()%2) swap(&arr[i],&arr[i+1]);
  }
  //printf("!"); //记录打乱次数
}
bool isSorted(int arr[], int length){
  for(int i = 0; i < length; i++) if(arr[i]>=arr[i+1]) return false;
  return true;
}
void bogoSort(int array[], int length){
  while(!isSorted(array,length)) randomize(array,length);
}

//Demo：
#include <stdio.h>
int main(){
  int numbers[] = {20,9,233,0,-23,7,1,666,4,345,63,45,2,45};
  bogoSort(numbers,14); //也可以改成更小
  for(int i = 0; i < 14; i++) printf("%d,",numbers[i]);
}

1. 希尔排序缩小递增量必须是要互质的。
2. 快速排序可以不用交换中间值。
   以下代码仅供参考：

void Array_Map_Sort_Quickly_Extrem(int* Array, int start, int end)
{
    int i=start;
    int j=end;
    int Pivot = Array[end];
    if(start<end)
    {
        while(i<j)
        {
            while(i<j &&Array[i]<=Pivot) i++;//Note: i choose the end as parameter
            Array[j]=Array[i];
            while(i<j &&Array[j]>=Pivot) j--;
            Array[i]=Array[j];
        }
        Array[i]= Pivot;
    }
    else 
        return;
    Array_Map_Sort_Quickly_Extrem(Array,start,i-1);
    Array_Map_Sort_Quickly_Extrem(Array,i+1,end);
}

0x02 References

《The C Primer Plus》
C语言教程

0x03 更多精彩

C语言学习笔记之基础篇

CTF系列 1 密码题解密网站总结（必收藏干货）

CTF系列 0 Crypto-密码学汇总

xcbyao's 黑色键盘 欢迎叨扰