avatar

抽象数据类型String

ADT——String

定义头文件——string.h

  • 结构定义与基本操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // 采用变长数组
    typedef struct
    {
    char * ch;
    int length;
    }Str;

    // 赋值操作
    int strAssign(Str * str, char * ch);

    // 取串长度
    int strLength(Str str);

    // 串比较
    int strCompare(Str s1, Str s2);

    // 串联接
    int concat(Str * str, Str str1, Str str2);

    // 求子串操作,以pos为起点,长度为len
    int subString(Str * substr, Str str, int pos, int len);

    // 清空串
    int clearString(Str * str);

实现文件——string.c

  • 给串赋值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include "string.h"

    // 给串赋值
    int strAssign(Str * str, char * ch)
    {
    // 如果ch非空,将其置空,这里用C的话
    // Linux下free这段代码有问题,不能释放
    // 可能和未初始化有关,去掉此判断即可
    if(str->ch)
    free(str->ch);

    int len = 0;
    char *c = ch;

    while(*c) { ++len; ++c; }

    // 如果赋空
    if(len==0)
    {
    str->ch = NULL;
    str->length = 0;
    return 1;
    }
    else
    {
    str->ch = (char *)malloc(sizeof(char) * len + 1);
    //如果分配失败
    if(str->ch == NULL)
    return 0;
    else
    {
    c = ch;
    int i;
    for(i = 0; i <= len; ++i, ++c)
    str->ch[i] = *c;
    // 下标从1开始,不把0号位置的长度考虑进去
    // 故此处减去1
    str->length = len-1;
    return 1;
    }
    }
    }
  • 取串长度
    1
    2
    3
    4
    5
    // 返回串的长度
    int strLength(Str str)
    {
    return str.length;
    }
  • 比较串的大小
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 这个字符串比较nice啊
    int strCompare(Str s1, Str s2)
    {
    int i;
    for(i = 0; i < s1.length && i < s2.length; ++i)
    if(s1.ch[i] != s2.ch[i])
    return s1.ch[i] - s2.ch[i];

    return s1.length - s2.length;
    }
  • 串的连接
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    // 字符串连接
    int concat(Str * str, Str str1, Str str2)
    {
    if(str->ch)
    {
    free(str->ch);
    str->ch = NULL;
    }
    str->ch = (char *)malloc(sizeof(char)*(str1.length + str2.length + 1));
    // 如果分配空间失败
    if(!str->ch)
    return 0;

    // 将字符串1赋给Str
    int i = 0;
    while(i < str1.length)
    {
    str->ch[i] = str1.ch[i];
    i++;
    }
    // 将字符串2继续赋给Str
    int j = 0;
    // 当j=str2.legthn时,将'\0'赋给str
    while(j <= str2.length)
    {
    str->ch[i+j] = str2.ch[j];
    j++;
    }
    str->length = str1.length + str2.length;
    return 1;
    }
  • 求子串
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    // 求子串
    int subString(Str * substr, Str str, int pos, int len)
    {
    // 排除不合法位置
    if(pos< 0 || pos >= str.length || len < 0 || len > str.length - pos)
    return 0;
    // 如果substr不为空,释放
    if(substr->ch)
    {
    free(substr->ch);
    substr->ch = NULL;
    }
    // 如果截取长度为0,substr赋值空
    if(len == 0)
    {
    substr->ch = NULL;
    substr->length = 0;
    return 1;
    }
    else
    {
    substr->ch = (char *)malloc(sizeof(char) * (len + 1));
    int i = pos;
    int j = 0;
    while(i < pos + len)
    {
    substr->ch[j] = str.ch[i];
    i++;
    j++;
    }
    substr->ch[j] = '\0';
    substr->length = len;
    return 1;
    }
    }
  • 销毁串
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int clearString(Str * str)
    {
    if(str->ch)
    {
    // 释放指针指向的内存后,还需要将其指向空
    // 否则任然指向原来的位置
    free(str->ch);
    str->ch = NULL;
    }
    str->length = 0;
    return 0;
    }
文章作者: Gy
文章链接: http://sgyat.cn/2020/04/12/String/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 年轻没有梦
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论