树结构综合版1——7数据结构ch5数组和广义表
43页1、数 据 结 构 Data Structure,主讲人: 刘 玮,第五章 数组和广义表,数组的定义,5.1,数组的顺序表示和实现,5.2,矩阵的压缩存储,5.3,广义表的基本概念和存储结构,5.4,5.1 数组的定义,数组可以看成是一种特殊的线性表,即线性表中数据元素本身也是一个线性表。,5.1.1 什么是数组,数组是n(n0)个相同数据类型数据元素构成的有限序列。,( ),( ),( ),( ),( ),( ),( ),( ),( ),二维数组同样满足数组的定义。二维数组可以看成一个特殊的一维数组,其中的每个元素又是一个一维数组。,5.1.2 数组的抽象数据类型ADT,Value(A, &e, index1,indexn),初始条件:A是n维数组,e为元素变量, 随后是n个下标值。,操作结果:若各下标不超界,则e赋值为 所指定的A的元素值,并返回OK。,Assign(&A, e, index1,indexn),初始条件:A是n维数组,e为元素变量, 随后是n个下标值。,操作结果:若各下标不超界,则e的值赋给 所指定的A的元素值,并返回OK。,数组的特点:,数组中的数据元素数目固定(结构
2、固定);,数组中的数据元素具有相同的数据类型(元素同构);,数组中的每个数据元素都与一组唯一的下标值相对应;,数组是一种随机存取结构。,5.2 数组的顺序表示和实现,在数组中插入或者删除一个元素有意义吗?,数组应该采用何种方式存储?,顺序存储方式,5.2 数组的顺序表示和实现,用一组连续的存储单元来表示数组。 有两种存储方式,以行为主:对二维数组进行“按行切分”,即将数组中的数据元素“按行依次排放”在存储器中; 以列为主:对二维数组进行“按列切分”,即将数组中的数据元素“按列依次排放”在存储器中。,每个数据元素占L个存储单元; LOC(0,0)表示数据元素a00的存储地址,是数组的起始地址(基地址); LOC(i,j)表示下标为(i,j)的数据元素aij的存储地址。,按行序为主序存放,LOC(i,j)=LOC(0,0)+(i*n+j)*L,“行序为主序” 二维数组中任一元素aij的存储位置:,推广到一般情况,可得到n维数组数据元素存储位置:,n维数组的映像函数,数组元素的存储位置是其下标的线性函数。,每个数据元素占L个存储单元; LOC(0,0)表示数据元素a00的存储地址,是数组的起
3、始地址(基地址); LOC(i,j)表示下标为(i,j)的数据元素aij的存储地址。,按列序为主序存放,LOC(i,j)=LOC(0,0)+(J*m+I)*L,数组的C语言表示,5.3 矩阵的压缩存储,压缩存储,为多个值相同的矩阵只分配一个存储空间; 对零元不分配空间。,值相同的元素或者0元素在矩阵中的分布有一定规律。,5.3.1 特殊矩阵,特殊矩阵,特殊矩阵的压缩存储,仅存储下三角,对称矩阵,下三角矩阵,对角矩阵,非零元较零元少,且分布没有一定规律的矩阵。,5.3.2 稀疏矩阵,稀疏矩阵,压缩原则:尽量少存或不存0元;尽量减少没有意义的运算;运算要方便。,压缩存储方法:三元组顺序表、行逻辑连接和十字链表。,存储特点,三元组顺序表,对于矩阵中每个非0元素,用它的行号、列号、元素值,即(i, j, aij)表示。 将表示稀疏矩阵的所有非0元素的三元组按行优先(列优先)顺序排列,则可得到一个其结点均是三元组的线性表,称为三元组表。 以顺序存储结构来表示三元组。 要唯一确定一个稀疏矩阵,还必须存储该矩阵的行数和列数。,数据类型定义,# define MAXSIZE 12500 三元组结点:
4、typedef struct int i, j; ElemType e; Triple; 稀疏矩阵: typedef struct Triple dataMAXSIZE+1 ; int mu, nu, tu; /*行、列、非零元素个数*/ TSMatrix ;,问题描述:,已知一个稀疏矩阵的三元组表,求该矩阵转置矩阵的三元组表。,常规算法: for(col=1;col=nu;col+) for(row=1;row=mu;row+) Tcolrow=Mrowcol;,例子:求转置矩阵,解决思路:,将矩阵行、列维数互换; 将每个三元组中的i和j相互调换; 重排三元组次序;,方法一:按矩阵的列序转置,按T.data中三元组次序依次在M.data中找到相应的三元组元素进行转置。,方法二:按矩阵的行序转置,按M.data中三元组次序转置,将转置结果放入T.data中适当位置。,优点:,非零元在表中按行序有序存储,便于进行依行序处理的矩阵运算。,缺点:,若需按行号存取某一行的非零元,则需从头开始查找。,为了便于随机存储任意一行的非零元,需要知道每一行的第一个非零元在三元组表中的位置。,行逻辑连接的
《树结构综合版1——7数据结构ch5数组和广义表》由会员E****分享,可在线阅读,更多相关《树结构综合版1——7数据结构ch5数组和广义表》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页