西电数据结构上机题——回文数判断用栈实现
【摘要】
设单链表中存放有n个字符,试编写算法,判断该字符串是否有中心对称的关系,例如xyzzyx是中心对称的字符串。(提示:将单链表中的一半字符先依次进栈,然后依次出栈与单链表中的另一半字符进行比较。) 我的代码...
设单链表中存放有n个字符,试编写算法,判断该字符串是否有中心对称的关系,例如xyzzyx是中心对称的字符串。(提示:将单链表中的一半字符先依次进栈,然后依次出栈与单链表中的另一半字符进行比较。)
我的代码 仅供参考
//判字符串是否回文
#include<stdio.h>
#include<malloc.h>
#include<string.h>
//定义单链表结构类型
typedef char datatype;
typedef struct node
{ datatype data;
struct node *next;
}linklist;
//定义顺序栈结构类型
const int maxsize=40;
typedef struct
{ datatype elements[maxsize];
int top;
}stack;
void setnull(stack *&);
int length(linklist*);
void printlink(linklist*);
void create(linklist *&,datatype*);
void push(stack*,datatype);
datatype pop(stack*);
int symmetry(linklist*,stack*);//判字符串是否回文的函数声明
int main()
{
linklist *head;stack *s;
datatype str[80];
gets(str);
create(head,str);
printlink(head);
setnull(s);
if(symmetry(head,s)) printf("字符串\"%s\"是回文\n",str);
else printf("字符串\"%s\"不是回文\n",str);
}
//栈初始化
void setnull(stack *&s)
{
s=(stack*)malloc(sizeof(stack));
s->top=-1;
}
//求单链表长度
int length(linklist*head)
{ linklist *p=head->next;
int n=0;
while(p!=NULL){ n++; p=p->next; }
return n;
}
//输出单链表
void printlink(linklist*head)
{ linklist *p=head->next;
while(p!=NULL)
{ printf("%c",p->data);
p=p->next;
}
printf("\n");
}
//建立具有头结点的单链表
void create(linklist *&head,datatype*str)
{ datatype *p=str;
linklist *s,*r;
head=(linklist*)malloc(sizeof(linklist));
r=head;
while(*p!='\0')
{
s=(linklist*)malloc(sizeof(linklist));
s->data=*p;
r->next=s;
r=s;
p++;
}
r->next=NULL;
}
//顺序栈入栈
void push(stack*s,datatype e)
{
s->top++;
s->elements[s->top]=e;
}
//顺序栈出栈
datatype pop(stack*s)
{
datatype temp;
s->top--;
temp=s->elements[s->top+1];
return temp;
}
//添加判字符串是否中心对称算法
int symmetry(linklist*head,stack*s)
{
int l=length(head);
linklist *p=head->next;
for(int i=1;i<=l/2;i++)
{
push(s,p->data);
p=p->next;
}
if(l%2==1)p=p->next;
while(p!=NULL)
{
if(p->data==pop(s))
{
p=p->next;
}
else return 0;
}
return 1;
}
- 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
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
文章来源: zstar.blog.csdn.net,作者:zstar-_,版权归原作者所有,如需转载,请联系作者。
原文链接:zstar.blog.csdn.net/article/details/108672222
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)