串、数组和广义表
串、数组和广义表
串：内容受限的线性表
数组、和广义表：线性结构的推广
串（string）
零个或多个任意字符组成的有限序列s(串名)="a1a2a3a4...an(串值) 串长n"
子串：串中任意个连续字符组成的子序列（含空串）称为该串的子串。
例如，“abcde”的子串有
“”，“a”,"ab","abc","adcd"和“abcde”等
真子串是指不包含自身的所有子串
主串：包含子串的串相应的称为主串
字符位置：字符在序列中的序号为该字符在串中的位置
子串位置：子串第一个字符在主串中的位置
空格串：有一个或多个空格组成的串，与空串不同
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的
串的顺序存储结构
优点：操作方便
缺点：存储密度低
存储密度=串值所占的存储/实际分配的存储
可以将多喝字符存放在一个节点中，以克服其缺点
串的模式匹配运算
算法目的
确定主串中所含的子串（模式串）第一次出现的位置（定位）
算法应用
搜索引擎、拼写检查、语言翻译、数据压缩
算法种类
- BF算法(Brute-Force，又称古典的、经典的、朴素的、穷举的)
- KMP算法（特点：速度快）
Brute-Force
简称简单匹配算法，采用穷举法的思路
package main
import "fmt"
func IndexBF(s string, t string) int {
i := 0
j := 0
for i < len(s) && j < len(t) {
fmt.Println(s[i:i+1], t[j:j+1], i, j)
if s[i:i+1] == t[j:j+1] { // 如果母串的字母等于子串的 则进行下一个的比较
i++
j++
} else { // 否则回溯 从母串的下一个开始比较
i = i - j + 1
j = 0
}
}
fmt.Printf("%d-----%d\n", j, i)
if j >= len(t) { // 当子串的指针等于子串长度则存在
return i - len(t)
}
return 0
}
func main() {
s1 := "asdasdjahsgdkashjdgakdha"
s2 := "dha"
res := IndexBF(s1, s2)
fmt.Println(res)
}
时间复杂度O(n*m)
KMP（Kunth Morris Pratt）算法
利用已经部分匹配的结果而加快模式串的滑动速度
且主串S的指针I不必回溯！可提速到0（n+m）
数组
按一定格式排列起来的具有相同类型的数据元素的集合。
一维数组
若线性表中的数据元素为非结构的简单元素则称为一维数组
一维数组的逻辑结构
线性结构，定长的线性表
声明格式
数据类型 变量名称【长度】
next := [...]int{1, 2, 3, 4, 5, 6}
二维数组
若一维数组中的数据元素又是一堆数组结构，则称为二维数组
二维数组的逻辑结构
- 非线性结构：每一个数据元素即在一个行列表中又在一个列列表中
- 线性结构定长的线性表：该线性表的每个数据元素也是一个定长的线性表
doubleArray := [][]int{{1, 2, 3}, {2, 2, 2}, {2, 3, 4}}
矩阵
由m*n个元素拍成的m行n列的表
矩阵的常规存储
将矩阵描述成一个二维数组
矩阵的常规存储的特点
- 可以对其元素进行随机存储
- 矩阵运算非常简单；存储密度为1
不适宜常规存储的矩阵
值相同的元素很多且呈现某种规律分布；零元素多
矩阵的压缩存储
为多个相同的非零元素只分配一个存储空间；对零元素怒不分配空间
特殊矩阵的压缩存储
什么是压缩存储
若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间
什么样的矩阵能够压缩
一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
什么叫稀疏矩阵
矩阵中非零元素的个数较少（一般小于5%）
矩阵压缩
对称矩阵
特点：在n*n的矩阵a中，满足如下性质aij=aji(1<=i,j<=n)
1 5 1 3 7
5 0 8 0 0
1 8 9 2 6
3 0 2 5 1
7 0 6 1 3
存储方法：只存储下（或者上）三角（包括主对角线）的数据元素。共占用n(n+1)/2个元素空间
对称矩阵的存储结构：
对称矩阵上下三角中的元素数均为
n(n+1)/2
可以以行序为主序将元素存放在一个一维数组sa[n(n+1)/2]中例如
sa=[1,5,0,1,8,9,3,0,2,5,1 ...]
ann的在一维数组中的位置
ann是第n行 那他前面有n-1行，前面有在这一行他前面有n-1个元素，他前面所有的元素和是1+2+3+4+....(j-1)=(1+j-1)*(j-1)/2=j*(j-1)/2 首项+末项*项数/2
三角矩阵
特点：对角线以下或以上的数据元素（不包括对角线）全部为常数C
存储方法：重复元素c共享一个元素空间，共占用n(n+1)/2+1个元素怒空间sa[1.....n(n+1)/2+1 ]
对角矩阵
特点：
在n*n的方针中，所有非零元素怒都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有 三对角矩阵、五对角矩阵、七对角矩阵等
稀疏矩阵
设在M*N的矩阵中有t个非零元素，
三元组顺序表又称为 有序的双下标法。
三元组顺序表的优点：非零元素在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算
三元组顺序表的缺点：不能随机存取。若按照行号存取某一行中的非零元素，则需要从头开始进行查找
广义表
又称lists是N>=0个元素A0,A1,A2,A3…An-1 的有限序列，其中每一个ai或者是元素，或者是一个广义表