重複した文字を再帰的に削除する

Question

私は、指定された文字列からすべての重複する文字を再帰的に削除する再帰関数を作成しようとしています。 たとえば、 "Hello world" - > "Helo wrd"などです。私が持っている

制限はありません：許可

1. ませループ。
2. 元の関数（remove_duplicates）に引数を追加することはできません。
3. string.hのライブラリの関数は使用できませんが、再帰的に書き込むことはできます。

もう1つの補助的な再帰関数を使用することができます。

私がこれまでに書いた関数は、短い文字列に対してしか機能しません。関数を何度も呼び出します。それをより効率的にする方法は？あなたは結果の文字列を格納するグローバル変数を使用できる場合

void remove_duplicates3(char string[], int index)//(str,RecursiveStrlen(str, 0)-1) 
{ 
    int length = RecursiveStrlen(string + 1, 0); 
    if (string[index] == '\0' || index == 0) 
    { 
     return; 
    } 

    if (string[0] != string[index]) 
    { 
     remove_duplicates3(string, index - 1); 
    } 
    else 
    { 
     BackspaceString(string, index); 
     remove_duplicates3(string, length - 1); 
    } 

    remove_duplicates3(string + 1, length - 1); 
} 

int RecursiveStrlen(char str[], int index) 
{ 
    if (str[index] == '\0') 
     return index; 
    return RecursiveStrlen(str, index + 1); 
} 


void BackspaceString(char string[],int index)//deletes one char from string in a specific index 
{ 
    if (string[index] == '\0')//end of string 
     return; 
    string[index] = string[index + 1]; 
    BackspaceString(string, index + 1); 
} 

Answer 1

ピュア再帰的なソリューション：

void remove_char(char string[], char c, int read_index, int write_index) { 
    if (string[read_index] == 0) { 
     string[write_index] = 0; 
     return; 
    } 
    if (c == string[read_index]) { 
     remove_char(string, c, read_index + 1, write_index); 
    } else { 
     string[write_index] = string[read_index]; 
     remove_char(string, c, read_index + 1, write_index + 1); 
    } 
} 

void remove_duplicates(char string[], int index) { 
    if (string[index] != 0 && string[index + 1] != 0) { 
     remove_char(string, string[index], index + 1, index + 1); 
     remove_duplicates(string, index + 1); 
    } 
} 

Answer 2

、あなたはこれを行うことができます：

char result[30]=""; 
char over[30]=""; 


int check(char *over, char c) 
{ 
    if(*over != '\0') 
    { 
     if(*over == c) 
     { 
      return 1; //exists 
     } 
     else 
     { 
      return check(over+1, c); 
     } 
    } 
    return 0; //doesn't exist 
} 

int strLen(char *str) 
{ 
    if(*str=='\0') 
    { 
     return 0; 
    } 
    return strLen(str+1)+1; 
} 

void remove_duplicates(char *str) 
{ 
    if(*str != '\0') 
    { 
     if(check(over, *str)==0) 
     { 
      int len=strLen(result); 
      result[len++]=*str; 
      result[len]='\0'; 

      len=strLen(over); 
      over[len++]=*str; 
      over[len]='\0'; 
     } 
     remove_duplicates(str+1); 
    } 
} 

結果の文字列がresultとoverに保存されているが、既に遭遇格納する文字列です。文字を文字列として返します。 overにが見つからなかった場合は、check()関数によって文字cと照合して0を返します。

check()は、overの値をチェックして、その引数cがoverに存在するかどうかを判断します。

remove_duplicates()は、入力文字列strの各文字をチェックします。文字がstrに以前に遭遇しなかった場合は、すでに遭遇した文字のリストにoverと追加され、result文字列に追加されます。

これは入力文字列strが終了するまで続きます。

Answer 3

あなたの文字列はASCII文字のみを持っている場合 -

int arr[256] = {0}; 

/* 
* str - Input string 
* presult - Pointer to the buffer contain result 
*/ 
void remove_duplicates(char *str, char *presult) 
{ 
    if(*str != '\0') 
    { 
     if(arr[*str] == 0) 
     { 
      *presult = *str; 
      arr[*str] = 1; 
      remove_duplicates(str+1, presult+1); 
     } 
     remove_duplicates(str+1, presult); 
    } 
}