链栈实现括号匹配

发表于

链栈实现括号匹配

  数据结构中有一种结构叫做栈，它是一种先入后出的结构，通过这个程序的编写，基本上颠覆了我对于指针的认识，我才发现我对于c语言的指针并没有深入理解，我仅仅是对于一级指针有所了解。指针的值和指针所指向的对象我还有点搞不清楚。

这个程序是括号的检验，因为之前写过顺序栈，这次想用链栈实现，使用尾插法，并让指针域指向上一个节点姐可以形成栈，通过这个程序我认识到了在动手写程序之前把逻辑搞清楚是很重要的，这个程序的逻辑就是，输入括号-> 若为左括号入栈，若为右括号就与栈顶括号进行匹配->此时只有两种情况，1.匹配，即删去栈顶节点，并判断是否为空栈，若为空栈就结束程序，输出匹配。2.不匹配，输出不匹配，结束程序。把逻辑理清楚后剩下的就是编程的事了，以后最好把逻辑用注释写在开头。

编程中我犯了大忌，在函数里申请内存，一出函数就被释放了，导致程序崩溃。还有往函数里传递指针，函数形参的问题。代码如下：

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct SqStack
{
    char c;
    struct SqStack *next;
}SqStack;

void InitStack(SqStack *s,SqStack **top)
{
    *top=s;
}

void GetTop(SqStack *s,char *e,SqStack *top)
{
    if(top->next==NULL)
    {
        printf("空栈\n");
        exit(0);
    }
    *e=top->next->c;
}
void Push(SqStack *&s,SqStack *&top,char c)//入栈，先对原来的top赋值，然后再申请新空间，top指向新空间
{
    SqStack *temp;
    temp=(SqStack *)malloc(sizeof(SqStack));
    top->c=c;
    temp->next=top;
    top=temp;
}
int match(char l, char r)//减检验，若为左括号就入栈，右括号才进行检验,返回值为-1，不匹配，为0，正常入栈，为1，消除栈顶。
{
    if(r=='('||r=='['||r=='{')
        return 0;
    if(r==')')
    {
        if(l!='(')
            return -1;
        else
            return 1;
    }
    if(r==']')
    {
        if(l!='[')
            return -1;
        else
            return 1;
    }
    if(r=='}')
    {
        if(l!='{')
            return -1;
        else
            return 1;
    }
}
void pop(SqStack *&s,SqStack *&top)
{
    top->next=top->next->next;
}
int Isempy(SqStack *&s,SqStack *&top)
{
    if(top->next==NULL)
    {
        return 1;
    }
    else
        return 0;
}
int main()
{
    SqStack *base;
    SqStack *top;
    SqStack *s;
    s=(SqStack *)malloc(sizeof(SqStack));
    s->next=NULL;
    InitStack(s,&top);
    char ch,zh;
    scanf("%c",&ch);
    Push(s,top,ch);
    while((ch=getchar())!='\n')//进行括号的输入，若遇到右括号，与栈顶元素进行配对，配对成功即将栈顶元素出栈，否则输出不配对，终止程序
    {
        scanf(" %c",&ch);
        GetTop(s,&zh,top);
        if(match(zh,ch)==-1)//如果为右括号且不匹配
        {
            printf("%c     ------    %c",zh,ch);
            printf("不匹配\n");
            exit(0);
        }
        if(match(zh,ch)==0)//若为左括号i，直接入栈
        {
            Push(s,top,ch);
        }
        if(match(zh,ch)==1)//若为右括号且匹配，pop()
        {
            pop(s,top);
            if(Isempy(s,top)==1)
            {
                printf("匹配");
                exit(0);
            }
        }
    }

}
这两天睡眠相当不好，不知道为什么。还有和大二一起做的课程表app项目感觉自己被轻视了，其实被轻视也很正常，因为我现在的确做不出什么东西。但我相信总有一天，我会打脸的。也许就是我大二的时候。为了做这个app我又要去学java和android，前段时间学的python又要荒废了，我希望这次能够有始有终，python上个暑假我就开始学了，直到现在连皮毛都没学到。