文章目录
字符串
顺序串：用数组来存储串中的字符序列
具体类型定义
#define MAXSIZE 100
typedef struct
{
char str[MAXSIZE];
int length;
}seqstring;
链接串：用链接存储结构来存储串
字符串的模式匹配
模式匹配指的是寻找字符串p在字符串t中首次出现的起始位置，其中p为模式,t为正文，t的长度远远大于p的长度
模式匹配—BF算法
综上：普通模式匹配效率较低
模式匹配—KMP算法
KMP算法next向量计算方法
数组
二维数组映射方式
- 按行优先
- 按列优先
特殊矩阵-压缩存储
对称矩阵
三角矩阵
- 上三角
- 下三角
对角矩阵
三对角矩阵又叫做带状矩阵
注意这里从0开始
稀疏矩阵-压缩存储
三元组表
按行优先逐个记录，先左后右，先上后下
是否对应惟一的稀疏矩阵？
不是，不知道是按行优先还是按列优先
typeodef struct{
int data[100][100];
int m,n;
}matrix;
typedef int spmatrix[100][3];
void compressmatrix(matrix A,spmatrix B)
{
int i,k=1;//第一行
for(i=0;i<A.m;i++)
for(j=0;j<A.n;j++)
if(A.data[i][j]!=0){
B[k][0]=i;
B[k][1]=j;
B[k][2]=A.data[i][j];
k++;
}
B[0][0]=A.m;//行数，列数，非0元素的总个数存储
B[0][1]=A.n;
B[0][2]=k-1;
}
十字链表
递归
递归出口：规模小到一定程度
最简单的例子
void print(int n)
{
if(n>0)
{
printf("%d:",n);
printf("How are you\n");
print(n-1);
}
}
- 循环迭代：自底向上
- 递归：自顶向下
复杂递归程序到非递归程序的转换
递归
#define MAXSIZE 20
typedef int listarr[MAXSIZE];
void listorder(listarr list,int left,int right)
{
int mid;
if(left<=right)
{
mid=(left+right)/2;
printf("%4d",list[mid]);
listorder(list,left,mid-1);
listorder(list,mid+1,right);
}
}
非递归：听不懂，以后来补笔记
递归函数，求数组中的最大数
int max(int a[],int left,int right)
{
int lmax,rmax,mid;
if(left==right){
//只含有一个元素
return a[left];
}
else{
mid=(left+right)/2;
lmax=(a,left,mid);//注意这里不是mid-1
rmax=(a,mid+1,rigth);
return lmax>rmax?lmax:rmax;
}
}
编写函数，采用递归法实现数组首尾倒置
void reverse(int a[],int left,int right)
{
int temp;
temp=a[left];
a[left]=a[right];
a[right]=temp;
reverse(a,left+1,right-1);
}
递归查找（顺序，二分）
尾递归
int seqSearch(int a[],int n,int x)
{
if(n==0) return -1;
else if(n==1) return a[n-1]==x?n-1:-1;
else if(a[0]==x) return -1;
else return seqSearch(a,n-1,x);
}
int seqSearch(int a[],int left,int right)
{
if(left>right) return -1;
else if(left==right) return a[n-1]==x?left:-1;
else if(a[left]==x) return -1;
else return seqSearch(a,left+1,right);
}
课上答疑
用kmp算法，abaabaabcabaabc中abaabc需要对比多少字符？
10次
测试题
- 对于KMP算法，在模式匹配时指示主串匹配位置的指针
不会变小
指针不会回溯，所以指针不会变小
- 对于半带宽为b的带状矩阵，它的特点是：对于矩阵元素aij,若它满足
|i-j|>b，则aij=0
文章评论