字符串動態數組的C實現方法

我們知道C++是支持容器的， 對於各種數據類型都能有很好的支持，但是C不一樣， C的數據類型支持真的很差，一旦換一種類型，又得重新編碼，比如從int型的動態數組 轉到string類型的動態數組，會發現這是件非常痛苦的事情。今天手賤，用C實現一下字符串動態數組的編寫。

主要目的是：
1. 回顧一下，C中的動態內存分配方法，（主要就是malloc， realloc， free的使用）， 按照我們的理解C++中的 new 本質也就是 malloc + construct， 先分配一片內存， 然後在這片內存上placement new 一個對象。
2. 體會一下接口的封裝設計，指針的傳遞， 注意內存的分配和釋放。

編碼過程中遇到的兩個問題，記錄如下：

1.error C2275 將此類型用作表達式非法：
    主要原因， C中要求變量的聲明定義在區域的段首，若寫到中間會報錯， 而C++不存在這個問題
2. int StringInsertOneByPointer(StringArr * arr, const char * target, pStringNode pos) 
函數中由於realloc函數會對指針地址修改， 若此時沒有及時修正哨兵的值， 會存在錯誤。

下面放出源代碼：
代碼寫的有些粗糙， 只是基本實現了功能， 還有很大的改進空間，比如搜索的時候， 我們只是從頭到尾進行遍歷 是O(n)的算法復雜度， 可以根據是否已經排序，設計出針對已經排序後序列的二分查找算法 O(logn)。
同樣的，排序那段，我們只是簡單的使用冒泡排序算法， 復雜度為 O(n^2), 可以改用快速排序 O(nlogn)， 當然這些在數據量小的時候，效果不明顯， 在大數據情況下，就可以看出差別了。

// =====================【字符串的數組】==================
// @ author         :           zhyh2010
// @ date           :           20150601
// @ version        :           1.0
// @ description    :       實現一個字符串的數組封裝，實現增加，刪除，插入，修改，排序
// =====================【字符串的數組】==================

#include 
#include 
#include 
#include 

#define SUCCESS 0
#define INPUT_ERROR -1
#define MALLOC_ERROR -2
#define NOT_FIND NULL

typedef struct _StringNode
{
    int length;
    char * pStr;
}StringNode, *pStringNode;

typedef struct _StringArr
{
    StringNode * pHead;
    int length;
    int capacity;
}StringArr, *pStringArr;

// ====================== add  ========================
int StringAddOne(StringArr * arr, const char * source);

// ====================== delete =======================
int StringDeleteOne(StringArr * arr, const char * target);

// ====================== search =======================
pStringNode StringSearchFirst(StringArr * arr, const char * target);

// ====================== insert =======================
int StringInsertOneByPointer(StringArr * arr, const char * target, pStringNode pos);
int StringInsertByStr(StringArr * arr, const char * target, const char * PosPointer);
int StringInsertByID(StringArr * arr, const char * target, int id);

// ======================= modify ========================
int StringModify(StringArr * arr, const char * target, const char * source);

// ======================= sort =========================
int StringSort(StringArr * arr, int seq);

// ====================== create ========================
pStringArr StringCreate();

// ===================== destroy =======================
void StringDestroy(pStringArr parr);

// ==================== 測試用例 ======================
void main()
{
    pStringArr pArr = StringCreate();
    int ret = -1;
    pStringNode pres = NOT_FIND;

    // =========== insert ================
    ret = StringInsertByID(pArr, "love", 10);
    ret = StringInsertByID(pArr, "new", 0);
    ret = StringInsertByStr(pArr, "hi", "love");
    ret = StringInsertByStr(pArr, "ho", "new");
    ret = StringInsertByStr(pArr, "hi", "zhyh201012");
    ret = StringInsertByStr(pArr, "ho", "ll12");

    // =========== add one ===============
    ret = StringAddOne(pArr, "hello world");
    ret = StringAddOne(pArr, "zhyh2010");
    ret = StringAddOne(pArr, "zh");
    ret = StringAddOne(pArr, "hihocoder");
    ret = StringAddOne(pArr, "ustc");
    ret = StringAddOne(pArr, "china");
    ret = StringAddOne(pArr, "jp");

    // ========== search first ===========
    pres = StringSearchFirst(pArr, "zhyh2010");
    pres = StringSearchFirst(pArr, "zhy");

    // ========= deleteone ===============
    ret = StringDeleteOne(pArr, "hy");
    ret = StringDeleteOne(pArr, "ustc");
    ret = StringDeleteOne(pArr, "jp");

    // ========== modify ==================
    ret = StringModify(pArr, "123", "asldf");
    ret = StringModify(pArr, "zhyh2010", "zhyh2010@ustc");

    // =========== insert ================
    ret = StringInsertByID(pArr, "love", 10);
    ret = StringInsertByStr(pArr, "ho", "china");
    ret = StringInsertByStr(pArr, "hi12", "china");
    ret = StringInsertByStr(pArr, "ho2", "china");
    ret = StringInsertByStr(pArr, "h3i", "china");
    ret = StringInsertByStr(pArr, "h2o", "china");

    // =========== sort =======================
    ret = StringSort(pArr, 0);

    // ========== destroy =================
    StringDestroy(pArr);
}


// ====================== add  ========================
int StringAddOne(StringArr * arr, const char * source)
{
    if (arr == NULL || source == NULL)
        return INPUT_ERROR;

    // alloc memory
    if (arr->capacity <= arr->length)
    {
        if (arr->pHead == NULL)
        {
            // alloc space when phead == NULL
            pStringNode pNode = (pStringNode)malloc(sizeof(StringNode));
            if (pNode == NULL)
                return MALLOC_ERROR;

            arr->pHead = pNode;
            arr->capacity += 1;
        }
        else
        {
            // realloc space
            pStringNode pNode = (pStringNode)realloc(arr->pHead, sizeof(StringNode)* 2 * arr->capacity);
            if (pNode == NULL)
                return MALLOC_ERROR;

            arr->pHead = pNode;
            arr->capacity = 2 * arr->capacity;
        }
    }

    int source_len = strlen(source);
    char * tmp = (char *)malloc(sizeof(char)* (source_len + 1));
    if (tmp == NULL)
        return MALLOC_ERROR;

    //pStringNode pNode = arr->pHead + arr->length;             //  c2275 C不允許在中途聲明變量
    //StringNode * pNode = &(arr->pHead)[arr->length];
    arr->pHead[arr->length].length = source_len + 1;
    arr->pHead[arr->length].pStr = tmp;

    strcpy(arr->pHead[arr->length].pStr, source);
    arr->length += 1;
    return SUCCESS;
}

// ====================== delete =======================
int StringDeleteOne(StringArr * arr, const char * target)
{
    pStringNode pres = (pStringNode)NOT_FIND;

    if (arr == NULL || target == NULL)
        return INPUT_ERROR;

    pres = StringSearchFirst(arr, target);
    if (pres == (pStringNode)NOT_FIND)
        return (int)NOT_FIND;

    free(pres->pStr);

    for (; pres != arr->pHead + arr->length - 1; pres++)
        *pres = *(pres + 1);
    pres->length = 0;
    pres->pStr = NULL;

    arr->length -= 1;

    return SUCCESS;
}

// ====================== search =======================
pStringNode StringSearchFirst(StringArr * arr, const char * target)
{
    pStringNode pres = (pStringNode)NOT_FIND;

    if (arr == NULL || target == NULL)
        return (pStringNode)INPUT_ERROR;

    //pStringNode pres = NOT_FIND;
    for (int i = 0; i != arr->length; i++)
    {
        if (strcmp(target, arr->pHead[i].pStr) == 0)
        {
            pres = &arr->pHead[i];
            break;
        }
    }

    return pres;
}

// ====================== insert =======================
int StringInsertOneByPointer(StringArr * arr, const char * target, pStringNode pos)
{
    char * tmp = NULL;
    pStringNode pOld = NOT_FIND;

    if (arr == NULL || target == NULL || pos == NULL)
        return INPUT_ERROR;

    //assert(arr->capacity == 0);
    assert(arr->capacity > 0);

    if (arr->capacity <= arr->length)
    {
        pOld = arr->pHead;
        arr->pHead = (pStringNode)realloc(arr->pHead, sizeof(StringNode)* 2 * arr->capacity);
        arr->capacity = 2 * arr->capacity;
        // 修正邊界
        pos += arr->pHead - pOld;
    }

    // 在指針指向的位置處插入 （前叉）
    tmp = (char *)malloc(sizeof(char)* (strlen(target) + 1));
    if (tmp == NULL)
        return MALLOC_ERROR;

    for (pStringNode pres = arr->pHead + arr->length - 1; pres != pos - 1; pres--)
        *(pres + 1) = *pres;

    pos->pStr = tmp;
    strcpy(pos->pStr, target);
    pos->length = strlen(target) + 1;
    arr->length += 1;

    return SUCCESS;
}

int StringInsertByStr(StringArr * arr, const char * target, const char * PosPointer)
{
    pStringNode pres = NOT_FIND;

    if (arr == NULL || target == NULL || PosPointer == NULL)
        return INPUT_ERROR;

    pres = StringSearchFirst(arr, PosPointer);
    return StringInsertOneByPointer(arr, target, pres);
}

// id 從 0 開始計算
int StringInsertByID(StringArr * arr, const char * target, int id)
{
    pStringNode pres = NOT_FIND;

    if (arr == NULL || target == NULL)
        return INPUT_ERROR;

    if (id < 0)
        id = 0;
    if (id > arr->length)
        id = arr->length;

    if (arr->length == 0)
        return StringAddOne(arr, target);

    pres = arr->pHead + id;
    return StringInsertOneByPointer(arr, target, pres);
}

// ======================= modify ========================
int StringModify(StringArr * arr, const char * target, const char * source)
{
    pStringNode pres = NOT_FIND;
    pStringNode tmp = NOT_FIND;

    if (arr == NULL || target == NULL || source == NULL)
        return INPUT_ERROR;

    pres = StringSearchFirst(arr, target);
    if (pres == NULL)
        return (int)NOT_FIND;

    tmp = (pStringNode)malloc(sizeof(char)* (strlen(source) + 1));
    if (tmp == NULL)
        return MALLOC_ERROR;

    free(pres->pStr);
    pres->pStr = tmp;
    pres->length = strlen(source) + 1;

    strcpy(pres->pStr, source);
    return SUCCESS;
}


// ======================= sort =========================
int StringSort(StringArr * arr, int seq)
{
    StringNode tmp;

    if (arr == NULL)
        return INPUT_ERROR;

    if (arr->pHead == NULL || arr->length == 1)
        return SUCCESS;

#define MAX2MIN 1
#define MIN2MAX 0

    seq = (seq > 0) ? MAX2MIN : MIN2MAX;

    if (seq == MIN2MAX)
    {
        // 使用冒泡法排序
        for (int i = 0; i != arr->length - 1; i++)
        {
            for (int j = 0; j != arr->length - 1 - i; j++)
            {
                if (strcmp(arr->pHead[j].pStr, arr->pHead[j+1].pStr) > 0)
                {
                    tmp = arr->pHead[j + 1];
                    arr->pHead[j + 1] = arr->pHead[j];
                    arr->pHead[j] = tmp;
                }
            }
        }
    }
    else
    {
        for (int i = 0; i != arr->length - 1; i++)
        {
            for (int j = 0; j != arr->length - 1 - i; j++)
            {
                if (strcmp(arr->pHead[j].pStr, arr->pHead[j + 1].pStr) < 0)
                {
                    tmp = arr->pHead[j + 1];
                    arr->pHead[j + 1] = arr->pHead[j];
                    arr->pHead[j] = tmp;
                }
            }
        }
    }

    return SUCCESS;
}

// ====================== create ========================
pStringArr StringCreate()
{
    pStringArr parr = (pStringArr)malloc(sizeof(StringArr));
    if (parr == NULL)
        return parr;

    parr->capacity = 0;
    parr->length = 0;
    parr->pHead = NULL;
    return parr;
}

// ===================== destroy =======================
void StringDestroy(pStringArr parr)
{
    if (parr == NULL)
        return;

    while (parr->length != 0)
    {
        if (parr->pHead[parr->length - 1].pStr != NULL)
        {
            free(parr->pHead[parr->length - 1].pStr);
            parr->pHead[parr->length - 1].length = 0;
            parr->length--;
        }
    }
    if (parr->pHead != NULL)
        free(parr->pHead);

    free(parr);
}