三. 串与矩阵

一. 串

• 字符串大多使用堆分配存储, 堆由C语言的动态分配函数malloc和free来管理.

typedef struct{
    char *ch;
    int length;
}HString;
//高度类似SqList, 除了去掉了maxsize;

串的模式匹配

问题: s.find(t), 返回的是index, 如果是-1, 代表找不到;
注意: 很多算法默认是str[0]存放str.length, 因此要留心;

1. Brutal Force算法

• 其复杂度为O(n*m) (n=len(s), m=len(t))

2. KMP算法

• next函数 #这个算法没啥太好解释的, 就是用来找回溯的位置. 一般来说, 最起码要掌握next函数的规律;

get_next(T, next[])
i = 1, next[1]=0, j=0
while i<len(T):
    if (j ==0 || T[i]==T[j]):
        i+=1
        j+=1
        if (T[i]!=T[j]): next[i] = j
        else: next[i] = next[j]
    else: 
        j = next[j]  #j的值退回去;

• 参考输入:
  abbbabc #下标从1开始,
  0111003 #next[j] = 0, 意味着本位已经不用再与第一位比较, 可以直接看下一位了;

---

KMP(s, t, pos, next)  #next数组已经计算完成了
i = pos
j = 1
while (i<=len(s) and j<=len(t)):
    if j==0 or s[i] == t[j]:
        i+=1
        j+=1
    else:
        j = next[j]  #get the next position to check, 回溯
if j>len(t): 
    return i-len(t)  #return begin index
else: 
    return -1  #not found

• 改进的next函数

二. 矩阵

• 稀疏矩阵
  • 使用三元组(i, j , e)来存储
    • 三元组的顺序表

typdef struct {
int i, j; //坐标
ElemType e;  //元素
}

- 三元组的十字链表(三元组结点再加两个域, 一个存储同行的下一个, 一个存储列的下一个), 同时在整个表上补上两个指针, 一个是ColHead, 一个是RowHead;