问答题
针对串顺序表永写一算法,判断该字符串是否是同文(即正读与反读相同,如“abcba”是一个同文,而“abc”则不是)。
【正确答案】(1)数据结构
采用字符串的顺序表示定义。
(2)思路
因为在数组中可以利用元素的下标之间的关系轻易地查到所需的元素,所以依次用第i个元素与倒数第i个元素比较即可,其中i从1到n/2。
(3)算法
int isPa1_seq(PSeqString s){ /*判断字符串s是否回文*/
int i;
for(i=0;i<=(s->n-1)/2;i++)
if(s->c[i]!=s->c[s->n-1-i])returnFALSE;
return TRUE;
}
(4)代价分析
该算法访问字符串中每个字符最多1次,时间代价为O(n)。
【答案解析】