中央广播电视大学 数据结构（本） 课程学习辅导和例题选讲 北京交通大学 计算机与信息技术学院 李伟生教授 2008.6.20
北京交通大学 计算机与信息技术学院 李伟生教授 2008.6.20 中央广播电视大学 数据结构（本） 课程学习辅导和例题选讲
第1章 绪论 [重点掌握的知识点举例] 1.数据结构：（数据元素间的关系称为结构）， 相互间存在一种或多种特定关系的数据元 素的集合称为数据结构 ·逻辑结构 ● 物理结构
[重点掌握的知识点举例] 1.数据结构：(数据元素间的关系称为结构)， 相互间存在一种或多种特定关系的数据元 素的集合称为数据结构 ⚫ 逻辑结构 ⚫ 物理结构 第1章 绪论
第1章 绪论 [重点掌握的知识点举例] ·逻辑结构：元素间的逻辑关系，与计算机无 关 ·物理结构：把数据存储到计算机中，并具体 体现数据之间的关系。简言之，是逻辑结构 在计算机中的表示（包括数据元素和关系的 表示)，同一种逻辑结构可以对应不同的物 理结构
[重点掌握的知识点举例] ⚫ 逻辑结构：元素间的逻辑关系，与计算机无 关 ⚫ 物理结构：把数据存储到计算机中，并具体 体现数据之间的关系。简言之，是逻辑结构 在计算机中的表示(包括数据元素和关系的 表示)，同一种逻辑结构可以对应不同的物 理结构 第1章 绪论
第1章 绪论 [重点掌握的知识点举例] 2.基本的数据结构 ·集合：属于同一集合 ● 线形： 一对一，数据元素之间存查亡对 的关系，线性表除第不 素和最后个 元素外每个完素宥一个直接前驱和直接后 ·树形：一对多 图：多对多
[重点掌握的知识点举例] 2.基本的数据结构 ⚫ 集合：属于同一集合 ⚫ 线形：一对一，数据元素之间存在一对一 的关系，线性表除第一个元素和最后一个 元素外每个元素有一个直接前驱和直接后 继 ⚫ 树形：一对多 ⚫ 图：多对多 第1章 绪论
第1章 绪论 [重点掌握的知识点举例] 3.算法：解决特定问题的方法 ·算法的5个特征：有穷、确定、可行、零个 或多个输入、一个或多个输出 ●时间复杂度 基本操作、频度、问题规模、数量级、时 间复杂度与实现算法的软、硬件无关
[重点掌握的知识点举例] 3.算法：解决特定问题的方法 ⚫ 算法的5个特征：有穷、确定、可行、零个 或多个输入、一个或多个输出 ⚫ 时间复杂度 基本操作、频度、问题规模、数量级、时 间复杂度与实现算法的软、硬件无关 第1章 绪论
第1章 绪论 [重点掌握的知识点举例] 3.算法：解决特定问题的方法 ●时间复杂度 n个矩阵的乘积算法的基本操作为乘法， 时间复杂度为0(n) 要在n个数据元素中找最大元素，基本操 作为比较，比较次数为n-1,时间复杂度为 0(n
[重点掌握的知识点举例] 3.算法：解决特定问题的方法 ⚫ 时间复杂度 n个矩阵的乘积算法的基本操作为乘法， 时间复杂度为O(n3) 要在n个数据元素中找最大元素，基本操 作为比较，比较次数为n-1，时间复杂度为 O(n) 第1章 绪论
第2章 线性表 [重点掌握的知识点举例] 1.线性表的定义：属于同一个数据对象的 数据元素的有限序列
[重点掌握的知识点举例] 1.线性表的定义：属于同一个数据对象的 数据元素的有限序列 第2章 线性表
第2章 线性表 [重点掌握的知识点举例] 2.顺序存储（顺序表） 逻辑结构与存储结构一致，可用数组或指 针实现，能随机访问，如果线性表存储后最 常用的操作是取第i个结点及其前驱，采用 顺序表较方便，但顺序表插入删除操作平均 而言移动元素次数较多，效率很低。插入位 置i,移动元素次数为n-i+1.删除位置是i, 移动次数n-i
[重点掌握的知识点举例] 2.顺序存储(顺序表) 逻辑结构与存储结构一致，可用数组或指 针实现，能随机访问，如果线性表存储后最 常用的操作是取第i个结点及其前驱，采用 顺序表较方便，但顺序表插入删除操作平均 而言移动元素次数较多，效率很低. 插入位 置i，移动元素次数为n-i+1.删除位置是i， 移动次数n-i 第2章 线性表
第2章 线性表 [重点掌握的知识点举例] 3.链式存储（链表）： 以结构变量存储结点，动态生成结点，以 指针链接结点，能有效利用存储空间，插入 删除方便，但不能随机访问.单向链表可从 某结点访问到后继结点
[重点掌握的知识点举例] 3.链式存储(链表)： 以结构变量存储结点，动态生成结点，以 指针链接结点，能有效利用存储空间，插入 删除方便，但不能随机访问.单向链表可从 某结点访问到后继结点 第2章 线性表
第2章 线性表 [重点掌握的知识点举例] 4.单向链表操作的关键步骤： ·建立链表的头插法：指针变量p开辟单元， 生成结点，指针变量q始终指向头结点，操 作为： p->next=q->next; q->next=p;
[重点掌握的知识点举例] 4.单向链表操作的关键步骤： ⚫ 建立链表的头插法：指针变量p开辟单元， 生成结点，指针变量q始终指向头结点，操 作为： p->next=q->next; q->next=p; 第2章 线性表