串

串–零个或多个字符组成的有限序列
串的模式匹配
1,BF算法

#include <stdio.h> 
#include <stdlib.h>
int Strlength(char n1[256])
{int i;for(i = 1;n1[i] != '\0';i ++);return i - 1;
}
int Cha(char n1[],char n2[])
{int i = 1,j = 1;while(i <= n1[0] && j <= n2[0]){if(n1[i] == n2[j]){i ++;j ++;}else{i = i - j + 2;//回溯j = 1;}}if(j > n2[0]){return i - n2[0];}else{return 0;}
}
int main()
{char n1[256];char n2[256];printf("请输入主串:");scanf("%s",&n1[1]);n1[0] = Strlength(n1);printf("请输入字串:");scanf("%s",&n2[1]);n2[0] = Strlength(n2);int j = Cha(n1,n2);if(j == 0){printf("查找失败");}else{printf("位置:%d\n",j);}}

KMP算法
求next[]数组的值

KMP算法的实现

#include <stdio.h>
#include <stdlib.h>
typedef unsigned char String[256];
int GetLength(String s)
{int i;for(i = 0;s[i] != '\0';i ++);return i - 1;} 
void GetNext(String b,int next[])
{int j = 1,k = 0;next[j] = k;while(j < b[0]){if(k == 0 || b[j] == b[k]){j ++;k ++;next[j] = k;}else{k = next[k];}}
}
int Index(String a,String b,int next[])
{int i = 1,j = 1;while(i <= a[0] && j <= b[0]){if(j == 0 || a[i] == b[j]){j ++;i ++;}else{j = next[j];}}if(j > b[0]){return i - b[0];}else{return 0;}
}
int main()
{String a,b;int next[100];printf("请输入主串:");scanf("%s",&a[1]);a[0] = GetLength(a);printf("请输入字串:");scanf("%s",&b[1]); b[0] = GetLength(b);GetNext(b,next);if(Index(a,b,next)){printf("找到:%d\n",Index(a,b,next));}else{printf("没有找到\n");}
}

数组

一维数组:连续存储的同类型元素的集合
特点;
1,随机存取
2,长度不能改变

二维数组:每个元素受两个关系的约束，及行和列
内存中的存储(顺序开辟一块连续的空间存储)
1,行优先存储
2,列优先存储
行优先存储元素的位置(二维数组最后一个元素amn)
已知a11,aij = LOC(a11) + ((i - 1) * n + j - 1) * L
同理
列优先存储元素的位置
aij = LOC(a11) + ((j - 1) * m + i - 1)*L
例题

方法一LOC(2)(2) = LOC(0)(0) + (2 - 0) * n(一行有几个) + 2 - 0 = 676
n = 15,同理A33 = 692
方法二:0.0,1.1,2.2,3.3用二维数组表示的时候都在一条对角线上
a22 -a00 = 32,而33，到22是一个所以 676 + 32 / 2 = 692

矩阵的压缩存储

凝魂三问
为啥要压缩?
因为矩阵会出现0，而把矩阵存储在内存中，还要为0开辟空间，这样就有点浪费空间了，所以要压缩存储
啥叫压缩存储??
为多个相同的非o元素只分配一个存储空间，对0元素不分配空间
啥样的矩阵能够压缩？？？
对称矩阵，对角矩阵，稀疏矩阵等
矩阵的压缩代码

#include <stdio.h>
#define M 2
#define N 2 
#define MAX 100
typedef int ElemType;
typedef struct YuSan{int i;int j;ElemType v;
}YuSan;
typedef struct Arrays{int H;int l;int count;YuSan data[MAX + 1];
}Arrays;
void Insi(Arrays &t,ElemType arr[M][N])
{t.H = M;t.l = N;t.count = 0;int m,n;for(m = 0;m < t.H;m ++){for(n = 0;n < t.l;n ++){if(arr[m][n] != 0){t.count ++;t.data[t.count].i = m + 1;t.data[t.count].j = n + 1;t.data[t.count].v = arr[m][n];}}}}
void DisPlay(Arrays t)
{printf("总行数:%d\t总列数:%d\t总个数:%d\n",M,N,t.count);int k;printf("行数\t列数\t数值\n");for(k  =1;k <= t.count;k ++){printf("%d\t%d\t%d\n",t.data[k].i,t.data[k].j,t.data[k].v);}
}
void ZhuanZhi(Arrays a,Arrays &b)
{b.H = a.l;b.l = a.H;b.count = a.count;int m,n,k = 0;for(n = 1;n <= a.l;n ++){for(m = 1;m <= a.count;m ++){if(a.data[m].j == n)//用数组的列数和输出的列数比较，第1列，会变成第1行 {k ++;b.data[k].i = a.data[m].j;b.data[k].j = a.data[m].i;b.data[k].v = a.data[m].v;}}}
}
int main()
{ElemType arr[M][N];Arrays t;Arrays b;printf("请输入:\n");int m,n;for(m = 0;m < M;m ++){for(n = 0;n < N;n ++){scanf("%d",&arr[m][n]);}}Insi(t,arr);DisPlay(t);printf("转置后:\n");ZhuanZhi(t,b);DisPlay(b);
}

广义表