第03章堆栈和队列.ppt.ppt
文本预览下载声明
第3章 堆栈和队列;3.1 堆 栈;2、堆栈抽象数据类型
数据集合:
{a0,a1,…,an-1}ai的数据类型为DataType。
操作集合：
(1) StackInitiate(S) ：初始化堆栈S
(2) StackNotEmpty(S)：堆栈S非空否
(3) StackPush(S, x) ：入栈
(4) StackPop(S, d)：出栈
(5) StackTop(S, d)：取栈顶数据元素;3、顺序堆栈;a0;顺序堆栈的操作实现： （1）初始化StackInitiate(S)
void StackInitiate(SeqStack *S)
{
S-top = 0;
}
（2）非空否StackNotEmpty(S)
int StackNotEmpty(SeqStack S)
{
if(S.top = 0)return 0;
else return 1;
}
;（3）入栈StackPush(S, x)
int StackPush(SeqStack *S, DataType x)
{ if(S-top = MaxStackSize)
{
printf(堆栈已满无法插入! \n);
return 0;
}
else
{ S-stack[S-top] = x;
S-top ++;
return 1;
}
};（4）出栈StackPop(S, d)
int StackPop(SeqStack *S, DataType *d)
{ if(S-top = 0)
{ printf(堆栈已空无数据元素出栈! \n);
return 0;
}
else
{ S-top --;*d = S-stack[S-top];
return 1;
}
};（5）取栈顶数据元素StackTop(SeqStack S, DataType *d)
int StackTop(SeqStack S, DataType *d)
{ if(S.top = 0)
{ printf(堆栈已空! \n);
return 0;
}
else
{ *d = S.stack[S.top - 1];
return 1;
}
}; 测试主程序：
任务：建立一个顺序堆栈，首先依次输入数据元素1, 2, 3,......,10，然后依次出栈堆栈中的数据元素并显示。
假设该顺序堆栈的数据元素个数在最坏情况下不会超过100个。
#include stdio.h
#include stdlib.h
#define MaxStackSize 100
typedef int DataType;
#include SeqStack.h
?;void main(void)
{ SeqStack myStack;
int i , x;
StackInitiate(myStack);
for(i = 0; i 10; i++)
StackPush(myStack, i+1)
StackTop(myStack, x)
printf(当前栈顶数据元素为：%d\n, x);
printf(依次出栈的数据元素序列如下：\n);
while(StackNotEmpty(myStack))
{ StackPop(myStack, x);
printf(%d , x);
}
};程序运行
显示全部