严蔚敏清华分享：快速转置算法及数据结构理解

在"方法二(快速转置的算法)-数据结构PPT--严蔚敏(清华大学)"中，讨论了如何高效地进行矩阵转置操作。这个算法的关键在于理解矩阵A的稀疏特性，即并非所有元素都是非零的。算法的核心思路是利用三元组表a.data的次序来直接转换，其中每个三元组包含非零元素的位置和值。为了实现这一过程，引入了两个辅助向量num[]和cpot[]： 1. num[]数组用于统计矩阵A中每一列（在转置后为每一行）非零元素的数量，这对于确定转置后新矩阵B中相应行首元素的位置至关重要。 2. cpot[]数组则记录了A中每一列的第一个非零元素在转置矩阵B的data部分应插入的位置。 算法操作步骤如下： - 首先计算每列非零元素个数，并存储在num[]中。 - 然后，遍历A的三元组表，根据非零元素数量信息，直接将元素插入到转置矩阵B的data部分的cpot[]指示的位置。 这种方法的优势在于，由于预先确定了非零元素的插入位置，转置过程不需要额外的搜索操作，从而提高了效率，特别适合于稀疏矩阵的处理。 同时，这份PPT还提及了数据结构在实际问题中的应用，如电话簿查询、图书馆检索系统、教师资料管理等，强调了数据结构的灵活性，无论是有限还是无限的对象都可以通过适当的数据结构来组织和管理。 在讲解数据结构时，提到了抽象数据类型(ADT)的概念，它超越了系统预定义的数据类型，允许用户自定义。ADT由值域和一组操作组成，其核心特点包括抽象和信息隐蔽。抽象使得设计具有通用性，而信息隐蔽隐藏了数据的具体存储方式和操作实现，用户仅通过接口进行操作。 例如，ADT中整数数据类型的定义包括其数学概念和基本运算。在C语言中，需要注意数组下标的零基索引，即第i个元素的索引为i-1。此外，顺序存储的线性表虽提供方便的存取，但其插入和删除操作效率较低，因为可能涉及大量元素的移动，且数组大小固定可能导致空间浪费和扩展困难。 这个PPT内容涵盖了矩阵转置的高效算法、数据结构的应用实例以及抽象数据类型的基本理论，为理解和应用数据结构提供了深入且实用的视角。