4.23.c

数据结构练习。。。。判断输入字符串是否为对称的

/******************************************************************
* * 文件名：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");
}