数据结构第四章

4.1.1串的定义和基本操作

字符串的操作、比较大小（见PPT）

4.1.2 串的存储结构

串其实是一种特殊的线性表。

串的顺序存储

1. 静态数组实现（定长顺序存储）

#define MaxLen 255		//预定义最大串长为255
typedef struct{
	char ch[MaxLen];	//每个分量存储一个字符
	int length;			//串的实际长度
}SString;
           

基本操作的实现

• 求字串：用sub返回串S的第pos个字符起长度为len的子串

//求子串
bool SubString(SString &Sub, SString S, int pos, int len){
	//子串范围越界判断
	if(pos + len -1 > S.length)
		return false;
		for(int i = pos; i < pos + len; i++)
			Sub.ch[i - pos + 1] = S.ch[i];
		Sub.length = len;
}  
           

• 比较操作，若S>T,则返回值>0;若S=T，则返回值=0；若S<T,则返回值<0

int StrCompare(SString S, SString T){
	for(int 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;		
}
           

• 定位操作。

int Index(SString S, SString T){
	int i = 1,n = SreLength(S),m = StrLength(T);
	SString sub;				//用于暂存子串
	while(i <= n - m + 1){
		SubString(sub, S, i, m);
		if(StrCompare(sub,T) != 0) ++i;
		else return i; 			//返回子串在主串中的位置
	}
	return 0;					//S中不存在T相等的子串
}
           

2.动态数组实现(堆分配存储)

typedef struct{
	char *ch;			//按串长分配存储区，ch只向串的基地址
	int length;			//串的长度
}HString;

HString S;
S.ch = (char *)malloc(MaxLen * sizeof(char));
S.length = 0;
           

串的链式存储

typedef struct StringNode{
	char ch;			//每个节点存一个字符
	struct StringNode * next;
}StringNode, *String;
           

分析：此方式存储密度低：每个字符1B，每个指针4B

改进：

typedef struct StringNode{
	char ch[4];			//每个节点存多个字符
	struct StringNode * next;
}StringNode, *String;
           

4.2.1 朴素模式匹配算法

int Index(SString S,SString T){
	int i = k = j =1;
	while(i <= S.length && j <= T.length){
		if(S.ch[i] == T.ch[j]){
			i++;
			j++;
		}else{
			k++;
			i = k;
			j = 1;
		}
	}
	if(j > T.length){
		return k;
	}else
		return 0;
}
           

4.2.2KMP算法（朴素模式匹配算法的优化）

改进思路：主串指针不回溯，只有模式串指针回溯