数组和字符串中的数据结构和算法（上）

入门题看string match

两种比较容易实现的字符串实现算法，
假设在长度n的母串中匹配长度为m的字符串
1 暴力求解：顺序遍历母串，将每个字符作为匹配的起始字符，判读是否匹配字串。算法复杂度m*n。
代码的讲解，在注释中

#include 
#include 
#include 
using namespace std;int main()
{char* StrStr(const char* str, const char* target){if (!*target)//判断是否为空，c语言判断字符串为空，一般是取一个星号，跟\0比较，{return str;}char* p1Begin = p1, * p2 = (char*)target;//p1,p2两个指针，p1begin相当于临时存储了p1的位置，p2永远指向target开始的位置while (p1 && p2 && *p1 == *p2)//p1存在，p2存在，并且两个值相等。{p1++;p2++;}if (!*p2)//如果说p2走到了末位，就代表有{return p1Begin;//此时p1已经走完了}p1 = p1Begin + 1;//p1这个字符串默认向后走一个return NULL;}
}

2 Rabin-Karp
Rabin-Karp算法的思想：

假设子串的长度为M,目标字符串的长度为N
计算子串的hash值
计算目标字符串中每个长度为M的子串的hash值（共需要计算N-M+1次）
比较hash值
如果hash值不同，字符串必然不匹配，如果hash值相同，还需要使用朴素算法再次判断

d取字符集的个数
#define d 256 /*  S  -> Search SequenceT  -> Target Sequenceq  -> A prime number
*/
void search(char* S, char* T, int q) {int M = strlen(S);int N = strlen(T);int i, j;int SHashValue = 0;  // hash value for Search Sequenceint THashValue = 0;  // hash value for Target Sequenceint h = 1;           // h 的计算公式：pow(d, M-1) % q//计算hfor (i = 0; i < M - 1; i++)h = (h * d) % q;// Calculate the hash value of Search Sequencefor (i = 0; i < M; i++){SHashValue = (d * SHashValue + S[i]) % q;THashValue = (d * THashValue + T[i]) % q;}// Slide the pattern over text one by one for (i = 0; i <= N - M; i++) {// Chaeck the hash values of current T and S// If the hash values match then only check for characters on by oneif (SHashValue == THashValue) {/* Check for characters one by one */for (j = 0; j < M; j++) {if (txt[i + j] != pat[j])break;}if (j == M) {    // if SHashValue == THashValue and S[0...M-1] = T[i, i+1, ...i+M-1]cout << "Pattern found at index " << i << endl;}}// Calulate hash value for next text: Remove leading digit, // add trailing digit           if (i < N - M){THashValue = (d * (THashValue - T[i] * h) + T[i + M]) % q;// We might get negative value of THashValue, converting it to positiveif (THashValue < 0)THashValue = (THashValue + q);}}
}

如果我们要在 ASCII 字符集范围内查找“搜索词”，由于 ASCII 字符集中有 128 个字符，那么 M 就等于 128，比如我们要在字符串 “abcdefg” 中查找 “cde”，那么我们就可以将搜索词 “cde” 转化为“("c"的码点 * M + "d"的码点) * M + "e"的码点 = (99 * 128 + 100) * 128 + 101 = 1634917”这样一个数值。

分析一下这个数值：1634917，它可以代表字符串 “cde”，其中：

代表字符 “c” 的部分是“ "c"的码点 * (M 的 n - 1 次方) = 99 * (128 的 2 次方) = 1622016”

代表字符 “d” 的部分是“ "d"的码点 * (M 的 n - 2 次方) = 100 * (128 的 1 次方) = 12800”

代表字符 “e” 的部分是“ "e"的码点 * (M 的 n - 3 次方) = 101 * (128 的 0 次方) = 101”

（n 代表字符串的长度）

我们可以随时减去其中一个字符的值，也可以随时添加一个字符的值。

“搜索词”计算好了，那么接下来计算“源串”，取“源串”的前 n 个字符（n 为“搜索词”的长度）”abc”，按照同样的方法计算其数值： ("a"的码点 * M + "b"的码点) * M + "c"的码点 = (97 * 128 + 98) * 128 + 99 = 1601891

然后将该值与“搜索词”的值进行比较即可。比较发现 1634917 与 1601891 不相等，则说明 “cde” 与 “abc” 不匹配，则继续向下寻找，下一步应该比较 “cde” 跟 “bcd” 了，那么我们如何利用前一步的信息呢？首先去掉 “abc” 的数值中代表 a 的部分： (1601891 - "a"的码点 * (M 的 n - 1 次方)) = (1601891 - 97 * (128 的 2 次方)) = 12643

然后再将结果乘以 M（这里是 128），再加上 “d” 的码点值不就成了 “bcd” 的值了吗：

12643 * 128 + "d"的码点 = 1618304 + 100 = 1618404

这样就可以继续比较 “cde” 和 “bcd” 是否匹配，以此类推。

Array

int array[arraysize]//在堆上定义长度为arraysize的整型数组。
int *array=new int [arraysize]

Stack （栈）VS heap（堆）

stack 主要是由操作系统自动管理的空间，当进入一个函数后，操作系统会为函数函数自动分配存储空间，当函数返回时，系统会弹出内存块，根据指针回到前一个内存块，所以，栈总是以后进先出的工作方式工作
heap是用来储存动态分布的存储空间，程序员可以进行手动的对内存进行分配和回收，否则会引起内存泄漏

二维数组

好处是可以通过下标去访问元素，数组这种数据结构不适合分拣元素，如果想要分拣元素，那么应该使用vector元素，对于vector的访问元素，后面博客会给出用法。

Hash table

哈希表（HashTable）又叫做散列表，是根据关键码值（即键值对）而直接访问的数据结构。也就是说，它通过把关键码映射到表中一个位置来访问记录，以加快查找速度

拉链法

它是通过一种辅助的数据结构，把相同的元素进行连接起来，例如John Smith 和Sandra Dee哈希值相同，把 Sandra Dee链接到了John Smith的后面，这种方式实现比较简单，但是它的空间利于率是小于下面的线性搜索法的

线性搜索法

线性搜索法就是这个意思，如图示，如果有两个哈希值相同的情况下，例如，John Smith 和Sandra Dee
对应的哈希值都为152，那么Sabdra Dee就会往后走，自动寻找空位，就行补齐

参考文章：
https://blog.csdn.net/seacowtech/article/details/79256299

https://blog.csdn.net/iva_brother/article/details/82253989

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！