代码之家 › 专栏 › 技术社区 › Zacky112

从字符串中删除重复字符的C程序

Zacky112 · 技术社区 · 15 年前

我遇到了一个面试问题,要求将重复的字符从给定的字符串中删除。因此,如果输入为“hi there”,则预期输出为“hi ter”。它还被告知只考虑字母代表和所有字母是小写。我想出了以下程序。我有话要讲清楚我的逻辑。但是这个程序并不能像预期的那样工作。如果输入为“hii”,则正常工作,但如果输入为“hi there”,则失败。请帮忙。

#include <stdio.h>
int main() 
{
    char str[] = "programming is really cool"; // original string.
    char hash[26] = {0}; // hash table.
    int i,j; // loop counter.
// iterate through the input string char by char.
for(i=0,j=0;str[i];)
{
    // if the char is not hashed.
    if(!hash[str[i] - 'a'])
    {
        // hash it.
        hash[str[i] - 'a'] = 1;
        // copy the char at index i to index j.
        str[j++] = str[i++];
    }
    else
    {
        // move to next char of the original string.
        // do not increment j, so that later we can over-write the repeated char.
        i++;
    }
}

// add a null char.
str[j] = 0;

// print it.
printf("%s\n",str); // "progamin s ely c" expected.

return 0;

}

7 回复 | 直到 15 年前

codaddict 15 年前

什么时候? str[i] 是非字母表,比如空格,当你这样做时:

hash[str[i] - 'a']

你的计划可能会失败。

ASCII值 space 是 32 而那 a 是 97 因此,您可以使用负索引有效地访问数组哈希。

要解决此问题,可以通过执行以下操作忽略非字母:

if(! isalpha(str[i]) {
    str[j++] = str[i++]; // copy the char.
    continue;  // ignore rest of the loop.
}

Paul R 15 年前

这将在任何空格字符(或超出范围“a”..'z)上中断,因为您的访问超出了哈希数组的界限。

jim 15 年前

void striprepeatedchars(char *str)
{
    int seen[UCHAR_MAX + 1];
    char *c, *n;

    memset(seen, 0, sizeof(seen));

    c = n = str;
    while (*n != '\0') {
        if (!isalpha(*n) || !seen[(unsigned char) *n]) {
            *c = *n;
            seen[(unsigned char) *n]++;
            c++;
        }
        n++;
    }
    *c = '\0';
}

finnw 15 年前

这是代码高尔夫,对吧?

d(s){char*i=s,*o=s;for(;*i;++i)!memchr(s,*i,o-s)?*o++=*i:0;*o=0;}

tur1ng 15 年前

…

// iterate through the input string char by char.
for(i=0,j=0;str[i];)
{
  if (str[i] == ' ')
  {
    str[j++] = str[i++];
    continue;
  }

    // if the char is not hashed.
    if(!hash[str[i] - 'a'])
    {

…

Vijay Mathew Chor-ming Lung 15 年前

#include <stdio.h>
#include <string.h>

int hash[26] = {0};

static int in_valid_range (char c);
static int get_hash_code (char c);

static char * 
remove_repeated_char (char *s)
{
  size_t len = strlen (s);
  size_t i, j = 0;
  for (i = 0; i < len; ++i)
    {
      if (in_valid_range (s[i]))
    {
      int h = get_hash_code (s[i]);
      if (!hash[h])
        {
          s[j++] = s[i];
          hash[h] = 1;
        }
    }
      else
    {
      s[j++] = s[i];
    }
    }
  s[j] = 0;
  return s;
}

int
main (int argc, char **argv)
{
  printf ("%s\n", remove_repeated_char (argv[1]));
  return 0;
}

static int 
in_valid_range (char c)
{
  return (c >= 'a' && c <= 'z');
}

static int 
get_hash_code (char c)
{
  return (int) (c - 'a');
}

Phil Wallach 15 年前

char *s;
int i = 0;

for (i = 0; s[i]; i++)
{
    int j;
    int gap = 0;
    for (j = i + 1; s[j]; j++)
    {
        if (gap > 0)
            s[j] = s[j + gap];
        if (!s[j])
            break;
        while (s[i] == s[j])
        {
            s[j] = s[j + gap + 1];
            gap++;
        }
    }
}