内容纲要
串
串的概念及其特性:
- 串是n(>= 0)个字符的有限序列,记作:S = c1c2c3…cn。S是串名字, c1c2c3…cn 是串值,ci是串中字符,n是串的长度,n=0是空串。其中的空串与空白串不同," "长度为3的空白串,""长度为0的空串。
- 串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。
- 通常将子串在主串中首次出现时,该子串首字符对应的主串中的序号,定义为子串在主串中的位置。
- 空串是任意串的子串,任意串是其自身的子串。
- 通常在程序中使用的串可分为两种:串变量和串常量。
C语言中字符串操作:
- 字符串初始化char strn
- 单个字符串的输入函数gets(str)
- 字符串输出函数puts(str)
- 字符串求长度函数strlen(str)(不包括\0与分界符)
- 字符串连接函数strcat (str1, str2)
- 字符串比较函数strcmp (str1, str2)从头开始逐个比较其ASCII码
自定义字符串数据类型:定长顺序存储表示,堆分配存储表示,块链存储表示。
顺序串:使用静态分配的字符数组存储字符串中的字符序列。字符数组的长度预先用MAXSTRLEN 指定,一旦空间存满不能扩充。
堆式串:字符数组的存储空间是通过malloc( )函数动态分配的。串的最大空间数MAXSTRLEN 和串中实际字符个数length保存在串的定义中。可以根据需要,随时改变字符数组的大小。
堆式串的运算
- 初始化空串算法initString (Hstring &S)
- 提取子串算法subString ( HString& s, int pos, int len )
- 串的连接算法concat ( HString &s, HString &t )
代码实现:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXSTRLEN 256
typedef struct {
char* ch; //串的存储数组
int maxSize; //串数组的最大长度
int length; //串的当前长度
} HString;
void initString(HString& s)
{
s.ch = (char*)malloc(MAXSTRLEN * sizeof(char));
if (s.ch == NULL) exit(1); //判断分配成功与否
s.ch[0] = '\0'; //置空串
s.maxSize = MAXSTRLEN; //置串的最大字符数
s.length = 0; //实际字符数置0
}
HString subString(HString& s, int pos, int len)
{
HString t;//创建子串
t.ch = (char*)malloc(MAXSTRLEN * sizeof(char));
t.maxSize = MAXSTRLEN;
if (pos < 0 || len < 0 || pos + len - 1 >= s.maxSize){//参数错误返回空串
t.length = 0;
t.ch[0] = '\0';
}else{
if (pos + len - 1 >= s.length)
len = s.length - pos;
for (int i = 0, j = pos; i < len; i++, j++)
t.ch[i] = s.ch[j]; //复制子串的字符
t.length = len; t.ch[len] = '\0';
}
return t; //返回复制的子串
}
void concat(HString& s, HString& t)
{
int i;
if (s.length + t.length <= s.maxSize) {//s可以容纳
for (i = 0; i < t.length; i++){
s.ch[s.length++] = t.ch[i];
}
s.length += t.length;
s.ch[s.length] = '\0';
}
else {//存储空间不足
char* str = s.ch;
s.maxSize = s.length + t.length;
s.ch = (char*)malloc(sizeof(char) * s.maxSize);
strcpy(s.ch, str);//复制原来串的数据
concat(s, t);//递归
free(str);
}
}
块链串:使用单链表作为字符串的存储表示。链表的每个结点可以存储1 个字符,称其“块的大小”为1,也可以存储n 个字符,称其“块的大小”为n。存储密度=串值所占的存储位/实际分配的存储位;显然,存储密度越高,存储利用率越高。块链存储表示一般带头结点,设置头、尾指针。
串的模式匹配:
- 简单算法(朴素算法、BF算法)O(n*m)
- 首尾匹配算法O(n*m)
- KMP算法O(n)
时间复杂度分析:(n为主串长度,m为模式串长度)
模式匹配 | 最好情况 | 最坏情况 | 平均情况 | 空间复杂度 |
---|---|---|---|---|
朴素算法 | O(1) | O((n-m+1)*m) | O(n*m) | O(1) |
KMP算法 | O(n+m) | O(n) | O(m) |
留言