Question

求数据结构高手给解道题！如下：

设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。例如：xyzzyx，xyzyx都算是中心对称的字符串。（提示：将一半字符先依次进栈）用C语言编写！！
谢谢高手们给予解答！！

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define maxsize 100
int i=0;
typedef struct node
{
char data;
struct node *next;
}Linklist;
Linklist *InitStack(char S[])
{
Linklist *head,*H,*p;
while(S[i]!=NULL)
{
p=(Linklist*)malloc(sizeof(Linklist));
p->data=S[i];
p->next=NULL;
if(i==0)
head=H=p;
else
{
H->next=p;
H=p;
}
i++;
}
return head;
}
//
int duichen(Linklist *H)
{
char S[maxsize];
int top=0,j=0;
Linklist *p=H;
while(j<(i/2))
{
p=p->next;j++;}
while (p!=NULL)
{
S[top]=p->data;
top++;
p=p->next;
}
p=H;
while(p!=NULL)
{
top--;
if(p->data==S[top])
p=p->next;
else break;
}
if(top==-1)
return 1;
else
return 0;
}
void main()
{
char S[maxsize],c;
Linklist *H;
while(1)
{
printf("input a string:");
scanf("%s",S);
H=InitStack(S);
if(duichen(H)==1)
printf("\nyes!\n");
else
printf("\nno!\n");
}
}

Answer 2

这样写如何：
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>

bool f(char *s);

int main()
{

char s[]="abcdcba";

printf("%d",f(s));

system("pause");

return 0;
}

bool f(char *s)
{
int len;
int i;
int flag=1;
len=strlen(s);

for(i=0;i<len/2;i++)
{
if(*(s+i)!=*(s+len-i-1))
{
flag=0;
break;
}
}

return flag;
}

Answer 3

两个指针就行了呀
初始i指头，j指尾
比较i、j所指是否相同
若不同则跳出 否则i:=i-1 j:=j-1
这样一直比下去，直到i>j时跳出就可以了

Answer 4

# include <stdio.h>
# define N 6
/*N为字符个数，可改变*/
/*输入字符时连续输入既可，不用加空格，如：asddsa*/
typedef char DataType;
typedef struct node
{
DataType data;
struct node *next;
}SLNode;

void SLNode_Initiate(SLNode **head)
{
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)
exit(1);
(*head)->next=NULL;
}
int SLNode_Insert(SLNode *head,int pos,DataType add)
{
SLNode *p,*s;
int i;
p=head;
for(i=0;i<pos;i++)
p=p->next;
if((s=(SLNode *)malloc(sizeof(SLNode)))==NULL)
return 0;
s->data=add;
s->next=p->next;
p->next=s;
return 1;
}
int SLNode_Get(SLNode *head,int pos)
{
SLNode *p=head;
int i;
for(i=0;i<=pos;i++)
p=p->next;
return p->data;
}
main()
{
int i,j;
char ch;
SLNode *L;
SLNode_Initiate(&L);
printf("please input the words:");
for(i=0;i<N;i++)
{
ch=getchar();
SLNode_Insert(L,i,ch);
}
for(i=0,j=N-1;i<=j;i++,j--)
if(SLNode_Get(L,i)==SLNode_Get(L,j)) ;
else break;
if(i>=N/2)
printf("Yes!\n");
else printf("No!\n");
getch();
}

Answer 5

先对N进行奇偶判断,

然后对N/2个字符依次进栈,

奇数个的话,直接将第N/2+1个字符舍弃(偶数无此判断)

然后对后面的字符与当前出栈的字符比较,
相等则继续比较后面,不相等则直接返回false

若全部比较完则返回true