Двумерный динамический массив: с каждым шагом создаётся дополнительная ячейка

Gudsaf

Здравствуйте!Сегодня пред мной стала интересная задача. У нас есть строка (вводится пользователем). Идёт парс строки, выделяется нужное и отправляется в массив. Массив нужен динамический. Структура массива:
[0;symbol1]
[0;symbol2]
........
[0;symboln]
Как вы поняли symbol1, symbol2...symboln - те самые символы которые приходят после парсинга строки.Мне нужна только часть кода с инициализацией массивом. По-возможности, если вы захотели сделать добро и помочь, опишите в комментариях как можно подробнее. И да -нормальные переменные, а не в одну букву.с меня плюшка
13 ответов

Gudsaf

#define MAXSIZE_STB 100
#define MAXZISE_STRING 1000
...
char buffer[MAXSIZE_STB][MAXSIZE_STRING];
         scanf("%s", buffer[0]);
Динамический не значит безмерный. Наличие контроля за размерами входного буфера позволит избежать ряд ошибок и путаниц. А работать с блоками, размеры блоков задаем при инициализации массива, удобно и комфортно.


Gudsaf

ой горе.. если ты у меня попросишь спеть песню, я в ответ на твоё пожелание буду танцевать со стулом. (на спасибку я жмот, ибо ответ не "в туда")


Gudsaf

Постановка задачи неполная. Я не телепат. Гадать на кофейной гуще не собираюсь. p.s. а свои отзывы и прочее оставь себе, не за этим я на этом форуме. dixi


Gudsaf

Постановка задачи неполная
Перечитал, не спорю (дописал ниже). Суть задачи такая:
Динамически создавать элементы массива под приходящий последующий символ ( symbol(n) ). Если символ не пришёл, то и создавать ничего не надо
п.с. теперь тоже буду всем новичкам кидать в ответ Dixi


Gudsaf

Динамически создавать элементы массива под приходящий последующий символ ( symbol(n) ).
Если пришел символ и размер строки достиг размера выделенной памяти, то выделяешь дополнительную память функцией realloc, в противном случае - не выделяешь.При этом предлагаю следующую структуру программы.Массив символов:
char *array = NULL;
Указатель array инициализируется NULL, чтобы realloc вел себя как malloc при первом вызове.Текущий (сколько сейчас символов в массиве) и максимальный (под сколько символов выделено памяти) размер массива:
size_t actual_size, max_size;
Ты читаешь строку, проводишь парсинг. При этом при каждом выделенном символе проверяешь, не достигнут ли максимальный размер массива:
if(actual_size == max_size)
Если максимальный размер массива достигнут, то ты вычисляешь новый размер массива и выделяешь дополнительную память:
if(actual_size == max_size)
{
    max_size = calculate_extra_size(max_size);
    array = realloc(array, max_size * sizeof *array); /* Важно: при ошибке realloc потеряется array.
                                                       * Если это критично, то нужно присваивать результат realloc
                                                       * вспомогательной переменной
                                                       */
}
То, как ты будешь вычислять (calculate_extra_size) новый размер массива, зависит от тебя. Можно увеличивать старый размер на единицу (тогда вызовы realloc) будут происходить чаще, можно увеличивать его в два раза или на какую-нибудь константу, можно придумать что-нибудь посложнее.


Gudsaf

Если максимальный размер массива достигнут, то ты вычисляешь новый размер массива и выделяешь дополнительную память:
if(actual_size == max_size)
{
    max_size = calculate_extra_size(max_size);
    array = realloc(array, max_size * sizeof *array); 
}
Не пойму на самом деле эту конструкцию. Вот мои вопросы: по ней
  • Правильно ли то, что написано далее: у нас есть исходный массив array у которого уже есть несколько ячеек (зачем тогда иначе введена переменная actual_size ?), потом мы в него машинно (при условии что конечная ячейка массива уже занята) дописываем новые ячейки, так?
  • Почему бы вообще не создавать массив так сказать с нуля? То есть если выполнится условие, то начинается создание первой ячейки динамического массива, выполнится ещё раз условие создастся следующая ячейка и т.д.
  • Можно ли вообще обойтись без условия if(actual_size == max_size)?
Вот смотрите кусок моего кода (собственно пишу калькулятор):
....
//объявили указатель(?правильно?) tempstring
//записываем массив чисел
    while (string[position] != '\0') //перебираем строку
    {       
        while (string[position]>= '0' && string[position]<= '9')//берём чисто циры
        {
            /*1-создаём вспомогательную динамическую строку tempstring
            *записываем символ в tempstring если он проходит через while*/  
        }   
        while (!(string[position]>= '0' && string[position]<= '9'))
            break;
    }
    //2-сформированную строку tempstring переводим в число через atof()
    //3-это число записываем в второй динамический двумерный массив digits...
    //типа [1;числоА][1;числоБ][1;числоВ]...[1;числоN]
....
Теперь, по шагам. ПРОВЕРЬТЕ, пожалуйста и если есть возможность дополните 1-создаём вспомогательную динамическую строку tempstring и пишем подходящий символ перед while ввожу
char *tempstring = NULL;
переписываю ваш код под своё условие
....
while (string[position]>= '0' && string[position]<= '9')//берём чисто циры
    {
    int position_tstr = 0;   //счётчик для tempstring
    *tempstring = (char*) (realloc(tempstring, sizeof(char) + (sizeof *tempstring)));
    tempstring[position_tstr++] = string[position];
    }
....
2-сформированную строку tempstring переводим в число через atof()
....
number = atof (tempstring);
....
3-это число записываем в второй динамический двумерный массив digits (я так-то и первый динамический вроде не правильно написал а вот со вторым так тут вообще караул) так же вводим указатель где-то над while
int **digits = NULL;
дописываем в код:
....
            break;
    }
    //2-сформированную строку tempstring переводим в число через atof()
    number = atof (tempstring);
    //3-это число записываем в второй динамический двумерный массив digits...   
    //типа [1;числоА][1;числоБ][1;числоВ]...[1;числоN]
    /******************************
    ******************************
    *****ВОТ ТУТ КРИК О ПОМОЩИ!****
    ******************************/
....


Gudsaf

Правильно ли то, что написано далее: у нас есть исходный массив array у которого уже есть несколько ячеек (зачем тогда иначе введена переменная actual_size ?), потом мы в него машинно (при условии что конечная ячейка массива уже занята) дописываем новые ячейки, так?
Первоначально у нас в массиве ничего нет (но это в данном случае не важно). Необходимость в двух различных переменных actual_size и max_size возникает потому, что я предлагаю расширять массив не на один элемент, а сразу на несколько. Допустим, сначала мы выделили память под 10 элементов, ввели эти десять элементов, поняли, что место закончилось, выделили память еще под 10 элементов (расширили исходный массив), и т.д.При этом минимизируется число вызовов realloc, что в общем-то хорошо. На самом деле realloc теоретически может сам оптимизировать выделение памяти, но на это надеяться нельзя (в стандарте это не прописано). В принципе, ты можешь выделять память и по одному элементу, дело твое. При этом действительно необходимость в дополнительной переменной отпадает.
Почему бы вообще не создавать массив так сказать с нуля? То есть если выполнится условие, то начинается создание первой ячейки динамического массива, выполнится ещё раз условие создастся следующая ячейка и т.д.
См. выше.
Можно ли вообще обойтись без условия if(actual_size == max_size)?
Да, если ты будешь выделять память по одному элементу. См. выше.
ПРОВЕРЬТЕ, пожалуйста и если есть возможность дополните
Память для tempstring выделяется неправильно: при каждом вызове realloc выделяется два байта, т.е. массив по сути не расширяется. Оператор sizeof возвращает размер памяти в байтах, которую занимает значение типа его аргумента. sizeof(char) возвратит 1, т.к. размер char равен 1 байту. sizeof *tempstring тоже возвратит единицу, т.к. у выражения *tempstring значение имеет тип char, а размер char равен 1 байту. Также не вижу необходимости при считывании отдельного числа в переменную tempstring выделять память под отдельную цифру. Можно сразу вычислить длину строки, которая будет представлять число, и выделить память под нее один раз.Вот небольшой пример, демонстрирующий то, что я говорю. Программа читает строки из стандартного потока ввода до тех пор, пока не встретит символ EOT (чтобы его ввести, нужно нажать Ctrl+D на UNIX-системах, либо Ctrl-Z и Enter в Windows), и выводит эти строки в обратном порядке:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* Функция mystrdup возвращает динамическую строку,
 * являющуюся копией своего аргумента, или NULL, если
 * не удалось выделить память.
 * Это буквальная реализация функции strdup, которая не является
 * стандартной, но доступна в POSIX-системах.
 */
char *mystrdup(const char *str)
{
    char *result = malloc(strlen(str) + 1);
    if(result != NULL)
        strcpy(result, str);
    return result;
}
 
int main(void)
{
    char **lines = NULL;        /* Массив строк */
    size_t actual_size = 0;     /* Количество введенных строк */
    size_t max_size = 0;        /* Количество строк, под которые
                                 * выделена память */
    size_t i = 0;               /* Вспомогательная переменная для
                                 * подсчета размера новой памяти */
    char buf[BUFSIZ];           /* Вспомогательный буфер */
 
    size_t alloc_count = 0;     /* Количество операций выделения памяти */
 
    int ret = EXIT_FAILURE;     /* Код возврата программы */
    
    puts("Enter lines (Press Ctrl+D on Linux, Ctrl+Z on Windows to stop):");
        
    /* fgets возвращает NULL при конце ввода или ошибке */
    while(fgets(buf, BUFSIZ, stdin) != NULL)
    {
        char *nl;
        
        /* Проверка, нужно ли выделять еще память */
        if(actual_size == max_size)
        {
            char **tmp;            
            /* Вычисляем новый размер */
            max_size = 1 << ++i; /* Это выражение каждый раз  будет
                                  * возвращать вдвое большее значение 
                                  * (степени двойки с натуральными показателями) */
 
            /* Выделяем память */
            tmp = realloc(lines, max_size * sizeof *lines);
 
            /* Если не удалось выделить память */
            if(tmp == NULL)
            {
                perror("realloc");
                goto handle_error;
            }
 
            lines = tmp;
            ++alloc_count;
        }
 
        /* Копируем введенную строку */
        lines[actual_size] = mystrdup(buf);
 
        /* Ошибка создания динамической копии строки */
        if(lines[actual_size] == NULL)
        {
            perror("mystrdup");
            goto handle_error;
        }
 
        /* Убираем из строки символ перевода строки,
         * если он там есть */
        if((nl = strchr(lines[actual_size], '\n')) != NULL)
            *nl = '\0';
        
        ++actual_size;
    }
 
    if(ferror(stdin))
    {
        perror("stdin");
        goto handle_error;
    }
 
    if(actual_size != 0)
        puts("The lines reversed:");
    
    /* Ошибок не было, печатаем результаты */
    for(i = 0; i < actual_size; ++i)
        printf("%s\n", lines[actual_size - i - 1]);
 
    printf("Lines total: %d; the number of allocations: %d\n",
           (int) actual_size, (int) alloc_count);
    
    ret = EXIT_SUCCESS;
    
handle_error:
    for(i = 0; i < actual_size; ++i)
        free(lines[i]);
    free(lines);
    
    exit(ret);
}
В данном примере размер выделяемой памяти в массиве каждый раз увеличивается вдвое, начиная с двух элементов: 2 элемента, 4 элемента, 8 элементов и т.д.Пример ввода:
User@intel ~/samples/c
$ ./sample
Enter lines (Press Ctrl+D on Linux, Ctrl+Z on Windows to stop):
first line
second line
fourth line
fifth line
sixth line
seventh line
last line
The lines reversed:
last line
seventh line
sixth line
fifth line
fourth line
second line
first line
Lines total: 8; the number of allocations: 3
 
User@intel ~/samples/c
$
собственно пишу калькулятор
Калькулятор арифметических выражений? У меня такое ощущение, что ты делаешь что-то не так.


Gudsaf

Калькулятор арифметических выражений? У меня такое ощущение, что ты делаешь что-то не так.
Да, калькулятор.. мне хоть как-нибудь бы написать! А теперь к делу. Вчера сам дописал всё же блок для получения числа с использованием tempstring. Итак на выходе имеем число: n. Теперь задача состоит в другом: необходимо для каждого нового числа n создавать строку в двумерном массиве. Особенности этого массива -состоит из подмассивов размером в две ячейки -первая ячейка подмассива всегда равна единичке, вторая равна пришедшему из блока числу. -каждая следующая строка (строка это и есть сам подмассив) массива создаётся, если приходит число из блока.То есть, если у нас из блока пришло число n1, то создаётся первая строка массива по шаблону [1;n1] и так далее пока не перестанут приходить числа из блока.Если из блока пришло три числа - n1, n2, n3 двумерный массив будет выглядеть так: [1;n1] [1;n2] [1;n3] Если пришло четыре числа, то ещё добавится [1;n4]Вот такое дело мне ещё нужно провернуть, постараюсь сам, но не откажусь от помощи!


Gudsaf

Вот такое дело мне ещё нужно провернуть, постараюсь сам, но не откажусь от помощи!
Это вообще не проблема. Но мне непонятно, зачем для задачи калькулятора создавать массив с такой структурой:
-состоит из подмассивов размером в две ячейки -первая ячейка подмассива всегда равна единичке, вторая равна пришедшему из блока числу. -каждая следующая строка (строка это и есть сам подмассив) массива создаётся, если приходит число из блока.
и что ты дальше будешь с этим массивом делать. Зачем вообще нужны эти единички? Можешь вкратце описать алгоритм, по которому ты собираешься реализовывать калькулятор?


Gudsaf

Это вообще не проблема .... Можешь вкратце описать алгоритм, по которому ты собираешься реализовывать калькулятор?
Ну не знаю, для кого как...Алгоритм такой: часть 1 -получаем строку -выделяем из строки числа -записываем числа в массив чисел типа [1;число] - выделяем из строки операции -записываем операции в массив операций типа [1;операция] часть 2 -начинаем поочерёдно считывать операции из массива операций -находим операцию с высшим рангом -запоминаем её позицию -относительно это позиции идём в массив чисел (Необходимо пояснить: если операция стояла на третьем месте, то соответственно, числа которые в строке стояли около неё имеют третью и четвёртую позицию) -считываем два числа соотв этой операции -производим операцию над числами -записываем результат Обратно в массив чисел, (Необходимо пояснить: если числа стояли на 3 и 4 месте, то результат пишется на 3 место) -меняем 1 на 0 у того числа которое посчитали (Соответственно У четвёртого места значение меняем на 0 вместо 1) - у операции так же ставим 0 - enjoyчто-то не создаётся на каждый шаг новая строчка...
int k = 0, i = 0 ,number=0;
    int *(*mass) = NULL;
    int size = (sizeof(int));
    while (-10 < k )
    {
        mass = (int**) realloc(mass, (sizeof(mass)) + 2 * size);
        for(i;i<20;i++)
        {
            mass[i]=(int*)realloc(mass[i],2 * size);
            mass[i][0]=1;
            mass[i][1]=number;
        }
        k++;
    }


Gudsaf

Алгоритм такой:
Сразу скажу: этим алгоритмом не получится корректно обрабатывать ошибки грамматики. Приоритеты операций будут обрабатываться очень неэффективно.Обычно такая задача решается методом рекурсивного спуска (тут можно почитать) либо через трансляцию в выражение в постфиксной нотации (которое уже вычисляется достаточно просто, см. пример).


Gudsaf

Сразу скажу: этим алгоритмом не получится корректно обрабатывать ошибки грамматики. Приоритеты операций будут обрабатываться очень неэффективно.Обычно такая задача решается методом рекурсивного спуска (тут можно почитать) либо через трансляцию в выражение в постфиксной нотации (которое уже вычисляется достаточно просто, см. пример).
Метод рекурсивного спуска не понятно описан... Думаю над польской записью, но опять же скажу честно, читая кернигана и ритчи не смог её нормально понять. Потому и сунулся делать массивы с флагами, которые были забракованы.Эх успеть бы до воскресенья написать!