程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C基礎萬能動態數組，動態數組

C基礎萬能動態數組，動態數組

編輯：關於C語言

C基礎萬能動態數組，動態數組

引言 - 動態數組切入

　　開發中動態類型無外乎list 或者 vector, 這裡就是在C中實現vector結構容器部分.

對於C中使用的數據結構, 可以參照下面感覺很不錯框架源碼學習 , 感覺是<<C接口與實現>>的標准Demo

　　　　twemproxy https://github.com/twitter/twemproxy/tree/master/src

寫的很清楚易懂, 給人一種鋪面而來的美感.

關於動態數組設計的總思路, 主要體現在下面的數組結構 struct array {}; 中

struct array {
    void *        as;        /* 存儲數組具體內容首地址 */
    unsigned    len;    /* 當前數組的長度 */
    unsigned    size;   /* 當前數組容量大小 */
    size_t        alloc;    /* 每個元素字節大小 */
};

as 保存動態數組的首地址, len保存當前動態數組中元素個數, size表示動態數組容量(內存總大小), alloc記錄每次分配多大內存.

是不是很簡單, 數據結構一但確定什麼都OK了. 在具體分析之前先擴展講解一下 C11的內聯函數. 內聯函數是應用場景很多, 宏一般的性能, 並且還可以當函數調試!

// 內聯函數聲明部分, 不需要加inline
extern void heoo(void);

// 內聯函數定義部分
inline void
heoo(void) {
  ... 
}

上面就是內聯函數的套路, 在定義的時候加上內聯屬性inline. 這種做法是為了VS2015 和 GCC5.3 對於inline 語法解析的統一.

具體看下面搜索到的老外給的資料

　　　　內聯解析warning資料 http://www.avrfreaks.net/forum/declaring-function-extern-inline-header-file

Computer science 還是老外厲害些, 國內最屌, 也只是國外一線的水准. 目前猜測的原因是, 祖國就一個, 國外太多了. O(∩_∩)O哈哈~

前言 - 接口分析

　　具體設計了下面幾種接口, 基本夠用了.也很好用.

/*
 * 返回創建數組對象
 * size        : 創建數組的總大小個數
 * alloc    : 數組中每個元素的字節數
 *            : 返回創建的數組對象
 */
extern array_t array_new(unsigned size, size_t alloc);

/*
 * 銷毀這個創建的數組對象
 * a        : 創建的數組對象
 */
extern void array_delete(array_t a);

/*
 * 重新構建一個數組對象
 * a        : 可變數組對象
 * size        : 新可變數組總長度
 */
extern void array_newinit(array_t a, unsigned size);

/*
 * 得到節點elem在數組中索引
 * a        : 可變數組對象
 * elem        : 查詢元素
 *            : 返回查詢到位置
 */
extern unsigned array_idx(array_t a, void * elem);

/*
 * 為可變數組插入一個元素, 並返回這個元素的首地址
 * a        : 可變數組對象
 *            : 返回創建對象位置
 */
extern void * array_push(array_t a);

/*
 * 彈出一個數組元素
 * a        : 可變數組對象
 *            : 返回彈出數組元素節點
 */
extern void * array_pop(array_t a);

/*
 * 按照索引得到數組元素
 * a        : 可變數組對象
 * idx        : 索引位置
 *            : 返回查詢到數據
 */
extern void * array_get(array_t a, unsigned idx);

/*
 * 得到數組頂的元素
 * a        : 可變數組對象
 *            : 返回得到元素
 */
extern void * array_top(array_t a);

/*
 * 兩個數組進行交換
 * a        : 數組a
 * b        : 數組b
 */
extern void array_swap(array_t a, array_t b);

/*
 * 數組進行排序
 * a        : 數組對象
 * compare    : 比對規則
 */
extern void array_sort(array_t a, icmp_f compare);

/*
 * 數組進行遍歷
 * a        : 可變數組對象
 * func        : 執行每個結點函數, typedef flag_e    (* each_f)(void * node, void * arg);
 * arg        : 附加參數
 *            : 返回操作結果狀態碼
 */
flag_e array_each(array_t a, each_f func, void * arg);

圍繞創建, 銷毀, 添加元素, 刪除元素, 交換, 遍歷, 排序等操作. 具體參看 array.h 文件

#ifndef _H_SIMPLEC_ARRAY #define _H_SIMPLEC_ARRAY #include <stdlib.h> #define sm_free free typedef enum { RT_SuccessBase = 00, //結果正確的返回宏 RT_ErrorBase = -1, //錯誤基類型, 所有錯誤都可用它, 在不清楚的情況下 RT_ErrorParam = -2, //調用的參數錯誤 RT_ErrorMalloc = -3, //內存分配錯誤 RT_ErrorFopen = -4, //文件打開失敗 RT_ErrorClose = -5, //文件描述符讀取關閉, 讀取完畢也會返回這個 } flag_e; // icmp_f 最好是 int cmp(const void * ln, const void * rn); 標准結構 typedef int (* icmp_f)(); // 循環操作函數, arg 外部參數, node 內部節點 typedef flag_e (* each_f)(void * node, void * arg); struct array { void * as; /* 存儲數組具體內容首地址 */ unsigned len; /* 當前數組的長度 */ unsigned size; /* 當前數組容量大小 */ size_t alloc; /* 每個元素字節大小 */ }; // 定義可變數組類型對象 typedef struct array * array_t; /* * 在棧上創建對象 ##var * var : 創建對象名稱 * size : 創建對象總長度 * alloc : 每個元素分配空間大小 */ #define ARRAY_NEW(var, size, alloc) \ struct array $__##var = { NULL, 0, 0, alloc }, * var = &$__##var;\ array_newinit(var, size) #define ARRAY_DELETE(var) \ sm_free(var->as) /* * 返回創建數組對象 * size : 創建數組的總大小個數 * alloc : 數組中每個元素的字節數 * : 返回創建的數組對象 */ extern array_t array_new(unsigned size, size_t alloc); /* * 銷毀這個創建的數組對象 * a : 創建的數組對象 */ extern void array_delete(array_t a); /* * 重新構建一個數組對象 * a : 可變數組對象 * size : 新可變數組總長度 */ extern void array_newinit(array_t a, unsigned size); /* * 得到節點elem在數組中索引 * a : 可變數組對象 * elem : 查詢元素 * : 返回查詢到位置 */ extern unsigned array_idx(array_t a, void * elem); /* * 為可變數組插入一個元素, 並返回這個元素的首地址 * a : 可變數組對象 * : 返回創建對象位置 */ extern void * array_push(array_t a); /* * 彈出一個數組元素 * a : 可變數組對象 * : 返回彈出數組元素節點 */ extern void * array_pop(array_t a); /* * 按照索引得到數組元素 * a : 可變數組對象 * idx : 索引位置 * : 返回查詢到數據 */ extern void * array_get(array_t a, unsigned idx); /* * 得到數組頂的元素 * a : 可變數組對象 * : 返回得到元素 */ extern void * array_top(array_t a); /* * 兩個數組進行交換 * a : 數組a * b : 數組b */ extern void array_swap(array_t a, array_t b); /* * 數組進行排序 * a : 數組對象 * compare : 比對規則 */ extern void array_sort(array_t a, icmp_f compare); /* * 數組進行遍歷 * a : 可變數組對象 * func : 執行每個結點函數, typedef flag_e (* each_f)(void * node, void * arg); * arg : 附加參數 * : 返回操作結果狀態碼 */ flag_e array_each(array_t a, each_f func, void * arg); #endif // !_H_SIMPLEC_ARRAY View Code

下面添加棧上聲明部分, 采用宏設計

// 定義可變數組類型 對象
typedef struct array * array_t;

/*
 * 在棧上創建對象 ##var
 * var        : 創建對象名稱
 * size        : 創建對象總長度
 * alloc    : 每個元素分配空間大小
 */
#define ARRAY_NEW(var, size, alloc) \
    struct array $__##var = { NULL, 0, 0, alloc }, * var = &$__##var;\
    array_newinit(var, size)
#define ARRAY_DELETE(var) \
    sm_free(var->as)

是不是很有意思, 這些都是具體開發中的解決方案.

此事我們的設計思路已經轉成接口設計代碼. 現在先寫一些前測試代碼 test_array.c

下面主要測試棧上動態數組分配和使用

#define LEN(arr) \
    (sizeof(arr)/sizeof(*(arr)))

//簡單結構
struct dict {
    char * key;
    char * value;
};

// 單獨遍歷函數
static flag_e _dict_echo(struct dict * node, void * arg)
{
    printf("[%s]    => [%s]\n", node->key, node->value);
    return RT_SuccessBase;
}

// 比較函數
static int _dict_cmp(struct dict * ln, struct dict * rn) {
    return strcmp(ln->key, rn->key);
}

/*
 * 主要測試 array 動態數組模塊代碼
 */
void test_array(void) {
    struct dict * elem;

    struct dict dicts[] = {
        { "zero"    , "零" },
        { "one"        , "一" },
        { "two"        , "二" },
        { "three"    , "三" },
        { "four"    , "四" },
        { "five"    , "五" },
        { "six"        , "六" },
        { "seven"    , "七" },
        { "eight"    , "八" },
        { "night"    , "九" },
        { "night"    , "十" },
    };

    /* Step 1 : 測試堆上array對象 */
    int i = -1, len = LEN(dicts);
    array_t a = array_new(len, sizeof(struct dict));

    // 插入數據
    while (++i < len) {
        elem = array_push(a);
        *elem = dicts[i];
    }

    // 打印數據測試
    puts("----------- start data look at the following:");
    array_each(a, (each_f)_dict_echo, NULL);

    // 排序一下
    array_sort(a, _dict_cmp);

    // 打印數據測試
    puts("----------- sort data look at the following:");
    array_each(a, (each_f)_dict_echo, NULL);

    array_delete(a);

    exit(EXIT_SUCCESS);
}

為什麼采用exit 結束操作, 先賣一個關子. 上面是圍繞創建和遍歷最後排序的測試. 從上面感受這些動態數組的api使用方式.

軟件設計套路很多但是對於C. 請參照下面套路.

　　業務理解 -> 數據結構 -> 接口定義 -> | 接口實現

　　　　　　　　　　　　　　　　　　 -> |　　　　　　-> 業務實現 -> 業務測試 -> 提交功能

　　　　　　　　　　　　　　　　　　 -> | 接口測試

標黑的特別重要. 當然了, 對於高級語言, 數據結構可以省略了, 主要是業務理解 -> 接口實現. 這也是軟件設計界一種解放吧. 正文部分會具體分析實現部分.

正文 - 接口實現

　　好的接口定義, 是一切好的開始. 接口實現還是很容易的. 例如下面關於動態數組的 array.c 實現

#include "array.h" #include <stdio.h> #include <assert.h> #include <string.h> // 導入需要的輔助函數 static void * sm_malloc(size_t sz) { void * ptr = malloc(sz); if(NULL == ptr) { fprintf(stderr, "sm_malloc malloc sz = %ld is error!\n", sz); exit(EXIT_FAILURE); } memset(ptr, 0, sz); return ptr; } static void * sm_realloc(void * ptr, size_t sz) { void * nptr = realloc(ptr, sz); if(NULL == nptr) { free(ptr); fprintf(stderr, "sm_realloc realloc ptr, sz = %p, %ld is error!\n", ptr, sz); exit(EXIT_FAILURE); } if(NULL != ptr) memset(nptr, 0, sz); return nptr; } /* * 返回創建數組對象 * size : 創建數組的總大小個數 * alloc : 數組中每個元素的字節數 * : 返回創建的數組對象 */ array_t array_new(unsigned size, size_t alloc) { struct array * a = sm_malloc(sizeof(struct array)); if (size * alloc > 0) a->as = sm_malloc(size * alloc); a->size = size; a->alloc = alloc; return a; } /* * 銷毀這個創建的數組對象 * a : 創建的數組對象 */ inline void array_delete(array_t a) { sm_free(a->as); sm_free(a); } /* * 重新構建一個數組對象 * a : 可變數組對象 * size : 新可變數組總長度 */ inline void array_newinit(array_t a, unsigned size) { assert(NULL != a); a->as = sm_realloc(a->as, size * a->alloc); if (a->len > size) a->len = size; a->size = size; } /* * 得到節點elem在數組中索引 * a : 可變數組對象 * elem : 查詢元素 * : 返回查詢到位置 */ inline unsigned array_idx(array_t a, void * elem) { unsigned char * p, * q; unsigned off; assert(NULL != a && elem >= a->as); p = a->as; q = elem; off = (unsigned)(q - p); assert(off % (unsigned)a->alloc == 0); return off / (unsigned)a->alloc; } /* * 為可變數組插入一個元素, 並返回這個元素的首地址 * a : 可變數組對象 * : 返回創建對象位置 */ void * array_push(array_t a) { assert(NULL != a); if (a->len == a->size) { /* the array is full; allocate new array */ a->size <<= 1; a->as = sm_realloc(a->as, a->size * a->alloc); } return (unsigned char *)a->as + a->alloc * a->len++; } /* * 彈出一個數組元素 * a : 可變數組對象 * : 返回彈出數組元素節點 */ inline void * array_pop(array_t a) { assert(NULL != a && 0 != a->len); --a->len; return (unsigned char *)a->as + a->alloc * a->len; } /* * 按照索引得到數組元素 * a : 可變數組對象 * idx : 索引位置 * : 返回查詢到數據 */ inline void * array_get(array_t a, unsigned idx) { assert(NULL != a && idx < a->len); return (unsigned char *)a->as + a->alloc * idx; } /* * 得到數組頂的元素 * a : 可變數組對象 * : 返回得到元素 */ inline void * array_top(array_t a) { assert(NULL != a && 0 != a->len); return (unsigned char *)a->as + a->alloc * (a->len - 1); } /* * 兩個數組進行交換 * a : 數組a * b : 數組b */ inline void array_swap(array_t a, array_t b) { struct array t = *a; *a = *b; *b = t; } /* * 數組進行排序 * a : 數組對象 * compare : 比對規則 */ inline void array_sort(array_t a, icmp_f compare) { assert(NULL != a && 0 != a->len && NULL != compare); qsort(a->as, a->len, a->alloc, (int ( *)(const void *, const void *))compare); } /* * 數組進行遍歷 * a : 可變數組對象 * func : 執行每個結點函數, typedef flag_e (* each_f)(void * node, void * arg); * arg : 附加參數 * : 返回操作結果狀態碼 */ flag_e array_each(array_t a, each_f func, void * arg) { flag_e rt; unsigned char * s, * e; assert(NULL != a && NULL != func); s = a->as; e = s + a->alloc * a->len; while (s < e) { rt = func(s, arg); if (RT_SuccessBase != rt) return rt; s += a->alloc; } return RT_SuccessBase; } View Code

觀看array.c 中具體部分下面三個函數是控制整個動態數組生命周期的

/*
 * 返回創建數組對象
 * size        : 創建數組的總大小個數
 * alloc    : 數組中每個元素的字節數
 *            : 返回創建的數組對象
 */
array_t 
array_new(unsigned size, size_t alloc) {
    struct array * a = sm_malloc(sizeof(struct array));
    if (size * alloc > 0)
        a->as = sm_malloc(size * alloc);

    a->size = size;
    a->alloc = alloc;

    return a;
}

/*
 * 銷毀這個創建的數組對象
 * a        : 創建的數組對象
 */
inline 
void array_delete(array_t a) {
    sm_free(a->as);
    sm_free(a);
}

/*
 * 重新構建一個數組對象
 * a        : 可變數組對象
 * size        : 新可變數組總長度
 */
inline void
array_newinit(array_t a, unsigned size) {
    assert(NULL != a);
    a->as = sm_realloc(a->as, size * a->alloc);
    if (a->len > size)
        a->len = size;
    a->size = size;
}

new 創建, delete銷毀, newinit重新創建. 其中還有一個 api, 向動態數組加入元素也特別有意思

/*
 * 為可變數組插入一個元素, 並返回這個元素的首地址
 * a        : 可變數組對象
 *            : 返回創建對象位置
 */
void * 
array_push(array_t a) {
    assert(NULL != a);

    if (a->len == a->size) {
        /* the array is full; allocate new array */
        a->size <<= 1;
        a->as = sm_realloc(a->as, a->size * a->alloc);
    }

    return (unsigned char *)a->as + a->alloc * a->len++;
}

返回插入元素的首地址, 需要自己初始化. 特別新潮的做法. (當然了對於C這種老古董, 這些也都是老掉牙的東西, 只是自娛自樂, 開心就好)

實現部分到這裡基本完畢了, 最好能看一遍其中具體文件, 設計思路非常好, 實現也是力求最快最簡.

對於 exit這個坑 , 主要看 linux上代碼, 例如 man select 會出現

exit(EXIT_SUCCESS) ; 這個做法是為了, 解決在函數調用結束, 釋放啟動這個 main函數之前聲明的資源.

當然系統都會對 mian 函數特殊處理, 哪怕return 也能釋放干淨. 但是假如一個文件沒有main函數, 啟動了新的入口函數,

這是否return 是不會幫我們額外清理一些資源的. 這時候運行結束會崩潰. exit 就是為了解決退出時候資源釋放問題.

到這裡我們給出測試部分了. 先看 Makefile 文件

CC = gcc
DEBUG = -ggdb3 -Wall
RUN = $(CC) $(DEBUG) -o $@ $^
RUNO = $(CC) -c -o $@ $<
RUNMAIN = $(RUN) -nostartfiles -e $(*F)

all:test_array.out test_array_stack.out

%.o:%c
    $(RUNO)
    
test_array.out:test_array.o array.o
    $(RUNMAIN)

test_array_stack.out:test_array.o array.o
    $(RUNMAIN)

# 清除命令
.PHONY:clean
clean:
    rm -rf *.i *.s *.o *.out *~ ; ls

具體的測試文件 test_array.c

#include "array.h" #include <stdio.h> #include <string.h> #define LEN(arr) \ (sizeof(arr)/sizeof(*(arr))) //簡單結構 struct dict { char * key; char * value; }; // 單獨遍歷函數 static flag_e _dict_echo(struct dict * node, void * arg) { printf("[%s] => [%s]\n", node->key, node->value); return RT_SuccessBase; } // 比較函數 static int _dict_cmp(struct dict * ln, struct dict * rn) { return strcmp(ln->key, rn->key); } /* * 主要測試 array 動態數組模塊代碼 */ void test_array(void) { struct dict * elem; struct dict dicts[] = { { "zero" , "零" }, { "one" , "一" }, { "two" , "二" }, { "three" , "三" }, { "four" , "四" }, { "five" , "五" }, { "six" , "六" }, { "seven" , "七" }, { "eight" , "八" }, { "night" , "九" }, { "night" , "十" }, }; /* Step 1 : 測試堆上array對象 */ int i = -1, len = LEN(dicts); array_t a = array_new(len, sizeof(struct dict)); // 插入數據 while (++i < len) { elem = array_push(a); *elem = dicts[i]; } // 打印數據測試 puts("----------- start data look at the following:"); array_each(a, (each_f)_dict_echo, NULL); // 排序一下 array_sort(a, _dict_cmp); // 打印數據測試 puts("----------- sort data look at the following:"); array_each(a, (each_f)_dict_echo, NULL); array_delete(a); exit(EXIT_SUCCESS); } void test_array_stack(void) { struct dict * elem; struct dict dicts[] = { { "zero" , "零" }, { "one" , "一" }, { "two" , "二" }, { "three" , "三" }, { "four" , "四" }, { "five" , "五" }, { "six" , "六" }, { "seven" , "七" }, { "eight" , "八" }, { "night" , "九" }, { "night" , "十" }, }; /* Step 1 : 測試堆上array對象 */ int i = -1, len = LEN(dicts); ARRAY_NEW(a, len, sizeof(struct dict)); // 插入數據 while (++i < len) { elem = array_push(a); *elem = dicts[i]; } // 打印數據測試 puts("----------- start data look at the following:"); array_each(a, (each_f)_dict_echo, NULL); // 排序一下 array_sort(a, _dict_cmp); // 打印數據測試 puts("----------- sort data look at the following:"); for(i=0; i<len; ++i) { elem = array_get(a, i); _dict_echo(elem, NULL); } ARRAY_DELETE(a); exit(EXIT_SUCCESS); } View Code

最終效果 , 先看編譯結果圖