我现在手边没书了－－gg得一个：


/*字符串的顺序表示*/

#include<stdio.h>
#include<stdlib.h>

#define MAXNUM 80 /* 串允许的最大字符个数。根据需要定义 */
struct SeqString { /* 顺序串的类型 */
int n; /*串的长度n<MAXNUM */
char c[MAXNUM];
};

typedef struct SeqString *PSeqString;

/*创建空顺序串*/
PSeqString createNullStr_seq( void ) {
PSeqString pstr = (PSeqString)malloc(sizeof(struct SeqString)); /* 申请串空间 */
if (pstr == NULL)
printf("Out of space!!\n");
else
pstr->n = 0;
return (pstr);
}

/* 创建一个字符串，用C的串s初始化它 */
PSeqString createStr_seq( char *s ) {
char *p, *q;
PSeqString pstr = (PSeqString)malloc(sizeof(struct SeqString)); /* 申请串空间 */
if (pstr == NULL)
printf("Out of space!!\n");
else {
for ( p = q = pstr->c; *s != '\0' && p - q < MAXNUM; )
*p++ = *s++;
pstr->n = p - q;
}

return pstr;
}

/*判断串s是否为空串，若为空串，则返回1，否则返回0*/
int IsNullStr (PSeqString s) {
return s->n == 0;
}

/*返回串s的长度*/
int length (PSeqString s) {
return s->n;
}

/* 求从s所指的顺序串中第i(i>0)个字符开始连续取j个字符所构成的子串 */
PSeqString subStr_seq(PSeqString s,int i,int j) {
int k;
PSeqString s1 = createNullStr_seq( ); /* 创建一空串 */
if (s1==NULL) return (NULL);
if ( i > 0 && i <= s->n && j > 0 ) {
if ( s->n < i+j-1 ) j = s->n-i+1; /*若从i开始取不了j个字符,则能取几个就取几个*/
for (k = 0; k < j; k++)
s1->c[k] = s->c[i+k-1];
s1->n = j;
}
return s1;
}

/*返回将串s1和s2拼接在一起构成一个新串*/
PSeqString concat (PSeqString s1, PSeqString s2 ) {
PSeqString s;
int k;
if( s1->n + s2->n > MAXNUM) {
printf("overflow\n");
return NULL;
}

s = createNullStr_seq( ); /* 创建一空串 */
for(k = 0; k < s1->n; k++)
s->c[k] = s1->c[k];
for(k = s1->n; k < s1->n + s2->n; k++)
s->c[k] = s2->c[k - s1->n];
s->n = s1->n + s2->n;
return s;
}

/* 朴素子串匹配算法。求p所指的串在t所指的串中第一次出现时,*/
/* p所指串的第一个元素在t所指的串中的序号(即：下标+1) */
int index0( PSeqString t, PSeqString p ) {
int i = 0, j = 0;/*初始化*/

while (i < p->n && j < t->n) /*反复比较*/
if (p->c[i] == t->c[j]) { /* 继续匹配下一个字符 */
i++; j++;
}
else { /* 主串、子串的i、j值回溯，重新开始下一次匹配 */
j -= i - 1; i = 0;
}

if (i >= p->n) /* 匹配成功，返回p中第一个字符在t中的序号 */
return( j - p->n + 1);
else return 0; /* 匹配失败 */
}

/*int index (s1,s2 )
如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置. 参见模式匹配*/

/* 变量next是数组next的第一个元素next[0]的地址 */
void makeNext(PSeqString p, int *next) {
int i = 0,k = -1; /* 初始化 */
next[0] = -1;

while (i < p->n-1) { /* 计算next[i+1] */
while (k >= 0 && p->c[i] != p->c[k])/* 找出p0~pi中最大的相同的前后缀长度k */
k = next[k];
i++; k++;
if (p->c[i] == p->c[k]) /* 填写next[i]，同时考虑改善 */
next[i] = next[k];
else next[i] = k;
}
}

/* 无回溯的子串匹配算法，求p所指的串在t所指的串中第一次出现。*/
/* 有出现是返回p所指串的首元素在t所指串中的序号（从1开始），没有时返回0 */
int index(PSeqString t, PSeqString p) {
int i = 0, j = 0; /* 初始化 */
int next[MAXNUM]; /* 内部索引数组 */

makeNext(p, next); /* 在什么时候求next数组，可以考虑不同方式 */
while (i < p->n && j < t->n) /*反复比较*/
if ( i == -1 || p->c[i] == t->c[j] ) { /* 继续匹配下一字符 */
i++; j++;
}
else i = next[i]; /* j不变，i后退 */

if (i >= p->n)
return( j - p->n + 1); /* 匹配成功，返回p中第一个字符在t中的序号 */
else return 0; /* 匹配失败 */
}