C语言学习笔记

整理一下所学知识以及课上ppt的内容!(`・ω・)

算法相关

性能分析

排序

相关文章

三数排序

一个简单的冒泡排序的变种,通过多次比较和交换来确保三个数按升序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void sort() {
int a, b, c, t;
scanf("%d%d%d", &a, &b, &c);
if (a > b) {
t = a;
a = b;
b = t;
}
if (b > c) {
t = b;
b = c;
c = t;
}
if (a > b) {
t = a;
a = b;
b = t;
}
printf("%d %d %d\n", a, b, c);
}

冒泡排序

原地排序,稳定,

O(n2)O(n^{2})
  • 基本思想:通过相邻数据的交换来达到排序的目的。
  • 排序过程:
    1. 比较第一个数与第二个数,若为逆序a[0]>a[1],则交换;然后比较第二个数与第三个数;依次类推,直至第n-1个数和第n个数比较为止——第一趟冒泡排序,结果最大的数被安置在最后一个元素位置上;
    2. 对前n-1个数进行第二趟冒泡排序,结果使次大的数被安置在第n-1个元素位置;
    3. 重复上述过程,共经过n-1趟冒泡排序后,排序结束

排序总轮数 = 元素个数 - 1
每轮对比次数 = 元素个数 - 排序轮数 - 1

冒泡排序

1
2
3
4
5
6
7
8
9
for(i = 0; i < N-1; i++){
for(j = 0; j < N-1-i; j++){
if(a[j] > a[j+1]){
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}

插入排序

原地排序,稳定,

O(n2)O(n^{2})
  • 基本思想:通过对未排序的数据逐个插入合适的位置而完成排序工作。
  • 排序过程:
    1. 首先对数组的前两个数进行从小到大的排序——第一趟插入排序;
    2. 接着将第3个数与排好序的两个数比较,将第3个数插入到合适的位置——第二趟插入排序;
    3. 重复上述过程,直到把最后一个数据插入合适的位置,共经过n-1趟排序后,排序结束。

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
// 从第二个元素开始
for (i = 1; i < N; i++){
// t是我们要插入到前面已排序部分的元素
t = a[i];
// 向前扫描已排序部分的元素
for(j = i-1; j >= 0 && t < a[j]; --j){
// 当前元素t小于a[j],则将a[j]向后移动一位(即a[j+1] = a[j]),为插入t腾出位置
a[j+1]=a[j];
}
// 不等于,说明t需要插入到a[j+1]的位置
if(j != i-1)
a[j+1] = t;
}

选择排序

原地排序,不稳定

O(n2)O(n^{2})
  • 基本思想:在每一步中选取最小值来重新排列,从而达到排序的目的。
  • 排序过程:
    1. 首先通过n-1次比较,从n个数中找出最小的, 将它与第一个数交换——第一趟选择排序,结果最小的数被安置在第一个元素位置上;
    2. 再通过n-2次比较,从剩余的n-1个数中找出关键字次小的记录,将它与第二个数交换——第二趟选择排序;
    3. 重复上述过程,共经过n-1趟排序后,排序结束。

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 外层循环,从数组的第一个元素到倒数第二个元素
for(i = 0; i < N-1; i++){
// 初始化最小元素的索引为当前索引i
k = i;
// 内层循环,从当前元素的下一个位置到数组的最后一个元素
for(j = i+1; j < N; j++)
// 如果找到比当前最小元素更小的元素,更新最小元素的索引为j
if (a[k]>a[j])
k = j;
// 如果最小元素的索引不是当前索引i
if(k != i){
t = a[i];
a[i] = a[k];
a[k] = t;
}
}

二分

  • 定义:按折半的方法在一个有序数组中查找一个给定值的元素。
    如果找到,则返回元素的位置(下标),否则返回-1。
  • 过程:每次考察数组当前部分中间元素,
    • 如果中间元素刚好是要找的,就结束搜索过程;
    • 如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;
    • 如果中间元素大于所查找的值同理,只需到左侧查找。

(均以升序数组为例)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int start, int end, int key){
int ret = -1; // 未搜索到数据返回-1下标
int mid;
while(start <= end){
mid = start + ((end - start) >> 1); // 直接平均可能会溢出,所以用这个算法
if(arr[mid] < key)
start = mid + 1;
else if(arr[mid] > key)
end = mid - 1;
else{ // 最后检测相等是因为多数搜索情况不是大于就是小于
ret = mid;
break;
}
}
return ret; // 单一出口
}

二分查找的局限性:

  • 数据结构:数组
  • 针对:有序数据
  • 适合处理静态数据,只能用在插入、删除操作不频繁,一次排序多次查找的场景中
  • 数据量太小不适合二分查找:如果要处理的数据量很小,顺序遍历就足够了
  • 数据量太大也不适合二分查找:数组为了支持随机访问的特性,要求内存空间连续,对内存的要求比较苛刻

查找第一个值等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int start = 0, end = N-1;
while(start <= end){
int mid = start + ((end - start) >> 1);
if(arr[mid] > key)
end = mid - 1;
else if(arr[mid] < key)
start = mid + 1;
else{
// 找到了第一个等于 key 的元素,跳出循环。
if ((mid == 0) || (arr[mid - 1] != key))
break;
else
end = mid - 1;
}
}

查找第一个大于等于给定值的元素

1
2
3
4
5
6
7
8
9
10
11
12
int start = 0, end = N-1;
while(start <= end){
int mid = start + ((end - start) >> 1);
if(arr[mid] < key)
start = mid + 1;
else{
if((mid == N-1) || (arr[mid - 1] < key))
break;
else
end = mid - 1;
}
}

递归

写递归代码的关键在于写递推公式

递归定义的两要素:

  • 递归边界条件:所描述问题的最简单情况
    它本身不再使用递归定义,也称为递归出口
  • 递归体:使问题向边界条件转化的规则
    递归定义必须能使问题越来越简单
    大规模问题和小规模问题之间的关系

常见递归公式

e.g. 计算n!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
long long fact(int n)
{
long long f;
if(n == 1) f = 1;
else f = n * fact (n-1);
// 若要打印1~n之间所有数的阶乘
// printf("%d! = %lld\n", n, f);
return f;
}

int main(){
int n;
do{
scanf("%d",&n);
}while(n<=0);
printf("%d! = %ld\n", n, fact(n));
return 0;
}

进栈过程

辗转相减法

1
2
3
4
5
6
7
8
9
10
int gcd(int m,int n){
int g;
if(m < n)
g = gcd(n, m);
else if(n == 0)
g = m;
else
g = gcd(m-n, n);
return g;
}

数字顺序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
void sequence(int n){
if(n/10 != 0)
sequence(n/10);
//
printf("%d", n%10);
}

int main(void){
int num;
printf("请输入一个整数:");
scanf("%d",&num);
if(num < 0){
putchar('-');
num = -num;
}
sequence(num);
return 0;
}

数字逆序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
void reverse(int n){
//
printf("%d",n%10);
if(n/10 != 0)
reverse(n/10);
}

int main(void){
int num;
printf("请输入一个整数:");
scanf("%d",&num);
if(num < 0){
putchar('-');
num = -num;
}
reverse(num);
return 0;
}

字符串顺序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
void sequence(){
char ch;
if((ch=getchar()) != '\n'){
//
putchar(ch);
sequence();
}
}

int main(void){
printf("请输入一个字符串:\n");
sequence();
putchar('\n');
return 0;
}

字符串逆序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
void reverse(){
char ch;
if((ch=getchar()) != '\n'){
reverse();
//
putchar(ch);
}
}

int main(void){
printf("请输入一个字符串:\n");
reverse();
putchar('\n');
return 0;
}

求斐波那契数列的第n项

1  1   2    3  5  8  13
a  b  a+b
    a    b  a+b

O(log n)O(log\ n)
1
2
3
4
5
6
7
int fib4(int n){
return fib_it(1,1,n);
}
int fib_it(int a,int b,int n){
if(n == 1) return a;
else return fib_it(b, a+b, n-1);
}

二分查找的递归实现

1
2
3
4
5
6
7
8
9
10
11
12
int binsearch(int list[], int bottom, int top, int key){
int mid;
if(bottom > top) return -1;
else{
mid = bottom + (top-bottom)/2;
if(key == list[mid]) return mid;
else if(key < list[mid])
return binsearch(list, bottom, mid-1, key);
else
return binsearch(list, mid+1, top, key);
}
}

数字转字符串输出

1234 -> 1-2-3-4

1
2
3
4
5
6
7
8
void change(long n){
if(n / 10){
change(n / 10);
putchar('-');
putchar(n%10 + '0');
}
else putchar(n + '0');
}

辗转相除法(欧几里得算法)求最大公约数

计算公式gcd(m, n) = gcd(n, m % n)

1
2
3
4
long long gcd(long long m, long long n){
if(n == 0) return m;
return gcd(n, m%n);
}

我们采用Euclid(欧几里得)算法来求最大公因子,其算法是:

  1. 输入两个正整数m和n。
  2. 用m除以n,余数为r,如果r等于0,则n是最大公因子,算法结束,否则(3)。
  3. 把n赋给m,把r赋给n,转2.。

辗转相除法

C5016

  • 编写程序,求N个有理数的和。
    每个有理数均以分子/分母的形式给出,你输出的和也必须是有理数的形式。
  • 第一行给出一个正整数N(≤100)。
    随后一行给出N个有理数,中间用空格隔开,每个有理数均以分子/分母的形式给出。
    题目保证所有分子和分母都在long long范围内。另外,负数的符号一定出现在分子前面。
  • 输出上述数字和的最简形式 —— 即将结果写成整数部分 分数部分,其中分数部分写成分子/分母,要求分子小于分母,且它们没有公因子。
    如果结果的分数部分为0,则只输出整数部分;然后,如果结果的整数部分为0,则只输出分数部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

// 这是一个递归函数,用于计算两个数 a 和 b 的最大公约数(GCD)。如果 a 为 0,则返回 b,否则递归调用自身,参数为 b % a 和 a。
inline long long gcd_(long long a, long long b) { return (a == 0) ? b : gcd_(b % a, a); }
// 这是一个包装函数,确保 a 小于 b 后调用 gcd_ 函数来计算最大公约数。
inline long long gcd(long long a, long long b) { return (a < b) ? (gcd_(a, b)) : (gcd_(b, a)); }
// 计算两个数 a 和 b 的最小公倍数(LCM)。公式为 a * b / gcd(a, b)。
inline long long lcm(long long a, long long b) { return a * b / gcd(a, b); }

// 定义一个有理数结构体 Rat,包含分子 a 和分母 b。构造函数初始化分子和分母,默认值为 0/1。
struct Rat{
long long a, b;
explicit Rat(long long aa = 0, long long bb = 1) { a = aa, b = bb; }
};
// 重载加法运算符,用于两个有理数相加。首先计算分母的最小公倍数,然后计算分子。最后约分结果。
inline Rat operator +(Rat A, Rat B){
Rat ret;
ret.b = lcm(A.b, B.b);
ret.a = A.a * (ret.b / A.b) + B.a * (ret.b / B.b);

long long g = gcd(abs(ret.a), ret.b);
ret.a /= g, ret.b /= g;

return ret;
}
// 重载加法赋值运算符,用于将一个有理数加到另一个有理数上。调用之前定义的 operator + 函数。
inline Rat operator+=(Rat &A, Rat B) { return A = A + B; }


// 主函数,首先读取有理数的个数 n。然后初始化结果 ans 为 0/1。读取每个有理数并求和。最后根据结果的形式输出整数部分和分数部分。
int main(){
int n;
scanf("%d", &n);
Rat x, ans(0, 1);
for (int i = 0; i < n; i++){
scanf("%lld/%lld", &x.a, &x.b);
if(x.a != 0)
ans += x;
}

if(abs(ans.a) >= ans.b)
printf("%lld ", ans.a / ans.b);
if(ans.a % ans.b)
printf("%lld/%lld", ans.a % ans.b, ans.b);
return 0;
}

高精度计算

由于C语言中对于整型数据来说都有其数据表示范围,当某个整数超出整型数据表示范围时,将无法用一个整型变量来存储它。

加法

我们可以用数字字符串的形式来表示它们,然后通过对数字字符串进行相加就可以实现任意长度的大整数求和。
基本思想:竖式计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define N 20 // 数字字符的个数

int tag = 0; // 进位标志

// 响铃
void beep(){
printf("\07");
}

// 读取数字字符串
void GetNumberStr(char s[], int n){
int i = 0;
char ch;
while(1){
ch = getch(); // 读取输入的字符,不显示
// 回车符,退出
if(ch == '\r')
break;
// 退格符
if(ch == '\b'){
if (i > 0){
printf("%c %c", ch, ch);
i--;
}
else beep();
continue;
}
// 非数字字符
if(ch < '0' || ch > '9'){
beep();
continue;
}
if(i < n){ // 数字字符
printf("%c", ch);
s[i++] = ch;
}
else beep();
}
s[i] = '\0'; // 置字符串结束标志
}

// 计算两个数字字符之和
char AddChar(char ch1, char ch2) {
char ch;
// 两数字字符所对应的数字与进位相加
ch = (ch1-'0' + ch2-'0') + tag;
// 结果大于10,进位
if(ch >= 10){
tag = 1;
// 将个位数减10后加上'0'转换成其数字字符
return (ch - 10 + '0');
}
// 结果小于10,不进位
else{
tag = 0;
// 将和数加上'0'转换成其数字字符
return (ch + '0');
}
}

// 去掉字符串左边的空格
void LeftTrim(char str[]){
int i;
// 查找第一个非空格字符的位置
for(i = 0; str[i] == ' '; i++)
;
strcpy(str, str+i);
}

// 计算两个数字字符串之和,放在c中
void AddNumberStr(char a[], char b[], char c[], int n) {
int i, j, k;
// 将c全部清空
memset(c, ' ', N+2);
i = strlen(a) - 1;
j = strlen(b) - 1;
k = n;

// 将被加数与加数按照从右向左的顺序相加
while(i >= 0 && j >= 0)
c[k--] = AddChar(a[i--], b[j--]);
while(i >= 0) // 被加数没有加完
c[k--] = AddChar(a[i--], '0');
while(j >= 0) // 加数没有加完
c[k--] = AddChar(b[j--], '0');
// 最后有进位,将其放在和数的最高位
if(tag == 1)
c[k] = '1';
c[N+1] = '\0'; // 置字符串结束标志
LeftTrim(c); // 去掉字符串c左边的空格
}


int main(){
char a[N+1] = {'\0'}, b[N+1] = {'\0'}, c[N+2];

printf ("a = ");
// 输入被加数a
while(strlen(a) == 0)
GetNumberStr(a, N);
printf ("\nb = ");
// 输入加数b
while(strlen(b) == 0)
GetNumberStr(b, N);
// 计算和数c
AddNumberStr(a, b, c, N);
printf("\na + b = %s \n", c);

return 0;
}

todo: e.g. oj 数列求和-加强版

除法

todo: pat 1017

素数

判断是否素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <math.h>
int main(){
int m, flag = 1;
scanf("%d", &m);
// 如果一个数m可以被某个数整除,那么这个数必定小于等于m的平方根
for(i = 2; i <= sqrt(m); i++){
if(m % i == 0){
flag = 0;
break;
}
}
if(flag) printf("%d 是素数\n", m);
else printf("%d 不是素数\n", m);

return 0;
}

埃拉托斯特尼筛法求素数

取一个从2开始的整数序列,通过不断划掉序列中的非素数的整数逐步确定序列里的素数。
方法:

  1. 令n为2,它是素数
  2. 划掉序列中n的所有倍数(n*2, n*3, n*4…)
  3. 找到n之后下一个未划掉的元素,它是素数,令n等于它并回到步骤2继续

用数组元素的代表对应整数,prime[i]代表整数i。
对每个整数只需表示两种情况:它未被划掉(1),或是已被划掉(0)。

e.g. 100以内的素数

法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>

int main(){
int i, j, prime[101];
prime[0] = 0;
prime[1] = 0;
for(i = 2; i <= 100; i++){
prime[i] = i;
}
// 划掉 i 的倍数
for(i = 2; i <= 100; i++){
for(j = i + 1; j <= 100; j++){
if(prime[i] && prime[j] && prime[j] % prime[i] == 0){
prime[j] = 0;
}
}
}
// 输出
for(i = 0; i <= 100; i++){
if(prime[i]){
printf("%d ", prime[i]);
}
}

return 0;
}

法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#define N 100
int main(){
int prime[N+1] = {0}, i, j;
// 初始时都被认为是素数
for(i = 2;i <= N; i++)
prime[i] = 1;

// 如果 i 是素数,则将 i 的所有倍数(从 i*2 开始)标记为 0(表示这些数不是素数)。
for(i = 2; i*i <= N; i++){
if(prime[i] == 1){
for(j = i*2; j <= N; j += i)
prime[j] = 0;
}
}
for(i = 2,j = 0;i <= N; i++){
if(prime[i] != 0)
// 每打印 5 个数换行一次
printf("%4d%c",i,((++j)%5==0?'\n':' '));
}
return 0;
}

质因子分解

C5047

  • 输入一个大于1的整数,编写程序将其分解成若干个质因子(素数因子)积的形式。
  • 将输入的正整数分解成若干个质因子积的形式,质因子的出现顺序按从小到大排列。如:40=2*2*2*5;
    如果整数本身为质数或素数,直接输出,如:13=13。

应该是用到了短除法的思想:3
短除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>

int main(){
int n, i;
scanf("%d", &n);
printf("%d=", n);
// 检查从2开始的所有可能的质因数
for(i = 2; n != 1; ){
// 若i是n的一个因数
if(n % i == 0){
printf("%d", i);
// 相除,继续检查剩余的部分
n /= i;
// n还未完全分解,输出乘号
if(n != 1){
printf("*");
}
}
else{
// i不是因数,尝试下一个数字
i++;
}
}
return 0;
}

字典序

字典序(Lexicographical Order)是一种字符串排序方式,类似于字典中单词的排列顺序。
它按照字符的ASCII值进行比较,从第一个字符开始逐个比较,直到找到不同的字符为止。
如果一个字符串是另一个字符串的前缀,则较短的字符串排在前面。

e.g.1 实验四2-10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <string.h>
#define NUM_COUNTRIES 8

int main() {
char countries[NUM_COUNTRIES][20] = {
"CHINA", "JAPAN", "KOREA", "INDIA", "CANADA", "AMERICA", "ENGLAND", "FRANCE"
};
int i, j;
char temp[20];

// 使用冒泡排序法对国家名字进行排序
for(i = 0; i < NUM_COUNTRIES-1; i++){
for(j = 0; j < NUM_COUNTRIES-1-i; j++){
if(strcmp(countries[j], countries[j+1]) > 0){
strcpy(temp, countries[j]);
strcpy(countries[j], countries[j+1]);
strcpy(countries[j+1], temp);
}
}
}
for(i = 0; i < NUM_COUNTRIES; i++){
printf("%s\n", countries[i]);
}
return 0;
}

e.g.2 输入多个城市的名字,按升序排列输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <string.h>
#define CITYNUM 10

int main(){
int i, j, k, num;
char city[CITYNUM][20];
char str[80];
num = 0; //实际输入的城市数初始化为0
//输入城市名字符串(长度不能超过19)
for(i = 0; i < CITYNUM; i++){
printf("input the name of the %dth city: ", i+1);
gets(str); //输入城市名
if(str[0] == 0) break; //为空串,表示输入结束
//城市名字符串超过19时,重输
if(strlen(str) > 19){
i--;
continue;
}
strcpy(city[i], str); //将输入的城市名保存到字符串数组中
num++; //实际输入的城市数增1
}
//选择排序
for(i = 0; i < num-1; i++){
k = i; //k为当前城市名最小的字符串数组的下标中
for(j = i+1; j < num; j++)
if(stricmp(city[k], city[j]) > 0)
k = j;
//将最小城市名的字符串city[k]与city[i]交换
if(k != i){
strcpy(str, city[i]);
strcpy(city[i], city[k]);
strcpy(city[k], str);
}
}
//显示排序后的结果
for(i = 0; i < num; i++)
printf("%s ", city[i]);
printf("\n");
}

位运算

快速模2

temp & 1等价于temp % 2

C5033

  • 编写程序,计算给定的一系列正整数中奇数的和。
  • 在一行中给出一系列正整数,其间以空格分隔。
    当读到零或负整数时,表示输入结束,该数字不要处理。
  • 输出正整数序列中奇数的和。
1
2
3
4
5
6
7
int ans = 0, temp;
while(1){
scanf("%d", &temp);
if(temp <= 0) break;
asn += (temp & 1) * temp;
}
printf("%d\n", ans);

无中间变量的值交换

1
2
3
4
5
6
7
8
9
10
11
12
13
// 使用加减法
a = a + b;
b = a - b;
a = a - b;
// 使用乘除法
a = a * b;
b = a / b;
a = a / b;
// 使用异或运算(适用于整数)
// 异或操作符的特性:任何数与其自身进行异或操作的结果为0,任何数与0进行异或操作的结果为其本身
a = a ^ b;
b = a ^ b;
a = a ^ b;

位运算代替乘法

n << 1 等价于 n * 2

位运算代替除法

n >> 1 等价于 n / 2

对于 n 是有符号数的情况,当你可以保证 n ≥ 0 时,n >> 1n / 2 指令数更少。

求出该数的各位数字

利用整除运算符/及求余运算符%按下述公式求得:

m/10p%10m/10^{p}%10

p=0时求得的是位数字,当p=1时求得位数字,当p=2时求得位数字。

利用这种方法可以使用循环结构得到位数不定的任意整数的逆序。

还可以用于计算所有数字之和,判断回文数。

逆序输出正整数

  1. 计算数字的位数

  2. 使用公式提取每一位数字,并逐步将新提取的数字(digit)添加到 reversed 的末尾

    • 通过 reversed * 10 将当前的 reversed 值向左移动一位,为新的数字腾出空间。
    • 然后通过 + digit 将新提取的数字添加到 reversed 的末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int reverseNumber(int num) {
int reversed = 0;
int p = 0;
int temp = num;

while (temp != 0) {
temp /= 10;
p++;
}

for (int i = 0; i < p; i++) {
int digit = num / (int)pow(10, i) % 10;
reversed = reversed * 10 + digit;
}

return reversed;
}

求任意正整数中的最大数字

num % 10; -> 获取num的最后一位

num /= 10; -> 去掉num的最后一位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

int main(){
int num, max = 0;
scanf("%d", &num);
while(num != 0){
if(num % 10 > max){
max = num % 10;
}
num /= 10;
}
printf("%d", max);
return 0;
}

拆数

读入一个整数num,统计该数的位数。
计算整数的位数

语言基础

逻辑运算符

浮点数作比较

if语句常见题目

基本输入输出

无符号整数的输出

常用的字符和字符串处理函数

printf打印字符串

fgets()更安全

gets与scanf区别

  • %lf: double
    %Lf: 输出long double型数据
    %.3s: 只输出字符串前三个字符

  • printf函数返回的是它打印了多少个字符

  • 如果缓冲区不空,scanf按自己的格式提取,提取成功,从缓冲区提走数据;提取失败,不从缓冲区提走数据。

  • 关于getchar和scanf函数的返回值:

    1.getchar函数

    • getchar的返回类型是int。
    • 它返回被读取的字符的 ASCII 值,或者在到达文件末尾时返回EOF(End of File)。
    • 因此,你通常将返回值存储在一个int类型的变量中,以便能够存储字符的 ASCII 值以及EOF。

    2.scanf函数

    • scanf函数返回成功读取和赋值的参数个数,或者在没有成功读取任何参数时返回EOF。
    • 如果scanf成功读取了一个字符,它将返回 1;如果成功读取了两个字符,将返回 2,以此类推。
    • 如果在读取之前就遇到文件末尾,它将返回EOF。
  • ctype.h 是 C 标准库中的一个头文件,提供了用于字符分类和转换的函数。这些函数主要用于检查字符是否属于某种类别(如字母、数字、空白符等),以及进行简单的字符转换(如大小写转换ch2=toupper(ch1);)。

  • conio.h 是一个非标准的 C 语言头文件,主要用于提供一些控制台输入输出功能。这个名字来源于 “Console Input/Output” 的缩写。提供了一些函数如:getch()getche():获取单个字符输入,但 getch() 不回显到屏幕上,而 getche() 则会回显。

  • 两次调用scanf()时,应使用getchar()吸收掉上次遗留的换行符和空格等。
    使用fflush(stdin)清空键盘缓存区是未定义行为。

数组

memset清零数组

memcpy复制数组元素

strlen()

strcpy()

strcat()

strcmp()

  • memset()是对内存的每个字节单元都赋值为ch,所以主要适合字节型数组的整体赋值与对非字节型数组的清零。

  • puts() - 向显示器输出字符串并自动换行
    gets() - 输入以回车结束的字符串

  • 处理字符串中的每一个字符的模板

    1
    2
    3
    4
    char str[10]="hello";
    for(i=0; str[i]!='\0'; i++){
    //在这里写求解过程
    }
  • sprintf()用于将格式化的数据写入字符串中。
    成功时,返回写入到字符串中的字符数(不包括终止符 \0)。失败时,返回一个负值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <stdio.h>

    int main() {
    char buffer[50];
    int n = 123;
    sprintf(buffer, "The number is %d", n);
    printf("%s\n", buffer); // 输出:The number is 123
    return 0;
    }

指针

零指针与空类型指针

通过指针访问二维数组

  • 在引用指针变量所指向的内容之前,必须对指针进行赋值,即将指针指向已经定义的变量或常量。
    指针使用前一定要指向可用的内存单元

结构与联合

无类型名的结构体

  • 利用typedef语句为结构类型起别名,格式为:typedef 类型名 类型名的别名;
    通常用大写字母来表示类型名的别名

常见题型

数字相关的计算

求完数

实验三1-3,模拟考

n以内的斐波那契数

实验三1-10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

int main(){
int f1 = 1, f2 = 1, n;
scanf("%d", &n);
printf("%d %d ", f1, f2);
while(f2 < n){
int temp = f2;
f2 = f1 + f2;
f1 = temp;
if(f2 < n)
printf("%d ", f2);
}
return 0;
}

守形数

C5014

  • 输出[m,n]范围内的守形数。
    若某数的平方的低位与该数本身相同,则称该数为守形数。
    例如,25就是守形数,因为25的平方是625,而625的低位25与原数25相同。

  • 输入包含2个正整数m和n,之间用空格隔开。2≤m≤n≤10000

  • 输出所有满足条件的整数,整数之间用1个空格隔开,行首行末均无空格。如果不存在,请输出”No exist”。

https://gitee.com/journey-of-dawn/wust-oj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
int main(){
int m, n, k, t, s, flag = 0;
scanf("%d %d", &m, &n);

for (int i = m; i <= n; i++){
t = i; k = i * i; s = 1; //t表示某数,k表示某数的平方

while (t){
s *= 10; //s用来记录某数平方的位数(比如t=25,s=100)
t /= 10;
}

//检验某数平方的低位与某数是否相等
if ((k % s) == i){
flag++;
if (flag == 1)
printf("%d", i);
else
printf(" %d", i);
}
}

if (flag == 0)
printf("No exist");
return 0;
}

进制转换

21年期末程序填空题
十进制/二进制转化器:编写一个函数DeToBi,将十进制数转化为二进制表示,转化后的而二进制数存放在数组db中。
例如:十进制数64,输出二进制表示1000000.

1
2
3
4
5
6
7
8
9
10
int DeToBi(int db[], int n){
int i = 0, r;
do{
r = n % 2; // 计算 n 除以 2 的余数,即当前位的二进制值
n = n / 2; // 将 n 除以 2,准备计算下一位
db[i] = r; // 将当前位的二进制值存入数组 db 中
i++; // 数组索引加 1,准备存储下一位
}while(n); // 当 n 不为 0 时继续循环
return i; // 返回二进制数的位数
}

【例6.11】进制转换:将十六进制数字串转换成整数,假定字符串中不含任何非法字符
注意:

  • 本例为模拟scanf函数的%x所实现的功能
  • 输入的前缀0x或0X
  • 进制的基数
  • 对于数字字符、大写字母、小写字母应分别考虑
1
2
3
4
5
6
7
8
9
10
11
int i = 0, number = 0;
str[i] == '0' && (str[i+1]=='x' || str[i+1]=='X') ? i+=2 : i;
for( ; str[i] != '\0'; i++){
if(str[i]>='0' && str[i]<='9')
number=number*16+str[i]-'0';
else if(str[i]>='a' && str[i]<='f')
number=number*16+str[i]-'a'+10;
else if(str[i]>='A' && str[i]<='F')
number=number*16+str[i]-'A'+10;
}
printf("%s=%d\n",str,number);

日期计算

计算该年中的第几天

实验五2-5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>

int mday(int y, int m){
int m_list[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
if((y % 4 == 0 && y % 100 != 0) || (y % 100 == 0 && y % 400 == 0))
m_list[2]++;
return m_list[m];
}

int nday(int y, int m, int d){
int i, sum = 0;
for(i = 1; i < m; i++){
sum += mday(y, i);
}
sum += d;
return sum;
}

int main(){
int ret, y, m, d;
while(1){
printf("输入“年 月 日”:");
scanf("%d%d%d", &y, &m, &d);
if(m >= 1 && m <= 12 && (d <= mday(y, m))) break;
else printf("输入有误,重新输入\n");
}
ret = nday(y, m, d);
printf("%d", ret);
return 0;
}

字符串操作

求两字符串交集

22年期末程序填空题
从键盘输入两个长度不超过80的字符串s1和s1,求两者的交集并输出(使用指针形式填空)。
如 s1:”abcabf”,s2:”txabccfde”,则输出为:”abcf”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <string.h>

void find(char *s1, char *s2, char *s){
// 遍历第一个字符串s1
for( ; *s1 != '\0'; s1++){
char *p = s2;
// 遍历第二个字符串s2
for( ; *p != '\0'; p++)
// 如果在s2中找到与s1当前字符相同的字符,跳出循环
if(*s1 == *p) break;
// 如果在s2中找到了相同的字符
if(*p != '\0'){
char *q = s;
// 遍历结果字符串s,检查是否已经包含该字符
for( ; *q != '\0'; q++)
if(*p == *q) break;
// 如果结果字符串s中不包含该字符,则将其添加到s中
if(*q == '\0')
*q = *s1;
}
}
}
int main(){
char s1[80], s2[80], s[80];
// 初始化结果字符串s,全部置为0
memset(s, 0, sizeof(s));
scanf("%s%s", s1, s2);
find(s1, s2, s);
if(strlen(s) != 0)
puts(s);
else printf("No");
return 0;
}

删除相同字符

  • 例:从字符串中删除与所给字符相同的字符并压缩字符串
  • 如:字符串为char s[20]=”AABBBcBB”;
    要删除的字符为char key=’B’;
1
2
3
4
5
6
7
int i, j;
char key = 'B';
for(i=0, j=0; s[i]!='\0'; i++){
if(s[i] != key)
s[j++] = s[i];
}
s[j] = '\0';

判断回文字符串

1
2
3
4
5
6
7
8
9
10
int fun(char *s){
char *p1, *p2;
p1 = p2 = s;
while(*p2) p2++;
--p2;
while(p1 < p2)
if(*p1++ != *p2--)
return 0;
return 1;
}

字符串匹配

todo: 数组3ppt p48