datastruct_3

串相关笔记

#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
//串的相关函数：
//顺序存储串：
#define MAXLEN 255
typedef struct{
	char ch[MAXLEN];//静态数组实现 
	int length;
}SString;

typedef struct{
	char *ch;//动态数组实现 ，按串长分配存储区，ch指向串的基地址 
	int length;
}HString; 

void get_next(SString T,int next[]);
void get_nextval(SString T,int next[]);
int main(){
	HString S;
	S.ch=(char*)malloc(MAXLEN*sizeof(char));
	S.length=0;
	return 0;
}


typedef struct{
	char ch[MAXLEN];//存储多个字符以提高空间利用率 
	struct StringNode *next;
}StringNode,*String;//串的链式存储
 
bool SubString(SString *pSub,SString S,int pos,int len){//用Sub返回串S的第pos个字符起长度为len的子串 
	if(pos+len-1>S.length){
		return false;//子串范围越界 
	}
	int i;
	for(i=pos;i<pos+len;i++){
		pSub->ch[i-pos+1]=S.ch[i];
	} 
	pSub->length=len;
	return true;
} //求子串

int StrCompare(SString S,SString T){
	int i;
	for(i=1;i<=S.length&&i<=T.length;i++){
		if(S.ch[i]!=T.ch[i]){
			return S.ch[i]-T.ch[i];
		}
	}
	return S.length-T.length;
} //等价于strcmp;

int Index(SString S,SString T){
	int i=1,n=S.length,m=T.length;
	SString sub;
	while(i<=n-m+1){
		SubString(&sub,S,i,m);
		if(StrCompare(sub,T)!=0)++i;
		else{
			return 1;
		}
	}
	return 0;
} //定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0

//KMP算法:
int next[MAXLEN];//next数组也可以当做函数变量输入
int nextval[MAXLEN];
int Index_KMP(SString S,SString T){
	int i=1,j=1;
	get_next(T,next);
	get_nextval(T,next);
	while(i<=S.length&&j<=T.length){
		if(j==0||S.ch[i]==T.ch[j]){
			++i,++j;
		}
		else{
			j=nextval[j];//next数组要根据实际情况决定 (同理于nextval数组)
		}
	}
	if(j>T.length){
		return i-T.length;
	}
	else{
		return 0;
	}
} 
//next数组的求法：
void get_next(SString T,int next[]){
	int i=1,j=0;
	next[1]=0;
	while(i<T.length){
		if(j==0||T.ch[i]==T.ch[j]){
			++i,++j;
			next[i]=j;
		}
		else{
			j=next[j];
		}
	}
} 
//nextval数组的求法（next数组的优化）：
void get_nextval(SString T,int next[]){
	int j=2;
	nextval[1]=0;
	for(j=2;j<=T.length;j++){
		if(T.ch[next[j]]==T.ch[j]){
			nextval[j]=nextval[next[j]];
		}
		else{
			nextval[j]=next[j];
		}
	}
}