链栈

- 日理万妓 2023-08-17 15:15 80阅读 0赞

typedef struct LinkNode {
    	ElemType data;
    	struct LinkNode* next;
    }LinkStNode;

初始化

void InitStack(LinkStNode*& s)
    {
    	s = (LinkStNode*)malloc(sizeof(LinkStNode));
    	s->next = NULL;
    }

销毁

void DestroyStack(LinkStNode*& s)
    {
    	LinkStNode* pre = s;
    	LinkStNode* p = pre->next;
    	while (p != NULL)
    	{
    		free(pre);
    		pre = p;
    		p = pre->next;
    	}
    	free(pre);
    }

判断栈是否为空

bool StackEmpty(LinkStNode* s)
    {
    	return (s->next == NULL);
    }

进栈

void Push(LinkStNode * &s, ElemType e)
    {
    	LinkStNode* p = (LinkStNode*)malloc(sizeof(LinkStNode));
    	p->data = e;
    	p->next = s->next;
    	s->next = p;
    }

出栈

bool Pop(LinkStNode * &s, ElemType & e)
    {
    	LinkStNode* p;
    	if (s->next == NULL)
    		return false;
    	else
    	{
    		p = s->next;
    		e = p->data;
    		s->next = p->next;
    		free(p);
    		return true;
    	}
    }

取栈顶元素

bool GetTop(LinkStNode * s, ElemType & e)
    {
    	if (s->next == NULL)
    		return false;
    	else
    	{
    		e = s->next->data;
    		return true;
    	}
    }

括号匹配（）

bool Match(ElemType exp[])
    {
    	bool match = true;
    	ElemType e;
    	int i = 0;
    	LinkStNode* st = (LinkStNode*)malloc(sizeof(LinkStNode));
    	st->next = NULL;
    	while (exp[i] != '\0')
    	{
    		if (exp[i] == '(')
    			Push(st, exp[i]);
    
    		if (exp[i] == ')')
    		{
    			if (GetTop(st, e) == true)
    			{
    				if (e == '(')
    				{
    					Pop(st, e);
    				}
    				else
    				{
    					match = false;
    					break;
    				}
    			}
    			else
    			{
    				match = false;
    				break;
    			}
    		}
    		i++;
    	}
    	if (!StackEmpty(st))
    		return false;
    	DestroyStack(st);
    	return match;
    }

转载于:https://www.cnblogs.com/KIROsola/p/11341966.html