字符串

Created Mar 12, 2025 - Last updated: Mar 12, 2025

Seeding 🌱

algorithm 模板字符串

字符串

字符串的定义与结构

字符串一般简称为串。字符串中任意个连续的字符组成的子序列称为该字符串的子串

// 字符串抽象数据类型定义
数据对象:String
数据关系:<$s_{i-1},s_i$>
基本操作:
    InitStr(s):             初始化
    StrCopy(s):             复制字符串
    StrIsEmpty(s):          判断字符串是否为空串
    StrInsert(s,pos,t):     在字符串s的pos位置插入字符串t
    StrRemove(s,pos,len):   删除字符串s从pos位置长度为len的字串
    SubString(s,pos,len):   返回字符串s从pos位置长度为len的字串
    StrLength(s):           返回字符串s的长度
    StrConcat(s,t):         返回字符串s和t连接而成的新串
    StrCompare(s,t):        返回字符串s和t的大小关系
    PatternMatch(s,t):      返回字符串s中首次出现字符串t的位置
    Replace(s,sub_s,t):     将字符串s中的所有字串sub_s替换为字符串t

字符串的存储结构

字符串的存储表示与线性表相同，一般有顺序存储结构和链式存储结构

字符串的顺序存储结构

字符串插入

char* StrInsert(char* s, int pos, char* t)
{
    int n = strlen(s);
    int m = strlen(t);
    for (int i = n; i >= pos; i--)
    {
        s[i + m] = s[i];
    }
    for (int i = 0; i < m; i++)
    {
        s[pos + i] = t[i];
    }
    return s;
}

字符串删除

char* StrRemove(char* s, int pos, int len)
{
    int n = strlen(s);
    for (int i = pos + len - 1; i < n; i++)
    {
        s[i - len] = s[i];
    }
    return s;
}

字符串截取

char* SubString(char* s, int pos, int len)
{
    char* sub_s = (char*)malloc((len + 1) * sizeof(char));
    int n = strlen(s);
    int i = 0;
    while (i < len && pos - 1 + i < n) {
        sub_s[i] = s[pos - 1 + i];
        i++;
    }
    sub_s[i] = '\0';
    return sub_s;
}

字符串连接

char* StrConcat(char* s, char* t)
{
    int n = strlen(s);
    int m = strlen(t);
    for (int i = 0; i < m; i++)
    {
        s[n + i] = t[i];
    }
    return s;
}

字符串比较

#define min(a, b) ((a) < (b) ? (a) : (b))
int StrCompare(char* s, char* t)
{
    int len = min(strlen(s), strlen(t));
    int i = 0;
    while (i < len && s[i] == t[i]) {
        i++;
    }
    if (i == len) {
        if ((int)strlen(s) > len) {
            return 1;
        } else if ((int)strlen(t) > len) {
            return -1;
        } else {
            return 0;
        }
    } else if (s[i] > t[i]) {
        return 1;
    } else {
        return -1;
    }
    return 0;
}

字符串的链式存储结构

\\节点定义
struct Char {
    char c;
    struct Char* next;
};

struct String {
    struct Char* head;
    size_t length;
};

字符串插入

void StrInsert(struct String* s, int pos, struct String* t)
{
    int flag = 1;
    if (s->length > 0) {
        struct Char* tail = t->head;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        if (s->length > 0) {
            struct Char* p = s->head;
            int count = 1;
            while (p != NULL && count < pos - 1) {
                p = p->next;
                count++;
            }
            if (count == pos - 1) {
                tail->next = p->next;
                p->next = t->head;
            } else if (pos == 1) {
                tail->next = s->head;
                s->head = t->head;
            } else {
                flag = 0;
            }
        } else {
            s = t;
        }
    }
    if (flag != 0) {
        s->length = s->length + t->length;
    }
}

字符串删除

void StrRemove(struct String* s, int pos, int len)
{
    if (s->length > 0) {
        struct Char* p = s->head;
        int count = 1;
        while (p != NULL && count < pos - 1) {
            p = p->next;
            count++;
        }
        struct Char* deleted;
        if (pos == 1 || (p != NULL && count == pos - 1)) {
            if (pos == 1) {
                deleted = s->head;
            } else {
                deleted = p->next;
            }
        } else {
            return;
        }
        count = 0;
        while (deleted != NULL && count < len) {
            struct Char* t = deleted;
            deleted = deleted->next;
            free(t);
            count++;
            s->length = s->length - 1;
        }
        if (pos == 1) {
            s->head = deleted;
        } else {
            p->next = deleted;
        }
    }
}

链式字符串截取

struct String* SubString(struct String* s, int pos, int len)
{
    struct String* sub_s = (struct String*)malloc(sizeof(struct String));
    struct Char* tail;
    if (s->length > 0)
    {
        struct Char* p = s->head;
        int count = 1;
        while (p != NULL && count < pos) {
            p = p->next;
            count++;
        }
        if (p != NULL && count == pos) {
            count = 0;
            sub_s->head = (struct Char*)malloc(sizeof(struct Char));
            tail = sub_s->head;
            while (p != NULL && count < len) {
                struct Char* t = (struct Char*)malloc(sizeof(struct Char));
                tail->next = t;
                tail = tail->next;
                sub_s->length++;
                p = p->next;
                count++;
            }
        }
    }
    tail = sub_s->head;
    sub_s->head = tail->next;
    free(tail);
    return sub_s;
}

字符串连接

void StrConcat(struct String* s, struct String* t)
{
    if (s->length > 0) {
        struct Char* p = s->head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = t->head;
    }
    s->length = s->length + t->length;
}

字符串比较

int StrCompare(struct String* s, struct String* t)
{
    struct Char* sp = s->head;
    struct Char* tp = t->head;
    while (sp!=NULL&&tp!=NULL&&sp->c == tp->c) {
        sp = sp->next;
        tp = tp->next;
    }
    if (sp != NULL && tp == NULL) {
        return 1;
    }else if (sp == NULL&&tp !=NULL) {
        return -1;
    }
    else if (sp == NULL && tp == NULL) {
        return 0;
    } else if (sp->c > tp->c) {
        return 1;
    } else {
        return -1;
    }
    return 0;
}