在C语言中实现可调整大小数组(向量或ArrayList)

Question

我在C中实现了一个非常简单的可调整大小的整数数组，只包括在各种索引中添加和删除元素的功能。

我还没有看过使用空指针来处理任何类型的数据。我主要想知道我的代码结构是否还好，包括外部API细节的头文件和隐藏实现细节的源文件。

vector.h

#ifndef VECTOR_H
#define VECTOR_H

typedef struct vector_struct* Vector;

extern Vector vector_create();
extern void vector_destroy(Vector vector);
extern void vector_add(Vector vector, int* element);
extern void vector_add_index(Vector vector, int* element, int index);
extern void vector_remove(Vector vector, int index);
extern void vector_pop(Vector vector);
extern void vector_print(Vector vector);

#endif

vector.c文件：

#include "vector.h"
#include <stdlib.h>
#include <stdio.h>

struct vector_struct {
  int capacity;
  int number_of_elements;
  int* elements;
};

/*
Private function to allocate memory for vector creation
*/
static void* get_memory(size_t size) {
  void* memory;
  if ((memory = malloc(size)) == NULL) {
    exit(EXIT_FAILURE);
  }
  return memory;
}

/*
Private function to resize the amount of memory allocated for the given vector
*/
static void resize_vector(Vector vector, size_t size) {
  if ((vector->elements = realloc(vector->elements, size)) == NULL) {
    exit(EXIT_FAILURE);
  }
  vector->capacity = size / sizeof(int);
}

/*
Create and initialize a vector for use
*/
extern Vector vector_create() {
  Vector vector = get_memory(sizeof(Vector));

  vector->capacity = 10;
  vector->number_of_elements = 0;
  vector->elements = get_memory(sizeof(int) * 10);

  return vector;
}

/*
Free memory allocated for vector
*/
extern void vector_destroy(Vector vector) {
  free(vector->elements);
  free(vector);
}

/*
Add given element to the end of the vector
*/
extern void vector_add(Vector vector, int* element) {
  if (vector->number_of_elements+1 > vector->capacity) {
    resize_vector(vector, (vector->capacity * 2) * sizeof(int));
  }

  vector->elements[vector->number_of_elements] = *element;
  vector->number_of_elements++;
}

/*
Add given element at the given index in the vector
*/
extern void vector_add_index(Vector vector, int* element, int index) {
  if (index < 0 || index >= vector->number_of_elements) {
    exit(EXIT_FAILURE);
  }

  if (vector->number_of_elements+1 > vector->capacity) {
    resize_vector(vector, (vector->capacity * 2) * sizeof(int));
  }

  for(int i=vector->number_of_elements; i>index; i--) {
    vector->elements[i] = vector->elements[i-1];
  }

  vector->elements[index] = *element;
  vector->number_of_elements++;
}

/*
Removes element at given index, shifting all elements after that index
to the left once in order to fill in the empty index 
*/
extern void vector_remove(Vector vector, int index) {
  if (index < 0 || index >= vector->number_of_elements) {
    exit(EXIT_FAILURE);
  }

  for(int i=index; i<vector->number_of_elements-1; i++) {
    vector->elements[i] = vector->elements[i+1];
  }
  vector->number_of_elements--;

  if (vector->number_of_elements < (vector->capacity / 2)) {
    resize_vector(vector, (vector->capacity / 2) * sizeof(int));
  }
}

/*
Removes the last element in the vector
*/
extern void vector_pop(Vector vector) {
  if (vector->number_of_elements < 1) {
    exit(EXIT_FAILURE);
  }

  vector->number_of_elements--;
}

/*
Prints the vector's contents
*/
extern void vector_print(Vector vector) {
  printf("Capacity of vector: %d\nContents:\n", vector->capacity);
  printf("[");
  for (int i=0; i<vector->number_of_elements; i++) {
    printf((i == vector->number_of_elements-1) ? " %d " : " %d,", vector->elements[i]);
  }
  printf("]\n");
}

Answer 1

• 请勿typedef指针。
• exit对一个糟糕的指数有点太苛刻了。考虑返回一个成功/失败指示。
• vector->capacity *= 2和vector->capacity /= 2体现了重新分配策略。这种政策分散在许多功能上是不对的。我建议将它合并到一个函数中(resize_vector是一个很好的候选函数)，并以所需的新大小无条件地调用它。
• number_of_elements不向客户端公开。这意味着客户端不能遍历向量元素，这严重限制了数组的实用程序。或者公开它，或者提供一个映射接口，按照ty对联f (*op)(int，void *)；.map(向量向量，op，int，void *)；( void *参数，用于在op调用中共享状态)。