第3单元 线性数据结构 计算机软件基础 The software bas ic of computer 主讲:赵英良 西安交通大学 计算机教学实验中心
下一页 计算机软件基础 The software basic of computer 主讲：赵英良 西安交通大学 计算机教学实验中心 第3单元 线性数据结构 （二）
第2单元内容概要(一) 、数据结构 1。基本概念:数据、数据元素、数据项、数据结构、 数据结构的形式化描述方法 2。数据的逻辑结构: 逻辑结构的类别(集合、线性、树、图) 3。数据的物理结构及类别(顺序、链式、索引、散 列) 4。算法的描述及评价 (1)算法的概念: (2)算法的特性:有限、确定、可行、输入、输出 上一页 (3)设计算法的要求:正确、可读、健壮、效率 停止放映(4)算法的评价:时间复杂性、空间复杂性 下一页 第2页
下一页 上一页 停止放映 第 2 页 第2单元内容概要（一） 一、数据结构 1。基本概念：数据、数据元素、数据项、数据结构、 数据结构的形式化描述方法。 2。数据的逻辑结构： 逻辑结构的类别（集合、线性、树、图） 3。数据的物理结构及类别（顺序、链式、索引、散 列） 4。算法的描述及评价 （1）算法的概念： （2）算法的特性：有限、确定、可行、输入、输出 （3）设计算法的要求：正确、可读、健壮、效率 （4）算法的评价：时间复杂性、空间复杂性
第2单元内容概要(二) 、顺序表 1。线性表及相关概念和特征 线性表、长度、空表、前驱、后继 均匀性、有序性、形式化定义 2。顺序表 概念、特征、描述(数组、last) 3。顺序表的操作 (1)判空、判满、判合法(2)插入(3)删除 ●4。顺序表的优缺点及适用场合 数据连续存放、随机存取 上一页 逻辑上相邻,物理上也相邻 「停止放映 存储结构简单、易实现 插入、删除操作不便 下一页 存储密度大,空间利用率高 第3页
下一页 上一页 停止放映 第 3 页 第2单元内容概要（二） ⚫ 二、顺序表 1。线性表及相关概念和特征 线性表、长度、空表、前驱、后继、 均匀性、有序性、形式化定义 2。顺序表 概念、特征、描述（数组、last） 3。顺序表的操作 （1）判空、判满、判合法 （2）插入（3）删除 ⚫ 4。顺序表的优缺点及适用场合 – 数据连续存放、随机存取 – 逻辑上相邻，物理上也相邻 – 存储结构简单、易实现 – 插入、删除操作不便 – 存储密度大，空间利用率高
第2单元内容概要(三) 链表 1。单链表 结点、指针域、数据域、头指针、头结点。 2。单链表的描述 3。单链表的操作 (1)指针操作 指针说明、分配存储空间、判空、判满、释放 空间 (2)查找操作(3)插入(4)删除 上一页 4。单链表的特点及适用场合 5。单循环链表、双向链表、双向循环链表 「停止放映 描述、建立、判空、查找、插入、删除 下一页 第4页
下一页 上一页 停止放映 第 4 页 第2单元内容概要（三） ⚫ 三、链表 ⚫ 1。单链表 ⚫ 结点、指针域、数据域、头指针、头结点。 ⚫ 2。单链表的描述 ⚫ 3。单链表的操作 ⚫ （1）指针操作、 ⚫ 指针说明、分配存储空间、判空、判满、释放 空间 ⚫ （2）查找操作 （3）插入 （4）删除 ⚫ 4。单链表的特点及适用场合 ⚫ 5。单循环链表、双向链表、双向循环链表 描述、建立、判空、查找、插入、删除
本单元内容 栈、队列、数组、串的 有关概念 逻辑结构及特点 存储结构 有关操作 涉及章节:第1章的 1.3栈和队列(P32~P46) 上一页 1.4串和数组(P47P55) 「停止放映 下一页 第5页
下一页 上一页 停止放映 第 5 页 本单元内容 ⚫ 栈、队列、数组、串的: –有关概念 –逻辑结构及特点 –存储结构 –有关操作 ⚫ 涉及章节：第1章的 1.3 栈和队列 (P32~P46) 1.4 串和数组 (P47~P55)