第2章 线性表

第2章线性表 2 1线性表的基本概念2 2线性表的顺序实现2 3线性表的链接实现单链表及单链表上的运算循环链表 双链表 静态链表2 4顺序表和链表的比较 2 1线性表的基本概念 学生成绩登记表 姓名 英语 数据结构 高数 学号 丁一 96 78 87 0101 李二 87 90 78 0102 张三 67 86 86 0103 孙红 69 81 96 0104 王冬 87 74 66 0105 数据元素之间的关系是什么 线性表 LinearList n n 0 个数据元素a1 a2 an组成的有限序列 一般记作L a1 a2 an 其中 L为线性表的名字 数据元素的个数n定义为表的长度 当n 0时称为空表 记作 或 一般要求元素的类型相同 图形表示二元组表示L 其中D a1 a2 a3 an S R R 一 定义 例1 数列 11 13 15 17 19 21 例2 英文字母表 A B C D E Z 线性 第一个元素无前趋 最后一个元素无后继 其它每个元素有且仅有一个直接前趋和一个直接后继 二 逻辑结构 线性表的特性 有限性 线性表中数据元素的个数是有穷的 相同性 线性表中数据元素的类型是同一的 顺序性 线性表中相邻的数据元素ai 1和ai之间存在序偶关系 ai 1 ai 即ai 1是ai的前驱 ai是ai 1的后继 a1无前驱 an无后继 其它每个元素有且仅有一个前驱和一个后继 1 初始化INITIATE L 建一空表 之后其它操作才能进行 2 求表长LENGTH L 线性表中的结点个数3 读表元 按序号找 GET L i 得到值或地址 4 定位 按值找 LOCATE L x 得到序号或地址 5 插入INSERT L x i L的第i个位置插入值为x的结点6 删除DELETE L i 删除L的第i个结点7 排序 实际问题中基本运算的种类和个数可能不同 非基本运算 修改第i个元素SET L i x 求前趋PRIOR L x 和后继NEXT L x 判空EMPTY L 合并MERGE L L1 L2 和拆分SPLIT L i L1 L2 等 三 基本运算 四 存储结构 1 顺序存储 顺序表2 链式存储 链表 五 线性表的抽象数据类型定义 一 ADTListData线性表中的数据元素具有相同类型 相邻元素具有前驱和后继关系OperationInitList前置条件 表不存在输入 无功能 表的初始化输出 无后置条件 建一个空表DestroyList前置条件 表已存在输入 无功能 销毁表输出 无后置条件 释放表所占用的存储空间 五 线性表的抽象数据类型定义 二 Length前置条件 表已存在输入 无功能 求表的长度输出 表中数据元素的个数后置条件 表不变Get前置条件 表已存在输入 元素的序号i功能 在表中取序号为i的数据元素输出 若i合法 返回序号为i的元素值 否则抛出异常后置条件 表不变Locate前置条件 表已存在输入 数据元素x功能 在线性表中查找值等于x的元素输出 若查找成功 返回x在表中的序号 否则返回0后置条件 表不变 五 线性表的抽象数据类型定义 三 Insert前置条件 表已存在输入 插入i 待插x功能 在表的第i个位置处插入一个新元素x输出 若插入不成功 抛出异常后置条件 若插入成功 表中增加一个新元素Delete前置条件 表已存在输入 删除位置i功能 删除表中的第i个元素输出 若删除成功 返回被删元素 否则抛出异常后置条件 若删除成功 表中减少一个元素Empty前置条件 表已存在输入 无功能 判断表是否为空输出 若是空表 返回1 否则返回0后置条件 表不变ADT 顺序表 SequentialList 用顺序存储的线性表 即把线性表的结点按逻辑次序依次存放到一组地址连续的存储单元里 存储顺序反映逻辑关系 随机存取 Loc i Loc 1 i 1 c 2 2线性表的顺序实现 typedefintdatatype 结点的数据类型 假设为intconstintmaxsize 100 最大表长度 假设为100typedefstruct datatypedata maxsize 第一个结点是data 0 intn 当前长度 sqlist 顺序表类型 1 data 数组 结点ai在数组元素data i 1 中 2 n 表长 终端结点的下标为n 1 3 datatype 结点类型 视实际情况而定 4 sq1ist 顺序表类型 结构 有关信息封装一起作整体 用一个名字表示 访问细节时 成员选择 指针指向运算符 例 sqlist L L data i L n sqlistL L data i L n 在表的第i 1 i n 1 个位置上 插入一个新结点x 使长度为n的线性表 a1 ai 1 ai an 变为长度为n l的线性表 a1 ai 1 x ai an 1 插入 先将表中位置i n上的结点全部后移一位以空出第i个位置 然后在该位置上插入新结点x 最后表长加1 注 移动只能从后向前进行 即按n n 1 i的次序进行 intinsert sqlist L datatypex inti 将x插入到顺序表L的第i个位置上intj if L n maxsize coutL n 1 coutn j i j L data j L data j 1 结点后移L data i 1 x 插入x 第i个结点的数组下标是i 1L n 修改表长return1 插入成功 比较 参数取顺序表指针 顺序表值 移动次数Ci n i 1 最少 0 i n 1 最多 n i 1 设Pi 1 n 1 平均 加权平均 例某2天内 1天16 1天18 平均多少 例某10天内 5天15 2天17 3天20 平均多少 2 删除 将表的第i 1 i n 个结点删去 使长度为n的线性表 a1 ai 1 ai ai 1 an 变为长度为n 1的线性表 a1 ai 1 ai 1 an 先将表中位置i 1 n上的结点全部前移一位以填补删除操作造成的空缺 最后表长减1 注意 移动只能从前向后进行 即按i 1 i 2 n的次序进行 intdelete sqlist L inti 从顺序表中删除第i个位置上的结点intj if L n 0 coutL n coutn j L data j 2 L data j 1 结点前移L n 修改表长return1 删除成功 移动次数为Ci n i 最少0次 i n时 最多n 1次 i 1时 设Pi 1 n 平均 3 定位 求表L中第一个值为x的结点的序号 当不存在这种结点时结果为0 因此可从前向后比较各结点的值是否等于x intlocate sqlist L datatypex inti i 1 while in 未找到 比较次数 平均复杂度为O n 例 交替扫描 方法1 对顺序表从前向后搜索 或称扫描 遇到正值结点就将它插入到表的后部 或从后向前搜索 遇到负值结点就将它插入到表的前部 但顺序表上插入或删除不方便 要移动大量结点 效率不高 例已知顺序表结点有正有负 使负值结点位于顺序表的前面部分 正值结点位于顺序表的后面部分 方法2 由表的两端向中间交替扫描 即先从前向后扫描 找到一个值为正的结点 再从后向前扫描 找到一个值为负的结点 然后交换两者的内容 接着再从这两个位置开始继续进行同样的过程 直到两个扫描方向相遇 整个表扫描处理完毕 这样就避免了大量结点的移动问题 voidorder sqlist L datatypex inti j i 0 j L n 1 while idata i data j 0 j 从后向前扫描if idata i L data i L data j L data j x i j 例 删多个元素 方法1 每找到一个待删点 就将其后所有点前移一位 若有多个待删点 后面的点要移动多次 移动量大 最坏O n2 方法2 对每一个零元 用尾部的非零元与其交换 这可采用前后交替扫描的方法 每结点最多移动1次 O n 但会改变非零元的相对位置 方法3 每找到一个零元 并不马上删除 而是累计当前零元数s 于是 对每一个非零元 将其前移s个位置 每结点最多移动1次 O n 例将顺序表中的所有零元素删除 voidpurge sqlist L inti s s 0 for i 0 in i if L data i 0 s 累计零点数elseif s 0 L data i s L data i 非零点前移s位 L n L n s 调整表长 例 删多个元素 voidintersection sqlist A sqlist B intm n i k n length A m length B for i 0 in elsei 例 集合交 改进 不必每找到一个就在A中删除 可先做删除标记 以后集中删除 思考题 一个顺序表中存放字符 只有数字字符和英文字符 编写算法删除所有的数字字符编写算法 实现顺序表的建立 要求建立的顺序表中元素按照从小到大顺序排列 且顺序表中不能有重复的元素顺序存储的线性表A 其数据元素为整型 试编写一算法 将A拆成B和C两个表 使A中元素值大于等于0的元素放入B 小于0的放入C中 要求 1 表B和C另外设置存储空间 2 表B和C不另外设置 而利用A的空间 小结 链表 LinkedList 用链式存储的线性表 即用一组任意的存储单元存储线性表的各个数据元素 相互间的逻辑关系 前趋或后继 通过附加指针表示 所有结点通过指针域链接在一起 构成一个链表 元素之间的逻辑关系通过附加指针表示 结点可以连续 可以不连续 结点的逻辑顺序与物理顺序可以不一致 2 3线性表的链接实现 链表分类链表总空间的构成特点 动态链表 静态链表指针链接方式 单链表 循环链表和双链表 链表 线性表的链接存储结构 存储思想 用一组任意的存储单元存放线性表的元素 顺序表和链表的比较 单链表 SinglyLinkedList 每个结点有两部分信息 数据域 存放结点的值 内容 指针域 亦称链域 存放结点后继的地址 或位置 由于每个结点只有一个链域 故得名 存储元素值 存储后继地址 2 3 1单链表 存储地址 数据域 指针域 空指针 不指向任何结点 常用NULL或 表示 头指针 单链表第一个结点的地址 单链表由头指针唯一确定 头指针具有标识单链表的作用 单链表可用头指针命名 如head表 头结点 单链表第一个结点前人为增加的结点 不存放数据 作用 简化链表操作 统一空表与非空表有时可将头结点看成0号结点 头指针 空指针 头结点 尾结点 首结点 typedefchardatatype 结点数据类型 假设为chartypedefstructnode pointer 结点指针类型structnode 结点结构datatypedata pointernext typedefpointerlklist 单链表类型 即头指针类型 1 pointer 指针类型 即structnode 指向structnode型变量常见错误 未初始化 未赋值就使用2 structnode 结构 data 数据域 next 链域 3 lklist pointer类型 名字不同 lklist说明头指针 表示单链表 pointer说明一般结点 包括工作结点 比较 lklistA pointerA 同一类型取不同名字可说明类型相同 作用不同的变量 即把类型赋予一定的 语义 有利于提高程序的可读性 4 访问指针所指对象成员 P data p data 动态分配与释放 p newnode deletep NULL pointerp 2 3 2单链表上的运算 建表 尾插法 头插法初始化求表长按序号查找定位 按值查找 插入运算删除运算单链表例题讲解与总结 an s rear s 从空表开始 反复读入数据 生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的尾端直到读入结束符为止 s newnode s data ch rear next s rear s rear x x 1 建表 尾插法 例 依次输入A B C 尾插法建表 有头结点 A C B s newnode s data ch rear next s rear s lklistcreat 尾插法建表 有头结点pointerhead rear s charch head newnode 生成头结点rear head 尾指针初值while cin ch ch 读入并检测结束s newnode s data ch 生成新结点rear next s rear s 插入表尾 改尾指针 rear next NULL 尾结点的后继为空returnhead 1 建表 头插法 a1 head x s head x s 从空表开始 反复读入数据 生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端直到读入结束符为止 s newnode s data ch s next head next head next s 例 依次输入A B C 头插法建表 有头结点 A C B s newnode s data ch s next head next head next s lklistcreat 头插法建表 有头结点lklisthead pointers charch head newnode 生成头结点head next NULL while cin ch ch 输入并检测结束s newnode 生成新结点s data ch 装入数据s next head next head next s 插到头结点后 returnhead 2 初始化 head lklistinitlist pointerhead head newnode head next NULL returnhead 建立一个只有头结点的空表 3 求表长 head a1 a2 a3 j 1 j 2 j 3 j 0 NULL intlength lklistL intj pointerp j 0 p L next 从首结点开始while p NULL 逐点检测 计数j p p next returnj 3 求表长 head a1 a2 a3 j 1 j 2 j 3 j 0 NULL intlength lklistL intj pointerp j 0 p L next 从首结点开始while p NULL 逐点检测 计数j p p next returnj 链表运算特点 从前向后搜索 扫描 p p next pointerget lklisthead inti 0 i nintj pointerp if inext 未到第i点 继续 returnp 含找到 未找到两种情况 4 按序号查找 注意 头结点看成第0号结点 5 定位 按值查找 返回结点指针 注意 返回结点的地址 pointerlocate lklisthead datatypex pointerp p head next 从首结点开始搜索while p NULL if p data x break p p next 到下一个点 returnp 含找到 未找到两种情况 intlocate lklisthead datatypex intj pointerp j 0 计数器p head next 从首结点开始扫描while p NULL j if p data x break 找到 退出p p next 没找到 继续 if p NULL returnj 找到xelsereturn 1 没有x 查找失败 注意 返回结点号 没有返回 1 头结点视为0号 5 定位 按值查找 返回序号 6 插入一 无头结点 略 B A x 插入到任意结点后 不分空表 首结点前 还是中间结点后 尾结点后 统一处理 p s newnode s data x s next p next p next s 6 插入二 有头结点 1 查找第i 1个结点 2 建立新结点 3 修改第i 1个结点和新结点的指针 插入到第i结点前 不需移动结点 只需修改有关指针需从表头开始顺序查找插入位置 intinsert lklisthead datatypex inti pointerq s q get head i 1 找第i 1个点if q NULL 无第i 1点 即in 1时 coutdata x s next q next 新点的后继是原第i个点q next s 原第i 1个点的后继是新点return1 插入成功 等效插入 已知当前点位置 前插 略 不找前趋前插 新结点插在当前点 p后交换两结点内容逻辑上与原来在 p之前插入等效 1 s newnode 2 s data p data 3 s next p next 4 p data x 5 p next s 7 删除一 无头结点 略 q A C NULL p q next p next deletep 删除任意结点 不分首结点 还是中间结点 尾结点 统一处理 7 删除二 有头结点 删除第i结点 1 查找链表的第i 1个结点 设q指向它 p指向第i个结点 2 修改第i 1个结点的后继指针 使其指向第i个结点的后继 3 释放第i个结点空间 intdelete lklisthead inti pointerp q q get head i 1 找待删点的直接前趋if q NULL q next NULL 即in时 coutnext 保存待删点地址q next p next 修改前趋的后继指针deletep 释放结点return1 删除成功 等效删除 已知当前点位置 自删 略 不找前趋删除当前点 当前点 p后继的值复制到当前结点中删当前结点的后继逻辑上与原来删 p等效 但要求 p有后继 即不能是终端结点 1 q p next 2 p data q data 3 p next q next 4 deleteq head p head head p p head a1 a2 a2 a3 a3 a3 例删除所有表结点 示意 voiddestory lklistL 删除所有结点pointerp q p L while p NULL q p next 保存待删点后继deletep 释放空间p q L NULL 头指针置空 L a2 a3 例1单链表销毁 a1 例3单链表逆置 略 对每个结点 p 将其next改指其前趋 q 修改 p的next后 将不能从 p搜索到其后继 所以修改前先将其后继 r的位置保留起来 原首结点成为尾结点 其next应为NULL 为使该结点的处理与其它结点一致 可在算法开始时将其前趋置为NULL而不是head 头结点的next指向原尾结点 voidreverse lklisthead pointerp q r q NULL 首结点的前趋p head next while p NULL r p next p next q q p p r head next q 原尾结点成为首结点 3 5 A 1 7 3 9 例3链表合并 原理 将两表当前结点中较小的尾插到新表 将两个递增有序线性链表归并成一个递增有序表 若要求就地进行如何 C lklistpurge lklistA lklistB pointerC p q r p A next q B next C A r C 取A头结点作C头结点while p NULL 习题 写一个函数 实现单链表的Display运算 输出单链表中所有结点的数据元素值 删除单链表中结点的值在low和high之间的结点 若存在这样的结点 小结 单链表的特点1通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系 2插入删除操作通过修改结点的指针实现 3不能随机存取元素 循环链表 CircularLinkedList 是一种首尾相接的链表 其特点是无需增加存储量 仅对表的链接方式稍作改变 就可使表的处理更加方便灵活 2 3 3循环链表 first a1 ai 1 an ai 从单链表中某结点p出发如何找到其前驱 单循环链表 从任一结点出发可访问到其它所有结点有时不给头指针 而给尾指针rear 尾结点 rear头结点 rear next首结点 rear next next 单链表中 将尾结点的指针域由NULL改为指向头结点或首结点 例 按值查找 pointerlocate lklistL datatyex pointerp p L next while p L 注意 结束条件不是p NULL而是p L 习题 写一个函数 实现单循环链表的求表长Length运算 例多项式的表示 structnode intco 系数intexp 指数structnode next 只存非零系数 各系数组成链表 每结点三部分信息 系数值 指数和后继指针运算中首尾项可能变化 为方便起见 采用循环链表 多项式相加 A 1 3x6 7x12B x4 3x6 9x10 8x14 C 10 14 712 814 910 first a1 ai 1 an ai 从单循环链表中某结点p出发 找到其前驱 需要访问多少个结点 如何改进 存储元素值 存储后继地址 存储前趋地址 双 向 链表 DoublyLinkedList 每个结点有两个指针域 一个指向直接后继 一个指向直接前趋 找前趋 后继都方便 2 3 4双链表 双 向 链表 DoublyLinkedList 类型定义 2 3 4双链表 typedefintdatatype 结点数据类型 假设为inttypedefstructdnode dpointer 结点指针类型structdnode 结点结构datatypedata dpointerprior dpointernext typedefdpointerdlklist 双链表类型 即头指针类型 双循环链表 双循环链表 双向链表中 把表尾结点的右指针域 next域 指向表头结点 把表头结点的左指针域 prior域 指向表尾结点 形成双循环链表 对称性p prior next p p next prior 前插 s newnode s data x s next p s prior p prior p prior next s p prior s A B x P 自删 p prior next p next p next prior p prior deletep a c p NULL 初始化 建立空双循环链表 仅有头结点 dlklistcreat dpointerhead head newdnode head prior head next head returnhead 求长度 intlength dlklistL dpointerp intnum p L next num 0 while p L p p next num returnnum 也可沿前趋指针求 习题 写一个函数 实现双循环链表的定位 按值查找 Locate运算 intLocate dlklistL datatypex 试写出两个一元多项式相加的算法 静态链表 StaticLinkedList 通过数组下标实现的链表 由于数组空间要预先静态分配 故得名 数组空间也称存储池 原理 定义一个结构数组 每个结点存放两个信息 一个是结点本身的数据 一个是其后继的数组下标 申请结点时 从存储池内取一结点 释放结点时 归还到存储池内 2 3 5静态链表 constintmaxsize 100 存储池容量typedefintdatatype 结点数据类型inttypedefintcursor 游标类型constcursorNIL 1 静态链表空指针typedefstruct datatypedata 数据域cursornext 指针域 snode 结点类型snodenodepool maxsize 存储池cursorsp 游标变量 1 初始化 将存储池所有结点链成一个可用空间表或备用空间表 头指针设为sp 类型是cursor 在结点分配和回收中要使用sp 为了避免参数的频繁传递 将sp设为全局量 1 初始化 voidinitialize inti for i 0 i maxsize 1 i 结点依次链接nodepool i next i 1 nodepool maxsize 1 next NIL 尾结点sp 0 结点分配和回收 分配结点 从表sp上取第一个结点 并在sp中删除该结点 voiddeletenode cursorp nodepool p next sp sp p 结点插到sp的前面 归还结点 将结点插入到表sp的头上 cursornewnode cursorp if sp NIL returnNIL 分配失败p sp p指向分配到的结点sp nodepool sp next 从sp表上删除分配走的结点returnp 返回分配到的结点 2 按序号查找 cursorget cursorL inti intj cursorp if i 0 returnNIL 参数不合理j 1 p L 从头结点开始while p NIL 顺序查找第i结点j if j i break p nodepool p next returnp 注意 头结点看成第0号结点 向后搜索语句 p nodepool p next 3 按值查找 注意 返回结点的地址 cursorlocate cursorL datatypex cursorp p nodepool L next 从首结点开始搜索while p NIL if nodepool p data x break p nodepool p next 到下一个点 returnp 4 第i点前插入 intinsert cursorL datatypex inti cursorp s p get L i 1 找ai前趋if p NIL cout 插入位置非法 n return 1 s newnode if s NIL cout 空间已满 不能插入 n return0 nodepool s data x 插入结点xnodepool s next nodepool p next no