数据结构（C语言描述）教学课件斯庆巴拉第5章数组.ppt

《数据结构（C语言描述）教学课件斯庆巴拉第5章数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组数组的基本概念和存储结构稀疏矩阵的定义、表示方法、存储结构及基本操作的实现算法特殊矩阵的存储广义表的定义、链式存储结构，以及相应操作的实现算法。第5章数组5.1数组5.2数学中的应用5.3广义表本章总结5.1数组5.1.1一维数组5.1.2多维数组5.1.1一维数组一维数组在数组结构中可以看成是一个线性表或一个向量，通常分配一块连续的存储单元。在C语言中，一维数组a[n]的存储单元是从a[0]至a[n－1]的一块连续的存储空间，设a[0]的存储地址LOC（a[0]），数据元素所占的存储单

2、元为k个字节，则任一元素a[i]的首字节地址LOC（a[i]）：LOC（a[i]）=LOC（a[0]）+i*k(0≤i

3、形式的线性表，如式子（5-3）所示。是以列序为主序的存储结构。数组的存储结构对于二维数组来说，设数组的第一个元素a0,0的地址LOC（a0,0），每个元素所占的存储单元为k，则二维数组中任一元素ai，j的存储地址：LOC（ai,j）=LOC（a0,0）+（i*n＋j）*kn为列数n维数组a[d1][d2]…[dn]的数据元素存储位置的计算公式：5.2数学中的应用5.2.1稀疏矩阵5.2.2特殊矩阵5.2.1稀疏矩阵稀疏矩阵的概念稀疏矩阵的三元组线性表表示稀疏矩阵的顺序存储方式稀疏矩阵的链式存储方式

4、稀疏矩阵各种操作的实现稀疏矩阵的概念：在一个阶数较大的矩阵中非零元素个数s相对于矩阵元素的总个数t非常小，即s<

5、下：structSMatrix{intm，n，t；//m，n和t域分别用来存储稀疏矩阵的行数、列数和非零元素的个数Tripledata[MaxTerms+1]；//存储非零元素的三元组}；三元组线性表的顺序存储结构：（1）行逻辑链式存储把具有相同行号的三元组结点按列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为：structTripleNode{introw，col；//存储行号和列号Elemtypeval；//存储元素值structTripleNode*next；//指向同一行的

6、下一个结点}；typedefstruct{intm，n，t；//m，n和t用于保存稀疏矩阵的行数、列数和非零元素的个数TripleNode*vector[MaxRows+1]；//存储单链表头指针}LMatrix；稀疏矩阵的链式存储方式（2）十字链式存储将稀疏矩阵的每一行设置一个单独链表，同时也为每一列设置一个单独链表。稀疏矩阵的每一个非零元素同时包含在两个链表中，即每一个非零元素同时包含在所在行的行链表和所在列的列链表中，处于两个链表的交点处，方便了对稀疏矩阵行方向和列方向的搜索十字链式存储的类

7、型定义为：（略）稀疏矩阵各种操作的实现InitMatrix（M）：初始化将矩阵置为空CreatMatrix（M，m，n）：创建一个稀疏矩阵PrintMatrix（M）：输出稀疏矩阵TransposeMatrix（M，T）：求转置矩阵AddMatrix（M，N，T）：矩阵相加操作一：InitMatrix（M）（略）操作二：CreatMatrix（M，m，n）分析：创建一个稀疏矩阵，m和n代表所创建的稀疏矩阵的行号和列号。输入时按照三元组线性表中三元组排列的次序输入，每行输入一个三元组，行号、列号和元

8、素值之间用空格分开，最后按回车确定一个三元组的输入。输入完所有的三元组后，以三元组（-1，*，*）结束整个输入过程。(*代表任意整数)实现算法：（略）操作三：PrintMatrix（M）（按三元组形式输出稀疏矩阵）操作四：TransposeMatrix（M，T）分析：对于一个m×n的矩阵Am×n，其转置矩阵是一个n×m的矩阵。设为Bn×m，满足ai，j=bj，i其中1≤i≤m，1≤j≤n。在转置过程中，需要对顺序存储的稀疏矩阵进行n（行数）次扫描，每次都扫描整个三元组顺序表，故矩阵