第四章串-创新互联

免责声明：

创新互联服务项目包括梁园网站建设、梁园网站制作、梁园网页制作以及梁园网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，梁园网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到梁园省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

• 笔记来源：本系列所有笔记均整理自 B站·王道考研·数据结构 视频教程。
• 参考书籍：《2021年数据结构考研复习指导》，王道论坛所著，电子工业出版社出版，ISBN ：9787121379819。

目录

1 串的定义与实现 1.1 串的定义

串是字符串的简称。由有限个字符组成的序列。记作S = 'a1a2a3...an'。

• 子串：由任意个字符组成的有序序列
• 主串：包含子串的串
• 串的长度：串中包含的字符个数（空格也是一个有效字符，空串长度为0）
• 子串在主串中的位置：子串第一个字符在主串中第一次出现的位置
• 串相等：两个串的长度相等，且每个位置的字符也相等

有些语言使用双引号表示字符串，比如 Java，C，C++；有些语言使用单引号表示字符串，如 Python。

串是一种特殊的线性表，只不过串的操作对象是子串：

1.2 串的存储结构 顺序存储

基于方案四（数组第0个位置），使用静态数组实现串的顺序结构及其操作：

#includenamespace TEST2 {#define MAXLEN 255 // 串的大长度
	// 串的顺序存储
	// 使用一个额外的成员来记录串的实际长度

	// 静态数组方式实现
	struct StaticSeString {char str[MAXLEN]; // 使用静态数组存储串中的字符
		int length; // 串的长度
	};

	typedef StaticSeString String;

	// 动态态数组方式实现
	struct DynamicSeString {char* str; // 使用动态分配内存方式，根据串的长度分配内存
		int length; // 串的长度
	};


	// 求子串
	bool SubString(const String& string, String& sub, int pos, int len) {if (pos + len - 1 >string.length) {	// 所求子串越界
			return false;
		}
		for (int i = pos; i< pos + len; i++) {	// 从数组第1个位置开始存，第0个位置空出
			sub.str[i - pos + 1] = string.str[i];
		}
		sub.length = len;
		return true;
	}
	// 比较两个字符串，s1>s2 返回正数，s1for (int i = 1; i<= s1.length && i<= s2.length; i++) {	if (s1.str[i] != s2.str[i]) {		return s1.str[i] - s2.str[i];
			}
		}
		// 执行到此，说明较短的字符串对比结束，因此较长的字符串比较大
		return s1.length - s2.length;
	}
	// 子串定位
	int SubIndex(const String& parent, const String& child) {String temp; // 暂存从主串中取出的子串
		int i = 1;
		int n = parent.length; // 主串的长度
		int m = child.length; // 子串的长度
		while (i<= n - m + 1) {	SubString(parent, temp, i, m); // 取子串
			// 取出的子串不等于目标子串
			if (CompareString(temp, child)) {		// 继续从下一个位置重新取子串
				i++;
			}
			else {		// 找到了
				return i;
			}
		}
		return 0; // 没有找到
	}
	
	// 通过C风格字符串初始化
	void InitString(String& s, const char str[]) {int i = 0;
		char ch;
		do {	ch = str[i];
			s.str[i + 1] = ch; // 第0个位置空闲
			i++;
		} while (ch != '\0'); // C风格字符串以 \0 结束
		s.length = i - 1; // 注意实际长度
	}

	void PrintString(const String& s) {for (int i = 1; i<= s.length; i++) {	std::cout<< s.str[i];
		}
		std::cout<< std::endl;
	}

}

int main() {using std::cout;
	using std::endl;
	using namespace TEST2;

	String s1;
	InitString(s1, "zhangjian");
	PrintString(s1);

	String s2;
	InitString(s2, "nn");
	PrintString(s2);

	cout<< SubIndex(s1, s2)<< endl;

}

链式存储

一个节点存储一个字符，还要使用4字节的空间（32位系统中）来存储一个指针，这样存储密度低。可以一个节点存储多个字符的方式来提高存储密度，最后一个节点没有存满的话可以使用一些特殊的字符填充进去。

2 串的模式匹配

串的定义方案：字符数组的第0个位置闲置出，从第1个位置开始存储字符，额外使用一个成员来存储串的长度。

朴素模式匹配算法

模式匹配，也就是子串定位操作。若主串S中存在与串T相同的子串C，则返回其在主串S中的位置（从1开始），否则返回0；

算法思想：从主串中，取出与目标子串长度相同的子串，与之逐一字符匹配，若出现不一致的字符，即跳过本轮匹配，取下一子串进行匹配；若主串中待比较字符数小于子串长度，即定位失败。

// 朴素模式匹配算法
	int SimpleSubIndex(const String& parent, const String& child) {int k = 1; // 子串在主串中的位置
		int i = k; // 主串中当前比较的字符位序
		int j = 1; // 子串中当前比较的字符位序
		// k<= parent.length -  child.length + 1 ：如果主串剩余未匹配字符数小于目标子串长度，表示匹配失败，无需进行逐一字符比较
		while (k<= parent.length - child.length + 1 && i<= parent.length && j<= child.length) {	// 逐一字符比较
			if (parent.str[i] == child.str[j]) {		// 比较下一个字符
				++i;
				++j;
			}
			else {		k++; // 下一个子串
				i = k; // 重置主串中当前比较的字符位序
				j = 1; // 重置子串中当前比较的字符位序
			}
		}
		if (j >child.length) {	return k;
		}
		else {	return 0;
		}

	}

算法时间复杂度（主串长度n，子串长度m）：

• 最坏的情况：每次取出匹配的子串前（m-1）个字符都相同，第 m 个字符不同，时间复杂度为 O(n - m +1) * n ，约等于 O(m * n)
• 较好的情况：每次取出的子串第一个字符与目标子串都匹配失败

朴素模式匹配算法的缺点：普通的朴素模式匹配算法就是一种暴力匹配算法，当某些模式串与目标子串能够部分匹配时，主串的扫描指针i经常需要回退，增加时间开销。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：第四章串-创新互联
本文链接：http://jkwzsj.com/article/ceechs.html