/// 例如xyzzyx， xyzyx 都算是中心对称的字符串。要求用尽可能少的时间完成判断。
#include "stdafx.h"
#include <stdlib.h>
#define MAXSIZE 8
typedef struct node
{
char data;
node* pNext;
}node;
typedef struct stringList
{
node* dataHead;
int number;
}stringList;
typedef struct charStack
{
node* pRear;
}charStack;
//取栈顶函数，执行后栈不变
char getHead(charStack* pCS)
{
if (pCS != NULL && pCS->pRear != NULL)
{
return pCS->pRear->data;
}
else
{
return ”;
}
}
//出栈函数
char pop(charStack* pCS)
{
//pCS为空，返回空值，pCS不改变
if (pCS == NULL || pCS->pRear == NULL)
{
return ”;
}
//pCS仅有一个元素，出栈，pCS置空
else if(pCS->pRear->pNext == pCS->pRear)
{
node* temp = pCS->pRear->pNext;
int tempdata = temp->data;
pCS->pRear = NULL;
free(temp);
return tempdata;
}
else
{
node* temp = pCS->pRear->pNext;
int tempdata = temp->data;
pCS->pRear->pNext = temp->pNext;
free(temp);
return tempdata;
}
}
//入栈函数
char push(charStack* pCS, char& data)
{
node* s = NULL;
//保证pCS有效
while (pCS == NULL)
{
pCS = (charStack*)malloc(sizeof(charStack));
pCS->pRear = NULL;
}
//给s分配空间
while(s == NULL)
{
s = (node*)malloc(sizeof(node));
s->data = data;
s->pNext = NULL;
}
//当pCS为空时，将s作为pCS的唯一元素
if (pCS->pRear == NULL)
{
pCS->pRear = s;
s->pNext = s;
}
else if(pCS->pRear->pNext == pCS->pRear)
{
s->pNext = pCS->pRear;
pCS->pRear->pNext = s;
}
else
{
s->pNext = pCS->pRear->pNext;
pCS->pRear->pNext = s;
}
return s->data;
}
bool isEmpty(charStack* pCS)
{
if (pCS == NULL || pCS->pRear == NULL)
{
return true;
}
else
{
return false;
}
}
//输入字符串的函数，用尾插法建链表
stringList* InputList(void)
{
stringList* head = NULL;
head = (stringList*)malloc(sizeof(stringList));
if (head == NULL)
{
printf("内存分配出错！n");
return NULL;
}
node* datahead = NULL;
node* s = NULL;
node* r = NULL;
char ch;
int dnumber = 0;
printf("请输入一个字符串：n");
ch = getchar();
while(ch != ‘n’)
{
s = (node*)malloc(sizeof(node));
s->data = ch;
if(datahead == NULL)
{
datahead = s;
}
else
{
r->pNext = s;
}
r = s;
scanf("%c", &ch);
dnumber ++;
}
if(r != NULL)
{
r->pNext = NULL;
}
head->dataHead = datahead;
head->number = dnumber;
return head;
}
// 删除链表的函数
void del (stringList* head)
{
if(head == NULL || head->dataHead == NULL)
{
return;
}
node* temp = head->dataHead;
node* p = temp;
while(temp != NULL)
{
p = temp->pNext;
delete(temp);
temp = p;
}
delete(head);
return;
}
// 显示链表的函数
void PrintList(stringList* head)
{
if(head == NULL || head->dataHead == NULL)
{
printf("这是一个空列表。n");
return;
}
node* dhead = head->dataHead;
while(dhead != NULL)
{
printf("%c", dhead->data);
dhead = dhead->pNext;
}
printf("n");
printf("%dn", head->number);
return;
}
//判断字符串是否对称
void Proceed(stringList* pHead)
{
charStack cs;
cs.pRear = NULL;
int number = pHead->number;
node* temp = pHead->dataHead;
//一半元素入栈
for(int i = 0; i < number / 2; i ++)
{
push(&cs, temp->data);
temp = temp->pNext;
}
//若原字符串长度为奇数，则忽略中间的一个字符
if( (number & 1) == 1)
{
i++;
temp = temp->pNext;
}
for(; i < number; i++)
{
if(temp->data == pop(&cs))
{
temp = temp->pNext;
continue;
}
printf("不是对称字符串！n");
return;
}
printf("是对称字符串！n");
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
stringList* head = NULL;
char ch = ‘y’;
while(ch == ‘y’)
{
head = InputList();
PrintList(head);
Proceed(head);
printf("还继续吗？n");
ch = getchar();
getchar();
}
return 0;
}
biggates难得更新的网页 