《DS05-数组和广义表 数据结构.ppt》由会员分享，可在线阅读，更多相关《DS05-数组和广义表 数据结构.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章要点q数组的类型定义和表示方法q特殊矩阵和稀疏矩阵存储方法 及运算的实现q广义表的结构特点第五章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表n5.1.1 多维数组组的定义n定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()n5.1.2 数组的顺序存储结构n次序约定n以行序为主序n以列序为主序a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放amn.am2am1.a
2、2n.a22a21a1n.a12a1101n-1m*n-1n按列序为主序存放按列序为主序存放01m-1m*n-1mamn.a2na1n.am2.a22a12am1.a21a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*ln5.2.1 特殊矩阵n对称矩阵a11a12.a1na21a22.a2nan1an2.ann.a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：n三角矩阵a1100.0a21a220.0an1an2an3.ann.
3、0Loc(aij)=Loc(a11)+(+(j-1)*li(i-1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：n对角矩阵a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann.0a32a33a3400Loc(aij)=Loc(a11)+2(i-1)+(j-1)a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：M由(1,2,12),(1,3,9),(3,1,-3
4、),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数（6,7）唯一确定5.2.2稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值n稀疏矩阵的压缩存储方法n顺序存储结构n三元组表#define M 20typedef struct node int i,j;int v;TriTupleNode;TriTupleNode maM;三元组表所需存储单元个数为3(t+1)其中t为非零元个数6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1
5、 15 6 4 -7 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分别存放矩阵行列维数和非零元个数行列下标非零元值n求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表Y问题分析一般矩阵转置算法：for(col=0;coln;col+)for(row=0;rowm;row+)ncolrow=mrowcol;T(n)=O(mn)6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v7 6 8 1 3 -3 1
6、6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8mb?解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序算法描述：算法分析：T(n)=O(M的列数n非零元个数t)若 t 与mn同数量级，则6 7 8 1 2 12 1 3 9 3 1 -3
7、 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1col=2方法二：按行序转置（快速转置）即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数实现：设两个数组numcol：表示矩阵M中第col列中非零元
8、个数cpotcol：指示M中第col列第一个非零元在mb中位置显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1;(2col ma0.j)1357889colnumcolcpotcol12223241506170算法分析：T(n)=O(M的列数n+非零元个数t)若 t 与mn同数量级，则T(n)=O(mn)算法描述：6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol112
9、2323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp46297535.3 广义表 广广义义表表(Lists)也称为列列表表，它是线性表的推广。大家知道，线性表是n（n0）个元素a1，a2，ai，an的有限序列。其中，线性表的元素仅限于原子项，所谓原原子子，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放松对线性表元素的这种限制，允许它们具有其自身独立的类型结构，那么就产生了广义表的概念。广义表是n（n0）个元素a1，a2，ai，an的有限序列，其中a
10、i或者是原子，或者是一个广义表。通常，广义表可记作LS=(a1,a2,ai,an)。LS是广义表的名字，n为广义表LS的长长度度。若ai本身也是广义表，则称它为LS的子表子表。不包含任何元素（即n=0）的广义表称为空表。需要注意的是：需要注意的是：n广义表通常用圆括号括起来，用逗号分隔其中的元素。n为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。n若广义表LS非空(n1)，则a1称为LS的表表头头，其余元素组成的表(a2,ai,an)称为LS的表表尾尾。显然，表尾一定是子表，但表头可以是原子，也可以是子表。n广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。广义表是一个
11、多层次多层次的线性结构线性结构。例如:有A、B、C、D、E五个广义表的描述如下：A=()A是一个空表,它的长度为零B=(e)列表B只有一个原子e,B的长度为1.C=(a,(b,c,d)列表C的长度为2,两个元素分别为原子a和子表(b,c,d)D=(A,B,C)列表D的长度为3,三个元素都是列表,显 然,将 子 表 的 值 代 入 后,则 有D=(),(e),(a,(b,c,d)E=(a,E)这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,.)广义表的结构特点广义表的结构特点:1)广义表中的数据元素有相对次序次序;2)广义表的长长度度定义为最外层包含的元素个数;3)广
12、义表的深度深度定义为所含括弧的重数;注意:“原子”的深度为“0”;“空表”的深度为14)表头可以是原子或列表;表尾必定是列表。5)广义表可以是一个递归递归的表;递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表 LS=(1,2,n)均可分解为 表头表头 Head(LS)=1 和 表尾表尾 Tail(LS)=(2,n)两部分例如：例如：Head(b,c)=(b,c)Tail(b,c)=()Head(a,(b,c)=a Tail(a,(b,c)=(b,c)Head(c)=(c)Tail(c)=()广义表还可以用图形来形象的表示，下图给出了几个广义表的图形表示，其中的分支结点对应广义表，非分
13、支结点（即叶子）对应原子或者空表。与树对应的广义表称为纯纯表表（Pure List），这种表中没有共享和递归的成分，即没有任何成分出现多次，它限制了表中成分的共享和递归，例如图中的(a)，(b)，(c)都是纯表；与有向无环图对应的表称为再再入入表表，这种表存在元素共享，在图中表现为存在结点共享，例如图中(d)，子表A是共享结点，它既是C的一个元素，又是子表B的元素；与有回路的有向图对应的表称为递递归归表表，这种表的某个成员内含有广义表自己，例如图中(e)中，表D是其自身的子表。n各种表之间的关系满足：递归表 再入表 纯表 线性表n广义表的基本运算，除包括线性表的基本运算外，还有求深度、取表头、取表尾、遍历等。这些运算中大部分与对应的线形表、树或者图的运算类似，只是取表头和取表尾是广义表特有的运算。