登陆不了建设银行网站/大型营销型网站制作
【笔试题目】
给定一个字符串,实现如下函数接口,删除其首部和尾部连续的空格。(注:夹在非空格字符之间的空格是合法的,不用删除。)
char* delete_leading_trailing_whitespaces(char *output, const char *input);
【测试样例】
编号 | 情况 | 输入 | 输出 |
---|---|---|---|
1 | 空字符串 | “” | NULL |
2 | 空格字符串 | " " | NULL |
3 | 首尾无空格 | “Hello World” | “Hello World” |
4 | 首部有空格 | " Hello World" | “Hello World” |
5 | 尾部有空格 | "Hello World " | “Hello World” |
6 | 首尾有空格 | " Hello World " | “Hello World” |
【方法一】状态标记法
【基本思路】找到output的头(start)和尾(end)在input中的指针位置,然后把start到end的所有字符拷贝到output中。
此外,在遍历处理input的过程中,维护一个状态变量state,用于标记当前处理状态是否处于空格字符串状态,其定义如下:
enum {STATE_OUT, /* 值为0,表示当前状态处于非空格字符串状态 */STATE_IN, /* 值为1,表示当前状态处于空格字符串状态 */} state;
1、找出output的头
我们知道,通过下面这个循环,可以跳过字符串首部的空格。当跳出循环时,指针指向input的第一个非空格字符。
while (*input == ' '){input++;}
如果该非空格字符是尾零’\0’,那么表明input是空格字符串,此时output应该返回NULL;
if (*input == '\0){output = NULL;return output;}
否则,该非空格字符就是output的首个字符。此时,设置状态变量state为STATE_OUT状态,表示当前指针处于非空格状态,并且记录下当前指针位置start。
2、循环处理剩余的部分。
当指针指向空格字符时,标记当前状态为STATE_IN状态,表示当前指针处于连续的空格状态;
当指针指向非空格状态时,状态变更为STAT_OUT状态,表示当前指针处于非连续的空格状态。
{//TODO:添加相关图片解释
}
此外,状态每次由STATE_OUT转为STATE_IN时,都需要记录当时STATE_IN状态的指针位置end,表示从该位置开始后面可能一直是空格;
而状态每次由STATE_IN转为STATE_OUT状态时,需把end指针重置为NULL,表示之前的连续空格串不是input尾部的。
4、尾部空格串的判断
随着指针位置逐步地偏移,最终到达尾零'\0'。那么怎么判断input尾部是否存在连续的空格呢?
如果此时state为STATE_IN,那就是存在的。而记录下的end指针就是output的结尾,将其赋值为'\0'就可以得出output。
5、求出output
copy区间[start,end)的字符到output中。
【测试样例4和6过程分析】
【方法二】
【基本思路】首先,从input的头部循环偏移到第一个非空格字符,找到output的start位置;同理,从input的尾部循环偏移到第一个非空格字符,找到output的end位置;最后,copy区间[start,end]的字符到output中。
【实现代码】
【方法一】
char* delete_leading_trailing_whitespaces(char *output, const chat*input)
{// 定义状态变量stateenum {STATE_OUT,STATE_IN,} state = STATE_OUT;// 定义output的start和end指针char *start = NULL, *end = NULL;// 传入参数input和output检查if (!input || !output)return NULL;// 跳过input首部的连续空格while (*input == ' ')input++;// input为空格字符串if (*input == '\0')return NULL;// 记录startstart = const_cast<char*>(input++);// 处理input剩余的部分while (*input != '\0'){if ((*input == ' ')){if (state == STATE_OUT){state = STATE_IN;end = const_cast<char*>(input);}}else{end = NULL;state = STATE_OUT;}input++;}if (state == STATE_IN){printf("has trailing spaces\n");}else{end = const_cast<char*>(input);}// copy从start到end的字符for (start; start < end; start++){*output = *start;output++;}*output++ = '\0';return output;
}
【方法二】
char* delete_leading_trailing_whitespaces(char *output, const chat*input)
{// 定义output的start和end指针char *start = input, *end = input;// 传入参数input和output检查if (!input || !output)return NULL;// 跳过input首部的连续空格while (*input == ' ')input++;// input为空格字符串if (*input == '\0')return NULL;// 记录startstart = input;// 反向处理找endwhile (*end != '\0')end++;end--;while (*end == ' ')end--;// copy从start到end的字符for (start; start <= end; start++){*output = *start;output++;}*output++ = '\0';return output;
}
【测试代码】
#include <stdio.h>
#include <stdlib.h>int main(int argc, char* argv[])
{if (argc != 2){fpritnf(stderr, "Usage: %s string\n", argv[0]);return 1;}char *output = (char*)malloc(32);delete_leading_trailing_whitespaces(output, argv[1]);printf("output = [%s]", output);return 0;
}