阅读:0       作者:解学武

串的堆分配存储结构(C语言实现)

堆分配存储是结构的一种具体实现方案,指的是用一整块适当大小的堆内存空间来存储字符串。

所谓堆内存,就是堆区的内存空间。以 C 语言为例,程序运行时占用的内存空间会分成很多大小不等的块(区域),它们通常被称为堆区、区、常量区、全局数据区、代码区等。这些区域各有分工,比如全局数据区用来存储全局变量和静态变量,代码区用来存储要运行的程序指令等。

和内存的其它区域相比,堆区最大的特点就是:不会自动分配和回收,必须由程序员手动申请,使用完后再手动释放。

在 C 语言中,申请堆内存的操作可以调用 malloc() 或者 calloc() 函数来完成,例如:
char * a = (char *)malloc(5 * sizeof(char));
如果 malloc() 函数执行成功,我们就申请了能存储 5 个字符的堆内存空间。

如果申请的堆内存空间不够用,还可以调用 realloc() 函数扩容,例如:
a = (char *)realloc(a, 10 * sizeof(char));
realloc() 函数执行成功,原本只能存 5 个字符的堆内存,扩容成能存储 10 个字符。

堆内存使用完后,需要手动调用 free() 函数释放,例如:
free(a);

强调:堆内存必须及时手动释放,否则会造成内存泄漏。

堆分配存储的具体实现

串的堆分配存储结构,可以用如下的结构体来表示:
typedef struct {
    char* ch;
    int length;
}HString;
ch 用来指向申请好的堆空间,以便存储字符串;length 用来记录串的长度。

举个简单的例子:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN1 10
#define LEN2 20
typedef struct {
    char* ch;
    int length;
}HString;

int concat(HString* str1, HString* str2) {
    int i;
    if (LEN1 < str1->length + str2->length) {
        str1->ch = (char *)realloc(str1->ch, (str1->length + str2->length + 1) * sizeof(char));
        //如果申请失败,则返回 0,表示连接失败
        if (str1->ch == NULL) {
            return 0;
        }
    }
    //合并两个串到 str1 中
    for (i = str1->length; i < str1->length + str2->length; i++) {
        str1->ch[i] = str2->ch[i - str1->length];
       
    }
    str1->ch[str1->length + str2->length] = '\0';
    str1->length += str2->length;
    return 1;
}

int main()
{
    HString str1 = { NULL,0 }, str2 = { NULL,0 };
    //创建存储"http://"的堆分配存储结构
    str1.ch = (char *)malloc(LEN1 * sizeof(char));
    strcpy(str1.ch, "http://");
    str1.length = strlen(str1.ch);

    //创建存储"http://"的堆分配存储结构
    str2.ch = (char *)malloc(LEN2 * sizeof(char));
    strcpy(str2.ch, "data.biancheng.net");
    str2.length = strlen(str2.ch);

    //连接两个串
    if (concat(&str1, &str2)) {
        printf("连接成功,新字符串为:%s", str1.ch);
    }
    else
    {
        printf("连接失败\n");
    }
    //手动释放申请的两个堆空间
    free(str1.ch);
    free(str2.ch);
    return 0;
}
运行结果为:

连接成功,新字符串为:http://data.biancheng.net

程序中的 concat() 函数实现了连接两个字符串,此过程必须预先判断堆内存是否够用,必要时可以调用 realloc() 函数扩容。

总结

和定长顺序存储结构相比,堆分配存储结构最大的不同就是存储字符串的空间可以动态变化,这也是很多实际场景中弃用定长顺序存储结构而选用堆分配存储结构的主要原因。