数据结构C语言版第五章课件严蔚敏

《数据结构C语言版第五章课件严蔚敏》由会员分享，可在线阅读，更多相关《数据结构C语言版第五章课件严蔚敏（37页珍藏版）》请在装配图网上搜索。

1、2021/3/111第第5章章 数组和广义表数组和广义表 5.1 数组的定义和运算数组的定义和运算5.2 数组的顺序存储和实现数组的顺序存储和实现5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 5.4 广义表广义表 2021/3/112l 数组是数组是n(n1)个相同类型数据元素个相同类型数据元素a0,a1,an-1构成构成的有限序列的有限序列,且该有限序列存储在一块地址连续的内且该有限序列存储在一块地址连续的内存单元中。存单元中。l 数组的定义类似于采用顺序存储结构的线性表，是数组的定义类似于采用顺序存储结构的线性表，是线性表在维数上的扩张，也就是线性表中的元素又线性表在维数上的扩张，也就是线

2、性表中的元素又是一个线性表。是一个线性表。l n维数组，维数组，bi是第是第i维的长度，则维的长度，则n维数组共有维数组共有 个个数据元素，每个元素受数据元素，每个元素受n个关系的制约，就单个关个关系的制约，就单个关系而言，这系而言，这n个关系仍然是线性的。个关系仍然是线性的。1.数组的定义和运算数组的定义和运算 1niib2021/3/113l数组具有以下性质：数组具有以下性质：(1)(1)数组中的数据元素数目固定。一旦定义了一个数组中的数据元素数目固定。一旦定义了一个 数组数组,其数据元素数目不再有增减变化。其数据元素数目不再有增减变化。(2)(2)数组中的数据元素具有相同的数据类型。数组

3、中的数据元素具有相同的数据类型。(3)(3)数组中的每个数据元素都和一组惟一的下标值对数组中的每个数据元素都和一组惟一的下标值对 应。应。(4)(4)数组是一种随机存储结构。可随机存取数组中的数组是一种随机存储结构。可随机存取数组中的 任意数据元素。任意数据元素。l数组的基本操作数组的基本操作 (1)取值取值 Value(A,&e,index1,.,indexn)(2)赋值赋值Assign(&A,e,index1,indexn)2021/3/1142.2.数组的存储结构数组的存储结构l一维数组中一维数组中,LOC(a,LOC(a0 0)确定确定,每个数据元素占用每个数据元素占用L L个个存储单

4、元存储单元,则任一数据元素则任一数据元素a ai i的存储地址的存储地址LOC(aLOC(ai i)就可就可由以下公式求出：由以下公式求出：LOC(aLOC(ai i)=LOC(a)=LOC(a0 0)+i)+i*L(0in-1)L(0in-1)l二维数组二维数组,由于计算机的存储结构是线性的由于计算机的存储结构是线性的,如何用如何用线性的存储结构存放二维数组元素就有一个行列线性的存储结构存放二维数组元素就有一个行列次序排放问题。次序排放问题。2021/3/115二维数组通常可以描述为两种形式二维数组通常可以描述为两种形式 :以以行序行序为主序为主序:PASCAL、C可以看成可以看成 A=(0

5、，1，m-1-1 ).其中其中i 是一个行向量形式的线性表，是一个行向量形式的线性表，0im-1-1i =(ai0，ai1，ai n-1-1).a00 a01 a02 a0,n-1-1a10 a11 a12 a1 1,n-1-1am-1-1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1.Amn =2021/3/116可以看成可以看成 A=(0，1，n-1-1 ).其中其中j 是一个列向量形式的线性表，是一个列向量形式的线性表，0jn-1-1j =(a0j，a1j，am-1-1j ).a00 a01 a02 a0,n-1-1a10 a11 a12 a1 1,n-1-1am

6、-1-1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1.Amn =以以列序列序为主序为主序:FORTRAN2021/3/117对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。a00a01a0,n-1-1a10a11a1 1,n-1-1am-1-1,0 0am-1-1,n-1-1am-1-1,1 101m-1-1设数组以设数组以行序行序为主序。为主序。设二维数组设二维数组 A(mn)其数组元素其数组元素 aij 的存储位置为的存储位置为LOC(i，j)=LOC(0，0)其中，其中，LOC(0，0)是是

7、a00的存储位置；的存储位置；L是每个数组元素占用的存储单元数；是每个数组元素占用的存储单元数；L例，例，LOC(1，1)=LOC(0，0)+(n1+1)L+(ni+j)L2021/3/118ln维数组维数组每一元素对应下标每一元素对应下标(j1,j2,jn)，0jibi-1，bi为第为第i维维的长度。以行序为主序。的长度。以行序为主序。LOC(j1,j2,jn)=LOC(0,0,0)+(bnb2j1+bnb3j2+bnjn-1+jn)L2021/3/119l例例:对二维数组对二维数组float a54float a54计算：计算：(1)(1)数组数组a a中的数组元素数目；中的数组元素数目；

8、(2)(2)若数组若数组a a的起始地址为的起始地址为2000,2000,且每个数组元素长度且每个数组元素长度为为3232位位(即即4 4个字节个字节),),数组元素数组元素a32a32的内存地址。的内存地址。元素数目共有元素数目共有5*4=20个。个。C语言采用行序为主序的存储方式语言采用行序为主序的存储方式,则有：则有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056。2021/3/11103.矩阵的压缩存储矩阵的压缩存储 l特殊矩阵（对称矩阵、三角矩阵、对角矩阵）特殊矩阵（对称矩阵、三角矩阵、对角矩阵）特殊矩阵是指非零元素或零元素的分布

9、有一定规律的特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵矩阵,为了节省存储空间为了节省存储空间,特别是在高阶矩阵的情况下特别是在高阶矩阵的情况下,可以利用特殊矩阵的规律可以利用特殊矩阵的规律,对它们进行压缩存储对它们进行压缩存储,也就也就是说是说,使多个相同的非零元素共享同一个存储单元使多个相同的非零元素共享同一个存储单元,对对零元素不分配存储空间。零元素不分配存储空间。2021/3/1111l对称矩阵的压缩存储对称矩阵的压缩存储若一个若一个n n阶方阵阶方阵A A中的元素满足中的元素满足ai,j=aj,i(1i,jn),则称其则称其为为n n阶阶对称矩阵对称矩阵。（1 1）只存储对称矩

10、阵中上三角或下三角中的元素）只存储对称矩阵中上三角或下三角中的元素,（2 2）将）将n2个元素压缩存储到个元素压缩存储到n(n+1)/2个元素的空间中，个元素的空间中，以一个一维数组作为以一个一维数组作为A A的存储空间。的存储空间。1,11,21,2,12,22,1,2,nnn nnnn naaaaaaAaaa2021/3/1112 n2个元素个元素 n(n+1)/2个元素个元素 aij(1i,jn)Bn(n+1)/2 l1+2+(i-1)+j-1；laij aji(1)1,2(1)1,2i ijijkj jiij 当当a11a21a22a31anna12=a13=k=0123n(n+1)2

11、-12021/3/1113l下三角矩阵的压缩存储下三角矩阵的压缩存储 Bn(n+1)/2+1(1)1,2(1),2i ijijkn nij当当1,12,12,2,1,2,n nnnn naaaAaaaCk=0123n(n+1)2-1a11a21a22a31annca12,a13 2021/3/1114l对角矩阵对角矩阵：所有的非零元都集中在以主对角线为中心：所有的非零元都集中在以主对角线为中心 的带状区域内。的带状区域内。.b 条 b 条 0 0 .半带宽为半带宽为b b的对角矩阵的对角矩阵 2021/3/1115共有共有3n-2个非零元。个非零元。主对角线左下方的元素下标有关系式：主对角线左

12、下方的元素下标有关系式：i=j+1 k=3(i-1)-1+1-1=3(i-1)-1=2(i-1)+i-2=2(i-1)+j-1.主对角线上的元素下标有关系式：主对角线上的元素下标有关系式：i=j k=3(i-1)-1+2-1=3(i-1)=2(i-1)+i-1=2(i-1)+j-1.主对角线右上方的元素下标有关系式：主对角线右上方的元素下标有关系式：i=j-1 k=3(i-1)-1+3-1=3(i-1)+1=2(i-1)+i=2(i-1)+j-1.l三对角矩阵三对角矩阵B3n-2;k=2(i-1)+j-1;2021/3/1116l稀疏矩阵稀疏矩阵 非零元较零元少，且没有一定规律。非零元较零元少

13、，且没有一定规律。mn的矩阵，有的矩阵，有t个非零元，个非零元，矩阵的稀疏因子矩阵的稀疏因子：=t/(m*n)，当，当0.05时为稀疏矩阵。时为稀疏矩阵。压缩存储，只存储非零元压缩存储，只存储非零元三元组顺序表三元组顺序表(i，j，ai,j)行逻辑链接的顺序表行逻辑链接的顺序表十字链表十字链表(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 701290000000000030000 14 0002400000180060015007 000A2021/3/1117#define MaxSize 10

14、0 /*矩阵中非零元素最多个数矩阵中非零元素最多个数*/typedef struct int i;/*行号行号*/int j;/*列号列号*/ElemType e;/*元素值元素值*/Triple;/*三元组定义三元组定义*/typedef struct int rows;/*行数行数*/int cols;/*列数列数*/int nums;/*非零元素个数非零元素个数*/Triple dataMaxSize+1;/*data0未用未用*/TSMatrix;/*三元组顺序表定义三元组顺序表定义*/2021/3/1118rowcole121213931 3361443245218611564 71

15、2345678211231913 3631434242518161546 712345678 需要重新排序 行列互换rowcolel用三元组表实现稀疏矩阵的转置运算用三元组表实现稀疏矩阵的转置运算 一个一个6*7的矩阵的矩阵A，以行序为主序顺序排列，以行序为主序顺序排列2021/3/1119l矩阵的转置，方法一：矩阵的转置，方法一：2021/3/1120l Status TransposeSMatrix(TSMatrix A,TSMatrix&B)B.rows=A.cols;B.cols=A.rows;B.nums=A.nums;if(B.nums!=0)q=1;/*q为为B.data的下标的

16、下标*/for(col=1;col=A.cols;col+)for(p=1;p=A.nums;p+)/*p为为A.data的下标的下标*/if(A.datap.j=col)B.dataq.i=A.datap.j;B.dataq.j=A.datap.i;B.dataq.e=A.datap.e;q+;return OK;2021/3/1121方法方法1时间复杂度：时间复杂度：O(cols*nums)当非零元个数当非零元个数nums和和cols*rows同数量级时，同数量级时，O(rows*cols2)仅适用于仅适用于numsrows*cols.常规存储方式时，常规存储方式时，实现矩阵转置的经典算法

17、如下：实现矩阵转置的经典算法如下：for(i=0;im;i+)for(j=0;j n;j+)Ti j=Mji;O(cols*rows)2021/3/1122l方法二：方法二：依次按三元组表依次按三元组表A(6*7)的次序进行转置，转置后直接放到的次序进行转置，转置后直接放到三元组表三元组表B的正确位置上。这种转置算法称为快速转置算法。的正确位置上。这种转置算法称为快速转置算法。row col e 1 2 12 1 3 9 3 1-3 3 6 14 4 3 24 5 2 18 6 1 15 6 4-7 col 1 2 3 4 5 6 7 numcolcpotcol22210101357889nu

18、mcol:A中第中第col列非零元的个数。列非零元的个数。cpotcol:B中第中第col行第一个非零元行第一个非零元 在在B中的位置中的位置2021/3/1123l Status FastTranSMatrix(TSMatrix A,TSMatrix&B)B.rows=A.cols;B.cols=A.rows;B.nums=A.nums;if(B.nums)for(col=1;col=A.cols;+col)numcol=0;for(t=1;t=A.nums;+t)+numA.datat.j;cpot1=1;for(col=2;col=A.cols;+col)cpotcol=cpotcol-

19、1+numcol-1;for(p=1;p=A.nums;+p)col=A.datap.j;q=cpotcol;B.dataq.i=A.datap.j;B.dataq.j=A.datap.i;B.dataq.e=A.datap.e;+cpotcol;return OK;O(cols+nums)当当nums和和cols*rows同数量级时同数量级时O(rows*cols)2021/3/1124 row col e 1 1 2 12 2 1 3 9 3 3 1-3 4 3 6 14 5 4 3 24 6 5 2 18 7 6 1 15 8 6 4-7 row col ecol 1 2 3 4 5 6

20、 7 num col 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9 12345678 1 3 -3 3 1 9 2 1 12 cpot1cpot2cpot2cpot3cpot3cpot4cpot6 6 3 14 3 4 24 2 5 18 1 6 15 4 6 -7 2021/3/1125小结小结基本学习要点如下：基本学习要点如下：(1)理解数组和一般线性表之间的差异。理解数组和一般线性表之间的差异。(2)重点掌握数组的顺序存储结构和元素地址计算重点掌握数组的顺序存储结构和元素地址计算方法。方法。(3)掌握各种特殊矩阵如对称矩阵、上、下三角矩掌握各种特殊矩阵如对称矩阵

21、、上、下三角矩阵和对角矩阵的压缩存储方法。阵和对角矩阵的压缩存储方法。(4)掌握稀疏矩阵的各种存储结构以及基本运算实掌握稀疏矩阵的各种存储结构以及基本运算实现算法。现算法。(5)灵活运用数组这种数据结构解决一些综合应用灵活运用数组这种数据结构解决一些综合应用问题。问题。2021/3/1126l练习：练习：将一个将一个A1.100,1.100的三对角矩阵，按行优先存的三对角矩阵，按行优先存入一维数组入一维数组B1.298，A中元素中元素a66,65在在B数组中的数组中的位置位置k=?。在主对角线左下方，在主对角线左下方，65*3-1+1=195。2021/3/1127l作业：作业：5.2 5.2

22、52021/3/11281.广义表的定义（列表）广义表的定义（列表）广义表是线性表的推广，是由零个或多个单元素或子表所广义表是线性表的推广，是由零个或多个单元素或子表所 组成的有限序列。组成的有限序列。LS=(a1,a2,ai,an)ai：是单个数据元素：是单个数据元素,则则ai是广义表的是广义表的原子原子；如果；如果ai是一个广是一个广义表义表,则则ai是广义表的是广义表的子表子表。规定用小写字母表示原子规定用小写字母表示原子,用大写字母表示广义表的用大写字母表示广义表的 表名。表名。l广义表与线性表的区别：广义表与线性表的区别：线性表的成份都是结构上不可分的单个数据元素，而广线性表的成份都

23、是结构上不可分的单个数据元素，而广义表的成份即可以是单元素，也可以是有结构的表，其定义义表的成份即可以是单元素，也可以是有结构的表，其定义是递归的定义。是递归的定义。5.4 广义表广义表2021/3/1129l广义表的长度：广义表中所含元素的个数广义表的长度：广义表中所含元素的个数n,n0。l广义表的深度：广义表展开后所含的括号的广义表的深度：广义表展开后所含的括号的最大层数。（广义表中括号嵌套的最大次数，最大层数。（广义表中括号嵌套的最大次数，广义表中括弧的重数）广义表中括弧的重数）2021/3/1130l D=()空表，长度为空表，长度为0，深度为，深度为1。l A=(a,(b,c)长度为

24、长度为2，第一个元素为原子，第一个元素为原子a，第二，第二个元素为子表个元素为子表(b,c)，深度为，深度为2。l B=(A,A,D)长度为长度为3，其前两个元素为表其前两个元素为表A，第第三个元素为空表三个元素为空表D，深度为，深度为3。l C=(a,C)长度为长度为2递归定义的广义表，递归定义的广义表，C相当于相当于无穷表无穷表C=(a,(a,(a,)，深度无限。，深度无限。递归表的深度是无穷值递归表的深度是无穷值,长度是有限值长度是有限值。l F=(a,(a,b),(a,b),c)长度为长度为1，深度为，深度为4。2021/3/1131l 广义表的广义表的表头表头(Head)和和表尾表尾

25、(Tail)：当广义表非空时，称第一个元素当广义表非空时，称第一个元素a1为广义表的表头，为广义表的表头，其余元素组成的表其余元素组成的表(a2,a3,an)称为广义表的表尾。称为广义表的表尾。表头可能是原子，也可能是广义表，但表尾一定是广表头可能是原子，也可能是广义表，但表尾一定是广义表。义表。l 广义表的图形表示广义表的图形表示 用方框表示原子，用圆圈表示广义表。用方框表示原子，用圆圈表示广义表。2021/3/1132A=();B=(e);C=(a,(b,c,d)D=(A,B,C);E=(a,(a,b),(a,b),c)c a b a b E d e a b c D A B C d b c

26、 C a B e A a 2021/3/11332.广义表的基本操作广义表的基本操作l 取表头取表头 GetHead(LS)=a1。l 取表尾取表尾 GetTail(LS)=(a2,a3,an)。B=(e)GetHead(B)=e;GetTail(B)=().A=(a,(b,c),d,e)GetHead(GetHead(GetTail(A)=GetHead(GetHead(b,c),d,e)=GetHead(b,c),d,e)=(b,c).A=();B=()A空表，长度空表，长度0，深度，深度1，无表头和表尾；，无表头和表尾；B长度长度1，深度，深度2，表头，表头()，表尾，表尾()。2021

27、/3/11343.广义表的存储结构广义表的存储结构 广义表是一种递归的数据结构广义表是一种递归的数据结构,因此很难为每个广因此很难为每个广义表分配固定大小的存储空间义表分配固定大小的存储空间,所以其存储结构只好所以其存储结构只好采用动态链式结构。采用动态链式结构。l 广义表的头尾链表存储表示广义表的头尾链表存储表示l 广义表的扩展线性链表存储表示广义表的扩展线性链表存储表示2021/3/1135C=(a,(b,c,d)C 1 0 a 1 1 1 1 0 b 0 c 0 d(a,(b,c,d)(b,c,d)(b,c,d)(c,d)(d)l 广义表的头尾链表存储表示广义表的头尾链表存储表示2021/3/1136 C 1 0 a 1 0 b 0 c 0 d C=(a,(b,c,d)(b,c,d)l 广义表的扩展线性链表存储表示（带表头结点）广义表的扩展线性链表存储表示（带表头结点）2021/3/1137l作业：作业：5.10