回文序列

╰半夏微凉° 2022-07-16 13:27 271阅读 0赞

2016年8月1日13:55:05
        编写一个算法,判断任意给定的字符序列是否是回文序列,
        什么是回文序列?
        所谓回文是指一个字符序列顺着看和倒着看是完全相同的字符序列,例如12344321,12321
        分析:可以通过构造栈和队列来实现,可先把任意给定的字符序列存放到队列和栈中,然后将字符序列出队和出栈,
            比较出栈和出队列的字符是否相等,
            1>若相同,则继续出栈,出队列,继续进行比较是否相等,直到堆栈和队列为空,
            2>若不同,则说明该字符序列不是回文数,直接输出判断的结果,不是回文数;
            3.在比较的过程中,如果堆栈出栈的字符和队列中出队的字符一直相同,此时堆栈和队列都为空时,
                说明给点的字符序列是回文数

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    typedef char DataType;
    
    //结点的结构体类型定义
    typedef struct node  
    {
        DataType data;//数据域
        struct node * pNext;//指针域
    }linkList;
    
    //栈的结构体类型定义
    typedef struct stack
    {
        linkList * pTop;//指向栈顶元素
        linkList * pBottom;//指向栈底元素
    }linkStack;
    
    //队列结构体类型定义
    typedef struct
    {
        linkList * front;//指向队头元素
        linkList * rear;//指向队尾元素的下一个元素
    }linkQueue;
    
    //函数前置声明
    void initLinkQueue(linkQueue * Q);//初始化队列
    void traverseLinkQueue(linkQueue * Q);//遍历队列
    int  isEmpty(linkQueue * Q);//判断队列是否为空
    int  enLinkQueue(linkQueue * Q,DataType element);//链式队列入队
    int  deLinkQueue(linkQueue * Q,DataType * element);//链式队列出队
    int  getHead(linkQueue * Q,DataType * element);//获取队首元素
    void clearLinkQueue(linkQueue * Q);//链式队列的销毁
    void initLinkStack(linkStack * S);//初始化链式栈
    int  isEmpty(linkStack * S);//判断链式栈是否为空
    int  pushLinkStack(linkStack * S,DataType element);//链式栈的压栈操作
    int  popLinkStack(linkStack * S,DataType * element);//链式栈弹栈操作
    int  getTop(linkStack * S, DataType * element);//获取链式栈的栈顶元素
    int  getLength(linkStack * S);//获取链式栈的长度
    void destroyLinkStack(linkStack * S);//链式栈的销毁
    
    
    
    //初始化链式队列
    void initLinkQueue(linkQueue * Q)
    {
        Q->front = (linkList * )malloc(sizeof(linkList));
        if(!Q->front)
        {
            printf("动态内存分配失败!\n");
            exit(-1);
        }
        Q->rear = Q->front;
        Q->front->pNext = NULL;
        return;
    }
    
    //判断队列是否为空,为空返回1,否则返回0;
    int isEmpty(linkQueue * Q)
    {
        if(NULL == Q->front->pNext)
            return 1;
        else
            return 0;
    }
    
    //链式队列入队操作,入队成功返回1,入队失败返回0;
    int  enLinkQueue(linkQueue * Q,DataType element)
    {
        linkList * pNew ;
    
        pNew = (linkList * )malloc(sizeof(linkList));
        if(!pNew)
        {
            printf("动态内存分配失败!\n");
            exit(-1);
        }
        pNew->data = element;
        pNew->pNext = NULL;
        Q->rear->pNext = pNew;
        Q->rear = pNew;
        return  1;
    }
    
    //链式队列的出队操作,出队成功返回1,否则返回0
    int  deLinkQueue(linkQueue * Q,DataType * element)
    {
        linkList * pFree;
    
        if( isEmpty(Q) )
        {
            printf("队列为空,无法继续出队!\n");
            return 0;
        }
        else
        {
            pFree = Q->front->pNext;
            *element = pFree->data;
            Q->front->pNext = pFree->pNext;
            if(pFree == Q->rear)
            {
                Q->rear = Q->front;
            }
            free(pFree);
            return 1;
        }
    }
    
    //获取队列的队头元素,成功返回1,失败返回;
    int  getHead(linkQueue * Q,DataType * element)
    {
        linkList * pHead;
        if( isEmpty(Q) )
            return 0;
        pHead = Q->front->pNext;
        *element = pHead->data;
        return 1;
    
    }
    
    //遍历队列
    void traverseLinkQueue(linkQueue * Q)
    {
        linkList * pCur;
        pCur = Q->front->pNext;
        if(!pCur)
        {
            printf("队列为空!\n");
            return;
        }
        while(pCur)
        {
            printf("%c",pCur->data);
            pCur = pCur->pNext;
        }
        return ;
    }
    
    //清空队列,在使用完队列之后,需要将链式队列中的结点空间全部释放
    void clearLinkQueue(linkQueue * Q)
    {
        while(Q->front)
        {
            Q->rear = Q->front->pNext;
            free(Q->front);
            Q->front = Q->rear;
        }
        return;
    }
    
    //链式栈的初始化
    void initLinkStack(linkStack * S)
    {
        S->pTop = (linkList * )malloc(sizeof(linkList));
        if(!S->pTop)
        {
            printf("动态内存分配失败!\n");
            exit(-1);
        }
        S->pBottom = S->pTop;
        S->pBottom->pNext = NULL;
        return ;
    }
    
    //判断链式栈是否为空,若为空则返回1,不为空则返回0;
    int  isEmpty(linkStack * S)
    {
        if(S->pBottom == S->pTop)
            return 1;
        else
            return 0;
    }
    
    //链式栈的压栈操作
    int  pushLinkStack(linkStack * S,DataType element)
    {
        linkList * pNew;
    
        pNew = (linkList * )malloc(sizeof(linkList));
        if(NULL == pNew )
        {
            printf("动态内存分配失败!\n");
            exit(-1);
        }
        pNew->data = element;
        /*if( NULL == pTop ) { pNew->pNext = NULL; pTop = pNew; } else { pNew->pNext = pTop; pTop = pNew; }*/
        pNew->pNext = S->pTop;
        S->pTop = pNew;
        return 1;
    }
    
    //链式栈的弹栈操作
    int  popLinkStack(linkStack * S,DataType * element)
    {
        linkList * pFree;
    
        if( isEmpty(S) )
        {
            printf("栈为空,无法继续出栈");
            return 0;
        }
    
        pFree = S->pTop;
        *element = pFree->data ;
        S->pTop = S->pTop->pNext;
        free(pFree);
        return 1;
    }
    
    //获取链式栈的栈顶元素
    int  getTop(linkStack * S, DataType * element)
    {
        if(isEmpty(S))
            return 0;
        *element = S->pTop->data ;
        return 1;
    }
    
    //获取链式栈的长度
    int  getLength(linkStack * S)
    {
        int i = 0;
        linkList * pCur;
        pCur = S->pTop;
        /* if(NULL == pCur) { printf("栈为空!\n"); return 0; } */
        while( pCur )
        {
            pCur = pCur->pNext;
            i++;
        }
        return i;
    }
    
    //链式栈的销毁
    void destroyLinkStack(linkStack * S)
    {
        while(S->pTop)
        {
            S->pBottom = S->pTop->pNext;
            free(S->pTop);
            S->pTop = S->pBottom;
        }
        return;
    }
    
    int main(void)
    {
        linkStack S;
        linkQueue Q;
        DataType ch;
        DataType ch1;
    
        //队列,栈的初始化
        initLinkStack(&S);
        initLinkQueue(&Q);
    
        //从键盘接受用户输入的字符
        printf("请输入一个字符序列:");
        while('\n' != (ch = getchar()))
        {
            pushLinkStack(&S,ch);
            enLinkQueue(&Q,ch);
        }
    
        //将用户输入的字符打印输入
        printf("您所输入的字符序列:");
        traverseLinkQueue(&Q);
        printf("\n");
    
        //将队列,栈中的字符序列依次出队,出栈
        //如果这个个字符不同,则说明不是回文,
        printf("出队序列 出栈序列\n");
        while( !isEmpty(&S) )
        {
            deLinkQueue(&Q,&ch);
            printf("%-10c",ch);
            popLinkStack(&S,&ch1);
            printf("%-4c\n",ch1);
            if(ch1!=ch)
            {
                printf("该字符序列不是回文!\n");
                return 0; 
            }
        }
        printf("该字符序列是回文!\n");
    
        return 0;
    }