《妙趣横生的算法》（C语言实现）-第10章算法设计与数据结构面试题精粹

2023-12-31 06:28
文章标签 算法 语言 实现 设计 数据结构 面试题 精粹 妙趣横生

本文主要是介绍《妙趣横生的算法》（C语言实现）-第10章算法设计与数据结构面试题精粹，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【10-1】输入一个字符串并将它输出，以ctrl+z组合键表示输入完毕，要求将输入的字符串中多于1个的连续空格符合并为1个。

//10-1 2023年12月30日17点11分-17点18分
# include <stdio.h>
int main()
{char c;c = getchar();//scanf("%c", &c);int space = 0;while (c != EOF) {if (c == ' ') {  //遇到空格符时统计空格数目 space++;if (space == 1) {putchar(c);}} else {  //遇到非空格符时清零空格数目 space = 0;putchar(c);  //显示非空格符 }
//        不要用scanf("%c", &c);c = getchar();}return 0;
}

总结：这类输入流操作的问题可以直接对输入的字符进行判断和处理，无需将输入的字符先保存在数组或者其他数据结构中，这样会非常容易解决。
【10-2】从终端输入10个整数，输出其中最大的数和次大的数。要求输入的10个整数互不相等。

//10-2 2023年12月30日17点25分-17点42分 
# include <stdio.h>
void bubble_sort(int a[], int n)
{for (int i = n-1; i > 0; i--){for (int j = 0; j < i; ++j) {if (a[j] < a[j+1]) {int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}}printf("第%d次循环排序后结果：", n-i);for (int k = 0; k < n; k++) {printf("%3d", a[k]);}printf("\n");}
}
int main()
{int arr[10];  //定义一个数组printf("Please input 10 integers:\n"); for (int i = 0; i < 10; i++) {  //输入数据 scanf("%d", &arr[i]);}bubble_sort(arr, 10);  //冒泡排序printf("After sorting:\n");for (int i = 0; i < 10; i++) {  //输出数据 printf("%d ", arr[i]);}printf("\nthe maxest number is %d, the other is %d\n", arr[0], arr[1]); return 0;
} 
//12 43 23 13 65 17 98 45 67 88

//书上的代码
# include <stdio.h>
int main()
{int a, maxVal = -1000, secondVal = -1000;for (int i = 0; i < 10; i++) {scanf("%d", &a);if (a > maxVal) {secondVal = maxVal;maxVal = a;} else {if (a > secondVal) {secondVal = a;}}}printf("The max value is    %d\n", maxVal);  //输出最大的数 printf("The second value is %d\n", secondVal);  //输出次大的数 return 0;
}

总结：类似上一道题，可以不用保存这10个整数，直接在数据输入的过程中加以控制和比较。
【10-3】编写一个程序，求分数序列的前50项和。

//10-3 2023年12月30日17点50分-17点56分 
# include <stdio.h> 
int main()
{double s = 0.0;double a = 2, b = 1;  //用浮点类型，用int结果就不一样了s += a / b;for (int i = 1; i < 50; ++i) {double tmp = b;b = a;a += tmp;s += a / b;}printf("sum is %g\n", s);return 0;
}

总结：用好数据类型，可以写成函数哦！
【10-4】编写一个函数实现字符串内容逆置，要求不另外开辟字符串空间。

//10-4 2023年12月30日18点01分 
# include <stdio.h>
# include <string.h>
void reverse(char *s)
{for (int i = 0, j = strlen(s) - 1; i < j; i++, j--) {char tmp = s[i];s[i] = s[j];s[j] = tmp;}
}
int main()
{char s[200];printf("Please input a string:\n");gets(s);reverse(s);printf("After reversing:\n%s", s);return 0;
}

【10-5】编写一个程序，将两个字符串连接，要求不破坏原有字符串。

//10-5 2023年12月30日18点04分-18点10分 
# include <stdio.h>
char * cnnString(char *s1, char *s2)
{char s[400];int len = 0;for (int i = 0; s1[i]; i++) {s[len++] = s1[i];}for (int i = 0; s2[i]; i++) {s[len++] = s2[i];}s[len] = '\0';return s;
}
//书上代码
/*char * cnnString(char *s1, char *s2)
{int len, len1, len2;char *s3;len1 = strlen(s1);len2 = strlen(s2);len = len1 + len2 + 1;s3 = (char *)malloc(len);for (int i = 0; i < len1; i++)s3[i] = s1[i];for (int i = 0; i < len2; i++)s3[i+len1] = s2[i];s3[len-1] = '\0';return s3;
}*/
int main()
{char s1[200], s2[200];printf("Please input a string:\n");gets(s1);printf("Please input a string:\n");gets(s2);char *s;s = cnnString(s1, s2);printf("Connecting:\n%s", s);
//    printf("%s", cnnString(s1, s2));return 0;
}

总结：我自己写的代码运行时警告：返回了局部变量的地址，要注意！！这是因为在函数里创建的字符串是在栈上创建的，用动态分配，书上的代码就不会有警告。
【10-6】编写一个递归函数，求和。

//10-6 2023年12月30日18点17分-18点20分 
# include <stdio.h>
int sum(int n)
{if (n == 1)return 1;elsereturn n+sum(n-1);
} 
int main()
{int n;printf("Please input a integer:\n");scanf("%d", &n);printf("The result is \n%d\n", sum(n));return 0;
}

总结：递归函数解决问题哦。找到递归终止条件，递归函数。
【10-7】用递归方法编写一个程序，返回整型数组array中的最大值。数组array中的元素互不相等。

//10-7 2023年12月30日19点37分-19点51分 
# include <stdio.h>
int max(int a[], int n)  //递归方法哦！
{if (n == 1)return a[0];else //return a[n-1] >= max(a, n-1) ? a[n-1] : max(a, n-1);  //目前正确 return a[0] >= max(a+1, n-1) ? a[0] : max(a+1, n-1);
//        return a[0] >= max(a, n-1) ? a[0] : max(a, n-1);  //错误 
//        return max(a, n-1);  //错误 
}
int main()
{int n;printf("Please input a integer:\n");scanf("%d", &n);int arr[n];printf("Please %d numbers:\n", n);for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}printf("The maxValue is\n%d\n", max(arr, n));return 0;
}

【10-8】用递归方法解决输出字符串。
看到这个题目时，我感觉不使用递归的话，应该很好输出。本题的输出结果其实就是这个小写字符串与它对应的大写字符串的逆序交叉输出。使用递归方法的话，终止条件应该是只包含一个小写字母，那么输出两个字母；如果是包含n个小写字母呢？
想法：n个小写字母其实就是一个小写字母循环，规律呢？

//10-7 2023年12月30日19点52分-20点16分 
# include <stdio.h>
# include <string.h>
char upper(char c)  //将小写字母转换为大写字母 
{return (c-'a'+'A');
}
//void func(char *s, int n)  //错误 
//{
//    if (n == 1) {
//        printf("%c%c", s[strlen(s)-n]-32, s[n-1]);
//    } else {
//        func(s, n-1);
//    }
//}
void func(char *str, int n, int i)  //递归法按要求格式输出字符串 
{if (i < n) {printf("%c%c", upper(str[n-i-1]), str[i]);func(str, n, i+1);}
}
int main()
{char s[200];printf("Please input a string:\n");  //输入字符串 scanf("%s", s);printf("The result is\n");func(s, strlen(s), 0);  //调用递归函数func() return 0;
}

总结：这道题目还是有些难思考到。
【10-9】递归方法实现字符串内容就地逆置。

//10-9 2023年12月30日20点19分-20点27分 
# include <stdio.h>
# include <string.h>
void reverse(char *s, int n, int i)
{
//    if (n == 1) {  //错误 
//        printf("%c", s[n-1]);
//    } else {
//        reverse(s, n-1);
//    }if (i < n) {  //目前正确 printf("%c", s[n-1-i]);reverse(s, n, i+1);}
}
int main()
{char s[200];printf("Please input a string:\n");gets(s);printf("The result is\n");reverse(s, strlen(s), 0);return 0;
} 

//10-9 书上代码 
# include <stdio.h>
# include <string.h>
void reverser(char *s, int n, int i)
{if (i < n) {char tmp = s[n];  //字符的置换 s[n] = s[i];s[i] = tmp;reverser(s, n-1, i+1);  //递归调用函数reverser() }
}
void reverse(char *s)
{reverser(s, strlen(s)-1, 0);  //调用递归函数 
}int main()
{char s[200];printf("Please input a string:\n");gets(s);reverse(s);printf("The result is\n%s", s);return 0;
}

总结：要与题目要求的接口一致哦！！
【10-10】编程计算可以制作出多少种水果拼盘。

//10-10 2023年12月30日20点34分-20点42分
# include <stdio.h> 
void func(int n)
{switch(n) {case 0: printf("apple "); break;case 1: printf("orange "); break;case 2: printf("banana "); break;case 3: printf("pineapple "); break;case 4: printf("pear "); break;}
}
int fruitPlate()
{int count = 0;for (int i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) {if (j == i) {continue;}for (int k = 0; k < 5; k++) {if (k == j || k == i) {continue;}count++;func(i);func(j);func(k);printf("\n");}}}return count;
}
int main()
{printf("There are %d kinds of methods for arranging plate.", fruitPlate());return 0;
}

总结：穷举法。写成函数然后调用哦！
【10-11】请在屏幕上输出一张乘法口诀表。

//10-11 2023年12月30日20点43分-20点46分 
# include <stdio.h>
void func()
{for (int i = 1; i < 10; i++) {for (int j = 1; j <= i; j++) {printf("%d*%d=%2d  ", j, i, j*i);}printf("\n");}
}
int main()
{func();return 0;
}

【10-12】编程找出一个数字。

//10-12 2023年12月30日20点47分-20点50分 
# include <stdio.h>
# include <math.h>
int is_square(int n)  //判断完全平方数函数
{int r = sqrt(n);if (r * r == n) {return 1;} else {return 0;}
}
int func(void)
{for (int i = 1; ; i++) {  //穷举法找数字if (is_square(i+100) && is_square(i+168)) {return i;}}
}
int main()
{printf("The number is %d", func());return 0;
}

【10-13】求和。

//10-13 2023年12月30日20点53分-20点57分 
# include <stdio.h>
int sum(int num, int t)
{int s = 0, r = 0;for (int i = 1; i <= num; i++) {r = r * 10 + t;s += r;}return s;
}
int main()
{printf("Please input n and a:\n");int n, a;scanf("%d %d", &n, &a);printf("The result is\n%d", sum(n, a));return 0;
}

【10-14】设计一个递归算法将一个整数n转换成字符串。

//10-14 2023年12月30日20点58分-
# include <stdio.h>
# include <malloc.h>
/*char *func(int num)  //非递归做法 
{int tmp = num, k = 0;if (tmp == 0) {k = 1;}while (tmp) {k++;tmp /= 10;}char *ret = (char *)malloc(sizeof(char)*(k+1));
//    char ret[100];ret[k] = '\0';if (num == 0) {ret[0] = '0';}while (num) {ret[k-1] = num % 10 + '0';num /= 10;--k;}return ret;
}*/
//书上代码
void trans(int n)
{int i = n % 10;  //得到整数n的个位数字if (n/10 > 0)trans(n/10);  //递归调用trans，将高位数转换为字符串printf("%c", i + '0'); 
} 
int main()
{int n;printf("Please input a integer:\n");scanf("%d", &n);
//    printf("The result is\n%s", func(n));printf("The result is\n");trans(n);return 0;
}

总结：用递归方法还是不熟练，写不出来。
【10-16】编程实现字符串复制。

//10-16 2023年12月30日21点11分-21点16分 
# include <stdio.h>
void mystrcpy(char *str, char *ret)
{/*int i;for (i = 0; str[i]; i++) {  //逐个字符复制 ret[i] = str[i];}ret[i] = '\0';*/int i = 0;while (str[i]) {*(ret+i) = *(str+i);  //复制字符串 i++;  //指针后移 }ret[i] = '\0';  //目的字符串的末尾要添加字符串结束标志'\0' 
}
int main()
{char s[200], t[200];printf("Please input a string:\n");//scanf("%s", s);gets(s);mystrcpy(s, t);printf("The result is\n%s", t);return 0;
}

【10-17】编写一个函数loopMove(char *str, int n)实现字符串的循环右移功能。
自己有点想不出来诶！
书上分析，每次取字符串尾部一个字符保存到临时变量，然后将字符串前面的所有字符右移一位，然后将临时变量中存放的字符复制到字符串的首部，如此循环n次。

//10-17 2023年12月30日21点19分-21点27分 
# include <stdio.h>
# include <string.h>
void loopMove(char *str, int n)
{int strLength = strlen(str);for (int i = 0; i < n; i++) {char tmp = str[strLength - 1];  //取出字符串的最后一个元素 for (int j = 0; j < strLength - 1; j++) {str[strLength-j-1] = str[strLength-j-2];  //前面的元素后移 }str[0] = tmp;  //将原字符串尾部的元素放在字符串首部 }
}
int main()
{char s[200];printf("Please input a string:\n");gets(s); int n;printf("Please input a integer:\n");scanf("%d", & n);loopMove(s, n);printf("The result is\n%s", s);return 0;
}

【10-18】找出01字符串中0和1连续出现的最大次数。

//10-18 2023年12月30日21点36分- 21点52分
# include <stdio.h>
void getMax(char *str, int *max0, int *max1)
{int cnt_0 = 0, cnt_1 = 0;if (str[0] == '0') {cnt_0++;} else {cnt_1++;}for (int i = 1; str[i]; i++) {if (str[i] == str[i-1]) {if (str[i] == '0') {cnt_0++;} else {cnt_1++;}} else {if (str[i] == '0') {if (cnt_1 > *max1) {*max1 = cnt_1;cnt_1 = 0;}cnt_0++;} else {if (cnt_0 > *max0) {*max0 = cnt_0;cnt_0 = 0;}cnt_1++;}}}if (cnt_1 > *max1) {*max1 = cnt_1;}if (cnt_0 > *max0) {*max0 = cnt_0;}
}
int main()
{char s[200];printf("Please input a string:\n");scanf("%s", s);int max0 = 0, max1 = 0;getMax(s, &max0, &max1);printf("max0 = %d, max1 = %d", max0, max1);return 0;
}

总结：函数中返回两个变量的值，用指针传递。
【10-19】编程计算该数列第20项的值。

//10-19 2023年12月30日21点55分-22点00分 
# include <stdio.h>
/*int func(int num)
{int tmp = 1;for (int i = 2; i <= num; i++) {if (i % 2 == 0) {tmp = tmp * 2 + 1;} else {tmp *= 2;}}return tmp;
}*/
//书上代码
unsigned long func(int num)
{if (num == 1)return 1;if (num % 2 == 0)return 2*func(num-1)+1;elsereturn 2*func(num-1);
} 
int main()
{printf("Please input n:\n");int n;scanf("%d", &n);
//    printf("The result is\n%d", func(n));printf("The result is\n%ld", func(n));return 0;
}

总结：递归函数。还有注意数据的范围。
【10-20】计算这位集邮爱好者集邮总数是多少？以及每册中各有多少邮票？

//10-20 2023年12月30日22点04分-22点07分 
# include <stdio.h>
int main()
{int x;for (int y = 1; y < 7; y++) {if (303*7*10 % (56-10*y) == 0) {x = 303*7*10 / (56-10*y);break;}}printf("x = %d, A = %d, B = %d, C = 303", x, x/5, x-x/5-303);return 0;
}

【10-21】编写递归算法，计算出每个人的年龄。

//10-21 2023年12月30日22点09分-22点14分 
# include <stdio.h>
int func(int num)
{if (num == 1) {  //第一个人10岁 return 10;} else {return 2+func(num-1);  //第n个人的年龄比第n-1人的年龄大2岁 }
}
int main()
{for (int i = 1; i <= 5; i++) {printf("Age %d: %d\n", i, func(i));} return 0;
}

【10-22】

这篇关于《妙趣横生的算法》（C语言实现）-第10章算法设计与数据结构面试题精粹的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/555228。

相关文章

C语言中联合体union的使用

C语言中联合体union的使用

本文编辑整理自： http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=179471 一、前言 “联合体”(union）与“结构体”(struct)有一些相似之处。但两者有本质上的不同。在结构体中,各成员有各自的内存空间, 一个结构变量的总长度是各成员长度之和。而在“联合”中,各成员共享一段内存空间, 一个联合变量
阅读更多...
C++对象布局及多态实现探索之内存布局（整理的很多链接）

C++对象布局及多态实现探索之内存布局（整理的很多链接）

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
Java面试题：通过实例说明内连接、左外连接和右外连接的区别

Java面试题：通过实例说明内连接、左外连接和右外连接的区别

在 SQL 中，连接（JOIN）用于在多个表之间组合行。最常用的连接类型是内连接（INNER JOIN）、左外连接（LEFT OUTER JOIN）和右外连接（RIGHT OUTER JOIN）。它们的主要区别在于它们如何处理表之间的匹配和不匹配行。下面是每种连接的详细说明和示例。 表示例 假设有两个表：Customers 和 Orders。 Customers CustomerIDCus
阅读更多...
在线装修管理系统的设计

在线装修管理系统的设计

管理员账户功能包括：系统首页，个人中心，管理员管理，装修队管理，用户管理，装修管理，基础数据管理，论坛管理 前台账户功能包括：系统首页，个人中心，公告信息，论坛，装修，装修队 开发系统：Windows 架构模式：B/S JDK版本：Java JDK1.8 开发工具：IDEA(推荐) 数据库版本： mysql5.7 数据库可视化工具： navicat 服务器：SpringBoot自带 ap
阅读更多...
大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs），基本上是经过强化训练的 n-gram 模型，它们在网络规模的语言语料库（实际上，可以说是我们文明的知识库）上进行了训练，展现出了一种超乎预期的语言行为，引发了我们的广泛关注。从训练和操作的角度来看，LLMs 可以被认为是一种巨大的、非真实的记忆库，相当于为我们所有人提供了一个外部的系统 1（见图 1）。然而，它们表面上的多功能性让许多研究者好奇，这些模型是否也能在通常需要系
阅读更多...
通过SSH隧道实现通过远程服务器上外网

通过SSH隧道实现通过远程服务器上外网

搭建隧道 autossh -M 0 -f -D 1080 -C -N user1@remotehost##验证隧道是否生效，查看1080端口是否启动netstat -tuln | grep 1080## 测试ssh 隧道是否生效curl -x socks5h://127.0.0.1:1080 -I http://www.github.com 将autossh 设置为服务，隧道开机启动
阅读更多...
时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测 目录 时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测基本介绍程序设计参考资料 基本介绍 MATLAB实现LSTM时间序列未来多步预测-递归预测。LSTM是一种含有LSTM区块（blocks）或其他的一种类神经网络，文献或其他资料中LSTM区块可能被描述成智能网络单元，因为
阅读更多...
vue项目集成CanvasEditor实现Word在线编辑器

vue项目集成CanvasEditor实现Word在线编辑器

CanvasEditor实现Word在线编辑器 官网文档：https://hufe.club/canvas-editor-docs/guide/schema.html 源码地址：https://github.com/Hufe921/canvas-editor 前提声明： 由于CanvasEditor目前不支持vue、react 等框架开箱即用版，所以需要我们去Git下载源码，拿到其中两个主
阅读更多...
DDei在线设计器-API-DDeiSheet

DDei在线设计器-API-DDeiSheet

DDeiSheet   DDeiSheet是代表一个页签，一个页签含有一个DDeiStage用于显示图形。   DDeiSheet实例包含了一个页签的所有数据，在获取后可以通过它访问其他内容。DDeiFile中的sheets属性记录了当前文件的页签列表。   一个DDeiFile实例至少包含一个DDeiSheet实例。   本篇最后提供的示例可以在DDei文档直接预览 属性 属性名说明数
阅读更多...
代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2