Проблема копирования массивов в последовательности Look-and-say

Question

Я пытаюсь выполнить последовательность «Посмотри и скажи» ( wiki ), и я застрял.

Я считаю строки массивом символов.Сначала я иду через массив line с for и нахожу «границы / различия» (в 1211: 1 | 2 | 11) и отмечаю их в массиве int diff как позиции.Затем я вычисляю count и нахожу, какое число находится внутри границ, и записываю его в новый массив line_new.Затем мне нужно скопировать новый массив line_new в старый line, и вот, я думаю, проблема в этом.

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

Ожидаемый результат:

1
11
21
1211
111221
312211

Фактические результаты:

1
11
21
1211 \\line_new
12 \\line

Код:

#include<stdio.h>
#include <string.h>
#define length(x)  (sizeof(x) / sizeof((x)[0]))

void spocitej(int n){

    int count = 1;
    char line[] = {"21"};
    char line_new[] = {" "};
    int diff[] = {0};

    char num;

    int len, len_d;
    int i, j, k, l, X, m;

    printf("1\n");
    printf("11\n");
    printf("21\n");

    for(i = 4; i < n; i++){

        j = 0;
        len = strlen(line)-1;

        for(i = 0; i < len; i++){
        if(line[i] != line[i+1]){
                diff[j] = i;
                j++;
            }
       }

       len_d = length(diff);
       l = 0;


       for(k = 0; k < len_d; k++){

            if(k == 0){
                count = diff[k]+1;
                num = line[0];
                line_new[l] = count+'0';
                line_new[l+1] = num;
                l = l+2;
            }else if(k!=0 && k!=len_d-1){
                count = diff[k]-diff[k-1];
                line_new[l] = count+'0';
                line_new[l+1] = line[diff[k]];
                l = l+2;
            }

            if(k == len_d-1){
                count = (len - diff[k]);
                num = line[len];
                line_new[l] = count+'0';
                line_new[l+1] = num;
                line_new[l+2] = '\0';
            }
          }

        puts(line_new);

//        strcpy(line, line_new);
        strncpy(line, line_new, sizeof(line_new));


        puts(line);

        printf("\n");
    }
}




int main()
{
    int n = 5;
    spocitej(n);

    fflush(stdin);
    getchar();

    return 0;
}

Answer 1

На основе строки 21 следующая генерируемая строка - 1211.Чтобы сохранить эту строку в памяти компьютера, вам нужно 4 байта для видимых символов, плюс 1 байт для завершающего символа NUL '\0'.

В вашем текущем коде вы резервируете массив фиксированной длины, имеяпробел для 1 видимого символа плюс завершающий '\0'.Этого недостаточно.

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

К сожалению, C не предлагает никакой структуры данных, такой как StringBuffer или StringBuilder, поэтому вы должны сделать это самостоятельно.Основным компонентом является функция malloc, которая выделяет вам память.Безопасной ставкой было бы сказать:

char *line_new = malloc(2 * strlen(line) + 1);

Это дает вам достаточно места.Если вам больше не нужно это пространство, вы должны позвонить free(line_new), иначе ваша программа быстро израсходует всю память вашего компьютера.

Answer 2

Размер вашего массива, вероятно, не тот, который вы ожидаете

• line содержит 3 символа (инициализируются с помощью '2', '1' и '\ 0')
• line_new содержит только 2 символа (инициализируется с помощью '' и '\ 0')
• diff содержит только 1 int (инициализируется с помощью 0), массив бесполезен и может быть int diff;

Таким образом, length(diff) всегда равен 1, тот факт, что вы помещаете его в цикл, вероятно, означает, что вы предполагаете, что он меняется, но это не так.

Когда вы заполняете line_newВы не всегда ставите нулевой символ-терминатор, так что puts(line_new); может продолжаться вне массива до тех пор, пока не найдет '\ 0', это ненадлежащее поведение

Если n представляетдля максимального количества цифр, которые вы вычисляете, вам нужен массив n + 1 символов, а не только 3 и 2. Но я не уверен насчет цели n , потому что вы ожидаете 111221 с n = 5

---

Предложение, первый аргумент которого - первая цифра, а второй - число циклов:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char ** argv)
{
  if (argc != 3)
    return -1;

  int f = atoi(argv[1]); /* the first digit */
  int n = atoi(argv[2]); /* the number of turn */

  if ((f < 1) || (f > 9) || (n < 1))
    return -1;

  /* grow in length is like 30% per generation */
  size_t maxsz = (int) pow(1.4, n+1) + 1;

  /* the two arrays and their used size */
  char * arr1 = malloc(maxsz);
  char * arr2 = malloc(maxsz);
  size_t sz1, sz2;

  /* starting with 1 time first digit */
  arr1[0] = f;
  sz1 = 1;

  while (n--) {
    size_t i;

    for (i = 0; i != sz1; ++i)
      printf("%d", arr1[i]);
    putchar('\n');

    /* add a final not possible 10 to not have a special case for the last digit */
    arr1[sz1] = 10;
    sz2 = 0;
    i = 1;

    /* counts */
    do {
      arr2[sz2] = 1;
      while (arr1[i] == arr1[i-1]) {
        arr2[sz2] += 1;
        i += 1;
      }
      arr2[sz2 + 1] = arr1[i-1];
      sz2 += 2;
    } while (++i <= sz1);

    /* exchange role between arr1 and arr2 to avoid to copy arr2 into arr1 */
    char * arr = arr1;

    arr1 = arr2;
    arr2 = arr;
    sz1 = sz2;
  }

  free(arr1);
  free(arr2);
  return 0;
}

Компиляция и выполнение:

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -g cc.c -lm
pi@raspberrypi:/tmp $ ./a.out 1 1
1
pi@raspberrypi:/tmp $ ./a.out 1 2
1
11
pi@raspberrypi:/tmp $ ./a.out 1 3
1
11
21
pi@raspberrypi:/tmp $ ./a.out 1 4
1
11
21
1211
pi@raspberrypi:/tmp $ ./a.out 1 5
1
11
21
1211
111221
pi@raspberrypi:/tmp $ ./a.out 1 6
1
11
21
1211
111221
312211
pi@raspberrypi:/tmp $ ./a.out 1 10
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
pi@raspberrypi:/tmp $ ./a.out 3 10
3
13
1113
3113
132113
1113122113
311311222113
13211321322113
1113122113121113222113
31131122211311123113322113

Выполнение под valgrind

pi@raspberrypi:/tmp $ valgrind ./a.out 1 20
==5026== Memcheck, a memory error detector
==5026== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5026== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5026== Command: ./a.out 1 20
==5026== 
1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211
11131221133112132113212221
3113112221232112111312211312113211
1321132132111213122112311311222113111221131221
11131221131211131231121113112221121321132132211331222113112211
311311222113111231131112132112311321322112111312211312111322212311322113212221
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211
==5026== 
==5026== HEAP SUMMARY:
==5026==     in use at exit: 0 bytes in 0 blocks
==5026==   total heap usage: 3 allocs, 3 frees, 3,368 bytes allocated
==5026== 
==5026== All heap blocks were freed -- no leaks are possible
==5026== 
==5026== For counts of detected and suppressed errors, rerun with: -v
==5026== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)