【4.1】字符串基本概念

字符串示例:

s1=“123”
s2=“ABBABBC”
s3=“BB”
4=“BB ”
s5=“Hello World!”
s5=“”

字符串: 特殊的 线性表，即元素为 字符 的线性表

n ( ≥ 0 ) 个字符的有限序列，n ≥ 1时，一般记作 S : “c0c1c2…cn-1”

• S 是串名字
• “c0c1c2…cn-1”是串值
• ci 是串中的字符
• N 是串长(串的长度):一个字符串所包含的字符个数
• 空串:长度为零的串，它不包含任何字符内容(注意 与 空格串“ ”的区别)

一、字符串是一种特殊的线性结构

数据对象：

• 无特殊限制
• 串的数据对象为字符集

基本操作：

• 线性表的大多以“单个元素”为操作对象
• 串通常以“串的整体”作为操作对象

线性表的存储方法同样适用于字符串 – 应根据不同情况选择合适的存储表示

二、字符/符号

• 字符 (char) :组成字符串的基本单位
• 取值依赖于字符集 Σ(同线性表，结点的有限 集合)
• 二进制字符集:Σ = {0,1}
• 生物信息中 DNA 字符集:Σ = {A,C,G,T} – 英语语言: Σ = {26个字符，标点符号}
• ……

字符编码

单字节(8 bits)

• 采用 ASCII 码对 128 个符号进行编码
• 在C和C++中均采用

其他编码方式

• GB
• CJK
• UNICODE

字符编码顺序

• 为了字符串间比较和运算的便利，字符编码表 一般遵循约定俗成的“偏序编码规则”
• 字符偏序:根据字符的自然含义，某些字符间 两两可以比较次序
• 其实大多数情况下就是字典序
• 中文字符串有些特例，例如“笔划”序

三、字符串的数据类型

因语言而不同 ：

• 简单类型
• 复合类型

字符串常数和变量：

• 字符串常数(string literal)
• 例如: “\n”, “a”, “student”…
• 字符串变量

子串(Substring)

子串定义 ：

假设 s1，s2 是两个串:

s1 = a0a1a2…an-1

s2 = b0b1b2…bm-1

其中0≤m ≤n,若存在整数i(0≤i ≤n-m)，使得 bj =ai+j, j= 0,1,…,m-1 同时成立，则称 串 s2 是串 s1 的 子串，s1 为串 s2 的主串， 或称s1包含串s2

特殊子串：

• 空串是任意串的子串
• 任意串S都是S本身的子串
• 真子串:非空且不为自身的子串

字符串的基本运算

C 标准函数库需要

#include <string.h>

求串长  int strlen(char *s);
串复制  char *strcpy(char *s1, char*s2);
串拼接   char *strcat(char *s1, char *s2);
串比较 (注意)
  int strcmp(char *s1, char *s2);
  看 ASCII 码，s1>s2，返回值 > 0;两串相等，返回 0
定位  char *strchr(char *s, char c);
右定位   char *strrchr(char *s, char c);
求子串   char *strstr(const char *str1, const char *str2);

定位函数示例

• 寻找字符 o, strchr(s,’o’) 结果返回 4
• 反方向寻找 r, strrchr(s,’o’) 结果返回 7

String抽象数据类型

C++标准字符串类库

#include <string> 
using namespace std;

字符串类(class String)

• 适应字符串长度动态变化的复杂性
• 不再以字符数组 char S[M] 的形式出现，而采用一 种动态变长的存储结构

C++ String 部分操作列表：

得到字符串中的字符：

重载下标运算符[ ]

char& string::operator [] (int n);

按字符定位下标

int string::find(char c,int start=0);

反向寻找，定位尾部出现的字符

int string::rfind(char c, int pos=0);

四、思考

1. 判断哪些是”software”的子串

• 空串、software、soft、oft…
• fare、sfw…

2. 若字符串 s =“software”，则其子串的数目为?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾