免责声明：
创新互联服务项目包括梁园网站建设、梁园网站制作、梁园网页制作以及梁园网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，梁园网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到梁园省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
- 笔记来源：本系列所有笔记均整理自 B站·王道考研·数据结构 视频教程。
- 参考书籍：《2021年数据结构考研复习指导》，王道论坛所著，电子工业出版社出版，ISBN ：9787121379819。
目录
1 串的定义与实现 1.1 串的定义串是字符串的简称。由有限个字符组成的序列。记作S = 'a1a2a3...an'。
有些语言使用双引号表示字符串，比如 Java，C，C++；有些语言使用单引号表示字符串，如 Python。
串是一种特殊的线性表，只不过串的操作对象是子串：
基于方案四（数组第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位系统中）来存储一个指针，这样存储密度低。可以一个节点存储多个字符的方式来提高存储密度，最后一个节点没有存满的话可以使用一些特殊的字符填充进去。
串的定义方案：字符数组的第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）：
朴素模式匹配算法的缺点：普通的朴素模式匹配算法就是一种暴力匹配算法，当某些模式串与目标子串能够部分匹配时，主串的扫描指针i经常需要回退，增加时间开销。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧