Question

一道C语言的题目，真心没有头绪

通常称正读和反读都相同的字符序列为“回文”，例如‘abba’和‘abcdcba’是回文,‘abcde’和‘abab’则不是回文。若字符序列存储在一个单链表中，编写一个算法判别此字符序列是否是“回文”。
要求：用C语言写出算法。

Answer 1

#include<stdio.h>
#include<stdlib.h>
#define maxlen 20
typedef struct{
	char ch[maxlen];
	int last;
}Sequenlist;
typedef struct{
	char data[maxlen];
	int top;
}Seqstack;
Sequenlist *Sqlsetnull(){      //建空顺序表
	Sequenlist *L;
	L=(Sequenlist *)malloc(sizeof(Sequenlist));
	L->last=-1;
	return L;
}
Seqstack * Setstack(){       //建空栈
	Seqstack *S;
	S=(Seqstack *)malloc(sizeof(Seqstack));
	S->top=-1;
	return S;
}
Seqstack * Pushstack(char x,Seqstack *S){  //入栈
	S->top++;
	S->data[S->top]=x;
	return S;
}
Seqstack * Popstack(Seqstack *S){    //出栈
	S->top--;
	return S;
}
char Gettop(Seqstack *S){     //取栈顶
	return S->data[S->top];
}
Sequenlist *Pushlist(){   //将字符串存入顺序表中
	Sequenlist *L;
	L=Sqlsetnull();
char a;
	printf("请输入字符串，并以'#'结束!\n");
	a=getchar();
	while(a!='#'){
		L->last++;
		L->ch[L->last]=a;
		a=getchar();
	}
	return L;
}
int Compare(Sequenlist *L){     //判断是不是回文
	int  i,n;
	n=(L->last+1)/2;
	Seqstack *S;
	S=Setstack();
	for(i=0;i<n;i++){
		S=Pushstack(L->ch[L->last],S);
		L->last--;
	}
	while(L->last!=S->top)
		L->last--;
	while(L->ch[L->last]==S->data[S->top]&&L->last!=-1){
		L->last--;
		S=Popstack(S);
	}
	if(L->last==-1)     //是回文返回1
		return 1;
	else                //不是回文返回0
		return 0;
}
void Resultout(int a){    //结果输出
	if(a==1)
		printf("该字符串是回文!\n");
	if(a==0)
		printf("该字符串不是回文!\n");
}
void main(){
	Resultout(Compare(Pushlist()));
}

Answer 2

鉴于单链只能单向访问
新建另一个单链
用头插法，顺序拷贝源链的节点插入新链的头部
然后比较这样两个单链的前半段就OK了

Answer 3

编码中.....

追问

谢啊~麻烦最好有注释

追答

#include <stdio.h>
#include <stdlib.h>

struct node{
char c;
node *next;
}; 
node *creat();  //创建链表
node *reverse(node *); //反转链表
void main()
{
char str1[100],str2[100];
int i=0,j=0;
node *head;
head = creat();
for(node* tmp=head;tmp;tmp=tmp->next) //遍历链表，将每个元素存在字符数组str1
str1[i++]=tmp->c;
head = reverse(head); //反转链表
for(node* tmp=head;tmp;tmp=tmp->next) //将反转后链表的每个元素存在字符数组str2中
str2[j++]=tmp->c;
for(j=0;j<i;j++){ //比较
if(str1[j]!=str2[j])
{
printf("该字符串不是回文.\n");
return ;
}
}
printf("该字符串是回文.\n");
}
node *creat()  
{
printf("请输入字符串(输入回车结束):");
char c;
c=getchar();
node *p1,*p2,*head;
head=NULL;
p1=(node *)malloc(sizeof(node));
p1->c=c;
head =p1;
p2=p1;
p1->next=NULL;
while(1)   
{
c=getchar();
if(c=='\n')
break;
p1=(node *)malloc(sizeof(node));
p1->c=c;
p2->next=p1;
p1->next=NULL;
p2=p1;
}
return head;
}

node *reverse(node *first)
{
node *p1,*p2,*p3;
p2=first;
p3=first->next;
do{
p1=p2;
p2=p3;
p3=p2->next;
p2->next=p1;
}
while(p3!=NULL);
first->next=NULL;
return p2;
}

满意请采纳！不懂可以问。