西南科技大学814考研一
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" 是计算机编程中的一种数据类型。它表示一个无符号字符型变量，即只能存储非负整数的字符型变量。
三种结构
-
顺序结构：这是C语言中最基本的程序结构，指的是按照代码的先后顺序，逐行执行，不发生跳转。
-
选择结构：这种结构用于根据特定条件来执行不同部分的代码。C语言中的选择结构主要由
if、else if和else语句实现。switch语句也是一种选择结构，用于处理多个可能的情况。 -
循环结构：这种结构用于重复执行一段代码，直到满足某个条件时停止。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的函数，作为程序的入口点。
交换两个值与指针
错误方法 \textcolor{red}{错误方法} 错误方法
#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库，这个库中包含了用于文件操作的函数，例如：
- fopen()：打开文件；
- fclose()：关闭文件；
- fgetc()：从文件中读取一个字符；
- fgets()：从文件中读取一行；
- fprintf()：将格式化的数据写入文件；
- 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;
}
ftell(fp)：这是一个函数，用于获取文件指针fp当前在文件中的位置（以字节为单位）。ftell(fp) - 2：从fp的当前位置往回数 2 个字节。s[ftell(fp) - 2]：这表示字符数组s中位置为ftell(fp) - 2的字符。这里有一个假设，即ftell(fp) - 2是一个有效的数组索引，不会越界。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;
}