数据结构线性表入门.ppt

2020 3 26 算法与数据结构AlgorithmsandDataStructuresCH2线性表 教授 信息技术大学计算机工程学院 2 1基本概念与ADT2 2顺序表示2 3链接表示2 4应用举例2 5矩阵2 6广义表与动态存储管理 提纲 2020 3 26 2 114 2 1基本概念与ADT2 2顺序表示2 3链接表示2 4应用举例2 5矩阵2 6广义表与动态存储管理 2020 3 26 3 114 线性结构 只有一个开始结点和一个结束结点 所有结点排成一个线性序列串 栈 队列都是线性结构线性表 简称为表 是零个或多个元素的有穷序列 L k0 k1 kn 1 线性表的逻辑结构 L 其中K k0 k1 kn 1 R 0 i n 2 i称为元素ki的索引或下标 基本概念 2020 3 26 4 114 表中所含元素的个数称为表的长度 长度为零的表称为空表 k0称为第一个元素 kn 1称为最后一个元素 ki 0 i n 2 是ki 1的前驱 ki 1是ki的后继 k0只有一个后继 kn 1只有一个前驱 2020 3 26 5 114 例1 大写英文字母 A B C D Z 1 10的整数 1 2 3 4 10 例2 某院系的学生名册学号姓名性别年龄专业名称 09001001张丰男17信息与计算科学09001002刘小红女18信息与计算科学09001003李静女18数学与金融工程09001004王建平男18数学与金融工程 2020 3 26 6 114 2020 3 26 7 114 某年南方GDP排名前20的城市同年南方GDP排名前20的城市 List 线性表类型 DataType 元素类型 Position 元素的下标类型 可说明如下 Listlist DataTypex Positionp 注 元素的类型与讨论无关 抽象数据类型 ADT 2020 3 26 8 114 线性表的抽象数据类型 ADT ADTListisoperationsListcreateNullList void 创建并且返回一个空线性表intinsertPre Listlist positionp DataTypex 在list中p位置前插入值为x的元素 并返回插入成功与否的标志intinsertPost Listlist positionp DataTypex 在list中p位置后插入值为x的元素 并返回插入成功与否的标志intdeleteV Listlist DataTypex 在list中删除一个值为x的元素 并返回插入成功与否的标志 2020 3 26 9 114 intdeleteP Listlist positionp 在list中删除位置为p的元素 并返回插入成功与否的标志 Positionlocate Listlist DataTypex 在list中查找值为x的元素的位置 intisNull Listlist 判别list是否为空线性表 endADTList 2020 3 26 10 114 2 1基本概念与ADT2 2顺序表示2 3链接表示2 4应用举例2 5矩阵2 6广义表与动态存储管理 2020 3 26 11 114 线性表最简单的存储方法是采用顺序方式 称作线性表的顺序表示 通常可称此时的线性表为顺序表具体做法是 将线性表中的元素一个接一个地存储在一片相邻的存储区域中 线性表的顺序存储结构是一种可以随机存取的存储结构 2020 3 26 12 114 假设每个元素占用c个存储单元 则下标为i 1的元素的存储位置与下标为i的元素的存储位置之间 满足下列关系 loc ki 1 loc ki c通常把顺序表中k0的存储位置loc k0 称为线性表的首地址或基地址 下标为i的元素ki的存储位置为 loc ki loc k0 i c 存储结构 2020 3 26 13 114 2020 3 26 14 114 顺序表定义 C语言 2020 3 26 15 114 defineMAXNUM100DataTypeelement MAXNUM defineMAXNUM100intn 存放线性表中元素的个n MAXNUM DataType element element 0 element 1 element n 1 存放线性表中的元素 设palist是一个指向SeqList类型的指针变量 则 palist MAXNUM 顺序表中最大元素的个数 palist n 顺序表中实际元素的个数 palist element 0 palist element palist n 1 顺序表中的各个元素 2020 3 26 16 114 structSeqList intMAXNUM 顺序表中最大元素的个数 intn 存放线性表中元素的个n MAXNUM DataType element element 0 element 1 element n 1 存放线性表中的元素 typedefstructSeqList PSeqList 1 创建一个空顺序表PSeqListcreateNullList seq intm 分配顺序表空间 PSeqList malloc sizeof structSeqList 为顺序表分配数组空间 大小为m DataType malloc sizeof DataType m MAXNUM置为m n置为0 说明 malloc 在内存的动态存储区域中分配一个长度为size的连续空间 如果未成功 返回空指针NULL free 释放由p指向的内存区 运算的实现 2020 3 26 17 114 2020 3 26 18 114 PSeqListcreateNullList seq intm 创建新的顺序表 PSeqListpalist PSeqList malloc sizeof structSeqList if palist NULL palist element DataType malloc sizeof DataType m if palist element palist MAXNUM m palist n 0 空表长度为0 return palist elsefree palist printf Outofspace n 存储分配失败 returnNULL 2 判断线性表是否为空intisNullList seq PSeqListpalist 判断palist的n字段是否为0即可 2020 3 26 19 114 intisNullList seq PSeqListpalist 判别palist所指顺序表是否为空表 return palist n 0 3 求某元素位置intlocate seq PSeqListpalist DataTypex x与表中元素依次 相同则返回下标若表中没有x 则返回 1 2020 3 26 20 114 intlocate seq PSeqListpalist DataTypex 求x在palist所指顺序表中的下标 intq for q 0 qn q if palist element q x return q return 1 4 顺序表的元素插入intinsertPre seq PSeqListpalist intp DataTypex 在下标为p 1与下标为p的元素之间插入一个新的元素x1 溢出检测 palist nMAXNUM2 p的有效性 0 p palist n3 下标为n p的元素依次后移一位 2020 3 26 21 114 2020 3 26 22 114 2020 3 26 23 114 intinsertPre seq PSeqListpalist intp DataTypex 在palist所指顺序表中下标为p的元素之前插入元素x intq if palist n palist MAXNUM 溢出 printf Overflow n return0 if ppalist n 不存在下标为p的元素 printf Notexist n return0 for q palist n 1 q p q 插入位置及之后的元素均后移一个位置 palist element q 1 palist element q palist element p x 插入元素x palist n palist n 1 元素个数加1 return1 同样的 intinsertPost seq PSeqListpalist intp DataTypex 2020 3 26 24 114 5 顺序表中删除元素 按下标 intdeleteP seq PSeqListpalist intp 检查p的有效性下标为p 1 palist n 1的元素依次前移一位 2020 3 26 25 114 2020 3 26 26 114 2020 3 26 27 114 2020 3 26 28 114 intdeleteP seq PSeqListpalist intp 在palist所指顺序表中删除下标为 的元素 intq if ppalist n 1 不存在下标为p的元素 printf Notexist n return0 for q p qn 1 q 被删除元素之后的元素均前移一个位置 palist element q palist element q 1 palist n palist n 1 元素个数减1 return1 6 顺序表中按值删除元素intdeleteV seq PSeqListpalist DataTypex 1 定位x的位置 locate seq2 删除该位置的元素 参考deleteP seq 代码 略 2020 3 26 29 114 1 删除算法的时间复杂性即 估算顺序表删除运算中的平均移动元素个数设Pi是在下标为i的位置上删除元素的概率删除下标为i 第i 1个 的元素需要移动n i 1个元素于是 删除的平均移动数为 若有Pi 1 n 则有 分析与评价 2020 3 26 30 114 2 插入算法的时间复杂性设Pi 是在下标为i的位置之前插入元素的概率在下标为i的元素之前插入元素需要移动n i个元素于是 删除的平均移动数为 若有Pi 1 n 1 则有 2020 3 26 31 114 因此 删除和插入算法的时间复杂度为 T n O n 观察插入算法 如何补救 重新申请一个比较大 如原数组大小 2 的数组 以代替原来的数组 顺序表空间的扩展 2020 3 26 32 114 intinsertPre seq PSeqListpalist intp DataTypex if palist n palist MAXNUM 溢出 printf Overflow n return0 可用以下代码代替插入算法中的相应代码 2020 3 26 33 114 pos1 DataType malloc sizeof DataType palist MAXNUM 2 if pos1 NULL printf Overflow return0 for q 0 qMAXNUM q pos1 q palist element q free palist element palist element pos1 palist MAXNUM 2 1 假设有两个集合A和B分别用两个线性表来表示palist和pblist 线性表中的数据元素即为集合的元素 现在要求一个新集合A AUB思路 从线性表B中依次取得每个元素 retrieve seq pblist p x在线性表A中查找x locate seq palist x 若不存在则插入到表最后 insertPost seq palist palist n 1 x 思考 线性表应用举例 2020 3 26 34 114 2 求顺序表中第一个值为x的元素的前驱和后继的位置 3 合并有序 非递减顺序 线性表A和B 合并后的线性表C也具有同样的特性 2020 3 26 35 114 优点 逻辑相邻 物理相邻存储空间使用紧凑可随机存取任一元素缺点 插入 删除操作需要移动大量的元素预先分配空间需按最大空间分配 利用不充分表容量难以扩充 小结 线性表示的优缺点 2020 3 26 36 114 2 1基本概念与ADT2 2顺序表示2 3链接表示2 4应用举例2 5矩阵2 6广义表与动态存储管理 2020 3 26 37 114 特点 逻辑相邻但物理不相邻增加指针来指示其后继 链接表示 2020 3 26 38 114 每个节点有两个域 数据域 info 数据元素本身的信息指针域 link 后继结点的存储位置最后一个元素没有后继 其指针为空设一线性表有n个元素 则此n个结点就通过指针链接成一个链表 由于每个结点只有一个指针域 故又称为单链表 指向链表中第一个结点的指针称为头指针 单链表表示 2020 3 26 39 114 2020 3 26 40 114 结点类型和单链表类型定义 说明 PNode与LinkList实为同一类型 既可以是指向某一结点的指针类型 也可以看成单链表的类型 即头指针的类型 2020 3 26 41 114 structNode 单链表结点类型 typedefstructNode PNode 结点指针类型 structNode 单链表结点结构 DataTypeinfo PNodelink typedefstructNode LinkList 单链表类型 structNode DataTypeinfo Nodelink 2020 3 26 42 114 头结点 info字段一般存放与整个链表相关的信息 如元素个数等 link字段指向第一个结点头结点的引入增加了额外的空间使得对于第一个结点的处理 如插入 删除等 与其它结点的处理一致起来 2020 3 26 43 114 1 创建空链表LinkListcreateNullList link void 为单链表的头结点申请空间 若成功则返回单链表 单链表运算的实现 2020 3 26 44 114 LinkListcreateNullList link void 创建一个带头结点的空链表 申请表头结点空间 LinkListllist LinkList malloc sizeof structNode if llist NULL llist link NULL elseprintf Outofspace n 创建失败 return llist 2 判断单链表是否为空intisNullList link LinkListllist 只要检查头结点的指针 llist link 是否为空 2020 3 26 45 114 intisNullList link LinkListllist 判断带有头结点的单链表llist是否是空链表 return llist link NULL 3 在单链表中求某元素的存储位置Pnodelocate link LinkListllist DataTypex 在带头结点的单链表llist中求第一个值为x的结点的存储位置依次查找 对比 若找不到则返回NULL 2020 3 26 46 114 PNodelocate link LinkListllist DataTypex 在llist带有头结点的单链表中找第一个值为x的结点存储位置 PNodep if llist NULL return NULL p llist link while p NULL 4 在某结点后插入新节点intinsertPost link LinkListllist PNodep DataTypex 在结点p后面插入值为 的新结点 2020 3 26 47 114 1 q link p link 2 p link q 注意 1 2 顺序不能反 2020 3 26 48 114 intinsertPost link LinkListllist PNodep DataTypex 在llist带头结点的单链表中 p所指结点后面插入元素x PNodeq PNode malloc sizeof structNode 申请新结点 if q NULL printf Outofspace n return 0 else q info x q link p link p link q return 1 5 在某结点前插入新节点intinsertPre link LinkListllist PNodep DataTypex 在结点p前面插入值为 的新结点1 先找到结点p的前驱 locatePre link 2 在p的前驱之后插入新结点 2020 3 26 49 114 2020 3 26 50 114 PNodelocatePre link LinkListllist PNodep 在单链表中求p所指结点的前驱结点 PNodep1 if llist NULL return NULL p1 llist while p1 NULL 6 单链表中按值删除元素intdeleteV link LinkListllist DataTypex 删除第一个元素值为x的结点 并返回删除成功与否的标志从第一个结点开始查找第一个元素值为x的结点删除该结点 修改指针 需记录其前驱结点 2020 3 26 51 114 p link p link link 2020 3 26 52 114 intdeleteV link LinkListllist DataTypex 在llist带有头结点的单链表中删除第一个值为x的结点 PNodep q p llist if p NULL return 0 while p link NULL 7 单链表中按位置删除元素intdeleteP link LinkListllist PNodep 删除链表中的结点p 并返回删除成功与否的标志 先调用locatePre link llist p 找到p所指结点的前驱结点然后实现结点删除 2020 3 26 53 114 单链表 n个结点 的结点查找最坏情况下要查找n个结点 平均情况下需要查找n 2个结点 因此时间复杂度为O n 其它操作的时间复杂度 分析与比较 2020 3 26 54 114 优点 不要预先按最大的需要分配连续空间 线性表的插入和删除只需修改指针域 而不需移动其他元素 缺点 每个结点中的指针域需额外占用存储空间 存储密度小 链式存储结构是一种非随机存储结构 查找任一结点都要从头指针开始 沿指针域一个一个地搜索 这增加了有些算法的时间代价 小结 链接表示的优缺点 2020 3 26 55 114 1 循环链表单链表 最后一个结点的指针为NULL循环链表 最后一个结点的指针指向头一个结点优点 从循环链表中任一结点出发 都能访问遍所有结点 单链表的改进和扩充 2020 3 26 56 114 2 双链表单链表 找到某结点的前驱比较困难双链表 每个结点有两个指针域 一个指向前驱 一个指向后继 2020 3 26 57 114 2 双链表 cont 双链表及其结点的定义 2020 3 26 58 114 structDoubleNode 双链表结点 typedefstructDoubleNode PDoubleNode 结点指针类型 structDoubleNode 双链表结点结构 DataTypeinfo PDoubleNodellink rlink structDoubleList 双链表类型 PDoubleNodehead 指向第一个结点 PDoubleNoderear 指向最后一个结点 2 双链表 cont 双链表中 删除指针变量p所指的结点 p llink rlink p rlink p rlink llink p llink free p 2020 3 26 59 114 2 双链表 cont 双链表中 在p所指结点后插入一个新结点 q PDoubleNode malloc sizeof structDoubleNode q llink p q rlink p rlink p rlink llink q p rlink q 2020 3 26 60 114 3 循环双链表双链表 循环链表头结点由头指针cdlist指出 并链接在头结点和尾结点之间 2020 3 26 61 114 2 1基本概念与ADT2 2顺序表示2 3链接表示2 4应用举例2 5矩阵2 6广义表与动态存储管理 2020 3 26 62 114 问题描述 设有n个人围坐在一个圆桌周围 现从第s个人开始报数 数到第m的人出列 然后从出列的下一个人重新开始报数 数到第m的人又出列 如此反复直到所有的人全部出列为止 Josephus问题 对于任意给定的n s和m 求出按出列次序得到的n个人员的序列 Josephus问题 2020 3 26 63 114 2020 3 26 64 114 以n 8 s 1 m 4为例 a n4 b n4n8 c n4n8n5 d n4n8n5n2 2020 3 26 65 114 e n4n8n5n2n1 f n4n8n5n2n1n3 g n4n8n5n2n1n3n7 h n4n8n5n2n1n3n7n6 求解Josephus问题的一般步骤 1 利用线性表的一些运算构造Josephus表 如 创建空线性表 插入元素等 2 从Josephus表中的第s个结点开始寻找 输出和删除表中的第m个结点 然后再从该结点后的下一结点开始寻找 输出和删除表中的第m个结点 重复此过程 直到Josephus表中的所有元素都删除 2020 3 26 66 114 主要步骤 1 将整数序列 1 2 3 n 存储在一个palist所指顺序表中用整数i来代替ni 2 最初从第s个人开始 即palist element s 1 则第一个报数出列的元素编号应为 s 1 m 1 n 设该编号为i 是否s n对程序并不影响 3 输出元素palist element i 并将该元素从顺序表中删除 4 继续在新的顺序表中进行以上 2 3 操作 直至顺序表为空为止相关代码 采用顺序表模拟 2020 3 26 67 114 2020 3 26 68 114 include include include SeqList h voidjosephus seq PSeqListpalist ints intm ints1 i w s1 s 1 for i palist n i 0 i 找出列的元素 s1 s1 m 1 i w palist element s1 求下标为s1的元素的值 printf Outelement d n w 元素出列 deleteP seq palist s1 删除出列的元素 2020 3 26 69 114 voidmain inti n s m printf npleaseinputthevalues element free jos alist 主要步骤 1 将整数序列 1 2 3 n 存储在一个循环单链表中init clink函数 建立一个头指针为jos clist的Josephus循环单链表 2 在循环单链表中的第s个结点开始寻找 反复输出和删除其中的第m个结点 由josephus clist函数实现 其主要步骤为 a 找jos clist所指的循环单链表中的第s个结点放在指针变量p中 b 从p所指结点开始计数寻找第m个结点 c 输出该结点的元素值 d 删除该结点 并将该结点的下一个结点放在指针变量p中 转去执行 b 直到所有结点被删除为止 采用循环链表模拟 2020 3 26 70 114 2020 3 26 71 114 include include include LinkList h defineFALSE0 defineTRUE1 intinit clist PLinkListpclist intn 用1 n为 pclist所示的循环表初始化 PNodep q inti q PNode malloc sizeof structNode if q NULL return FALSE pclist q q info 1 q link q if n 1 return TRUE for i 2 iinfo i p link q link q link p q p return TRUE 2020 3 26 72 114 voidjosephus clist PLinkListpclist ints intm PNodep pre inti p pclist 找第s个元素 if s 1 pre p p p link while p pclist pre p p p link elsefor i 1 ilink 当链表中结点个数大于1时 while p p link 找第m个结点 for i 1 ilink 输出该结点 printf outelement d n p info if pclist p pclist p link pre link p link 删除该结点 free p p pre link 输出最后一个结点 printf outelement d n p info pclist NULL free p 2020 3 26 73 114 voidmain LinkListjos clist intn s m 输入所需各参数的值 do printf npleaseinputthevaluesofn scanf d 2 1基本概念与ADT2 2顺序表示2 3链接表示2 4应用举例2 5矩阵2 6广义表与动态存储管理 2020 3 26 74 114 矩阵作为一种线性表的推广在矩阵的逻辑结构 K R 中 可以定义K是一个线性表的集合 R是K上的一个线性关系 矩阵可看做是线性表的线性表 矩阵 2020 3 26 75 114 1 行优先顺序即元素按行向量顺序排列 第i 1个行向量紧接在第i个行向量后面矩阵Am n中元素的排列顺序是 a00 a01 a0n 1 a10 a11 a1n 1 am 10 am 11 am 1n 1其地址计算公式为 假设每个元素占一个单元 Loc aij loc a00 i n j2 列优先顺序即元素按列向量顺序排列 第j 1个列向量紧接在第j个列向量后面矩阵Am n中元素的排列顺序是 a00 a10 am 10 a01 a11 am 11 a0n 1 a1n 1 am 1n 1其地址计算公式为 Loc aij loc a00 j m i 矩阵的顺序表示 2020 3 26 76 114 按行优先顺序存储 其地址计算公式为 以下都假设每个元素占一个单元 Loc aij loc a00 i n j按列优先顺序存储 其地址计算公式为 Loc aij loc a00 j m i矩阵的顺序表示的特点 存储密度很高 存取的速度很快 2020 3 26 77 114 对于某些特殊情况 可以改进 考虑n n的下三角矩阵A 因为所有i j时 都有aij 0 因此只需要存储非零 满足0 j i n 1 的元素 若按 行优先顺序 把非零的aij顺序存储 其地址计算公式为 Loc aij loc a00 i i 1 2 j 0 j i n 1 同理 上三对角矩阵和对称矩阵也可以参考下三角矩阵的方法处理 2020 3 26 78 114 稀疏矩阵设m n的矩阵A中有k个非零元素 又设k大大小于m n 记为K m n 则称A为稀疏矩阵为节省存储空间 最好是只存稀疏矩阵中的非零元素 但这样一来很难继续保持用顺序表示时所具有的可以随机存取矩阵元素的优点 存储稀疏矩阵的方法是多种多样的 下面介绍其中几种 1 三元组表示法 2 伪地址表示法 3 带辅助行向量的二元组表示法 4 行 列表示法 稀疏矩阵的表示方法 2020 3 26 79 114 1 三元组表示法这个方法用一个数组 顺序结构 来表示稀疏矩阵 这个数组中只存放稀疏矩阵的非零元素 每个结点包括3个字段 分别为该非零元素的行下标 列下标和值 结点间的顺序按矩阵的行优先顺序排列 跳过非零元素 设行下标和列下标也占一个存储单元 那么这种方法需要3k个存储单元 2020 3 26 80 114 2020 3 26 81 114 对于矩阵X 其稀疏矩阵的三元组表示为 行下标列下标值0001510322205 15311114123523 66409175228 分析设行下标和列下标也占一个存储单元 那么这种方法需要 个存储单元 为非零元素个数 在上面的例子中k 8 因为是顺序存储 行下标和列下标又是递增排列的 可以 把ij连接成为一个整数 作为关键码 用二分法检索 查找一个矩阵元素的时间为 log2k 关于二分法检索的算法 将在第6章中介绍 这种表示的缺点是修改不便 若矩阵元素的值发生变化 一个原来值为零的元素现在变成非零 就要往表里插入结点 为了保持表示的行优先顺序 以便进行二分法检索 那么插入时就必须在存储器里移动所有后面的元素 2020 3 26 82 114 2 伪地址表示法元素的伪地址就是元素在矩阵里按行优先顺序的相对位置 包括零元素一起算 伪地址法和三元组法相似 只是数组的每个结点只包括两个字段 分别为矩阵非零元素的伪地址和值 这种方法需用2k个存储单元 比三元组法要节省 它付出的代价是计算伪地址 而伪地址是很好算的 元素aij的伪地址为i n j 2020 3 26 83 114 2020 3 26 84 114 伪地址值0015132225 15371148 3515 66249173228 稀疏矩阵伪地址表示 3 带辅助行向量的二元组表示法这个方法是三元组表示法的一个变种 在三元组表示法中 去掉行下标字段 而加上一个有 个元素的辅助行向量NRA 它的值定义如下 NRA 0 0 NRA i NRA i 1 矩阵第i 1行中非零元素的个数用带辅助行向量的二元组表示法表示稀疏矩阵 每个非零元素只需要两个字段表示 分别为非零元素的列下标和值 2020 3 26 85 114 2020 3 26 86 114 4 行 列表示法矩阵的一个非零元素用一个结点表示 每个结点包括五个字段 分别为元素的行下标 列下标 值 以及指向本行下一个非零元素的指针和指向本列下一个非零元素的指针 另外还有行的头指针向量和列的头指针向量 行的头指针向量有 个元素 分别指向代表各行的第一个非零元素的结点 列的头指针向量有 个元素 分别指向代表各列的第一个非零元素的结点 2020 3 26 87 114 2020 3 26 88 114 讨论时间代价和空间代价始终是数据结构与算法设计的最主要因素 然而它们往往是相互对立的 一个好的设计总是在时间代价和空间代价之间作出了一个好的权衡 而这种权衡的标准需要根据实际计算机的资源情况和求解问题的特点来确定 顺序表和单链表是两种最简单的数据结构 但是它们的应用非常广泛 本节中对于稀疏矩阵的所有表示都是这两种结构的扩充和组合 稀疏矩阵本身也是许多复杂结构的抽象 2020 3 26 89 114 2 1基本概念与ADT2 2顺序表示2 3链接表示2 4应用举例2 5矩阵2 6广义表与动态存储管理 2020 3 26 90 114 广义表是线性表的推广 具有广泛的应用价值 它是表处理语言 例如LISP 的基础结构 也可以用于表示动态存储空间的整体模型 2020 3 26 91 114 从逻辑上看 广义表也是零个或多个元素组成的序列 但是 广义表中的元素允许以不同形式出现 它可以是一个原子 逻辑上不能再分解的元素 也可以又是一个广义表 作为广义表元素的广义表称作广义表的子 广义 表 一个广义表还允许直接或间接地作为它自身的子 广义 表 为了区分广义表和原子 可以用圆括号把一个广义表括起来 再用逗号来分隔广义表中的元素 一个广义表中所包含的元素的个数 称为这个广义表的长度 长度为零的广义表称为空 广义 表 一个广义表的深度 就是指广义表中所含子表的层数 广义表 2020 3 26 92 114 书写中约定 用大写字母表示广义表 用小写字母表示原子 例如 2020 3 26 93 114 广义表的分类如果广义表中的元素全部都是原子 例如广义表 这种广义表就是线性表 如果广义表中的元素允许有子广义表 但所有各层子广义表均无共享 例如广义表 这种广义表 称为纯表 在各层子广义表中允许共享的广义表 例如广义表 的子表B中共享了A 称为再入表 允许 子 广义表直接 或间接 地把作为自己的子广义表时 这样的广义表 例如广义表 称为递归表 2020 3 26 94 114 广义表的操作建立一个广义表 取广义表的头一个元素 在广义表中插入一个元素 删除一个元素 取删除头一个元素后的广义表 把一个广义表拆成两个部分 把两个广义表合并成一个新广义表 周游一个广义表 拷贝一个广义表 判别某元素是否原子 判别两个广义表是否相等 判别某广义表是否空广义表 2020 3 26 95 114 广义表的表示方法主要有 单链表示法带头结点的单链表示法 2020 3 26 96 114 单链表示法每个结点由三个字段组成 atom info link 其中atom是一标志位 atom 0表示本结点为子广义表 这时字段info存放子广义表中第一个元素所对应结点的地址 atom 1表示本结点为原子 字段info存放本原子的信息 当信息量比较大时 也可以存放本原子信息存放的地址 字段link存放与本元素同层的下一个元素所对应结点的地址 当本元素是所在层的最后一个元素时 link NULL 2020 3 26 97 114 2020 3 26 98 114 带头结点的单链表示法上述单链表示法的一个主要缺点是 如果要删除广义表 或子广义表 中某一元素 例如删除A中的x 则需要搜索广义表中所有结点后才能进行 解决办法 对每个子广义表 增设一个广义表头结点 为区分是一般结点或者是表头结点 不妨令表头结点atom字段为 1 表头结点的info字段可以用来存放本广义表 或子广义表 的有关信息 表头结点的link字段指向广义表中第一个元素对应的结点 2020 3 26 99 114 2020 3 26 100 114 单链表中的元素的个数是任意的 允许自由变化 习惯上把这种在使用期间 可自由插入和删除的数据结构称为动态数据结构 在程序运行过程中 对于动态数据结构结点的分配和回收需要采用动态存储管理的方法 结点的动态分配与回收 2020 3 26 101 114 在前面的讨论中 当单链表插入值为x的元素时 只需调用函数malloc 便能得到一个所需结点的空间 并返回这个结点的起始地址 在某指针所指向的结点删除后 调用函数free 就可以将该结点所占的空间释放 以利于再分配 函数malloc和free就是实现动态存储管理的两个最基本的函数 2020 3 26 102 114 等长结点的分配与回收可利用空间表 2020 3 26 103 114 不等长结点的分配与回收一个处理方法是 在动态区中建立多个可利用空间表 每个可利用空间表对应一种固定长度的结点 缺点是 难以真正解决多个可利用空间表的共享问