C语言基础

字节大小

char：1 字节
unsigned char：1 字节
short：2 字节
unsigned short：2 字节
int：通常为 4 字节（32 位平台）或 8 字节（64 位平台）
unsigned int：通常为 4 字节（32 位平台）或 8 字节（64 位平台）
long：通常为 4 字节（32 位平台）或 8 字节（64 位平台）
unsigned long：通常为 4 字节（32 位平台）或 8 字节（64 位平台）
long long：8 字节
unsigned long long：8 字节
float：4 字节
double：8 字节
long double：通常为 8 字节（32 位平台）或 16 字节（64 位平台）

"i love you"字符串C语言中占多少字节
C语言字符串是字符数组表示，并且结尾用\0
"i love you"={'i',' ','l','o','v','e',' ','y','o','u','\0'}
11
字节

union联合体：不需要补位，找最大

struct结构体：union和数组直接加，其余需要按照补位

补位：char(1),int(4)

char需要补最大的int也就是char占四位总共8位

注意

字节小的可以转换位字节大的，大的转换小的时候向下取整数

输出类型

类型值必须对应打印类型格式

例子

**1:**不同类型进行运算时候，小类型要转换为大类型在进行运算

3+'a'这样的表达式会发生隐式类型转换，'a'会被转换为它对应的ASCII码值97，然后与3相加得到100，这个值是一个整型值。

**2:**变量定义，赋值一定是相同类型

    char a[10]="SERWERTE";//不会报错
    char b[5];
    b="wertw";//会报错，string类型给char类型会报错

**3:**字符数组的存储地址

在C语言中，字符数组会以字符串的形式存储，字符串的每个字符会占用1个字节的空间，并且在字符串的末尾会加上一个'\0'作为字符串的结束标志。这个'\0'字符也会被存储在数组中，占用1个字节的空间。

**4:**数组初始化

int a[2][3]={1};
只赋值a[0][0]=1,其余都为0

变量

变量名只能由字母、数字和下划线组成，且必须以字母或下划线开头，不能用特殊字符

自增

int a=1;
int b=++a; //a先加1 a=2 在赋值给b=2
int c=a++; //先赋值给c c=1,a在自增1；a=2

变量后先加

"unsigned char" 是计算机编程中的一种数据类型。它表示一个无符号字符型变量，即只能存储非负整数的字符型变量。

三种结构

1. 顺序结构：这是C语言中最基本的程序结构，指的是按照代码的先后顺序，逐行执行，不发生跳转。

2. 选择结构：这种结构用于根据特定条件来执行不同部分的代码。C语言中的选择结构主要由if、else if和else语句实现。switch语句也是一种选择结构，用于处理多个可能的情况。

3. 循环结构：这种结构用于重复执行一段代码，直到满足某个条件时停止。C语言中的循环结构主要由for、while和do...while循环实现。

   for(开始；判定条件；循环结束执行)

顺序结构

c语言逻辑判断的结果是0或者1

#include <stdio.h>
#include <stdlib.h>

int main (){
    if(3>2&&3%2){
        printf("%s","进入");
    }else{
        printf("%s","不进入");
    }
    return 0;
}

循环结构

swith case

满足一个case 里面没有break 会不判断，继续执行下面的case语句

default 默认执行，前面满足有break不会执行，没有会执行

#include <stdio.h>
#include <stdlib.h>

int main (){
    int i;
    for(i=0;i<2;i++){
        switch (i) {
            case 1:
                printf("%d",i);
            case 2:
                printf("%d",i);
            case 3:
                printf("%d",3);
            default:
                printf("%d",i);
        }
    };
    return 0;
}

注意

x=4
!x=0
在C语言中，!是一个逻辑非运算符，它会对操作数进行逻辑非运算。如果操作数为0，则逻辑非运算的结果为1；如果操作数不为0，则逻辑非运算的结果为0。

运算符

运算符表达式：（表达式有几个）一目、二目、三目

三目运算符：?:

逗号

int a;
printf("%d",(a=2*5,a*4,a+3));

在这段代码中，使用了逗号运算符。逗号运算符会从左到右依次计算每个表达式，并返回最右侧表达式的值。

首先，a=2*5 将 a 赋值为 10。

然后，a*4 计算得到 40，但这个值并没有被赋给任何变量，因此它会被忽略。

最后，a+3 计算得到 13，这是逗号运算符返回的值。

因此，printf("%d",(a=2*5,a*4,a+3)); 会输出 13。

逻辑运算符

逻辑运算符的优先级从高到低为：NOT（!） > AND（&&） > OR（||）

&& 有一个为真就是真，前面为真不需要判断后面直接返回真

||全真为真，前面为假直接返回假

int x,y,z,t;    
x=y=z=1;
t=++x || ++y && ++z; 
printf("%d,%d,%d,%d",x,y,z,t);

++x 将 x 自增 1，然后返回 x 的值，所以 ++x 的值为2，然后 t = ++x || ++y && ++z，因为 || 运算符具有短路特性，当 ++x 的值为真（非0）时，后面的 ++y && ++z 将不再执行，直接返回 ++x 的结果，所以 y 和 z 的值没有改变，仍然为1。而 t 的值就是 ++x 的结果，也就是2。所以最后的输出结果为 2,1,1,1。

普通函数

isspace是C语言中的一个函数，用于检查给定的字符是否是空白字符。

C语言程序的基本单位是函数。一个C语言程序可以由一个或多个函数组成，其中必须有一个名为main的函数，作为程序的入口点。

交换两个值与指针

$错误方法$

#include <stdio.h>
void f(int *p,int *q){
    int *c;
    c=p;
    p=q;
    q=c;
}
void tran(int a,int b){
    int c = a;
    a=b;
    b=c;
}
//u.a和u.b共享同一块内存区域。当你先给u.a赋值，然后给u.b赋值，你实际上是在覆盖u.a的值。
int main() {
    int x=4,y=8;
    int *p = &x;
    int *q = &y;
    printf("交换之前地址%d-%d\n",p,q);
    printf("交换之前指针对应的值%d-%d\n",*p,*q);
    f(p,q);
    printf("交换之后地址%d-%d\n",p,q);
    printf("交换之后指针对应的值%d-%d\n",*p,*q);
    printf("x,y之前的值%d-%d\n",x,y);
    f(&x,&y);
    printf("x,y之后的值%d-%d\n",x,y);
    printf("x,y之前的值%d-%d\n",x,y);
    tran(x,y);
    printf("x,y之后的值%d-%d\n",x,y);
}

函数f中的参数a和b是整型指针，函数内部对a和b的修改并不会影响到函数外部的p和q。这是因为指针变量在C语言中也是按值传递的，也就是说，函数f接收的是p和q的副本，而非它们本身。

因此，在函数f中交换a和b的值，并不会影响到p和q。所以，主函数main中的打印结果会显示，指针的地址和对应的值都没有发生变化。

指针函数

看后面，就是一个函数

返回函数结果的地址

定义：int *f()

#include <stdio.h>
int *f(){
    static  int x = 10; //全局使用
    return &x;          //返回x的地址
}
int main() {
    int *r = f();   //接受返回地址
    printf("%d\n",*r);   //打印地址对应的值
    return 0;
}

函数指针

看后面就是一个指针 ；一个指向函数的指针；在内存空间中存放的是函数的地址；

int add(int a,int b){
    return a+b;
}
int main() {
    int (*r)(int a,int b) = &add;   //函数指针接受函数地址
    int out = r(2,3);         //调用函数
    printf("%d\n",out);
    return 0;
}

输出与输入

格式化输出

int x=10,y=3;
printf("%d\n",x%y,x/y);
输出：1

printf函数中，格式化字符串"%d\n"只对应一个输出，即x%y的结果

int a=3366;
printf("│%-08d│",a);

这段代码的目的是打印整数 a，值为 3366，在一个格式化的字符串中，字符串的格式为 “│ %-08d │”。让我们分析一下这个格式化字符串：

• │ 是一个字面字符，它会被直接打印出来。
• % 是一个格式说明符的开始。
• - 表示左对齐。
• 0 表示如果数字的位数少于指定的宽度，那么不足的部分会用0填充。
• 8 表示数字的宽度为8位。
• d 表示打印一个整数。

所以，这段代码会打印出 │33660000│。整数 a（3366）左对齐，并在右侧用0填充，以确保总共有8位数字。

int x;
x = printf("I am c program\n");
printf("x=%d", x);

首先打印字符串 “I am c program\n”，然后打印变量 x 的值。变量 x 的值就是 printf 函数返回的值，也就是打印的字符数（不包括最后的 ‘\0’ 字符）。

打印与++

#include <stdio.h>
//合并方法
int main() {
    int a = 1;
    printf("%d ",a++);//在前先打印，a在+1；
    return 0;
}
1 

#include <stdio.h>
//合并方法
int main() {
    int a = 1;
    printf("%d ",++a);//a先+1，后先打印；
    return 0;
}
2

#include <stdio.h>

int main( ){
    int arr[] = {2,4,6,8,10,12,14,16};
    int *p=arr;
    printf("%d ", *p); //p指针指向数组第一元素
    printf("%d ", *p+1); //拿到p指针指向元素,该元素的值加1，在打印，p还是指向该元素，该元素的值没有发送变化
    printf("%d ", *p++); //先打印p指针指向元素的值；p指针往后后移一个
    printf("%d ", (*p)++); //先打印p指针指向元素的值；设置p指针指向的值在加1
    printf("%d ",--*p);    //先拿出p指针指向元素的值，设置元素值减1，在打印
    return 0;
}


#include <stdio.h>

int main( ){
    int arr[] = {1,2,3,4,5,6,7,8};
    int *p=arr + sizeof(arr) / sizeof(int) - 1;
    *p--+=123; // 双目大于单目 --》*p=*p+123;p是指针p--等同p往前移动一个
    printf("%d", *p--);//先打印，p在往前移动一个
    printf("%d", (*p)--);// 先拿着值，打印值，值在减1
    printf("%d", *--p);//先指针往前移动，在拿着值
    printf("%d",--*p);//先拿值，值在减1
    return 0;
}

    #include <stdio.h>
    int main()
    {
        FILE *fp;
        int i, a[6] = {1, 2, 3, 4, 5, 6}, b[6];
        fp = fopen("d.dat", "w + b");
        //将数组中元素写入fp文件指针，数组，每次写入元素存储地址大小，写六个，文件指针
        fwrite(a, sizeof(int), 6, fp);
        for (i = 0; i < 6; i++)
            //将数组中下标为2的元素写入fp文件指针，数组，每次写入元素存储地址大小，写六个，文件指针
            fwrite(&a[2], sizeof(int), 1, fp);
        //重置到文件开头
        rewind(fp);
        //定位到数组a的第三个元素（索引为2）  
        fseek(fp, sizeof(int) * 2, SEEK_CUR);
        // 读取6个整数到数组b  
        fread(b, sizeof(int), 6, fp);
        fclose(fp);
        for (i = 0; i < 6; i++)
            printf("%d,", b[i]);
    }
//结果
3,4,5,6,3,3,

数组

什么类型的数组用什么类型指针的接收

int arr[10] = {1,2,3,4,5,6,7,8,9,10,};
//c语言数组名是第一个元素的地址
int *p = arr;
int *p1 = arr+1;//数组第二个元素的地址
int *p2 = arr++;//不允许，编译报错
printf("%d",*p);
return 0;

#include <stdio.h>
#include <stdlib.h>

int main (){
    char arr[20] = {"hello world"};
    //数组名是第一个元素的地址
    char *p1=arr;
    //打印第一个元素
    printf("%c\n",*arr);printf("%c\n",*p1);
    //打印第六个元素
    printf("%c\n",*arr+5);printf("%c\n",*p1+5);
    //打印第六个元素地址
    if(arr+5 == p1+5){
        printf("%s","是一样的结果\n");
    }else{
        printf("%s","不是一样的结果\n");
    }
    printf("%c\n",arr+5);printf("%c\n",p1+5);
    return 0;
}

二维数组

#include <stdio.h>
int main (){
    int n;
    int array[1000][3];
    scanf("%d",&n);
    for(int i = 0;i<n;i++){
        scanf("%d %d %d",&array[i][0],&array[i][1],&array[i][2]);
    }
    printf("输入的数组:\n");
    for(int i=0;i<n;i++){
        printf("%d %d %d\n",array[i][0],array[i][1],array[i][2]);
    }
    return 0;
}

#include <stdio.h>

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);

    // 声明二维数组
    int array[m][n];

    // 获取用户输入的二维数组元素
    printf("请输入二维数组的元素:\n");
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &array[i][j]);
        }
    }

    // 打印二维数组以验证输入
    printf("\n您输入的二维数组是:\n");
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }

    return 0;
}

字符串

定义字符串

char *str1 = "Hello, World 1!";
char str2[] = "Hello, World 2!";
printf("%s\n",str1);
printf("%s\n",str2);

字符串的比较

字符数组

if(!*s2) 在 C 语言中是判断 s2 指向的字符是否为 '\0' —— 字符串结束标志。

if(*s2)在C语言中是判断s2指向的字符是否不为'\0'。

#include <stdio.h>
int main() {
    char a[5] ={'a','b','c','d','e'};
    char *ptr = (char*)(&a+1); //ptr指向a的下一个
    printf("%c, %c\n",*(a+1),*(ptr-1)); //*(ptr-1) 指向a中最后一个
    return 0;
}

文件读写

C语言操作文件的标准库是stdio.h库，这个库中包含了用于文件操作的函数，例如：

1. fopen()：打开文件；
2. fclose()：关闭文件；
3. fgetc()：从文件中读取一个字符；
4. fgets()：从文件中读取一行；
5. fprintf()：将格式化的数据写入文件；
6. fscanf()：从文件中读取格式化的数据。

FILE *fp; // 文件指针
char ch; // 读取的字符
// 打开文件，如果文件不存在则创建新文件
fp = fopen("./study.txt", "w+");
// 向文件中写入数据
fprintf(fp, "Hello, world!\n");
// 向文件中写入数据
fputs("This is testing for fputs...\n", fp);
// 将文件指针移到文件开头
fseek(fp, 0, SEEK_SET);
// 从文件中读取数据并输出到控制台
while ((ch = fgetc(fp)) != EOF) {
putchar(ch);
}
// 关闭文件
fclose(fp);

fprintf() 和 fputs() 都是用于向文件中写入数据的 C 语言标准库函数，但它们有一些区别。

区别一：参数不同

fprintf() 函数需要指定格式化字符串以及要写入的数据，可以写入多种类型的数据，并且可以按照指定的格式进行输出。而 fputs() 函数只能写入字符串数据，不能写入其他类型的数据。

区别二：返回值不同

fprintf() 函数返回写入的字符数，如果发生错误则返回负值。而 fputs() 函数返回非负数表示成功，返回 EOF 表示失败。

区别三：功能不同

fprintf() 函数可以将多种类型的数据按照指定的格式写入文件中，可以实现更加复杂的输出操作。而 fputs() 函数只能将字符串写入文件中，功能相对较为简单。

综上所述，fprintf() 函数更加灵活和强大，可以实现更加复杂的输出操作，而 fputs() 函数则适用于简单的字符串写入操作。

fgetc() 是一个 C 语言标准库函数，用于从指定的文件中读取一个字符。

putchar() 函数会将 ch 字符输出到标准输出设备上，并返回输出的字符。如果输出失败，则返回 EOF。

例子：

读取文件内容算平均值再写入到文件

#include <stdio.h>

int main() {
    FILE *fp;
    int num, sum = 0, count = 0;
    float avg;
    // 打开文件
    fp = fopen("data.txt", "r");
    if (fp == NULL) {
        printf("无法打开文件！\n");
        return 1;
    }

    // 读取文件中的数字并计算总和和数量
    while (fscanf(fp, "%d", &num) != EOF) {
        sum += num;
        count++;
    }
    // 计算平均值
    avg = (float)sum / count;
    // 将平均值写入文件
    fp = fopen("avg.txt", "w");
    if (fp == NULL) {
        printf("无法打开文件！\n");
        return 1;
    }
    fprintf(fp, "%.2f", avg);
    fclose(fp);
    printf("平均值已写入文件 avg.txt\n");
    // 关闭文件
    fclose(fp);
    return 0;

}

例子

#include "stdio.h"
int main(){
    FILE *fp = NULL;
    char s[] ="How to tell a story?", ch;
    fp = fopen("data. txt","w");
    //将字符串写入文件
    fprintf(fp,"%s", s);
    fclose(fp);
    //读文件
    fp = fopen("data. txt","r");
    //移送文件指针
    fseek(fp,4,SEEK_SET) ;
    //读取字符判断是不是到文件末尾
    while ((ch = fgetc(fp)) != EOF){
        //是t 往前两个设置为结束符，while判断结束跳出循环
        if(ch =='t'){
            s[ftell(fp) - 2]='\0';
        }
    }
    printf("%s\n",s);
    fclose(fp);
    return 0;
}

1. ftell(fp)：这是一个函数，用于获取文件指针 fp 当前在文件中的位置（以字节为单位）。
2. ftell(fp) - 2：从 fp 的当前位置往回数 2 个字节。
3. s[ftell(fp) - 2]：这表示字符数组 s 中位置为 ftell(fp) - 2 的字符。这里有一个假设，即 ftell(fp) - 2 是一个有效的数组索引，不会越界。
4. s[ftell(fp) - 2] = '\0';：这将 s 数组中位置为 ftell(fp) - 2 的字符设置为 \0（字符串的结束标记）。

联合体

#include <stdio.h>
union {
    int a;
    char b;

} u;
//u.a和u.b共享同一块内存区域。当你先给u.a赋值，然后给u.b赋值，你实际上是在覆盖u.a的值。
int main() {
    u.a = 65;
    u.b = 'a';//覆盖a的值
    printf("%d\n", u.a);
    printf("%c\n", u.b);

}

算法

算法复杂度

模式匹配:O(m*n)

KMP:O(m+n)

模式匹配

暴力

void bruteForce(char *src, char *target) {  
    int srcLen = strlen(src);  
    int targetLen = strlen(target);  
  
    for (int i = 0; i <= srcLen - targetLen; i++) {  
        int j;  
        for (j = 0; j < targetLen; j++) {  
            if (src[i + j] != target[j])  
                break;  
        }  
        if (j == targetLen) {  
            printf("Pattern found at index %d \n", i);  
        }  
    }  
}

kmp

i不会回退，当不匹配时，回退j,j回退的值在next数组中找

由匹配字符串构建，next数组

next数组构建原理：

nenxt数组长度与匹配串长度一致，循环匹配字符串，

next数组下标值：在匹配串中从0到下标的子串中，分别求该子串前缀或者后缀，从前缀或者后缀中找出一样的，公共缀的最长长度就是next数组对应的下标值

"ABCDABD"为例，
1.首先需要找出ABCDABD这一串字符串的所有前缀

    A
    AB
    ABC
    ABCD
    ABCDA
    ABCDAB
    ABCDABD
    2.然后找出每个前缀字符的最长公共前后缀
    "A"的前缀和后缀都为空集，共有元素的长度为0；
    "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
    "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
    "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
    “ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A”，长度为1；
    “ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB”，长度为2；
    "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
    3.然后就形成了部分匹配值（prefix table）
    每个前缀字符的最长公共前后缀放在一起就形成了部分匹配表，也就是：
    0 0 0 0 1 2 0

//构建next数组
void computeLPSArray(char *pat, int M, int *lps) {  
    int len = 0;   
    lps[0] = 0;   
  
    int i = 1;  
    while (i < M) {  
        if (pat[i] == pat[len]) {  
            len++;  
            lps[i] = len;  
            i++;  
        } else {  
            if (len != 0) {  
                len = lps[len - 1];  
            } else {  
                lps[i] = len;  
                i++;  
            }  
        }  
    }  
}  
  
void KMPSearch(char *pat, char *txt) {  
    int M = strlen(pat);  
    int N = strlen(txt);  
    //匹配字符串构建next数组
    int lps[M];  
    computeLPSArray(pat, M, lps);  
  
    int i = 0;   
    int j = 0;   
    while (i < N) { 
        //匹配上加1
        if (pat[j] == txt[i]) {  
            j++;  
            i++;  
        }  
        //找到返回index
        if (j == M) {  
            printf("Found pattern at index %d \n", i - j);  
            j = lps[j - 1];  
            //没有找到
        } else if (i < N && pat[j] != txt[i]) {  
            //不是第一个没有匹配，回退j
            if (j != 0)  
                j = lps[j - 1];  
            //第一个找到，直接加
            else  
                i = i + 1;  
        }  
    }  
}

数组合并

两个有序数组合并一个有序数组

#include <stdio.h>
//合并方法
int main() {
    int a[] = {1,3,5,7,9};
    int asize= sizeof(a)/ sizeof(a[0]);
    int b[] = {2,4,6,8,10};
    int bsize= sizeof(b)/ sizeof(b[0]);
    int r[] ={0,0,0,0,0,0,0,0,0,0};
    int rsize=asize+bsize;
    //合并ab到
    int i=0,j=0,l=0;
    while(i<=asize&&j<=bsize){
        if(a[i]<=b[j]){
            r[l]=a[i];
            i=i+1;
        }else{
            r[l]=b[j];
            j=j+1;
        }
        l=l+1;
    }
    for(int i=0;i<rsize;i++){
        printf("%d ",r[i]);
    }
    return 0;
}

动态规划

未知的问题用已知的解决

定义dp数组，判断数组里面是否有，有就取，没有就放在数组

斐波那契数列

int n =10;
int dp[n+1];
dp[0]=0;
dp[1]=1;
int l = sizeof(dp)/sizeof (dp[0]);
for (int j = 2; j <=l ; ++j) {
    dp[j]=dp[j-1]+dp[j-2];
}
for (int i = 0; i < l; ++i) {
    printf("%d ",dp[i]);
}
printf("%d ",dp[n-1]);

走楼梯

dp[1] = 1;  
dp[2] = 2;  
for (int i = 3; i <= n; i++) {  
	p[i] = dp[i - 1] + dp[i - 2];  
}  

最长连续递增子序列

#include <stdio.h>
int max(int a,int b){
    if(a>b){
        return a;
    }else{
        return b;
    }
}
int main() {
    int arr[] = {3,2,5,7,1,4,10,8,9};
    int len=sizeof(arr)/ sizeof(arr[0]);
    int dp[len]; //定义dp数组
    for (int i = 0; i < len; ++i) { //初始化
        dp[i]=1;
    };
    for (int i = 0; i < len; ++i) {
        int temp = arr[i];//i位置上的元素
        for (int j = i; j >0 ; j--) {
            if(arr[j]<temp && i==j+1){  //在i之前找到比这个小,并且是连续的
                dp[i]=dp[j]+1; //以i位置结尾的最长递增子序列的长度是j的加1（i本身）
                break;
            }
        }
    }
    int result = 1;
    for (int i = 0; i < len; ++i) { //初始化
        result=max(result,dp[i]);
    };
    printf("最长递增子序列的长度:%d",result);
    return 0;
}

贪心

最优解决:程序通过贪心算法计算出需要使用多少个硬币找零，收银员总是先给最大的硬币

也就是说要找的零钱张数最少

#include <stdio.h>
int found(int a[],int mon,int len,int dp[]){
    //要找给顾客的钱为0；就退出循环
    if(mon == 0){
        return 0;
    }else{
        for (int i = 0; i < len; ++i) {
            if(a[i]>=mon){
                //先找最大
                dp[i-1]=mon/a[i-1];
                mon=mon%a[i-1];
                len=i;
                break;
            }
        }
        return found(a,mon,len,dp);
    }
}
int main() {
    //若干零钱
    int arr[] = {1,2,5,10,20,50,100};
    int mon = 37;//实际要给顾客找零
    int len = sizeof(arr)/ sizeof(arr[0]);
    int dp[len];//对应零钱找的张数
    for(int i=0;i<len;i++){
        dp[i]=0;
    }
    found(arr,mon,len,dp);
    for(int i=0;i<len;i++){
        printf("%d张%d\n",dp[i],arr[i]);
    }
    return 0;
}

背包

01背包

#include <stdio.h>
int max(int a, int b) {
    return a > b ? a : b;
}

int knapsack(int w[], int v[], int n, int W) {
    int i, j;
    //构建二维数组：行放入物品种类0-n号物品种类，列是背包对应的重量，ij是背包对应的最大价值
    int dp[n+1][W+1];
    // 初始化dp数组--背包重量为0，其最大价值为0；背包种类为0；其最大价值为0
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= W; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = -1;
            }
        }
    }
    // 动态规划求解
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= W; j++) {
            if (j < w[i-1]) {//当前背包重量小于物品重量
                dp[i][j] = dp[i-1][j]; //背包最大价值是背包重量-1对应的最大价值
            } else {
                //当前背包重量可以放该物品
                //不放，背包最大价值还是当前物品重量-1对应的价值
                //放，背包最大价值是当前放入物品重量对应的价值+没放之前背包对应的最大价值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    return dp[n][W];
}

int main() {
    int w[] = {2, 1, 3}; // 物品的重量
    int v[] = {4, 2, 3}; // 物品的价值
    int W = 5; // 背包的总重量
    int n = sizeof(w) / sizeof(w[0]); // 物品的数量
    int max_value = knapsack(w, v, n, W); // 求最大价值
    printf("最大价值为：%d\n", max_value);
    return 0;

}

回溯

DFS:深度优先搜索借鉴递归、栈实现

BFS:广度优先搜索借鉴队列实现

DFS 递归判断迷宫有出路没有

#include <stdio.h>
#define M 5
#define N 5
//迷宫出口
int a=3;int b=4;
//迷宫
//0是没有访问过
//-1墙
//2访问过
int maze[M][N] = {
        {0, 0, 0, 0, 0},
        {0, -1, -1, 0, -1},
        {0, -1, 0, 0, -1},
        {0, -1, -1, -1, -1},
        {-1, 0, 0, 0, 0}

};
//找出路
int find_path(int m,int n){
    //当前是不是目标,是：返回找到出口
    if(m==a && n==b){
        maze[m][n]=2;
        return 1;
    }
    //刚开始一定可以进去；标记走过
    maze[m][n]=2;
    //在迷宫内并且可以走
    //上
    if(0<=m-1&&m-1<=M&&maze[m-1][n]==0){
        return find_path(m-1,n);

    }
    //右
    else if(0<=n+1&&n+1<=M&&maze[m][n+1]==0){
        return find_path(m,n+1);
    }
    //下
    else if(0<=m+1&&m+1<=M&&maze[m+1][n]==0){
        return find_path(m+1,n);
    }
    //左
    else if(0<=n-1&&n-1<=M&&maze[m][n-1]==0){
        return find_path(m,n-1);
    }else {
        return 0;
    }

}
int main() {
    if(find_path(0,0)){
        printf("有出路");
    }else{
        printf("没有出路");
    }
    //找出路

}

BFS长草问题–BFS借助队列

【问题描述】
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。
【输入格式】
输入的第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。
【输出格式】
输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
【样例输入】
4 5
.g...
.....
..g..
.....
2
【样例输出】
gggg.
gggg.
ggggg
.ggg.

#include<stdio.h>
#include <stdlib.h>
#define M 6
#define N 6
// 定义链表节点结构体
typedef struct node {
    int data;
    struct node* next;
} Node;
// 定义队列结构体
typedef struct queue {
    Node* front; // 队头指针
    Node* rear; // 队尾指针
    int size; // 队列长度
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

// 判断队列是否为空
int isEmpty(Queue* q) {
    return q->front == NULL;
}

// 获取队列长度
int getLength(Queue* q) {
    return q->size;
}

// 入队操作
void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 创建新节点
    newNode->data = data;
    newNode->next = NULL;
    if (isEmpty(q)) { // 如果队列为空，队头和队尾都指向新节点
        q->front = newNode;
    } else { // 否则，将新节点插入到队尾，并更新队尾指针
        q->rear->next = newNode;
    }
    q->rear = newNode; // 更新队尾指针
    q->size++; // 队列长度加1
}



// 出队操作
int dequeue(Queue* q) {
    if (isEmpty(q)) { // 如果队列为空，返回错误码-1
        return -1;
    }
    int data = q->front->data; // 取出队头节点的数据
    Node* temp = q->front; // 用临时变量保存队头节点地址
    q->front = q->front->next; // 将队头指针指向下一个节点
    if (q->front == NULL) { // 如果队头指针为空，说明队列已空，将队尾指针也置为空
        q->rear = NULL;
    }
    free(temp); // 释放队头节点的内存空间
    q->size--; // 队列长度减1
    return data; // 返回取出的数据

}
//第几个月后
int k = 1;
//草地
char c[M][N]=
        {{'.','.','.','.','.','.'},
         {'.','.','.','.','g','.'},
         {'.','g','.','.','.','.'},
         {'.','.','.','.','.','.'},
         {'.','.','g','.','.','.'},
         {'.','.','.','.','.','.'}};
//bfs长草
void bfs(Queue *x,Queue *y){
    //初始化:长草地址加入队列
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N ; ++j) {
            if(c[i][j]=='g'){
                enqueue(x,i);
                enqueue(y,j);
            }
        }
    }
    //队列长度大于0
    while(getLength(x)>0){
        //出队
        int qx = dequeue(x);
        int qy = dequeue(y);
        //循环拿到下一步
        //移动方向
        int mv[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
        for(int i=0;i<4;i++){
            int *temp = mv[i];
            int tx = qx+temp[0];
            int ty = qy+temp[1];
            //如果下个方向可以长草
            if(0<=tx&&tx<M && c[tx][ty]=='.'&&0<=ty&&ty<N){
                //标记长草
                c[tx][ty]='g';
                //坐标加入队列
                enqueue(x,tx);
                enqueue(y,ty);
            }
        }
    }
}
int main(){
    printf("初始化草地:\n");
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N ; ++j) {
            printf("%c ",c[i][j]);

        }
        printf("\n");
    }
    //创建队列
    Queue x;
    initQueue(&x); // 初始化队列
    Queue y;
    initQueue(&y); // 初始化队列
    //长草
    bfs(&x,&y);
    printf("%d个月草地长草后:\n",k);
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < M ; ++j) {
            printf("%c ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

例子

数组移位置

编写一个程序，有 n 个整数，要求你编写一个函数使其向右循环移动 m 个位置

输入：输入 n m 表示有 n 个整数，移动 m 位

输出：输出移动后的数组

例如：

输入：
10 5
1 2 3 4 5 6 7 8 9 0

输出：
6 7 8 9 0 1 2 3 4 5

    #include <stdio.h>
    int main()
    {
        int a[] ={1,2,3,4,5,6,7,8,9,0};
        int l=sizeof(a)/sizeof (int);
        int b[l];
        int index;
        for(int i=0;i<l;i++){
            int now = (i+5)%l;
            b[now]=a[i];
        }
        for(int i=0;i<l;i++){
            printf("%d ",b[i]);
        }

        return 1;
    }

判断字符数组大小

例如：

输入：
abc
abd

输出：

abd

#include<stdio.h>
int strcmp(char *p1,char *p2){
    //不为0，并且p1对应元素=p2对应元素 进入循环
    while (*p1 && (*p1 == *p2))
    {
        p1++;
        p2++;
    }
    return *(const unsigned char *)p1 - *(const unsigned char *)p2;

}
int main()
{
    char a[]="abc",b[]="abd";
    if(strcmp(a,b)>0)
        printf("%s", a);
    else
        printf("%s", b);
    return 0;
}

走楼梯

题目描述

现有一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用，你选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
编程要求

此题已给出部分代码，你可在/begin-end/之间进行编码，让程序通关。
输入输出格式

输入格式
第一行输入一个整数 costSize；
第二行输入数组 cost。
输出格式
输出一个整数。
输入输出样例1

输入
4
10 21 13 16
输出
23
输入输出样例2

输入
5
1 2 3 4 5
输出
6
说明提示

2≤costSize≤1000
1≤cost[i]≤100

获得二维数组中B、b的个数

#include <stdio.h>

int cnt(char *s) {
    int i = 0;
    int c = 0;
    // 如果字符串非空
    if (s)
        while (*(s + i)) {
            if (s[i] == 'B' || *(s + i) == 'b') {
                c++;
            }
            i++;
        }
    return c;
}

int main() {
    int c = 0;
    char s[][6] = {"book", "BBS", "bee", "table"};
    // 获取数组长度
    int len = sizeof(s) / sizeof(s[0]);
    // 遍历数组中的每个字符串，并计算'B'或'b'的个数
    for (int i = 0; i < len; i++) {
        //对于二维数组 s[0]是一个指针，指向book
        c += cnt(s[i]);
    }
    printf("%d\n", c);
    return 0;
}

函数指针

#include <stdio.h>
int* (*funcpl[2])(int*, int*,int*);
int (*funcp2[2])(int*, int*);
int* max(int *a, int *b,int *c){
    int*x=*a>*b?a:b;
    return *x >*c ?x:c;
}
int* min(int *a, int *b, int *c){
    int *x=*a<*b?a:b;
    return*x<*c?x:c;
}
int mul(int *a,int *b){
    return *a * *b;
}
int div(int *a, int *b){
    //判断b是不是0;不是返回a/b;是返回-1
    return *b?*a/(*b):-1;
}


int main(){
    int a = 10,b= 20,c = 30, result = 0;
    funcpl[0] = max;
    funcpl[1] = min;
    funcp2[0] = mul;
    funcp2[1] = div;
    for(int j= 0;j< 2;){
        result +=(*funcp2[j++])((*funcpl[0])(&a,&b,&c),(*funcpl[1])(&a, &b,&c));
    }
    printf("%d\n",result);
    return 1;
}

回文数

#include <stdio.h>

int is_palindrome(int num) {
    int reversed = 0;
    int temp = num;
   /**********FOUND**********/
    while (temp != 0) {
        reversed = reversed * 10 + temp % 10;
        /**********FOUND**********/
        temp=temp/10;

    }
    if (num == reversed) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    int num = 12321;
    if (is_palindrome(num)) {
        printf("%d is a palindrome.\n", num);
    } else {
        printf("%d is not a palindrome.\n", num);
    }
    return 0;
}

交换a,b的值

#include <stdio.h>

/**********FOUND**********/
void swap(int *a, int *b) {  // 错误：传递的是值的拷贝，无法实现交换
   /**********FOUND**********/
    int temp = *a;
   /**********FOUND**********/
    *a = *b;
   /**********FOUND**********/
    *b = temp;
}

int main() {
    int x = 10;
    int y = 5;
    printf("Before swap: x = %d, y = %d\n", x, y);
   /**********FOUND**********/
    swap(&x, &y);
    printf("After swap: x = %d, y = %d\n", x, y);
    return 0;
}

自增与逻辑

C语言中！=0的整数为ture,==0为false

#include <stdio.h>



int main(){
    int a = 1;
    int b=-2;
    for( ; a-- && b++; ){
        printf("%d ,%d,", a, b);
    }
    printf("%d ,%d,", a, b);
    return 1;
}

注意：a–&&

先拿a的值，判断true还是false，与&&右边比较，a在减少1

函数

函数的形参和实参分别占用不同的存储单元

若指针指向变量，则可以向指针所指内存单元写入数据

可以取变量的地址赋值给同类型的指针变量

printf("%d\n", strlen("\t"\\n'\065\08AB"));

    \t 代表一个制表符 (tab)。
    \\n 代表一个换行符，因为 \ 被转义了，所以它表示一个普通的换行。
    ' 是一个单引号字符。
    \065 是八进制表示的字符，其对应的十进制是 53，代表字符 S。
    \08AB 这里有点问题，因为 \08A 和 B 都被解释为独立的字符。八进制08A对应的是一个不可打印的控制字符，而B就是一个普通的字母。
	两个字符

求数组中最大可以构成的等差数组的组数

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//判断素数
int isPrime(int n){
    if(n<2){
        return 1;
    }else{
        for(int i = 2;i<n;i++){
           if(n%i==0){
               return 0;
           }
        }
        return 1;
    }
}
// 查找等差数列的函数
int findArithmeticSequences(int arr[], int n) {
    if (n < 3) return 0; // 如果数组元素少于3, 则不可能有等差数列

    int maxCount = 0; // 记录最大的等差数列组数  1 2 3 4 最大组数就有三组（1，2；2，3；3，4）
    for (int i = 0; i < n - 2; i++) { // 遍历数组
        int count = 0; // 计数器，记录当前起始点的等差数列数量
        int diff = arr[i + 1] - arr[i]; // 计算当前起始点的公差

        // 检查等差数列
        for (int j = i + 1; j < n - 1; j++) {
            if (arr[j + 1] - arr[j] == diff) {
                count++; // 找到一个等差数列，增加计数器
                j++; // 跳过这个元素，因为下一个元素可能与当前元素形成新的等差数列
            }
        }
        maxCount = count > maxCount ? count : maxCount; // 更新最大的等差数列组数
    }
    return maxCount + 1; // 返回最大的等差数列组数（+1是因为我们需要至少3个元素来形成一个等差数列）
}



int main() {
    int a=1,b=11;
    int max_len = 0; // 最长等差数列的长度
    int temp[b-a];
    //数组长度
    int index=0;
    //获取之间的素数数组
    for (int i = a; i <= b; i++) {
        if (isPrime(i)==0){
            continue; // 如果i不是质数，跳过
        }else{
            temp[index]=i;
            index++;
        }
    };
    int r = findArithmeticSequences(temp,index);
    printf("%d",r);

    return 0;

}