“数据结构”复习指导 2009.6
“数据结构”复习指导 2009.6
一、各章节主要知识点选讲 二、对相关算法的要求和举例 三、习题选讲
一、各章节主要知识点选讲 二、对相关算法的要求和举例 三、习题选讲
第章 绪论 1.数据结构的基本概念 。 一个数据项 数据元素：是数据的基本单位，可以是 多个数据项复合组成 数据对象：是数据的子集，是性质相同的数据元素的集合 数据结构：是相互之间存在一种或多种特定关系的数据元素 的集合，数据元素间的关系称为结构
第1章 绪论 1.数据结构的基本概念 • 数据元素：是数据的基本单位，可以是 • 数据对象：是数据的子集，是性质相同的数据元素的集合 • 数据结构:是相互之间存在一种或多种特定关系的数据元素 的集合，数据元素间的关系称为结构 一个数据项 多个数据项复合组成
第1章 绪论 逻辑结构：数据元素间的逻辑（抽象)关系，与计算 机无关，同一种逻辑结构可以有不同的存 储结构（物理结构例：链式顺序） 物理结构：数据的逻辑结构在计算机中的表示 (数据元素的表示和关系的表示) ·4种基本结构： 集合 线性（一对一） 树形（一对多） 图状（多对多）
第1章 绪论 • 逻辑结构：数据元素间的逻辑（抽象）关系，与计算 机无关，同一种逻辑结构可以有不同的存 储结构（物理结构 例：链式 顺序） • 物理结构：数据的逻辑结构在计算机中的表示 （数据元素的表示和关系的表示） • 4种基本结构： 集合 线性（一对一） 树形（一对多） 图状（多对多）
第1章 绪论 2.算法的基本概念 算法的5个特性：（有穷性、确定性、可行性、零个或 多个输入、一个或多个输出) 时间复杂度：评估算法的重要标准之一，能较好的体现算 法本身的时间效率，与计算机硬件无关 (基本操作、问题的规模、基本操作的频度是 问题规模的函数) 例：n个数中找最大的
第1章 绪论 2.算法的基本概念 • 算法的5个特性:（有穷性、确定性、可行性、零个或 多个输入、一个或多个输出） • 时间复杂度：评估算法的重要标准之一，能较好的体现算 法本身的时间效率，与计算机硬件无关 （基本操作、问题的规模、基本操作的频度是 问题规模的函数） 例: n个数中找最大的
第2章 线性表 1.线性表的逻辑结构 ·前驱、后继 ·一对一的关系 2.线性表的顺序存储结构（使用连续的存储空间） ·顺序表 特点：可以随机访问 。 插入：若有n个元素的顺序表，在第i个元素之前插入， 也即插入元素作为第i个元素 i=n+1时移动元素次数为0； i=1时移动元素次数为n; 一般情况n-i+1; 等概率情况下平均n/2
第2章 线性表 1.线性表的逻辑结构 • 前驱、后继 • 一对一的关系 2.线性表的顺序存储结构（使用连续的存储空间） • 顺序表 特点：可以随机访问 • 插入:若有n个元素的顺序表，在第i个元素之前插入， 也即插入元素作为第i个元素 i=n+1时移动元素次数为0； i=1时移动元素次数为n； 一般情况n-i+1； 等概率情况下平均n/2
第2章 线性表 ·删除 i=1时移动元素次数为n-1; i=n时移动元素次数为0； 一般情况移动次数n-i; 等概率平均情况（n+1)/2. ·插入、删除的基本操作为元素移动 时间复杂度为0(n)
第2章 线性表 • 删除 i=1时 移动元素次数为n-1； i=n时移动元素次数为0； 一般情况移动次数n-i； 等概率平均情况（n+1）/2. • 插入、删除的基本操作为元素移动 时间复杂度为O(n)
第2章 线性表 3.线性表的链式存储结构（存储空间可以连续也可以不连续） ·链表（结点、头指针、尾结点、带头结点的链表） 特点：不能随机访问
第2章 线性表 3.线性表的链式存储结构（存储空间可以连续也可以不连续） • 链表（结点、头指针、尾结点、带头结点的链表） 特点：不能随机访问
第2章 线性表 4.单向链表 。 静态法（说明变量）建立链表 尾插法建立链表（头指针、q始终指向尾结点、p生成新结点） 头插法建立链表（头指针、q始终指向头结点、p生成新结点） 插入（在第i个结点前插入新结点，p生成新结点，q指向第 i-1个结点…) 。 删除（删除第i个结点，q指向第i个结点的前驱（第i-1个结 点)，p指向第i个结点) 四种操作都必须知道操作位置结点的前驱结点的指针
第2章 线性表 4.单向链表 • 静态法（说明变量）建立链表 • 尾插法建立链表（头指针、q始终指向尾结点、p生成新结点） • 头插法建立链表（头指针、q始终指向头结点、p生成新结点） • 插入（在第i个结点前插入新结点，p生成新结点，q指向第 i-1个结点…） • 删除（删除第i个结点，q指向第i个结点的前驱（第i-1个结 点），p指向第i个结点） • 四种操作都必须知道操作位置结点的前驱结点的指针
第2章 线性表 5.单向循环链表 。 特点：从任一结点开始可以访问到表中其它结点，但 不能随机访问 ·由单向链表构造单向循环链表 ·如何判断单向循环链表 ·把两个单向循环链表链成一个 单向循环链表（给定两个链表的尾指针，由尾指针 可以得到链表的头指针) 6.双向循环链表 存储结构 特点 插入、删除
第2章 线性表 5.单向循环链表 • 特点：从任一结点开始可以访问到表中其它结点，但 不能随机访问 • 由单向链表构造单向循环链表 • 如何判断单向循环链表 • 把两个单向循环链表链成一个 单向循环链表（给定两个链表的尾指针，由尾指针 可以得到链表的头指针） 6.双向循环链表 ⚫ 存储结构 ⚫ 特点 ⚫ 插入、删除