C 语⾔利⽤队列和栈实现回⽂判断
回⽂判断
问题描述
回⽂是指⼀个字符序列以中间字符为基准两边字符完全相同。要求程序从键盘输⼊⼀个字符串，⽤于判断回⽂的不包括字符串的结束标志。
算法思想
把字符串中的字符逐个分别存⼊队列和堆栈，然后逐个出队列和退栈并⽐较出队列的元素和退栈的元素是否相等，若全部相等则该字符是回⽂，否则就不是回⽂。
函数模块
，判断字符序列是否为回⽂。
，从键盘输⼊回⽂序列。
，主函数，循环调⽤，当⽤户要求退出时，停⽌运⾏。
堆栈和队列分别利⽤和⽂件。
测试数据
C 语⾔程序
头⽂件
#ifndef  SEQLIST_H_INCLUDED
#define  SEQLIST_H_INCLUDED
#endif  // SEQLIST_H_INCLUDED
//typedef int DataType;
typedef  struct  snode
{
DataType data ;
struct  snode *next ;
}LSNode ;
void  StackInitiate (LSNode **head )
{
*head =(LSNode *)malloc (sizeof (LSNode ));
(*head )->next =NULL ;
}
int  StackNotEmpty (LSNode *head )
{
if (head ->next ==NULL )return  0;
else  return  1;
}
int  StackPush (LSNode *head ,DataType x )
{
LSNode *p ;
p =(LSNode *)malloc (sizeof (LSNode ));
p ->data =x ;
p ->next =head ->next ;//新的结点插⼊在头结点后⾯
head ->next =p ;//新结点成为栈顶
（1）voidPalindrome (charstr [])（2）voidEnterStr (charstr [])（3）voidmain ()Palindrome (charstr [])，EnterStr (charstr [])（4）Stack .h LQueue .h （1）ABCDEFEDCBA
（2）ABCDEFFEDCBA
（3）ABCDBCA
Stack .h
head->next=p;//新结点成为栈顶
return1;
}
int StackPop(LSNode *head,DataType *x)
{
LSNode *p=head->next;
if(p==NULL)
{
printf("此栈已空！\n");
return0;
}
head->next=p->next;//删除原结点
*x=p->data;
free(p);
return1;
}
int StackTop(LSNode *head,DataType *x)
{
LSNode *p=head->next;
if(p==NULL)
{
printf("堆栈已空！\n");
return0;
}
*x=p->data;
return1;
}
void Destory(LSNode *head)
{
LSNode *p,*s;
p=head;
while(p!=NULL)
{
s=p;
p=p->next;
free(s);
}
}
Lqueue.h
#ifndef LQUEUE_H_INCLUDED
#define LQUEUE_H_INCLUDED
#endif// LQUEUE_H_INCLUDED
//typedef int DataType;
typedef struct qnode
{
DataType data;//为什么不在此处定义两个指针
struct qnode *next;//此处需要使⽤qnode，因此typedef struct qnode }LQNode;//定义结点
typedef struct
{//不带头结点
LQNode *front;
LQNode *rear;
}LQueue;//只是两个指针
void QueueInitiate(LQueue *Q)
{
Q->front=NULL;
Q->rear=NULL;
}
int QueueNotEmpty(LQueue Q)
{
{
if(Q.front==NULL)return0;
else return1;
}
void QueueAppend(LQueue *Q,DataType x)
{
LQNode *p;
p=(LQNode *)malloc(sizeof(LQNode));//申请结点空间
p->data=x;
p->next=NULL;
//rear->a(n-1)，为最后⼀个元素
if(Q->rear!=NULL)Q->rear->next=p;//队列⾮空时，将结点p插⼊在队尾    Q->rear=p;//修改队尾指针
if(Q->front==NULL)Q->front=p;//队列为空时，修改队头指针
}
int QueueDelete(LQueue *Q,DataType *x)
{
LQNode *p;
if(Q->front==NULL)
{
printf("队列已空，⽆可删元素！\n");
return0;
}
else
{
*x=Q->front->data;//取队头元素数据
p=Q->front;//记录队头指针
Q->front=Q->front->next;//出队列，结点脱链
if(Q->front==NULL)Q->rear=NULL;//队列中只有⼀个元素的情况
free(p);
return1;
}
}
int QueeuGet(LQueue *Q,DataType *x)
{
if(Q->front==NULL)
{
printf("队列已空，⽆元素可取！\n");
return0;
}
else
{
*x=Q->front->data;
return1;
}
}
void DestoryList(LQueue *Q)
{
LQNode *p,*p1;//释放空间时必须要两个指针
p=Q->front;
while(p->next!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
}
主⽂件
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
#include"Stack.h"
#include"LQueue.h"
#include<string.h>
void Enterstr(char str[])
{
printf("请输⼊字符串：\n");
scanf("%s",str);
}
void Palindorme(char str[])
{
int len,i,j;
char p,q;
c语言struct头文件
len=strlen(str);
LQueue Q;
LSNode *S;
QueueInitiate(&Q);
StackInitiate(&S);
for(i=0;i<len;i++)
{
StackPush(S,str[i]);
QueueAppend(&Q,str[i]);
}
j=0;
while(StackNotEmpty(S)==1&&QueueNotEmpty(Q)==1) {
StackPop(S,&p);
QueueDelete(&Q,&q);
if(p==q)j++;
}
if(j==len)
printf("此字符串是回⽂！\n");
else
printf("此字符串不是回⽂！！\n");
}
int main()
{
void Enterstr(char str[]);
void Palindorme(char str[]);
char s1[100],s;
while(1)
{
Enterstr(s1);
Palindorme(s1);
printf("输⼊N退出!\n");
scanf("%s",&s);
if(s=='N')break;
}
return0;
}
实验结果

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。