3.1 字符串及其抽象数据类型
3.1.1 基本概念
字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。
一个串可以记为 s="s0s1..sn-1"(n >= 0)，其中s是串的名字，双引号括起来的字符序列是串的值。
3.1.2 抽象数据类型
ADT String is
operations
String createNullStr(void) // 创建一个空串
int isNullStr(String s) // 判断串s是否为空
int length(String s) // 返回s的长度
String concat(String s1, String s2) // 返回将串s1和串s2拼接在一起构成的一个新串
String subStr(String s, int i, int j) // 在串s中，求从串的第i个字符开始连续j个字符所构成的子串
int idnex(String s1, String s2) // 如果串s2是s1的子串，则可求串s2在串s1中的第一次出现的位置
end ADT String
3.2 字符串的实现
3.2.1 顺序表示
顺序串类型定义如下：
typedef struct SeqString {
int MAXNUM;
int n;
char *c;
} SeqString;
创建空顺序串
SeqString *createNullStr_Seq(int m) {
SeqString *pstr = (SeqString *) malloc(sizeof(SeqString));
if (pstr != NULL) {
pstr->c = (char *) malloc(sizeof(char) * m);
if (pstr->c) {
pstr->n = 0;
pstr->MAXNUM = m;
return pstr;
} else {
free(pstr);
}
}
return NULL;
}
求顺序表示的串的子串
SeqString *substr_seq(SeqString *s, int i, int j) {
SeqString *s1;
int k;
s1 = createNullStr_seq(j);
if (s1 == NULL) {
return NULL;
}
if (i > 0 && i <= s->n && j > 0) {
if (s->n < i+j -1) {
j = s->n - i + 1;
}
for (k = 0; k < j; k++) {
s1->c[k]= s->c[i+k-1];
}
s1->n = j;
}
return s1;
}
3.2.2 链接表示
链表定义如下：
typedef struct StrNode {
char c;
struct StrNode * link;
} StrNode;
typedef struct StrNode *LinkString;
创建带头结点的空链串
LinkString createNullStr_link(void) {
LinkString pst;
pst = (LinkString) malloc(sizeof(StrNode));
if (pst != NULL) {
pst->link = NULL;
}
return pst;
}
求单链表示的串的子串
LinkString subStr_link(LinkString s, int i, int j) {
LinkString s1;
StrNode *p, *q, *t;
int k;
s1 = createNullStr_link();
if (s1 == NULL) {
return NULL;
}
if (i < 1 || j < 1) {
return s1;
}
p = s;
for (k = 1; k <= i; k++) [
if (p != NULL) {
p = p->link;
} else {
return s1;
}
}
if (p == NULL) {
return s1;
}
t = s1;
for(k = 1; k <= j; k++) {
if (p != NULL) {
q = (StrNode *) malloc(sizeof(StrNode));
if (q == NULL) {
return s1;
}
q->c = p->c;
q->link = NULL;
t->link = q;
t = q;
p = p->link;
}
}
return s1;
}
3.3 模式匹配
3.3.1 朴素的模式匹配
基本思想
实现模式匹配的最简单做法是：用p中的字符串依次与t中的字符比较。如下图(a)所示，如果t0 = p0, t1 = p1, ..., tm-1 = pm-1，则匹配成功，返回第一次出现的位置是从第一个字符t0开始。否则必有某个i(0<= i <= m-1)，使得 ti != pi，这是可将p右移一个字符，重新开始比较。
朴素的模式匹配
例子如下：
朴素的模式匹配举例
朴素的模式匹配算法
/**
* t为主串，p为匹配串
*/
int index(SeqString *t, SeqString *p) {
int i, j;
i = 0;
j = 0;
while(i < p->n && j < t->n) {
if (p->c[i] == t->c[j]) { // 继续匹配下一个字符
i++;
j++;
} else { // 主串、子串回溯，重新下一次匹配
j = j - i + 1;
i = 0;
}
}
if (i >= p->n) {
return j-p->n+1; // 返回p中低一个字符在t中的序号
} else {
return -1; // 匹配失败返回-1
}
}
缺点：效率不高
3.3.2 无回溯的模式匹配
基本思想
造成朴素匹配算法速度慢的原因是有回溯，而这些回溯不一定是必要的。
为了提高提配的速度，要能找到一个大于等于1的右移的位数，并且确定p和t继续比较的字符。最为理想的情况，匹配过程对于t是无回溯的。也就是在右移若干位后，应该立即用p中一个新的字符pk(k < i) 和 tj(甚至tj+1)继续进行比较。
无回溯的模式匹配算法
int pMatch(SeqString *t, SeqString *p, int *next) {
int i, j;
i = 0, j = 0;
while (i <p->n && j <t->n) {
if (i == -1 || p->c[i] == t->c[j]) {
i++; j++;
} else {
i = next[i];
}
}
if (i >= p->n) {
return j - p->n + 1; // 匹配成功
} else {
return -1; // 匹配失败
}
}
计算next数组
makeNext(SeqString *p, int *next) {
int i = 0, k = -1;
next[0] = -1;
while (i < p->n - 1) {
while(k >=0 && p->c[i] != p->c[k]) {
k = next[k];
}
i++;
k++;
next[i] = k;
}
}
计算next数组(改进后)
makeNext(SeqString *p, int *next) {
int i = 0, k = -1;
next[0] = -1;
while (i < p->n - 1) {
while (k >= 0 && p->c[i] != p->c[k]) {
k = next[k];
}
i++;
k++;
if (p->c[i] == p->c[k]) {
next[i] = next[k];
} else {
next[i] = k;
}
}
}
网友评论