问答题
试设计一个C算法(或C程序)：用单链表作存储结构，以回车符为结束标志，输入一个任意长度的字符串；然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”)，输出信息“Yes”或“No”；最后删除字符串并释放全部空间。例如：若输入“ABCDl2321DCBA”，是回文，则输出“YeS”；若输入“ABCDl23DCBA”，不是回文，则输出“No”。要求：定义相关数据类型，不得使用数组(顺序表)作字符串的存诸结构和辅助存储空间。假定字符串的长度为n，试分析上述算法的时间复杂度。【华中科技大学2004五(10分)】
【正确答案】正确答案：利用栈存放字符串的前半部分，将后半部分与栈中弹出元素比较。核心语句段如下： char S[]； ／／字符栈，容量足够大 p=head一>next ／／设链表带头结点 int i=0； while(ic=n／2) ／／前一半字符入栈，链表指针后移 (S[i]=p一>data；p=p一>next； i++；) if(n％2==1)p=p一>next； ／／若链表有奇数个结点，则跳过中间结点 while(p) if(p一>data==s[i])(p=p一>next；i一一；) else break； ／／不是回文 if(!P&&i==0)return(1)； else return(0)；
【答案解析】