利用链栈和链队列判断字符串是否为回文

一时失言乱红尘 2022-12-16 09:22 135阅读 0赞

基本思想：  
将需要判断的字符分别压入一个空链栈和空链队列中。当字符串全部压入栈和队列后，逐个弹出字符，对链栈和链队列弹出的字符逐个进行比较是否相等，由于栈是先进后出，队列是先进先出，从而相当于对字符串首尾行进比较，从而能判断出字符串是否为回文。  
代码即详细注释如下：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef char DataType;
    struct Node//链栈空节点 
    { 
        DataType      data;
        struct Node*  next;
    };
    typedef struct Node  *PNode;
    typedef struct Node  *LinkStack;
    struct Queue
    { 
        PNode        f;//f指向链队列首元素
        PNode        r;//r指向链队列尾元素
    };
    typedef struct Queue *LinkQueue;
    
    LinkStack SetNullStack_Link()//创建链栈头节点
    { 
        LinkStack top = (LinkStack)malloc(sizeof(struct Node));
        if (top != NULL) 
        top->next = NULL;//必须指定next为NULL,因为要进行头插法创建链栈
        else printf("Alloc failure");
        return top;
    }
    
    int IsNullStack_link(LinkStack top)//判断链栈是否为空
    { 
        if (top->next == NULL)
            return 1;
        else
            return 0;
    }
    void Push_link(LinkStack top, DataType x)//将元素x压入链栈中
    { 
        PNode p;
        p = (PNode)malloc(sizeof(struct Node));
        if (p == NULL)
            printf("Alloc failure");
        else
        { 
            p->data = x;
            p->next = top->next;
            top->next = p;
        }
    }
    void Pop_link(LinkStack top)//弹出链栈栈顶元素
    { 
        PNode p;
        if (top->next == NULL)//判断链栈是否为空
            printf("it is empty stack!");
        else
        { 
            p = top->next;
            top->next = p->next;
            free(p);//弹出后释放节点
        }
    }
    DataType Top_link(LinkStack top)//返回链栈栈顶元素
    { 
        if (top->next == NULL)//判断链栈是否为空或
        { 
            printf("It is empty stack!");
            return 0;
        }
        else
            return top->next->data;
    }
    
    LinkQueue  SetNullQueue_Link()//创建空链队列,f指向队头，r指向队尾
    { 
        LinkQueue lqueue;
        lqueue = (LinkQueue)malloc(sizeof(struct Queue));
        if (lqueue != NULL)//对指针成员进行初始化
        { 
            lqueue->f = NULL;//
            lqueue->r = NULL;
        }
        else
            printf("Alloc failure! \n");
        return  lqueue;
    }
    
    int IsNullQueue_link(LinkQueue lqueue)//判断链队列是否为空
    { 
        return (lqueue->f == NULL);
    }
    
    void EnQueue_link(LinkQueue lqueue, DataType x)//将元素压入链队列中
    { 
        PNode  p;
        p = (PNode)malloc(sizeof(struct Node));
        if (p == NULL)
            printf("Alloc failure!");
        else { 
            p->data = x;
            p->next = NULL;
            if (lqueue->f == NULL)//第一次插入元素时，头尾指针必须同时指向此元素
            { 
                lqueue->f = p;
                lqueue->r = p;
            }
            else
            { 
                lqueue->r->next = p;
                lqueue->r = p;
            }
        }
    }
    void DeQueue_link(LinkQueue lqueue)//删除链队列队头元素
    { 
        struct Node  * p;
        if (lqueue->f == NULL)
            printf("It is empty queue!\n ");
        else
        { 
            p = lqueue->f;//p指向要删除的元素
            lqueue->f = lqueue->f->next;
            free(p);//释放节点
        }
    }
    DataType  FrontQueue_link(LinkQueue lqueue)//返回队头元素
    { 
        if (lqueue->f == NULL)
        { 
            printf("It is empty queue!\n");
            return 0;
        }
        else
            return (lqueue->f->data);
    }
    
    int main()
    { 
        DataType ch;
        int flag;
        LinkStack stack_pal = SetNullStack_Link();
        LinkQueue queue_pal = SetNullQueue_Link();
        ch = getchar();
        while (ch != '#')//输入字符串，以#号结束
        { 
            Push_link(stack_pal, ch);
            EnQueue_link(queue_pal, ch);
            ch = getchar();
        }
        flag = 1;   while(!IsNullQueue_link(queue_pal)&&!IsNullStack_link(stack_pal)) //当链队列和链栈为空时结束循环
        { 
            if (Top_link(stack_pal)!=FrontQueue_link(queue_pal))//当链队列队头元素和链栈栈顶元素相同时
            { 
                flag = 0;
                break;
            }
            else//当链队列队头元素和链栈栈顶元素不同时
            { 
    
             DeQueue_link(queue_pal);
             Pop_link(stack_pal);
    
            }
        }
        if (flag==1)
            printf("this is palindromic");
        else
            printf("this is NOT palindromic");
        return 0;
    }