文档介绍：合肥工业大学人工智能与数据挖掘研究室数据结构与算法(第三部分数据结构) 胡学钢计算机与信息学院 2009 年10月合肥工业大学合肥工业大学人工智能与数据挖掘研究室人工智能与数据挖掘研究室?使用指针表示动态集合?栈、队列、链表、有根树等合肥工业大学合肥工业大学人工智能与数据挖掘研究室人工智能与数据挖掘研究室第三部分数据结构第十章基本数据结构栈和队列(简要回顾) 合肥工业大学合肥工业大学人工智能与数据挖掘研究室人工智能与数据挖掘研究室 栈和队列栈的定义?栈是只能在一端插入和删除元素的线性表。术语:栈顶, 栈底, 入栈(压栈) , 出栈(弹栈) a n a n-1…… a 1 入栈(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; //注意:两条语句顺序不能颠倒 a a 1 1a a n n∧∧ a a 3 3a a 2 2 head head ……头指针首元素结点尾结点 a 1 1a 2 2a 3 3a n n ^ …… X head P s②①合肥工业大学合肥工业大学人工智能与数据挖掘研究室人工智能与数据挖掘研究室 链表?引入“头结点”?可以降低一些操作的常数因子?在循环结构中,使得代码更加简洁?在短链表中,会造成存储的浪费