数组和广义表
- 格式:ppt
- 大小:3.99 MB
- 文档页数:88
数据结构串、数组和广义表知识点总结
数据结构是计算机科学中研究数据如何组织、存储、管理和操作的学科。
三个常见的数据结构串、数组和广义表都是用于存储和操作数据的。
1. 串:
- 串是由0个或多个字符组成的有限序列。
它是一维数组的特例。
- 串的操作包括插入、删除、修改和查找等常见操作。
- 串可以通过数组、链表或动态分配的内存来实现。
2. 数组:
- 数组是一种线性数据结构,它由一组连续的内存空间组成,
存储相同类型的数据。
- 数组的操作包括插入、删除、修改和查找等常见操作。
- 数组的访问时间复杂度为O(1),但插入和删除的时间复杂度
较高。
3. 广义表:
- 广义表是由若干元素组成的有序集合,每个元素可以是原子
或者是一个广义表。
- 广义表可以通过链表来实现,每个节点包含两个指针,一个
指向元素,一个指向下一个节点。
- 广义表的操作包括插入、删除、修改和查找等常见操作。
- 广义表可以表示任意层次的嵌套结构,具有灵活性和扩展性。
总结:
- 串、数组和广义表都是常见的数据结构,用于存储和操作数据。
- 串是字符的有限序列,可以通过数组或链表来实现。
- 数组是一维线性数据结构,存储相同类型的数据,具有常数时间复杂度的访问操作。
- 广义表是由元素组成的有序集合,可以通过链表来实现,能够表示任意层次的嵌套结构。
第五章数组和广义表一.选择题1.在二维数组A 中引用A[i,j]的时间_________。
A.与i、j的大小有关B.与i、j的大小无关C.与i的大小有关,与j的大小无关D.与i的大小无关,与j的大小有关2.在稀疏矩阵的带行指针向量的链接存储中,每一行单链表中的结点都具有相同的________。
A.行号 B.列号 C.元素值 D.地址3.二维数组A 按行顺序存储,其中每个元素占1个存储单元。
若 A[1][1]的存储地址为420, A[3][3]的存储地址为446,则A[5][5]的存储地址为_______。
A.470 B.471 C.472 D. 4734.在稀疏矩阵的十字链接存储中,每个列单链表中的结点都具有相同的_____。
A.行号 B.列号 C.元素值 D.地址5.下面的说法中,不正确的是________。
A.对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可B.对角矩阵中只须存放的非零元素即可C.稀疏矩阵中值为零的元素较多,因此可以采用三元组表方法存储D.稀疏矩阵中大量值为零的元素分布有规律,因此可以采用三元组表方法存储6.对一些特殊矩阵采用压缩存储的目的主要是为了________。
A.表达变得简单 B.对矩阵元素的存取变得简单C.去掉矩阵中的多余元素 D.减少不必要的存储空间的开销7.若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中,则该对称矩阵在 B 中占用了________个数组元素。
A.n2 B.n*(n-1) C.n*(n+1)/2 D.n*(n-1)8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。
A. 行号B.列号C.元素值D.元素总数9.稀疏矩阵一般的压缩存储方法有两种,即________。
A.二维数组和三维数组 B.三元组和散列C. 三元组和十字链表 D.散列和十字链表10.有一个 10 阶对称矩阵 A,采用压缩存储方式(以行序为主存储,且A[0 Ⅱ0]=1),则A[8][5]的地址是________。
《数据结构与算法》第五章数组和广义表本章介绍的数组与广义表可视为线性表的推广,其特点是数据元素仍然是一个表。
本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。
5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构,它可以看作线性表的推广。
数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据,但属于同一数据类型,比如:一维数组可以看作一个线性表,二维数组可以看作“数据元素是一维数组”的一维数组,三维数组可以看作“数据元素是二维数组”的一维数组,依此类推。
图5.1是一个m行n列的二维数组。
5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。
通常,数组在内存被映象为向量,即用向量作为数组的一种存储结构,这是因为内存的地址空间是一维的,数组的行列固定后,通过一个映象函数,则可根据数组元素的下标得到它的存储地址。
对于一维数组按下标顺序分配即可。
对多维数组分配时,要把它的元素映象存储在一维存储器中,一般有两种存储方式:一是以行为主序(或先行后列)的顺序存放,如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配,即一行分配完了接着分配下一行。
另一种是以列为主序(先列后行)的顺序存放,如FORTRAN语言中,用的是以列为主序的分配顺序,即一列一列地分配。
以行为主序的分配规律是:最右边的下标先变化,即最右下标从小到大,循环一遍后,右边第二个下标再变,…,从右向左,最后是左下标。
以列为主序分配的规律恰好相反:最左边的下标先变化,即最左下标从小到大,循环一遍后,左边第二个下标再变,…,从左向右,最后是右下标。
例如一个2×3二维数组,逻辑结构可以用图5.2表示。
以行为主序的内存映象如图5.3(a)所示。
分配顺序为:a11 ,a12 ,a13 ,a21 ,a22,a23 ; 以列为主序的分配顺序为:a11 ,a21 ,a12 ,a22,a13 ,a23 ; 它的内存映象如图5.3(b)所示。
第8章数组和广义表[能力要求](1)计算机基础知识:掌握线性表的概念以及顺序表和链表的基本操作。
(2)分析问题:针对具体的问题,要能够运用线性表去进行分析,逐步找到解决问题的方法。
(3)具有概念化和抽象化能力:针对具体的应用和实际的问题,能够运用线性表对问题进行抽象,提取它的逻辑结构和存储结构。
(4)发现问题和表述问题:在具体的工程中,能够发现工程中涉及到顺序表和链表的问题,并能够明确表述。
(5)建模:在具体的工程中,能够使用线性表进行建模,设计合理的数据结构和相应的算法。
(6)解决方法和建议:在具体工程应用中,发现了关于线性表的问题,要能够解决问题,并提出合理的建议。
(7)定义功能、概念和结构:使用线性表这种逻辑结构处理一些具体问题,实现系统的功能。
(8)设计过程的分段与方法:采取不同的阶段去设计(概念设计、详细设计)一个具体的线性表的应用项目。
(9)软件实现过程:了解系统中各个模块中的关于线性表的设计;讨论算法(数据结构、控制流程、数据流程);使用编程语言实施底层设计(编程)。
8.1知识点:数组的定义和顺序存储一、选择题1①常对数组进行的两种基本操作是()。
A.建立与删除 B.索引和修改C.对数据元素的存取和修改D.查找与索引2①下面说法中,不正确的是()。
A.数组是一种线性结构B.数组是一种定长的线性表结构C.除了插入与删除操作外,数组的基本操作还有存取、修改、检索和排序等D.数组的基本操作有存取、修改、检索和排序等,没有插入与删除操作3②数组A中,每个元素的长度为3个字节,行下标I从1到8,列下标J从1到10,从首地址SA开始连续存放在存储器内,该数组占用的字节数为()。
A.80 B.100 C.240 D.2704②在二维数组A[9][10]中,每一个数组元素A[i][j] 占用3个存储空间,所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储空间是()。
A. 80 B.100 C.240 D.2705②设有一个n*n的对称矩阵A,将其下三角部分按行存放在一个一维数组B中,A[0][0]存放于B[0]中,那么第I行的对角元素A[I][I]存放于B中()处。
第5章:数组和广义表 1. 了解数组的定义;填空题:1、假设有二维数组A 6×8,每个元素用相邻的6个字节存储,存储器按字节编址。
已知A 的起始存储位置(基地址)为1000,则数组A 的体积(存储量)为 288 B ;末尾元素A 57的第一个字节地址为 1282 。
2、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的 行下标 、 列下标 和 元素值 。
2. 理解数组的顺序表示方法会计算数组元素顺序存储的地址;填空题:1、已知A 的起始存储位置(基地址)为1000,若按行存储时,元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ;若按列存储时,元素A 47的第一个字节地址为 (6×7+4)×6+1000)=1276 。
(注:数组是从0行0列还是从1行1列计算起呢?由末单元为A 57可知,是从0行0列开始!) 2、设数组a[1…60, 1…70]的基地址为2048,每个元素占2个存储单元,若以列序为主序顺序存储,则元素a[32,58]的存储地址为 8950 。
答:不考虑0行0列,利用列优先公式: LOC(a ij )=LOC(a c 1,c 2)+[(j-c 2)*(d 1-c 1+1)+i-c 1)]*L 得:LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950选择题:( A )1、假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储,其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为 。
(无第0行第0列元素)A .16902B .16904C .14454D .答案A, B, C 均不对 答:此题(57列×60行+31行)×2字节+10000=16902( B )2、设矩阵A 是一个对称矩阵,为了节省存储,将其下三角部分(如下图所示)按行序存放在一维数组B[ 1, n(n-1)/2 ]中,对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是:A .i(i-1)/2+j-1B .i(i-1)/2+jC .i(i+1)/2+j-1D .i(i+1)/2+j3、从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。
数据结构数组与广义表知识点总结数组是一种线性数据结构,可以存储多个相同类型的元素。
它的特点是元素的大小固定,并且在内存中是连续存储的。
数组的访问方式是通过下标来访问,下标从0开始。
数组可以在编程中应用于各种情况,比如存储一组数字、一组字符串等。
广义表是一种扩展的线性数据结构,可以存储不同类型的元素。
它由元素和表构成,其中表可以是空表、原子或子表。
广义表可以递归定义,即子表可以包含更多的子表。
广义表的访问方式是通过递归来访问,可以对表的元素进行遍历和操作。
在数据结构中,数组和广义表都有自己的特点和用途,下面对它们的知识点进行总结:1.数组的特点及应用:-数组是一种线性数据结构,可以存储多个相同类型的元素。
-数组的内存分配是连续的,可以通过下标来访问元素。
-数组的大小固定,一旦定义后不能改变。
-数组的访问速度快,可以通过下标直接访问元素。
-数组适合用于存储一组相同类型的数据,比如一组数字、一组字符串等。
-数组的应用场景包括但不限于:排序算法、查找算法、图像处理、矩阵运算等。
2.数组的操作和常用算法:-初始化:可以直接赋值或使用循环初始化数组。
-访问元素:通过下标访问元素,下标从0开始。
-修改元素:直接通过下标修改元素的值。
-插入元素:需要移动插入位置之后的元素。
-删除元素:需要移动删除位置之后的元素。
-查找元素:可以使用线性查找或二分查找等算法。
-排序算法:比如冒泡排序、选择排序、插入排序等。
-数组还有一些常用的属性和方法,比如长度、最大值、最小值等。
3.广义表的特点及应用:-广义表是一种扩展的线性数据结构,可以存储不同类型的元素。
-广义表由元素和表构成,表可以是空表、原子或子表。
-广义表可以递归定义,即子表可以包含更多的子表。
-广义表的访问方式是通过递归遍历和操作。
-广义表适合存储一组不同类型的数据,比如存储学生信息、函数调用栈等。
-广义表的应用场景包括但不限于:函数式编程、树的表示、图的表示等。
第五章数组与广义表一、假设有二维数组A6*8,每个元素用相邻的6个字节存储,存储器按字节编址。
已知A的起始存储位置(基地址)为1000。
计算:1、数组A的体积(即存储量);2、数组A的最后一个元素a57的第一个字节的地址;3、按行存储时,元素a14的第一个字节的地址;4、按列存储时,元素a47的第一个字节的地址;答案:1、(6*8)*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+(288-6)=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100,每个整数占四个字节。
问下列元素的存储地址是什么?(1)a0000(2)a1111(3)a3125 (4)a8247答案:(1)100(2)loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵(aij)n*n,将其上三角元素逐行存于数组B[m]中,(m 充分大),使得B[k]=aij且k=f1(i)+f2(j)+c。
试推导出函数f1,f2和常数C(要求f1和f2中不含常数项)。
答:K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵,试从空间和时间角度比较采用两种不同的存储结构(二维数组和三元组表)完成∑aii运算的优缺点。
(对角线求和)解:1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度:O(n)2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度:O(n2)二十一、当稀疏矩阵A和B均以三元组表作为存储结构时,试写出矩阵相加的算法,其结果存放在三元组表C中。
数据结构05数组与广义表数组与广义表可以看做是线性表地扩展,即数组与广义表地数据元素本身也是一种数据结构。
5.1 数组地基本概念5.2 数组地存储结构5.3 矩阵地压缩存储5.4 广义表地基本概念数组是由相同类型地一组数据元素组成地一个有限序列。
其数据元素通常也称为数组元素。
数组地每个数据元素都有一个序号,称为下标。
可以通过数组下标访问数据元素。
数据元素受n(n≥1)个线性关系地约束,每个数据元素在n个线性关系地序号 i1,i2,…,in称为该数据元素地下标,并称该数组为n维数组。
如下图是一个m行,n列地二维数组A矩阵任何一个元素都有两个下标,一个为行号,另一个为列号。
如aij表示第i行j列地数据元素。
数组也是一种线性数据结构,它可以看成是线性表地一种扩充。
一维数组可以看作是一个线性表,二维数组可以看作数据元素是一维数组(或线性表)地线性表,其一行或一列就是一个一维数组地数据元素。
如上例地二维数组既可表示成一个行向量地线性表: A1=(a11,a12,···,a1n)A2=(a21,a22, ···,a2n)A=(A1,A2, ···,Am) ············Am=(am1,am2, ···,amn)也可表示成一个列向量地线性表:B1=(a11,a21,···,am1)B2=(a12,a22, ···,am2)A=(B1,B2, ···,Bm) ············Bn=(a1n,a2n, ···,amn)数组地每个数据元素都与一组唯一地下标值对应。