计算机系课件之数据结构(C语言)(ppt 148页).ppt

广东交通职业基数学院计算机系 课件设计 数据结构 C语言 DATASTRUCTURE 教材数据结构 C语言 曲建民刘元红郑陶然清华大学出版社 参考教材1数据结构 C语言版 严蔚敏吴伟民清华大学出版社2数据结构题集 C语言版 严蔚敏吴伟民清华大学出版社 课程特点及课时分配 难度大综合性强必须下苦功学习课程说明考试每周4节 共20周评分标准 平时成绩20 包括考勤 课堂回答问题等 期中成绩30 期末成绩50 教学内容 第一章绪论第二章线性表第三章栈和队列第四章数组和串第五章树第六章图第七章内部排序第八章查找第九章文件 第一章绪论 1 1什么是数据结构1 2基本概念和术语1 3运算 算法和算法分析 主要知识点 数据处理的种类和能力 数据 数值数据 数 整数 实数 非数值数据 字符字符串文字图形图象声音 数据 客观对象的符号表示数学中的整数 实数 课程名 地名 书名 1 1什么是数据结构 数据结构要解决的问题 数值问题与非数值问题 1 数值问题例1已知 游泳池的长len和宽wide 求面积area 设计求解问题的方法 编程main intlen wide area scanf d d n 建模型 问题涉及的对象 游泳池的长len宽wide 面积area 对象之间的关系 area len wide 1 1什么是数据结构 学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82 06 01广州56100计算机200102石磊男83 12 21汕头51200计算机100202李梅女83 02 23阳江53200计算机200301马耀先男82 07 12广州50900计算机3 2 非数值问题例2已知某级学生情况 要求分班按入学成绩排列顺序 在这类文档管理的数学模型中 计算机处理的对象之间通常存在着一种最简单的线性关系 这类数学模型称为线性模型 1 1什么是数据结构 城市间交通网问题 1 1什么是数据结构 数据结构的研究问题 非数值数据之间的结构关系 及如何表示 如何存储 如何处理 本课程讨论的问题 应用中常用的几种数据间的结构关系 及如何表示 如何存储 如何处理 1 1什么是数据结构 数据 客观对象的符号表示 例如 学号 姓名 班名都是数据 数据元素 数据的基本单位 相当于 记录 在计算机程序中通常作为一个整体考虑和处理数据项 相当于记录的 域 是数据的不可分割的最小单位 如 学号数据对象 性质相同的数据元素的集合 例如 所有班名相同的记录集合数据结构 是相互间存在关系的数据元素集合 1 2基本概念和术语 对每种数据结构 主要讨论如下两方面的问题 1 数据的逻辑结构 数据结构的基本操作 2 数据的存储结构 数据结构基本操作的实现 数据的逻辑结构 数据之间的结构关系 是具体关系的抽象 数据结构的基本操作 指对数据结构的加工处理 数据的存储结构 物理结构 数据结构在计算机内存中的表示 数据结构基本操作的实现 基本操作在计算机上的实现 方法 1 2基本概念和术语 数据的逻辑结构通常有四种基本结构 集合线性结构树型结构图结构 1 2基本概念和术语 一 运算加工型运算插入运算删除运算更新运算应用型运算查找运算读取运算 1 3运算 算法和算法分析 二 算法及其描述算法是对求解某个问题的步骤的一种描述方法或操作序列 算法的基本特征 1 输入 0个或多个输入 2 输出 1个或多个输出 3 有穷性 算法必须在有限步内结束 4 确定性 组成算法的操作必须清晰无二义性 5 可行性 组成算法的操作必须能够在计算机上实现 求两个正整数m n中的最大数MAX的算法 1 若m n则max m 2 若m n则max n 例 1 3运算 算法和算法分析 描述算法的书写规则 所有算法均以函数形式给出 算法的输入数据来自参数表参数表的参数在算法之前均进行类型说明有关结点结构的类型定义 以及全局变量的说明等均在算法之前进行说明 1 3运算 算法和算法分析 评价算法标准算法的正确性 易读性 可维护性 健壮性 高效率等 算法时间复杂度T n 本课程采用以求解问题的基本操作的执行次数作为算法时间的度量算法的空间复杂度S n 一个算法所需要辅助存储空间的多少为空间复杂度 O n3 称为矩阵相乘算法时间复杂度 O n3 表示矩阵相乘算法执行时间与n3成正比 即O n3 与n3同一数量级 n阶矩阵相乘的算法 For i 1 i n i For j 1 j n j c i j 0 For k 1 k n k c i j a i k b k j 例 1 3运算 算法和算法分析 有些算法 基本操作执行次数与问题的输入数据有关 这时可考虑 1 算法平均时间复杂度 2 算法在最坏情况下的时间复杂度 算法的时间复杂度一般来说 设算法中基本操作的执行次数是问题规模n的某个函数f n 算法的时间复杂度记作 T n O f n 它表示随问题规模n的增大 算法执行时间的增长率与f n 的增长率相同 1 3运算 算法和算法分析 算法的时间复杂度为O N3 1 3运算 算法和算法分析 2算法空间复杂度在本课程中 用执行算法所需的辅助空间的大小作为算法所需空间的度量 设执行算法所需的辅助空间是问题规模n的某个函数g n 则算法空间复杂度记作 S n O g n 表示算法辅助空间的增长率与g n 的增长率相同 1 3运算 算法和算法分析 计算解法1先计算x的幂 存于power 中 再分别乘以相应的系数 defineN100floatevaluate floatcoef floatx intn floatpower N f inti for power 0 1 i 1 i n i power i x power i 1 for f 0 i 0 i N i f f coef i power i return f 1 3运算 算法和算法分析 例 问题规模为n 算法时间复杂度 O n 空间复杂度 O N 解法2 defineN100floatevaluate floatcoef floatx intn floatf inti for f coef n i n 1 i 0 i f f x coef i return f 时间复杂度为O n 空间复杂度为O 1 1 3运算 算法和算法分析 第二章线性表 2 1线性表的定义和基本运算2 2线性表的顺序存储结构2 3线性表的链式存储结构2 3 1单链表2 3 2循环链表2 3 3双向链表2 4线性表的应用举例 主要内容 第二章线性表 线性结构特点 在数据元素的非空有限集中存在唯一的一个被称作 第一个 的数据元素存在唯一的一个被称作 最后一个 的数据元素除第一个外 集合中的每个数据元素均只有一个前驱除最后一个外 集合中的每个数据元素均只有一个后继 2 1线性表的逻辑结构定义 一个线性表是n个数据元素的有限序列 例英文字母表 A B C Z 是一个线性表 数据元素 特征 元素个数n 表长度 n 0空表1 i n时ai的直接前驱是ai 1 a1无直接前驱ai的直接后继是ai 1 an无直接后继元素同构 且不能出现缺项 2 2线性表的顺序存储结构顺序表 定义 用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法 LOC ai LOC a1 i 1 LLOC ai 1 LOC ai L其中 L 一个元素占用的存储单元个数LOC ai 线性表第i个元素的地址特点 实现逻辑上相邻 物理地址相邻实现随机存取实现 可用C语言的一维数组实现 typedefintDATATYPE defineM1000DATATYPEdata M 例typedefstructcard intnum charname 20 charauthor 10 charpublisher 30 floatprice DATATYPE DATATYPElibrary M 数据元素不是简单类型时 可定义结构体数组 动态申请和释放内存Datatype pData DATATYPE malloc M sizeof DATATYPE free pData 插入定义 线性表的插入是指在第I 1 i n 1 个元素之前插入一个新的数据元素x 使长度为n的线性表 变成长度为n 1的线性表 需将第i至第n共 n i 1 个元素后移 Ch2 1 c x 算法时间复杂度T n 设Pi是在第i个元素之前插入一个元素的概率 则在长度为n的线性表中插入一个元素时 所需移动的元素次数的平均次数为 算法 删除定义 线性表的删除是指将第i 1 i n 个元素删除 使长度为n的线性表 变成长度为n 1的线性表 需将第i 1至第n共 n i 个元素前移 Ch2 2 c 算法评价设Qi是删除第i个元素的概率 则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为 故在顺序表中插入或删除一个元素时 平均移动表的一半元素 当n很大时 效率很低 算法 顺序存储结构的优缺点优点逻辑相邻 物理相邻可随机存取任一元素存储空间使用紧凑缺点插入 删除操作需要移动大量的元素预先分配空间需按最大空间分配 利用不充分表容量难以扩充 2 3线性表的链式存储结构特点 用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai 除存储本身信息外 还需存储其直接后继的信息结点数据域 元素本身信息指针域 指示直接后继的存储位置 例线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 43 13 1 NULL 37 7 19 25 头指针 实现 typedefstructnode datatypedata structnode link JD JD h p p 表示p所指向的结点 p data p data表示p指向结点的数据域 p link p link表示p指向结点的指针域 生成一个JD型新结点 p JD malloc sizeof JD 系统回收p结点 free p 2 3 1线性链表定义 结点中只含一个指针域的链表叫 也叫单链表 头结点 在单链表第一个结点前附设一个结点叫 头结点指针域为空表示线性表为空 单链表的基本运算查找 查找单链表中是否存在结点X 若有则返回指向X结点的指针 否则返回NULL算法描述 算法评价 插入 在线性表两个数据元素a和b间插入x 已知p指向a s link p link p link s 算法描述 算法评价 算法描述 算法评价 删除 单链表中删除b 设p指向a p link p link link 动态建立单链表算法 设线性表n个元素已存放在数组a中 建立一个单链表 h为头指针 算法描述 算法评价 Ch2 3 c 单链表特点它是一种动态结构 整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取 查找速度慢 循环链表 circularlinkedlist 循环链表是表中最后一个结点的指针指向头结点 使链表构成环状特点 从表中任一结点出发均可找到表中其他结点 提高查找效率操作与单链表基本一致 循环条件不同单链表p或p link NULL循环链表p或p link H 双向链表 doublelinkedlist 单链表具有单向性的缺点结点定义 typedefstructnode datatypeelement structnode prior next JD p prior next p p next proir voiddel dulist JD p p prior next p next p next prior p prior free p 删除 算法描述 算法评价 T n O 1 p prior next p next p next prior p prior voidins dulist JD p intx JD s s JD malloc sizeof JD s element x s prior p prior p prior next s s next p p prior s 算法描述 算法评价 T n O 1 插入 1循环链表的概念循环链表是线性表的另一种链式存储结构 它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点2循环链表图示 a 非空表 b 空表 2 3 2循环链表 单向循环链表说明 在解决某些实际问题时循环链表可能要比线性链表方便些 如将一个链表链在另一个链表的后面 循环链表与线性链表操作的主要差别是算法中循环结束的条件不是p或p link是否为NULL 而是它们是否等于首指针 对循环链表 有时不给出头指针 而是给出尾指针 a a1 an 给出尾指针的循环链表 2 3 2循环链表 p a link q b link a link q link b link p free q 2 3 2循环链表 1双向链表的概念 a 结点图示 存储数据元素data 存储后继结点的地址next 存储前趋结点的地址prior 双向链表中 每个结点有两个指针域 一个指向直接后继元素结点 另一个指向直接前趋元素结点 2 3 3双向链表 2双向链表图示 head typestructdulnode pointer Typestructdulnode datatypedata pointerprior next dulnode 2 3 3双向链表 在双向链表中删除结点时指针变化情况 在双向链表中插入一个结点时指针的变化情况 p p 3 双向链表的基本操作算法 2 3 3双向链表 p 1 插入操作算法 在p所指结点之后插入q结点的过程 q NODE malloc sizeof NODE q data x q rlink p rlink q llink p p rlink q q rlink llink q 2 3 3双向链表 2 删除操作算法 p llink rlink p rlink p rlink llink p llink free p 2 3 3双向链表 2 4线性表的应用举例一元多项式的表示及相加一元多项式的表示 可用线性表P表示 但对S x 这样的多项式浪费空间 用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构 也可以用单链表 单链表的结点定义 typedefstructnode intcoef exp structnode next JD 一元多项式相加 设p q分别指向A B中某一结点 p q初值是第一结点 运算规则 Ch2 7 c 算法描述 数据结构 第三章栈和队列 主要内容 栈的定义栈的存储结构及其运算的实现 栈是限定仅能在表尾一端进行插入 删除操作的线性表 a1 a2 ai 1 ai ai 1 an 插入 删除 一什么是栈 3 1 1栈的定义 第一个进栈的元素在栈底 最后一个进栈的元素在栈顶 第一个出栈的元素为栈顶元素 最后一个出栈的元素为栈底元素 不含元素的栈称为空栈 出栈Pop 进栈Push 栈顶 栈底 二 栈的逻辑结构 top bottom 空栈 top bottom bottom bottom A A B C D E A B 栈操作图示 A进栈 BCDE进栈 EDC出栈 C D E 栈的特点后进先出LIFO 入栈与出栈 思考 假设有A B C三个元素进S栈的顺序是A B C 写出所有可能的出栈序列 CBA ACB ABC CAB BAC BCA 如果是4个元素 那么它不可能的出栈序列有哪些 可能的出栈序列 12431324134221342143231424313241321434214321 不可能出现的出栈序列 2413312434124123423142134312 栈是一种线性表 它的特点是A 设用一维数组A 1 n 来表示一个栈 令A n 为栈底 用整型变量T指示当前栈顶位置 A T 为栈顶元素 往栈中推入 PUSH 一个新元素时 变量T的值B 从栈中弹出 POP 一个元素时 变量T的值C 设栈空时 有输入序列a b c 经过PUSH POP PUSH PUSH POP操作后 从栈中弹出的元素序列是D 变量T的值是E A 1 先进先出2 后进先出3 进优于出4 出优于进5 随机进出B C 1 加12 减13 不变4 清05 加26 减2D 1 a b2 b c3 c a4 b a5 c b6 a cE 1 n 12 n 23 n4 n 15 n 2 水平考试试题 设有四个数据元素a1 a2 a3和a4 对它们进行栈操作 在进栈操作时 按a1 a2 a3 a4次序每次进入一个元素 假设栈的初始状态都是空 现要进行栈操作是进栈两次 出栈一次 再进栈两次 出栈一次 这时 第一次出栈得到的元素是A 第二次出栈得到的元素是B经操作后 最后在栈中的元素还有C个 供选择的答案A 1 a12 a23 a34 a4B 1 a12 a23 a34 a4C 1 12 23 34 0 水平考试试题 栈属于加了限制条件的线性结构 栈是后进先出的线性表 进栈和出栈只能从栈的一个端点进行 栈中的元素个数可以是0 此时是空栈 栈的元素的个数是可以变化的 可以是多个 但不能是无穷多个 每个栈中的元素的类型相同 栈的特性 栈的应用 实现数制转换实现函数的递归行编辑 接受用户从终端输入的程序或数据 并存入用户的数据区表达式求值 一个程序设计语言应该允许设计者根据需要用表达式描述计算过程 编译器则应该能分析表达式并计算出结果 Flash演示 三栈的基本操作 初始化IniStack S 构造一个空栈S 准备存放数据 进栈操作Push S x 将数据元素x插入栈S 使x成为S的栈顶元素 出栈操作Pop S 当栈不空时返回栈顶元素为该函数的值 然后删除栈顶元素 取栈顶元素GetTop S 当栈不空时返回栈顶元素为该函数的值 但栈顶保持不变 判栈空EmptyStack S 若S为空栈则该函数值为1 否则为0 一 栈的顺序存储结构 用一个一维数组和一个整型变量来实现 structstack datatypearray maxlen inttop 栈数组array maxlen 用来存放栈中所有元素 整型变量top的整数值表示栈顶元素在数组array中的位置 也称为栈顶指针 3 1 2栈的存储结构及其运算的实现 约定栈顶指针指向向栈顶元素的位置 顺序栈的图示 栈空 栈满 Top 1 Top maxlen 1 1 初始化栈viodinitstack structstacks s top 1 2 进栈操作viodPush structstacks datatypex s top s top 1 s array top x 3 出栈操作intpop structstacks return array s top s top 栈在运算过程中可能发生 溢出 现象 上溢下溢 2 进栈操作viodPush structstacks datatypex s top s top 1 s array top x if s top MAXlen 1 error 栈满 else 3 出栈操作intpop structstacks return array s top s top if s top 1 Error emptystack else 顺序栈的不足 存在栈满以后就不能再进栈的问题 这是因为用了定长的数组存储栈的元素 解决方法 使用链式存储结构 二 栈的链式存储和实现栈的链式存储结构 也称链栈 其各结点的结构与单链表中的结点结构完全相同 如图所示 在前面学习了线性链表的插入删除操作算法 不难写出链式栈初始化 进栈 出栈等操作的算法 结点结构定义 Typedefstructnode elemtypedata structnode next node pointer 1 初始化栈Voidinitstack pointers s null 进栈前进栈后 2 进栈 进栈算法Voidpush pointers datatypex p pointer malloc sizeof node p data x p next s next s next p 出栈前出栈后 3 出栈 出栈算法 Datatypepop pointers if s next null return null else p s next x p data s next p next free p return x 3 2 1队列的定义 队列是限定仅能在表头进行删除 表尾进行插入的线性表 a1 a2 ai 1 ai ai 1 an 插入 删除 3 2队列 a1a2a3 an 入队列 队头 队尾 出队列 队列的示意图 队列的特点先进先出 说明 第一个入队的元素在队头 最后一个入队的元素在队尾 第一个出队的元素为队头元素 最后一个出队的元素为队尾元素 3 2队列 rear front J1 J2 rear front J2 a 空队列 b J1 J2相继入队列 c J1出队 d J3 J4和J5相继入队之后 J2出队 rear front rear front J5 J4 J3 front rear均为整数用箭头指示只是为了直观 3 2队列 3 2 2队列的基本操作1 初始化操作initQueue Q 建立一个空队列Q 准备存放数据 2 入队操作enQueue Q x 将数据x插入到队列Q的队尾 队列的长度加1 3 出队操作outQueue Q 当队列为空时 返回队列头元素的值 同时删除队列头元素 队列的长度减1 4 取队头元素操作GetQueue Q 当队列为空时 返回队列头元素的值 但不删除队列头元素 5 判空操作 若队列为空 则返回的值为1 否则为0 3 2队列 3 2 3队列的存储结构及其基本运算的实现1 链式存储结构 3 2队列 front rear 空链队列 front 链队列图示 structnode 链队列结点的类型定义 intdata structnode link typedefstructnodeNODENODE front rear 1 进队列运算 Voidaddqlink intx NODE p p NODE malloc sizeof NODE p data x p link NULL rear link p rear p 3 2队列 2 出队列运算 NODE deleqlink NODE p if front rear return NULL p front link front link p link if front link NULL rear front return p 3 2队列 3 队列的应用 1 解决计算机主机与外设不匹配的问题 2 解决由于多用户引起的资源竞争问题 3 离散事件的模拟 模拟实际应用中的各种排队现象 4 用于处理程序中具有先进先出特征的过程 在操作系统课程中会讲到 3 2队列 2 顺序存储结构将front和rear两个整型变量作为c语言结构体的两个成员 该结构体定义如下 Structsq queue Datatypedata maxlen Intfront rear 3 2队列 1 初始化运算initqueue structsq queuesq 得到一个长度为maxsize的空队列sq 此时sq front 0 sq rear 0 2 进队列运算enqueue structsq queuesq datatypex sq rear sq rear 1 sq rear data x3 出队列运算outqueue structsq queuesq sq front sq front 14 读队列头元素运算gethead structsq queuesq 返回的函数值为sq rear data sq队列没有改变5 判断队列是否是空emptyqueue structsq queuesq 3 2队列 3 循环队列 b 队空 c 队满 队空 队满都有front rear J7 3 2队列 有两种方法 1 另设一个标志位以区分队空 队满 2 少用一个存储单元 队满条件 front rear 1 front d 3 2队列 1 初始化操作功能 建一个空队列Q 算法 Intqueue MAX Intfront rear intInitQueue Sq 构造一个空队列Qfront 0 rear 0 Return 1 循环队列的基本操作算法 建一个空队列Q 3 2队列 2 入队操作功能 将元素x插入队尾 元素x入队前 元素x入队后 3 2队列 求余运算 intinsert queue intx 入队列 if rear 1 MAX front return 0 rear rear 1 MAX queue rear x return 1 3 出队操作功能 删除队头元素 3 2队列 intdel queue 出队列 if rear front return 0 front front 1 MAX return queue front 小结和作业 作业 课后习题1 2 3实训题 参见 第四章数组和串 主要内容 4 1数组4 1 1数组的概念和运算4 1 2数组的顺序存储和访问4 1 3矩阵的压缩存储4 2串4 2 1串的基本概念4 2 2串的基本运算4 2 3串的存储结构 4 1 1数组的概念运算数组是由一组个数固定 类型相同的数据元素组成阵列 以二维数组为例 二维数组中的每个元素都受两个线性关系的约束即行关系和列关系 在每个关系中 每个元素aij都有且仅有一个直接前趋 都有且仅有一个直接后继 在行关系中aij直接前趋是aij 1aij直接后继是aij 1在列关系中aij直接前趋是ai 1jaij直接后继是ai 1j 4 1数组 二维数组也可看作这样的线性表 其每一个数据元素也是一个线性表A 0 1 2 3 4 p 其中每一个数据元素 j是一个列向量的线性表 j a0j a1j a2j a3j am 1j 或 i是一个行向量的线性表 i ai0 ai1 ai2 ai3 ain 1 4 1数组 数组的基本操作访问 给定一组下标 存取相应的数据元素 修改 给定一组下标 修改相应数据元素中的某个数据项的值 操作方法根据其存储结构决定 4 1数组 4 1 2数组的顺序存储和访问一维数组在内存中的存放很简单 只要顺序存放在连续的内存单元即可 二维数组 如何用顺序结构表示 内存地址是一维的 而数组是二维的 要将二维数组挤入一维的地址中 有两个策略 以行为主序 C语言使用 以列为主序 4 1数组 设A是一个具有m行n列的元素的二维数组 以行为主序的方式 以列为主序的方式 4 1数组 4 1 3矩阵的压缩存储一特殊矩阵的压缩存储二稀疏矩阵的压缩存储1三元组表的存储结构2十字链表的存储结构 4 1数组 数组元素存储地址的计算假设二维数组A每个元素占用s个存储单元 Loc aij 为元素aij的存储地址 Loc a00 是a00存储位置 也是二维数组A的基址 若以行序为主序的方式存储二维数组 则元素aij的存储位置可由下式确定 Loc aij Loc a00 n i j s若以列序为主序的方式存储二维数组 则元素aij的存储位置可由下式确定 Loc aij Loc a00 m j i s一般在程序设计过程中 一维数组和二维数组使用较普遍 超过二维以上的多维数组使用相对较少 对于高维数组的顺序存储方法 可以将二维的情形加以推广便能够得到 4 1数组 矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象 一个m行n列的矩阵是一平面阵列 有m n个元素 可以对矩阵作加 减 乘等运算 只有少数程序设计语言提供了矩阵运算 通常程序员是用二维数组存储矩阵 由于这种存储方法可以随机地访问矩阵的每个元素 因而能较为容易地实现矩阵的各种运算 4 1数组 应用中常遇到一些阶数很高的矩阵 矩阵中有许多值相同的元素或零元素 二维数组存储矩阵会浪费很多的存储单元 例如 设一个1000 1000的矩阵中有800个非零元素 若用二维数组存储需要106个存储单元 因此 需要使用高效的存储方法 减少数据的存储量 即对原矩阵 根据数据分布特征进行压缩存储 本章将讨论两类矩阵的压缩存储 1特殊矩阵的压缩存储2稀疏矩阵的压缩存储 4 1数组 一特殊矩阵值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例 对称矩阵 上 下 三角矩阵都是特殊矩阵 4 1数组 特殊矩阵压缩存储 以对称矩阵为例 对称矩阵是满足下面条件的n阶矩阵 aij aji0 i j n 1 对称矩阵元素可以只存储下三角部分 共需n n 1 2个单元的空间 三角矩阵的存储方式类似 4 1数组 以一维数组sa 作为n阶对称矩阵A的存储结构 A中任意一元素aij与它的存储位置sa k 之间存在着如下对应关系 例如 a53在sa 中的存储位置是 k 5 5 1 2 3 18sa 18 a53 4 1数组 压缩存储的对称矩阵的取值算法intget M inti intj if i j return sa i i 1 2 j elsereturn sa j j 1 2 i 压缩存储的对称矩阵的赋值算法voidassign M inti intj intvalue if i j sa i i 1 2 j value elsesa j j 1 2 i value 4 1数组 带状矩阵所有非0元素都集中在以主对角线为中心的带状区域 半带宽为d时 非0元素有 2d 1 n 1 d d个 a00a01a02000000000a10a11a12a1300000000a20a21a22a23a2400000000a31a32a33a34a3500000000a42a43a44a45a4600000000a53a54a55a56a5700000000a64a65a66a67a6800000000a75a76a77a78a7900000000a86a87a88a89a81000000000a97a98a99a910a91100000000a108a109a1010a1011000000000a119a1110a1111 d 4 1数组 为计算方便 认为每一行都有2d 1个非0元素 若少则用0补足 所以 存放矩阵的数组sa 有n 2d 1 个元素数组元素sa k 与矩阵元素aij之间有关系k i 2d 1 d j i 4 1数组 0a00a01a10a11a12a21a22a23a32a33a34a43a440 压缩存储的带状矩阵的取值算法intget Md inti intj if abs i j d return sa i 2 d 1 d j i elsereturn 0 压缩存储的带状矩阵的赋值算法voidassign Md inti intj intvalue if abs i j d sa i i 1 2 j value 4 1数组 稀疏矩阵1什么是稀疏矩阵有较多值相同元素或较多零元素 且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵 例 A有42 6 7 个元素有8个非零元素 4 1数组 2稀疏矩阵的压缩存储 只讨论有较多零元素矩阵的压缩存储 1 三元组表 i j aij A 0 1 12 0 2 9 2 0 3 2 5 14 3 2 24 4 1 18 5 0 15 5 3 7 加上行 列数6 7 表示非零元的三元组 4 1数组 2 三元组顺序表假设以顺序存储结构来表示三元组表 则可得稀疏矩阵的一种压缩存储方式 我们称之为三元组顺序表 稀疏矩阵的三元组顺序表的类型定义structnode introw col 非零元的行下标和列下标intvalue 非零元值 typedefstructnodeNODE NODEma MAX ma 0 用于存储矩阵行数 列数 非零元个数 用于存储非零元三元组的结构 4 1数组 A的三元组顺序表图示 例如ma 1 row 0 ma 1 col 1 ma 1 value 12 4 1数组 3 转置运算算法转置运算是一种最常用的矩阵运算 对于一个m行n列的矩阵A 它的转置矩阵B是一个n行m列的矩阵 例如 下图中的矩阵A和B互为转置矩阵 4 1数组 转置运算算法 4 1数组 矩阵B 矩阵A 分析 1 将矩阵的行列数的值交换 2 将每一个三元组的i和j相互调换 3 重排三元组之间的次序 4 1数组 转置运算算法按照A的列序来进行转换的基本思想对ma 从头至尾扫描 第一次扫描时 将ma 中列号为0的所有元组交换行列值后 依次赋值到mb 中第二次扫描时 将ma 中列号为1的所有元组交换行列值后 依次赋值到mb 中依此类推 直至将ma 的所有三元组赋值到mb 中 4 1数组 ijv ijv 20 3 1418 02 3 5015 0515 0112 1012 4118 029 209 3224 2324 53 7 35 7 2514 5214 A矩阵 B矩阵 对A六次扫描完成转置运算 第一次扫描查找第0列元素 第一次扫描结束 第二次扫描结束 第二次扫描查找第1列元素 第三次扫描查找第2列元素 第四次扫描查找第3列元素 第五次扫描查找第4列元素 第六次扫描查找第5列元素 转置运算算法图示 012345678 678 768 4 1数组 转置算法 采用三元组表存储表示 求稀疏矩阵A的转置矩阵Binttranspose NODEma NODEmb inti j k if ma 0 value 0 return 0 mb 0 row ma 0 col mb 0 col ma 0 row mb 0 value ma 0 value k 1 k为当前三元组在mb 存储位置 下标 for i 0 i ma 0 col i 找ma 中第i列所有非0元素for j 1 j ma 0 value j j为扫描ma 的 指示器 j 指向 三元组称为当前三元组if ma j col i mb k row ma j col mb k col ma j row mb k value ma j value k return 1 4 1数组 时间复杂度分析算法的基本操作为将ma 中的三元组赋值到mb 是在两个循环中完成的 故算法的时间复杂度为O n t 其中n为A矩阵的列数 t为非0元素个数 当非零元的个数t和矩阵元素个数m n同数量级时 即t m n 转置运算算法的时间复杂度为O n m n 由此可见 在这种情况下 用三元组顺序表存储矩阵 虽然可能节省了存储空间 但时间复杂度提高了 因此算法仅适于t m n的情况 该算法效率不高的原因是 对为实现A到B的转置 该算法对ma 进行了多次扫描 其特点是 以B矩阵的三元组为中心 在A矩阵的三元组中通盘查找合适的结点置入mb k 中能否在对ma 一次扫描的过程中 完成A到B的转置 4 1数组 十字链表的存储结构以三元组表示的稀疏矩阵 在运算中 若非0元素的位置发生变化 会引起数组元素的频繁移动 为解决这