数据结构 第1-2章 术语及线性表.ppt

数据库技术 浙江省计算机等级考试三级 绍兴文理学院经管学院张冰心13516758474667531zbxszq 浙江省计算机等级考试 三级 一 实行理论考试 二 包括 数据库技术 网络技术 微机系统及应用 单片机及嵌入式系统应用 数据库技术考试题型 一 判断题 2 10 二 选择题 1 35 2 10 三 综合题 25 1 结构化查询语句SQL 15 2 画E R图 10 数据库 是用来存放大量数据的仓库 这些数据是长期存放在计算机内 有组织的 可共享的数据集合 用户将数据以表 窗体等形式存入数据库 当用到该数据时 可直接到数据库中调用 例如 工资管理数据库存货管理数据库图书馆管理系统 一 什么是数据库 二 用什么创建数据库 在Microsoftoffice里有一组件叫Access 它就是一个数据库管理系统 数据库管理系统是位于用户与操作系统之间的一个数据管理软件 通过它 用户可根据自己的需求来创建数据库 Access2003是Access中最新的版本 若在安装时采用 完全安装 那么在打开Access时 鼠标左键单击 帮助 在下拉菜单里有一个罗斯文数据库示例 它是一个供求关系数据库示例 初学者可借此来加深对数据库的理解 典型的数据库管理系统 MicrosoftSQLServerMicrosoftAccessMicrosoftFoxProOracleSybase 三 数据库有什么用 不仅可以创建通讯簿 CD VCD收藏等个人使用的数据库 还可以创建公司人事管理系统等复杂的数据库 总之 你有什么样的需求就可以创建什么样的数据库 数据库技术 一 数据库 是用来存放大量数据的仓库 这些数据是长期存放在计算机内 有组织的 可共享的数据集合 二 数据库管理系统 是位于用户与操作系统之间的一个数据管理软件 三 数据库用户 数据库管理员 终端用户应用程序开发人员等 四 数据库系统 是指在计算机系统中引入数据库后的系统构成 是操作系统和应用系统之间的接口 五 数据库技术 研究如何科学地组织和管理数据 高效地获取和处理数据 数据 是信息的载体 是指能够被计算机识别 存储和加工的信息的载体 数据元素 是数据的基本单位 一个数据元素可以由一个或若干个数据项组成 在计算机程序中通常作为一个整体考虑和处理 数据项 数据的不可分割的最小单位 数据对象 是性质相同的数据元素的集合 是数据的一个子集 第一篇数据结构 第1章数据结构的基本概念及有关术语 数据元素与数据项的区别 1 数据元素是数据的基本单位 它在计算机存储器上的映像是结点 2 数据项是数据的最小标识单位 它在计算机存储器上的映像是数据域 例1 某选修课成绩表 整张表就是一个 数据 每一列就是一个 数据元素 也叫 记录 它在计算机存储器上的映象叫结点 每一列表示一个字段 每个单元格就是一个 数据项 每个学院汇总就是一个 数据对象 数据结构的基本概念及有关术语 二 数据结构 data structure 是相互之间存在的一种或多种特定关系的数据元素的集合 它反映一个数据的内部构成 即一个数据由哪些成份构成 以什么方式构成 呈什么结构 基本数据结构 线性结构 树 图 集合数据结构的形式定义为 DS D S 如 复数 表示为 Complex C R 其中 C是含两个实数的集合 c1 c2 R是定义在集合上的一种关系 数据结构包含的三方面 数据的逻辑结构 数据的物理存储结构和数据的运算 算法的设计取决与数据的逻辑结构 算法的实现取决与数据的物理存储结构 数据结构的基本概念及有关术语 三 数据的逻辑结构 是 数据结构 定义中的关系 指数据间的逻辑关系 包括 线性结构和非线性结构 其中非线性结构又包括 树型结构和网状结构 通常所说的数据结构就是指数据的逻辑结构 线性结构 除了第一个和最后一个元素以外 其他元素有且仅有一个直接前驱元素 有且仅有一个直接后继元素 树型结构 是一种层次关系 数据元素只能与上一层中的一个数据元素相关 但可以和下一层的多个数据元素相关 网状结构 任何两个数据元素间都可以相关 数据结构的基本概念及有关术语 四 数据的存储结构 是数据的逻辑结构的计算机存储器里的实现 亦称为映象 即数据元素及其关系在计算机中的表示 包括 顺序 链式 索引 散列等存储方式 A 顺序存储结构 逻辑结构中相邻的数据元素在存储器中存放的位置是相邻的 B 链式存储结构 逻辑结构中相邻的数据元素在存储器中存放的位置是不相邻的 是通过指针进行联系的 数据运算 施加于数据的操作 数据结构的基本概念及有关术语 五 数据类型 在一种程序设计语言中 数据类型指变量所具有的数据种类 如 整型 字符型 而在数据库中 是指一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型 AbstractDataTypes ADT 是一个数学模型以及定义在该模型上的一组操作 例如 线性表 这样的ADT 其数学模型是 数据元素的集合 该集合内的元素有这样的关系 除第一个和最后一个元素外 其他每个元素有惟一的前驱和惟一的后继 可以有这样一些操作 插入元素 删除元素等 ADT实际上就是对数据结构的定义 它定义了一个数据的逻辑结构以及在此结构上的一组算法 ADT的作用 可以使我们更容易描述现实世界 例如 用线性表描述学生成绩表 用树或图描述遗传关系 其关键在于 使用它的人可以只关心它的逻辑特征 不需要了解它的存储方式 同样 定义它的人同样不必要关心它如何存储 数据结构的基本概念及有关术语 六 算法 是指解决特定问题的方法 是由若干条指令组成的有穷序列 算法的基本特征 1 输入 0个或多个输入 2 输出 1个或多个输出 3 有穷性算法必须在有限步内结束 每步有限时间内完成 4 确定性组成算法的操作必须无二义性 5 可行性组成算法的操作必须能够在计算机上实现 算法的分析 主要是算法复杂度的分析方法及其运用 数据结构的基本概念及有关术语 七 评价算法的标准 正确性 可读性 健壮性 效率与低存储要求算法的时间复杂度T n 通常把算法中所含的简单操作的次数作为算法执行的时间的度量 并称其为算法的时间复杂度 不要求精确的计算 仅仅估算出其数量级即可 例 求下面程序的时间复杂度 x 0for i 1 i n i for j 1 j n j for k 0 k n k x 答案 o n 3 以上算法的时间复杂度为 O n3 O n3 表示该算法执行时间与n3成正比 即O n3 与n3同一数量级 数据结构的基本概念及有关术语 七 算法的时间复杂度一般来说 设算法中基本操作的执行次数是问题规模n的某个函数f n 算法的时间复杂度记作 T n O f n 它表示随问题规模n的增大 算法执行时间的增长率与f n 的增长率相同 有些算法 基本操作执行次数与问题的输入数据有关 这时可考虑 1 算法平均时间复杂度 2 算法在最坏情况下的时间复杂度 数据结构的基本概念及有关术语 八 算法的空间复杂度 用执行算法所需的辅助空间的大小作为算法所需空间的度量 设执行算法所需的辅助空间是问题规模n的某个函数g n 则算法空间复杂度记作 S n O g n 一个正在运行的算法 所占用的存储空间 存储算法本身所需的空间 算法在运行过程中所需的临时存储空间 输入 输出数据所占用的存储空间 第2章线性表 1 线性表的定义 线性表 linearlist 是由n n 0 个数据元素 结点 a1 a2 an组成的有限序列 1 数据元素的个数n定义为表的长度 n 0时为空表 2 将非空的线性表 n 0 记作 a1 a2 an 3 数据元素ai 1 I n 只是一个抽象符号 其具体含义在具体情况下是不同的 例如 26个英文字母的字母表 A B Z 是线性表 表中每个字母是一个数据元素 结点 线性表中的每个数据元素可以是一个数 一个字符 一幅图或更复杂的信息 在稍微复杂的线性表中 一个数据元素也可以由若干个数据项组成 这时常把数据元素称为记录 含有大量记录的线性表又称文件 2 线性表的逻辑结构 设A a1 a2 ai 1 ai ai 1 an 是一线性表 1 线性表的数据元素可以是各种各样的 但同一线性表中的元素必须是同一类型的 2 在表中ai 1领先于ai ai领先于ai 1 称ai 1是ai的直接前驱 ai 1是ai的直接后继 3 在线性表中 除第一个元素和最后一个元素之外 其他元素都有且仅有一个直接前驱 有且仅有一个直接后继 具有这种结构特征的数据结构称为线性结构 线性表是一种线性数据结构 4 线性表中元素的个数n称为线性表的长度 n 0时称为空表 5 ai是线性表的第i个元素 称i为数据元素ai的序号 每一个元素在线性表中的位置 仅取决于它的序号 线性表的基本操作 1 存取操作 存取线性表中第i个数据元素 2 查找操作 在线性表中查找满足条件元素 3 插入操作 在线性表的第i个元素之前插入一个新元素 4 删除操作 删除线性表的第i个元素 5 分解操作 将一个线性表拆分为多个线性表 6 合并操作 7 排序 3 线性表的存储结构 一 线性表的顺序存储结构 顺序表1 线性表 a1 a2 a3 an 的顺序存储结构采用一组地址连续的存储单元依次存储线性表的元素 并以存放元素的物理位置来体现元素之间的逻辑关系 线性表中的每个元素只占用存放自身数据信息的空间 而无需占用额外空间来存放表示元素间逻辑关系的信息 线性表的这种机内表示称作线性表的顺序存储结构 反之 称这种存储结构的线性表为顺序表 要点 A 假设线性表中所有的结点类型相同 则每个结点所占用存储空间大小亦相同 假设表中每个结点占用t个存储单元 并设表中开始结点a1的存储地址 通常称为线性表的基地址 是LOC a1 那么第i个元素的存储位置LOC ai 为 Loc ai Loc a1 i 1 t故 只要知道基地址和每个结点的大小 就可以在相同的时间内求出任一结点的存储地址 所以是一种随即存储结构 B 采用这种存储方式的优点就是空间利用率大 密度高 C 采用这种存储方式的线性表在进行删除 插入操作过程中 大部分时间被花在移动数据元素的操作中 故此法不适合需要频繁进行删除 插入操作的线性表 D 采用此法需预先分配存储空间 一旦空间分配完毕 存储容量就难以再被扩充 故长度变化较大的线性表 必须在预先分配存储空间时按线性表的最大长度进行分配 1 顺序表的插入操作 插入 insert v x i 功能 在顺序表v中的第i 1 i n 1 个数据元素之前插入一个新元素x 插入前线性表为 a1 a2 a3 ai 1 ai an 插入后 线性表长度为n 1 线性表为 a1 a2 a3 ai 1 x ai an 算法的时间主要花费在FOR循环中的结点后移语句上 该语句的执行次数是n I 1 假设在表中任何合法位置 1 I n 1 上的插入结点的机会是均等的 则p1 p2 pn 1 1 n 1 因此 在等概率插入的情况下 移动结点的平均次数 E pi n I 1 n I 1 n 1 n 2 2 顺序表的删除操作删除算法的主要步骤 A 若i不合法或表L空 算法结束 提示错误信息 B 将第i个元素之后的元素 不包括第i个元素 依次向前移动一个位置 C 表长 1算法的时间也是主要花费在结点移动上 该语句的执行次数是n I 假设在表中任何合法位置 1 I n 上的插入结点的机会是均等的 则p1 p2 pn 1 n 因此 在等概率删除的情况下 移动结点的平均次数 E pi n I n I n n 1 2 2 线性表的链式存储 采用一组任意的存储单元存储线性表的数据元素 在分配空间存放数据元素自身信息的同时 还需要为表示数据元素间逻辑关系的信息提供存储空间 这两部分信息组成了数据元素的存储映象 即结点 存放数据元素自身信息的域称为数据域 存放表示数据元素间逻辑关系信息的域称为指针域 Data域 存放结点值的数据域Next域 存放结点的直接后继结点地址的指针域 要点 A 不仅可以用来表示线性表 也可以表示各种非线性的数据结构 B 链式存储是一种只能顺序访问表中元素的存储结构 C 它即便于实现删除 插入等操作 又便于扩充表容量 只是空间利用率会降低 存放密度会下降 单链表链表通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起的 每个结点只有一个链域的链表称为单链表 HeadHead a 空表 b 非空表A 叫头结点 即第一元素结点前面的一个附加结点其中数据域可为空 也可为一些线性表的长度之类的辅助信息 B 中的 0 表示线性链表中最后一个结点的指针域为空 NULL 空指针 不指向任何结点 线性链表最后一个结点的指针通常是空指针 C 带头结点的线性链表 第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表 带头结点的好处是 使空表和非空表的处理统一 例 有线性表为 CHEN HE SUE LI WU ZHOU LIU ZHAO 采用链式存储 其物理存储结构如下图 在单链表中 从一已知结点出发 只能访问到该结点及其后续结点 无法找到该结点之前的其他结点 这一缺点在单循环链表中得到了弥补 此线性链表的逻辑状态 Head 单链表中元素的插入操作 A 利用结点变量的名字 p 表示指向某一结点的指针 访问结点分量 p 上图表示某一指针p指向某一结点 该结点的数据域可以表示成 p data或p data 它存放着该结点的内容 该结点的指针域可以表示成 p next或p next 它存放着该结点的后继结点的物理存放地址 B 插入运算是将值为X的新结点插入到表的第I个结点的位置上 即插到ai 1与ai之间 1 找到ai 1的物理存储位置p 不作要求 略 2 生成一个数据域为X的新结点 s 即S data X 3 新结点的指针域指向结点ai 即S next P next 4 令结点 p的指针域指向新结点 即P next S 例如在上例中 在数据域为SUN的结点和数据域为LI的结点中间插入一个数据域为FAN的结点 1 先找到SUN结点的物理存储位 此处为13 令指向SUN结点的箭头为p 此时SUN结点的指针域可表示成P next 2 再生成一个数据域为FAN的新结点 s 即S data FAN 3 因为SUN结点的指针域P next所存放的就是LI结点所在的物理存放地址 此处为为21 而语句S next P next就是将 21 赋值给了新结点 s的指针域 这样 s就指向了LI结点 4 最后将 s的物理存放地址赋值给SUN结点 即P next S 这样SUN结点后的指针就指向了 s 到此 插入操作完成 插入算法的时间只要耗费在查找ai 1上 故时间复杂度为o n 单链表中元素的删除操作 例如在上例中 想删掉数据域为ZHOU的结点 只要将WU结点的指针域存放LIU结点的物理存放地址即可 以下仅为关键操作步骤 1 指针p指向 则其指针域可表示p next 此处为25 将其赋值给r 即r p next 则此时指针r就指向了目标删除结点ai 此处为 此时r next 97 2 将r next赋值给p next 即p next r next 此时p next中原来的25被换成了97 成了 它的直接后继结点就是 注 删除操作也可写成 p next p next next 例题 1 某一单链表的每个结点中包括一个指针li