资源描述：
《数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、线性表—具有相同类型的数据元素的有限序列栈队串特殊线性表L={a1,a2,…,ai-1,ai,…,an}a1,a2,…,ai-1,ai,…,ana1,a2,…,ai-1,ai,…,ana1,a2,…,ai-1,ai,…,an限为字符8/23/2021多维数组广义表广义线性表a1,a2,…,ai-1,ai,…,ana1,a2,…,ai-1,ai,…,an元素扩展为线性表（相同）元素扩展为线性表（可不同）8/23/2021本章知识要点本章重点本章难点第4章广义线性表—多维数组和广义表数组的定义，存储结构及寻址方法；特
2、殊矩阵，稀疏矩阵的存储方法与寻址方法；三元组顺序表的转置运算；广义表的定义，存储结构及基本运算。数组的寻址方式；特殊矩阵，稀疏矩阵的存储方法；广义表中求表头和表尾的方法。稀疏矩阵压缩存储的转置方法；广义表的存储结构。8/23/20214.1多维数组4.1.1数组的定义1.数组的定义数组（array）是由类型相同的数据元素构成的有序集合，每个数据元素称为数组元素（简称元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1,i2,…in称为该元素的下标，并称该数组为n维数组。{a1a2……
3、an}a11a12……a1na21a22……a2n……………………aij………………am1am2…amn1维数组2维数组8/23/20214.1多维数组4.1.1数组的定义2.数组的特点1）元素的推广性：元素不限定是单个数据元素2）元素的同一性：元素具有相同的数据类型3）元素的确定性：元素受n(n≥1)个线性关系的约束，元素个数和元素间的逻辑关系相对确定简单的线性表就是一维数组；元素是一维数组的线性表就是二维数组；以此类推。a11a12……a1na21a22……a2n……………………aij………………am1am2
4、…amn(A1，A2，…，An)Ai=(a1i，a2i，…，ami)8/23/20214.1多维数组4.1.1数组的定义3.数组的操作特点a11a12……a1na21a22……a2n……………………aij………………am1am2…amn数组有哪些基本的操作？插入或删除数组一个元素有意义吗？事实上，除了对数组整体进行初始化或销毁外，数组最常用的操作就是读和写（对指定单元的访问）。8/23/20214.1多维数组4.1.1数组的定义4.数组的抽象数据类型定义详见P50。我们注意到，数组的ADT中关键的操作，除初始化数
5、组外，就是读和写操作，而它们的核心就是：寻址。8/23/20214.1多维数组问题1：内存的绝对地址和相对地址？问题2：C语言中一维数组的存储方式及寻址方式？问题3：顺序表与单链表的存储特点？为了讨论数组的存储与寻址方式，我们先复习几个与之相关的问题：4.1.2数组的存储结构与寻址8/23/20214.1多维数组内存的绝对地址：内存的物理地址编号内存的相对地址：内存相对于某个基地址的编号0123iaai&a[i]a+i实例：计0611班2008春游，入住某处六楼房间号是绝对地址；学号（尾号）是相对地址（相对于六
6、楼的第一间房间号）按学号尾号依次入住。4.1.2数组的存储结构与寻址8/23/20214.1多维数组C++中一维数组的存储方式及寻址方式：1）使用连续的内存单元；2）通过数组基地址+相对地址（数组名+下标）来寻址。0123in-1a0a1a2a3……ai…an-1ai：ai的相对地址=ai前边的元素个数=i4.1.2数组的存储结构与寻址ai的绝对地址为：LOC(ai)=LOC(a0)+i*cc为每个元素占用的内存单元数8/23/20214.1多维数组4.1.2数组的存储结构与寻址顺序表和单链表的存储特点：存取方式
7、插/删操作个数限制存储密度顺序表单链表随机存取顺序存取不方便方便受限不受限=1＜1由于数组不涉及插入和删除操作，不需要预留空间，而且要求能随机存取，因此，数组采用存储结构是：顺序存储结构8/23/20214.1多维数组4.1.2数组的存储结构与寻址1.数组的顺序存储顺序存储即使用连续的内存单元来存储，由于内存单元是一维的结构，而多维数组是多维的结构，所以，用顺序存储结构来存储多维数组需要解决多维结构到一维结构的映射问题。2.二维数组的映射方式a11a12……a1na21a22……a2n……………………aij………
8、………am1am2…amnX(行)(列)Y二维数组元素间的逻辑关系8/23/20214.1多维数组4.1.2数组的存储结构与寻址2.二维数组的映射方式1）按行优先：行（X）方向元素优先使用连续单元。2）按列优先：行（Y）方向元素优先使用连续单元。由于绝大多数语言都是采用按行优先，我们也重点介绍按行优先的映射方式。8/23/20214.1多维数组4.1.2数组的存储结构与寻
