对于整体知识架构比较重要的概念:
串的元素只能是字符;
数组中的元素是线性表;
广义表中的元素又是广义表。
严格来说,数组和广义表不是线性结构,他们是线性结构的推广。
由于串很少进行插入和删除操作,所以顺序存储结构更常用。
注:块的英文单词为chunk.
由于串的算法在高级语言中都学过,下面主要讲解串的模式匹配算法.
模式(子串)匹配BF算法
举例说明
注意:串结构中的数组的[0]位置并没有存储元素,而是从[1]位置开始存储的,所以这里的i和j都是从1开始。
回溯:匹配失败后,i=i-j+2,可以分为两步理解,首先是i-j-1让i退回到刚才起点的位置,然后+1,是到刚才起点的下一个位置。
算法思想总结
算法描述
串结构中的数组的[0]位置并没有存储元素,而是从[1]位置开始存储的,所以这里的i和j都是从1开始。
如果需要从任意位置pos开始查找
疑问倒数第二行代码if语句中是否不用加=号?
时间复杂度分析
最好时m,最坏是n*m,分析如下:
举例说明next[j]的情况
KMP算法描述
其中,T代表模式串,S代表主串。
上面没看懂 老师说的是:该算法比较难理解,能看懂,会用就行。
一维数组的存储方式和地址
二维数组的存储方式和地址
例题
4.稀疏矩阵
三元组法的特点:
三元组法的缺点,不能随机存取,首先在存的时候只能顺序存入,没有存前面的元素,就不会知道现在这个元素应该存在哪儿。其次,在取值的时候,只能从头到尾的搜索该值的信息。
补充:随机存取、顺序存取
1、随机存取就是直接存取,可以通过下标直接访问到元素的位置,与存储位置无关,时间复杂度永远为O(1),例如数组。存取第N个数据时,不需要访问前(N-1)个数据,直接就可以对第N个数据操作 (array)。
2、顺序存取,不能通过下标访问,在存取第N个数据时,必须先访问前(N-1)个数据 ,例如链表。
老师并没有讲代码,之后自己学习
原子:单一元素
广义表通常用链表来存储
程序实现:
// 线性结构_串_模式(子串)匹配问题_病毒感染.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include<stdlib.h> using namespace std; typedef struct { char ch[11]; int length; }SString; void CreatS(SString& S) { int i = 1; while(1) { cin >> S.ch[i]; //输入字符时,一定要用空格隔开,不然就是字符串了。 i++; if (cin.get() == '\n') break; } S.length = i-1; } void DoubleS(SString& S) { for (int i = 1; i <= S.length; i++) { S.ch[i + S.length] = S.ch[i]; } S.length = S.length * 2; } SString GetSS(SString& T, int n) { SString T_temp; for (int i = 1; i <= T.length/2; i++) { T_temp.ch[i] = T.ch[n]; n++; } T_temp.length = T.length / 2; return T_temp; } bool index_BF(SString S, SString& T) { DoubleS(T); for (int n = 0; n < T.length / 2; n++) { SString T_temp = GetSS(T, n); int i = 1; int j = 1; while (i <= S.length && j <= T_temp.length) { if (S.ch[i] == T.ch[j]) { i++; j++; } else { i = i - j + 2; j = 1; } } if (j >= T_temp.length) { return true; break; } } return false; } void Show(SString S) { for (int i = 1; i <= S.length; i++) { cout << S.ch[i] << " "; } cout << endl; } int main() { SString S, T; CreatS(S); CreatS(T); cout << "输入结果:" << endl; Show(S); Show(T); cout <<"是否感染:"<< index_BF(S, T); }