数据结构 第2章 线性表.ppt

1 线性结构的定义 若结构是非空有限集 则有且仅有一个开始结点和一个终端结点 并且所有结点都最多只有一个直接前趋和一个直接后继 可表示为 a1 a2 an 简言之 线性结构反映结点间的逻辑关系是的 特点 只有一个首结点和尾结点 特点 除首尾结点外 其他结点只有一个直接前驱和一个直接后继 线性结构包括 线性表 堆栈 队列 字符串 数组等 其中最典型 最常用的是 线性表 一对一 1 1 2 第2章线性表 2 1线性表的基本概念2 2线性表的顺序存储结构及其算法2 3线性表的链式存储结构及其算法2 4算法应用举例 3 2 1线性表的基本概念 线性表它是一种最简单的线性结构 是一种可以在任意位置进行插入和删除数据元素操作的 由n n 0 个相同类型数据元素a0 a1 an 1组成的线性结构 4 a0 a1 ai 1 ai ai 1 an 1 线性表的逻辑结构 n 0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 n 0 空表 线性终点 5 A B C D Z 例2分析学生档案表是什么结构 分析 数据元素都是同类型 记录 元素间关系是线性的 分析 数据元素都是同类型 字母 元素间关系是线性的 注意 同一线性表中的元素必定具有相同特性 例1分析26个英文字母组成的英文表是什么结构 6 线性表抽象数据类型 它包括两个方面 数据集合 a0 a1 an 1 ai的数据类型为DataType操作集合 1 InitList List 初始化线性表 建一空线性表List 2 ListLength L 求当前数据元素个数 3 GetElement List i 取线性表中第i个元素 1 n 4 ListInsert L i x 插入数据元素 5 ListDelete L i x 删除数据元素 6 ListGet L i x 取数据元素等 7 3 线性表的存储结构 1 顺序存储结构 它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法 特点 任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻 逻辑上相邻的元素 物理上也相邻 2 链式存储结构 它是把数据元素和指针定义成一个存储体 使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法 特点 任意两个在逻辑上相邻的数据元素在物理上不一定相邻 数据元素的逻辑次序是通过链中的指针链接实现的 8 2 2线性表的顺序存储结构及其算法 一 顺序表的存储结构二 顺序表的实现三 顺序表的运算效率分析 9 一 顺序表的存储结构表示 1 顺序表 用一组地址连续的存储单元依次存储线性表的各个数据元素 即采用顺序存储结构的线性表 它通常采用静态数组实现数据元素的存储 可以利用数组V n 来实现 注意 在C语言中数组的下标是从0开始 即 V n 的有效范围是从V 0 V n 1 10 1 逻辑上相邻的数据元素 其物理上也相邻 2 若已知表中首元素在存储器中的位置 则其他元素存放位置亦可求出 利用数组V n 的下标 设首元素a0的存放地址为LOC a0 称为首地址 设每个元素占用存储空间 地址长度 为L字节 则表中任一数据元素的存放地址为 LOC ai 1 LOC ai LLOC ai LOC a0 L i 对上述公式的解释如图所示 2 线性表顺序存储特点 11 地址内容元素在表中的位序 0 i 1 n 1 空闲区 i 1 L b LOC a0 b L b iL b n 1 L b MaxSize 1 L LOC ai LOC a0 L i 3 线性表的顺序存储结构示意图 12 4 用C语言描述 typedefstruct DateTypelist MaxSize intsize SeqList MaxSize表示数组的最大元素个数 list表示顺序表的数组名 size表示顺序表中当前存储的数据元素个数 它必须满足size MaxSize SeqList是该结构体的名字 13 设有一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是 则 的第一个字节的地址是多少 113 LOC M 3 98 5 3 113 解 已知地址计算通式为 LOC ai LOC a0 L i 例1 14 charV 30 voidbuild 字母线性表的生成 即建表操作 inti V 0 a for i 1 i n 1 i V i V i 1 1 核心语句 方法1V i V i 1 1 方法2V i a i 方法3V i 97 i 例2 用数组V来存放26个英文字母组成的线性表 a b c z 写出在顺序结构上生成和显示该表的C语言程序 15 voidmain void 主函数 字母线性表的生成和输出 n 26 n是表长 是数据元素的个数 而不是V的实际下标 build display voiddisplay 字母线性表的显示 即读表操作 inti for i 0 i n 1 i printf c v i printf n 执行结果 abcdefghijklmnopqrstuvwxyz 16 二 顺序表的实现 或操作 数据结构的基本运算 修改 插入 删除 查找 排序 1 修改通过数组的下标便可访问某个特定元素并修改之 核心语句 V i x 显然 顺序表修改操作的时间效率是O 1 17 在线性表 n个元素 的第i个位置前插入一个元素 实现步骤 将第n至第i位的元素向后移动一个位置 将要插入的元素写到第i个位置 表长加1 注意 事先应判断 插入位置i是否合法 表是否已满 for j n 1 j i j a j 1 a j a i x n 元素后移一个位置 插入x 表长加1 核心语句 2 插入 18 在线性表的第i个位置前插入一个元素的示意图如下 插入25 19 实现步骤 将第i 1至第n位的元素向前移动一个位置 表长减1 注意 事先需要判断 删除位置i是否合法 删除线性表的第i个位置上的元素 for j i 1 j n 1 j a j 1 a j n 元素前移一个位置 表长减1 核心语句 3 删除 20 删除顺序表中某个指定的元素的示意图如下 21 例 建立一个线性表 先依次输入数据元素1 2 3 4 10 然后删除 最后依次显示当前线性表中的数据元素 假设该线性的数据元素个数最坏情况下不会超过100个 实现方法 1 采用直接编写一个主函数实现 2 利用已设计实现的抽象数据类型模块 存放在头文件名为SeqList h中 通过 include SeqList h 22 三 顺序表操作的效率分析 算法时间主要耗费在移动元素的操作上 因此计算时间复杂度的基本操作 最深层语句频度 T n O 移动元素次数 而移动元素的个数取决于插入或删除元素的位置 思考 若插入在尾结点之后 则根本无需移动 特别快 若插入在首结点之前 则表中元素全部要后移 特别慢 应当考虑在各种位置插入 共n 1种可能 的平均移动次数才合理 时间效率分析 23 推导 假定在每个元素位置上插入x的可能性都一样 即概率P相同 则应当这样来计算平均执行时间 将所有位置的执行时间相加 然后取平均 若在首结点前插入 需要移动的元素最多 后移n次 若在a1后面插入 要后移n 1个元素 后移次数为n 1 若在an 1后面插入 要后移1个元素 若在尾结点an之后插入 则后移0个元素 所有可能的元素移动次数合计 0 1 n n n 1 2 故插入时的平均移动次数为 n n 1 2 n 1 n 2 O n 共有多少种插入形式 连头带尾有n 1种 24 同理可证 顺序表删除一元素的时间效率为 T n n 1 2 O n 插入效率 删除效率 即插入 删除算法的平均时间复杂度为O n 25 链式存储结构 本节小结 线性表顺序存储结构特点 逻辑关系上相邻的两个元素在物理存储位置上也相邻 优点 可以随机存取表中任一元素 方便快捷 缺点 在插入或删除某一元素时 需要移动大量元素 解决问题的思路 改用另一种线性存储方式 26 作业