数据结构实战

        再次说明一下，本教程为数据结构的实战教程，关于理论性的基础知识并不是本教程的重点，我们只关心各种算法的实现部分。而关于理论知识部分请大家学习《数据结构》书籍。

        下面我们来实现关于字符串查找的改进算法——KMP算法。

        KMP算法的核心就是求解模式串中的next函数值，来看一下它的实现方法。

//KMP算法计算next数组中的值
bool get_next(char *str, int *next)
{
	if (str == null || next == null)
	{
		return false;
	}

	int len = str_length(str);

	//第0个字符值为0
	next[0] = 0;
	for (int j = 0; j < len; ++j)
	{
		//第1个字符值为1
		if (j == 0)
		{
			next[j + 1] = 1;
		}
		else
		{
			int k = j;
			do
			{
				k = next[k] - 1;
				//找到相同的字符
				if (str[j] == str[k])
				{
					//下一个值为k+1
					next[j + 1] = k + 1 + 1;
					break;
				}
				//没找到则为1
				else if (k == 0)
				{
					next[j + 1] = 1;
					break;
				}
			}
			while (k > 0);
		}
	}

	return true;
}

        实现KMP算法查找字符串的模式串：

/*
 * 返回str_ind在str中第pos个字符后出现的位置
 * 采用KMP算法
 */
int str_index(char *str, char *str_ind, int pos)
{
	if (str_ind == null || str == null || pos < 0)
	{
		return -1;
	}
	//计算长度
	int length = str_length(str);
	int len = str_length(str_ind);
	if (pos >= length)
	{
		return -1;
	}

	//计算next值
	int next[len];
	get_next(str_ind, next);

	//设定起始位置
	int i = pos;
	int j = 0;
	//开始匹配
	while (i < length && j < len)
	{
		//从模式串向匹配串开始匹配
		if (j == 0 && str[i] != str_ind[j])
		{
			i++;
		}
		//如果相等则各加1
		else if (str[i] == str_ind[j])
		{
			i++;
			j++;
		}
		//如果不相等则从next值中取得下一个j的下标
		else
		{
			j -= next[j];
		}
	}

	//如果匹配成功
	if (j == len)
	{
		//计算位置
		return i - j;
	}

	return -1;
}

        再来编写一个main函数：

int main(int argc, char **args)
{
	int ind = -1;

	ind = str_index("Hello WorlD WorlS World!", "World", 0);
	printf("%d\n", ind);

	ind = str_index("Hello WorlD WorlS World!", "Worl", 0);
	printf("%d\n", ind);

	ind = str_index("Hello WorlD WorlS World!", "Worl", 7);
	printf("%d\n", ind);

	ind = str_index("Hello WorlD WorlS World!", "Worl", 15);
	printf("%d\n", ind);

	ind = str_index("Hello WorlD WorlS World!", "WorlT", 0);
	printf("%d\n", ind);

	return 0;
}

        运行结果：

18
6
12
18
-1

         再来实现一个字符串替换功能：

//使用new串替换str中所有的old
bool str_replace(char *str, char *old, char *new)
{
	if (str == null || old == null || new == null)
	{
		return false;
	}

	int ind = -1;
	int old_len = str_length(old);
	int new_len = str_length(new);
	do
	{
		ind = str_index(str, old, 0);
		if (ind < 0)
		{
			break;
		}

		str_delete(str, ind, old_len);
		str_insert(str, new, ind);
	}
	while (1);

	return true;
}

        将main函数中加入字符串替换：

int main(int argc, char **args)
{
    /*
     * ......
     */

	//字符串替换
	char str[30];
	str_copy(str, "Hello WorlD WorlS World!");
	str_replace(str, "or", "BM");
	printf("%s\n", str);


	return 0;
}

        运行结果：

Hello WBMlD WBMlS WBMld!

        本例代码：

code path   chapter.03/e.g.3.2/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure