严蔚敏建立词索引表

#include “HString.h“

// 创建一个空串
HString createString（）{
	HString hs;
	InitString（&hs）;
	return hs;
}

Status InitString（HString *T）{
	T->ch = NULL;
	T->len = 0;
	return OK;
}

Status StrAssign（HString *T char *chars）{
	// 生成一个其值等于串常量chars的串T
	// 临时变量
	int len=0i=0;
	char *c;
	if（T->ch） 
		free（T->ch）;
	// 计算chars的长度
	for（len=0c=chars; *c; ++c）
		++len;
	
	if（!len）{T->ch = NULL; T->len = 0;}
	else
	{
		if（!（T->ch = （char*）malloc（len*sizeof（char））））
			exit（0）;
		for（i=0;i			T->ch[i] = chars[i];
		T->len = i;
	}
	return OK;
}	

// 返回S的元素个数，称为串的长度
int StrLength（HString S）{
	return S.len;
}

int StrCompare（HString SHString T）{
	// 若S>T，则返回值>0；若S=T，则返回值=0；若S	int i=0;
	for（i=0;i		if（S.ch[i]!=T.ch[i]） return S.ch[i]-T.ch[i];
	}
	return S.len - T.len;
}

Status ClearString（HString *S）{
	// 将S清为空串
	if（S->ch） {
		free（S->ch）; 
		S->ch = NULL;
	}
	S->len = 0;
	return OK;
}

Status Concat（HString *T HString S1 HString S2）{
	// 用T返回由S1和S2联接而成的新串
	int i=0;
	if （T->ch） free（T->ch）;
	if（!（T->ch = （char*）malloc（（S1.len + S2.len）*sizeof（char））））
		exit（0）;
	//连接第一个串
	for（i=0;ich[i] = S1.ch[i];
	//连接第二个串
	for（i=0;ich[i + S1.len] = S2.ch[i];
	T->len = S1.len + S2.len;
	return OK;
}

Status Substring（HString *Sub HString S int pos int len）{
	// 用Sub返回串S的第pos个字符起长度为len的子串。
	// 其中，1<=pos<=StrLength（S）且0<=len<=StrLength（S）-pos+1
	int i=0;
	if（pos < 1 || pos > S.len || len < 0 || len > S.len - pos +1）
		return ERROR;
	if（Sub->ch）free（Sub->ch）;
	if（!len） {Sub->ch = NULL; Sub->len = 0;}
	else
	{
		Sub->ch = （char*）malloc（len*sizeof（char））;
		for（i=0;i			Sub->ch[i] = S.ch[i+pos-1];
		Sub->len = len;
	}
	return OK;
}

Status StrCopy（HString *des HString src）{
	// des为目标串，src为源串
	// 把src拷贝到des
	int i=0;
	if（des->ch） free（des->ch）;
	des->ch = （char *）malloc（sizeof（char）*src.len）;
	if（!des->ch） exit（0）;
	for（i=0;i	{
		des->ch[i] = src.ch[i];
	}
	des->len = src.len;
	return OK;

}

// 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0
// 其中，T非空，1<=pos<=StrLength（S）.
int Index（HString S HString Tint pos）{
	int i=posj=1;
	while（i<=S.len&&j<=T.len）{
		if（S.ch[i-1] == T.ch[j-1]）{
			++i;++j;
		} else {
			i=i-j+2; j=1;
		}
	}
	if（j>T.len）return i-j;
	else return  0;
}

int Index_KMP（HString S HString T int pos）{
	int i=posj=1;
	int *next = （int *）malloc（sizeof（int）*（T.len+1））;
	get_nextval（T next）;
	while（i<=S.len && j<=T.len）{
		if（j==0 || S.ch[i-1] == T.ch[j-1]）{
			++i; ++j;
		}
		else 
			j = next[j];
	}
	free（next）;
	if（j>T.len） return i-j;
	else return 0;
}

void get_next（HString T int next[]）
{
	//求模式串的next函数值并存入数组next
	int i=1j=0; 
	next[1]=0;
	while（i		if（j==0||T.ch[i-1] == T.ch[j-1]）{
			++i;++j;next[i] = j;
		} else {
			j = next[j];
		}
	}
}

void get_nextval（HString T int nextval[]）
{
	//求模式串的next函数值并存入数组ne