17 | 数据结构（下）：大整数实战，提升 Shift-And 算法能力

胡光

你好，我是胡光，咱们又见面了。
上节课呢，我们讲了大整数表示法的相关知识，并且给你演示了大整数加法及乘法处理过程。其实，你是否掌握了大整数表示法是次要的，主要是你可以在这个过程中，认识到数据结构的作用，也就是我强调的数据结构就是负责表示数据。
原先，我们之所以无法做较大整数的运算，那是因为我们所掌握的数据类型，无法表示很大的数字，有了大整数表示法以后，我们就可以做特别特别大的整数表示了。
我之前也一直在说，算法是做数据计算的，它和数据结构是程序设计中非常重要的两部分。既然是两部分，说明算法和数据结构可以独立分开设计。
关于这点呢，你可以想想上节课我们学的大整数加法，它其实就是算法。为什么这么说呢？你想想，这个加法过程难道是有了大整数以后，才出现的么？显然不是，即使没有大整数表示法，我们还是了解加法过程的，只不过这一次我们用大整数表示法，模拟了加法过程。因此，加法过程是一个独立的算法过程。
总而言之，就是在之前的课程中，我们确定了这样一个结论：如果是计算流程不合理，我们需要改进算法；如果是数据表示受限，我们需要求助于数据结构。
为了让你更清晰地认识到，算法和数据结构是两个可以独立设计的部分，今天我们通过一个具体的算法，来感受一下这个独立设计的过程。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文介绍了数据结构中的大整数实战和 Shift-And 算法的应用。作者首先强调了数据结构的重要性，指出算法和数据结构可以独立设计。然后介绍了字符串匹配问题，重点讨论了单模匹配问题，并给出了暴力匹配算法的程序代码。接着引入了 Shift-And 算法，解释了其基本流程和信息转换过程。在 Shift-And 算法中，模式串的信息被转换成二进制编码，实现了高效的单模匹配。整体而言，本文通过具体的算法实例，展示了算法和数据结构的独立设计，以及 Shift-And 算法在字符串匹配问题中的应用，为读者提供了深入理解数据结构和算法的机会。 Shift-And 算法通过信息转换和位运算实现了高效的字符串匹配，将模式串的信息转换成二进制编码，从而提升了匹配效率。文章还提到了 Shift-And 算法的时间复杂度优势，相比暴力匹配算法，其时间复杂度为 O(n + m)，在处理长度较长的模式串时表现出更高的效率。此外，文章还提出了改进 Shift-And 算法的思路，通过增加支持更大二进制整数表示的数据结构，实现对更长模式串的匹配处理。通过本文的学习，读者可以深入理解算法和数据结构的独立设计，以及等价信息表示对问题解决的重要性。文章内容涵盖了算法设计、数据结构优化以及计算思维等方面的知识，对读者的编码能力训练具有一定的指导意义。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《人人都能学会的编程入门课》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(9)

最新
精选

徐洲更
改进Shift-And算法的思考: 数据结构的底层有两种想法， 1. 用数组，每个数组用0和1表示 2. 用字符串，用长度位N的01的字符串表示但是C语言是不支持运算重载的，也就是位运算的符号是不能套用在新的数据结构，因此得要创建新的函数对应原来的位操作。算法思想不变，但是代码形式会发生改变。
作者回复: 没错！说的完全正确！还有一种解决方法，其实可以尝试开长度为 n 的整型数组，每一个整型对应于 30 位 2 进制位。
2020-02-22
3
4
1043
胡老师这门课不仅仅就是编程入门的能力，可以说学懂了这个编程入门课就是进入了编程高手所要必须要掌握的终极技能的大门槛，再华丽、精深的编程技巧都是由优美的算法思维和结构协调的数据结构所组成。思维清晰、逻辑严谨、结构有序一直是编程进阶基础的基本功，唯有练好基本功，才能筑起更高、更稳的“大厦”。胡老师用入门这个简洁的语言告诉你：万丈高楼平地起，再牛的编程高手也得从这里、这个方向开始努力进阶的，这个入门接口是进入编程世界唯一不变的“高速公路的收费门岗”。
作者回复: d(^_^o)
2020-04-13

3
奕
虽然Shift-And算法搞懂了，但是一般是想不到的
作者回复: 嗯，这需要很多看似无关的基础算法思维，才有可能做到创造这种算法，其中还包括了编译原理相关算法思维。d(^_^o)
2020-02-22

2
Modern
哇，非常精彩，对于这个算法我的语义化理解是，p中的1从低位到高位移动的过程，每一次能够前进，就说明了当前位置的字符与模式串同一位置的字符相同，到达了m位置后就说明了每个位置都检查了一遍，都相同，于是就是完全匹配上了
作者回复: Yes！理解的非常到位！d(^_^o)
2020-03-23

1
许童童
Shift-And算法很不错哦。
作者回复: (｡ì _ í｡)
2020-02-22

1
罗耀龙@坐忘
茶艺师学编程 1、文中的bruce_force例子和shift_and算法例子，我自己跑，都是内存溢出结果······ 2、思考题，我硬着头皮做，心里知道这肯定是错的······ 代码如下： #include <stdio.h> typedef struct BIGP{ int p[1000]; } ; int shift_and(const char *str, const char *p_str){ int code[256] = {0}, m = 0; for (int i = 0; p_str[i]; i++, m++){ code[p_str[i]] |= (1 << i); } struct BIGP PP; int pp.p = {0}; for (int i = 0; str[i]; i++){ pp.p = (pp.p << 1| 1) & code[str[i]]; if (pp.p & (1 << (m - 1)))return 1; } return 0; } int main(){ struct BIG PP; const char *str, *p_str; scanf("%s %s", str, p_str); printf("%s", shift_and(str, p_str)); return 0; }
2020-08-07

1
look for
作业： #include <stdio.h> #define SIZE 100 int arr[SIZE]; // 定义一个表示二进制大整数的数组 // 转化为二进制大整数表示 int *convert_to_big_int(int num) { // 每次都重新初始化二进制大整数数组 for (int i = 0; i < SIZE; i++) { arr[i] = 0; } int count = 0; if (num == 0) { arr[0] = 0; return arr; } do { arr[++count] = num % 2; num = num / 2; } while (num != 0); arr[0] = count; return arr; } // 二进制大整数左移一位 void big_int_left_move_one(int *arr) { if (arr[0] == 0) { arr[0] = 1; arr[1] = 1; return; } arr[0] += 1; for (int i = arr[0]; i > 1; i--) { arr[i] = arr[i - 1]; } arr[1] = 0; } // 二进制大整数或1操作 void big_int_or_one(int *arr) { arr[1] = 1; if (arr[0] == 0) { arr[0] = 1; } } // 二进制大整数进行与操作 void big_int_and(int *a, int *b) { int flag = 0; for (int i = a[0]; i > 0; i--) { if (a[i] && b[i]) { a[i] = 1; // 判断是否是第一次进入，第一次进入则设置a[0]的长度 if (!flag) { a[0] = i; flag = 1; } } else { a[i] = 0; } } // 判断之前是否与成功过，若没与成功过，则设置a[0]=0 if (!flag) { a[0] = 0; } } // 进行shift_and算法匹配 int shift_and(const char *str, const char *p_str) { int code[256] = {0}; int m = 0; // 初始化每一个字符的编码 for (int i = 0; p_str[i]; i++, m++) { code[p_str[i]] |= (1 << i); } int p[SIZE] = {0}; for (int i = 0; str[i]; i++) { // p = (p << 1 | 1) & code[str[i]]; int *stri = convert_to_big_int(code[str[i]]); // 把code[str[i]]进行二进制大整数表示 big_int_left_move_one(p); // p左移一位 big_int_or_one(p); // p或上1 big_int_and(p, stri); // p进行与运算 // 如果p所对应的模式串的最高位为1，代表匹配成功 if (p[m]) { return 1; } } return 0; }
2022-10-27归属地：山东


马建华
遍历字符串为何可以把循环写为“for (int i = 0; text[i]; i++)”？这里text[i]表示的是数字还是字符？
2021-03-27


doge
typedef struct BigInt { char *Int; int high; int size; } BigInt; BigInt* BigIntLeftShiftN(BigInt* pbi, int n) { if (!pbi) return pbi; if (!pbi->high && !pbi->Int[0]) return pbi; if (n + pbi->high > pbi->size) { DBG("Error happens, number bit exceed"); return NULL; } int moveN = pbi->high + 1; pbi->high += n; for (int i = pbi->high; moveN > 0; i--, moveN--) { pbi->Int[i] = pbi->Int[i - 1]; } for (--n; n >= 0; n--) { pbi->Int[n] = 0; } return pbi; } BigInt* BigIntAnd(BigInt *target, const BigInt* src) { if (!target || !src) { return target; } if (!src->high && !src->Int[0]) { target->high = 0; target->Int[0] = 0; return target; } int flag = 1; for (int i = target->high; i >= 0; i--) { target->Int[i] = target->Int[i] & src->Int[i]; if (flag) { if (!target->Int[i]) { target->high--; } else { flag = 0; } } } return target; } int BigIntShiftAnd(const char* text, const char* pat) { if (!text || !pat || !strlen(text) || !strlen(pat) || strlen(text) < strlen(pat)) return -1; int len = (int)strlen(pat); BigInt** code = CodeInit(len); if (!code) return -1; for (int i = 0; pat[i]; i++) { code[(int)pat[i]]->high = i; code[(int)pat[i]]->Int[i] = 1; } BigInt* ret = BigIntGet(len); if (!ret) { CodeFree(code, len); return -1; } int pos = -1; for (int i = 0; text[i]; i++) { ret = BigIntLeftShiftN(ret, 1); ret->Int[0] = 1; ret = BigIntAnd(ret, code[(int)text[i]]); if (ret->high == len - 1 && ret->Int[ret->high] > 0) { pos = i - len + 1; break; } } CodeFree(code, len); return pos; } 程序尝试这写出来了，验证好像没问题，就是感觉空间开销有点大。希望老师指点。评论空间有限，省略了初始化函数和销毁函数。
2020-09-29



收起评论