验证回文串

题目：给定一个字符串，验证它是否是回文串。

例如：

​​“abccba”  ​TRUE

​  ​  ​“abcddefa”  FALSE

在这里我使用了两种方法来解决这个问题，第一种是单链表，第二种是用顺序表。

单链表

​在用单链表解决这个问题的时候，由于要访问一个节点的前一个节点，随之而然的就想到了使用双向链表的方法，一个指向先驱节点，一个指向后继节点，这样访问就会十分方便。可是，使用单向链表来解决这个问题就会繁琐很多。基本上就把一个链表分成了两个链表，一个指针指向前面，从前往后遍历；一个指针指向尾部，也是从前往后遍历，但是尾部递减（往前移动）。

​使用单链表实现，资源消耗是很大的。用了两重循环，时间复杂度是(n/2)*n，为O(n^2)；空间复杂度为0。所以我觉得使用单链表来做不合适，用双向链表来做效率会提高很多。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ElemType char

typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LinkList;

LinkList* Create()
{
	LinkList *L;
	LinkList *s;
	ElemType e;
	L=(LinkList*)malloc(sizeof(LinkList));
	L->next=NULL;
	printf("请输入字符串：");
	while(1)
	{
		scanf("%c",&e);
		if(e!='1')
		{
			s=(LinkList*)malloc(sizeof(LinkList));
			s->data=e;
			s->next=L->next;
			L->next=s;
		}
		else
		{
			break;
		}
	}
	return L;
}

int ListLength(LinkList *L)
{
	LinkList *p;
	p=L->next;
	int sum=0;
	while(p)
	{
		sum++;
		p=p->next;
	}
	return sum;
}

void Printf(LinkList *L)
{
	printf("当前链表为：");
	L=L->next; //跳过头结点，从一号结点开始进行遍历输出。 
	while(L!=NULL)
	{
		printf("%c",L->data);
		L=L->next; 
	}
	printf("\n");
}
 void isPalindrome(LinkList *L,int a,int b)
 {
 	LinkList *p=L;
 	LinkList *q=L;
 	int f=1;

 	for(int i=0;i<a;i++)
 	{
 		p=p->next;
 		//printf("1.p=%c\n",p->data);
 		for(int j=0;j<b;j++)
 		{
 			q=q->next;
		}
		//printf("2.q=%c\n",q->data); 
		if(p->data==q->data)
 		{
 			b--;
 			//printf("b=%d\n",b);
			q=L;
				//isPalindrome(L,a,b);
		}	
		else 
		{
			f=0;
			break;
		}
	}
 	if(f==1)printf("TRUE\n");
 	else printf("FALSE\n");
 }

int main()
{
	LinkList *L;
	L=Create();
	ListLength(L);
	Printf(L);
	isPalindrome(L,ListLength(L)/2,ListLength(L));
}

顺序表

​顺序表具有随机访问的特点，用来解决比较某些位置的数据内容是否相同刚刚好，在时间复杂度上会大大减小，效率会有很大的提高。时间复杂度为O(n);空间复杂度为0。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxSize 100
#define ElemType char

typedef struct
{
	ElemType ch[MaxSize];
	int length;
}SqList;

SqList* Create()
{
	SqList *L;
	char c;
	int i=0;
	L=(SqList *)malloc(sizeof(SqList));
	L->length=0;
	printf("请输入字符串（以1结束）：");
	while(1)
	{
		scanf("%c",&c);
		if(c!='1')
		{
			L->ch[i]=c;
//			printf("%d:%c",i,L->ch[i]);
			i++;
//			printf("%d",i);
			L->length++;
		}
		else break;
	}
	return L;
 } 
 
void PrintfList(SqList *L)
 {
 	for(int i=0;i<=L->length-1;i++)
 	{
 		printf("%c",L->ch[i]);
	 }
	printf("\n");
 }
 
void Cmp(SqList *L)
{
	int i=0,j=L->length-1;
	int flag=1;
	while(i<(L->length/2-1))
	{
		if(L->ch[i]==L->ch[j])
		{
			i++;
			j--;
		}
		else
		{
			flag=0;
			break;
		}
	}
	if(flag==1)printf("TRUE");
	else printf("FALSE");
}

int main()
{
	SqList *L;
	L=Create();
	PrintfList(L);
	Cmp(L);
 }