数据结构实战

        字符串在内存中可以使用链式结构也可以使用线性结构。我们将用线性结构来存放字符串（以后的内容涉及到字符串在内存中均为线性存储方式），并对字符串进行相关操作。

        首先来看一下字符串在内存中的存放格式：

char *str = "Hello World!";

        在内存中定义了一个指针变量str，它的值是0x2000（地址0x2000是假设的），也就是"Hello World!"这个字符串的首地址。下面我们来看一下对于str指针可以取得这个字符串中字符的相关计算方法：

*str == 'H';
str[0] == 'H';
*(str + 1) = 'e';
str[1] = 'e';

        也就是说对于线性存储的字符串，可以对指针直接解引用*str，也可以将其当作数组用下标的方式进行取值。下面来看一下字符串的相关操作：

//计算字符串长度
int str_length(char *str)
{
	if (str == null)
	{
		return 0;
	}

	//计算字符串长度
	int length = 0;
	while (*str != '\0')
	{
		length++;
		str++;
	}

	return length;
}

//拷贝字符串
bool str_copy(char *str_target, char *str_source)
{
	if (str_target == null || str_source == null)
	{
		return false;
	}

	//复制字符串
	while (*str_source != '\0')
	{
		*str_target++ = *str_source++;
	}
	*str_target = '\0';

	return true;
}

//比较两个字符串，如果str0 < str1 返回-1, 如果相等返回 0 否则返回 1
int str_compare(char *str0, char *str1)
{
	if (str0 == null || str1 == null)
	{
		return 0;
	}

	//比较
	while (*str0 != '\0' && *str1 != '\0')
	{
		//小于
		if (*str0 < *str1)
		{
			return -1;
		}
		//大于
		else if (*str0 > *str1)
		{
			return 1;
		}
		str0++;
		str1++;
	}
	//如果都结束，表示相等
	if (*str0 == '\0' && *str1 == '\0')
	{
		return 0;
	}
	//如果str0结束str1没结束，表示小于
	else if (*str0 == '\0')
	{
		return -1;
	}
	//str1结束str0没结束，表示大于
	else
	{
		return 1;
	}
}

//将str0和str1连接，结果用str_new返回
bool str_concat(char *str_new, char *str0, char *str1)
{
	if (str_new == null || str0 == null || str1 == null)
	{
		return false;
	}

	//复制str0
	while (*str0 != '\0')
	{
		*str_new++ = *str0++;
	}
	//复制str1
	while (*str1 != '\0')
	{
		*str_new++ = *str1++;
	}
	//结尾符
	*str_new = '\0';

	return true;
}

//将str从pos位置切割出len个字符到sub中
bool str_sub(char *sub, char *str, int pos, int len)
{
	if (sub == null || str == null || pos < 0 || len == 0)
	{
		return false;
	}

	//从pos位置开始
	str += pos;
	int i = 0;
	//截取len长度的子串
	while (*str != '\0')
	{
		if (i++ >= len)
		{
			break;
		}
		*sub++ = *str++;
	}
	//结束符
	*sub = '\0';

	return true;
}

//返回str_ind在str中第pos个字符后出现的位置
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;
	}

	//从pos开始计算
	str += pos;
	int ind = 0;

	while (*str != '\0')
	{
		//查找子串
		bool same = true;
		for (int i = 0; i < len; ++i)
		{
			//如果在子串长度内发现不同字符，表示当前子串查找失败
			if (str[i] != str_ind[i])
			{
				same = false;
				break;
			}
		}
		//如果存在子串，返回位置
		if (same)
		{
			return ind + pos;
		}
		ind++;
		str++;
	}

	return -1;
}

//在str在第pos个位置上插入字符串str_ins
bool str_insert(char *str, char *str_ins, int pos)
{
	if (str == null || str_ins == null || pos < 0)
	{
		return false;
	}

	//计算长度
	int len = str_length(str);
	if (pos >= len)
	{
		return false;
	}
	//计算长度
	int len_ins = str_length(str_ins);
	// 处理\0所以len - pos + 1
	for (int i = len + len_ins, j = 0; j < len - pos + 1; i--, j++)
	{
		//向后复制
		str[i] = str[i - len_ins];
	}
	for (int i = 0; i < len_ins; i++)
	{
		//插入子串
		str[pos + i] = str_ins[i];
	}

	return true;
}

//删除str中第pos位置后len个字符
bool str_delete(char *str, int pos, int len)
{
	if (str == null || pos < 0 || len < 0)
	{
		return false;
	}

	//计算长度
	int length = str_length(str);

	//向前复制len长度
	for (int i = 0; i < length - pos; ++i)
	{
		str[pos + i] = str[pos + i + len];
	}
	//结束符
	str[length - len] = '\0';

	return true;
}

        再来写一个main函数测试字符串功能函数：

int main(int argc, char **args)
{
	char *str = (char *) malloc(100);

	str_copy(str, "Hello World!");
	printf("%s\n", str);

	int cmp0 = str_compare("abcde", "abcde");
	int cmp1 = str_compare("abcde", "abcdf");
	int cmp2 = str_compare("abcdf", "abcde");
	int cmp3 = str_compare("abcde", "abcdef");
	int cmp4 = str_compare("abcdef", "abcde");
	printf("%d %d %d %d %d\n", cmp0, cmp1, cmp2, cmp3, cmp4);

	str_concat(str, "Hello ", "World!");
	printf("%s\n", str);

	str_sub(str, "Hello World!", 7, 2);
	printf("%s\n", str);

	int ind0 = str_index("Hello World!", "o", 0);
	int ind1 = str_index("Hello World!", "o", 5);
	printf("%d %d\n", ind0, ind1);

	str_copy(str, "Hello World!");
	str_insert(str, "My Beautiful ", 6);
	printf("%s\n", str);

	str_delete(str, 6, 3);
	printf("%s\n", str);

	str_delete(str, 6, 10);
	printf("%s\n", str);

	free(str);

	return 0;
}

        运行结果：

Hello World!
0 -1 1 -1 1
Hello World!
or
4 7
Hello My Beautiful World!
Hello Beautiful World!
Hello World!

        本例代码：

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

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