文章同步發(fā)布于掘金。

0. 引言

在C語言中，數(shù)組的長度是固定不變的。它不像C++那樣有動態(tài)大小數(shù)組的vector。所以在平時的工作中，我們也會實現(xiàn)C語言版的動態(tài)數(shù)組。今天看到一個C語言實現(xiàn)的動態(tài)數(shù)組CLIST。在這里記錄一下。

1. CLIST整體介紹

首先，我們來看一下頭文件clist.h。首先是實現(xiàn)動態(tài)數(shù)組的數(shù)據(jù)結構Clist:

typedef struct CList
{
  void  (* add)        (struct CList *l, void *o);            /* Add object to the end of a list */
  void  (* insert)     (struct CList *l, void *o, int n);     /* Insert object at position 'n' */
  void  (* replace)    (struct CList *l, void *o, int n);     /* Replace object at position 'n' */
  void  (* remove)     (struct CList *l, int n);              /* Remove object at position 'n' */
  void* (* at)         (struct CList *l, int n);              /* Get object at position 'n' */
  int   (* realloc)    (struct CList *l, int n);              /* Reallocate list to 'size' items */
  int   (* firstIndex) (struct CList *l, void *o);            /* Get first index of the object */
  int   (* lastIndex)  (struct CList *l, void *o);            /* Get last index of the object */
  int   (* count)      (struct CList *l);                     /* Get list size */
  void  (* clear)      (struct CList *l);                     /* Clear list */
  void  (* free)       (struct CList *l);                     /* Destroy struct CList and all data */
  void  (* print)      (struct CList *l, int n, const char *type);  /* Print list data */
  void *priv;          /* NOT FOR USE, private data */
} CList;

這里，開發(fā)作者將動態(tài)數(shù)組的一些常見功能以函數(shù)指針的方式，都放到了結構體Clist了，作為Clist的成員。作為C語言的開發(fā)人員，我還是在平時的開發(fā)中，很少遇見這樣的方式的。這樣寫應該是為了C++的同學考慮的吧。這些函數(shù)的具體功能，在后面一一分析。最后還有一個指針成員priv，這個其實才是實現(xiàn)動態(tài)數(shù)組的數(shù)據(jù)結構，這里為了不具體的對用戶暴露，所以寫成了一個萬能指針，具體的數(shù)據(jù)結構在.c中實現(xiàn)。

其次，Clist.h中還有一個函數(shù)聲明:

CList *CList_Init(size_t objSize); /* Set list object size in bytes */

這個是初始化Clist的，入?yún)⑹菍ο蟮拇笮?，然后返回值是Clist類型的指針。

接下來我們來看一下clist.c文件。

2. Clist私有數(shù)據(jù)

Clist的動態(tài)數(shù)組，就一個以下數(shù)據(jù)結構:

typedef struct
{  
  int count;          /* Number of items in the list. */  
  int alloc_size;     /* Allocated size in quantity of items */  
  size_t item_size;   /* Size of each item in bytes. */  
  void *items;        /* Pointer to the list */  
} CList_priv_;

這里, count是當前數(shù)組中的元素個數(shù); alloc_size是當前數(shù)組最大的個數(shù)，也就是數(shù)組的容量, 當count == alloc_size時，數(shù)組就會動態(tài)擴容。item_size是每個對象的大小。items就是存儲具體數(shù)據(jù)的數(shù)組了。

3. 初始化動態(tài)數(shù)組: CList_Init

CList *CList_Init(size_t objSize)
{
  CList *lst = malloc(sizeof(CList));
  CList_priv_ *p = malloc(sizeof(CList_priv_));
  if (!lst || !p) {
    fprintf(stderr, "CList: ERROR! Can not allocate CList!\n");
    return NULL;
  }
  p->count = 0;
  p->alloc_size = 0;
  p->item_size = objSize;
  p->items = NULL;
  lst->add = &CList_Add_;
  lst->insert = &CList_Insert_;
  lst->replace = &CList_Replace_;
  lst->remove = &CList_Remove_;
  lst->at = &CList_At_;
  lst->realloc = &CList_Realloc_; 
  lst->firstIndex = &CList_FirstIndex_;
  lst->lastIndex = &CList_LastIndex_;
  lst->count = &CList_Count_;
  lst->clear = &CList_Clear_;
  lst->free = &CList_Free_;
  lst->print = &CList_print_;
  lst->priv = p;
  return lst;
}

這個沒啥好說的，函數(shù)的功能就是初始化數(shù)據(jù)結構CList。

4. 在動態(tài)數(shù)組末尾添加元素:CList_Add_

void CList_Add_(CList *l, void *o)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  if (p->count == p->alloc_size && 
        CList_Realloc_(l, p->alloc_size * 2) == 0)
    return;
  
  char *data = (char*)p->items;
  data = data + p->count * p->item_size;
  memcpy(data, o, p->item_size);
  p->count++;
}

這里首先判斷一下，是否需要動態(tài)擴容: 如果當前數(shù)組的個數(shù)count等于當前數(shù)組的容量alloc_size，則調(diào)用CList_Realloc_函數(shù)，為數(shù)組擴容，擴容后，數(shù)組的容量是當前容量的2倍。然后，通過指針的偏移，找到數(shù)組的最后，將對象拷貝到數(shù)組中，并更新當前數(shù)組個數(shù)。

5. 在數(shù)組索引為n的位置插入元素: CList_Insert_

void CList_Insert_(CList *l, void *o, int n)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  if (n < 0 || n > p->count) {
    fprintf(stderr, "CList: ERROR! Insert position outside range - %d; n - %d.\n",  p->count, n);
    assert(n >= 0 && n <= p->count);
    return;
  }

  if (p->count == p->alloc_size && 
      CList_Realloc_(l, p->alloc_size * 2) == 0)
    return;

  size_t step = p->item_size;
  char *data = (char*) p->items + n * step;
  memmove(data + step, data, (p->count - n) * step);
  memcpy(data, o, step);
  p->count++;
}

CList_Insert_首先也是判斷是否需要擴容。然后，通過指針偏移找到插入元素的位置。通過memove和memcpy將新元素插入。

6. 在數(shù)組索引為n的位置替換元素:CList_Replace_

void CList_Replace_(CList *l, void *o, int n)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  if (n < 0 || n >= p->count)
  {
    fprintf(stderr, "CList: ERROR! Replace position outside range - %d; n - %d.\n", 
                        p->count, n);
    assert(n >= 0 && n < p->count);
    return;
  }

  char *data = (char*) p->items;
  data = data + n * p->item_size;
  memcpy(data, o, p->item_size);
}

這個也沒啥可說的，就是替換第n個元素。

7. 刪除第n個元素: CList_Remove_

void CList_Remove_(CList *l, int n)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  if (n < 0 || n >= p->count)
  {
    fprintf(stderr, "CList: ERROR! Remove position outside range - %d; n - %d.\n",
                        p->count, n);
    assert(n >= 0 && n < p->count);
    return;
  }

  size_t step = p->item_size;
  char *data = (char*)p->items + n * step;
  memmove(data, data + step, (p->count - n - 1) * step);
  p->count--;

  if (p->alloc_size > 3 * p->count && p->alloc_size >= 4) /* Dont hold much memory */
    CList_Realloc_(l, p->alloc_size / 2);
}

這里需要注意的是最后，如果當前數(shù)組的容量大于數(shù)組元素個數(shù)的3倍，并且容量大于等于4，它會將數(shù)組的容量減少為當前數(shù)組容量的一半。這樣做的目的是減少空閑內(nèi)存的消耗。

8. 獲取第n個元素:CList_At_

void *CList_At_(CList *l, int n)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  if (n < 0 || n >= p->count)
  {
    fprintf(stderr, "CList: ERROR! Get position outside range - %d; n - %d.\n", 
                      p->count, n);
    assert(n >= 0 && n < p->count);
    return NULL;
  }

  char *data = (char*) p->items;
  data = data + n * p->item_size;
  return data;
}

9. 動態(tài)數(shù)組擴容: CList_Realloc_

int CList_Realloc_(CList *l, int n)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  if (n < p->count)
  {
    fprintf(stderr, "CList: ERROR! Can not realloc to '%i' size - count is '%i'\n", n, p->count);
    assert(n >= p->count);
    return 0;
  }

  if (n == 0 && p->alloc_size == 0)
    n = 2;

  void *ptr = realloc(p->items, p->item_size * n);
  if (ptr == NULL)
  {
    fprintf(stderr, "CList: ERROR! Can not reallocate memory!\n");
    return 0;
  }
  p->items = ptr;
  p->alloc_size = n;
  return 1;
}

這里擴容后的容量是n，如果n小于當前數(shù)組元素的大小，就不會擴容，直接返回了。

10. 返回第一個等于指定值的下標:CList_FirstIndex_

int CList_FirstIndex_(CList *l, void *o)
{ 
  CList_priv_ *p = (CList_priv_*) l->priv;    
  char *data = (char*) p->items;
  size_t step = p->item_size;
  size_t i = 0;
  int index = 0;
  for (; i < p->count * step; i += step, index++)
  {
    if (memcmp(data + i, o, step) == 0)
      return index;
  }
  return -1; 
}

11. 返回最后一個等于指定值的下標:CList_LastIndex_

int CList_LastIndex_(CList *l, void *o)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  char *data = (char*) p->items;
  size_t step = p->item_size;
  int i = p->count * step - step;
  int index = p->count - 1;
  for (; i >= 0 ; i -= step, index--)
  {
    if (memcmp(data + i, o, step) == 0)
      return index;
  }
  return -1;
}

12. 獲取當前數(shù)組的元素個數(shù): CList_Count_

int CList_Count_(CList *l)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  return p->count;
}

13. 清理動態(tài)數(shù)組數(shù)據(jù): CList_Clear_

void CList_Clear_(CList *l)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  free(p->items);
  p->items = NULL;
  p->alloc_size = 0;
  p->count = 0;
}

14. 銷毀動態(tài)數(shù)組: CList_Free_

void CList_Free_(CList *l)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  free(p->items);
  free(p);
  free(l);
  l = NULL;
}

15. 打印數(shù)組: CList_print_

void CList_print_(CList *l, int n, const char *type)
{
  CList_priv_ *p = (CList_priv_*) l->priv;
  printf("\nCList:  count = %i  item_size = %zu   "
       "alloc_size = %i \n", p->count, p->item_size, p->alloc_size);

  if (n > 0)
  {
    n = (n > p->count) ? p->count : n;
    char *data = NULL;
    int i = 0;
    for (; i < n; i++)
    {
      data = (char*) p->items + i * p->item_size;
      if (type == NULL) printf("%p  ", data);  /* Print out pointers */
      else if (strcmp(type, "char") == 0) printf("%c ", *(char*) data);
      else if (strcmp(type, "short") == 0) printf("%hi  ", *(short*) data);
      else if (strcmp(type, "int") == 0) printf("%i  ", *(int*) data);
      else if (strcmp(type, "long") == 0) printf("%li  ", *(long*) data);
      else if (strcmp(type, "uintptr_t") == 0) printf("%zx  ", (uintptr_t*) data);
      else if (strcmp(type, "size_t") == 0) printf("%zu  ", *(size_t*) data);
      else if (strcmp(type, "double") == 0) printf("%f  ", *(double*) data);
      else if (strcmp(type, "string") == 0) printf("%s\n", data);
      else { printf("Unknown type."); break; }
    }
    printf("\n\n");
  }
}

16 具體用法

int main()
{
    struct unit {
    long int size;
    void *ptr;
    } unit;
    CList *list = CList_Init(sizeof(unit));     /* Initialization */

    long int i; 
    for (i = 0; i < 10; i++) {
        struct unit U = { i, &i };
        list->add(list, &U);            /* Adding data at the end */
        list->insert(list, &U, 0);      /* Insert at position 0 */    
    }
    /* 打印元素 此時數(shù)組元素為: 
     * 9  8  7  6  5  4  3  2  1  0  0  1  2  3  4  5  6  7  8 
     */
    i = list->count(list);            /* Get number of items in the list */
    list->print(list, i, "long");     /* Print out 'i' elements of list, first element of struct is shown */

    /* Get item at position '1' */
    /* 下標為1的元素，輸出當然是8 */
    struct unit *tmp = (struct unit*) list->at(list, 1);  
    printf("Unit size is %li, pointer is %p \n", tmp->size, tmp->ptr);

    /* 刪除第一個元素，數(shù)組變成:
     * 9  7  6  5  4  3  2  1  0  0  1  2  3  4  5  6  7  8  9
     */
    list->remove(list, 1);
    i = list->count(list);            /* Get number of items in the list */
    list->print(list, i, "long");     /* Print out 'i' elements of list, first element of struct is shown */

    /* 替換第一個元素為100 */
    long int j = 100;
    struct unit tmp1 = {j, &j};
    list->replace(list, &tmp1, 1);
    i = list->count(list);            /* Get number of items in the list */
    list->print(list, i, "long");     /* Print out 'i' elements of list, first element of struct is shown */

    /* 清除數(shù)組元素，執(zhí)行后數(shù)組中沒有元素了 */
    list->clear(list);
    i = list->count(list);            /* Get number of items in the list */
    list->print(list, i, "long");     /* Print out 'i' elements of list, first element of struct is shown */

    list->free(list);                 /* Destroy all data and list */ 
    return 0;
}

輸出:

CList:  count = 20  item_size = 16   alloc_size = 32
9  8  7  6  5  4  3  2  1  0  0  1  2  3  4  5  6  7  8  9  

Unit size is 8, pointer is 000000000061FDFC

CList:  count = 19  item_size = 16   alloc_size = 32
9  7  6  5  4  3  2  1  0  0  1  2  3  4  5  6  7  8  9


CList:  count = 19  item_size = 16   alloc_size = 32
9  100  6  5  4  3  2  1  0  0  1  2  3  4  5  6  7  8  9


CList:  count = 0  item_size = 16   alloc_size = 0

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【他山之玉】C語言動態(tài)數(shù)組的實現(xiàn)

【他山之玉】C語言動態(tài)數(shù)組的實現(xiàn)

0. 引言

1. CLIST整體介紹

2. Clist私有數(shù)據(jù)

3. 初始化動態(tài)數(shù)組: CList_Init

4. 在動態(tài)數(shù)組末尾添加元素:CList_Add_

5. 在數(shù)組索引為n的位置插入元素: CList_Insert_

6. 在數(shù)組索引為n的位置替換元素:CList_Replace_

7. 刪除第n個元素: CList_Remove_

8. 獲取第n個元素:CList_At_

9. 動態(tài)數(shù)組擴容: CList_Realloc_

10. 返回第一個等于指定值的下標:CList_FirstIndex_

11. 返回最后一個等于指定值的下標:CList_LastIndex_

12. 獲取當前數(shù)組的元素個數(shù): CList_Count_

13. 清理動態(tài)數(shù)組數(shù)據(jù): CList_Clear_

14. 銷毀動態(tài)數(shù)組: CList_Free_

15. 打印數(shù)組: CList_print_

16 具體用法

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【他山之玉】C語言動態(tài)數(shù)組的實現(xiàn)

0. 引言

1. CLIST整體介紹

2. Clist私有數(shù)據(jù)

3. 初始化動態(tài)數(shù)組: CList_Init

4. 在動態(tài)數(shù)組末尾添加元素:CList_Add_

5. 在數(shù)組索引為n的位置插入元素: CList_Insert_

6. 在數(shù)組索引為n的位置替換元素:CList_Replace_

7. 刪除第n個元素: CList_Remove_

8. 獲取第n個元素:CList_At_

9. 動態(tài)數(shù)組擴容: CList_Realloc_

10. 返回第一個等于指定值的下標:CList_FirstIndex_

11. 返回最后一個等于指定值的下標:CList_LastIndex_

12. 獲取當前數(shù)組的元素個數(shù): CList_Count_

13. 清理動態(tài)數(shù)組數(shù)據(jù): CList_Clear_

14. 銷毀動態(tài)數(shù)組: CList_Free_

15. 打印數(shù)組: CList_print_

16 具體用法

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av