数据结构设计题

来源：百度知道 编辑：UC知道 时间：2024/09/28 07:01:47
用单链表做存储结构，以回车为结束标志，输入一个任意长度的字符串，然后判断他是否为“回文”，输出YES或NO，最后删除字符串并释放全部空间。
例：ABCD1221DCBA----回文
ABCD123DCBA-----不回文
要求：定义相关数据类型，不的使用数组（顺序表）做字符串的存储空间和辅助存储空间
有师兄告诉我这题怎么设计吗
但是他要求用但连表来存储，如果用双想连表用这样可行，可是但连表怎么查找这么多前驱

建立删除好说，这是判断回文的算法

link tail,front,r=NULL;//tail用来指向尾部，r是尾部判断标记,初始为NULL
front=head;//front用来指向头部，初始指向链表中第一个元素
bool hui=true;//假设是回文
while(front!=r&&front->next!=r) {
tail=front;//tail从头部开始向后寻找
while(tail->next!=r)tail=tail->next;
if(front->data==tail->data)//头部和尾部所对应的值相等
{
front=front->next;//front指向下次的头部
r=tail;//r标记当前的尾部
}
else
{ hui=false;//找到一组头尾不相等的值则不是回文
break;
}
}
if(hui)printf("Yes\n"); else printf("No\n");