职业学院课件第2章-线性表

第2章线性表 本章内容 2 1线性表的基本概念2 2线性表的顺序存储2 3线性表的链式存储2 4顺序表与链表的比较2 5线性表的应用举例 约瑟夫环问题 小结习题2 2 1线性表的基本概念 2 1 1线性表的定义1 线性表的定义线性表是具有相同数据类型的n n 0 个数据元素的有限序列 通常记为 a1 a2 ai 1 ai ai 1 an 其中 n为表长 当n 0时称为空表 在线性表中相邻元素之间存在着顺序关系 如对于元素ai而言 ai 1称为ai的直接前驱 ai 1称为ai的直接后继 2 1线性表的基本概念 2 线性表举例 1 简单的线性表 例如 26个英文字母表 a b c d e f g x y z 又例如一周七天 1 2 3 4 5 6 7 2 复杂的线性表 例如 在第1章概述中引用的一个学生信息登记表 如表1 1所示 学生信息登记表可以是用户自定义的学生类型 在复杂的线性表中 常把数据元素称为记录 Record 它由若干个数据项 Item 组成 而含有大量记录的线性表又称为文件 File 2 1线性表的基本概念 3 线性表的特点 1 有且仅有一个开始结点 a1 它没有直接前驱 2 有且仅有一个终端结点 an 它没有直接后继 3 除了开始结点和终端结点以外 其余的结点都有且仅有一个直接前驱和一个直接后继 2 1线性表的基本概念 4 线性表的二元组表示线性表如果用二元组进行描述如下 Linearity D R 数据对象 D ai 1 i n n 0 数据关系 ai 1 ai D 1 i n 关系中是一个序偶的集合 它表示线性表中数据元素的相邻关系 即ai 1领先于ai 2 1线性表的基本概念 2 1 2线性表的基本操作线性表的基本操作如下 1 初始化线性表InitList L 2 求线性表的长度GetLength L 3 按位置查找操作GetElem L i x 4 按值查找操作Locate L x 5 插入操作InsElem L i x 6 删除操作DelElem L i x 7 显示操作DispList L 2 2线性表的顺序存储 2 2 1顺序表1 顺序表的定义数据结构在内存中的表示通常有两种形式 即顺序存储表示和链式存储表示 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素 我们把用这种存储形式存储的线性表称为顺序表 线性表的顺序存储表示又称为顺序表 顺序表的逻辑顺序和物理顺序是一致的 2 2线性表的顺序存储 假设顺序表 a1 a2 ai 1 ai ai 1 an 每个数据元素占用d个存储单元 则元素ai的存储位置为 Loc ai Loc a1 i 1 d1 i n其中 Loc a1 是顺序表第一个元素a1的存储位置 通称为顺序表的起始地址 顺序存储结构示意图如图2 1所示 2 2线性表的顺序存储 图2 1顺序存储结构示意图 2 2线性表的顺序存储 2 顺序表的存储特点 1 顺序表的逻辑顺序和物理顺序是一致的 2 顺序表中任意一个数据元素都可以随机存取 所以顺序表是一种随机存取的存储结构 2 2线性表的顺序存储 3 顺序表的类型定义 defineMAXLEN100 定义常量MAXLEN为100表示存储空间总量 typedefintDataType 定义DataType为int类型 typedefstruct 顺序表存储类型 DataTypedata MAXLEN 存放线性表的数组 intLength Length是顺序表的长度 SeqList SeqListL 定义一个顺序表L 2 2线性表的顺序存储 2 2 2顺序表的基本运算的实现1 顺序表的初始化顺序表的初始化即建立一个空表L 将L设为指针参数 将表L的实际长度置0 其算法描述如下 voidInitList SeqList L 初始化顺序表L函数 L Length 0 初始化顺序表为空 2 2线性表的顺序存储 2 顺序表的建立从键盘输入n个整数 并将这些整数存入顺序表中 修改表长后建立表L 算法描述如下 voidCreateList SeqList L intn 建立顺序表并输入多个元素函数 inti printf 请输入 d个整数 n for i 0 idata i L Length i 设线性表的长度为i 2 2线性表的顺序存储 3 查找操作顺序表的查找分为按值与按序号查找 1 按位置查找 查找顺序表中第i个位置元素的值 在i无效时返回出错 有效时返回成功 并用指针x所指的变量传回第i个元素的值 2 2线性表的顺序存储 算法描述如下 intGetElem SeqList L inti DataType x 获取顺序表中第i位中元素函数 if iL Length 当查找位置i不正确时 return0 else x L data i 1 将顺序表中第i个元素值赋给指针x所指变量 return1 2 2线性表的顺序存储 2 按值查找操作 顺序表中的按值查找是指在顺序表中查找与给定值x相等的数据元素的所在位置 首先令i等于0 然后从表的第一个位置开始查找值为x的元素 当i小于表长且该位置元素值不等于x时i自加 直到循环结束为止 判断i值 若i值大于表长则查找失败返回0 否则表示查找成功返回其位置i 1 因为C语言下标从0开始 所以位置值为下标值加1 算法描述如下 2 2线性表的顺序存储 intLocate SeqList L DataTypex 在顺序表L中定位元素x函数 inti 0 while iLength 返回的是元素位置 2 2线性表的顺序存储 4 插入操作线性表的插入是指在表的第i个位置上 因为C语言数组下标从0开始 所以插入位置下标为i 1 插入一个值为x的新元素 插入后使原表长增1 成为表的长度为n 1的表 顺序表插入结点的步骤如下 1 将ai an之间的所有结点依次后移 为新元素让出第i个位置 2 将新结点x插入到第i个位置 3 修改表长 顺序表插入元素的过程如图2 2所示 2 2线性表的顺序存储 图2 2顺序表插入元素的过程 2 2线性表的顺序存储 顺序表插入元素的算法如下所示 intInsElem SeqList L inti DataTypex 在顺序表L中在第i位中插入新元素x函数 intj if L Length MAXLEN printf 顺序表已满 return 1 表满 不能插入 if iL Length 1 检查给定的插入位置的正确性 printf 插入位置出错 return0 2 2线性表的顺序存储 if i L Length 1 插入的位置为表尾 则不需移动直接插入即可 L data i 1 x L Length return1 for j L Length 1 j i 1 j 插入表中某位置 则插入点后各结点后移 L data j 1 L data j L data i 1 x 新元素插入 L Length 顺序表长度增1 return1 插入成功 返回 2 2线性表的顺序存储 插入算法的时间性能分析 插入算法的基本操作是循环中的数据元素的后移 它出现在for循环中 该操作的执行次数取决于插入元素在线性表中的位序 设Ein为在长度为n的线性表中插入一元素时所需的平均移动次数 则 2 2线性表的顺序存储 5 删除操作线性表的删除操作是指将第i个元素 因为C语言数组下标从0开始 所以删除位置下标为i 1 从顺序表中去掉 删除后顺序表表长减1 顺序表删除元素的过程如图2 3所示 顺序表删除结点的步骤如下 1 将要删除的元素值赋给指针x所指的变量 2 将ai 1 an之间的结点依次顺序向前移动 3 顺序表的长度减1 删除成功 并返回 2 2线性表的顺序存储 图2 3顺序表删除示意图 2 2线性表的顺序存储 顺序表删除元素算法描述如下 intDelElem SeqList L inti DataType x 在顺序表L中删除第i位元素函数 intj if L Length 0 printf 顺序表为空 return0 表空 不能删除 if iL Length 检查是否空表及删除位置的合法性 printf 不存在第i个元素 return0 2 2线性表的顺序存储 x L data i 1 用指针变量 x返回删除的元素值 for j i jLength j 结点移动 L data j 1 L data j L Length 顺序表长度减1 return1 删除成功 返回 2 2线性表的顺序存储 与插入操作相似 设Edel为在长度为n的线性表中删除一元素时所需的平均移动次数 则 其时间主要消耗在了移动表中元素上 大约需要移动表中一半的元素 所以该算法的时间复杂度为 n 2 2线性表的顺序存储 6 输出表中元素操作从头至尾扫描顺序表L 输出表中各元素的值 算法描述如下 voidDispList SeqList L 显示输出顺序表L的每个元素函数 inti for i 0 iLength i printf 5d L data i 2 2线性表的顺序存储 7 显示菜单函数为了在主函数反复执行以上顺序表的各操作函数 我们在主函数中用循环语句实现此功能 并设计了一个菜单显示各功能选项 用函数Menu表示 其算法描述如下 2 2线性表的顺序存储 voidMenu 显示菜单子函数 printf n顺序表的各种操作 printf n printf n 1 建立顺序表 printf n 2 插入元素 printf n 3 删除元素 printf n 4 按位置查找元素 printf n 5 按元素值查找其在表中位置 printf n 6 求顺序表的长度 printf n 0 返回 printf n printf n请输入菜单号 0 6 2 3线性表的链式存储 2 3 1单链表1 单链表的定义每个数据元素不仅要表示它的具体内容 还要附加一个表示它的直接后继元素存储位置的信息 这样构成的链表称为线性单向链接表 简称单链表 其结点结构如图2 4所示 2 3线性表的链式存储 其中 data部分称为数据域 用于存储一个数据元素 结点Linknode 的信息 next部分称为指针域 用于存储其直接后继的存储地址的信息 单链表分为带头结点 其next域指向链表第一个结点的存储地址 和不带头结点两种类型 2 3线性表的链式存储 通常用 头指针 来标示一个线性链表 如头指针head是指某链表第一个结点的地址放到了指针变量head中 带头结点的链表的头结点的指针域为 NULL 则表示一个空表 由于单向链表不能随机存取存储的数据元素 在单向链表中存取第i个元素 必须从头指针出发寻找 其寻找的时间复杂度为O n 2 3线性表的链式存储 2 单链表的类型定义单链表由一个个结点构成 我们用C语言的结构体指针来描述 typedefintDataType 定义DataType为int类型 typedefstructlinknode 单链表存储类型 DataTypedata 定义结点的数据域 structlinknode next 定义结点的指针域 LinkList 2 3线性表的链式存储 如果想定义一个指向该结点类型的指针head C语言中的语句如下 LinkList head 如果想动态申请一个结点空间 并让指针head指向该结点空间 语句如下 head LinkList malloc sizeof LinkList 这样 head指针就指向该结点了 则这个结点的数据域为head data或是 head data 而指针域为head next或 head next C语言中释放指针head所指结点空间的语句为 free head 2 3线性表的链式存储 2 3 2单链表的基本操作实现1 单链表的初始化单链表的初始化即构造一个仅包含头结点的空单链表 其过程是首先申请一个结点并让指针head指向该结点 然后将它的指针域赋为空 NULL 最后返回头指针head 其算法描述如下 2 3线性表的链式存储 LinkList InitList 初始化链表函数 LinkList head head LinkList malloc sizeof LinkList 动态分配一个结点空间 head next NULL returnhead 头结点L指针域为空 表示空链表 2 3线性表的链式存储 2 单链表的建立 1 头插法建表 链表与顺序表不同 它是一种动态管理的存储结构 链表中的每个结点占用的存储空间不是预先分配 而是运行时系统根据需求生成的 因此 建立在初始化链表后 建立线性链表从空表开始 每读入有效的数据则申请一个结点s 并将读取的数据存放到新结点s的数据域中 然后将新结点插入到当前链表head的表头上 直到循环结束为止 其算法描述如下 2 3线性表的链式存储 voidCreateListH LinkList head intn 头插法建立链表函数 LinkList s inti printf 请输入 d个整数 n for i 0 idata 读入新结点的数据域 s next head next 将新结点的指针域存放头结点的指针域 head next s 将新结点插入头结点之后 printf 建立链表操作成功 2 3线性表的链式存储 2 尾插法建表 头插法建立链表虽然算法简单易理解 但生成的链表中结点的次序和原输入的次序相反 而尾插法建立链表可实现次序的一致 该算法依旧从空表开始 但需增加一个尾指针last 使其指向当前链表的尾结点 其过程是 每读入有效的数据则申请一个结点s 并将读取的数据存放到新结点s的数据域中 将s的尾指针设为空指针 NULL 然后将新结点插入到当前链表尾部 last指针所指的结点后面 直到循环结束为止 其算法描述如下 2 3线性表的链式存储 voidCreateListL LinkList head intn 尾插法建立链表函数 LinkList s last inti last head last始终指向尾结点 开始时指向头结点 printf 请输入 d个整数 n for i 0 idata 读入新结点的数据域 s next NULL 将新结点的指针域为空 last next s 将新结点插入表尾 last s 将last指针指向表尾结点 printf 建立链表操作成功 2 3线性表的链式存储 3 求表长操作因为链表是链式结构 所以链表中元素个数不是已知的 想求表中元素个数还要设一个计数变量j 初值为0 将一个指针p先指向链表中第一个元素 当p不为空时 循环将p指针后移 j加1 循环结束后j值即为链表长度 其算法描述如下 2 3线性表的链式存储 intLengthList LinkList head 求链表长度函数 LinkList p head next intj 0 while p NULL 当p不指向链表尾时 p p next j returnj 2 3线性表的链式存储 4 查找操作单链表的查找分为按值与按序号查找 下面将分别介绍这两种方法的实现 读者可根据具体的问题相应选择所需的查找方法 1 按值查找 算法思路 从链表的第一个元素结点开始 由前向后依次比较单链表中各结点数据域中的值 若某结点数据域中的值与给定的值x相等 则循环结束 否则继续向后比较直到表结束 然后判断指针p 若p不为空表示单链表中有x结点 输出查找成功的信息并输出x所在表中的位置 否则输出查找失败的信息 其算法描述如下 2 3线性表的链式存储 voidLocate LinkList head DataTypex 在链表中查找值为x的元素位置 intj 1 计数器 LinkList p p head next while p NULL 2 3线性表的链式存储 2 按序号查找 算法思路 首先判断i值是否大于表长 如果大于则输出位置错误信息 否则从链表的头结点开始 判断当前结点序号是否是i 成立则提前结束循环 最后输出第i位上的结点的数据域值和位置i 其算法描述如下 2 3线性表的链式存储 voidSearchList LinkList head inti 在链表中按位置查找元素 LinkList p intj 0 p head p指向链表的头结点 if i LengthList head printf 位置错误 链表中没有该位置 while p next NULL 2 3线性表的链式存储 5 插入操作顺序表的插入操作需要移动大量的数据元素 而链表的插入只需修改指针而无须移动原来表中元素 那链表的插入操作是如何实现呢 1 在指针所指的结点后插入新结点 若要在链表中指针p所指位置后面插入一个结点 则插入操作步骤如下 先将结点s的指针域指向结点p的下一个结点 执行语句s next p next 再将结点p的指针域改为指向新结点s 执行语句p next s 插入结点的过程如图2 6所示 2 3线性表的链式存储 图2 6在结点p之后插入结点s 2 3线性表的链式存储 2 插入算法思路 在第i个位置插入新结点s的算法思路如下 由于单链表的结点结构是单向后指的 因此要完成此操作需要找到第i结点的前驱结点即第i 1结点的指针p 然后在已知结点p后方插入新结点即可 其算法描述如下 2 3线性表的链式存储 voidInsList LinkList head inti DataTypex 按位置插入元素函数 intj 0 LinkList p s p head while p next NULL 2 3线性表的链式存储 if p NULL p不为空则将新结点插到p后 s LinkList malloc sizeof LinkList 生成新结点s s data x 将数据x放入新结点的数据域 s next p next 将新结点s的指针域与p结点后面元素相连 p next s 将p与新结点s链接 printf 插入元素成功 elseprintf 插入元素失败 2 3线性表的链式存储 6 删除操作首先通过循环定位求出第i结点的前驱结点 第i 1结点 p的地址 然后将指针s指向被删除结点 修改p next指针 使其指向s后的结点 最后释放指针s所指结点 算法中注意if p next NULL j i 1 语句 只有当第i 1结点存在 j i 1 而p又不是终端结点即 p next NULL 时 才能确定被删除结点存在 删除结点的过程如图2 7所示 2 3线性表的链式存储 图2 7在结点p之后删除结点s 2 3线性表的链式存储 其算法描述如下 voidDelList LinkList head inti 按位置删除链表中元素函数 intj 0 DataTypex LinkList p head s while p next NULL 2 3线性表的链式存储 if p next NULL 2 3线性表的链式存储 7 单链表的输出操作扫描单链表 输出各元素的值 其算法描述如下 voidDispList LinkList head 显示输出链表函数 LinkList p p head next p指针指向链表第一个结点 while p NULL 当p指针不为空时输出链表每个数据域值 printf 5d p data p p next 2 3线性表的链式存储 2 3 3循环链表1 循环链表循环链表 CircularLinkedList 是单链表的另一种形式 对于单链表而言 最后一个结点的指针域为空 如果将该链表中最后一个结点的指针域指向头结点 整个链表形成一个环 就构成了循环单链表 带头结点的循环单链表如图2 8所示 循环链表的基本操作的实现和单链表的基本一致 差别仅在于判别链表中最后一个结点的条件不再是 后继是否为空 p NULL或p next NULL 而是 后继是否为头结点 p head或p next head 2 3线性表的链式存储 图2 8带头结点的循环单链表 a 带头结点的空单循环链表 2 3线性表的链式存储 2 循环链表上的操作循环单链表中从任意一个结点出发均可找到链表中其他所有结点 在许多实际问题中 链表的插入和删除等操作主要发生在表的首尾两端 此时如果再采用图2 8所示的循环单链表显得不够方便 主要不利于查找尾结点 如果改变原来的循环单链表指针 用尾指针rear来指向链表最后一个结点 操作就会方便很多 改过的循环单链表如图2 9所示 这样查找终端结点和头结点都很方便 它们的存储地址分别是rear和rear next next指向 因此通常采用尾指针rear来表示循环单链表 2 3线性表的链式存储 图2 9用尾指针rear表示的循环单链表的一般形式 2 3线性表的链式存储 其算法如下 LinkList prior LinkList p 循环单链表查找结点前驱函数 LinkList q q p next while q next p q q next return q 2 3线性表的链式存储 2 3 4双向链表1 双向链表的定义图2 10双向链表的结点示意图在单链表结点中只有一个指向直接后继的指针域next 这样从某个结点出发只能顺指针方向寻找它的后继结点 若要寻找结点的直接前驱 则需从头指针出发查找前驱 若希望能够快速查找一个结点的直接前驱 则可以再增加一个指向其直接前驱的指针域prior 这样就构成了双向链接表 简称双向链表 其结点结构如图2 10所示 图2 10双向链表的结点示意图 2 3线性表的链式存储 双向链表用的结点结构用C语言描述如下 typedefcharDataType 定义DataType为char类型 typedefstructdunode 双向链表存储类型 DataTypedata 定义结点的数据域 structdunode prior 定义结点的前驱指针域 structdunode next 定义结点的后继指针域 DuLinkList 2 3线性表的链式存储 为了使算法对所有的结点处理可一致化 与单链表一样 本节讨论的双向链表均指带头结点的双向链表 如图2 11 a 所示是带头结点的非空双向循环链表 如图2 11 b 所示是带头结点的空双向循环链表 2 3线性表的链式存储 2 双向链表的基本运算 1 在双向链表中p指针指向的结点前插入新结点s操作 先创建一个以x为值的新结点s 在p结点之前插入结点s 则插入操作步骤如下 将结点s的prior域指向结点p的前一个结点 执行语句s prior p prior 将结点p的前一个结点的next域指向结点s 执行语句p prior next s 将结点s的next域指向p结点 执行语句s next p 将结点p的prior域指向结点s 执行语句p prior s 插入结点的过程如图2 12所示 2 3线性表的链式存储 图2 12在结点p之前插入结点s 2 3线性表的链式存储 双向循环链表的结点插入算法如下 voidDuIns Elem DuLinkList p DataTypex 双向循环链表的插入结点函数 DuLinkList s s DuLinkList malloc sizeof DuLinkList 生成新结点s s data x s prior p prior 对应图2 12中的 p prior next s 对应图2 12中的 s next p 对应图2 12中的 p prior s 对应图2 12中的 2 3线性表的链式存储 2 在双向链表中删除p指针指向的结点操作 先保证删除位置的正确性 在双向链表上找到删除位置结点地址 由p指向 先将结点p中的数据域中的值赋给指针变量 x 则删除操作步骤如下 将结点p前一个结点的next域指向结点p的next域 执行语句 p prior next p next 将结点p后一个结点的prior域指向结点p的prior域 执行语句 p next prior p prior 释放结点p空间 执行语句 free p 2 3线性表的链式存储 删除结点的过程如图2 13所示 图2 13删除结点p示意图 2 3线性表的链式存储 双向循环链表的结点删除算法如下 voidDuDel Elem DuLinkList p DataType x 双向循环链表的删除结点函数 x p data p prior next p next 对应图2 16中的a p next prior p prior 对应图2 16中的b free p 2 4顺序表与链表的比较 本章介绍了线性表的两种存储结构 顺序表和链表 顺序存储有如下优点 1 方法简单 高级语言都提供数组 实现容易 2 无须为表示线性表中元素的逻辑关系而额外增加存储开销 3 具有按元素序号随机访问的特点 2 4顺序表与链表的比较 顺序存储的缺点如下 1 在顺序表中进行插入 删除操作时 需要顺序移动元素 平均移动次数是线性表长度的一半 因此对长度较大的线性表操作效率较低 2 要预先分配足够大的存储空间 空间分配过大会造成浪费 过小又有可能导致一些操作 如插入 失败 顺序表的优点就是链表的缺点 而其缺点就是链表的优点 2 4顺序表与链表的比较 在实际使用中空间采用什么存储结构呢 通常考虑以下3个方面 1 基于空间的考虑当线性表长度变化不大 易于事先确定其大小时 为了节约存储空间 宜采用顺序表作为存储结构 当线性表的长度变化较大 事先难以确定期限大小时 应采用链表存储结构 2 基于时间的考虑基线性表的操作主要是进行查找 很少进行插入和删除时 采用顺序表为存储结构较好 对于频繁进行插入和删除的线性表 采用链表较好 3 基于语言的考虑各种高级语言都提供有数组 但不一定提供指针 链表是基于指针的 所以链表的使用受高级语言的限制 2 5线性表的应用举例 约瑟夫环问题 2 5 1问题描述图2 14约瑟夫环问题流程图约瑟夫环问题的一种描述是 编号为1 2 n的n个人按顺时针方向围坐一圈 每人持有一个密码 正整数 一开始任选一个正整数作为报数上限值m 从第一个人开始按顺时针方向自1开始顺序报数 报到m时停止报数 报m的人出列 将它的密码作为新的m值 从它的顺时针方向的下一个人开始重新从1报数 如此下去 直至全部人出列为止 最后按照出列的顺序输出各人的编号 2 5线性表的应用举例 约瑟夫环问题 2 5 2数据结构其主要的数据类型为无头结点的单向循环链表 如下 typedefstructNode intdata 存储人数 intpassword 存储的每人所对应的密码 structNode next LinkList 2 5线性表的应用举例 约瑟夫环问题 2 5 3程序流程1 主要模块的流程图本程序的流程图如图2 14所示 2 5线性表的应用举例 约瑟夫环问题 2 主要函数 1 构建单链表函数CreatList 2 初始化一个单循环链表函数InitList 3 确定需要处理的人数函数 GetPersonNumber 4 给每个人赋密码函数 GetPassword 5 确定开始的上限值函数 GetFirstCountValue 6 得到出队顺序GetOutputOrder 7 输出结果printResult 8 主函数main 小结 1 线性表是一种最简单的数据结构 数据元素之间存在着一对一的关系 其存储方法通常采用顺序存储和链式存储 2 线性表的顺序存储可以采用结构体的形式 它含有两个域 一个整型的长度域 用以存放表中元素的个数 另一个数据域 用来存放元素 其类型可以根据需要而定 顺序存储的最大优点是可以随机存取 且存储空间比较节约 而缺点是表的扩充困难 插入 删除要做大量的元素移动 3 线性表的链式存储是通过结点之间的链接而得到的 根据链接方式又可以分为单链表 双链表和循环链表等 小结 4 单链表有一个数据域 data 和一个指针域 next 组成 数据域用来存放结点的信息 指针域存放表中下一个结点的地址 在单链表中 只能从某个结点出发找它的后继结点 单链表最大的优点是表的扩充容易 插入和删除操作方便 而缺点是存储空间比较浪费 5 双链表有一个数据域 data 和两个指针域 prior和next 组成 它的优点是既能找到结点的前趋 又能找到结点的后继 6 循环链表使最后一个结点的指针指向头结点 或开始结点 的地址 形成一个首尾链接的环 利用循环链表将使某些运算比单链表更方便 习题2 一 选择题1 下面关于线性表的叙述中 错误的是 A 线性表采用顺序存储 必须占用一片连续的存储单元 B 线性表采用顺序存储 便于进行插入和删除操作 C 线性表采用链接存储 不必占用一片连续的存储单元 D 线性表采用链接存储 便于插入和删除操作 2 在有n个结点的顺序表上做插入 删除结点运算的时间复杂度为 A O 1 B O n C O n2 D O log2n 习题2 3 两个指针P和Q 分别指向单链表的两个元素 P所指元素是Q所指元素前驱的条件是 A P next Q nextB P next QC Q next PD P Q4 在单链表中 增加头结点的目的是 A 使单链表至少有一个结点B 标志表中首结点的位置C 方便运算的实现D 说明该单链表是线性表的链式存储结构5 在顺序表中 只要知道 就可以求出任意一个结点的存储地址 A 基地址B 结点大小C 向量大小D 基地址和结点大小 习题2 6 链表不具备的特点是 A 随机访问B 不必事先估计存储空间C 插入删除时不需移动元素D 所需空间与线性表成正比7 在 的运算中 使用顺序表比链表好 A 插入B 根据序号查找C 删除D 根据元素查找8 在单链表指针为p的结点之