songzi 2008-5-2 23:37
栈的学习与应用(数据结构)
[color=Red][size=7]栈的介绍：[/size][/color]
一、栈的定义
[indent][color=#ff0033]栈[/color]是限定仅在[b]表尾[/b]进行插入或删除操作的线性表。
栈的表尾称为[color=#ff0033]栈顶[/color]，表头称为[color=#ff0000]栈底[/color]，不含元素的空表称为[color=#ff0033]空栈[/color]。
栈的抽象数据类型定义：
ADT Stack{
[indent]数据对象:D={[size=+3]a[/size]i|[size=+3]a[/size]i[size=-1](-[/size] ElemSet,i=1,2,...,n,n>=0}
数据关系:R1={<[size=+3]a[/size]i-1,[size=+3]a[/size]i>|[size=+3]a[/size]i-1,[size=+3]a[/size]i[size=-1](-[/size] D,i=2,...,n}
基本操作:
[indent]InitStack(&S) 构造一个空栈S
DestroyStack(&S) 栈S存在则栈S被销毁
ClearStack(&S) 栈S存在则清为空栈
StackEmpty(S) 栈S存在则返回TRUE,否则FALSE
StackLength(S) 栈S存在则返回S的元素个数,即栈的长度
GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素
Push(&S,e) 栈S存在则插入元素e为新的栈顶元素
Pop(&S,&e) 栈S存在且非空则删除S的栈顶元素并用e返回其值
StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败
[/indent][/indent]}ADT Stack
[/indent]二、栈的表示和实现
[indent]栈的存储方式：
1、顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置
2、链栈:利用链表实现
顺序栈的类C语言定义:
typedef struct{
[indent]SElemType *base;
SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空
int StackSize; //栈的当前可使用的最大容量.
[/indent]}SqStack;
顺序栈的的模块说明:
struct STACK {
[indent]SElemType *base;
SElemType *top;
int stacksize;
};
[/indent]typedef struct STACK Sqstack;
Status InitStack(SqStack &S);
Status DestroyStack(SqStack &S);
Status ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType &e);
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackTraverse(SqStack S,Status (*visit)());
Status InitStack(SqStack &S) {
S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INI_SIZE;
return OK;
}//IniStack
Status DestroyStack(SqStack &S); {
}//DestroyStack
Status ClearStack(SqStack &S); {
S.top=S.base;
} //ClearStack
Status StackEmpty(SqStack S); {
if(S.top==S.base) return TRUE;
else return FALSE;
} //StackEmpty
int StackLength(SqStack S); {
int i; SElemType *p;
i=0;
p=S.top;
while(p!=S.base) {p++; i++; }
} //stackLength
Status GetTop(SqStack S,SElemType &e); {
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
} //GetTop
Status Push(SqStack &S,SElemType e); {
if(S.top - s.base>=S.stacksize) {
S.base=(ElemType *) realloc(S.base,
[indent](S.stacksize + STACKINCREMENT) * sizeof(ElemType));
[/indent]if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
} //Push
Status Pop(SqStack &S,SElemType &e); {
if(S.top==S.base)
[indent]return ERROR;
[/indent]e=*--S.top;
return OK;
}//Pop
Status StackTraverse(SqStack S,Status (*visit)()); {
}//StackTraverse
[url=http://219.219.90.4:8080/datastru/class10/stack.txt]以上伪代码的C语言源码[/url][/indent]三、总结
[indent]栈的定义
栈的顺序存储实现
[size=6][color=Red]栈的应用：[/color][/size]
[size=6]
[/size]
一、栈应用之一：数制转换
[indent]将十进制数转换成其它进制的数有一种简单的方法：
例：十进制转换成八进制：(66)[size=-3]10[/size]=(102)[size=-3]8[/size]
66/8=8 余 2
8/8=1 余 0
1/8=0 余 1
结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：
[table=98%][tr=#0066ff][td][color=#ffff33][b]void conversion() { [/b][/color]
[b][color=#ffff33]pSqStack S; [/color][/b]
[b][color=#ffff33]SElemType e; [/color][/b]
[b][color=#ffff33]int n; [/color][/b]
[b][color=#ffff33]InitStack(&S); [/color][/b]
[b][color=#ffff33]printf("Input a number to convert to OCT:\n");[/color][/b]
[b][color=#ffff33]scanf("%d",&n); [/color][/b]
[b][color=#ffff33]if(n<0) [/color][/b]
[indent][b][color=#ffff33]{ printf("\nThe number must be over 0."); [/color][/b]
[b][color=#ffff33]return;}[/color][/b]
[/indent][b][color=#ffff33]if(!n) Push(S,0); [/color][/b]
[b][color=#ffff33]while(n){ [/color][/b]
[indent][b][color=#ffff33]Push(S,n%8); [/color][/b]
[b][color=#ffff33]n=n/8; } [/color][/b]
[/indent][b][color=#ffff33]printf("the result is: "); [/color][/b]
[b][color=#ffff33]while(!StackEmpty(*S)){ [/color][/b]
[indent][b][color=#ffff33]Pop(S,&e); printf("%d",e);}[/color][/b]
[/indent][b][color=#ffff33]}[/color][/b]
[/td][/tr][/table]请看：[url=http://219.219.90.4:8080/datastru/class11/convert.txt]数制转换的C源程序[/url]
[/indent]二、栈应用之二：行编辑
[indent]一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。
例：在终端上用户输入为
whli##ilr#e(s#*s) 应为
while(*s)
[table=89%][tr=#0066ff][td][color=#ffff33][b]void LineEdit() {[/b][/color]
[b][color=#ffff33]pSqStack S,T; char str[1000]; [/color][/b]
[b][color=#ffff33]int strlen=0; char e; char ch; [/color][/b]
[b][color=#ffff33]InitStack(&S); [/color][/b]
[b][color=#ffff33]InitStack(&T); [/color][/b]
[b][color=#ffff33]ch=getchar();[/color][/b]
[b][color=#ffff33]while(ch!=EOFILE) {[/color][/b]
[indent][b][color=#ffff33]while(ch!=EOFILE&&ch!='\n') {[/color][/b]
[indent][b][color=#ffff33]switch(ch){ [/color][/b]
[indent][b][color=#ffff33]case '#': Pop(S,&ch); break; [/color][/b]
[b][color=#ffff33]case '@': ClearStack(S); break; [/color][/b]
[b][color=#ffff33]default: Push(S,ch); break; } [/color][/b]
[/indent][b][color=#ffff33]ch=getchar(); [/color][/b]
[/indent][b][color=#ffff33]} [/color][/b]
[b][color=#ffff33]if(ch=='\n') Push(S,ch);[/color][/b]
[b][color=#ffff33]while(!StackEmpty(*S)) { Pop(S,&e); Push(T,e); } [/color][/b]
[b][color=#ffff33]while(!StackEmpty(*T)) { Pop(T,&e); str[strlen++]=e; } [/color][/b]
[b][color=#ffff33]if(ch!=EOFILE) ch=getchar();[/color][/b]
[/indent][b][color=#ffff33]} [/color][/b]
[b][color=#ffff33]str[strlen]='\0'; [/color][/b]
[b][color=#ffff33]printf("\n%s",str); [/color][/b]
[b][color=#ffff33]DestroyStack(S); [/color][/b]
[b][color=#ffff33]DestroyStack(T); [/color][/b]
[b][color=#ffff33]}[/color][/b]
[/td][/tr][/table]
请看:[url=http://219.219.90.4:8080/datastru/class11/lineedit.txt]行编辑的C源程序[/url]
[/indent]三、栈应用之三：表达式求值
[indent]一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。
算法基本思想：
１首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；
２依次讲稿表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。
[table=97%][tr=#0066ff][td][b][color=#ffff00]char EvaluateExpression() {[/color][/b]
[color=#ffff00][b]SqStack *OPND,*OPTR; [/b][/color]
[color=#ffff00][b]char c,x,theta; char a,b; [/b][/color]
[color=#ffff00][b]InitStack(&OPTR); Push(OPTR,'#'); [/b][/color]
[color=#ffff00][b]InitStack(&OPND); [/b][/color]
[color=#ffff00][b]c=getchar(); [/b][/color]
[color=#ffff00][b]while(c!='#'||GetTop(*OPTR)!='#') {[/b][/color]
[indent][color=#ffff00][b]if(!In(c,OP)) {Push(OPND,c);c=getchar();} [/b][/color]
[color=#ffff00][b]else [/b][/color]
[indent][color=#ffff00][b]switch(Precede(GetTop(*OPTR),c)) { [/b][/color]
[indent][color=#ffff00][b]case '<': Push(OPTR,c); c=getchar(); break; [/b][/color]
[color=#ffff00][b]case '=': Pop(OPTR,&x); c=getchar(); break; [/b][/color]
[color=#ffff00][b]case '>': Pop(OPTR,&theta); [/b][/color]
[indent][indent][color=#ffff00][b]Pop(OPND,&b); Pop(OPND,&a); [/b][/color]
[color=#ffff00][b]Push(OPND,Operate(a,theta,b));[/b][/color]
[color=#ffff00][b]break; [/b][/color]
[/indent][/indent][/indent][color=#ffff00][b]} [/b][/color]
[/indent][color=#ffff00][b]} [/b][/color]
[/indent][color=#ffff00][b]c=GetTop(*OPND); [/b][/color]
[color=#ffff00][b]DestroyStack(OPTR); [/b][/color]
[color=#ffff00][b]DestroyStack(OPND); [/b][/color]
[color=#ffff00][b]return c; [/b][/color]
[color=#ffff00][b]} [/b][/color]
[/td][/tr][/table]请看:[url=http://219.219.90.4:8080/datastru/class11/expre.c]表达式求值的C源程序[/url]
[/indent]四、总结
[indent]栈的先进后出、后进先出的特性。
[/indent][/indent]