数据结构C语言版ppt课件.ppt
《数据结构C语言版ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构C语言版ppt课件.ppt(30页珍藏版)》请在三一文库上搜索。
1、中国网页设计 ,数 据 结 构 (C语言版),严蔚敏、吴伟民编著 清华大学出版社 学习网站:http:/ ,第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)*L 式中,LOC(i, j)是aij的存储位置,LOC(0, 0)是a00的存储位置,即二维数组A的起始存储位置,也称为基地址或基址。b2是数组第二维的长度,即数组A(mn)中的列数n。,中国网页设计 ,思考题:设有数组Ai,j,数组每个元素长度为3字节,i的值为1到8,j的值为1到10,且数组从内存首地址BA开始顺序存放。 以列序为主存放时,元素A5,8的存储首地址为( ) 以行序为主存放时,元素A5,8的存储首地址为( )。,中国网页设计 ,以
4、列序为主序的求址公式: LOC(i, j) = LOC(0, 0) + (jm + i)*L,中国网页设计 ,第5章 数组和广义表,三、矩阵的压缩存储 所谓的压缩存储是指:为多个值相同的元只分配一个存储空间;对零元不分配存储空间。 若值相同的元素或零元素在矩阵中的分布有一定规律,则称此类矩阵为特殊矩阵;反之称为稀疏矩阵。,中国网页设计 ,特殊矩阵,(1)对称矩阵:,定义 若n阶矩阵A中的元满足下述性质: aijaji 1i,jn 则称为n阶对称矩阵。,中国网页设计 ,第5章 数组和广义表,压缩存储 由于对称矩阵中的元素关于主对角线对称,因此,在对矩阵存储时, 可以只存储对称矩阵中的上三角或者下
5、三角的元素,使得对称的元素共享一个存储单元,则可将n2 个元压缩存储 到n(n+1)/2个元的空间中。我们以行序为主序存储其下三角(包 括对角线)中的元。,中国网页设计 ,第5章 数组和广义表,中国网页设计 ,有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储,A11为第一元素,其存储地址为1,每个元素占一个地址空间,求A75和A56的地址。,随堂练习,中国网页设计 ,对角矩阵的压缩存储,对角矩阵,也称带状矩阵,是另一类特殊的矩阵。所谓对角矩阵,就是所有的非零元素都集中在以主对角线两侧的带状区域内(对角线的个数为奇数)。也就是说除了主对角线和主对角线两边的对角线外,其他元素的值均为0.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 ppt 课件
链接地址:https://www.31doc.com/p-3185590.html