1.栈和队列是两种特殊的线性表

运算操作被限定仅仅能在表的一端或两端插入,删除元素,故也称它们为限定的线性表结构

2.栈的基本运算

1).Stackinit(&s) 构造一个空栈

2).Stackempty(s) 推断s是否为空栈,当s为空栈时,函数返回值1 否则 0

3).Push(&s,x) 在栈s 的顶部插入元素x,简称将x入栈

4).Pop(&s,&x) 在栈s

中删除顶元并将其值保存在x单元中返回,简称将x出栈

5)Gettop(s,&x) 读s栈中的顶元素,将其值保存在x 单元中并返回

6)Stacklength(s) 返回栈s中元素的个数,即s的长度

7)Stackfull(s) 判定栈s 是否已满,当s已满时,返回值为1 否则为 0

应用, (){}[] 括号的匹配举例:(待完好)

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>  //system(); 这个指令须要用到此头文件

#include <ctype.h> //toupper要用到

#include <malloc.h> //在内存管理时用到的头文件

#include <string.h>  //字符串的头文件

#define MAX_SIZE 100  //定义栈初始空间的容量

typedef struct      //建立结构体

{

	int top;

	int size;

	char *base;

}STACK;

void push(STACK *s, char e);   //压入元素

void pop(STACK *s, char *e);   //删除元素

void push(STACK *s, char e)

{

	if (s->top + 1 > MAX_SIZE) //假设 此时top之前指向 100的位置,那么就要溢出了,则例通过推断排除溢出的情况,直接退出当前函数

		return;

	*(s->base + s->top) = e; //base指向栈底,top指向栈顶元素的上一层空白处,将空白处填入e

	s->top++;   //空白处填入1后,top指向下一个空白

}

void pop(STACK *s, char *e)

{

	if (s->top <= 1)

		return;

	*e = *(s->base + s->top);

	s->top--;  //将栈顶指针 回移

}

STACK stack;

int result = 0;

void main(int argc, char **argv)

{

	char buf[100];

	int i = 0;

	char temp;

	stack.top = 1;  //数据从stack->base+stack+top 開始存

	stack.size = MAX_SIZE;  //为100

	stack.base = (char *)malloc(sizeof(char)*stack.size);//申请内存空间

	if (stack.base = NULL)

	{

		printf("stack = NULL RETURN");

		return;

	}

	memset(stack.base, '0', sizeof(STACK));

	memcpy(buf, argv[1], strlen(argv[1]));//将须要解析的字符串存在buf中

	buf[strlen(argv[1])] = '\0'; //'\0'来表示结束

	while (buf[i] != '\0')

	if (buf[i] == '(')  //碰到左括号

	{

		push(&stack, buf[i]); //出现左括号,入栈

	}

	else if (buf[i] == ')')  //碰到右括号

	{

		if (stack.top == 1) //假设栈中没有左括号,则错误,result=1

		{

			result = 1;

		}

		else if (*(stack.base + stack.top - 1) == '(');//假设栈里有左括号

		{

			pop(&stack, &temp); //出栈

		}

		i++;

	}

	if (stack.top > 1) //假设括号里还有左括号,缺少右括号

		result = 1;

	if (result == 1)

		printf("Wrong!");

	if (result == 0)

		printf("Right");

}

{}[] 的原理也一样

巴特西

C数据结构-栈和队列,括号匹配举例---ShinePans

1.栈和队列是两种特殊的线性表

2.栈的基本运算

最新文章

热门文章