数据结构之串代码实现

一 、串的概念

字符串简称串，是一种特殊的线性表，它的数据元素仅由一个字符组成。

二 、串的定义

串(String)是由零个或多个字符组成的有限序列，又称字符串。其中s是串名,用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成串的基本单位，i是它在整个串中的序号；n为串的长度,表示串中所包含的字符个数。

三 、串的常用术语

1. 长度–串中字符的个数，称为串的长度。
2. 空串–长度为零的字符串称为空串。
3. 空格串–由一个或多个连续空格组成的串称为空格串。
4. 串相等–两个串相等，是指两个串的长度相等且对应的字符都相等。
5. 自串–串中任意连续的字符组成的子序列称为该串的子串。
6. 主串–包含子串的串为该子串的主串。
7. 模式匹配–子串的定位运算又称为模式匹配，是一个求子串的队医给字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式。

四 、串的表示

串是数据元素类型为字符型的线性表，所以用于线性表的存储方式仍适合与串。但是由于串中的数据元素是单个字节，其存储方式又有其特殊之处。

五 、串的代码实现

1. 程序头部

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR -1

typedef int Status;
typedef struct {
    char *ch;
    int len;
} Str;

2. 串的初始化

Status StrInit(Str* str) {
    str->len = 0;
    str->ch = NULL;
    return OK;

}

3. 清空串中的内容

Status ClearStr(Str* str) {
    if (str->ch) {
        free(str->ch);
        str->ch == NULL;
    }
    str->len = 0;
    return OK;
}

4. 给串赋值

Status StrAssign(Str* str, char* ch) {

    if (str->ch) {
        free(str->ch);
        str->ch = NULL;
    }
    int len = 0;
    char *c = ch;
    while (*c) {
        ++len;
        ++c;
    }
    if (len == 0) {
        str->ch = NULL;
        str->len = 0;
        return OK;
    } else {
        str->ch = (char *) malloc(sizeof(char) * (len + 1));
        if (str->ch == NULL) {
            return ERROR;
        } else {
            c = ch;
            for (int i = 0; i < len; ++i, ++c) {
                str->ch[i] = *c;
            }
            str->len = len;
            return OK;
        }
    }
}

5. 两个字符串连接成一个字符串

Status Concat(Str* str1, Str* str2, Str* str) {
    if (str->ch) {
        free(str->ch);
        str->ch = NULL;
    }
    str->ch = (char *) malloc((str1->len + str2->len + 1) * sizeof(char));
    if (!str->ch) {
        return ERROR;
    }
    int i = 0, j = 0;
    while (i < str1->len) {
        str->ch[i] = str1->ch[i];
        ++i;
    }
    while (j < str2->len) {
        str->ch[i + j] = str2->ch[j];
        ++j;
    }
    str->ch[i + j] = '\0';
    str->len = str1->len + str2->len;
    return OK;
}

6. 求主串的子串，从指定位置截取指定的长度字符串

Status GetSubString(Str* str, int pos, int len, Str* SubStr) {
    if (pos < 0 || pos > str->len || len < 0 || len > str->len - pos) {
        return ERROR;
    }
    if (SubStr->ch) {
        free(SubStr->ch);
        SubStr->ch = NULL;
    }
    if (len == 0) {
        SubStr->ch = NULL;
        SubStr->len = 0;
        return OK;
    } else {
        SubStr->ch = (char *) malloc((len + 1) * sizeof(char));
        int i = pos, j = 0;
        while (i < pos + len) {
            SubStr->ch[j] = str->ch[i];
            ++i;
            ++j;
        }
        SubStr->ch[j] = '\0';
        SubStr->len = len;
        return OK;
    }
}

7. 程序主函数

int main() {
    Str *str1 = (Str *) malloc(sizeof(Str));
    Str *str2 = (Str *) malloc(sizeof(Str));
    Str *str3 = (Str *) malloc(sizeof(Str));
    Str *str4 = (Str *) malloc(sizeof(Str));
    Str *substr = (Str *) malloc(sizeof(Str));
    StrInit(str1);
    StrInit(str2);
    StrInit(str3);
    StrInit(str4);
    StrInit(substr);

    char ch1[] = "I LOVE China!";
    char ch2[] = "I LOVE YOU!";
    char ch3[] = "Data structure!";

    StrAssign(str1, ch1);
    StrAssign(str2, ch2);
    StrAssign(str3, ch3);

    Concat(str1, str2, str4);
    GetSubString(str3, 5, 9, substr);
    printf("字符串为:%s\t字符串的长度为:%d\n", str1->ch,str1->len);
    printf("字符串为:%s\t字符串的长度为:%d\n", str2->ch,str2->len);
    printf("字符串为:%s\t字符串的长度为:%d\n", str3->ch,str3->len);
    printf("字符串为:%s\t字符串的长度为:%d\n", str4->ch,str4->len);
    printf("字符串为:%s\t字符串的长度为:%d\n", substr->ch,substr->len);

    return 0;
}

程序运行结果：