/******************************************************************
* * 文件名：4.23.c
* * 創 建 人：龍珩
* * 日    期：2008-12-14
* * 描    述：以塊鏈結構作串的存儲結構，判別給定串是否具有對稱性
******************************************************************/

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

typedef struct _Chunk //定義塊鏈結構的結構體
{ 
	char ch; 
	struct _Chunk *next; 
} Chunk; 

Chunk* Ch_Create(const char *str) //創建塊鏈結構，同時存入獲得的字符串
{ 
	Chunk *head = NULL, *tail, *node; 

	while(*str) //當前字符串指針所指處不為空時存入數據
	{ 
		node = (Chunk *)malloc(sizeof(Chunk)); 
		node->ch = *str; 
		node->next = NULL; 
		if (head == NULL) 
		{ 
			head = node; 
			tail = node; 
		} 
		tail->next = node; 
		tail = node; 
		str++;
	} 
	return head; 
} 

void Ch_Print(Chunk *node) //輸出串
{ 
	while(node) 
	{ 
		printf("%c", node->ch); 
		node = node->next; 
	} 
	printf("\n"); 
} 

int Ch_Length(Chunk *node) //測量串的長度
{
	int len = 0;

	while(node)
	{
		len++;
		node = node->next; 
	}
	return len;
}

int Ch_Symmetry(Chunk * node, int len) //判斷串的對稱性
{
	int i,k;
	Chunk * S1 = node, * S2 = node;

	if(len%2) //判斷串長度的奇偶性
	{
		for(i=1;i<(len/2);i++) //奇數時S1指向L/2個節點，S2指向L/2+2個節點
		{
			S1 = S1->next;
		}
		S2 = S1->next->next;
	}
	else
	{
		for(i=1;i<(len/2);i++) ////奇數時S1指向L/2個節點，S2指向L/2+1個節點
		{
			S1 = S1->next;
		}
		S2 = S1->next;
	}
	for(i=1;(i<=(len/2)) && (S1->ch)==(S2->ch);i++) //同步向兩邊分開比較
	{
		S1 = node;
		for(k=1;k<((len/2)-i);k++)
		{
			S1 = S1->next;
		}

		S2 = S2->next;
	}
	if(i > (len/2)) //若i>(len/2)，說明比較全部相等，是對稱的
		return 1;
	else
		return 0;
	
}

void main()
{
	Chunk * list; 
	char ch[80];
	printf("請輸入要判斷的字符串\n");
	gets(ch);
	list=Ch_Create(ch);
	printf("輸入的字符串為\n");
	Ch_Print(list);
	printf("是長度為");
	printf("%d",Ch_Length(list));
	if(Ch_Symmetry(list,Ch_Length(list)))
		printf("的對稱字符串！\n");
	else
		printf("的不對稱字符串！\n");
}