栈的操作
从今天开始，重写《数据结构C语言版：严蔚敏》一书里的程序。毕竟数据结构是一个程序员的内功。以后定期每隔一天更新一次。若对数据结构不熟悉的同学可以一看，现在先写了顺序栈的代码P.S. 所有代码在C-free 5.0上通过编译运行，程序里用到一个common.h的头文件，里面保存一些常用的宏定义
栈的特性：后进先出。。。
以下是顺序栈的结构：SeqStack.h
#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef 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,*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 == ']'){//matchp++;break;}else{ //not matchprintf("括号不匹配\n");exit(ERROR);}}else{ //statck emptyprintf("缺少左括号\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的测试代码
页:
[1]