Как передать строку в связанный список вместо массива символов в C?

Question

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

Answer 1

Вы можете использовать связанный список, но более обычный подход состоит в том, чтобы выделить блок памяти с malloc() и динамически изменить размер этого блока с realloc(), если пользовательский ввод превышает границы массива.

void * malloc (размер size_t);

Функция malloc() выделяет размер байтов памяти и возвращает указатель на выделенную память.

void * realloc (void * ptr, size_t size);

Функция realloc() пытается изменить размер выделения, на который указывает ptr , и возвращает ptr . Если недостаточно места для увеличения выделения памяти, на которое указывают ptr , realloc() создает новое распределение, копирует столько старых данных, на которые указывает ptr , сколько будет соответствовать новому выделению, освобождает старое выделение и возвращает указатель на выделенную память. Если ptr равно NULL, realloc() идентично вызову malloc() для размера байтов. Если size равен нулю и ptr не равно NULL, выделяется новый объект минимального размера и исходный объект освобождается.

Answer 2

Вы можете сделать это в связанном списке, но связанный список символов обычно будет крайне неэффективной структурой данных - каждый узел будет иметь один символ и (как минимум) один указатель. В типичном случае вы смотрите 4 или 8 байтов для указателя и один для символа, поэтому вы накладываете лот накладных расходов.

Моя непосредственная рекомендация - разместить как минимум 16 символов в каждом узле в вашем связанном списке, чтобы сохранить издержки как минимум разумными. Конечно, динамический массив обычно будет еще лучше, но, по крайней мере, это предотвратит неразумность связанного списка 1008 *.

Answer 3

Вы можете либо:

1. вычислить длину строки, которая потребуется (например, подсчет количества символов до появления новой строки), затем выделить динамический массив с помощью malloc (), для этого требуется два прохода над входной строкой, ИЛИ
2. если невозможно предварительно рассчитать, какой длины должен быть массив, то вы можете malloc () фиксировать количество массива, читать его пользователем, а затем realloc (), если выделенный размер недостаточно велик. Для этого требуется n-проход, где n - число созданных realloc ().

Answer 4

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

char* storedString;

void storeString(char* inputString)
{
  char* s = storedString; // temporary handler
  while(++s = ++inputString); // copy string
}

int main(int argc, char** argv)
{
  storeString("hello");
  // you can now treat storedString as if it was an array of chars
  // containing: 'h'+'e'+'l'+'l'+'o'+'\0'
}