Huge Lemon的博客

算法集（改）

2020-03-07

对算法集.doc的整理，好像都是真题（一部分算法题，一部分是填空、改错等）

筛选法求素数

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
#include <stdio.h>
#define SIZE 100
#define PWIDTH 10
int main() {
	char sieve[SIZE];
	int i, n, printcol;

	for (i = 0; i < SIZE; i++) {
		sieve[i] = 0;
	} //存放100以内的素数标识

	sieve[0] = 1; //1表示不是素数
	printcol = 0; //行计数
	for (n = 1; n <= SIZE; n++) {
		if (sieve[n - 1] == 0) {
			printf("%d ", n);
			if (++printcol >= PWIDTH) {
				putchar('\n');
				printcol = 0;
			}
			for (i = n; i <= SIZE; i = i + n) {
				//i的倍数(i += n)全为合数
				sieve[i - 1] = 1;
			}
		}
	}
	printf("\n");
	return 0;
}

字符串交换

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

void swap(char **p, char **q) {
	char *temp;
	temp = *p;
	*p = *q;
	*q = temp;
}

int main() {
	char *str1 = "aaaa", *str2 = "bbb";
	swap(&str1, &str2);
	puts(str1);
	puts(str2);
	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
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#define N 100

int main() {
	int i, j, k, a[N + 1], *p;

	for (i = 0, p = a; p <= a + N; i++, p++) {
		*p = i;
	}		   //填充序号
	p = a + 1; //取值
	k = N;	 //统计剩余人数
	for (j = 1; k != 1; p++) {
		if (p > a + N) {
			p = a + 1;
		} //若越界，返回数组首部，开始下一轮

		if (*p != 0) {
			if (j % 3 == 0) {
				*p = 0;
				k--;
				j = 0;
			} //判断是否为3
			j++;
		} //判断是否被推出
	}
	for (i = 1; i <= N; i++) {
		if (a[i] != 0) {
			printf("最后剩下的数字是：%d\n", a[i]);
		}
	}
	return 0;
}

求第k小

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
#include <stdio.h>
#define MAXN 10

int search(int a[], int n, int k);
int main() {
	int a[MAXN] = {3, 3, 1, 3, 3, 0, 0, 2, 1, 3}, n;
	printf("输入n值：\n");
	scanf("%d", &n);
	printf("%d \n", search(a, 10, n));
	for (int i = 0; i < 10; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

int search(int a[], int n, int k) {
	int low, high, i, j, t;
	k--;
	low = 0;
	high = n - 1;
	do {
		i = low;
		j = high;
		t = a[low];

		//快速排序
		do {
			while (i < j && t <= a[j]) {
				j--;
			}
			a[i] = a[j];
			while (i < j && t > a[i]) {
				i++;
			}
			a[j] = a[i];
		} while (i < j);

		//以下开始进行二分查找，找到第k个位置
		if (i == k) {
			return t;
		} else if (i < k) {
			low = i + 1;
		} else {
			high = i - 1;
		}
	} while (low < high);
	return a[low];
}

将字符串中的数字提取到数组中

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
#include <stdio.h>
#include <string.h>

int find_int(int *arr, char *pc);

int main() {
	int arr[10];
	char s[] = "ues11tc2015jsj320#";

	for (int i = 0; i < find_int(arr, s); i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}

int find_int(int *arr, char *pc) {
	int i = 0, j = 0, k = 0, sum = 0;

	while (pc[i] != '\0') {
		if ('0' <= pc[i] && pc[i] <= '9') {
			k = 1;
			sum = sum * 10 + pc[i] - '0';
		} else if (k == 1) {
			k = 0;
			arr[j++] = sum;
			sum = 0;
		} else {
			k = 0;
		}
		i++;
	}
	return j;
}

输入20个数（浮点+整型），逆序存放到单链表中

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
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int flag;
	union {
		int x;
		float y;
	} data;
	struct node *next;
} node;
node *L;

node *Creatlist(int n);

int main() {
	int n = 4;
	node *r;
	r = Creatlist(n);

	while (r) {
		if (r->flag == 0) {
			printf("%d ", r->data.x);
		} else {
			printf("%.1f ", r->data.y);
		}
		r = r->next;
	}
	return 0;
}

node *Creatlist(int n) {
	int i = 0, f;
	node *L, *p;
	L = NULL;

	while (i < n) {
		printf("输入第%d个数字的标志位：", i);
		scanf("%d", &f); //若标志位0，则输入整型，否则输入浮点型
		p = (node *)malloc(sizeof(node));
		p->flag = f;
		printf("输入数据:");
		if (f == 0) {
			scanf("%d", &p->data.x);
		} else {
			scanf("%f", &p->data.y);
		}
		p->next = L;
		L = p;
		i++;
	}
	return L;
}

求最高分分数学生的编号

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
#include <stdio.h>
#include <stdlib.h>
#define N 10

typedef struct student {
	int num;
	int score;
} stu;

void HighScore(stu *p);

int main() {
	stu arr[N];
	HighScore(arr);
	return 0;
}

void HighScore(stu *p) {
	int i = 0, max = 0;
	stu *r, q;
	while (i < N) {
		printf("请输入学生的编号和分数: \n");
		scanf("%d,%d", &p[i].num, &p[i].score);
		i++;
	}
	printf("\n");

	/*
	// 直接进行大小比较
	int num = p[0].num;
	max = p[0].score;
	for(i = 1; i < N; i++) {
		if(max < p[i].score) {
			max = p[i].score;
			num = p[i].num;
		}
	}
	printf("最大：%d, %d\n", num, max);
	*/
	
	for (i = 0; i < N - 1; i++) {
		r = &p[i];
		for (int j = i + 1; j < N; j++) {
			if (p[j].score < p[i].score) {
				r = &p[j];
			}
		} //一轮遍历找出余下数据中的最小者

		//交换数据
		q.num = r->num;
		q.score = r->score;

		r->num = p[i].num;
		r->score = p[i].score;

		p[i].num = q.num;
		p[i].score = q.score;
	}

	max = p[N - 1].score;
	for (i = N - 1; i >= 0; i--) {
		if (p[i].score == max) {
			printf("%d %d\n", p[i].num, p[i].score);
		}
	}
}

字符数组逆置

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

int main() {
	char str[] = "abcdefg";
	printf("%s\n", str);
	char p;
	int len = (int)strlen(str);
	for (int i = 0; i < len / 2; i++) {
		p = *(str + i);
		*(str + i) = *(str + len - i - 1);
		*(str + len - i - 1) = p;
	}
	printf("%s\n", str);
	return 0;
}

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
#include <stdio.h>

int main() {
	char str1[100], str2[100];
	char *p, *q;

	printf("输入两个字符串，中间用空格隔开\n");
	scanf("%s %s", str1, str2);
	printf("%s %s", str1, str2);
	getchar();
	p = str1;
	q = str2;
	if (*p != *q) {
		printf("\n两个字符串不相等\n");
	} else {
		while ((*p == *q) && (*p != '\0') && (*q != '\0')) {
			p++;
			q++;
		}
		if ((*p == '\0') && (*q == '\0')) {
			printf("\n两个字符串相等\n");
		} else {
			printf("\n两个字符串不相等\n");
		}
	}
	return 0;
}

传地址

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

int func(int *t) {
	return (*t-- = 3) - 1; //
} //t得到p的地址1，地址1中内容被赋值为3，函数返回值为2，t--移动到地址0

int main() {
	int arr[] = {10, 7, 5};
	int *p = arr + 1;			  //p得到数组的地址1
	printf("%d\n", func(p) + *p); //p依旧在地址1 其值为3 | func(p) == 2，*p == 3
	return 0;
}

地址理解

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

int main() {
	int arr[3] = {5, 3, 1};
	int *p = &arr[1];
	p[1] = *p - 1 + (p[-1] = 3);
	for (int i = 0; i < 3; i++) {
		printf("%d ", arr[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
24
25
26
27
28
#include <stdio.h>
double sum(int x, int n);

int main() {
	int x, n;

	printf("输入数值x及项数n：\n");
	scanf("%d %d", &x, &n);
	printf("%f\n", sum(x, n));
	return 0;
}

double sum(int x, int n) {
	int i;
	double a, b, s;
	s = 1.0;
	a = b = 1;
	for (i = 1; i <= n; i++) {
		a = a * x;
		b = b * i;
		if (i % 2 == 0) {
			s = s + a / b;
		} else {
			s = s - a / b;
		}
	}
	return s;
}

去掉字符串中的字母数字和重复项

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>
void del(char *str);
char arr[81];

int main() {
	char *s = "UE&&&stc2018##@%";
	del(s);
	printf("%s\n", arr);
	return 0;
}

void del(char *str) {
	int i = 0;
	while ((*str) != 0) {
		if (('a' <= *str && *str <= 'z') || ('A' <= *str && *str <= 'Z') || ('0' <= *str && *str <= '9')) {
			//arr[i]=*str;
			str++;
			//i++;
		} else {
			while (*str == *(str + 1)) {
				str++;
			}
			arr[i++] = *str++;
		}
	}
}
Tags: 算法
← 回文链表 反转链表 II →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏