【趣学C语言和数据结构100例】
问题描述
判断一个素数能被几个 9 整除，即判断一个素数能整除几个 9 组成的数
读取7个数(1-50)的整数值，每读取一个值，程序打印出该值个数的 *。
计算字符串中子串出现的次数（暴力匹配）
- 计算字符串中子串出现的次数（KMP）
- 写一个函数，使给定的一个 3x3 的二维整型数组转置，即行列互换
代码分析
==31.素数整除几个 9 组成的数==
分析：9 组成的数，即9，99，999，9999等
输入素数，令sum=9,判断sum%素数是否为0，如果不是，则每次令sum变化为sum=sum*10+9，每次扩大设置计数。即可求解。
==32.队列的初始==
分析：使用for循环，进行7次输入，在每次输入，先判断是否为1-50，如果否则重新输入，如果是则使用for循环输出该值个数的 *。
==33.子串出现的次数，即暴力匹配==
分析：使用gets()输入2个字符串，使用strlen()计算他们的长度，创造2个for循环，第一个为整体的移动，第一个为当前的比较，第一个的条件为到他俩的长度的差<0,第二个的条件为到访问下面的下标<其长度，并且此刻字符相等则继续。每次进入第二个for循环，判断（下标是否等于其长度）即子串匹配成功，是计数++，并且重置 下面的下标，继续匹配下一个子串，可以选择跳过已经匹配的字符，即 i += 下面的长度 - 1;（不靠谱，可能会发生遗漏）
==34.子串出现的次数，即KMP==
分析：使用gets()输入2个字符串s1和s2。定义一个kmp函数来计算，即kmp(s1,s2);返回值为子串出现的次数。进来函数后，先创造一个计数工具count，使用strlen()计算他们的长度，第一步创造next 数组，计算子串的最长公共前后缀的长度。创造函数传入子串和next 数组。使用j记录位置，而且next[0] = 0，开始在子串遍历，当 pattern[i] 和 pattern[j] 相等时，next[i] = j + 1，但是!=使用while循环，一直回退到上一个匹配的位置，使用while循环，即j = next[j - 1]。计数之后即可返回，kmp函数，初始化 i = 0 (text 指针), j = 0 (pattern 指针)。当 text[i] 和 pattern[j] 相等时，继续比较下一个字符。否则回退到上一个匹配的位置。如果text[i] = = pattern[j]，则进行j++和i++;（必进行，所以放外面）如果 j == pattern.length，则匹配成功，计数加 1，并将 j 回溯到 lps[j-1]，继续搜索。最后返回计数，得到本题结果。
==35.数组转置==
分析：创造2个for循环，使array[i][j]和array[j][i]互换位置即可解答此题。
代码实现
#include <stdio.h>
#include <math.h>
#include <string.h>
// 计算模式串的 next 数组
void getNext(char *pattern, int *next) {
int j = 0;
next[0] = 0; // next[0] 总是为 0
for (int i = 1; pattern[i] != '\0'; i++) {
// 当 pattern[i] 和 pattern[j] 相等时，next[i] = j + 1
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1]; // 回退到上一个匹配的位置
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
}
// 使用 KMP 算法查找子串出现的次数
int kmp(char *text, char *pattern) {
int count = 0;
int textLength = strlen(text);
int patternLength = strlen(pattern);
int next[patternLength];
getNext(pattern, next); // 计算 next 数组
int i = 0, j = 0;
while (i < textLength) {
// 当 text[i] 和 pattern[j] 相等时，继续比较下一个字符
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1]; // 回退到上一个匹配的位置
}
if (text[i] == pattern[j]) {
j++;
}
if (j == patternLength) {
// 匹配成功
count++;
j = next[j - 1]; // 回退到上一个匹配的位置
}
i++;
}
return count;
}
// 打印二维数组
void printfarray(int array[3][3]) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
printf("%d ", array[i][j]);
}
printf("\n");
}
}
// 转置二维数组
void reversearray(int array[3][3]) {
int temp;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < i; j++) {
temp = array[i][j];
array[i][j] = array[j][i];
array[j][i] = temp;
}
}
}
int main()
{
// 31.判断一个素数能被几个9整除，即判断一个素数能整除几个9组成的数
int p,i;
long int sum=9;
printf("输入一个素数:");
scanf("%d",&p);
for(i=1;;i++){
if(sum%p==0){
break;
}
else{
sum =sum*10+9;
}
}
printf("素数%d能被%d个9整除的数%d。",p,i,sum);
// 32.读取7个数(1-50)的整数值，每读取一个值，程序打印出该值个数的 *。
int n;
for(int i=0;i<7;i++){
printf("输入一个数字:");
scanf("%d",&n);
if(n>50||n<1){
printf("重新输入一个数字:");
i--;
}else{
for(int j=0;j<n;j++){
printf("*");
}
}
printf("\n");
}
// 33.计算字符串中子串出现的次数暴力匹配
int count = 0;
int textLength, patternLength, i, j, k;
char text[50], pattern[50];
printf("输入2个字符串,主串在前,子串在后:\n");
gets(text);
gets(pattern);
textLength = strlen(text);
patternLength = strlen(pattern);
for (i = 0; i <= textLength - patternLength; i++) {
for (k = i, j = 0; j < patternLength && text[k] == pattern[j]; k++, j++);
if (j == patternLength) {
// 子串匹配成功
count++;
j = 0; // 重置 j，继续匹配下一个子串
i += patternLength - 1; // 跳过已经匹配的字符
}
}
printf("字符串中子串出现的次数: %d\n", count);
// 34.计算字符串中子串出现的次数KMP
char text[50], pattern[50];
printf("输入2个字符串,主串在前,子串在后:\n");
gets(text);
gets(pattern);
int count = kmp(text, pattern);
printf("字符串中子串出现的次数: %d\n", count);
// 35.写一个函数,使给定的一个 3x3 的二维整型数组转置,即行列互换
int array[3][3] = {
{
1, 2, 3}, {
4, 5, 6}, {
7, 8, 9}};
printf("转置前:\n");
printfarray(array);
reversearray(array);
printf("转置后:\n");
printfarray(array);
return 0;
}
总结
本文介绍了五个编程问题及其C语言实现，这些问题包括素数整除问题、打印星号、字符串匹配、二维数组转置等。这些问题覆盖了基础算法、字符串处理、数组操作等多个领域，展示了编程在解决实际问题中的应用。
素数整除问题要求判断一个素数能整除几个9组成的数。这个问题的解决关键在于循环构造9的倍数，并检查是否能被给定的素数整除。
打印星号问题要求读取7个数，并打印出相应数量的星号。这个问题的解决需要循环读取输入，并根据输入的数值打印相应数量的星号。
字符串匹配问题包括暴力匹配和KMP算法两种方法。暴力匹配通过双重循环遍历主串和子串，检查匹配情况；而KMP算法则通过预处理子串的最长公共前后缀数组，提高匹配效率。
二维数组转置问题要求将一个3x3的二维数组进行行列互换。这个问题的解决需要双重循环遍历数组，并交换行列对应的元素。
这些算法的实现不仅展示了C语言在处理字符串、数组和递归时的能力，也体现了算法设计的基本思想，如条件判断、循环控制和递归。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。
总的来说，这些算法问题不仅锻炼了编程能力，也加深了对数据结构和算法的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。同时，这些问题的解决也体现了算法在处理数据时的灵活性和效率，为我们在实际开发中遇到类似问题提供了解决思路。
