数据结构期末重点复习题

1 作业 1 简述逻辑结构和存储结构的联系 2 数据结构和数据类型有什么区别 3 分析以下算法的时间复杂度voidfunc intn inti 0 s 0 while s n i s s i 2 2020 4 7 顺序表算法设计练习 已知一个顺序表L 其中的元素递增有序排列 设计一个算法插入一个元素x后保持该顺序表仍递增有序排列 3 2020 4 7 参考算法 Voidinsert Sqlist 4 2020 4 7 顺序表算法设计练习 试写一个算法 实现顺序表的就地逆置 即利用原表的存储空间将线性表 a1 a2 an 逆置为 an an 1 a1 5 2020 4 7 参考算法 Voidreverse Sqlist 6 2020 4 7 顺序表算法设计练习 试设计一个高效的算法 删除线性表L中所有值为x的元素 7 2020 4 7 参考算法 Voiddeletelist Sqlist 8 2020 4 7 链表算法设计练习 设计一个算法删除带头结点的单链表L中值为x的结点的直接前驱结点 9 2020 4 7 参考算法 Intdelx Linklist 10 2020 4 7 链表算法设计练习 设计一个算法 在带头结点的单链表head中删除一个data域值最小的结点 假设该结点唯一 11 2020 4 7 参考算法 VoidDelMinNode Linklisthead Linklistp head next pre head Linklistminp minpre Elemtypemin p data minp p minpre pre While p NULL If p datadata min p data minp p minpre pre pre p p p next minpre next minp next Free minp 12 2020 4 7 1 假设表达式中允许包含3种括号 圆括号 方括号和大括号 设计一个算法采用顺序栈判断表达式中的括号是否正确配对 Intmatch charexp intn charst Maxsize inttop 1 inti 0 tag 1 while i n 13 2020 4 7 2 假设用一个循环单链表表示队列 并且只设一个指针rear指向队尾结点 但不设头指针 设计出相应的队初始化 入队算法 VoidinitQu Qnode rear s 14 2020 4 7 作业 1 设一系列正整数存放在一个数组中 试设计算法 将所有奇数存放在数组的前半部分 将所有的偶数放在数组的后半部分 要求尽可能少用临时存储单元并使时间最少 2 设计一个算法 计算一个三元组表表示的稀疏矩阵的对角线元素之和 15 例 设树T的度为4 其中度为1 2 3和4的结点个数分别为4 2 1 1则T中的叶子数为 A 5B 6C 7D 8提示 因为每个结点都有一条枝指向它 分支数为1 4 2 2 3 1 4 1所有结点数为分支数 1 所以1 4 2 2 3 1 4 1 4 2 1 1 xx 8例 若一棵二叉树具有10个度为2的结点 5个度为1的结点 则度为0的结点个数是 A 9B 11C 15D 不确定提示 n0 n2 1 16 例3 已知某二叉树先序序列 ABHFDECKG 和中序序列 HBDFAEKCG 画出该二叉树 17 例1 统计二叉树中叶子结点的个数 StatusCountLeaf BiTreeT int 18 例2 求二叉树的深度 intDepth BiTreeT if T depthval 0 else depthLeft Depth T lchild depthRight Depth T rchild depthval 1 max depthLeft depthRight returndepthval 19 例3 按先序序列建立二叉树的二叉链表 已知先序序列 ABC00DE0G00F000 其中0表示空格字符 空指针 建立相应的二叉链表 A B C D E F G 20 例 对于前序遍历与中序遍历结果相同的二叉树 对于前序遍历和后序遍历结果相同的二叉树为 A 一般二叉树B 只有根结点的二叉树C 根结点无左孩子的二叉树D 根结点无右孩子的二叉树E 所有结点只有左子数的二叉树F 所有结点只有右子树的二叉树例 某二叉树的前序序列和后序序列正好相反 则该二叉树一定是 的二叉树 A 空或只有一个结点B 任一结点无左子树C 高度等于其结点数D 任一结点无右子树 F B 21 例 一棵左子树为空的二叉树在先序线索化后 其中空的链域的个数是 A 不确定B 0C 1D 2例 一棵左右子树均不空的二叉树在先序线索化后 其中空的链域的个数是 A 0B 1C 2D 不确定 左子树为空的二叉树的根结点的左线索为空 无前驱 先序序列的最后结点的右线索为空 无后继 共2个空链域 只有最后一个叶结点没有后继 22 例 线索二叉树是一种 结构 A 逻辑B 逻辑和存储C 物理D 线性例 n个结点的线索二叉树上含有的线索数为 A 2nB n 1C n 1D n N个结点共有2n个指针域 二叉链表用了n 1个 剩下n 1个 23 练习 写出下图所示树的先序和后序遍历序列并将之转换成一棵二叉树 先根遍历 ABDEGHICF 后根遍历 DGHIEBFCA 24 6 4 2森林和二叉树的转换 规则 设森林F T1 T2 Tm 二叉树B root LB RB 1 森林转化成二叉树的规则 若F为空 m 0 B为空 若F不空 m 0 B的根root B 是F中第一棵树T1的根root T1 左子树LB从T1根结点的子树森林 T11 T12 T1m 转换来 右子树RB是从森林F T2 T3 Tm 转换而来 2 二叉树转换为森林的规则 若B为空 F为空 若B非空 则F中第一棵树T1的根为二叉树的根root B T1根的子树森林F1由B的左子树LB转换而来 F中除T1外其余树组成的森林F T2 T3 Tn 由B的右子树RB转换而来 25 森林转换成二叉树 步骤1 转换 将各棵树分别转换成二叉树步骤2 加线 将每棵树的根结点用线相连步骤3 旋转 以第一棵树根结点为二叉树的根 再以根结点为轴心 顺时针旋转 构成二叉树 森林F 26 森林转换成二叉树 步骤1 转换 将各棵树分别转换成二叉树步骤2 加线 将每棵树的根结点用线相连步骤3 旋转 以第一棵树根结点为二叉树的根 再以根结点为轴心 顺时针旋转 构成二叉树 E F G H I J 森林F 27 森林转换成二叉树 步骤1 转换 将各棵树分别转换成二叉树步骤2 加线 将每棵树的根结点用线相连步骤3 旋转 以第一棵树根结点为二叉树的根 再以根结点为轴心 顺时针旋转 构成二叉树 E F G H I J 森林F F转换的二叉树B 28 二叉树转换成森林 步骤1 抹线 将二叉树根结点与其右孩子连线 沿右分支搜索到的所有右孩子间连线全部抹掉 使之变成多棵二叉树步骤2 还原 将孤立的二叉树还原成树 二叉树B 29 二叉树转换成森林 步骤1 抹线 将二叉树根结点与其右孩子连线 沿右分支搜索到的所有右孩子间连线全部抹掉 使之变成多棵二叉树步骤2 还原 将孤立的二叉树还原成树 二叉树B 30 二叉树转换成森林 步骤1 抹线 将二叉树根结点与其右孩子连线 沿右分支搜索到的所有右孩子间连线全部抹掉 使之变成多棵二叉树步骤2 还原 将孤立的二叉树还原成树 A B C D E F G H I J 二叉树B 31 二叉树转换成森林 步骤1 抹线 将二叉树根结点与其右孩子连线 沿右分支搜索到的所有右孩子间连线全部抹掉 使之变成多棵二叉树步骤2 还原 将孤立的二叉树还原成树 B转换成的森林F 二叉树B A B C D E F G H I J 32 练习 写出下图所示森林的先序和中序遍历序列并将之转换成一棵二叉树 先序遍历 中序遍历 ABCDEFIKJGH BEFDCIAJGHK 33 例 设F是一个森林 B是由F变换得的二叉树 若中有n个非终端结点 则B中右指针域为空的结点有 个 A n 1B nC n 1D n 2 每一个非终端结点的孩子中都会贡献出一个空的右指针 例 设F是由T1 T2 T3三棵树组成的森林 与F对应的二叉树为B 已知T1 T2 T3的结点数分别为n1 n2和n3则二叉树B的左子树中有个结点 右子树中有个结点 n1 1 n2 n3 34 构造最优二叉树的说明 1在选取两棵根结点权值为最小和次小的二叉树时 如果出现权值相同的情况 可以在相同权值的二叉树中任选一棵 2当两棵根结点权值为最小和次小的二叉树组成新的二叉树的左右子树时 谁是左子树谁是右子树没有特殊规定 3在最优二叉树中没有度为1的结点 根据二叉树的性质3可知有n个叶子结点的二叉树有n 1个非终端结点共有2 n 1个结点 35 如何得到最短的二进制前缀码 赫夫曼编码 为了设计电文总长最短的二进制前缀编码 以n种字符出现的频率作权 设计一棵赫夫曼树 从根节点至即所有叶子节点 按左分支为0 右分支为1的原则即可得到最短二进制前缀编码即赫夫曼编码 例 已知某系统在通信联络中只可能出现8种字符 其概率为0 05 0 29 0 07 0 08 0 14 0 23 0 03 0 11 设计赫夫曼编码 解 设权w 5 29 7 8 14 23 3 11 36 编码 3 0111 5 0110 7 1110 8 1111 11 010 14 110 23 00 29 10 37 练习 用于通信的电文由8个字母c1 c2 c3 c4 c5 c6 c7 c8组成 各字母在电文中出现的频率分别为5 25 3 6 10 11 36 4 试设计不等长Huffman编码 并给出该电文的总码数 0000000100101000101 0111011 电文总码数 4 5 2 25 4 3 4 6 3 10 3 11 2 36 4 4 257 38 2020 4 7 练习 1 设无向图的顶点个数为n 则该图最多有 条边 2 一个有n个结点的图 最少有 个连通分量 最多有 个连通分量 3 在一个无向图中 所有顶点的度数之和等于所有边数的 倍 4 要连通具有n个顶点的有向图 至少需要 条边 5 若无向图G V E 中含7个顶点 则保证图G在任何情况下都是连通的 则需要的边数最少是 39 2020 4 7 无向图 顶点的度 该顶点所在单链表中表结点个数 与顶点V1相邻接的顶点在数组中的下标 40 2020 4 7 权值 无向网 41 2020 4 7 以顶点V1为始点的弧的终点顶点在数组中的下标 顶点的出度该顶点所在单链表中表结点个数顶点的入度查询整个邻接表中的表结点 与该顶点的序号 数组下标 一致的表结点个数 有向图 42 2020 4 7 图的邻接表表示 问题 具有n个顶点e条边的无向图的邻接表中有多少个表头结点 有多个表结点 边结点 有向图呢 43 2020 4 7 练习 请画出下图的邻接矩阵和邻接表 44 2020 4 7 7 3 1深度优先搜索 举例 深度遍历 V1 V3 V7 V6 V2 V5 V8 V4 给定存储结构 图的遍历序列唯一 45 2020 4 7 7 3 2广度优先搜索 举例 广度遍历 V1 V3 V2 V7 V6 V5 V4 V8 给定存储结构 图的遍历序列唯一 46 2020 4 7 下列有关图遍历的说法中不正确的是 A 连通图的深度优先搜索是一个递归过程B 图的广度优先搜索中邻接点的寻找具有 先进先出 的特征C 图的遍历要求每一顶点仅被访问一次D 对图进行一次深度优先遍历可以访问图中所有顶点 47 2020 4 7 给定有向图如下 给出其邻接表存储结构基于邻接表 给出DFS序列和BFS序列 48 2020 4 7 练习 已知一个图的顶点集V和边集E分别为 V 1 2 3 4 5 6 7 E 1 2 3 1 3 5 1 4 8 2 5 10 2 3 6 3 4 15 3 5 12 3 6 9 4 6 4 4 7 20 5 6 18 6 7 25 用克鲁斯卡尔算法得到最小生成树 试写出在最小生成树中依次得到的各条边 答 用克鲁斯卡尔算法得到的最小生成树为 1 2 3 4 6 4 1 3 5 1 4 8 2 5 10 4 7 20 49 2020 4 7 练习 设有无向图G 要求给出用普里姆算法构造最小生成树所走过的边的集合 答 E 1 3 1 2 3 5 5 6 6 4 50 2020 4 7 7 5 1拓扑排序 实现步骤 C1 C3 C2 C7 C5 C6 C4 拓扑有序序列 逻辑结构上 拓扑序列不唯一 51 2020 4 7 7 5 2关键路径 AOE 网 ActiveOnEdge 在带权的有向无环图中 顶点表示事件 弧表示工程的一个活动 弧上权值表示活动持续的时间 用来估算工程完成时间 源点 入度为0的顶点 汇点 出度为0的顶点 路径长度 AOE网中路径上各活动持续时间之和 关键路径 路径长度最长的路径 说明 1 完成工程的最短时间是从开始点到完成点的最长路径的长度 2 关键路径的改变会影响整个工期 52 2020 4 7 设活动ai在有向无环图G的有向边上 事件vj的最早发生时间ve j 从源点v0到vj的最长路径长度 ve 0 0 ve j 从源点到顶点j的最长的路径长度 ve k Max ve j dut 事件vj的最迟开始时间vl j 保证汇点vn 1在ve n 1 时刻完成的前提下 事件vj最迟允许开始的时间 vl n 1 ve n 1 从源点到汇点的最长路径长度 vl k 从汇点到顶点k的最短的路径长度 vl j Min vl k dut 7 5 2关键路径 定义和术语 53 2020 4 7 7 5 2关键路径 定义和术语 设活动ai在有向边上 有 活动ai的最早开始时间e i 从源点v0到vj的最长路径长度 e i ve j 活动ai的最迟开始时间l i 是不推迟工程完成的前提下 该活动允许的最迟开始时间 l i vl k dut 活动ai时间余量 l i e i 关键活动 满足l i e i 的活动 关键路径上的活动都是关键活动 54 2020 4 7 7 5 2关键路径 求关键活动 求顶点 事件 vk的最早开始时间 从ve 0 0向汇点方向递推求顶点 事件 vj的最迟开始时间 从vl n 1 ve n 1 向源点递推 ve k Max ve j dut vl j Min vl k dut 在拓扑有序的前提下进行 在逆拓扑有序前提下进行 55 2020 4 7 18 14 16 10 7 8 6 6 0 vl i 18 14 16 7 7 5 4 6 0 ve i V9 V8 V7 V6 V5 V4 V3 V2 V1 i 关键路径是V1 V2 V5 V7 V9和V1 V2 V5 V8 V9 ve k Max ve j dut vl j Min vl k dut e i ve j l i vl k dut 14 16 10 7 7 8 6 6 3 2 0 l i 0 0 0 0 0 0 差 14 16 7 7 7 5 4 6 0 0 0 e i a11 a10 a9 a8 a7 a6 a5 a4 a3 a2 a1 注意 关键路径可有多条 缩短工期必须缩短关键活动所需的时间 56 2020 4 7 如何求关键路径 算法思想 1 输入e条弧 建立AOE网的存储结构 2 从源点v0出发 令ve 0 0 按拓扑有序求其余各顶点的最早发生时间ve i 1 i n 1 如果得到的拓扑有序序列中顶点个数小于网中顶点数n 则说明网中存在环 不能求关键路径 算法终止 否则执行步骤 3 3 从汇点vn出发 令vl n 1 ve n 1 按逆拓扑有序求余各顶点的最迟发生时间vl i n 2 i 2 4 根据各顶点的ve和vl值 求每条弧s的最早开始时间e s 和最迟开始时间l s 若某条弧满足条件e s l s 则为关键活动 57 2020 4 7 下列关于AOE网的叙述中 不正确的是 A 关键活动不按期完成就会影响整个工程的完成时间B 某些关键活动提前完成 那么整个工程将会提前完成C 所有的关键活动提前完成 那么整个工程将会提前完成D 任何一个关键活动提前完成 那么整个工程将会提前完成 58 2020 4 7 9 2 1二叉排序树 二叉排序树 二叉查找树 BinarySortTree BST 空树或具有下列性质的二叉树 根的左子树若非空 则左子树上的所有结点的关键字值均小于根结点的值 根的右子树若非空 则右子树上的所有结点的关键字值均大于根结点的值 它的左右子树同样是二叉排序树 中序遍历二叉排序树可得到一个关键字的有序序列 59 2020 4 7 9 2 1二叉排序树的插入 例 序列45 24 53 12 90构成一棵二叉排序树建BST树过程 一个无序序列可以构造二叉排序树前提 查找失败插入的结点是一个叶子结点 且是查找失败时查找路径上访问的最后一个结点的左孩子或右孩子 插入算法 二叉排序树的存储结构使用链表首先执行查找算法 找出被插入结点的父亲结点 若二叉树为空 则首先单独生成根结点 判断被插结点是其父亲结点的左 右孩子 将结点插入 45 53 90 24 12 60 2020 4 7 9 2 1二叉排序树 删除 设二叉排序树上被删除结点是p PL是p的左子树 PR是p的右子树 p的双亲结点是f 不失一般性 设p是f的左孩子 有三种情况 被删除的结点p是叶子结点 被删除的结点p只有左子树或者只有右子树 被删除的结点既有左子树 也有右子树 对二叉排序树 删去一个结点相当于删去有序序列中的一个记录 61 2020 4 7 9 2 1二叉排序树 删除 1 被删除的结点p是叶子结点 修改双亲结点的指针 令f lchild NULL 例 删除叶子结点12 62 2020 4 7 9 2 1二叉排序树 删除 2 被删除的结点p只有左子树或者只有右子树 令PL或PR直接为其双亲结点f的左子树即可 f lchild p lchild p rchild 例 删除结点24 63 2020 4 7 9 2 1二叉排序树 删除 3 被删除的结点既有左子树 也有右子树 在删去p结点前 中序遍历该二叉树得到的序列为 CLC QLQSLSPPRF 即S是中序遍历序列中被删结点p的直接前驱结点 方法一 令P的左子树为F的左子树 P的右子树为S的右子树 64 2020 4 7 9 2 1二叉排序树 删除 3 被删除的结点既有左子树 也有右子树 在删去p结点前 中序遍历该二叉树得到的序列为 CLC QLQSLSPPRF 即S是中序遍历序列中被删结点p的直接前驱结点 方法二 令p的直接前驱S替代p 再从二叉排序树中删去S 65 2020 4 7 9 2 1二叉排序树 删除举例 删除45 45 12 37 3 24 66 2020 4 7 9 2 1二叉排序树 删除举例 删除45 45 12 3 24 53 100 61 90 78 37 67 2020 4 7 练习 假定一棵二叉排序树采用二叉链表存储结构 其根结点指针为T 设计一个算法输出该二叉排序树中最大的键值和最小的键值 68 2020 4 7 statusmaxmindata if T returnerror p q T while p lchild NULL p p lchild printf Theminimumdatais d p data while q rchild NULL q q rchild printf Theminimumdatais d q data 69 2020 4 7 9 3哈希表 查找表的特点 记录的关键字和在结构中的位置之间无确定关系查找过程是给定值依次和关键字集合中各个关键字的比较查找效率取决于和给定值进行比较的关键字个数 希望不经比较 直接可以找到所查记录哈希函数 在记录的关键字和其在表中位置之间建立一种函数关系 即以f key 作为关键字为key的记录在表中的位置 70 2020 4 7 9 3哈希表定义和术语 冲突 不同关键字得到同一哈希地址 key1 key2 f key1 f key2 同义词 在一个哈希函数中具有相同函数值的不同关键字 哈希表 根据设定的哈希函数H key 和所选中的处理冲突的方法 将一组关键字映象到一个有限的 地址连续的地址集 区间 上 并以关键字在地址集中的 象 作为相应记录在表中的存储位置 这种表被称为哈希表 哈希造表或散列 映象过程 哈希地址或散列地址 所得的存储位置 构造哈希表要注意的问题 考虑选择一个 好 的哈希函数 选择一种处理冲突的方法 71 2020 4 7 9 3 3处理冲突的方法 1开放定址法 Hi H key di MODmi 1 2 k k m 1 H key 为哈希函数 m 哈希表长 di是增量序列 有三种取法di 1 2 m 1 称为线性探测再散列di 12 12 22 22 k2 k m 2 称为二次探测再散列di 伪随机数列 称为随机探测再散列 72 2020 4 7 处理冲突方法举例 例 一组关键字19 14 23 01 68 20 84 27 55 11 10 79 按H key keymod13和线性探测再散列方法处理冲突构造表长为16的哈希表 0123456789101112131415 3 1 1 9 3 1 1 3 4 1 2 1 比较次数 2 0 0 8 2 0 0 2 3 0 1 0 冲突次数 ASLss 1 12 1 6 2 3 3 4 9 2 5 14 01 68 27 55 19 20 84 79 23 11 10 73 2020 4 7 9 3 3处理冲突的方法 例 用哈希函数H key keyMOD13和链地址法处理冲突求一组关键字19 14 23 01 68 20 84 27 55 11 10 79的哈希表 ASLss 1 12 1 6 2 4 3 4 1 75 74 2020 4 7 练习 已知关键字序列为 75 33 52 41 12 88 66 27 哈希表长为10 哈希函数为 H k k 9 解决冲突用线性探测法 请 1 构造出哈希表 2 计算等概率下查找成功的平均查找长度 75 2020 4 7 TypedefstructLNode ElemTypedata 数据域structLnode next 指针域 LNode LinkList 二 结点和单链表的C语言描述 LinkListL L为单链表的头指针 76 2020 4 7 TypedefstructLNode ElemTypedata 数据域structLnode next 指针域 LNode LinkList 二 结点和单链表的C语言描述 LinkListL L为单链表的头指针 77 2020 4 7 三 单链表操作的实现 GetElem L i e 取第i个数据元素 ListInsert L i e 插入数据元素 ListDelete L i e 删除数据元素 ClearList L 重置线性表为空表 CreateList L n 生成含n个数据元素的链表 78 2020 4 7 线性表的操作GetElem L i e 在单链表中的实现 j 1 2 3 79 2020 4 7 因此 查找第i个数据元素的基本操作为 移动指针 比较j和i 单链表是一种顺序存取的结构 为找第i个数据元素 必须先找到第i 1个数据元素 令指针p始终指向线性表中第j个数据元素 80 2020 4 7 StatusGetElem L LinkListL inti ElemType e L是带头结点的链表的头指针 以e返回第i个元素 GetElem L 算法时间复杂度为 O ListLength L p L next j 1 p指向第一个结点 j为计数器 while p 顺指针向后查找 直到p指向第i个元素 或p为空 if p j i returnERROR 第i个元素不存在e p data 取得第i个元素returnOK 81 2020 4 7 线性表的操作ListInsert L i e 在单链表中的实现 有序对改变为和 82 2020 4 7 因此 在单链表中第i个结点之前进行插入的基本操作为 找到线性表中第i 1个结点 然后修改其指向后继的指针 可见 在链表中插入结点只需要修改指针 但同时 若要在第i个结点之前插入元素 修改的是第i 1个结点的指针 83 2020 4 7 StatusListInsert L LinkListL inti ElemTypee L为带头结点的单链表的头指针 本算法 在链表中第i个结点之前插入新的元素e LinstInsert L 算法的时间复杂度为 O ListLength L p L j 0 while p i大于表长或者小于1 84 2020 4 7 s LinkList malloc sizeof LNode 生成新结点s data e s next p next p next s 插入returnOK s p 85 2020 4 7 线性表的操作ListDelete L i e 在链表中的实现 有序对和改变为 86 2020 4 7 在单链表中删除第i个结点的基本操作为 找到线性表中第i 1个结点 修改其指向后继的指针 q p next p next q next e q data free q p q 87 2020 4 7 StatusListDelete L LinkListL inti ElemType e 删除以L为头指针 带头结点 的单链表中第i个结点 ListDelete L 算法的时间复杂度为 O ListLength L p L j 0 while p next 删除位置不合理 q p next p next q next 删除并释放结点e q data free q returnOK 88 2020 4 7 操作ClearList L 在链表中的实现 voidClearList ClearList free p 算法时间复杂度 O ListLength L 89 2020 4 7 逆位序输入n个数据元素的值 建立带头结点的单链表 操作步骤 一 建立一个 空表 二 输入数据元素an 建立结点并插入 三 输入数据元素an 1 建立结点并插入 an an an 1 四 依次类推 直至输入a1为止 90 2020 4 7 voidCreateList L LinkList L intn 逆序输入n个数据元素 建立带头结点的单链表 CreateList L 算法的时间复杂度为 O Listlength L L LinkList malloc sizeof LNode L next NULL 先建立一个带头结点的单链表 for i n i 0 i p LinkList malloc sizeof LNode scanf 插入 91 2020 4 7 时间复杂度为O La length Lb length 两个有序线性表合并为一个有序线性表的算法 voidMergeList L LinkList 92 2020 4 7 5 3 2稀疏矩阵 稀疏矩阵 设m行n列的矩阵含t个非零元素 则 t m n 称为稀疏因子 通常认为 0 05的矩阵为稀疏矩阵 抽象数据类型稀疏矩阵的定义 书96页稀疏矩阵的压缩存储稀疏矩阵中非零元素位置无规律记住非零元素的行i 列j 值aij稀疏矩阵中存在多个非零元素 三元组的C语言描述typedefstruct inti j ElemTypee Triple 三元组顺序表的C语言描述 defineMAXSIZE125000typedefstruct Tripledata MAXSIZE 1 intmu nu tu TSMatrix 93 2020 4 7 三元组表表示的稀疏矩阵的转置 设M和T分别是MM和TT的三元组表 如何由M得到T 将矩阵行列值 即m和n 相互交换将每个三元组中的i和j对换重排三元组的次序 94 2020 4 7 StatusTransposeSMatrix TSMatrixM TSMatrix TransposeSMatrix 三元组表表示的稀疏矩阵转置算法1 评价 O nu tu 优点 节省空间 tu mu nu适用 95 2020 4 7 三元组表表示的稀疏矩阵转置方法2 思想 按M data的三元组次序转置 再将三元组置入T中适当的位置 问题 转置前需知MM的每列中非零元素个数及第一个非零元素在T data中的位置 解决方案 设num和cpot两个向量 num col 矩阵MM的第col列中非零元素的个数 cpot col 矩阵MM第col列第一个非零元在T data中的位置 cpot 1 1 cpot col cpot col 1 num col 1 2 col M nu StatusFastTransposeSMatrix TSMatrixM TSMatrix TransposeSMatrix时间复杂度为O nu tu 若tu mu nu则为O mu nu 与经典算法相同 多用了两个辅助向量 三元组表表示的稀疏矩阵转置方法2 97 2020 4 7 稀疏矩阵的压缩存储 行逻辑链接顺序表 需求 随机存取任一行的非0元方法 记住矩阵每一行第一个非0元在三元组表中的位置设数组rpos 1 n 矩阵中