§1.5.1集合 如果数据结构中,数据元素之间不考虑关 系问题(无前驱/后继之分),则称这种结 构为集合 在集合中,各元素是“平等”的,它们的 共同关系是:都属于同一个集合
11 §1.5.1 集合 如果数据结构中，数据元素之间不考虑关 系问题（无前驱/后继之分），则称这种结 构为集合。 在集合中，各元素是“平等”的，它们的 共同关系是：都属于同一个集合
§1.5.2线性结构 如果数据结构中,数据元素之间只存在前后顺 序关系,则称这种结构为线性结构。 +每个元素都有唯一前趋和后继,第一个元素可 以没有前驱,最后一个可以没有后继 ◆线性结构是一种最常见的数据结构。线性表、 栈、队列、串等均为线性结构。 12
12 §1.5.2 线性结构 如果数据结构中，数据元素之间只存在前后顺 序关系，则称这种结构为线性结构。 每个元素都有唯一前趋和后继，第一个元素可 以没有前驱，最后一个可以没有后继 线性结构是一种最常见的数据结构。线性表、 栈、队列、串等均为线性结构
81.5.2线性结构 上图表示的数据结构为: DS=D, S) D={d1,d2, n S={r} r={<d1,d2>,<d2,d3>,…,<dn1,dn2} 13
13 §1.5.2 线性结构 上图表示的数据结构为： DS=(D, S) D={d1 , d2 , …, dn } S={ r } r={<d1 , d2>, <d2 , d3> , …, <dn-1 , dn>} d1 d2 dn
§1.5.3树形结构 如果除一个特殊元素没有前驱外,其他每个元素都有 唯一的前驱(后继个数不限),则称该结构为树型结 构(简称树)。其中,将无前驱的元素称为树根。 它代表的结构的形式描述为 DS=(D, S) W13 D={W1,Wl1,W12,W13,Wl1lw121,W122, W131,W132,W133,Wlll1v2w1221} w)12)w12)(w)(w12)3)S={r} wII11/W1112/W1221 r={<W1,Wll>,<W1,W12>,<W1,Wl3>, <Wll,Wlll>,<W12,Wl21>,<Wl2,W122>, 图一个家族结构的树表示 <W13,W131>,<W13,W132,>,<W13,W133>, wll,w1l,<wl1w1112>,<W122W1221>}
14 §1.5.3 树形结构 如果除一个特殊元素没有前驱外，其他每个元素都有 唯一的前驱（后继个数不限），则称该结构为树型结 构（简称树）。其中，将无前驱的元素称为树根。 W1 W12 W111 W121 W122 W11 W131 W132 W133 W13 W1111 W1112 W1221 图 - 一个家族结构的树表示 它代表的结构的形式描述为： DS= ( D, S) D = {W1, W11, W12, W13, W111, W121, W122, W131, W132, W133, W1111, W1112, W1221} S = {r} r = {<W1, W11>, <W1, W12>, <W1,W13>, <W11, W111>, <W12, W121>, <W12, W122>, <W13, W131>, <W13, W132,>, <W13, W133>, <W111, W1111>, <W111, W1112>, <W122, W1221> }
81.5.3树形结构 树形结构中的数据元素(结点)可分为三种 根,每个树结构只有一个根(空树无根),根无前趋, 但可有若千个后继; 丌子,叶子无后继,但只有且必有一个前趋, >普通结点,有且必有一个前趋,后继有若干个。 树型结构的应用 常用来表达层次关系 另一个重要应用是快速检索:为了提髙数据检索速度, 可将数据按树结构组织,如二叉排序树、平衡二叉树、B树 等 15
15 §1.5.3 树形结构 • 树形结构中的数据元素（结点）可分为三种: ➢ 根，每个树结构只有一个根（空树无根），根无前趋， 但可有若干个后继； ➢ 叶子，叶子无后继，但只有且必有一个前趋， ➢ 普通结点，有且必有一个前趋，后继有若干个。 ▪ 树型结构的应用 ➢ 常用来表达层次关系 ➢ 另一个重要应用是快速检索：为了提高数据检索速度， 可将数据按树结构组织，如二叉排序树、平衡二叉树、B树 等