频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
字符串动态数组的C实现方法
2015-06-23 11:42:09         来源:zhyh1435589631的专栏  
收藏   我要投稿

我们知道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);
}

点击复制链接 与好友分享!回本站首页
上一篇:OC基础:类的扩展.协议
下一篇:Objective-c调用Swift
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站