数据结构_串
2015-10-27 本文已影响37人
arkulo
定义
- 特殊的线性表，每个元素都是字符
- 元素可以是零个或多个
常用操作
查找子串、串的相似度、截取、反转、最长公共子串、分词、回文
顺序实现
- 字符串的操作一般都不改变内存空间（例外：连接两个字符串），因此顺序存储整体效率更高
- 存储单元大小＝串真实长度＋1（"\0"占一个字节空间）
- 比较适合的操作：查找、截取
链式存储
- 类似插入、删除的操作是效率较高的，截取就不好了
经典算法
朴素的模式匹配算法
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/simpleChuan.png
代码实现：
#include <stdio.h>
int main(int args,char *argv[])
{
char S[] = "abcde";
char T[4] = "cde";
int slen = sizeof(S);
int tlen = sizeof(T);
int i = 0;
int j = 0;
int from = 0;
while(i<slen && j<tlen)
{
if(S[i]==T[j])
{
from = (from==0)?i:from;
i++;
j++;
}else
{
i = i-j+1;
j = 0;
from = 0;
}
}
if(j==tlen)
{
printf("include subString from index %d\n",from);
}else
{
printf("no match!!\n");
}
return 0;
}
- while(i<slen && j<tlen)是降低时间复杂度的关键（相对于双层循环）
KMP算法
