3第3章栈和队列教程.ppt
文本预览下载声明
; 通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。;3.1.1 栈的定义及基本运算;;例：对于一个栈，给出输入项A、B、C，如果输入顺序是A、B、C，则所有可能的输出序列。;抽象数据类型栈的定义：
ADT Stack {
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系：R1＝{ ai-1, ai | ∈D, i=2,...,n }
约定an 端为栈顶，a1 端为栈底。
基本操作：
InitStack(S)
操作结果：构造一个空栈S。
DestroyStack(S)
初始条件：栈S已存在。
操作结果：栈S被销毁。;ClearStack(S)
初始条件：栈S已存在。
操作结果：将S清为空栈。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALE。
StackLength(S)
初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
GetTop(S, e)
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素;Push(S, e)
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。;Pop(S, e)
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
StackTraverse(S,visit( ) )
初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个元素调用函数
visit( )，一旦visit（）失败，则操作失败。
} ADT Stack
;3.1.1 栈的表示和实现
顺序栈：类似于线性表的顺序映象实现，用一片地址连续的存储空间来存储栈的元素，指向表尾的指针可以作为栈顶指针。; 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s.base[0]是栈底元素，那么栈顶指针s.top是正向增加的，即进栈时需将s.top加1，退栈时需将s.top 减1。因此，s.top=s.base表示空栈， s.top-s.base =stacksize表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。;//----- 栈的顺序存储表示 -----
#define STACK_INIT_SIZE 100; // 存储空间初始分配量
#define STACKINCREMENT 10; // 存储空间分配增量
typedef struct {
SElemType *base; // base的初值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
} SqStack;; Status InitStack (SqStack S){
// 构造一个空栈S
}// STACK_INIT_SIZE ;Status StackEmpty (SqStack S){
// 将栈S为空栈，则返回TRUE，否则返回FALSE
}// StackEmpty;Status Push (SqStack S, SElemType e);
// 插入元素e为新的栈顶元素
}//push;Status GetTop (SqStack S, SElemType e) {
// 若栈不空，则用e返回S的栈顶元素，并返回OK；
// 否则返回ERROR
}// GetTop;0;链栈
利用链表实现栈，注意链表中指针的方向是从栈顶到栈底。;;void conversion ( ) {
// 对于输入的任意一个非负10进制整数，打印输出
// 与其等值的8进制数
InitStack(S); // 构造空栈
scanf (%d,N);
while (N) { // 进栈
Push(S, N % 8);
N = N/8;
}
while (!StackEmpty(S)) {// 出栈
Pop(S,e);
printf ( %d, e );
}
} // conversion
;int conversion( int N , int d ) {
//将十进制数转换成d进制数
if(N==0) return 0;
else return)(d* conversion(N/10,d)+N%10);
}
int conversion( int N , int d ) {
//将d进制数转换成十进制
显示全部