c2-线性表(一)

线性表 一 执行校长 李伟 数据结构 第二讲 知识回顾 数据逻辑结构有那些 数据的物理结构有那些 算法的特性和要求 教学内容 线性表的类型定义线性表的顺序表示和实现 重点 难点 重点线性表的定义线性表的顺序表示和实现方法难点线性表的顺序存储的实现方法 线性表的类型定义 线性表的类型定义线性表的顺序表示和实现 线性表的类型定义 线性结构定义若结构是非空有限集 则有且仅有一个开始结点和一个终端结点 并且所有结点都最多只有一个直接前驱和一个直接后继 可表示为 a1 a2 an 线性表的类型定义 特点存在唯一的被称为 第一个 的数据元素 即首元素或者头元素 存在唯一的被称为 最后一个 的数据元素 即尾元素 除首尾元素外 其他数据元素只有一个直接前驱和一个直接后继 简言之 线性结构反映结点间的逻辑关系是一对一的 线性表的类型定义 线性结构包括 线性表 堆栈 队列 字符串 数组等 其中最典型 最常用的是 线性表 线性表由n n 0 个数据元素a1 a2 an组成的有限序列 其中数据元素的个数n定义为表的长度 当n 0时称为空表 线性表的类型定义 常常将非空的线性表 n 0 记作 a1 a2 an 这里的数据元素ai 1 i n 只是一个抽象的符号 其具体含义在不同的情况下可以不同 线性表的类型定义 例1 分析26个英文字母组成的英文表是什么结构 分析 数据元素都是同类型 字母 元素间关系是线性的 A B C D Z 线性表的类型定义 例2分析学生情况登记表是什么结构 在复杂的线性表中 一个数据元素可以由若干个数据项组成 在这种情况下 常把数据元素称为记录 含有大量记录的线性表又称文件 分析 数据元素都是同类型 记录 元素间关系是线性的 数据项 记录 文件 注意 同一线性表中的元素必定具有相同特性 线性表的类型定义 线性表的逻辑结构 a1 a2 ai 1 ai ai 1 an 线性起点 线性终点 数据元素 ai的直接前驱 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 n为元素总个数 即表长 n 0 n 0时称为 空表 线性表的类型定义 抽象数据类型定义 ADTList 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 1 2 n 基本操作 InitList L 操作结果 构造一个空的线性表LDestroyList L 初始条件 线性表L已存在操作结果 销毁线性表LClearList L 初始条件 线性表L已存在操作结果 将L重置为空表ListEmpty L 初始条件 线性表L已存在操作结果 若L为空表 则返回TRUE 否则返回FALSE 线性表的类型定义 抽象数据类型定义 ListLength L 初始条件 线性表L已存在操作结果 返回L中数据元素的个数GetElem L I e 初始条件 线性表L已存在 1 i ListLength L 操作结果 用e返回L中第i个数据元素的LocateElem L e compare 初始条件 线性表L已存在 compare 是数据元素判定函数操作结果 返回L中第1个与e满足关系的数据元素的位序 若这样的数据元素不存在 则返回值为0PriorElem L cur e pre e 初始条件 线性表L已存在操作结果 若cur e是L的数据元素 且不是第一个 则用pre e返回它的前驱 否则操作失败 pre e无定义 线性表的类型定义 抽象数据类型定义 NextElem L cur e next e 初始条件 线性表L已存在操作结果 若cur e是L的数据元素 且不是最后一个 则用next e返回它的后继 否则操作失败 next e无定义ListInsert L i e 初始条件 线性表L已存在 1 i ListLength L 1操作结果 在L中第i个位置之前插入新的数据元素e L的长度加1ListDelete L i e 初始条件 线性表L已存在 1 i ListLength L 操作结果 删除L中第i个数据元素 并用e返回其值 L的长度减1ListTraverse L visit 初始条件 线性表L已存在操作结果 依次对L中的每个数据元素调用函数visit 一旦visit 失败 则操作失败 ADTList 线性表的类型定义 算法2 1 voidunion List La中不存在和e相同的数据元素 则插入 union 利用两个线性表LA和LB分别表示两个集合A和B 现要求一个新的集合A A B 线性表的类型定义 算法2 2 已知线性表LA和线性表LB中的数据元素按值非递减有序排列 现要求将LA和LB归并为一个新的线性表LC 且LC中的元素仍按值非递减有序排列 线性表的类型定义 voidmergelist ListLa ListLb List mergelist 线性表的类型定义 算法分析上述两个算法的时间复杂度取决于抽象数据类型List定义中基本操作的执行时间 假如GetElem和ListInsert这两个操作的执行时间和表长无关 LocateElem的执行时间和表长成正比算法2 1的时间复杂度为O ListLength LA ListLength LB 算法2 2的时间复杂度为O ListLength LA ListLength LB 线性表的类型定义 线性表的类型定义线性表的顺序表示和实现 线性表的顺序表示和实现 顺序存储结构把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里 用这种方法存储的线性表简称顺序表 顺序存储结构特点逻辑上相邻的数据元素 其物理上也相邻 物理顺序与逻辑顺序相同 可随机存取 若已知表中首元素在存储器中的位置 则其他元素存放位置亦可求出 利用下标i 线性表的顺序表示和实现 例 已知 每个元素需占用L个存储单元 并以所占的第一个单元的存储地址作为数据元素的存储位置 则线性表中第i 1个数据元素的存储位置LOC ai 1 和第i个数据元素的存储位置LOC ai 之间满足下列关系 LOC ai 1 LOC ai L线性表的第i个数据元素ai的存储位置为 LOC ai LOC a1 i 1 L 线性表的顺序表示和实现 地址内容元素在表中的位序 b LOC a1 b L b i 1 L b n 1 L b MaxSize 1 L 空闲区 L 1 i 2 n i 1 LOC ai LOC a1 L i 1 线性表的顺序表示和实现 高级程序设计语言中 数组类型也有随机存取的特性 所以通常用数组来描述数据结构中的顺序存储结构 在此 由于线性表的长度可变 且所需最大存储空间随问题不同而不同 则在C语言中可用动态分配的一维数组 线性表的顺序表示和实现 线性表的动态分配顺序存储结构 defineLIST INIT SIZE100 初始分配量 defineLISTINCREMENT10 分配增量typedefstruct ElemType elem 基址intlength 当前长度intlistsize 当前存储容量 SqList SqList为结构体名字 数组指针elem指示线性表的基地址 length指示线性表的当前长度 listsize指示顺序表当前分配的存储空间大小 当空间不足时 可进行再分配 为顺序表增加一个大小为LISTINCREMENT个数据元素的空间 线性表的顺序表示和实现 算法2 3 初始化在这种结构中 容易实现线性表的某些操作 只是要特别注意C语言中数组下标从 0 开始 则表中第i个数据元素的下标是 i 1 StatusInitList Sq SqList InitList Sq 线性表的顺序表示和实现 线性表的插入操作线性表的插入操作是指在线性表的第i 1个元素和第i个数据元素之间插入一个新的元素 插入新元素后线性表的数据元素ai 1和ai之间的逻辑关系发生了变化 在线性表的顺序存储结构中 由于逻辑上相邻的数据元素在物理位置上也是相邻的 因此 除非i n 1 否则必须移动元素才能反映这个逻辑关系的变化 在线性表的第i个位置前插入一个元素的示意图如下 插入25 线性表的顺序表示和实现 线性表的顺序表示和实现 实现步骤 将第n至第i位的元素向后移动一个位置 将要插入的元素写到第i个位置 表长加1 注意事先应判断 插入位置i是否合法 表是否已满 线性表的顺序表示和实现 算法2 4StatusListInsert Sq SqList L inti ElemTypee if iL length 1 returnERROR if L length L listSize newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType If newbase exit OVERFLOW L elem newbase L listsize LISTINCREMENT q ListInsert Sq 线性表的顺序表示和实现 插入操作算法时间复杂度这里的问题规模是表的长度n 插入算法的时间主要花费在结点后移的语句上 该语句的执行次数为n i次 与插入节点所在位置i有关 由此可看出 所需移动结点的次数不仅依赖于表的长度 而且还与插入位置有关 长度为n的表中插入元素需移动元素的平均次数Eis n 2ListInsert Sq的时间复杂度为O n 删除顺序表中某个指定的元素的示意图如下 线性表的顺序表示和实现 线性表的顺序表示和