数据结构数组学习笔记.docx
- 文档编号:10753625
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:18
- 大小:335.48KB
数据结构数组学习笔记.docx
《数据结构数组学习笔记.docx》由会员分享,可在线阅读,更多相关《数据结构数组学习笔记.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构数组学习笔记
数组学习笔记
1、
java中的数据类型分类:
基本数据类型(或叫做原生类、内置类型)8种:
整数:
byte,short,int,long(默认是int类型)
浮点类型:
float,double(默认是double类型)
字符类型:
char
布尔类型:
boolean
引用数据类型3种:
数组,类,接口
其中,基本数据类型之间除了boolean,其他数据类型之间可以任意的相互转换(强制转化或默认转换),这个与c++中有点区别。
数组是对象,intfloatchar这些基本类型不是对象。
关于如何判断基本类型和对象,参考下面的:
行为:
基本类型只是一个值,没有任何行为
对象类型有自己的行为
内存分配:
基本类型在栈内分配
对象在堆内分配
对象引用保存在栈内
引用与值:
基本类型是值类型,仅表示一个值,保存在栈内
引用类型分两部分,对象引用保存在栈内,对象保存在堆内,
访问变量,是使用的引用找对象
2、
对一个排好序的数组进行查找,时间复杂度为()二分查找:
n,n/2,n/4…令n/2*k=1.得k=log2n(以2为为底的对数)
3、
shortint:
2个字节
sizeof 返回的值表示的含义如下(单位字节):
数组 —— 编译时分配的数组空间大小;
指针 —— 存储该指针所用的空间大小(存储该指针的地址的长度,是长整型,应该为 4 );
类型 —— 该类型所占的空间大小;
对象 —— 对象的实际占用空间大小;
函数 —— 函数的返回类型所占的空间大小。
函数的返回类型不能是 void 。
shorta[100] 空间100*2
4、
和顺序栈相比,链栈有一个比较明显的优势是通常不会出现栈满的情况
链栈存在于不连续的内存中,依靠节点指向后一个节点的指针进行地址查找
顺序栈就是数组,在内存中是连续的
5、
(1)《数据结构》对广义表的表头和表尾是这样定义的:
如果广义表LS=(a1,a2...an)非空,则a1是LS的表头,其余元素组成的表(a2,a3,..an)是称为LS的表尾。
根据定义,非空广义表的 表头是一个元素,它 可以是原子也可以是一个子表, 而表尾则必定是子表。
例如:
LS=(a,b),表头为a,表尾是(b)而不是b.另外:
LS=(a)的表头为a,表尾为空表().
(2)非空广义表,除表头外,其余元素构成的表称为表尾,所以非空广义表尾一定是个表。
广义表即我们通常所说的列表(lists)。
它放松了对表元素的原子性限制,允许他们有自身结构。
广义表的长度:
最大括号中的逗号数+1
广义表的深度:
展开后含括号的层数。
广义表的特性:
广义表的元素可以是子表,而子表的元素还可以是子表。
广义表可为其他广义表所共享。
广义表可以是一个递归的表,即广义表也可以是其本身的一个子表
广义表(((a,b,c),d,e,f))的长度为4,4个元素分别为子表(a,b,c)和单元素d,e,f。
二维以上的数组其实是一种特殊的广义表
6、
假设以行优先顺序存储三维数组A[5][6][7],其中元素A[0][0][0]的地址为1100,且每个元素占2个存储单元,则A[4][3][2]的地址是()
三维比如说是x,y,z组成的立体,按行存储就是先存yz面,
三维数组a[m1][m2][m3]中若按行优先存储,设a[0][0][0]的起始地址为p,每个元素占n个单元,则a[i][j][k]的起始地址为:
loc(i,j,k)=loc(i,0,0)+(j*m3+k)*n=loc(i-1,0,0)+(m2*m3+j*m3+k)*n=loc(i-2,0,0)+(2*m2*m3+j*m3+k)*n=…=p+(i*m2*m3+j*m3+k)*n
则loc(4,3,2)=1100+(4*6*7+3*7+2)*2=1482。
7、
从逻辑结构上看,n维数组的每个元素均属于n个向量,像2为数组的每个元素属于2个向量Z(x,y),通俗的说,在Z中增加一维,也就是在每个元素增加一类属性,也就是增加一个向量,此时Z中每个元素已经对应三种属性(向量).同理,n维数组的每个元素均属于n个向量.
8、
给定一个m行n列的整数矩阵(如图),每行从左到右和每列从上到下都是有序的。
判断一个整数k是否在矩阵中出现的最优算法,在最坏情况下的时间复杂度是________。
杨氏矩阵查找算法:
从矩阵的右上角开始,若右上角元素大于所找,则可右上角元素所在的列的所有元素均大于所找元素,下次查找忽略该列;若右上角元素小于所找,则右上角元素所在行的所有元素均小于所找元素,下次查找,忽略该行;若相等,结束查找;否则,由新形成的矩阵利用上述方式继续查找。
O(m+n).
8、
数组与指针的区别
(1)数组要么在静态存储区被创建(如全局数组),要么在栈上被创建。
(2)用运算符sizeof可以计算出数组的容量(字节数)
(3)指针可以随时指向任意类型的内存块。
数组要么在静态存储区被创建(如全局数组),要么在栈上被创建。
指针可以随时指向任意类型的内存块。
(1)修改内容上的差别
chara[]=“hello”;
a[0]=‘X’;
char*p=“world”;//注意p指向常量字符串
p[0]=‘X’;//编译器不能发现该错误,运行时错误
(2)用运算符sizeof可以计算出数组的容量(字节数)。
sizeof(p),p为指针得到的是一个指针变量的字节数,而不是p所指的内存容量。
C++/C语言没有办法知道指针所指的内存容量,除非在申请内存时记住它。
注意当数组作为函数的参数进行传递时,该数组自动退化为同类型的指针。
chara[]="helloworld";
char*p=a;
cout< cout< 计算数组和指针的内存容量 voidFunc(chara[100]) { cout< } 9、 稀疏矩阵一般的压缩存储方法有两种,即三元组和十字链表 稀疏矩阵在采用压缩存储后将会失去随机存储的功能。 因为在这种矩阵中,非零元素的分布是没有规律的,为了压缩存储,就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起,这样的结点组成的线性表中叫三元组表,它已不是简单的向量,所以无法用下标直接存取矩阵中的元素。 (1).三元组顺序表又称有序的双下标法,对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。 它的特点是,非零元在表中按行序有序存储,因此便于进行依行顺序处理的矩阵运算。 当矩阵中的非0元素少于1/3时即可节省存储空间。 (2).十字链表: 是既带行指针又带列指针的链接存储方式,每个三元组结点处于所在行单链表与列单链表的交点处,当矩阵的非零元个数和位置在操作过程中变化较大时,用这种存储结构更为恰当。 在十字链表中,每个非零元可用一个含五个域的结点表示,其中i,j和e三个域分别表示该非零元所在的行、列和非零元的值,向右域right用以链接同一行中下一个非零元,向下域down用以链接同一列中下一个非零元。 同一行的非零元通过right域链接成一个线性链表,同一列的非零元通过down域链接成一个线性链表,每个非零元既是某个行链表中的一个结点,又是某个列链表中的一个结点,整个矩阵构成了一个十字交叉的链表,故称这样的存储结构为十字链表,可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。 10、 图的广度优先搜索算法需使用的辅助数据结构为队列 广度优先用队列,深度优先用栈。 广度优先: 当一个节点被加入队列时,要标记为已遍历,遍历过程中,对于队列第一个元素,遍历其所有能够能一步达到的节点,如果是标记未遍历的,将其加入队列,从第一个元素出发所有能一步直接达到的节点遍历结束后将这个元素出列。 深度优先: 当遍历到某个节点A时,如果是标记未遍历,将其入栈,遍历它能够一步直接达到的节点,如果是标记未遍历,将其入栈且标记为已遍历,然后对其进行类似A的操作,否则找能够一步直接达到的节点进行类似操作。 直到所有能够一步直接达到的节点都已遍历,将A出栈。 11、 折半查找属于随机访问特性链表不行 堆排序也不能用链表因为调整堆时没法随机访问底层孩子节点 快速排序可以链表、归并排序可用链表、基数排序可用链表 插入排序链表比数组要快一些减少移动次数 12、 线性表中的链表: (1)适用于数据项数量不能预知的情况; (2)逻辑相邻的2元素的存储空间可以是不连续的;(3)链表节点一般有数据元素和指针域两部分组成;(4)存储空间需要动态分配。 13、 数组的定义,声明,赋值,分类如下: A选项只能算是一个数组的声明,而非定义,也不是赋值 B选项三条语句都是赋值 C选项是定义 D选项是定义,然后两条语句是赋值 14、 最坏情况下,合并两个大小为n的已排序数组所需要的比较次数为2n-1; 最好情况下,合并两个大小分别为n,m的已排序数组所需要的比较次数为min(n,m)。 15、 数组与链表的区别 数组静态分配内存,链表动态分配内存; 数组在内存中连续,链表不连续; 数组元素在栈区,链表元素在堆区; 数组利用下标定位,时间复杂度为O (1),链表定位元素时间复杂度O(n); 数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O (1)。 链表: 链表是一块不连续的动态空间,长度可变;链表需要按顺序检索节点,效率低; 链表的优点是可以快速插入和删除节点,大小动态分配,长度不固定。 链表不存在越界问题。 数组: 数组是一快连续的空间,声明时长度就需要固定。 数组的优点是速度快,数据操作直接使用偏移地址。 数组有越界问题。 16、 静态链表是用数组存储节点数据,模拟链表的实现,但是没有用到指针。 每个数组节点包括两部分: data域和cursor(游标)域。 data存储数据,cursor指明下个元素在数组中的下标。 (1)存取第i个元素时,需要从头遍历到i-1和元素,由第i-1个节点的cursor,才能知道第i个元素存储的位置,因此和i是相关的。 (2)使用数组对元素进行存储,在定义时大小已经确定。 (3)插入和删除操作无需移动元素,只需要修改cursor游标的值即可,就像修改动态链表中的指针一样。 17、 一个有序数列,序列中的每一个值都能够被2或者3或者5所整除,这个序列的初始值从1开始,但是1并不在这个数列中。 求第1500个值是多少 2、3、5的最小公倍数是30。 [1,30]内符合条件的数有22个。 如果能看出[31,60]内也有22个符合条件的数,那问题就容易解决了。 也就是说,这些数具有周期性,且周期为30. 第1500个数是: 1500/22=681500%68=4。 也就是说: 第1500个数相当于经过了68个周期,然后再取下一个周期内的第4个数。 一个周期内的前4个数: 2,3,4,5。 故,结果为68*30=2040+5=2045 18、 顺序存储结构在物理上一般是连续存储,而链式存储一般不占用连续空间,相对而言,顺序存储的存储密度就大(优点)。 19、 集合与线性表的区别在于是否允许元素重复; 线性表可以是有序的,也可以是无序的;集合不允许元素重复,线性表允许元素重复 20、 插入排序的原理: 始终定义第一个元素为有序的,将元素逐个插入到有序排列之中,其特点是要不断的移动数据,空出一个适当的位置,把待插入的元素放到里面去。 选择排序的原理: 每次在无序队列中“选择”出最小值,放到有序队列的最后,并从无序队列中去除该值(具体实现略有区别)。 21、 将对称矩阵中的n^2个元压缩存储在n(n+1)/2个元素的一维数组中,以行序为主序存储其下三角(包括对角线)中的元,假设一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构,则sa[k]和矩阵元素a[i,j]之间存在着一一对应的关系: 当i>.=j时,k=i(i-1)/2+j-1;当i 22、 在程序设计中,要对两个16K×16K的多精度浮点数二维数组进行矩阵求和时,行优先读取和列优先读取的区别是行优先快 23、 关于inta[10];问下面哪些不可以表示a[1]的地址? A.a+sizeof(int) //不正确,在32位机器上相当于指针运算a+4 B.&a[0]+1 //正确,数组首元素地址加1,根据指针运算就是a[1]的地址 C.(int*)&a+1 //正确,数组地址被强制类型转换为int*,然后加1,这样和B表示的一个意思 D.(int*)((char*)&a+sizeof(int)) //正确,数据地址先被转换为char*,然后加4,根据指针运算公式,向前移动4*sizeof(char),之后被转换为int*,显然是a[1]的地址 24、 若某线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用哪顺序表存储方式最节省时间。 线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算; 进行任意位置存取,这个最省时省力的就是数组了,也就是顺序表。 而且元素是在最后的位置进行插入和删除运算,也就不涉及其他元素进行位移的额外操作,最多涉及的就是去扩展空间了。 25、 已知数组D的定义是intD[4][8];,现在需要把这个数组作为实参传递给一个函数进行处理。 下列说明汇总可以作为对应的形参变量说明的是()。 int(*s)[8],intD[][8] int*s[8];//定义一个指针数组,该数组中每个元素是一个指针,每个指针指向哪里就需要程序中后续再定义了。 int(*s)[8];//定义一个数组指针,该指针指向含8个元素的一维数组(数组中每个元素是int型)。 区分int*p[n];和int(*p)[n];就要看运算符的优先级了。 int*p[n];中,运算符[]优先级高,先与p结合成为一个数组,再由int*说明这是一个整型指针数组。 int(*p)[n];中()优先级高,首先说明p是一个指针,指向一个整型的一维数组。 26、 线性表的顺序存储结构是一种随机存取的存储结构, 顺序存储就是以数组的形式存储,那我们取某个元素就可以直接以下标的形式取出,不需要像链表那样从头遍历,所以是随机存取 27、 对n个记录的线性表进行快速排序为减少算法的递归深度,每次分区后,先处理较短的部分。 在快速排序中,需要使用递归来分别处理左右子段,递归深度可以理解为系统栈保存的深度,先处理短的分段再处理长的分段,可以减少时间复杂度; 如果按长的递归优先的话,那么短的递归会一直保存在栈中,直到长的处理完。 短的优先的话,长的递归调用没有进行,他是作为一个整体保存在栈中的,所以递归栈中的保留的递归数据少一些。 28、 三元组转置: (1)将数组的行列值相互交换 (2)将每个三元组的i和j相互交换(3)重排三元组的之间的次序便可实现矩阵的转置 29、 数组比线性表速度更快的是原地逆序 (1)原地逆序 (2)返回中间节点(3)选择随机节点 30、 A,线性表逻辑上是线性的,存储上可以是顺序的,可以是链式的 B,顺序存储和链式存储各有优缺点 C,链式存储可以连续,可以不连续,存储时不管其连续还是不连续,都是用指针指向下一个结点 D,二维数组是顺序存储的线性表,其元素都是线性表的元素,二维数组是其数组元素为线性表的线性表。 E,插入、删除和搜索是数据结构应该具备的基本操作 31、 用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j沿链移动的操作为j=r[j].next。 32、 当很频繁地对序列中部进行插入和删除操作时,应该选择使用的容器是list。 C++STL的实现: (1).vector底层数据结构为数组,支持快速随机访问 (2).list底层数据结构为双向链表,支持快速增删 (3).deque底层数据结构为一个中央控制器和多个缓冲区,详细见STL源码剖析P146,支持首尾(中间不能)快速增删,也支持随机访问 (4).stack底层一般用23实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时 (5).queue底层一般用23实现,封闭头部即可,不用vector的原因应该是容量大小有限制,扩容耗时 (6).45是适配器,而不叫容器,因为是对容器的再封装 (7).priority_queue的底层数据结构一般为vector为底层容器,堆heap为处理规则来管理底层容器实现 (8).set底层数据结构为红黑树,有序,不重复 (9).multiset底层数据结构为红黑树,有序,可重复 (10).map底层数据结构为红黑树,有序,不重复 (11).multimap底层数据结构为红黑树,有序,可重复 (12).hash_set底层数据结构为hash表,无序,不重复 (13).hash_multiset底层数据结构为hash表,无序,可重复 (14).hash_map底层数据结构为hash表,无序,不重复 (15).hash_multimap底层数据结构为hash表,无序,可重复 33、 在java中,声明一个数组时,不能直接限定数组长度,只有在创建实例化对象时,才能对给定数组长度.。 如下,1,2,3可以通过编译,4,5不行。 而String是Object的子类,Stringa[]、String[]a、Objecta[]均可定义一个存放50个String类型对象的数组。 (1).Stringa[]=newString[50]; (2).Stringb[]; (3).charc[]; (4).Stringd[50]; (5).chare[50]; 34、 几种常见的数据结构的操作性能对比如下图所示 由上图可见,平衡二叉树的查找,插入和删除性能都是O(logN),其中查找和删除性能较好;哈希表的查找、插入和删除性能都是O (1),都是最好的。 35、 有两个N*N的矩阵A和B,想要在PC上按矩阵乘法基本算法编程实现计算A*B。 假设N较大,本机内存也很大,可以存下A、B和结果矩阵。 那么,为了计算速度,A和B在内存中应该如何存储(按行存指先存储第一行,再第二行,直到最后一行;按列存指先存储第一列,再第二列,直到最后一列)? A按行存,B按行存。 我们来看看传统的分块矩阵相乘: 很明显依然是行乘以列的方式。 再来看看Strassen矩阵相乘: 同样是分块,只是计算方式不同 很明显,涉及到行的加法(a+b,c+d,e+f,g+h),列的减法(f-h,g-e,b-d,a-c),对角线的加法(a+d,e+h)以及行列的乘法,所以无论是 ∙A按行存,B按行存。 ∙A按行存,B按列存。 计算速度都是差不多的。 36、 既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找 37、 在一个有8个int数据的数组中,随机给出数组的数据,找出最大和第二大元素一定需要进行(9)次比较: 比如ABCDEFGH,通过8进4的方式,A与B比较,C与D比较.....然后再4进2,A与C比较(假设A,C比B,D大),E与G比较。 再2进1,比如A与E比较(假设A,E比C,G大)选出最大的A,总共7次。 然后次大的数一定是被最大数PK下去的,所以再选BCE三个比较2次得到次大的数 A AE ACEG(7次)ABCDEFGH 再选BCE中最大的(2次),共9次,不过可以这个方法比较次数是少一点,但是所需要的空间大,要记下与沿途的最大值比较的数。 38、 数组指针和指针数组有什么区别 数组指针只是一个指针变量,它占有内存中一个指针的存储空间; 指针数组是多个指针变量,以数组形式存在内存当中,占有多个指针的存储空间; 数组指针(也称行指针) 定义int(*p)[n]; ()优先级高,首先说明p是一个指针,指向一个整型的一维数组,这个一维数组的长度是n,也可以说是p的步长。 也就是说执行p+1时,p要跨过n个整型数据的长度。 如要将二维数组赋给一指针,应这样赋值: inta[3][4]; int(*p)[4];//该语句是定义一个数组指针,指向含4个元素的一维数组。 p=a;//将该二维数组的首地址赋给p,也就是a[0]或&a[0][0] p++;//该语句执行过后,也就是p=p+1;p跨过行a[0][]指向了行a[1][] 所以数组指针也称指向一维数组的指针,亦称行指针。 指针数组 定义int*p[n]; []优先级高,先与p结合成为一个数组,再由int*说明这是一个整型指针数组,它有n个指针类型的数组元素。 这里执行p+1是错误的,这样赋值也是错误的: p=a;因为p是个不可知的表示,只存在p[0]、p[1]、p[2]...p[n-1],而且它们分别是指针变量可以用来存放变量地址。 但可以这样*p=a;这里*p表示指针数组第一个元素的值,a的首地址的值。 如要将二维数组赋给一指针数组: int*p[3]; inta[3][4]; for(i=0;i<3;i++) p[i]=a[i]; 这里int*p[3]表示一个一维数组内存放着三个指针变量,分别是p[0]、p[1]、p[2] 所以要分别赋值。 这样两者的区别就豁然开朗了,数组指针只是一个指针变量,似乎是C语言里专门用来指向二维数组的,它占有内存中一个指针的存储空间。 指针数组是多个指针变量,以数组形式存在内存当中,占有多个指针的存储空间。 还需要说明的一点就是,同时用来指向二维数组时,其引用和用数组名引用都是一样的。 比如要表示数组中i行j列一个元素: *(p[i]+j)、*(*(p+i)+j)、(*(p+i))[j]、p[i][j] 39、 【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆,删除堆顶元素0后的结果是 【1、2、5、4、3、9、7、8、6】 首先,题目有问题,[0,2,1,4,3,9,5,8,6,7],原数组是这样才对得上号。 第二,堆是一种经过排序的完全二叉树,最小堆: 根结点的键值是所有堆结点键值中最小者。 根据这个不难写出原来堆依次为顶层0第二层21第三层4395第四层867 第三,最小堆删除堆顶后,用最后一个元素暂代堆顶,然后变成顶层7第二层21第三层4395第四层86,7>2>1,故1和7对调,对调后顶层1第二层27第三层4395第四层86;因
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数组 学习 笔记