【c语言数据结构】栈代码

第一章 数据结构之栈

• 系列文章目录
• 前言
• • 顺序栈的实现
  • 应用
  • • 括号匹配算法

写本系列博文是为了本人考研方便复习，如果错误欢迎指正。

#include 
#include 
#include 

#define Status bool
#define MAX 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 20

typedef char ElemType;

typedef struct {
	ElemType *base; // 栈底 
	ElemType *top; // 栈顶 
	int stacksize; // 当前分配的栈的存储空间数 
}SqStack,* Stack;

Status InitStack(SqStack &s); // 初始化栈 
Status Push(SqStack &s, ElemType e); // 入栈 
Status Pop(SqStack &s); // 弹栈 
Status Destroy(SqStack &s); // 销毁 

Status InitStack(SqStack &s) {
	s.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
	if (!s.base) {
		exit(OVERFLOW);
	}
	s.top = s.base; // 直接对地址操作 
	//	printf("%p ", s.base);
	//	printf("%p", s.top);	
	s.stacksize = STACK_INIT_SIZE;
	return OK;
}

Status Push(SqStack &s, ElemType e) {

	if ( s.top == s.base + s.stacksize) {
		printf("抱歉栈溢出了！n");
		return ERROR; 
	}
	*(s.top) = e; // top所指的空间给e 
	s.top ++; // 栈顶加1 
	return OK;
}

Status Pop(SqStack &s, ElemType &e) {
	// 当栈顶等于栈底时该栈就空了 
	if ( s.top == s.base) {
		printf("抱歉栈已经到底了！");
		e = NULL;
		return ERROR;
	}
	s.top --;  
	e = *(s.top);
	return OK;
}

// 销毁
Status Destroy(SqStack &s) {
	free(s.base);
	return OK;
} 

int main() {
	ElemType e;
	SqStack s;
	InitStack(s);

	char *str;
	str = (char *)malloc(30 * sizeof(char));
	printf("请输入一个字符串！：");
	scanf("%s", str);
	int len = strlen(str);
	for (int i = 0; i < len; i++) {
		Push(s, *(str + i));
	}
	for (int i = 0; i < len; i++) {
		Pop(s, e);
		printf("%cn", e);
	}
	Destroy(s);
	free(str);
	return 0;
} 

// 括号匹配算法 
void match() {
//	char str[STRINGSIZE], e;
	char *str, e;
	str = (char *)malloc(STRINGSIZE * sizeof(char));
	printf("请输入想要匹配的括号字符串：");
	scanf("%s", str);
	int len = strlen(str);
	SqStack s;
	InitStack(s);
	
	// 字符串遍历 
//	for (int i = 0; i < len; i++) {
//      str = str + i; 这种代码千万别写 
//		printf("%cn" , *(str + i)); 
//	}
	for (int i = 0; i < len; i++) {
		if ( str[i] == '{' || str[i] == '[' || str[i] == '(') {
			Push(s, str[i]);
			printf("入栈%cn", str[i]);
		} else {
			// 如果读取的是有括号时 
			Pop(s, e);
			printf("出栈%cn", e);
			if ( e == NULL) {
				printf("右括号多余！");
				Destroy(s);
				free(str);
				return; 
			}
			switch (str[i]) {
				case '}':
					if ( e == '{') break;
				case ']':
					if ( e == '[') break;
				case ')':
					if ( e == '(') break;
				default:
					printf("括号匹配失败！");
					Destroy(s);
					free(str);
					return;
			}
		}
	}
	Pop(s, e);
	if (e == NULL) {
		printf("匹配成功！"); 
	} else {
		printf("左括号多余！"); 
	}
	Destroy(s);
	free(str);
	return; 
}