問題描述

\quad 回文是指一個字符序列以中間字符為基準兩邊字符完全相同，要求程式從鍵盤輸入一個字串，用于判斷回文的不包括字串的結束標志，

演算法思想

\quad 把字串中的字符逐個分別存入佇列和堆疊，然后逐個出佇列和退堆疊并比較出佇列的元素和退堆疊的元素是否相等，若全部相等則該字符是回文，否則就不是回文，

函式模塊

（ 1 ） v o i d P a l i n d r o m e ( c h a r s t r [ ] ) （1） void Palindrome(char str[]) （1）voidPalindrome(charstr[])，判斷字符序列是否為回文，
（ 2 ） v o i d E n t e r S t r ( c h a r s t r [ ] ) （2） void EnterStr(char str[]) （2）voidEnterStr(charstr[])，從鍵盤輸入回文序列，
（ 3 ） v o i d m a i n ( ) （3） void main() （3）voidmain()，主函式，回圈呼叫 P a l i n d r o m e ( c h a r s t r [ ] ) ， E n t e r S t r ( c h a r s t r [ ] ) Palindrome(char str[])，EnterStr(char str[]) Palindrome(charstr[])，EnterStr(charstr[]),當用戶要求退出時，停止運行，
（ 4 ） （4） （4） 堆疊和佇列分別利用 S t a c k . h Stack.h Stack.h和 L Q u e u e . h LQueue.h LQueue.h檔案，

測驗資料

（ 1 ） A B C D E F E D C B A （1） ABCDEFEDCBA （1）ABCDEFEDCBA
（ 2 ） A B C D E F F E D C B A （2）ABCDEFFEDCBA （2）ABCDEFFEDCBA
（ 3 ） A B C D B C A （3）ABCDBCA （3）ABCDBCA

C語言程式

頭檔案

S t a c k . h Stack.h Stack.h

#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;//新結點成為堆疊頂
    return 1;
}
int StackPop(LSNode *head,DataType *x)
{
    LSNode *p=head->next;
    if(p==NULL)
    {
     printf("此堆疊已空！\n");
     return 0;
    }
    head->next=p->next;//洗掉原結點
    *x=p->data;
    free(p);
    return 1;
}
int StackTop(LSNode *head,DataType *x)
{
    LSNode *p=head->next;
    if(p==NULL)
    {
        printf("堆疊已空！\n");
        return 0;
    }
    *x=p->data;
    return 1;
}

void Destory(LSNode *head)
{
    LSNode *p,*s;
    p=head;
    while(p!=NULL)
    {
        s=p;
        p=p->next;
        free(s);
    }
}

L q u e u e . h Lqueue.h 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)return 0;
    else return 1;
}
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");
        return 0;
    }
    else
    {
        *x=Q->front->data;//取隊頭元素資料
        p=Q->front;//記錄隊頭指標
        Q->front=Q->front->next;//出佇列，結點脫鏈
        if(Q->front==NULL)Q->rear=NULL;//佇列中只有一個元素的情況
        free(p);
        return 1;
    }
}
int QueeuGet(LQueue *Q,DataType *x)
{
    if(Q->front==NULL)
    {
        printf("佇列已空，無元素可取！\n");
        return 0;
    }
    else
    {
        *x=Q->front->data;
        return 1;
    }
}
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;
    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;
    }
    return 0;

}

實驗結果