线性结构 - 串小结

串String，一般又可以被称为字符串，是由0个或多个字符组成的有限序列。

一般表示为：S="a1a2a3...an"。其中，S是串的名字，双引号作为串的界定符用来表示串的内容，即串值；ai(0<=i<=n)代表串中的单个元素，n表示串的个数，当n为0时，被称为空串，

空白串和空串的区别，空白串是由一个或多个空格组成的串。

串的形式理论

子串

串中任意几个连续的字符组成的子序列，称为该串的子串

主串

包含子串的串被称为主串

子串的位置

子串在主串中首次出现时，该子串的首字符对应在主串中的序号，即为子串在主串中的位置

例如：A="This is String"，B="is"
B是A的子串。B在A中出现了2次，首次出现所对应的主串位置是3，因此，B在A中的位置为3
PS：空串是任意串的子串，任意串是其自身的子串

前缀和后缀 prefixes and suffixes

前缀：假设字符串S是字符串T的前缀，如果存在一个字符串U满足条件T = SU。如果U是非空的，则S是T的一个合适的前缀
后缀：假设字符串S是字符串T的后缀，如果存在一个字符串U满足条件T = US。如果U是非空的，则S是T的一个合适的后缀

旋转

串S = UV可以被说成T的旋转，如果T = VU；例如：当U = 00110， V = 01的时候，串0011001是0100110的旋转

逆转

串的逆转是指具有相同符号单顺序相反的字符串。例如：如果S = abc， S的逆转就是cba。

如果一个字符串与逆转后的字符串相同的话，称为回文。
比如：S="madam"，逆转后还是"madam"

串的特性

串中存在序列，说明串的相邻字符之间具有前驱和后继的关系。

串的存储结构

顺序存储：用一组地址连续的存储单元来存储串中的字符序列。与线性表的顺序存储类似，一般定义一个长数组

typedef struct {
    char ch[MAXSIZE]; /* MAXSIZE 存储字符串的最大长度 */
    int length;
}String;

链式存储：与线性表的链式存储也是相似的，但是由于串结构的特殊，结构中的每一个元素是一个字符，如果也用链表来存储串值，一个结点对应一个字符，就会造成很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用”#“或其他非串值字符补全

typedef struct Link{
    char ch[LinkNum]; /* LinkNum 每个结点最多可存储的个数 */
    struct Link *next;
}link, * String;

串的基本操作（顺序存储）

1. 初始化

Status strAssign(String *S, char *s) {
    
    if (strlen(s) > MAXSIZE) {
        return ERROR;
    }else {
        S->length = (int)strlen(s);
        for (int i = 0; i < S->length; i++) {
            S->ch[i] = *(s + i);
        }
    }
    return TRUE;
}

2. 清空串

Status clearString(String *S) {
    S->length = 0;
    return TRUE;
}

3. 判断串是否为空

Status isEmpty(String S) {
    return S.length == 0 ? TRUE : FALSE;
}

4. 串的长度

int lengthOfString(String S) {
    return S.length;
}

5. 串的遍历

void traverseString(String S) {
    for (int i = 0; i < S.length; i++) {
        printf("%c", S.ch[i]);
    }
    printf("\n");
}

6. 返回串第pos个起长度为len的子串

Status subString(String *Sub, String S, int pos, int length) {
    // 如果位置或者长度不合法，则为空串
    if (pos < 0 || pos > S.length || length < 1 || length > S.length) {
        Sub->length = 0;
        return ERROR;
    }
    for (int i = 0; i < length; i++) {
        Sub->ch[i] = S.ch[pos + i];
    }
    Sub->length = length;
    return TRUE;
}