串的基本概念和存储结构

基本概念

串是字符串的简称,是由零个或多个字符组成的有限序列

串中字的个数n称为串的长度。n=0时的串称为空串(用表示)。

串中任意个连续的字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。某个符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度相等且每个对应位置的字符都相等时,称这两个串是相等的。

例如,有串A= ‘China Beijing’,B = ‘Beijing’,C = ‘China’,则它们的长度分别为13,7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。

存储结构

定长顺序存储

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储申值的字符序列

1
2
3
4
5
6
7
8
9
#define MAXLEN 255//预定义最大申长为255

typedef struct(//每个分量存储一个字符

char ch [MAXLEN];//中的实际长度

int length;

}SString;

用这种方法声明的串的最大长度不能超过MAXLEN,否则超出的部分会被截断

二是串的最后会有一个结束标记字符“\0”

堆分配存储

堆分配存储表示仍然以一组地址连续的存储单元存放申值的字符序列,但它们的存储空间是在程序执行过程中动态分配得到的。

1
2
3
4
5
6
7
typedef struct{

char *ch;//按串长分配存储区,ch指向串的基地址

int length;//串的长度

)SString;

在C语言中,存在一个称之为“堆”的自由存储区,并用malloc()和free()函数来完成动 态存储管理。利用malloc()为每个新产生的事分配一块实际串长所需的存储空间,若分配成功, 则返回一个指向起始地址的指针,作为串的基地址,这个串由ch指针来指示:若分配失败,则返回NULL。已分配的空间可用free()释放掉

块链存储

类似于线性表的链式存储结构,也可采用链表方式存储串值。由于串的特殊性(每个元素只 有一个字符),在具体实现时,每个结点既可以存放一个字符,也可以存放多个字符。每个结点称为块,整个链表称为块链结构。

串的基本操作

转载原链接

1.求串长StrLength(s)
操作条件:串s 存在
操作结果:求出串s 的长度。

2.串赋值StrAssign(s1,s2)
操作条件: s1 是一个串变量,s2 或者是一个串常量,或者是一个串变量(通常s2 是一个串常量时称为串赋值,是一个串变量称为串拷贝)。
操作结果:将s2 的串值赋值给s1, s1 原来的值被覆盖掉。

3.连接操作:StrConcat (s1,s2,s) 或StrConcat (s1,s2)
操作条件:串s1,s2 存在。
操作结果:两个串的联接就是将一个串的串值紧接着放在另一个串的后面,连接成一个串。前者是产生新串s,s1 和s2 不改变; 后者是在s1 的后面联接s2 的串值,s1 改变, s2不改变。
例如: s1="he",s2=" bei",前者操作结果是s="he bei";后者操作结果是s1="he bei"。

4.求子串SubStr (s,i,len):
操作条件:串s 存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。
操作结果:返回从串s 的第i 个字符开始的长度为len 的子串。len=0 得到的是空串。
例如:SubStr("abcdefghi",3,4)= "cdef"

5.串比较StrCmp(s1,s2)
操作条件:串s1,s2 存在。
操作结果:若s1==s2,操作返回值为0;若s1<s2, 返回值<0;若s1>s2, 返回值>0。

6.子串定位StrIndex(s,t):找子串t 在主串s 中首次出现的位置
操作条件:串s,t 存在。
操作结果:若t∈s,则操作返回t 在s 中首次出现的位置,否则返回值为-1。
如:StrIndex("abcdebda","bc")=2
StrIndex("abcdebda","ba")=-1

7.串插入StrInsert(s,i,t)
操作条件:串s,t 存在,1≤i≤StrLength(s)+1。
操作结果:将串t 插入到串s 的第i 个字符位置上,s 的串值发生改变。

8.串删除StrDelete(s,i,len)
操作条件:串s 存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。
操作结果:删除串s 中从第i 个字符开始的长度为len 的子串,s 的串值改变。

9.串替换StrRep(s,t,r)
操作条件:串s,t,r 存在,t 不为空。
操作结果:用串r 替换串s 中出现的所有与串t 相等的不重叠的子串,s 的串值改变。以上是串的几个基本操作。其中前5个操作是最为基本的,它们不能用其他的操作来合成,因此通常将这5个基本操作称为最小操作集。