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

精选留言

• 
  徐洲更

  2020-02-22 10:57:38

  改进Shift-And算法的思考:
  数据结构的底层有两种想法，
  1. 用数组，每个数组用0和1表示
  2. 用字符串，用长度位N的01的字符串表示
  
  但是C语言是不支持运算重载的，也就是位运算的符号是不能套用在新的数据结构，因此得要创建新的函数对应原来的位操作。
  
  算法思想不变，但是代码形式会发生改变。
  

  作者回复

  没错！说的完全正确！
  还有一种解决方法，其实可以尝试开长度为 n 的整型数组，每一个整型对应于 30 位 2 进制位。

  2020-02-22 19:24:18

• 
  1043

  2020-04-13 23:03:45

  胡老师这门课不仅仅就是编程入门的能力，可以说学懂了这个编程入门课就是进入了编程高手所要必须要掌握的终极技能的大门槛，再华丽、精深的编程技巧都是由优美的算法思维和结构协调的数据结构所组成。思维清晰、逻辑严谨、结构有序一直是编程进阶基础的基本功，唯有练好基本功，才能筑起更高、更稳的“大厦”。胡老师用入门这个简洁的语言告诉你：万丈高楼平地起，再牛的编程高手也得从这里、这个方向开始努力进阶的，这个入门接口是进入编程世界唯一不变的“高速公路的收费门岗”。

  作者回复

  d(^_^o)

  2020-04-14 23:53:37

• 
  奕

  2020-02-22 18:03:41

  虽然Shift-And算法搞懂了，但是一般是想不到的

  作者回复

  嗯，这需要很多看似无关的基础算法思维，才有可能做到创造这种算法，其中还包括了编译原理相关算法思维。d(^_^o)

  2020-02-22 19:50:32

• 
  罗耀龙@坐忘

  2020-08-07 16:54:25

  茶艺师学编程
  
  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;
  }
• 
  Modern

  2020-03-23 08:49:18

  哇，非常精彩，对于这个算法我的语义化理解是，p中的1从低位到高位移动的过程，每一次能够前进，就说明了当前位置的字符与模式串同一位置的字符相同，到达了m位置后就说明了每个位置都检查了一遍，都相同，于是就是完全匹配上了

  作者回复

  Yes！理解的非常到位！d(^_^o)

  2020-03-23 16:42:56

• 
  许童童

  2020-02-22 14:11:01

  Shift-And算法 很不错哦。

  作者回复

  (｡ì _ í｡)

  2020-02-22 19:30:41

• 
  look for

  2022-10-27 16:09:46

  作业：
  
  #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;
  }
• 
  马建华

  2021-03-27 03:26:48

  遍历字符串为何可以把循环写为“for (int i = 0; text[i]; i++)”？ 这里text[i]表示的是数字还是字符？
• 
  doge

  2020-09-29 15:09:25

  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;
  }
  程序尝试这写出来了，验证好像没问题，就是感觉空间开销有点大。希望老师指点。评论空间有限，省略了初始化函数和销毁函数。