文档介绍：数据结构与算法
(第三部分数据结构)
胡学钢
计算机与信息学院
2009年10月
使用指针表示动态集合
栈、队列、链表、有根树等
第三部分数据结构
第十章基本数据结构
栈和队列(简要回顾)
栈和队列
栈的定义
栈是只能在一端插入和删除元素的线性表。
术语:栈顶, 栈底, 入栈(压栈), 出栈(弹栈)
an
an-1
……
a1
入栈
(PUSH)
出栈
(POP)
栈顶
(top)
栈底
(bottom)
a1 a2 … an
特性:后进先出( LIFO )
----Last in First out
…
a1
a2
an
an
…
a2
a1
栈的运算
对栈的基本运算有如下几个:
(1)初始化:设置栈为空。
(2)判断栈为空:
若为空,则返回TRUE,否则返回FALSE.
(3)判断栈为满:
若为满,则返回TRUE,否则返回FALSE.
(4)取栈顶元素:取出栈顶元素。
条件:栈不空。
否则,应能明确给出标识,以便程序的处理。
(5)入栈:将元素入栈,即放到栈顶。
如果栈满,怎样处理?
(6)出栈:删除当前栈顶的元素。
队列的定义
队列是只能在一端插入,另一端删除元素的线性表。
术语:队头, 队尾, 入队, 出队
a1 a2 … an
特性:先进先出
(FIFO:first in first out)
…
a1
a2
an
an
…
a2
a1
…
a1
a2
an
队头
队尾
出队
入队
队列的运算
对队列的基本运算有如下几个:
(1)初始化:设置队列为空。
(2)判断队列为空:
若为空,则返回TRUE,否则返回FALSE.
(3)判断队列为满:
若为满,则返回TRUE,否则返回FALSE.
(4)取队头元素:取出队头元素。
条件:队列不空。
否则,应能明确给出标识,以便程序的处理。
(5)入队:将元素入队,即放到队列的尾部。
如果队列满,怎样处理?
(6)出栈:删除当前队头的元素。
用两个栈来实现一个队列,并分析有关队列操作的运行时间。
用两个队列来实现一个栈,并分析有关栈操作的运行时间。
链表
基本存储结构:
插入操作分析:
三种位置:链表中间;链表尾;链表头
在链表中间某位置插入时,
s -> next = p -> next;
p -> next = s;
//注意:两条语句顺序不能颠倒
a1
an
∧
a3
a2
head
……
头指针
首元素结点
尾结点
a1
a2
a3
an ^
……
X
head
P
s
②
①
链表
引入“头结点”
可以降低一些操作的常数因子
在循环结构中,使得代码更加简洁
在短链表中,会造成存储的浪费