当前位置：首页 > news >正文

单词倒排——c语言解法

news 来源：原创 2024/5/9 13:03:16

题目链接:单词倒排__牛客网 (nowcoder.com)

以下是题目：

这个题中有三个点，一个是将非字母的字符转换为空格，第二是如果有两个连续的空格，那么就可以将这两个连续的空格变成一个空格。第三个点就是让单词倒排。

那么我们就可以将这三个点分别封装成三个函数。

还有就是，三个函数执行顺序的问题。这里需要想到连续的空格变成一个空格函数应该是放在非字符字符变成空格之后的。然后单词倒排放在最后可以完成操作。

接下来实现函数：

空格转换

首先先实现空格转换的函数。
//空格转换
void TranSpace(char* pw)//字符指针。
{char* ptr = pw;while (*ptr != '\0'){if (!isalpha(*ptr))//isalpha函数是判定一个字符是否属于字母。{*ptr = ' ';}ptr++;}
}
这里的形参是传过来的字符串的首地址，然后函数内容是对整个字符串进行遍历，只要不是字母，那么这个字符就会变成空格。

减少空格

接下来实现空格的减少。

这个实现的方式有点类似于strstr的实现方式（strstr函数实现方式忘记可以重新复习：字符串函数的模拟实现-CSDN博客），只要指针指向了空格，这个指针不要动，作为记忆保存点，然后重新创建一个指针往下遍历，直到碰到不是空格的字符就停下来。然后将中间的空格全部被后面的字符覆盖。

实现过程：

代码如下

//单空格转换
void SingleSpace(char* pw)
{char* prev = pw;char* cur = pw;char* end = pw;while (*end != '\0'){end++;}end--;//让end指针指向字符串的末尾置。while (*cur != '\0')//遍历整个字符串。{if (*cur == ' ') //只要cur指针指向空格就令prev指向现在的位置保存记忆， 然后cur开始往下遍历找空格{prev = cur;while (*cur == ' ') {cur++;}while (cur - 1 > prev)//对空格进行覆盖 {char* tail = cur;while (tail <= end){*(tail - 1) = *tail;tail++;}*end = '\0';end--;cur--;}}prev = cur;cur++;}
}

单词倒排

单词倒排有一种神奇的方式，如下图：

第一步是将各个单词分别进行倒置，第二步是将整个字符串倒置，然后单词就倒排了。代码如下：

//置换字符串
void TransWord(char* pw)
{char* head = pw;char* tail = pw;char* back = tail;while (*back != '\0') //每个单词分别倒置。{head = back;tail = back;while (*tail != ' ' && *tail != '\0'){tail++;}back = tail;back++;tail--;while (head < tail){char tmp = *head;*head = *tail;*tail = tmp;head++;tail--;}}head = pw;tail = pw;while (*tail != '\0') {tail++;}tail--;//；令tail指向字符串尾部。while (head < tail) //字符串逆置{char tmp = *tail;*tail = *head;*head = tmp;head++;tail--;}}