問題描述

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

演演算法思想

$\quad$ 把字串中的字元逐個分別存入佇列和堆疊，然後逐個出佇列和退棧並比較出佇列的元素和退棧的元素是否相等，若全部相等則該字元是迴文，否則就不是迴文。

函數模組

$（ 1 ） v o i d P a l i n d r o m e (c h a r s t r [])$ ，判斷字元序列是否為迴文。
$（ 2 ） v o i d E n t e r S t r (c h a r s t r [])$ ，從鍵盤輸入迴文序列。
$（ 3 ） v o i d m a i n ()$ ，主函數，迴圈呼叫 $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 [])$ ,當使用者要求退出時，停止執行。
$（ 4 ）$ 堆疊和佇列分別利用 $S t a c k . h$ 和 $L Q u e u e . h$ 檔案。

測試資料

$（ 1 ） A B C D E F E D C B A$
$（ 2 ） A B C D E F F E D C B A$
$（ 3 ） A B C D B C A$

C語言程式

標頭檔案

$S t a c k . 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$

#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;

}

實驗結果

在這裡插入圖片描述

C語言利用佇列和棧實現迴文判斷

迴文判斷