内容纲要

串的概念及其特性:

  • 串是n( >= 0 ) 个字符的有限序列,记作:S = “c1c2c3…cn”。S是串名字, “c1c2c3…cn” 是串值,ci是串中字符,n是串的长度,n=0是空串。其中的” “与””不同,长度为3的空白串,长度为0的空串。
  • 串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。
  • 通常将子串在主串中首次出现时,该子串首字符对应的主串中的序号,定义为子串在主串中的位置。
  • 空串是任意串的子串,任意串是其自身的子串。
  • 通常在程序中使用的串可分为两种:串变量和串常量。

C语言中字符串操作:

  • 字符串初始化char str[n](包含\0所占位,中文字符占2位)
  • 单个字符串的输入函数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)
最后修改日期:2020年4月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。