[TOC]

串、数组和广义表

串（字符串string）

是一个内容受限的线性表（只能存放字符）
子串

例如abcd的的子串

“ ” “a” “ab” ……..
子串在主串当中的位置
所有的空串都是相等的
一般选用顺序的

串的顺序实现

typedef struct SString{
    char ch[MAXSIZE];
    int Length;
}SString;

串的链式实现

优点

操作方便
缺点

存储密度较低

块链的是实现

typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk* next;
}Chunk;

typedef struct LString{
    Chunk *head,*tail;
    int curlen;
}LString;

串的模式匹配算法

BF算法

时间复杂度为O(n*m)

代码示例



typedef struct SString {
    char ch[MAXSIZE];
    int Length;
} SString;

status InitString(SString *string) {
    memset(string->ch, 0, MAXSIZE);
    scanf("%s", string->ch);
    string->Length = strlen(string->ch);
    return OK;
}

int BFMatchingAlorithm(SString *string, char *str) {
    int len = string->Length;
    int i = 0, j = 0;
    while (i < string->Length && j < strlen(str)) {
        if (string->ch[i] == str[j]) {
            ++i;
            ++j;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == strlen(str)) {
        return i - j;
    }
    return -1;
/*    for (int i = 0,j=0; i < len; ++i) {
        if(string->ch[i]==str[j]){
            while(j< strlen(str)&&string->ch[i]!='\0'){
                if(string->ch[i]!=str[j]){
                    i=i-j+1;
                    j=0;
                    break;
                }
                i++;
                j++;
            }
            if(j== strlen(str)){
                return i-j;
            }
        }
    }
    return -1;*/
}

int main() {
    SString string;
    int sub = 0;
    char str[10];
    InitString(&string);
    scanf("%s", str);
    sub = BFMatchingAlorithm(&string, str);
    printf("%d", sub);
    return 0;
}

注意事项
- 注意回溯的i的计算公式

KMP算法

计算next的值
- 第一个元素next为0
- 第二个元素next比较前面一个元素，就是1
- 其他元素比较前缀的子串

数组

定长的线性表
相同的元素
结构是固定
三维数组的存储

例如arr[i][j][k]
- arr[x][y][z]
  
  意思就是说，第z页的第x,y号元素
  
  内存为arr+z*x*y+x*y+y
稀疏矩阵的存储

采用三元法(i,j,元素)

既是只存放有元素的位置
三角矩阵

采用的是存一边的方法
对称矩阵

采用三角矩阵的存法