栈的操作

从今天开始，重写《数据结构C语言版：严蔚敏》一书里的程序。毕竟数据结构是一个程序员的内功。以后定期每隔一天更新一次。若对数据结构不熟悉的同学可以一看，现在先写了顺序栈的代码

P.S. 所有代码在C-free 5.0上通过编译运行，程序里用到一个common.h的头文件，里面保存一些常用的宏定义

 

栈的特性：后进先出。。。

以下是顺序栈的结构：SeqStack.h

 

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct SqStack{
	SElemType *base;
	SElemType *top;
	int stackSize;
}SqStack;

 

栈的ADT（abstract data type，抽象数据类型） 有initStack,destroyStack,clearStack,StackEmpty,StackLength,getTop,push,pop

 

seqStack.c为具体实现：

#include <common.h>
#include <stdio.h>
#include "SeqStack.h"

Status initStack(SqStack *s){
	s->base = (SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!s->base){
		exit(OVERFLOW);
	}
	s->top = s->base;
	s->stackSize = STACK_INIT_SIZE;
	return OK;
}

Status destroyStack(SqStack *s){
	free(s->base);
	s->base = NULL;
	s->top = NULL;
	s->stackSize = 0;
	return OK;
}

Status clearStack(SqStack *s){
	s->top = s->base;
	return OK;
}

Status stackEmpty(SqStack *s){
	if(s->base == s->top) return TRUE;
	return FALSE;
}

int stackLength(SqStack *s){
	return (s->top - s->base);
}

Status getTop(SqStack *s, SElemType *e){
	if(s->top == s->base)
		return ERROR;
	*e = *(s->top - 1);
	return OK;
}

Status push(SqStack *s, SElemType e){
	if(s->top - s->base >= s->stackSize){
		printf("realloc\n");
		s->base = (SElemType *) realloc(s->base,(s->stackSize + STACKINCREMENT)*sizeof(SElemType));
		if(!s->base) exit(OVERFLOW);
		s->top = s->base + s->stackSize;
		s->stackSize += STACKINCREMENT;
	}
	*s->top++ = e;
	return OK;
}

Status pop(SqStack *s, SElemType *e){
	if(s->top == s->base) return ERROR;
	*e = *--s->top;
	return OK;
}

void printSqStack(SqStack *s){
	if(s->base == s->top){
		printf("stack is null");
		return;
	}
	SElemType *tmp = s->top;
	while(--tmp != s->base){
		printf("%d ",*tmp);
	}
	printf("%d\n",*s->base);
}

 

定义了ADT后，就可以用栈进行相关的操作，利用栈先进后出的特性，可以进行数制转换，括号匹配的检验和行编辑程序

 

conversion.c 利用栈进行数制转换的代码

 

typedef int SElemType;
#include"SeqStack.c"

//输入非负十进制数，打印其十六进制 
void dec2hex(){
	SqStack s;
	int a,e;
	initStack(&s);
	scanf("%d",&a);
	while(a){
		push(&s,a % 16);
		a /= 16;
	}
	while(!stackEmpty(&s)){
		pop(&s,&e);
		printf("%d",e);
	}
	printf("\n");
}

main(){
	dec2hex();
}

 

bracketMatch.c 利用栈进行括号匹配的代码

/* 括号匹配算法，只对()[]有效 */ 
typedef char SElemType;
#include"SeqStack.c"

void bracketMatch(){
	SqStack s;
	SElemType ch[100],*p,e;
	initStack(&s);
	printf("please input str:");
	gets(ch);
	p = ch;
	while(*p){
		switch(*p){
			case '(':
			case '[':
				push(&s,*p++);
				break;
			case ')':
			case ']':
				if(!stackEmpty(&s)){
					pop(&s,&e);
					if(e == '(' && *p == ')' || e == '[' && *p == ']'){
						//match
						p++;
						break;
					}else{ //not match
						printf("括号不匹配\n");
						exit(ERROR);
					}
				}else{ //statck empty
					printf("缺少左括号\n");
					exit(ERROR);
				}
			default:
				p++;
		}
	}
	//printSqStack(&s);
	if(stackEmpty(&s)){
		printf("匹配完成\n");
	}else{
		printf("缺少右括号\n");
	}
	
}

main(){
	bracketMatch();
}

 

以上代码应注意的是：在具体算法实现时才定义SElemType，typedef int/char SElemType;的语句必须在

#include"SeqStack.c"

前才可以。

 

testSqStack.c是对栈的adt的测试代码