数据结构课件吴伟民编著.ppt

第二章线性表 线性结构特点 在数据元素的非空有限集中存在唯一的一个被称作 第一个 的数据元素存在唯一的一个被称作 最后一个 的数据元素除第一个外 集合中的每个数据元素均只有一个前驱除最后一个外 集合中的每个数据元素均只有一个后继 第二章线性表 教学目的 1 了解线性表的逻辑结构特性 以及线性表的两种存储实现方式 2 熟练掌握顺序表的定义与实现 包括查找 插入 删除算法的实现 3 熟练掌握在各种链表结构中实现线性表操作的基本方法 能在实际应用中选用适当的链表结构 教学的重点和难点 链表 2 1线性表的定义及运算1 线性表的定义 是由n n 0 个数据元素 结点 a1 a2 a3 an组成的有限序列 其中 n为数据元素的个数 也称为表的长度 当n 0时 称为空表 非空的线性表 n 0 记作 a1 a2 a3 an 2 线性表的逻辑特征 1 有且仅有一个开始结点a1 无直接前趋 2 有且仅有一个终端结点an 无直接后继 3 其余的结点ai都有且仅有一个直接前趋ai 1和一个直接后继ai 1 4 ai是属于某个数据对象的元素 它可以是一个数字 一个字母或一个记录 3 线性表的特性 1 线性表中的所有数据元素的数据类型是一致的 2 数据元素在线性表中的位置只取决于它的序号 3 结点间的逻辑关系是线性的 线性表的形式化定义为 linear list D R 其中D ai 1 i n n 0 ai elemtype R 1 i n 1 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 例3 学生健康情况登记表如下 抽象数据类型的定义为 P19 4 线性表的运算数据的运算是定义在逻辑结构上的 而具体的实现则在存储结构上进行 1 存取 2 插入 3 删除 4 查找 5 合并 6 分解 7 排序 8 求线性表的长度 基本运算 2 2线性表的顺序存储结构 顺序表 1 顺序表的定义 用一组连续的存储单元 地址连续 依次存放线性表的各个数据元素 即 在顺序表中逻辑结构上相邻的数据元素 其物理位置也是相邻的 2 顺序表中数据元素的存储地址若一个数据元素占L个存储单元 则其存储方式参见下图 地址内容元素在表中的位序 1 i 2 n 空闲区 i 1 L b LOC a1 b L b i 1 L b n 1 L b max 1 L 从图中可以看出 LOC ai 1 LOC ai l一般地 有第i个数据元素的存储位置为 LOC ai LOC a1 i 1 lLOC a1 称为基地址 第一个数据元素的存储位置 显然 数据元素在顺序表中位置取决于数据元素在线性表中的位置 顺序表的特点是 逻辑位置相邻 其物理位置也相邻 一个一维数组 下标的范围是 到 每个数组元素用相邻的 个字节存储 存储器按字节编址 设存储数组元素 的第一个字节的地址是 则 的第一个字节的地址是 113 例1 因此 LOC M 3 98 5 3 0 113 解 地址计算通式为 LOC ai LOC a1 L i 1 3 顺序表的描述 由于C语言中的一维数组也是采用顺序存储表示 故可以用数组类型来描述顺序表 又因为除了用数组来存储线性表的元素之外 顺序表还应该用一个变量来表示线性表的长度属性 所以我们用结构类型来定义顺序表类型 defineListSize100typedefintElemType typedefstruc ElemTypedata ListSize intlength Sqlist 4 顺序表的几种基本运算在顺序表存储结构中 很容易实现线性表的一些操作 如线性表的构造 第i个元素的访问 注意 C语言中的数组下标从 0 开始 因此 若L是Sqlist类型的顺序表 则表中第i个元素是L data i 1 以下主要讨论线性表的插入和删除两种运算 1 插入线性表的插入运算是指在表的第i 1 i n 1 个位置上 插入一个新结点x 使长度为n的线性表 a1 ai 1 ai an 变成长度为n 1的线性表 a1 ai 1 x ai an 插入算法的思想 1 将ai ai 1 an依次后移一个位置 使第i位置留空2 将新元素x放在空出的位置上 3 线性表长度加1 演示 x VoidInsertList Sqlist L ElemTypex inti intj if iL length 1 printf Positionerror returnERROR if L length ListSize printf overflow exit overflow for j L length 1 j i 1 j L data j 1 L data j L data i 1 x L length 插入算法分析 上述算法for循环语句的执行次数为n i 1 若i 1 需移动全部n个结点 最坏 O n 若i n 1 在表尾插入 无需用移动结点 直接插入即可 最好O 1 移动结点的平均次数 按等概率考虑 可能的插入位置为i 1 2 n n 1共n 1个 则pi 1 n 1 所以 顺序表插入算法平均约需移动一半结点 2 删除线性表的删除运算是指将表的第i 1 i n 结点删除 使长度为n的线性表 a1 ai 1 ai ai 1 an 变成长度为n 1的线性表 a1 ai 1 ai 1 an 删除算法的思想 1 将ai 1 an依次前移一个位置2 线性表长度减1 演示 VoiddeleteList Sqlist L inti intj if iL length printf Positionerror returnERROR for j i jlength 1 j L data j 1 L data j L length 删除算法分析 上述算法for循环语句的执行次数为n i 若i 1 最坏 O n 若i n 无需用移动结点 直接删除即可 最好O 1 移动结点的平均次数 按等概率考虑 可能的删除位置为i 1 2 n共n个 则pi 1 n所以 顺序表插入算法平均约需移动一半结点 小结 顺序表插入 删除算法平均约需移动一半结点 当n很大时 算法的效率较低 顺序表存储空间的动态分配 若将前面线性表的顺序存储结构类型中的数组形式改为指针形式 则得到动态分配形式如下 typedefintElemType typedefstruct ElemType elem intlength intlistsize Sqlist 顺序存储结构的优缺点优点逻辑相邻 物理相邻可随机存取任一元素存储空间使用紧凑缺点插入 删除操作需要移动大量的元素预先分配空间需按最大空间分配 利用不充分表容量难以扩充 2 3线性表的链式存储结构存储方式用一组任意的存储单元存储线性表的数据元素利用指针实现用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai 除存储本身信息外 还需存储其直接后继的信息结点 数据ai的链式存储映象 数据域 元素本身信息指针域 指示直接后继的存储位置 链式存储结构 n个结点链结成的一个链表 单链表中每个结点的存储地址是存放在其前趋结点next域中 而开始结点无前趋 故设头指针head指向开始结点 同时 由于终端结点无后继 故终端结点的指针域为空 即null 图示中也可用 表示 一 线性链表结点中只含一个指针域的链表叫 也叫单链表 例线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 的单链表示意图如下 43 13 1 NULL 37 7 19 25 头指针 listnode h p p 表示p所指向的结点 p data p data表示p指向结点的数据域 p next p next表示p指向结点的指针域 生成一个listnode型新结点 p listnode malloc sizeof listnode 系统回收p结点 free p TypedefcharElemtype Typedefstructnode Elemtypedata structnode next listnode 用C语言描述的单链表如下 头结点 在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为空 单链表上的查找运算 1 按序号查找get L i 在单链表L中查找第i个位置上的元素 若找到 则返回它的地址 否则返回NULL 算法思想如下 从头结点开始顺链扫描 用指针p指向当前扫描到的结点 用j作统计已扫描结点数的计数器 当p扫描下一个结点时 j自动加1 P的初值指向头结点 j的初值为0 当j i时 指针p所指的结点就是第i个结点 listnode get listnode L inti intj listnode p j 1 p L next while jnext returnp 算法的时间复杂度都为 n 2 按值查找Locate L x 在单链表L中 查找值为x的结点 若找到 返回它的地址 否则返回NULL 算法思想如下 从开始结点出发 顺链逐个结点的值和给定值key作比较 listnode Locate listnode head elemtypex listnode p p head next while p NULL 算法的时间复杂度都为 n 单链表上的插入运算 若将x插入a和b之间 插入结点的指针变化如图所示 算法思想 1 先求出第i 1个结点 2 然后在第i 1个结点之后插入结点x s next p next p next s INSERT listnode L elemtypex inti listnode p s intj p L j 0 while p end 单链表上的删除运算 若将x删除 删除结点的指针变化所示 思想 先找到被删结点 第i个 的前趋结点 即第i 1个结点 p 然后删除 p的后继 DELETE listnode L inti listnode p q intj p L j 0 while p next elseprintf error n end 思考 如何实现删除线性表head中数据域为a的结点 建立单链表 头插法建表 思想 从一个空表开始 重复读入数据 生成新结点 将读入数据存放在新结点的数据域中 然后将新结点插入到当前链表的表头上 直到读入结束标志为止 Listnode creatlist intn listnode p L inti L listnode malloc sizeof listnode L next NULL for i n i 0 i p listnode malloc sizeof listnode scanf 单链表特点它是一种动态结构 整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取 查找速度慢 二 循环链表 circularlinkedlist 循环链表是表中最后一个结点的指针指向头结点 使链表构成环状特点 从表中任一结点出发均可找到表中其他结点 提高查找效率操作与单链表基本一致 循环条件不同单链表p或p next NULL循环链表p或p next H 在有些情况下 在循环链表中设立尾指针而不设头指针 可使某些操作简化 例如将两个线性链表合并成一个表时 只需将一个表的表尾与另一个表的表头相接 例 在链表上实现将两个线性表 a1 a2 a3 an 和 b1 b2 b3 bn 链接成一个线性表的运算 linklistconnect linklist heada linklist headb linklistp heada next heada next headb next nextfree headb next headb next p return headb 三 双向链表 doublelinkedlist 单链表具有单向性的缺点结点定义 typedefstructnode elemtypedata structnode prior next JD p prior next p p next proir voiddel dulist listnode p p prior next p next p next prior p prior free p 删除 算法描述 p prior next p next p next prior p prior voidins dulist listnode p intx listnode s s listnode malloc sizeof listnode s ele