C语言如何用顺序栈实现回文序列判断

时间:2022-09-27 19:02:04

我是采用了两个栈值得比较大小判断得(可能比较浪费空间但是代码我感觉简单一点)

首先是定义一个栈的结构元素,由于是字符串类型就直接定义一个char的数组就可以:.

?
1
2
3
4
5
typedef struct stack
{
    char data[MAX_SIZE];      //储存字符串//
    int top;                  //记录栈顶//
}SeqStack;

下来就是初始化,我这里是用的耿国华老师的方法就直接给一个top元素指向栈顶,传入的指针地址:.

?
1
2
3
4
void Initstack(SeqStack *S)   //初始化栈,让top指向栈顶//
{
    S->top=-1;
}

下面就是创建顺序栈了,元素只要没满就一直可以入住:

?
1
2
3
4
5
6
7
8
9
10
int Push(SeqStack *S,char x)  //压栈,只要top小于MAX_SIZE-1就可以继续入栈//
{
    if(S->top<=MAX_SIZE-1)
    {
    S->top++;
    S->data[S->top]=x;
    }else{
        return -1;;
    }
}

下面是核心函数,操作实现回文序列的判断,我注释的比较清楚直接看就可以了:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void Pop(SeqStack *S)        //出栈操作,也是最主要的操作//
{
    SeqStack *p;                      
    p=(SeqStack*)malloc(sizeof(SeqStack));  //建立一个新的空栈,由于是指针类型要分配动态地址//
    Initstack(p);                           //给新的栈进行初始化//
    int i=S->top/2;                         //i用来分割两个字符串,将第二个字符串赋给新的空栈//
    int j=i-1;                              //j用来记录除了@之外的其他字符数量大小//
    while(S->top!=i)                        //开始对空栈进行赋值,对原来的栈开始清空(清空一般大小)//
    {
        p->top++;
        p->data[p->top]=S->data[S->top];
        S->top--;
    }
    S->top=S->top-2;                        //让原来的栈直接指向数字,跨过了字符@//
    for(int k=0;k<i-1;k++)                  //循环次数由i-1决定,也就是出去@字符之后的其他需要比较的字符//
    {
        if(S->data[S->top]==p->data[p->top])  //由于栈的特点先进后出,所以新栈的存储顺序和去掉@字符之后的旧栈的存储顺序是一样的,所以这里直接比较//
        {
            j--;                             //j是定义需要比较字符的大小,只要两个栈的元素ASCLL相等j就减一,如果全部相等j为0,该字符串就是互为回文序列//
        }
        S->top--;                            //两个top指针向下值//
        p->top--;
        if(j==0)                         //判断//
        {
            printf("两个字符串互为回文序列!");
        }
    }
    if(j!=0)
    {
        printf("两个字符串不互为回文序列!");
    }
    free(p);                       //free掉分配的空间//
}

下面附上整个代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
typedef struct stack
{
    char data[MAX_SIZE];      //储存字符串//
    int top;                  //记录栈顶//
}SeqStack;
void Initstack(SeqStack *S)   //初始化栈,让top指向栈顶//
{
    S->top=-1;
}
int Push(SeqStack *S,char x)  //压栈,只要top小于MAX_SIZE-1就可以继续入栈//
{
    if(S->top<=MAX_SIZE-1)
    {
    S->top++;
    S->data[S->top]=x;
    }else{
        return -1;;
    }
}
void Pop(SeqStack *S)        //出栈操作,也是最主要的操作//
{
    SeqStack *p;                      
    p=(SeqStack*)malloc(sizeof(SeqStack));  //建立一个新的空栈,由于是指针类型要分配动态地址//
    Initstack(p);                           //给新的栈进行初始化//
    int i=S->top/2;                         //i用来分割两个字符串,将第二个字符串赋给新的空栈//
    int j=i-1;                              //j用来记录除了@之外的其他字符数量大小//
    while(S->top!=i)                        //开始对空栈进行赋值,对原来的栈开始清空(清空一般大小)//
    {
        p->top++;
        p->data[p->top]=S->data[S->top];
        S->top--;
    }
    S->top=S->top-2;                        //让原来的栈直接指向数字,跨过了字符@//
    for(int k=0;k<i-1;k++)                  //循环次数由i-1决定,也就是出去@字符之后的其他需要比较的字符//
    {
        if(S->data[S->top]==p->data[p->top])  //由于栈的特点先进后出,所以新栈的存储顺序和去掉@字符之后的旧栈的存储顺序是一样的,所以这里直接比较//
        {
            j--;                             //j是定义需要比较字符的大小,只要两个栈的元素ASCLL相等j就减一,如果全部相等j为0,该字符串就是互为回文序列//
        }
        S->top--;                            //两个top指针向下值//
        p->top--;
        if(j==0)                         //判断//
        {
            printf("两个字符串互为回文序列!");
        }
    }
    if(j!=0)
    {
        printf("两个字符串不互为回文序列!");
    }
    free(p);                       //free掉分配的空间//
}
int main()
{
    SeqStack S;
    char x;
    int m=0;
    Initstack(&S);
    printf("请输入第一串字符\n");
    while(m!=2)                            //因为只需要输入两个字符串的判断,判断条件为m!=2//
    {
        scanf("%c",&x);
        if(x=='@')                           //输入@后表明第一个字符串结束//
        {
            m++;
            if(m==1)
            {
                printf("请输入第二串字符:\n");
            }
        }
        Push(&S,x);
    }
    Pop(&S);
    return 0;
}

下面加一个例子:

判断3+1与1+3是否为回文序列

C语言如何用顺序栈实现回文序列判断

以上就是C语言如何用顺序栈实现回文序列判断的详细内容,更多关于C语言顺序栈实现回文序列判断的资料请关注服务器之家其它相关文章!

原文链接:https://blog.csdn.net/qq_59002046/article/details/120758582