stack.txt

编译系统： Visual C++ 6.0 操作系统： Windows 2000/XP 这几个程序对于学习和理解数据结构有很大的帮助。

/*  2005-03-2  -----------------------------------------------
实验内容：
       有n个字符的字符串，判断字符串是否中心对称。
	   如: xyzzyx和xyzyx都是中心对称的字符串
实验要求：
	   字符串放在单链表中，内容1由栈实现（存储结构自定）
	   并实现利用栈的入栈和出栈完成判断。
-------------------------------------------------------------*/

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

#define max 100


//////////////////定义单链表的结点类型////////////////////
typedef struct node
{
	char data;
	struct node* next;
}LinkList;


/////////////////根据输入的字符(存储在字数组中)建立一个不带结点的单链表/////////////
LinkList* create(char s[])  //函数返回的类型为指针
{
	LinkList *head,   //头指针 
		     *newNode, //newNode始终指向新开的结点
			 *tail;    //tail始终指向链表中的最后一个结点
	
	for(int i=0;s[i]!='\0';i++)
	{
		newNode=(LinkList*)malloc(sizeof(LinkList));  //新开一个结点
		newNode->data=s[i];
		newNode->next=NULL;

		if(i==0)      //如果只输入了一个字符
		{
			head=newNode;
			tail=head;
		}
		else
		{
			tail->next=newNode;  //把新开的结点连接到链表的最后一个结点上
			tail=newNode;
		}
	}
	return head;
}


////////////////////定义栈的存储类型//////////////////////////
typedef struct
{
	char *base;   //栈顶指针（始终指向栈顶元素的下一个位置）
	char *top;    //栈底指针（始终指向栈底）
}stack;

void InitStack(stack &s)      //栈的初始化
{
	s.base=(char*)malloc(max*sizeof(char));
	s.top=s.base;
}
void push(stack &s,char e)   //进栈函数
{
	*s.top++=e;
}
char pop(stack &s,char &e)   //出栈函数
{
	e=*--s.top ;
	return e;
}


///////////////判断以单链表存储的字符串是否对称的函数////////////////
int judge(LinkList *head)
{
	stack s;
	char e;
	InitStack(s);  //定义一个栈并初始化
	
	LinkList* p=head;  //把头指针赋给p,即让p指向第一个结点
	while(p !=NULL)
	{
		push(s,p->data);
		p=p->next;
	}
	p=head;
	while(p!=NULL)   //将栈中的元素弹出，逐个与链表中的元素比较（可以看成是把链表换个方向，然后与原来的链表比较）
	{
		if(p->data == pop(s,e))
			p=p->next;
		else
			break;  //如果不相等，说明不是对称，调处循环
	}
	if(p==NULL) return 1;
	else return 0;
}

void main()
{
	printf("程序说明:\n");
	printf("目的：判断字符串是否关于中心对称.\n");
	printf("方法：字符串用单链表实现，将字符串全部入栈然后比较\n\n");

	char str[max]; //定义一个字符数组，用来存储输入的字符
	LinkList *h;
	while(1)
	{
		printf("\n\n请输入字符串(输入cls清屏,exit退出):");
		gets(str);
		if(strcmp(str,"exit")==0)   break;
		if(strcmp(str,"cls")==0) system("cls");
		
		switch(judge(create(str)))  //根据输入的字符串(存储在字符数组中)建立单链表然后进行判断
		{
		case 1:
			printf("\n			●%s是中心对称的的字符串\n",str);
			break;
		case 0:
			printf("\n			◆%s不是关于中心对称的\n",str);
			break;
		}
	}
}