1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
typedef struct node{
char data;
struct node *next;
}queue,stack,*LinkQueue,*LinkStack;
int push(LinkStack &sHead, char ch){//入栈操作
LinkStack p = (LinkStack)calloc(1, sizeof(stack));
if (p == NULL){
printf("Error calloc.\n");
return ERROR;
}
p->data = ch;
p->next = sHead;
sHead = p;
return OK;
}
char pop(LinkStack &sHead){//出栈
if (NULL == sHead) return ERROR;
LinkStack temp = sHead;
char ch = sHead->data;
sHead = sHead->next;
free(temp);
return ch;
}
int enqueue(LinkQueue &qHead, LinkQueue &qRear, char ch){//进入队列操作
LinkQueue p = (LinkQueue)calloc(1, sizeof(queue));//动态分配空间并初始化
if (p == NULL){
printf("Error calloc_queue.\n");
return ERROR;
}
p->data = ch;
p->next = NULL;
if (NULL != qRear)
qRear->next = p;
if (NULL == qHead)
qHead = qRear;
qRear = p;
return OK;
}
int queueDel(LinkQueue &qHead){//进行队列删除
if (qHead == NULL) return OK;
LinkQueue temp = qHead;
qHead = qHead->next;
free(temp);
return OK;
}
char dequeue(LinkQueue &qHead){//进行出队列操作
char ch = qHead->data;
LinkQueue temp = qHead;
qHead = qHead->next;
queueDel(temp);
return ch;
}
void input(LinkStack &sHead, LinkQueue &qHead,LinkQueue &qRear,int &len){
char ch;
printf("Please input the string which would be judged:");
while (scanf("%c", &ch) && '#' != ch){
push(sHead, ch);//推入栈
enqueue(qHead ,qRear, ch);//进入队列
len++;
}
}
int compare(LinkStack &sHead, LinkQueue &qHead,int len){
int cnt = 0;
while (sHead != NULL && qHead != NULL && cnt <= len/2){//判断一半的栈和队列是否已空
if (pop(sHead) != dequeue(qHead))//比较对应字符是否相同
return ERROR;//不同直接退出比较
cnt++;
}
return OK;//始终相同，匹配
}
void output(LinkStack &sHead, LinkQueue &qHead,int len){
if (compare(sHead, qHead,len))//调用判断函数进行判断是否满足
printf("It is a plalindrome.\n");
else printf("It isn't a plalindrome.\n");
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int len=0;
LinkStack sHead = NULL;//栈的头结点指针
LinkQueue qHead = NULL ,qRear = NULL;//队列的头结点和尾节点指针
input(sHead, qHead,qRear,len);
output(sHead, qHead,len);
return 0;
}
|