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");
}
{}[] 的原理也一样