strcmp()但是在A-Z之后，0-9呢？(C/C++)

Question

对于我完全不同意的原因，但是“反可用性的力量”继续尽管有我的反对而颁布命令，我有一个排序程序，它使用基本的strcmp（）比较按名称排序。它很好用；很难弄错。然而，在最后一刻，他们决定以数字开头的条目应该出现在以字母开头的条目之后，与ASCII排序相反。他们引用EBCDIC标准，称数字跟在字母后面，因此之前的假设并不是普遍真理，而我无法赢得这个争论的权力...但我离题了。

我的问题就在这里。我已经用一个新的函数调用nonstd_strcmp替换了所有适当的strcmp引用，并现在需要实施修改以完成排序更改。我使用了FreeBSD源作为我的基础：http://freebsd.active-venture.com/FreeBSD-srctree/newsrc/libkern/strncmp.c.html。

 if (n == 0)
  return (0);
 do {
  if (*s1 != *s2++)
   return (*(const unsigned char *)s1 -
    *(const unsigned char *)(s2 - 1));
  if (*s1++ == 0)
   break;
 } while (--n != 0);
 return (0);

我想我可能需要花些时间来仔细思考应该如何完成，但我相信我不是唯一一个经历过在发布前突然更改规格而感到脑袋一片空白的人。

- Aaron Burke

---

这个问题中蕴含的仇恨之多让我感到有趣。 - Michael Mrozek

这个问题为什么要加个C++标签？ - sbi

你有关于大写字母和小写字母的指示吗？（EBCDIC和ASCII在这方面也有所不同）顺便说一句，你的程序的目的是让其他人完成任务，ASCII顺序并没有什么神圣不可侵犯的地方。你唯一合理的抱怨是在发布前的要求更改。 - David Thornley

我不确定这与C++“绝对没有任何关系”；毕竟这是有效的C++语法。许多人在C++中处理C风格的字符串。我认为这个问题不应该被投票否决。提问者认为他的老板很傻，他可能是对的，没什么大不了的。 - BobbyShaftoe

关于 C++ 标签 - 该项目是混合的 C/C++ 代码。两者都可以接受。唯一的限制是要避免使用动态内存。注意：所有输入均为 A-Z 0-9，不存在小写字符。 - Aaron Burke

Answer 1

你需要做的是为每个字符创建一个排序表。这也是执行不区分大小写比较的最简单方法。

if (order_table[*s1] != order_table[*s2++])

请注意字符可能是带符号的，如果是这种情况，您的表格索引可能会变成负数。此代码仅适用于有符号字符：

int raw_order_table[256];
int * order_table = raw_order_table + 128;
for (int i = -128;  i < 128;  ++i)
    order_table[i] = (i >= '0' && i <= '9') ? i + 256 : toupper(i);

- Mark Ransom

---

好的...这很有道理。这是我需要重新启动大脑的火花！谢谢！ - Aaron Burke

使用int并不意味着表格过大。请注意，此算法仅在 '9' < 'A' 且输入为 [0-9A-Z] 时才需要。因此，您可以存储 (i>='0' && i<='9') ? 26+i : i - 'A'，而表只需要为索引“0”到“Z”分配内存即可。 - MSalters

@MSalters，是的，一个“int”比必要的更大；如果对值小心谨慎，则可以使用“short”甚至“char”。由于“int”被认为是最自然的大小，所以我选择了它。即使该项目将输入限制为[0-9A-Z]，我也不会以这种方式编码，因为我希望它能够在另一个没有这些限制的项目中重复使用。 - Mark Ransom

Answer 2

如果你的老板和其他我遇到的老板一样，你可能想要将其作为一个选项（即使它是隐藏的）：

排序方式： o 字母后面加数字 o 数字后面加字母

甚至更糟糕的是，他们可能会发现他们希望数字按数字顺序排序（例如，“A123”在“A15”之后），那么可以是：

o 字母后面加数字 o 数字后面加字母 o 智能数字在字母后面 o 字母在智能数字后面

这涉及到诊断真正的问题，而不是症状。我敢打赌，他们可能在最后一刻改变主意。

- franji1

---

智能数字被称为“自然排序”。http://www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html - Mark Ransom

不经意的双关语，我猜你是想说“预期”或者是“反感”吗？ - MSalters

哦，我毫不怀疑那就是会发生的事情。听起来你说话的口吻中蕴含着许多从挫折中学到的教训，Franji1！ - Aaron Burke

@Aaron - 是啊，如果他们不能做出决定，你说“让用户选择怎么样？”然后在最后一刻，在59分30秒完成它，那你会看起来像个英雄 :-D - franji1

Answer 3

你可以使用查找表来将ASCII转换为EBCDIC，以便在比较字符时使用 ;-）

- progrmr

---

他的东西是ASCII而不是EBCDIC，但查找表通常会更快，并且在他们决定重新排序其他字符时更容易修改。+1 - EvilTeach

+1：虽然将其转换为EBCDIC可能没有意义，但查找表几乎肯定是正确的方法。 - Jerry Coffin

他确实说过EBCDIC在字母后面有数字。但是任何将数字放在字母后面的查找表都可以使用。 - progrmr

Answer 4

在这种特殊情况下，只有大写字母（如评论中提到的）和数字0-9，您还可以省略顺序表，而是将两个不同的字符都乘以4，并将结果模256进行比较。 ASCII数字的范围（48至57）不会溢出8位（57×4 = 228），但大写字母的范围（65至90）会溢出（65×4 = 260）。当我们将乘法值模256进行比较时，每个字母的值都小于任何数字的值：90×4％256 = 104 < 192 = 48×4

代码可能如下所示：

int my_strcmp (const char *s1, const char *s2) {
    for (; *s1 == *s2 && *s1; ++s1, ++s2);
    return (((*(const unsigned char *)s1) * 4) & 0xFF) - \
           (((*(const unsigned char *)s2) * 4) & 0xFF);
}

当然，订单表格解决方案通常更加灵活，因为它允许为每个字符定义排序顺序 - 这种解决方案仅适用于大写字母与数字之间的特殊情况。（但例如在微控制器平台上，即使是保存表格使用的少量内存也可以带来实际的好处。）

- Arkku

---

非常聪明的解决方案，Arkku！实际上，这是在一个嵌入式系统上（虽然我们的内存并不紧张）。我使用了你的实现，它似乎通过了初始测试。我还添加了一个 strncmp 等效函数，唯一的更改是 for (; *s1 == *s2 && *s1 && n; ++s1, ++s2, --n); if( !n ) return n; - Aaron Burke

Answer 5

虽然我基本上同意以上的回答，但是我认为在循环的每次迭代中进行查找是愚蠢的，除非你认为大多数比较将具有不同的第一个字符，否则你可以改为

char c1, c2;
while((c1 = *(s1++)) == (c2 = *(s2++)) && c1 != '\0');
return order_table[c1] - order_table[c2];

此外，我建议使用静态初始化程序构建order_table，这将提高速度（无需每次或永远生成）并且也可能提高可读性。

- Jared Pochtar

---

这是一个不错的、聪明的优化，但你需要确保在正确的时间进行指针增量 - 给出的示例将不会比较字符串的第一个字符（如果一个或两个字符串恰好为空，则会偏离字符串的末尾）。 - Michael Burr

如果order_table中两个不同的字符可以具有相同的值（例如，不区分大小写的排序），则在某些情况下，这也不能正确工作。 - Arkku

@Michael 哇，你发现得真好，我完全没注意到（我真是太蠢了）。无论如何我已经进行了编辑，现在应该没问题了。@Arkku：OP指定大小写敏感的搜索（或者说不需要大小写不敏感），所以我认为没有理由让order_table具有多个字符共享相同的排序值。 - Jared Pochtar

我知道，我只是为了其他可能正在查看这个解决方案的人的利益而提到它。=） - Arkku

Answer 6

这里是一个相当不错的字符串比较实现，类似于其他帖子所描述的实现。

static const unsigned char char_remap_table[256] = /* values */

#define char_remap(c) (char_remap_table[(unsigned char) c])

int nonstd_strcmp(const char * restrict A, const char * restrict B) {
     while (1) {
          char a = *A++;
          char b = *B++;
          int x = char_remap(a) - char_remap(b);
          if (x) {
               return x;
          }
          /* Still using null termination, so test that from the original char,
           * but if \0 maps to \0 or you want to use a different end of string
           * then you could use the remapped version, which would probably work
           * a little better b/c the compiler wouldn't have to keep the original
           * var a around. */
          if (!a) { /* You already know b == a here, so only one test is needed */
               return x;  /* x is already 0 and returning it allows the compiler to
                           * store it in the register that it would store function
                           * return values in without doing any extra moves. */
          }
     }
}

除此之外，您可以将该函数概括为一个接受char_remap_table作为参数的函数，这样如果您需要稍后使用不同的映射，就可以轻松实现。

int nonstd_strcmp(const char * restrict a, const char * restrict b, const char * restrict map);

- nategoose