数据结构C语言版ppt课件.ppt

《数据结构C语言版ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构C语言版ppt课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构C语言版ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第5章 数组和广义表主要内容：一、数组的定义二、数组的表示和实现三、矩阵的压缩存储四、广义表的定义五、广义表的存储结构中国网页设计第5章 数组和广义表 数组是由n(n1)个具有相同数据类型的数据元素a1，a2，an组成的有序序列。这n个数据元素占用一块地址连续的存储空间。数组中的数据元素具有相同数据类型。数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。数组中的数据元素个数

2、是固定的。数组是一种特殊的线性表，表中的元素可以是原子类型，也可以是一个线性表。中国网页设计数组的定义 数组中的数据元素可以是原子类型的，如整型、字符型、浮点型等，这种类型的数组称为一维数组；也可以是一个线性表。二维数组可以看成是线性表的线性表。中国网页设计第5章 数组和广义表二、数组的表示和实现1、数组类型特点1)数组除了初始化和销毁外，只有存取元素和修改元素值的操作，不对数组进行插入和删除操作。2)数组是多维的结构，而存储空间是一个一维的结构。2、两种顺序映像方式1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。中国网页设计第5章 数组和广义表中国网页设计第5章 数组和广义表

3、以行序为主序的求址公式：以行序为主序的求址公式：假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由下式确定：LOC(i,j)=LOC(0,0)+(ni+j)*LLOC(i,j)=LOC(0,0)+(ni+j)*L式中，LOC(i,j)是aij的存储位置，LOC(0,0)是a00的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。b2是数组第二维的长度，即数组A(mn)中的列数n。中国网页设计思考思考题：设有数组Ai,j,数组每个元素长度为3字节，i的值为1到8，j的值为1到10，且数组从内存首地址BA开始顺序存放。1.以列序为主存放时，元素A5，8的存储首地址为

4、（）2.以行序为主存放时，元素A5，8的存储首地址为（）。中国网页设计以列序为主序的求址公式：以列序为主序的求址公式：LOC(i,j)=LOC(0,0)+(jm+i)*LLOC(i,j)=LOC(0,0)+(jm+i)*L中国网页设计第5章 数组和广义表三、矩阵的压缩存储所谓的压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配存储空间。若值相同的元素或零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵；反之称为稀疏矩阵。中国网页设计特殊矩阵(1)对称矩阵：定义定义 若若n阶矩阵阶矩阵A中的元满足下述性质：中的元满足下述性质：aijaji1i，jn则称为则称为n阶阶对称矩阵对称矩

5、阵。中国网页设计第5章 数组和广义表压缩存储压缩存储 由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时，由于对称矩阵中的元素关于主对角线对称，因此，在对矩阵存储时，可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共可以只存储对称矩阵中的上三角或者下三角的元素，使得对称的元素共享一个存储单元，则可将享一个存储单元，则可将n2 个元压缩存储个元压缩存储到到n(n+1)/2个元的空间中。我们以行序为主序存储其下三角（包个元的空间中。我们以行序为主序存储其下三角（包括对角线）中的元。括对角线）中的元。中国网页设计第5章 数组和广义表中国网页设计有一个10阶的对称矩阵A，采用压缩存

6、储方式以行序为主序存储，A11为第一元素，其存储地址为1，每个元素占一个地址空间，求A75和A56的地址。随堂练习中国网页设计对角矩阵的压缩存储对角矩角矩阵,也称带状矩阵，是另一类特殊的矩阵。所谓对角矩阵，就是所有的非零元素都集中在以主对角线两侧的带状区域内（对角线的个数为奇数）。也就是说除了主对角线和主对角线两边的对角线外，其他元素的值均为0.中国网页设计第5章 数组和广义表2、稀疏矩阵(1)定义：假设m行n列的矩阵含t个非零元素，则称为稀疏因子稀疏因子。通常认为0.05的矩阵为稀疏矩阵稀疏矩阵。中国网页设计第5章 数组和广义表(2)稀疏矩阵的存储：若按常规方法进行存储，零值元素会占了很大空

7、间因此对于稀疏矩阵的存储通常采用以下两种方式：三元组表和十字链表进行存储。中国网页设计第5章 数组和广义表中国网页设计第5章 数组和广义表中国网页设计第5章 数组和广义表中国网页设计第5章 数组和广义表四、广义表的定义中国网页设计广义表中所包含的元素(包括原子和子表)的个数称为表的长度。广义表中括号的最大层数称为表深(度)。中国网页设计2、广义表表示（1）广义表常用表示E=()E是一个空表，其长度为0。L=(a，b)L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表A=(x，L)=(x，(a，b)A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。B=(A，y)=(x，(

8、a，b)，y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。中国网页设计C=(A，B)=(x，(a，b)，(x，(a，b)，y)C的长度为2，两个元素都是子表。D=(a，D)=(a，(a，(a，()D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。（2）广义表的深度）广义表的深度一个表的深度是指表展开后所含括号的层数。【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为。中国网页设计取广义表头的操作是getHead（）取表尾的操作是getTail()，中国网页设计随堂练习1.设广义表L=()，()，试问GetHead(L)，GetTai

9、l(L)的值，求L的长度和深度各为多少?GetHead(L)和GetTail(L)的值是()和()。L的长度和深度都是2。中国网页设计2.广义表(a,(a,b),d,e,(i,j),k)的长度是_，深度是_3.设广义表L=（a,b,c），则L的长度和深度分别为（）。A.1和1B.1和3C.1和2D.2和353c中国网页设计3.求下列广义表运算的结果：(1)GetHead(p，h，w)(2)GetTail(b，k，p，h)(3)GetHead(GetTail(a，b)，(c，d)(4)GetTail(GetHead(a，b)，(c，d)【解答】(1)GetHead(p,h,w)=p(2)GetT

10、ail(b,k,p,h)=(k,p,h)(3)GetHead(GetTail(a，b)，(c，d)=GetHead(c,d)=(c,d)(4)GetTail(GetHead(a，b)，(c，d)=GetTail(a,b)=(b)中国网页设计第5章 数组和广义表思考题：1、广义表L=（a，（b，c），进行Tail（L）操作后的结果为（）。A.cB.b，cC.（b，c）D.（b，c）2、已知广义表：A=（a,b），B=（A，A），C=（a,(b,A),B），则tail(head(tail(C)的运算结果为（）；3、已知广义表LS=（a，b，c）,（d，e，f），则运用head和tail函数取出LS中原子e的运算表达式为:D(A)(head(tail(head(tail(LS)中国网页设计4.已知二维数组A35，其每个元素占3个存储单元，并且A00的存储地址为1200。求元素A13的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？【解答】LOC(A13)=1200+(1*5+3)*3=1224(按行序存储)LOC(A13)=1200+(3*3+1)*3=1230(按列序存储)中国网页设计-数据结构数据结构中国网页设计