西安石油大学数据结构教案第03章.ppt
文本预览下载声明
第3章 堆栈和队列
主要知识点
堆栈
堆栈应用
队列
队列应用
优先级队列
3.1 堆 栈
1、堆栈的基本概念
(1)定义:限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。
(2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。
作用：可以完成从输入数据序列到某些输出数据序列的转换
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、顺序堆栈
顺序堆栈：顺序存储结构的堆栈。
顺序栈的存储结构：
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素.
typedef struct
{ DataType stack[MaxStackSize];
int top;
} SeqStack;
顺序堆栈的操作实现： （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
显示全部