Как выполнить упражнение K&R 2–4?

Я учусь писать программы на C, используя книгу k & r (Язык программирования C), и у меня возникла проблема с одним из упражнений. Он просит меня обнаружить и удалить символ в строке s1, который соответствует любым символам в строке s2.

Итак, скажем s1 = "A";

И s2 = "AABAACAADAAE"

Я хочу вернуть "BCDE"

Я знаю, что нахожусь на правильном пути к этому, просто я не очень хорошо умею разрабатывать программы, не могли бы вы дать мне какие-нибудь дополнительные советы. Я попытался прочитать об алгоритме двоичного дерева поиска, но мне показалось, что он слишком сложен для этой повседневной задачи.

Всем спасибо!

/* An alternate version of squeeze(s1, s2) that deletes each character in
 * s1 that matches any character in the string s2
 *
 * [email protected]
 */

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

void squeeze(char s[], char t[]);

char string[] = "BAD";
char sstring[] = "ABC";

int
main(void)
{
    squeeze(string, sstring);
    return 0;
}

void
squeeze(char s[], char t[])
{
    int i, j, d;

    d = 0;
    if(strstr(s, t) == NULL)
        printf("%c", s[i]);
    s[j] = '\0';
}

c string kernighan-and-ritchie
person Community    schedule 07.01.2009    source источник
comment
Слишком локализован, но мы закрываем другой вопрос как дубликат этого. Ребята, не будьте близки-счастливы. И посетители из другого Q, пожалуйста, проголосуйте, чтобы снова открыть здесь.   -  person Potatoswatter    schedule 22.07.2013

Ответы (5)


arrow_upward
3
arrow_downward

Отличная книга. На вашем месте я бы поступил точно так же, как для squeeze () в разделе 2.8, но вместо прямого сравнения (s [i]! = C) я бы написал и использовал функцию

 int contains(char s[], int c)

который возвращает 1, если строка s содержит c, в противном случае - 0. Начните с простого подхода; когда это сработает, вы можете повысить производительность с помощью более сложных решений (двоичный поиск, но обратите внимание, что проблема не требует, чтобы символы в s2 располагались в определенном порядке).

person Federico A. Ramponi    schedule 07.01.2009
comment
Кроме того, я не думаю, что двоичный поиск стоит того. Ведь возможных символов всего 255 ... - person Federico A. Ramponi; 07.01.2009

arrow_upward
2
arrow_downward

Бинарный поиск для этого - излишество. Вам нужно три индекса. Один указатель (i) для обхода s, один указатель (k) для обхода t и один указатель (j) для отслеживания того, где вы находитесь в s для символов, которые вам нужно сохранить, потому что их нет в t. Итак, для каждого символа в s проверьте, находится ли он в t. Если это не так, сохраните его в s.

void squeeze(char *s, char *t) {
    int i, j, k;
    int found = 0;

    for(i = j = 0; s[i] != '\0'; i++) {
        found = 0;
        for(k = 0; t[k] != '\0' && (found == 0); k++) {
            if(t[k] == s[i]) {
                found = 1;
            }
        }

        if(found == 0) {
            s[j++] = s[i];
        }

    }

    s[j] = '\0';
}
person jason    schedule 07.01.2009

arrow_upward
0
arrow_downward

Для выполнения этой работы вам не нужен сложный двоичный поиск. Что вам нужно, так это двойной цикл for, который проверяет наличие каждого символа в одной строке в другой и копирует неиспользуемые символы в третий массив символов (что является вашим результатом).

Код может быть примерно таким (не тестировался!):

char *s1, *s2, *result; /* original strings and the result string */
int len1, len2; /* lengths of the strings */
for (i = 0; i < len1; i++) {
   for (j = 0; j < len2; j++) {
     if (s1[i] == s2[j]) {
       break;
     }
   }
   if (j == len2) {  /* s1[i] is not found in s2 */
     *result = s1[i]; 
     result++; /* assuming your result array is long enough */
   }
}
person PolyThinker    schedule 07.01.2009

arrow_upward
-1
arrow_downward

это моя функция:

void squeeze(char s1[],char s2[])
{
int i,j,p;
int found;

p=0;
for(i=0;s1[i]!='\0';i++)
{
    for(j=0;s2[j]!='\0';j++)
        if(s1[i]==s2[j])
            found=YES;
        else
            found=NO;
    if(found==NO)
        s1[p++]=s1[i];
     }
    s1[p]='\0';
}
person mr_sudo    schedule 16.06.2014

arrow_upward

arrow_downward

person    schedule
comment
он написан так же, как squeeze () в разделе 2.8 с небольшими изменениями - person tavisha06; 28.11.2013