第二章线性表22

第二章线性表 本章要点 线性结构的特点线性表的顺序存储的定义及各种运算线性表的链式存储的定义及各种运算线性表的顺序 链式存储在时空性能上的差异 本章导读 线性表 Linearlist 是最简单且最常用的一种数据结构 这种结构具有下列特点 存在一个唯一的没有前驱的 头 数据元素 存在一个唯一的没有后继的 尾 数据元素 此外 每一个数据元素均有一个直接前驱和一个直接后继数据元素 2 1线性表的类型定义 线性表由一组具有相同属性的数据元素构成 数据元素在不同的具体情况下 可以有不同的含义 在一些复杂的线性表中 每一个数据元素又可以由若干个数据项 Dataitem 组成 在这种情况下 通常将数据元素称为记录 record 线性表的例子 例1 英文字母表 A B C D E F X Y Z 例2 一列火车的车厢编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 例3 职工工资表 每一个职工的工资是一个记录 数据元素 每个记录包含八个数据项 综上所述 元素个数n为表长度 n 0为空表元素同构 且不能出现缺项 一个线性表是n n 0 个数据元素a0 a1 a2 an 1的有限序列 LinearList D R 其中 D ai ai ElemSet i 0 1 2 n 1n 1 R ai 1 ai D i 0 1 2 n 1 Elemset为某一数据对象集 n为线性表的长度 抽象数据类型线性表的定义如下 2 2线性表的顺序表示和实现 概念 在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素 称作线性表的顺序存储结构 顺序存储 Sequentialstorage Mapping 设一元素占用一个存储单元 例如 线性表 a1a2a3a4 只需4个存储单元 但它只能存储在图 1 的区域 图 2 中 虽然也有大于线性表所需的存储空间 但是 不能用来存储这个表 因为 图2中没有位置连续的4个可用单元 若用图2必将数据A或B进行移动 01234 M 1 01234 M 1 图2 1有满足需要的连续空间 图2 2没有满足需要的连续空间 AB 顺序存储中逻辑地址与物理地址之间的关系 顺序存储的实现在高级程序语言中 一般都用数组来描述顺序存储 在C语言中可用动态分配的一维数组描述如下 defineLIST INIT SIZE100 初次分配用户预估空间量 defineLISTINCREAENT10 每次分配增量Typedefstruct ElemType elem 数组指针表的基址intlength 当前长度 实际已存元素个数intlistsize 任何时刻能存最多元素个数 SqList 空间量 最多元素个数 每次分配增量 每个元素占用空间量 calloc realloc malloc Free C动态存储分配函数 Malloc 函数 函数格式 void 或char malloc unsignedsize 函数功能 在内存中分配大小为size字节的地址连续的空间 函数返回值 所分配的内存块首字节地址 若分配不成功 如内存不够 则返回0 Malloc 函数举例 例1 分配内存地址连续的变量Int p P int malloc 3 sizeof int 例2 分配内存地址连续的结构体Structstudent p P structstudent malloc sizeof structstudent Free 函数 函数格式 void 或char free void p 函数功能 释放P所指的内存区 函数返回值 无 1 构成一个空线性表 StatusInitList Sq SqList 2 线性表上的插入操作已知内存中有Sq List类型的顺序表L a1 ai 1 ai an 要求把一个新的数据e插到表中第I个数据之前 e插入前为图1 e插入后为图2 图2 3新数据e插入前 a1a2 aiai 1 an 1an a1a2 eai 1 anan 1 图2 4 新数据e插入后 01 i 1i n 1n 比较两图可以看出 e插入前 原在第i 1位置上的元素ai 在e插入后 变为第i位置上的元素ai 1 下面介绍实现上述操作的基本算法 01 i 1i n 1 VoidInsertlist seqlist L datatypex inti if iL length 1 Error positionerror 插入位置不合法if L length 1 L listsize Error overflow 申请空间已用完For j L length 1 j i 1 j 要求合理L elem j 1 L elem j 移动数据 为x腾空间L elem i 1 x 插入xL length 已存表长度加1 该算法是用基本的C语言编写的 当预定义的空间用完后 没有动态再给用户分配空间的功能 下面给出功能强的算法 StatusListInsert Sq SqList 现在 分析该算法的时间复杂性 其时间主要是移动数据操作的次数 假设pi是第i个数据之前插入一个数据的概率 则在长度为n的表中插入一个数据时移动次数的期望值 平均次数 为Eis Pi n i 1 假设在线性表的任何位置上插入数据都是等概率的 即Pi 1那么Eis n i 1 n 1 1 2 n n 1 1 n 1 i 1 3 线性表上的删除操作例如要求把下表1中第5个数据删除 注意第5个数据实际上是表中序号 即逻辑地址 为4的元素即数据e abcdfghi 表1删除前 表2删除后 abcdefghi 012345678 a1a2a3a4a5a6a7a8a9 abcdefghi 01234 p 5678 q 01234 p 5678 q 图2 5 数据删除前后 删除算法的描述 StatusListDelete Sq SqList 删除算法的时间估算假设qi是删除第i个元素的概率 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值 平均次数 为Edi qi n i 如果删除任何位置的元素都是等概率即qi Edi n i 由此可知该算法的时间复杂性为O n n 1 1 n 1 1 2 n i 1 n i 1 n 4 顺序查找 StatusListSearch Sq SqList abcdefghi 012345678 a1a2a3a4a5a6a7a8a9 5 线性表的合并 VoidmergeList sq SqlistLa SqlistLb SqlistLc 1 pa La elem pb Lb elem 2 Lc list Lc length La length Lb length 3 pc Lc elem ElemType malloc Lc listsize sizeof ElemType 4 pa last La elem La length 1 5 pb last Lb elem Lb length 1 6 while pa pa last 顺序存储小结优点逻辑相邻 物理相邻可随机存取任一元素存储空间使用紧凑缺点预先分配空间需按最大空间分配 利用不充分在任意位置上的插入与删除元素时 平均移动表的一半元素 当n很大时 效率很低 2 3线性表的链式表示和实现 为什么要用链式存储 LinkedList 希望能克服顺序存储的一些缺点 特点 用一组任意的存储单元存储线性表的数据元素利用指针实现了 用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai 除存储本身信息外 还需存储其直接后继的信息 1 线性链表 单链表 结点 node 线性表中一个数据元素所占用的存储空间 它由数据域与指针域两部分组成 数据域用来存储用户的有效数据 指针域用来存储直接后继数据元素所在结点的地址 王二麻子 0 x99fc 数据域 指针域 结点 例线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 43 13 1 NULL 37 7 19 25 头指针 单链表的存储结构定义 TypedefstructLNode ElemTypedata structLNode next LNode LinkList 说明 data域可以是任何复杂的结构体 Next的类型一定是本结构体类型 单链表的建立 无头节点的链表有头结点的链表 a b c d e0 a b c d e0 5 头结点 存储链表的长度 有头结点链表的建立 next head Data0 tail p 有头结点链表的建立 typedefstructLnode intdata structLnode next LNODE LNODE creat intx LNODE head p tail tail LNODE malloc sizeof LNODE head tail tail next 0 while 1 scanf d 单链表的插入 head Data s Data0 Data p 单链表的插入 ListInsert LNODE L intI intx LNODE p s intj 0 p L 1 while p 单链表的删除 head Data Data q Data0 p 单链表的删除 ListDelete LNODE L intI int x LNODE p q intj 0 p L 1 while p next 单链表插入 删除的特点 链表是顺序访问方式 非随机的访问 利用概率论知识 较容易得知此操作的时间复杂度应为 T n O n 两个单链表的合并 1 VoidMergeList LNODE La LNODE Lb LNODE Lc 2 pa La next pb Lb next Lc pc La 3 while pa11 时间复杂度 T n O La长度 Lb长度 思考题 求单链表的长度unsignedGetLength LNODE L 获取第pos个元素的值intGetElem LNODE L unsignedpos 判断在单链表中是否存在某元素unsignedFindInList LNODE L intdata 若利用单链表的头结点存储链表的长度 对链表的操作效率有益否 2 循环链表 circularlinkedlist 循环链表 是表中最后一个结点的指针指向头结点 使链表构成环状 特点 从表中任一结点出发均可找到表中其他结点 提高查找效率操作与单链表基本一致 循环条件不同单链表为 p或p next NULL循环链表为 p或p next Head 思考题 循环链表的操作 建立插入删除合并遍历循环链表和单链表的区别 3 双向链表 doublelinkedlist typedefstructnode structnode prior datatypedata structnode next DLList 单链表只有单向性 不能回溯 而双向表可以 p prior next p p next proir 双向链表的插入 intinsert dl DLList head inti datatypex 在带头结点的双向链表中第i个位置之前插入元素x DLList p s intj 0 p head while p NULL 1 当在链表中的第一个结点前插入新结点时 2 当在链表的最后一个结点后插入新结点时 讨论 在带头双向链表中进行插入操作时 还需注意下面两种情况 在双向链表中删除一个结点时 可用指针p指向该结点 称p结点 将p结点的前一个结点的next指向p结点的下一个结点 将p的下一个结点的prior指向p的上一个结点 在带头双向链表中删除一个结点 intDelete dl DLList head inti DLList p s intj 0 p head while p NULL 双向链表中结点的删除 1 当删除链表的第一个 头结点后 结点时 应将链表第二个结点的prior指向头结点 2 当删除链表的最后一个结点时 只需将链表的最后一个结点的上一个结点的next置为NULL即可 讨论 在双向链表中进行删除操作时 需注意下面两种情况 思考题 带头双向链表的其他操作 建立 DLList CreatDLList 求长度 intGetLength DLList list 输出数据 voidDisplay DLList list 双向循环链表的构造及其操作 链式存储结构的优点 1 结点可以动态申请和释放 2 数据元素的逻辑次序靠结点的指针来指示 不需要移动数据