Question

单链表判断字符中心对称

设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc（h，n），判断该链表的前n个字符是否中心对称。

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励20（财富值+成长值）

Answer 1

代码的主要思想
1 讲输入的字符串保存到顺序链表中
2 计算链表的长度
3 根据长度的积偶性，将链表的前一半加到栈中
4 从栈中pop出各个元素，跟链表后一半的各个字符比较，如果有不一样的，说明不对称
具体细节
//判字符串中心对称
#include<stdio.h>
#include<malloc.h>
#include<string.h>
//定义单链表结构类型
typedef char datatype;
typedef struct node
{ datatype data;
struct node *next;
}linklist;
//定义顺序栈结构类型，
const int maxsize=40;
typedef struct
{ datatype elements[maxsize];//栈空间的大小
int top;//栈顶下标（elements的下标）
}stack;

void setnull(stack *&);//清空栈
int length(linklist*);//计算链表长度
void printlink(linklist*);//打印链表的数据
void create(linklist *&,datatype*);//创建链表
void push(stack*,datatype);//压栈操作
datatype pop(stack*);//出栈操作
int symmetry(linklist*,stack*);//判字符串是否中心对称的函数声明

void main()
{
linklist *head;stack *s;//定义链表头和栈
datatype str[80];//用于保存输入的字符串
gets(str);//获取字符串
create(head,str);//创建链表，同时链表各个节点的内容就是字符串中的字符
printlink(head);//将链表的内容打印出来
setnull(s);
//栈初始化

//调用symmetry判断是否对称
if(symmetry(head,s)) printf("字符串\"%s\"中心对称\n",str);
else printf("字符串\"%s\"不是中心对称\n",str);
}
//栈初始化
void setnull(stack *&s)
{
s=(stack*)malloc(sizeof(stack));//申请内存
s->top=-1;//初始化栈顶元素下标为-1
}

//求单链表长度，遍历链表，计算长度
int length(linklist*head)
{ linklist *p=head->next;
int n=0;
while(p!=NULL){ n++; p=p->next; }
return n;
}
//输出单链表，遍历链表，打印各个节点的数据
void printlink(linklist*head)
{ linklist *p=head->next;
while(p!=NULL)
{ printf("%c",p->data);
p=p->next;
}
printf("\n");
}
//建立具有头结点的单链表，尾部插入新节点，不多说了
void create(linklist *&head,datatype*str)
{ datatype *p=str;
linklist *s,*r;
head=(linklist*)malloc(sizeof(linklist));
r=head;
while(*p!='\0')
{
s=(linklist*)malloc(sizeof(linklist));
s->data=*p;
r->next=s;
r=s;
p++;
}
r->next=NULL;
}
//顺序栈入栈
void push(stack*s,datatype e)
{
s->top++;//压入新元素，所以栈顶元素下标自加
s->elements[s->top]=e;//栈顶元素赋值
}
//顺序栈出栈
datatype pop(stack*s)
{
datatype temp;
s->top--;//弹出栈顶元素，原来栈顶元素的前一个元素变成新的栈顶元素
temp=s->elements[s->top+1];//获得栈顶元素的值
return temp;
}
//添加判字符串是否中心对称算法
int symmetry(linklist*head,stack*s)
{
int i,a;
datatype e;
linklist *p=head->next;
a=length(head)/2;//计算链表长度
if (length(head)%2==0)//长度为偶数情况
{
for (i=1;i<=a;i++)
{
e=p->data;
push(s,e);//前一半的元素压栈
p=p->next;
}
}
else //积数的情况
{
for (i=1;i<=a;i++)
{
e=p->data;
push(s,e);前一半的元素压栈
p=p->next;
}
if (i==a+1){e=p->data;push(s,e);}//积数情况的特殊处理
}
while (p)//由于p一直向后next，此时的p已经指到链表的后一半的第一个元素了
{
if(p->data!=pop(s))//链表后一半各个元素与栈内元素进行比较
return 0;//如果有不一样的，说明不对称
else p=p->next;
}
return 1;//都一样，所以字符串对称
}