第四章串

数据结构第四章串，什么是串？串中的内容可以是？子串是串中任意个连续字符构成的子序列，有兴趣的可以看看哟。

第四章串

• 1、定义
• 2、基本操作
  • StrAssign(&T，chars)
  • StrCopy(&T,S)
  • StrEmpty(S)
  • StrLength(S)
  • ClearString(&s)
  • DestoryString(&s)
  • Concat(&T,s1,s2)
  • SubString(&sub,s,i,len)
• 3、字符集编码：每个字符对应一个二进制数，字符大小的比较其实就是比较二进制数的大小
• 4、串的存储结构
  • 顺序存储
    • 串顺序存储抽象数据类型定义
      • 静态数组实现（定长顺序存储）
      • 动态数组实现（堆分配存储）
    • 顺序存储的优缺点
  • 链式存储
    • 抽象数据类型定义
    • 结合链表思考优缺点
  • 基本操作如何实现
• 5、串的模式匹配算法
  • 什么事字符串的模式匹配
    • 在主串中找到与模式串相同的子串，并返回其所在的位置
  • 朴素模式匹配算法
    • 算法思想
    • 最坏时间复杂度
  • KMP
    • KMP算法
    • next数组
    • KMP进一步优化
      • 优化思路
    • nextval数组
    • KMP优化前后区别

第四章串

• 1、定义
• 2、基本操作
  • StrAssign(&T，chars)
  • StrCopy(&T,S)
  • StrEmpty(S)
  • StrLength(S)
  • ClearString(&s)
  • DestoryString(&s)
  • Concat(&T,s1,s2)
  • SubString(&sub,s,i,len)
• 3、字符集编码：每个字符对应一个二进制数，字符大小的比较其实就是比较二进制数的大小
• 4、串的存储结构
  • 顺序存储
    • 串顺序存储抽象数据类型定义
      • 静态数组实现（定长顺序存储）
      • 动态数组实现（堆分配存储）
    • 顺序存储的优缺点
  • 链式存储
    • 抽象数据类型定义
    • 结合链表思考优缺点
  • 基本操作如何实现
• 5、串的模式匹配算法
  • 什么事字符串的模式匹配
    • 在主串中找到与模式串相同的子串，并返回其所在的位置
  • 朴素模式匹配算法
    • 算法思想
    • 最坏时间复杂度
  • KMP
    • KMP算法
    • next数组
    • KMP进一步优化
      • 优化思路
    • nextval数组
    • KMP优化前后区别