Question

c语言版 数据结构问题

假设以块链结构作为串的存储结构。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度O(strlenth（s））

Answer 1

1.找到结构的头(H)和尾(R)
2.
下面是伪代码
while(H在R之前) do begin

if data_at[H]!=data_at[R] then return false;//肯定不对称
H<-后继;
R<-前驱;
end;
return true;
时间复杂度O(strlen(s))
既为表长

Answer 2

bool IsPalindrome(const LString &s)
{//判断串s是否回文
	if (!s.curlen || s.curlen == 1)
		return true;//如果是空串或者一个字符，则没必要判断

	const Chunk *ps = s.head;
	int i = s.curlen / 2, k = 0;//注意整数除法
	char *hos = new char[i]; //存储字符串的一半

	while (i)//取前一半字符到数组中
	{
		if (k > CHUNKSIZE - 1)
		{
			k %= CHUNKSIZE;
			ps = ps->next;
		}
		hos[(i--) - 1] = ps->str[k++];//数组反向存储模拟栈
	}
	if (s.curlen % 2)//如果字符个数是奇数
	{
		++k;//忽略掉中间的一个字符
	}
	for (int j = 0; j < s.curlen / 2; ++j)//与另一半字符进行比较
	{
		if (k > CHUNKSIZE - 1)
		{
			k %= CHUNKSIZE;//取模
			ps = ps->next;
		}
		if (hos[j] != ps->str[k++])
			return false;
	}
	return true;//是回文
}

块链的结构和书本的定义是一摸一样的，不知道的话可以翻书。

还有，代码不是很好，有重复冗余的地方，不建议采用，但是算法的思想是没问题的，算法的时间复杂度是满足题目的。