/*  2005-03-2  -----------------------------------------------
實(shí)驗(yàn)內(nèi)容：
       有n個(gè)字符的字符串，判斷字符串是否中心對(duì)稱。
	   如: xyzzyx和xyzyx都是中心對(duì)稱的字符串
實(shí)驗(yàn)要求：
	   字符串放在單鏈表中，內(nèi)容1由棧實(shí)現(xiàn)（存儲(chǔ)結(jié)構(gòu)自定）
	   并實(shí)現(xiàn)利用棧的入棧和出棧完成判斷。
-------------------------------------------------------------*/

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

#define max 100


//////////////////定義單鏈表的結(jié)點(diǎn)類型////////////////////
typedef struct node
{
	char data;
	struct node* next;
}LinkList;


/////////////////根據(jù)輸入的字符(存儲(chǔ)在字?jǐn)?shù)組中)建立一個(gè)不帶結(jié)點(diǎn)的單鏈表/////////////
LinkList* create(char s[])  //函數(shù)返回的類型為指針
{
	LinkList *head,   //頭指針 
		     *newNode, //newNode始終指向新開的結(jié)點(diǎn)
			 *tail;    //tail始終指向鏈表中的最后一個(gè)結(jié)點(diǎn)
	
	for(int i=0;s[i]!='\0';i++)
	{
		newNode=(LinkList*)malloc(sizeof(LinkList));  //新開一個(gè)結(jié)點(diǎn)
		newNode->data=s[i];
		newNode->next=NULL;

		if(i==0)      //如果只輸入了一個(gè)字符
		{
			head=newNode;
			tail=head;
		}
		else
		{
			tail->next=newNode;  //把新開的結(jié)點(diǎn)連接到鏈表的最后一個(gè)結(jié)點(diǎn)上
			tail=newNode;
		}
	}
	return head;
}


////////////////////定義棧的存儲(chǔ)類型//////////////////////////
typedef struct
{
	char *base;   //棧頂指針（始終指向棧頂元素的下一個(gè)位置）
	char *top;    //棧底指針（始終指向棧底）
}stack;

void InitStack(stack &s)      //棧的初始化
{
	s.base=(char*)malloc(max*sizeof(char));
	s.top=s.base;
}
void push(stack &s,char e)   //進(jìn)棧函數(shù)
{
	*s.top++=e;
}
char pop(stack &s,char &e)   //出棧函數(shù)
{
	e=*--s.top ;
	return e;
}


///////////////判斷以單鏈表存儲(chǔ)的字符串是否對(duì)稱的函數(shù)////////////////
int judge(LinkList *head)
{
	stack s;
	char e;
	InitStack(s);  //定義一個(gè)棧并初始化
	
	LinkList* p=head;  //把頭指針賦給p,即讓p指向第一個(gè)結(jié)點(diǎn)
	while(p !=NULL)
	{
		push(s,p->data);
		p=p->next;
	}
	p=head;
	while(p!=NULL)   //將棧中的元素彈出，逐個(gè)與鏈表中的元素比較（可以看成是把鏈表?yè)Q個(gè)方向，然后與原來的鏈表比較）
	{
		if(p->data == pop(s,e))
			p=p->next;
		else
			break;  //如果不相等，說明不是對(duì)稱，調(diào)處循環(huán)
	}
	if(p==NULL) return 1;
	else return 0;
}

void main()
{
	printf("程序說明:\n");
	printf("目的：判斷字符串是否關(guān)于中心對(duì)稱.\n");
	printf("方法：字符串用單鏈表實(shí)現(xiàn)，將字符串全部入棧然后比較\n\n");

	char str[max]; //定義一個(gè)字符數(shù)組，用來存儲(chǔ)輸入的字符
	LinkList *h;
	while(1)
	{
		printf("\n\n請(qǐng)輸入字符串(輸入cls清屏,exit退出):");
		gets(str);
		if(strcmp(str,"exit")==0)   break;
		if(strcmp(str,"cls")==0) system("cls");
		
		switch(judge(create(str)))  //根據(jù)輸入的字符串(存儲(chǔ)在字符數(shù)組中)建立單鏈表然后進(jìn)行判斷
		{
		case 1:
			printf("\n			●%s是中心對(duì)稱的的字符串\n",str);
			break;
		case 0:
			printf("\n			◆%s不是關(guān)于中心對(duì)稱的\n",str);
			break;
		}
	}
}