以前寫的,用循環(huán)隊列和順序棧實現(xiàn)的
也可以用指針實現(xiàn)
分別有兩個指針,一個指向開始,一個指向結尾,各取一個字符比較,相等的話,前邊的向后移動一個,后邊的向前移動一個,直到兩個指針指向同一個位置,則為回文,中途要是不相等或者最后沒有指向同一個位置,則不是回文
////
//數(shù)據(jù)結構:循環(huán)隊列和順序棧
//算法思想:
//1.將字符串按照用戶輸入的順序分別入棧和隊列
//2.分別從隊列和棧中取出首個字符
//3.比較取出的字符,若相等,繼續(xù)分別從隊列和棧中取首個字符；否則跳出循環(huán),并設置標志flag=0;
//4.若隊列和棧中的字符取完,則結束,設置標志flag=1;
//5.flag=1,表示字符從前往后和從后往前的序列完全匹配,該字符串屬于回文
//6.flag=0,表示字符從前往后和從后往前的序列不完全匹配,該字符串不屬于回文
#include
#include
#define m 100
typedef struct
{
char stack[m];
inttop;
}stackstru;// 定義棧
typedef struct {
char queue[m];
intfront;
intrear;
}queuestru; //定義隊列
voidmain()
{
//函數(shù)聲明
int stinit(stackstru *s); //初始化順序棧
int stempty(stackstru *s);//判斷棧是否為空
int stpush(stackstru *s,char x);//入棧
char stpop(stackstru *s); //出棧
int quinit(queuestru *q); //初始化循環(huán)隊列
int quempty(queuestru *q);//判斷隊列是否為空
int enqueue(queuestru *q,char e); //入隊
char dequeue(queuestru *q); //出隊
//
char c;
int flag=0;
stackstru *s=(stackstru *)malloc(sizeof(stackstru)); //為順序棧申請空間
queuestru *q=(queuestru *)malloc(sizeof(queuestru)); //為隊列申請空間
stinit(s); //初始化棧
quinit(q); //初始化隊列
printf("Input a string:\n");//輸入字符串,輸入@標示輸入結束.
while((c=getchar())!='@') //將輸入的字符串入棧和隊列
{
putchar(c); //輸出輸入的字符
stpush(s,c);//字符進棧
enqueue(q,c); //字符進隊列
}
printf("\n");
printf("End input!\n"); //提示信息
while(stempty(s)) //棧中還有元素
{
if(stpop(s)==dequeue(q)) //出棧的字符與出隊列的字符匹配
{
flag=1; //將標志設置為1
continue; //繼續(xù)從棧和隊列中區(qū)字符
}
else //字符不匹配
{
flag=0;
break;//跳出循環(huán),將標志設置為0
}
}
if(flag==1)
printf("This string is palindrome!\n"); //標志位為1,完全匹配,是回文

else
printf("This string isn't palindrome!\n");//標志位為0,不完全匹配,不是回文
}
int stinit(stackstru *s)
{
s->top=0;
return 1;
} //初始化棧
int stempty(stackstru *s)
{
if(s->top==0) //棧頂為空
{
return 0;
}
else
{
return 1;
}
} //判斷棧是否空
int stpush(stackstru *s,char x)
{
if(s->top==m)//棧滿
{
printf("The stack is overflow!\n"); //輸出提示信息
return 0;
}
else //棧未滿
{
s->top=s->top+1;//棧頂后移
s->stack[s->top]=x; //字符入棧
return 1;
}
}//入棧操作
char stpop(stackstru *s)
{
char y;
if(s->top==0)//棧為空
{
printf("The stack is empty!\n"); //輸出提示信息
return ' ';//返回空格
}
else //棧不為空
{
y=s->stack[s->top];//取出棧頂元素
s->top=s->top-1; //棧頂指示移動
return y;
}
} //出棧操作
int quinit(queuestru *q)
{
q->front=0;
q->rear=0;
return 1;
}//初始化為一個空的循環(huán)隊列
int quempty(queuestru *q)
{
if(q->front==q->rear) //隊頭和隊尾相等
{
return 0;
}
else
{
return 1;
}
}//判斷隊列是否為空
int enqueue(queuestru *q,char e)
{
if((q->rear+1)%m==q->front) //隊列已滿
{
printf("The queue is overflow!\n"); //提示信息
return 0;
}
else
{
q->queue[q->rear]=e;//入隊
q->rear=(q->rear+1)%m;//移動隊尾指針
return 1;
}
} //入隊操作
char dequeue(queuestru *q)
{
char f;
if(q->front==q->rear)//隊列為空
{
printf("The queue is empty!\n");//提示信息
return 0;
}
else
{
f=q->queue[q->front]; //取出隊首元素
q->front=(q->front+1)%m;//移動對頭指針
return f;
}
}//出隊操作