双向链表的存储结构
提问：单向链表的缺点是什么？ 提示：如何寻找结点的直接前趋。 双向链表可以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域， 在双向链表的结点中有两个指针域，其一指向 直接后继，另一指向直接前趋。 直接后继，另一指向直接前趋。 3 HEAD 1 5 10 a1 a2 a3 a4
双向循环链表 第27页
线性表 : {a1，a2，a3，a4，a5 } ， ， ， ，
注意： 注意： 数据元素在计算机 存储空间中的位置关 系与它们的逻辑关系 不一定是相同的。 不一定是相同的。 一个逻辑数据结构 可以有多种存储结构， 可以有多种存储结构， 且不同的存储结构影 响数据处理的效率 。 线性表的存储结构有两种 顺序存储结构
1 a1 2 a2 3 a3 4 a4 5 a5 6 7 HEAD 3 链式存储结构
1 2 3 4 5 6 7 8 9 10 a3 a5 5 0 a4 10 a1 1 a2 9 第28页 2. 栈和队列
栈和队列都是特殊的线性表。 栈和队列都是特殊的线性表。 栈（Stack）及其基本运算 Stack） 队列（Queue）及其基本运算 队列（Queue） 循环队列及其基本运算 第29页
栈（Stack）是一种特殊的线性表。其特点是插入和删 Stack）是一种特殊的线性表 线性表。 除运算都只能在线性表的一端进行。 除运算都只能在线性表的一端进行。 栈是按照“先进后出” 后进先出” 栈是按照“先进后出”或“后进先出”的原则组织数 据的线性表。 据的线性表。 栈的物理存储结构可以用顺序结构， 栈的物理存储结构可以用顺序结构，也
11
可以用链表结 构。 下面讨论顺序存储结构中栈元素的插入和删除运算。 下面讨论顺序存储结构中栈元素的插入和删除运算。 顺序栈的进栈和出栈运算
栈的基本运算有三种：入栈、 栈的基本运算有三种：入栈、退栈和读栈顶元素 在顺序栈中插入和删除运算不需要 移动表中其他数据元素。 移动表中其他数据元素。 第30页
队列（Queue）是一种特殊的线性表。其特点是所有的 队列（Queue）是一种特殊的线性表。 插入都在表的一端进行 所有的删除运算都在表的另 进行， 删除运算都在表的 插入都在表的一端进行，所有的删除运算都在表的另 一端进行 进行。 一端进行。 队列是按照“先进先出” 后进后出” 队列是按照“先进先出”或“后进后出”的原则组织 数据的线性表。 数据的线性表。 队列的物理存储结构可以用顺序结构，也可以用链式 队列的物理存储结构可以用顺序结构， 结构。 结构。 顺序队列的运算
栈有三种操作： 入栈＼出栈＼ 栈有三种操作： 入栈＼出栈＼读栈顶元素 队列有三种操作：入队＼出队＼ 队列有三种操作：入队＼出队＼读队首元素 例：有入栈元素序列：ABCD，求可能的出栈序列． 有入栈元素序列： ，求可能的出栈序列． 如是队列又是什么情况呢？ 如是队列又是什么情况呢？ 第31页
循环队列 把队列的存储空间在逻辑上看作一个环， 把队列的存储空间在逻辑上看作一个环，当R指向存 指向存 储空间的末端后，就把它重新置于始端。 储空间的末端后，就把它重新置于始端。 循环队列的运算
队列中进行插入的一端称做队尾(rear),进行删除的一端 进行删除的一端 队列中进行插入的一端称做队尾 称做队首(front)。 称做队首 。
习题：数据结构分为逻辑结构和存储结构， 习题：数据结构分为逻辑结构和存储结构，循环队 列属于【 结构。（ 。（2005年9月） 列属于【 】结构。（ 年 月 答案：存储结构。 答案：存储结构。 第32页
常见数据结构的逻辑结构 线性表 栈 队列
也是一种操作受限的特殊的线性表 线性结构 是特殊的线性表 树型结构） 树 （树型结构） 是一种重要的非线形数据结构
12
第33页
数据存储结构方面的考题
1：数据的存储结构是指 （2005年4月） ： 年 月 A) 存储在外存中的数据 C) 数据在计算机中的顺序存储方式 2. 下列叙述中正确的是 （2009年3月） 年 月 A）栈是“先进先出”的线性表 ）栈是“先进先出” B）队列是“先进后出”的线性表 ）队列是“先进后出” C）循环队列是非线性结构 ） D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 ）有序线性表既可以采用顺序存储结构， B) 数据所占的存储空间量 D) 数据的逻辑结构在计算机中的表示 答案：D。 答案： 。 答案：D。 答案： 。
3. 数据结构分为线性结构和非线性结构，带链的队列属于 数据结构分为线性结构和非线性结构，带链的队列属于[ 4. 下列数据结构中，属于非线性结构的是 下列数据结构中， A）循环队列 ） C) 二叉树 B) 带链队列 D）带链栈 ）
]。 。 答案：线性结构。 答案：线性结构。 答案： 答案：c 第34页
5。下列叙述中正确的是（ ）。 （2008年9月） 。下列叙述中正确的是（ 年 月 答案： 。 答案：A。
A）顺序存储结构的存储一定是连续的，链式存储结构的存储空 ）顺序存储结构的存储一定是连续的， 间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性 ）顺序存储结构只针对线性结构， 结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 ）顺序存储结构能存储有序表， D）链式存储结构比顺序存储结构节省存储空间 ）
答案： 。 6。下列关于栈的叙述正确的是 （2008年4月） 年 月 栈按“先进先出” B)栈按 先进后出” 栈按“ A）栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C）只能在栈底插入数据 D）不能删除数据 答案：B。 答案： 。
7. 一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3， 一个队列的初始状态为空。现将元素 ， ， ， ， ， ， ， ， ， 2，1依次入队，然后再依次退队，则元素退队的顺序为 【1】 。（2010 ， 依次入队，然后再依次退队， 】 。（ 依次入队 年3月） 月 答案： ， ， ， ， ， ， ， ， ， ， 答案：A，B，C，D，E，F，5，4，3，2，1 第35页
8。假设用一个长度为50的数组（数组元索的下标从 。假设用一个长度为 的数组 数
13
组元索的下标从0 的数组（ 到49）作为栈的存储空间，栈底指针 ）作为栈的存储空间，栈底指针bottom指间栈底 指间栈底 元素，栈顶指针top指向栈顶元素，如果bottom=49， 元素，栈顶指针 指向栈顶元素，如果 ， 指向栈顶元素 top=30（数组下标），则栈中具有【 】个元素。 ），则栈中具有 个元素。 （数组下标），则栈中具有【 （2009年3月） 年 月 答案： 答案：19
9. 设某循环队列的容量为 ，如果头指针 设某循环队列的容量为50，如果头指针front=45(指向 指向 队头元素的前一位置)，尾指针rear=10(指向队尾元素 ， 指向队尾元素)， 队头元素的前一位置 ，尾指针 指向队尾元素 则该循环队列中共有 【2】 个元素。 （2010年3月） 】 个元素。 年 月 答案： 答案：15 第36页 线性结构与非线性结构
线性表、 线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为非线性结 一个数据结构不是线性结构，则称其为非线性结 构。
一个非空的数据结构若满足下面的两个条件， 一个非空的数据结构若满足下面的两个条件，则这种数据结 构即为线性结构 线性结构。 构即为线性结构。 有且仅有一个根结点； ① 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个直接前驱结点； ② 除第一个结点外，每一个结点最多有一个直接前驱结点； 除最后一个结点外，每一个结点最多有一个直接后继结点。 ③ 除最后一个结点外，每一个结点最多有一个直接后继结点。 3 HEAD 1 9 5 10 a1 a2 a3 a4 a5 第37页
线性链表的逻辑状态 3. 树与二叉树
树型结构是一种重要的非线性结构。 树型结构是一种重要的非线性结构。 树的概念 二叉树的概念 二叉树的存储 二叉树的遍历
14
第38页 树的概念
树的定义： 个结点的有限集。（n>=0） 个结点的有限集。（ 树的定义：n个结点的有限集。（ ） 根：only one 若n=0，则称为空树； ，则称为空树； 否则， 否则，当n>1时，其余结 时 点被分成m（ 点被分成 （m>0）个互不 ） 相交的子集T1， ， ， 相交的子集 ，T2，……， Tm，每个子集又是一棵树。 ，每个子集又是一棵树。 由此可以看出， 由此可以看出，树的定义是 递归的。 递归的。 Question：如何辨别根？ ：如何辨别根？ 第39页 E B F J A C G K D H M I 只有一个 结点的树 A
树型结构的常用术语
结点的度 一个结点的子树的 个数； ：结点A、 的度数 的度数？ 个数； Q：结点 、G的度数？ 树的度 树中所有结点度的最 大值； ：右图中树的度？ 大值；Q：右图中树的度？ 终端结点 度为 的结点； 度为0的结点 的结点； Q：图中叶子结点有几个？7 ：图中叶子结点有几个？ 非终端结点 度不为 的结点； 度不为0的结点 的结点； Q：图中非终端结点有几个？ 5 ：图中非终端结点有几个？
孩子结点、双亲结点、兄弟结点、结点的子孙、 孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先
第40页 B E F J A C G K D H M I 树型结构的常用术语
结点的层次 树中根结点的层 ① 次为1，根结点子树的根为第2层 次为 ，根结点子树的根为第 层， ② 以此类推； 以此类推； Q：图中结点F的层次？ ：图中结点 的层次 的层次？ ③
E A B F J C G K D H M I
树的深度 树中所有结点层次 的最大值； ：图中树的深度？ 的最大值； Q：图中树的深度？ 有序树、无序树 如果树中每 有序树、 棵子树从左向右的排列拥有一定 的顺序，不得互换， 的顺序，不得互换，则称为有序 否则称为无序树。 树，否则称为无序树。 ④ 第41页
15