第5章(陈佩佩数据结构课件)

- Y N YN
3 C3 乘客有优待证 Y N N - -
收费：票价的100%
X
收费：票价的90%
X
收费：票价的80% X
X
收费：票价的70%
X
13
树的应用：决策树
14
等级 不及格 及格 中等 良好 优秀
树的应用：判定树 分数段 0~59 60~69 70~79 80~89 90~100
比例 5％ 15％ 40％ 30％ 10％
✓ 遍历操作 TRAVERSE(T) ✓ 按某个次序依次访问树中各个结点，并使每个结点只被 访问一次；
✓ 清除操作 CLEAR(T) ✓ 将树T置为空树
12
树的应用
决策：根据一些给定的条件来确定应采取的行动。
R1 R2 R3 R4 R5
1 C1 乘客年龄16—60 Y Y Y N N
2 C2 购买往返票
✓ 叶子 ✓ 度为0的结点，也叫终端结点
✓ 分支结点 ✓ 度不为0的结点，也叫非终端结点
✓ 内部结点 ✓ 除根结点之外，分支结点也称为内部结点
6
树的基本术语
✓ 树的度:一棵树中最大的结点度数 ✓ 孩子:结点子树的根称为该结点的孩子 ✓ 双亲:孩子结点的上层结点叫该结点的双亲 ✓ 兄弟:同一双亲的孩子之间互成为兄弟 ✓ 祖先:结点的祖先是从根到该结点所经分支上的
集T1,T2,……Tm ✓ 其中每一个集合本身又是一棵树，称为根的子树
✓ 特点 ✓非空树中至少有一个根结点 ✓树中各子树是互不相交的集合
2
树的表示法
只有根结点的树
A
有子树的树
根 A
B
C
D
子树
E
F GH I J
KL

M
1 1 2 3 3 4
1 5 3 1 2 4
3 7 -1 -1 -2 2
N
1 1 2 3 4 5
1 3 3 2 4 1
3 -1 -2 -1 2 7
行列下 标调换
1 5 3 1 2 4
1 1 2 3 3 4
3 7 -1 -1 -2 2
按行下 标排序
法1：
按照矩阵M的列序进行转置，即按三元组A的 第二个字段值（列下标）由小到大的顺序进行转置。 为了找到M中每一列中所有的非零元素，需要对其 三元组表a.data从第一行起整个扫描一遍，由于 a.data是以M的行序为主序来存放每个非零元素 的，对于M中具有相同列下标的非零元来讲，先扫 描到的非零元的行下标一定小于后扫描到的非零元 的行下标，由此得到的恰是b.data应有的顺序。
• 压缩的含义
– 为多个值相同的元素只分配一个存贮空间； – 零元素不分配或少分配存贮空间。
• 特殊矩阵：元素值相同或零元素分布有 一定规律的矩阵。 • 稀疏矩阵：元素值相同或零元素分布没 有规律的矩阵。 • 特殊矩阵的压缩存贮实际是将二维数组 的数据元素压缩到一维数组上。
特殊矩阵的压缩存储
特殊矩阵: 非零元在矩阵中的分布有一定规则
常用的稀疏矩阵的存储方法
三元组表示法 顺序存储 行逻辑联接的顺序表 带辅助行向量的二元组表示法 伪地址表示法 带行指针向量的单链表示法 链接存储 散列存储 行列表示法（十字链表） 多链表示法（正交表）
顺序存储
1、三元组表示法 用一个线性表来表示稀疏矩阵，线性表的每个 结点对应稀疏矩阵的一个非零元素。其中包括三个 域，分别为该元素的行下标、列下标和值。结点间 的先后顺序按矩阵的行优先顺序排列（跳过零元 素），将线性表用顺序的方法存储在连续的存储区 里。

本文由ＦＵＫＡ２０１０贡献 ｐｄｆ文档可能在ＷＡＰ端浏览体验不佳。

建议您优先选择ＴＸＴ，或下载源文件到本机查看。

内容简介 《数据结构》（Ｃ　语言版）的第　１　章综述数据、数据结构和抽象数据类型等基本概念；第　２　章　至第　７　章从抽象数据类型的角度，分别讨论线性表、栈、队列、串、数组、广义表、树和二叉　树以及图等基本类型的数据结构及其应用；第　８　章综合介绍操作系统和编译程序中涉及的动态　存储管理的基本技术；第　９　章至第　１１　章讨论查找和排序，除了介绍各种实现方法之外，并着重　从时间上进行定性或定量的分析和比较；第　１２　章介绍常用的文件结构。

　《数据结构》　（Ｃ　语言版）的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其　应用；后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。

其内容和章节编排　１９９２　年　４　月出版的《数据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概　念。

全书采用类　Ｃ　语言作为数据结构和算法的描述语言。

市场价：　￥　３０．００　卓越价：　￥　２２．５０　此商品可以享受免费送货 编辑推荐 《数据结构》（Ｃ　语言版）是为“数据结构”课程编写的教材，也可作为学习数据结构及其算法的　Ｃ　程序设计的参数教材。

　本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用；　后半部分主要讨　论查找和排序的各种实现方法及其综合分析比较。

其内容和章节编排　１９９２　年　４　月出版的《数　据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概念。

全书采用类　Ｃ　语言　作为数据结构和算法的描述语言。

　本书概念表述严谨，逻辑推理严密，语言精炼，用词达意，并有配套出版的《数据结构题集》　（Ｃ　语言版），便于教学，又便于自学。

　本书后附有光盘。

光盘内容可在　ＤＯＳ　环境下运行的以类　Ｃ　语言描述的“数据结构算法动态模拟　辅助教学软件，以及在　Ｗｉｎｄｏｗｓ　环境下运行的以类　ＰＡＳＣＡＬ　或类　Ｃ　两种语言描述的“数据结　构算法动态模拟辅助教学软件”。

可进行的操作的总称
例 C语言中，提供int, char, float, double等基本 数据类型，数组、结构体、共用体、枚举 等构造数据类型，还有指针、空(void)类 型等。用户也可用typedef 自己定义数据类型 typedef struct { int num; char name[20]; float score; }STUDENT; STUDENT stu1,stu2, *p;
存储内容 元素1 元素4 …….. 元素2 ……..
指针 1400 ∧ ……. 1536 …….
1536
元素3
1346
数据结构的三个方面：
线性结构
数据的逻辑结构 非线性结构 数据的存储结构
线性表 栈 队 树形结构
图形结构
顺序存储
链式存储
数据的运算：检索、排序、插入、删除、修改等
数据类型—高级语言中指数据的取值范围及其上
数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算
机存储器中的实现
存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据 元素间的逻辑关系 数据的逻辑结构与存储结构密切相关

树
……..
……..
…...
…...
…...
…...
多叉路口交通灯管理问题
图
C AB
AC
AD
B
D
BA
BC
BD
E
DA EA EB DB EC DC ED
A
数据结构定义: 是一门研究非数值计算的程序设
计问题中计算机的操作对象以及它们之间的关系 和操作等等的学科