【C语言算法刷题】第10题
题目描述
主管期望你来实现英文输入法单词联想功能。
需求如下：
- 依据用户输入的单词前缀，从已输入的英文语句中联想出用户想输入的单词，按字典序输出联想到的单词序列，
- 如果联想不到，请输出用户输入的单词前缀。
注意：
- 英文单词联想时，区分大小写
- 缩略形式如”don’t”，判定为两个单词，”don”和”t”
- 输出的单词序列，不能有重复单词，且只能是英文单词，不能有标点符号
输入描述
输入为两行。
首行输入一段由英文单词word和标点符号组成的语句字符串str；
接下来一行为一个英文单词前缀pre。
输出描述
输出符合要求的单词序列或单词前缀，存在多个单词符合要求时，以空格分割
【示例1】
输入：
The furthest distance in the world, Is not between life and death, But when I stand in front of you, Yet you don't know that I love you.
f输出：
front furthest解释：
从用户已输入英文语句”The furthestdistance in the world,
Is not between life and death,
But when I stand in frontof you,
Yet you dont know that I love you.”中提炼出的所有单词中，
符合“f”作为前缀的有“furthest”和“front”，
按字典序排序并在单词间添加空格后输出，
结果为“front furthest”。题目解析
从字符串 str 中提取单词，并将这些单词存入一个二维数组 words[][] 中。具体步骤如下:
- 循环遍历字符串：使用
while循环，直到遇到字符串结束符\0。 - 字母复制：如果当前字符是字母（大写或小写），则将其复制到临时数组
tmp中，并增加tmp_size。 - 处理分隔符：如果遇到空格或逗号：
- 使用一个
for循环遍历已经存储的单词words，检查当前的tmp是否已经存在。 - 如果
tmp中的单词在words中不存在（即j等于words_size），则将tmp复制到words中，并增加words_size。
- 使用一个
- 重置临时数组：通过
memset将tmp清空，以便为下一个单词做准备，同时将tmp_size重置为零。 - 继续遍历：增加
i，继续读取下一个字符。
下面这段代码实现了从输入字符串中提取单词，排除重复的单词并存入数组words[][]。
while(str[i]!='\0'){
/*首先将语句中的字母全部复制到数组tmp[]*/
if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')){
tmp[tmp_size++]=str[i];
}else{/*当遇到空格或逗号时，分支逻辑进入else*/
int j=0;
for(;j<words_size;j++){
if(strcmp(words[j],tmp)==0){
break;
}
}/*for*/
if(j==words_size){
strcpy(words[words_size++],tmp);
/*将单词们存入一个二维数组words[]*/
}/*if*/
/*每一个单词进行重置清空*/
memset(tmp,'\0',21);
tmp_size=0;
}/*else*/
i++;
}/*while*/下面是代码的后半段，用于实现前缀pre与已经预处理好的words[][]数组的比对，并将答案存入res
int len=strlen(pre);/*len是前缀pre的长度*/
/*res[][]用来存储对比成功的答案，(可能有多个单词*/
char res[MAX_WORDS_LEN][MAX_WORD_LEN]={'\0'};
int res_size=0;
for(int j=0;j<words_size;j++){
if(strncmp(words[j],pre,len)==0){
strcpy(res[res_size++],words[j]);
}
}
if(res_size==0){
printf("%s\n",pre);/*对比失败，直接输出前缀*/
}else{
/*qsort 是标准库中提供的一个快速排序函数*/
qsort(res,res_size,sizeof(res[0]),cmp);
for(int k=0;k<res_size;k++){
printf("%s",res[k]);
}
}/*else*/
return 0;
}
完整C语言代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_WORDS_LEN 10001
#define MAX_WORD_LEN 21
int main(){
/*输入语句str*/
char str[MAX_WORDS_LEN];
gets(str);
/*输入前缀pre*/
char pre[MAX_WORD_LEN];
gets(pre);
/*定义一个二维的字符型数组word并初始化*/
char words[MAX_WORDS_LEN][MAX_WORD_LEN]={'\0'};
int words_size=0;
char tmp[MAX_WORD_LEN]={'\0'};
int tmp_size=0;
int i=0;
while(str[i]!='\0'){
/*首先将语句中的字母全部复制到数组tmp[]*/
if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')){
tmp[tmp_size++]=str[i];
}else{/*当遇到空格或逗号时，分支逻辑进入else*/
int j=0;
for(;j<words_size;j++){
if(strcmp(words[j],tmp)==0){
break;
}
}/*for*/
if(j==words_size){
strcpy(words[words_size++],tmp);
/*将单词们存入一个二维数组words[]*/
}/*if*/
/*每一个单词进行重置清空*/
memset(tmp,'\0',21);
tmp_size=0;
}/*else*/
i++;
}/*while*/
if(tmp_size!=0){
strcpy(words[words_size++],tmp);
}
int len=strlen(pre);/*len是前缀pre的长度*/
/*res[][]用来存储对比成功的答案，(可能有多个单词*/
char res[MAX_WORDS_LEN][MAX_WORD_LEN]={'\0'};
int res_size=0;
for(int j=0;j<words_size;j++){
if(strncmp(words[j],pre,len)==0){
strcpy(res[res_size++],words[j]);
}
}
if(res_size==0){
printf("%s\n",pre);/*对比失败，直接输出前缀*/
}else{
/*qsort 是标准库中提供的一个快速排序函数*/
qsort(res,res_size,sizeof(res[0]),cmp);
for(int k=0;k<res_size;k++){
printf("%s",res[k]);
}
}/*else*/
return 0;
}
字符串补充知识
1.strcmp()函数
2.strncmp()函数
strncmp() 是 C 语言中的一个字符串比较函数，定义在 <string.h> 头文件中。它的作用是比较两个字符串的前 n 个字符。
3.gets()与puts()函数
