串

串的定义

串，即字符串(String)，是由零个或者多个字符组成的有限序列。一般记为S=’$a_{1}$$a_{2}$···$a_{n}$’(n>=0)
其中，S是串名，单引号括起来的字符序列是串的值；$a_{i}$可以是字母、数字或者其他字符；串中字符的个数n称为串的长度。n=0时的串称为空串(用$\emptyset$表示)

例：T=’iPhone 17 Pro Max?’

  • 子串：串中任意个连续的字符组成的子序列

    ‘iPhone’,’Pro M’是串T的子串

  • 主串：包含子串的串

    T是子串’iPhone M’的主串

  • 字符在主串的位置：字符在串中的序号

    ‘1’在T中的位置是8(第一次出现)

  • 子串在主串的位置：子串的第一个字符在主串中的位置 (位序从1)

    ‘11 Pro’在T的位置是8

  • 空串 VS 空格串：

    M=’’ (空串)
    N=’ ‘ (空格串，由三个空格字符组成)

  • 串 VS 线性表
    串是一种特殊的线性表，数据元素之间呈线性关系
    串的数据对象限定为字符集(如中文字符、英文字符、数字字符、标点字符等)
    串的基本操作，如增删改查等通常以子串为操作对象

串的基本操作

假设有串T=’’,S=’iPhone 17 Pro Max?’,W=’Pro’

  • StrAssign(&T,chars):赋值操作。把串T赋值为chars
  • StrCopy(&T,S):复制操作。由串S复制得到串T
  • StrEmpty(S):判空操作。若S为空串，则返回TRUE，否则返回FALSE
  • StrLength(S):求串长。返回串S的元素个数
  • ClearString(&S):清空操作。将S清为空串
  • DestroyString(&S):销毁串。将串S销毁(回收存储空间)
  • Concat(&T,S1,S2):串链接。用T返回由S1和S2链接成的新串

    执行基本操作Concat(&T,S,W),后T=’iPhone 17 Pro Max?Pro’

  • SubString(&Sub,S,pos,len):用Sub返回串S第pos个字符起长度为len的子串

    执行SubString(&T,S,4,6)后，T=’one 17’

  • Index(S,T):定位操作。若主串S中存在串值与串T相同的子串，则返回他在主串S中第一次出现的位置；否则函数值为0

    执行基本操作Index(S,T),返回值为11

  • StrCompare(S,T):比较操作，若S>T,则返回值>0;若S=T,则返回值=0；若S<T,则返回值<0

    从第一个字符开始往后依次对比，先出现更大的字符的串更大
    长串的前缀与短串相同，长串更大
    只有两个串完全相同，才相等

字符集编码

y=f(x)
字符集：函数定义域
编码：函数映射规则f
y：对应的二进制数

任何数据存到计算机中一定是二进制数。
需要确定一个字符和二进制数的对应规则，这就是编码
“字符集”：

英文字符：ASCII字符集
中英文：Unicode字符集

基于同一个字符集，有多个编码方案，如UTF-8，UTF-16

采用不同的编码方式，每个字符占空间不同，考研时只需默认每个字符占1B即可

知识回顾与重要考点

串的存储结构

串的顺序存储

1
2
3
4
5
#define MAXSIZE 255
typedef struct{
    char ch[MAXSIZE];
    int length;
}SString;//静态数组存储(定长顺序存储)
1
2
3
4
5
6
7
8
#define MAXSIZE 255
typedef struct{
    char *ch;//按串长分配存储区，ch指向串的基地址
    int length;
}HString//动态数组实现(堆分配存储)
HString S;
S.ch=(char*)malloc(sizeof(char));
S.length=0;
  1. 方案1：专门定义一个length变量存放字符串的长度
  2. 方案2：ch[0]充当length
  3. 方案3：没有length变量，以字符’\0’表示结尾
  4. 方案4：放弃ch[0],专门声明length存放长度

串的链式存储

1
2
3
4
typedef struct StringNode{
    char ch;
    struct StringNode *next;
}StringNode,*String//存储密度低，每个字符1B，每个指针4B

提高存储密度

1
2
3
4
typedef struct StringNode{
    char ch[4];//若最后一节结点存不满，可以用一些特殊字符填满
    struct StringNode *next;
}StringNode,*String;//存储密度提高

基本操作的实现

求子串

SubString(&Sub,S,pos,len)
用Sub返回串S中从第pos个字符开始长度为len的子串 

1
2
3
4
5
6
7
8
bool SubString(SString &Sub,SString S,int pos,int len){
    if(pos+len-1>S.length)return false;//子串范围越界
    for(int i=pos;i<pos+len-1;i++){
        Sub.ch[i-pos+1]=S.ch[i];
    }
    Sub.length=len;
    return true;
}

比较操作

StrCompare(S,T)
比较操作，若S>T,返回值>0,若S=T,返回值=0,若S<T,返回值<0

1
2
3
4
5
6
bool StrCompare(SString S,SString T){
    for(i=1;i<=S.length&&i<=T.length;i++){
        if(S.ch[i]!=T.ch[i])return S.ch[i]-T.ch[i]
    }
    return S.length-T.length;
}

定位操作

Index(S,T)若主串S中存在与串T串值相等的子串，则返回他在主串S中第一次出现的位置;否则函数值为0；

1
2
3
4
5
6
7
8
9
10
int Index(SString S,SString T){
    int i=1,m=S.length,n=T.length;
    SString sub;
    while(i<=n-m+1){
        SubString(sub,S,i,n);
        if(StrCompare(sub,T)!=0)++i;
        else return i;
    }
    return 0;
}

知识回顾与重要考点