第四章数据结构——数组

格式：ppt
大小：511.50 KB
文档页数：32

下载文档原格式

天大《数据结构》学习笔记二

ቤተ መጻሕፍቲ ባይዱ据结构—学习笔记二
三、二维数组－矩阵 1、C 语言中的二维数组： 1 . 1 定义：i n tu [ 3 ] [ 2 ] ; i n tv [ 2 ] [ 3 ] ; 1 . 2 使用：u [ 0 ] [ 1 ] = 7 ; v [ 1 ] [ 2 ] = 6 ; C 语言中二维数组的行下标、列下标都从 0 开始。二维数组的元素是按行存放。 1 . 3 本课程的约定：行数为 m + 1 ，列数为 n + 1 ; 第[0]行与第[0]列一般不用。 2、二维数组的输入与输出： 2 . 1 输入： f o r ( i = 1 ; i < = m ; i + + ) f o r ( j = 1 ; j < = n ; j + + ) s c a n f ( “% d ”, & v [ i ] [ j ] ) ; 2 . 2 输出：f o r ( i = 1 ; i < = m ; i + + ) { f o r ( j = 1 ; j < = n ; j + + ) p r i n t f ( “% d ”, v [ i ] [ j ] ) p r i n t f ( “\ n ”) } 3、矩阵相加： 3 . 1 条件：两个矩阵的行数与列数均相同。 3 . 2 程序： { …… f o r ( i = 1 ; i < = m ; i + + ) f o r ( j = 1 ; j < = n ; j + + ) w [ i ] [ j ] = u [ i ] [ j ] + v [ i ] [ j ] } 4、矩阵相乘： 4 . 1 条件：第一个矩阵的列数等于第二个矩阵的行数。 4 . 2 程序： { …… f o r ( i = 1 ; i < = m ; i + + ) f o r ( j = 1 ; j < = k ; j + + ) { s = 0 ; f o r ( t = 1 ; t < = n ; t + + ) s = s + u [ i ] [ t ] * v [ t ] [ j ] ; w [ i ] [ j ] = s ; } } 5、课后练习：编程：求已知矩阵的最大值、最小值及其相应的位置。

《c语言教学资料》4数组

部分初始化
如果只对部分元素进行初始化，则未初始化的元素将自动赋值为0。例如，`int a[3][4] = {{1},{2}}`，则只有第一行和第二行的第一列被初始化，其余元素为0。
初始化列表
多维数组的初始化
多维数组的引用
引用方式
多维数组的引用方式与一维数组类似，使用索引来访问元素。例如，`a[i][j]`表示第i行第j列的元素。
二维数组在各种算法和数据结构中都有广泛的应用，例如矩阵运算、动态规划等。
详细描述
二维数组可以用于实现各种算法和数据结构，例如矩阵运算、动态规划等。在矩阵运算中，二维数组可以方便地存储和操作矩阵数据。在动态规划中，二维数组可以用于存储子问题的解，以便递归地求解更大规模的问题。
二维数组的应用
04
CHAPTER
动态规划
多维数组的应用
05
CHAPTER
字符数组与字符串
字符数组的定义与声明
了解字符数组的基本定义和声明方式
总结词
字符数组是用于存储字符序列的数据结构，可以通过指定数组大小来声明一个字符数组。例如，char arr[100]表示声明一个能够存储100个字符的字符数组。
详细描述
掌握字符串在C语言中的表示方法
详细描述
在C语言中，二维数组是通过定义一个数组的数组来实现的。通常使用两个方括号[]来声明二维数组，例如int a[3][4]表示一个有3行4列的整型二维数组。
二维数组的定义与声明
二维数组的初始化可以通过多种方式进行，包括分别初始化每个元素和按行初始化。
总结词
在声明二维数组时，可以直接对每个元素进行初始化，例如int a[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}}。也可以按行对数组进行初始化，例如int a[3][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}}，这种方式会自动将每行的元素分别赋给对应位置的元素。

数据结构答案第4章

第 4 章广义线性表——多维数组和广义表2005-07-14第 4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。

【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。

除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。

【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。

⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

【解答】三元组顺序表，十字链表⑸广义表((a), (((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。

【解答】3，4，(a)，((((b),c)),(d))⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。

【解答】Head(Head(Tail(LS)))2. 选择题⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。

数据结构复习

地址计算以三对角矩阵为例
三对角矩阵中所有非零元素为3*n-2,可用一维数组s[3*n-2]存储.aij与s[k]
LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d
=LOC(0,0)+(2i+j)*d
4.3.2 稀疏矩阵
5、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？
6、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。
第四章数组
4.1 数组的定义
（2）能否得到出栈序列423和432？并说明为什么不能得到或如何得到。
（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。
2、表达式求值
3、两个栈共享存储空间r[m]，写出向第i个栈插入x,删除第i个栈的栈顶元素算法。
4、循环队列的优点是什么？如何判断它的空和满？循环队列的操作算法？
（2）二叉链表法
5．3 遍历二叉树
在二叉树的一些应用中，常常要求在树中查找具有某
种特征的结点，或者对树中全部结点逐一进行某种处
理。这就引入了遍历二叉树的问题，即如何按某条搜
索路径巡访树中的每一个结点，使得每一个结点均被
访问一次，而且仅被访问一次。
DLR——先（根）序遍历，
LDR——中（根）序遍历，
习题：6.2,6.3,6.5,6.6,6.7,6.12,6.13,6.14,6.19,6.21,6.26,6.42,6.43,6.47,
第六章图

数据结构之数组（Array）详解

数据结构之数组（Array）详解数组(Array)是由相同类型的元素(element)集合组成的固定长度(Size)的⼀种数据结构。

在内存中是连续存储的，因此可以通过索引(Index)计算出某个元素的地址。

下⾯介绍都是已java为⽰例。

对于没有详细了解过的相信有所收获。

基础知识声明type arrayName[] 或者 type[] arrayName。

如：int arrInt[] 或者int[] arrInt声明过程，只是告诉编译器: arrInt变量保存了⼀个int类型的数组。

这个过程并没有分配内存。

new分配内存分配内存需要通过new完成，同时指明类型和数组⼤⼩。

如：int[] arrInt = new int[4];数组中元素通过new分配后⾃动完成初始化，⼀般有⼏种：数字类型初始化为0(如：int/byte/short/long初始化为0，float/double初始化为0.0)，布尔型初始化为false(boolean 初始化为false),String或者其他对象类型初始化为null。

数组赋值也有两种int[] arrInt = {1,3,5,7};或int[] arrInt = new int[4];arrInt[0] = 1;arrInt[1] = 3;arrInt[2] = 5;arrInt[3] = 7;⽰意图如下：多维数组多维数组类似，即数组中的元素也是数组。

如int[][] arrInt = {{1,3,5},{2,4,6},{0,10,20}};⽰意图如下：数组特点1. 索引(即下标) ⼀般从0开始，如java, C/C++。

2. 长度固定，在申请时长度固定。

内存连续，在内存中则是申请⼀块连续的固定⼤⼩的空间。

3. 数组有⼀维数组和多维数组，数组元素可以是基本数据类型(Primitive)，也可以是对象引⽤(Reference)。

4. 随机访问，能够根据位置(下标)直接访问到元素。

数据结构第4章数组和串

1
● 教学目的：理解抽象数据类型数组的概念，掌握数组的不同存储结构的实现及应用，了解广义表的相关概念，掌握串的逻辑结构、存储结构及其基本运算。
● 教学重点：数作在不同存储结构上的实现。 ● 教学难点：带状矩阵的压缩存储；稀疏矩阵的三元组表实现及其转置算法，堆结构的串操作实现；串的模式匹配算法。
矩阵的压缩存储
printf("Array a:\n"); k=0; for(i=0;i<N;i++)//输出矩阵A { for(j=0;j<N;j++) if(i<j)printf("%5d",sa[M-1]); else printf("%5d",sa[i*(i+1)/2+j]); printf("\n"); } printf("Array b:\n"); k=0; for(i=0;i<N;i++)//输出矩阵B { for(j=0;j<N;j++) if(i>j)printf("%5d",sb[M-1]); else printf("%5d",sb[j*(j+1)/2+i]); printf("\n"); }}
矩阵的压缩存储
由此可见，要唯一表示一个稀疏矩阵，在存储三元组表的同时还需存储该矩阵总的行数、列数及非零元个数。练习：写出图4-9(a)所示稀疏矩阵的三元组表。
三元组表（也是线性表）的存储方式主要有两种：顺序存储和链式存储，从而可引出稀疏矩阵的两种压缩存储方法：三元组顺序表和十字链表。 3、三元组顺序表
矩阵的压缩存储

数据结构课程学习报告

一、课程简介算法与数据结构是计算机等相关专业的一门十分重要的专业基础课，在计算机学科中起到承前启后的作用。

它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。

要求学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术，培养学生数据抽象的能力。

本课程主要是让我们掌握数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序等内容。

二、各章知识点概述第一章---绪论学习内容：数据结构相关的基本概念，包括数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构等；算法时间复杂度的分析。

重难点：数据结构相关的基本概念，数据结构所含两个层次的具体含义及其相互关系以及算法时间复杂度的分析方法（多重循序）。

第二章---线性表学习内容：第二章线性表主要内容是顺序表和链表的相关概念，顺序表和链表的查找、插入和删除等相关操作及其算法实现，链表的创建算法，并能够设计出线性表应用的常用算法，比如线性表的合并等；能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合，明确它们各自的优缺点。

重难点：理清顺序表和链表的特点，学会用C写相关操作的代码。

第三章---栈和队列学习内容：栈和队列的特点。

顺序栈和链栈的进栈和出栈算法，以及循环队列和链队列的进队和出队算法。

重难点：学会灵活运用栈和队列解决实际应用问题，用C及栈和队列的特点写相关操作的代码。

比如表达式求值算法，理解递归算法执行过程中栈的状态变化过程，以更好地使用递归算法等。

第四章---串、数组和广义表学习内容：串的存储方法，理解串的两种模式匹配算法—BF算法和KMP算法。

明确数组和广义表这两种数据结构的特点，数组地址计算方法，几种特殊矩阵的压缩存储方法。

广义表的定义、性质及GetHead和GetTail的操作。

重难点：KMP算法；数组存储时地址的计算方法等。

PTA第四章串、数组和广义表练习题

B(2.0) D(2.0) D(2.0) D(2.0) D(2.0) A(2.0) B(2.0) B(2.0) D(2.0) C(2.0) D(2.0) D(2.0)2-1广义表是一种（B）数据结构。

(2分)1.非递归的2.递归的3.树型4.图状作者: 严冰单位: 浙江大学城市学院2-2一个广义表为( a, (b, c), d, (), ((f, g), h) )，则该广义表的长度与深度分别为（D）。

(2分)1.4和62.6和33.3和54.5和3作者: 严冰单位: 浙江大学城市学院2-3稀疏矩阵的快速转置算法的时间复杂度是（D）。

(2分)1.三次方时间2.二次方时间3.对数时间4.线性时间作者: 严冰单位: 浙江大学城市学院2-4在定义稀疏矩阵的十字链接存储结构时，每个结点结构需包含（D）个域。

(2分)1. 42. 33. 64. 5作者: 严冰单位: 浙江大学城市学院2-5广义表与稀疏矩阵都是线性表的扩展，它们的共同点为（D）。

(2分)1.都可以用链接结构与顺序结构存储2.无共同点3.都是递归结构4.数据元素本身是一个数据结构作者: 严冰单位: 浙江大学城市学院2-6(neuDS_C++)以下叙述中正确的是(A )。

(2分)1.串是一种特殊的线性表2.串的长度必须大于零3.串中元素只能是字母4.空串就是空白串作者: 姚志军单位: 广东东软学院2-7(neuDS_C++)串是一种特殊的线性表，其特殊性体现在(B )。

(2分)1.可以顺序存储2.数据元素是一个字符3.可以链接存储4.数据元素可以是多个字符作者: 姚志军单位: 浙江大学2-8(neuDS_C++)设有两个串p和q，求q在p中首次出现的位置的运算称作( B)。

(2分)1.连接2.模式匹配3.求子串4.求串长作者: 姚志军单位: 广东东软学院2-9(neuDS_C++)设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y 串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是(D )。

南邮数据结构答案

第1 章绪论一、基础题1. A2. C3. C4. A5. C二、扩展题1.数据是计算机加工处理的对象；数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；数据项是组成数据元素的、不可分割的最小单位。

2.数据结构是按某种逻辑关系组织起来的数据元素的集合，使用计算机语言描述并按一定的存储方式存储在计算机中，并在其上定义了一组运算。

3.集合结构、线性结构、树形结构和图形结构。

集合结构中，元素之间没有关系；线性结构中，元素之间存在一对一的关系；树形结构中，元素之间存在一对多的关系，其中最多只有一个元素没有前驱元素，这个元素就是根；图形结构中，元素之间存在多对多的关系。

4.顺序存储、链式存储、索引存储和散列存储。

5.一个算法是对特定问题的求解步骤的一种描述，是指令的有限序列。

其特征包括：➢输入：算法有零个或多个输入➢输出：算法至少产生一个输出➢确定性：算法的每一条指令都有确切的定义，没有二义性。

➢能行性/可行性：可以通过已经实现的基本运算执行有限次来实现➢有穷性：算法必须总能在执行有限步之后终止6.联系：程序是计算机指令的有序集合，是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。

区别：在语言描述上不同，程序必须是用规定的程序设计语言来写，而算法的描述形式包括自然语言、伪代码、流程图和程序语言等；算法所描述的步骤一定是有限的，而程序可以无限地执行下去，比如一个死循环可以称为程序，但不能称为算法。

7.正确性：算法的执行结果应当满足功能需求，无语法错误，无逻辑错误简明性：思路清晰、层次分明、易读易懂，有利于调试维护健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果效率：有效使用存储空间和有高的时间效率最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法可使用性：用户友好性8(1)执行次数为n-1（n>=2），n=1时执行1次；时间复杂度为O(n)。

(2）执行次数为⌈log3n⌉；时间复杂度为O(logn)(3) 执行次数为n2；时间复杂度为O(n2)(4）执行次数为⌊√n⌋ + 1；时间复杂度为O(√n)第2 章线性表1．A2．D3．B4．C5．B6．D7．D8．C9．A10．D1.编写程序实现对顺序表逆置。

数据结构-C语言-第四章作业

数据结构
练习
数据结构
设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0] 存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
答：设数组元素A[i][j]存放在起始地址为Loc ( i, j ) 的存储单元中
Байду номын сангаас
练习
数据结构
设有二维数组A[10,20]，其每个元素占两个字节， A[0][0]存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 352 ，按列优先顺序存储，元素A[6,6]的存储地址为 232 。
答：(6*20+6)*2+100=352 (6*10+6)*2+100=232
练习
数据结构
1、设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算：
数组a的最后一个元素a[5][7]起始地址；按行序优先时，元素a[4][6]起始地址；按列序优先时，元素a[4][6]起始地址。
课本作业
4.5 4.8 4.10
∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676.
∴ n = ( 676 - 2 - 644 ) / 2 = 15
∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

k k
3 2 1 12 2 5 18
k 43 19
5 3 4 24 6 4 6 -7
7 6 3 14
8 mb
方法二：快速转置即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数
实现：设两个数组 num[col]：表示矩阵M中第col列中非零元个数 p[col]：指示M中第col列第一个非零元在mb中位置显然有： p[1]=1;
第三章数组
数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表
§3.1 数组的定义和特点
)
)
)
)
)
定义
(a11 a12 ... ... a1n )
Amn
(a21
a22
... ... a2n )
( ... ... ... ... ... )
(am1 am2 ... ... amn)
0 0 24 0 0 0 0
4 -7 8
0 18 0 0 0 0 0
15 0 0 7 0 0 0 67
ma
伪地址表示法
伪地址：本元素在矩阵中（包括零元素再内）按行优先顺序的相对位置
伪地址
0 12 9 0 0 0 0
0
00
0 0 0 0
M 3 0 0 0 0 14 0
0 0 24 0 0 0 0
3 0 0 0 7
0 0 1 0 0
A
1
2
0
0
0
0 0 0 0 0
0 0 0 2 0
13 3 -1 ^ 1 -1
5 7^ 2 -2 ^
^ 4 2^
需存储单元个数为3t+m
十字链表
设行指针数组和列指针数组，分别指向每行、
列第一个非零元
3 0 0
结点定义
row col val
tpedef struct node
Loc(i,j)=Loc(0,0)+(i*n+j)*s
0<i≤m-1, 0<j≤n-1
§定义一A[2][3]数组，对应的矩阵如下：
A
a00 a10
a01 a11
a02 a12
数组元素A[1][2]，其下标i=1，j=2，故它前面已经有i=1行，每行有3个元素，另外本行有j=2个元素，所以在元素A[1][2]之前，本数组已有5个元素。
Loc(aij)=Loc(a11)+[(
i(i-1) 2
+(j-1)]*l
对角矩阵
a11 a12 0 …………… . 0 a21 a22 a23 0 …………… 0 0 a32 a33 a34 0 ……… 0
……………………………
0 0 … an-1,n-2 an-1,n-1 an-1,n
0 0 … …an,n-1
……………………………………..
nm
a1221
a22
……..
am2n2 ……….
aamm11 aamm22 ………….... aammnn
a1mn1
LLoocc((aiaj)ij=)=LLoco(ca(a111)1+)+[([j(-i1-)1m)n++((ij--11))]]**l l
a2mn2 ……..
阵转置矩阵的三元组表问题分析一般矩阵转置算法：
for(col=0;col<n;col++) for(row=0;row<m;row++) n[col][row]=m[row][col];
T(n)=O(mn)
0 12 9 0 0 0 0
0 0 0 0 0 0 0
M 3 0 0 0 0 14 0
1 13
^^
17
^^
4 18 ^^
Ch4_3.c
2 25
^^
2 34
^
^
3.3 广义表
4.3.1基本概念广义表是第二章提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表(另一个线性表)。
357
ij v 07 6 8
p 1 1 2 12
p21 3 9
p 3 3 1 -3
p 4 3 6 14
p54 p65
3 24 2 18
p 7 6 1 15
p 8 6 4 -7 ma
1 1 3 -3
2 1 6 15 3 2 1 12
4 2 5 18 53 1 9 6 3 4 24 7 4 6 -7 8 6 3 14
(
(
(
(
(
数组特点
❖数组结构固定
❖数据元素同构
数组运算
❖给定一组下标，存取相应的数据元素
❖给定一组下标，修改数据元素的值
§3.2 数组的顺序存储结构
次序约定
❖以行序按为行主列序为主序存放 ❖以列序为主序
0
a11
11
a2112
…….
mn--11
am1n1
aa1111 aa1122 ………….... aa11nn aa2211 aa2222 ………….... aa22nn
mb
链式存储结构
带行指针向量的单链表表示
每行的非零元用一个单链表存放
设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空
typedef表头str结uct点no与de单链表结点类型定义
{ int col; int val; struct node *link;
}JD; typedef struct node *TD;
ann.
按行序为主序：
a11 a12 a21 a22 a23 …... …... ann-1 ann
k=0 1 2 3 4
n(n-1)/2 n(n+1)/2-1
Loc(aij)=Loc(a11)+2(i-1)+(j-1)
稀疏矩阵
❖定义：非零元较零元少，且分布没有一定规律的矩阵
❖压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值
0 12 9 0 0 0 0
0 0 0 0 0 0 0
M
3
0
0
0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 7 0 0 0 67
M由{(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) } 和矩阵维数（6,7）唯一确定
0 18 0 0 0 0 0
15 0 0 7 0 0 0 67
addr v
06 7
1 2 12
23 9 3 15 -3
20 14 4
24 24 5 30 18 6 36 15 7 39 -7
8 ma
非零元值矩阵行列维数
伪地址表示法需存储单元个数为2(t+1)
求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩
§3.3 矩阵的压缩存储
三角矩阵 a11 0 0 …….. 0 a21 a22 0 …….. 0
…………………. 0 an1 an2 an3…….. ann
按行序为主序：
a11 a21 a22 a31 a32 …... an1 …... ann
k=0 1 2 3 4
n(n-1)/2 n(n+1)/2-1
❖稀疏矩阵的压缩存储方法
0 12 9 0 0 0 0
0 0 0 0 0 0 0
顺序存储结构
M 3 0 0 0 0 14 0
三元组表 #define M 20
0 0 24 0 0 0 0
typedef struct node 0 18 0 0 0 0 0
行列下标
非零元值 { int i,j;
Ch4_1.c
ij v
06 7 8
p 1 1 2 12 p
p 21 3 9 p
p 3 3 1 -3
p
p
3 6 14 p
p 4 4 3 24 p
p 5 5 2 18 p
p 6 6 1 15 p
p 7 6 4 -7 p 8 ma
col=1
col=2
ij v
07 6 8
k 1 1 3 -3
k 2 1 6 15
15 0 0 7 0 0 0 67
ij v
int v; }JD;
06 7 8
JD ma[M];
1 1 2 12
21 3 9
33 3
44
1 -3 6 14 3 24
5 5 2 18 6 6 1 15
7 6 4 -7
8
ma
ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数
mm**nn--11 amn
1. 一维数组寻址公式
§对于一维数组，若其下标的下界为LB，上界为UB，第一元素（其下标为LB）的地址为Loc(LB)，下标为i的数组元素A[i]的地址为 Loc(i)，则计算Loc(i)的寻址公式为：
Loc(i)=Loc(LB)+(i-LB)*s §在C语言中，数组下标的下界为0，则数组
方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb 中应有的顺序
算法描述：
算法分析：T(n)=O(M的列数n非零元个数t) 若 t 与mn同数量级，则T(n)O(mn2)