文档介绍：数据结构 Data Structure
2007年9月
1
学时数：48（32+16）
学 分： 2
教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月 （配题集）
参考书：
[1] 殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月。￥26
[2] 殷人昆等，数据结构****题解析，清华大学出版社，2002年4月。￥26
[3] 李春保，数据结构****题与解析（C语言篇），清华大学出版社，2001年1月。￥28
[4] 丁宝康等，数据结构自学考试指导，清华大学出版社， 2001年5月。￥23
2
内 容 安 排
实验：课内上机（16规定内容）+课外上机（24平时作业中编程题验证）
3
数据结构课程的内容
逻辑结构唯一
存储结构不唯一
运算的实现依赖于存储结构
4
栈（Stack） 队列（Queue）
第三章 栈和队列
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
1. 定义
2. 逻辑结构
3. 存储结构
4. 运算规则
5. 实现方式
5
1. 定义
栈
与线性表相同，仍为一对一( 1:1)关系。
用顺序栈或链栈存储均可，但以顺序栈更常见
只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。
关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。
3. 存储结构
4. 运算规则
5. 实现方式
2. 逻辑结构
限定只能在表的一端进行插入和删除运算的线性表。
即栈顶
基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。
6
栈 是仅在表尾进行插入、删除操作的线性表。
表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base
例如： 栈 S= (a1 , a2 , a3 , ……….,an-1 , an )
插入元素到栈顶的操作，称为入栈。
从栈顶删除最后一个元素的操作，称为出栈。
an称为栈顶元素
a1称为栈底元素
想一想：要从栈中取出a1，应当如何操作？
强调：插入和删除都只能在表的一端（栈顶）进行！
7
Q1：堆栈是什么？它与一般线性表有什么不同？
堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。
与一般线性表的区别：仅在于运算规则不同。
一般线性表 堆栈
逻辑结构：1:1 逻辑结构： 1:1
存储结构：顺序表、链表 存储结构：顺序栈、链栈
运算规则：随机存取 运算规则：后进先出(LIFO)
“进”＝插入=压入=PUSH（an+1)
“出”＝删除=弹出=POP(an)
8
a1
a2
……
an
顺序栈S
ai
……
Q2：顺序表和顺序栈的操作有何区别？
表头
表尾
低地址
高地址
写入：S[i]= ai
读出： e= S[i]
压入(PUSH): S[top++]=an+1
弹出( POP) : e=S[--top]
低地址
高地址
S[i]
a1
a2
ai
an
……
顺序表S
……
an+1
以线性表 S= (a1 , a2 , …. , an-1 , an )为例
栈底base
栈顶top
前提：一定要预设栈顶指针top
9
栈不存在的条件： base=NULL;
栈为空 的条件 ： base=top;
栈满的条件 ： top-base=stacksize;
a1
a2
……
an
顺序栈S
ai
……
低地址
高地址
an+1
栈底base
栈顶top
10