С динамической вектор структуры

Question

Я имею следующую структуру для динамического вектора:

typedef struct { 
    TElement *data; 
    int len; 
}Vector; 

А 2 функции, один для инициализации вектора, а другой, чтобы добавить элемент:

Vector *initVector() 
{ 
    Vector *v; 
    v = malloc(sizeof(TElement)); 
    v->len = 0; 
    return v; 
} 
void append(Vector *v, TElement element) 
{ 
    v = (Vector *)realloc(v, (v->len + 1) * sizeof(TElement)); 
    v->data[v->len++] = element; 
} 

Когда я пытаюсь добавить элемент, программа падает, и я не знаю, почему, какие-либо идеи?

Answer 1

• В функции initVector(), выделяют sizeof(Vector) вместо sizeof(TElement)
• В функции append, изменять v->data вместо v и удалить ненужный и вредный бросок.

исправленный код:

Vector *initVector() 
{ 
    Vector *v; 
    v = malloc(sizeof(*v)); 
    v->len = 0; 
    return v; 
} 
void append(Vector *v, TElement element) 
{ 
    v->data = realloc(v->data, (v->len + 1) * sizeof(TElement)); 
    v->data[v->len++] = element; 
} 

Answer 2

В коде v имеет тип Vector *, и вы выделения памяти от размера TElement, что неправильно.

Изменить

v = malloc(sizeof(TElement)); 

в

v = malloc(sizeof*v); 

Это говорит,

• Всегда проверяйте для успеха malloc(), проверив возвращаемый указатель против NULL, чтобы избежать любого возможного UB, в случае отказа malloc().

• p = realloc(p,...) стиль очень плохой, потому что в случае, если realloc() не удался, вы тоже потеряете фактический указатель. Поместите возвращаемое значение realloc() во временный указатель, сверните с NULL для успеха и затем верните исходный указатель.

Answer 3

В вашем initVector вам необходимо зарезервировать место для одного Vector. Кроме того, вы должны установить v->data на NULL или действительный выделенный указатель, иначе ваш код будет иметь неопределенное поведение.

Vector *initVector() { 
    Vector *v; 
    v = malloc(sizeof Vector); 
    if (! v) { 
     /* error: malloc failed */ 
    } 
    v->data = 0; 
    v->len = 0; 
    return v; 
} 

В append вы должны быть изменения размера площади, на которую указывает data, а не Vector само распределение:

void append(Vector *v, TElement element) { 
    TElement *new_p = realloc(v->data, (v->len + 1) * sizeof(TElement)); 

    if (!new_p) { 
     /* error: malloc failed */ 
    } 
    v->data = new_p; 
    v->data[v->len++] = element; 
} 

Это также является очень хорошей идеей, чтобы проверить возвращаемое значение malloc; если нет, то имеет смысл прервать его после печати разумного сообщения, а не сбой с непонятным SIGSEGV.

---

Кроме того, растет вектор один элемент времени означает, что вставка элемент будет иметь O (N) временную сложность на контейнере с n элементов. Предпочтительнее выделять пространство в геометрических прогрессиях (например, когда вам нужно изменить размер распределения, затем распределите выделение в 1,5 или 2 раза, а не на постоянную сумму) и начните с некоторого большего минимального выделения 8 или 16 предметов.

Answer 4

Что вам нужно следующее

Vector *initVector() 
{ 
    Vector *v = malloc(sizeof(Vector)); 
           ^^^^^^ 
    if (v != NULL) 
    { 
     v->len = 0; 
     v->data = NULL; 
     ^^^^^^^^^^^^^^^ 
    } 

    return v; 
} 

void append(Vector *v, TElement element) 
{ 
    TElement *tmp = realloc(v->data, (v->len + 1) * sizeof(TElement)); 
          ^^^^^^^^  
    if (tmp != NULL) 
    { 
     v->data = tmp; 
     v->data[len++] = element; 
    } 
} 

Тип возврата последней функции может быть изменено с void к int, чтобы сообщить, был ли добавляется новый элемент. Например,

int append(Vector *v, TElement element) 
{ 
    int success; 

    TElement *tmp = realloc(v->data, (v->len + 1) * sizeof(TElement)); 
          ^^^^^^^^  
    if ((success = tmp != NULL)) 
    { 
     v->data = tmp; 
     v->data[len++] = element; 
    } 

    return success; 
}