《数据结构数组学习笔记》由会员分享，可在线阅读，更多相关《数据结构数组学习笔记（18页珍藏版）》请在金锄头文库上搜索。
1、数组学习笔记1、java中的数据类型分类：基本数据类型（或叫做原生类、内置类型）8种：整数：byte，short, i nt. Io ng （默认是 int 类型）浮点类型：float，double （默认是double类型） 字符类型：char布尔类型：boolean引用数据类型3种：数组，类，接口其中，基本数据类型之间除了 boolea n,其他数据类型之间可以任意的相互转换（强制转化 或默认转换），这个与C+中有点区别。数组是对象，int float char这些基本类型不是对象。关于如何判断基本类型和对象,参考下面的: 行为: 基本类型只是一个值，没有任何行为 对象类型有自己的行为 内
2、存分配: 基本类型在栈内分配 对象在堆内分配 对象引用保存在栈内 引用与值: 基本类型是值类型，仅表示一个值，保存在栈内 引用类型分两部分，对象引用保存在栈内，对象保存在堆内, 访问变量，是使用的引用找对象2、对一个排好序的数组进行查找，时间复杂度为（）二分查找:n,n/2, n/4令n/2*k=1 得 k=log2n （以2为为底的对数）3、 short int : 2 个字节 sizeof返回的值表示的含义如下(单位字节)：数组一编译时分配的数组空间大小；指针一存储该指针所用的空间大小(存储该指针的地址的长度，是长整型，应该 为4 )；类型一该类型所占的空间大小；对象对象的实际占用空间大小
3、；函数一函数的返回类型所占的空间大小。函数的返回类型不能是void。short a100空间 100*24、和顺序栈相比，链栈有一个比较明显的优势是通常不会出现栈满的情况 链栈存在于不连续的内存中，依靠节点指向后一个节点的指针进行地址查找 顺序栈就是数组，在内存中是连续的5、(1) 数据结构对广义表的表头和表尾是这样定义的：如果广义表LS=(a1,a2.an)非空，则al是LS的表头，其余元素组成的表(a2,a3,.an) 是称为LS的表尾。根据定义，非空广义表的表头是一个元素，它可以是原子也可以是一个子表，而表尾则必 定是子表。例如:LS=(a,b),表头为a,表尾是(b)而不是b.另外：L
4、S= (a)的表头为a,表尾 为空表()(2) 非空广义表，除表头外，其余元素构成的表称为表尾，所以非空广义表尾一定是个表。 广义表即我们通常所说的列表(lists)。它放松了对表元素的原子性限制，允许他们有自身结 构。广义表的长度：最大括号中的逗号数+1广义表的深度：展开后含括号的层数。广义表的特性：广义表的元素可以是子表，而子表的元素还可以是子表。广义表可为其他广义表所共享。广义表可以是一个递归的表，即广义表也可以是其本身的一个子表广义表(a,b,c),d,e,f)的长度为4, 4个元素分别为子表(a,b,c )和单元素d,e,f。二维以上的数组其实是一种特殊的广义表6、假设以行优先顺序存
5、储三维数组A567,其中元素A000的地址为1100,且每个元素 占2个存储单元，则A432的地址是()三维比如说是x,y,z组成的立体，按行存储就是先存yz面，三维数组am1m2m3中若按行优先存储，设a000的起始地址为p,每个元素占n个单 元，则aijk啲起始地址为：Ioc(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、从
6、逻辑结构上看,n维数组的每个元素均属于n个向量，像2为数组的每个元素属于2个向 量Z(x,y),通俗的说，在Z中增加一维，也就是在每个元素增加一类属性，也就是增加一个向量,此时Z中每个元素已经对应三种属性(向量)同理,n维数组的每个元素均属于n个向量.8、给定一个m行n列的整数矩阵(如图)，每行从左到右和每列从上到下都是有序的。判断 一个整数k是否在矩阵中出现的最优算法，在最坏情况下的时间复杂度 。杨氏矩阵查找算法：从矩阵的右上角开始，若右上角元素 大于所找，则可右上角元素所在的列的所有元素均大于所 找元素，下次查找忽略该列；若右上角元素小于所找，则 右上角元素所在行的所有元素均小于所找元素，
7、下次查找, 忽略该行；若相等，结束查找；否则，由新形成的矩阵利 用上述方式继续查找。0(m+n).1485 76 10111214 16 1891519218、数组与指针的区别(1) 数组要么在静态存储区被创建(如全局数组)，要么在栈上被创建。(2) 用运算符sizeof可以计算出数组的容量(字节数)(3) 指针可以随时指向任意类型的内存块。数组要么在静态存储区被创建(如全局数组)，要么在栈上被创建。指针可以随时指向任意 类型的内存块。(1) 修改内容上的差别char a = “hello”;a0 = X：char *p = “world”; /注意p指向常量字符串p0 = X; /编译器不能
8、发现该错误，运行时错误(2) 用运算符sizeof可以计算出数组的容量(字节数)。sizeof(p),p为指针得到的是一个 指针变量的字节数，而不是p所指的内存容量。C+/C语言没有办法知道指针所指的内存 容量，除非在申请内存时记住它。注意当数组作为函数的参数进行传递时，该数组自动退化 为同类型的指针。char a = hello world;char *p = a;coutvv sizeof(a) endl; / 12 字节 coutvv sizeof(p) vv endl; / 4 字节计算数组和指针的内存容量void Fun c(char a100)coutvv sizeof(a) vv
9、 endl; / 4 字节而不是 100 字节9、稀疏矩阵一般的压缩存储方法有两种,即三元组和十字链表稀疏矩阵在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布 是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点 存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下 标直接存取矩阵中的元素。（1）.三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所 在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储，因此便于进行依行 顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储
10、空间。（2）.十字链表：是既带行指针又带列指针的链接存储方式，每个三元组结点处于所在行单 链表与列单链表的交点处，当矩阵的非零元个数和位置在操作过程中变化较大时，用这种存 储结构更为恰当。在十字链表中，每个非零元可用一个含五个域的结点表示，其中i, j和e三个域分别表示 该非零元所在的行、列和非零元的值，向右域right用以链接同一行中下一个非零元，向下 域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性 链表，同一列的非零元通过down域链接成一个线性链表，每个非零元既是某个行链表中 的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，
11、故称这 样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组 表示之。10、图的广度优先搜索算法需使用的辅助数据结构为队列广度优先用队列，深度优先用栈。广度优先：当一个节点被加入队列时，要标记为已遍历，遍历过程中，对于队列第一个元素， 遍历其所有能够能一步达到的节点，如果是标记未遍历的，将其加入队列，从第一个元素出 发所有能一步直接达到的节点遍历结束后将这个元素出列。深度优先：当遍历到某个节点A时，如果是标记未遍历，将其入栈，遍历它能够一步直接 达到的节点，如果是标记未遍历，将其入栈且标记为已遍历，然后对其进行类似A的操作， 否则找能够一步直接达到的节点进行类似操作
12、。直到所有能够一步直接达到的节点都已遍 历，将A出栈。11、折半查找属于随机访问特性链表不行堆排序也不能用链表因为调整堆时没法随机访问底层孩子节点快速排序可以链表、归并排序可用链表、基数排序可用链表插入排序链表比数组要快一些减少移动次数12、线性表中的链表：（1）适用于数据项数量不能预知的情况；（2）逻辑相邻的2元素的存储空间可以是不连 续的；（3）链表节点一般有数据元素和指针域两部分组成；（4）存储空间需要动态分配。数组的定义，声明，赋值，分类如下:下列数错谋的是A. intintArray2=2:C. inta=D int a =new int2 : aO=new int3: a1=new
13、 int3;A选项只能算是一个数组的声明，而非定义，也不是赋值B选项三条语句都是赋值C选项是定义D选项是定义，然后两条语句是赋值14、最坏情况下，合并两个大小为n的已排序数组所需要的比较次数为2n-1;最好情况下，合并两个大小分别为n，m的已排序数组所需要的比较次数为min(n,m)。15、数组与链表的区别数组静态分配内存，链表动态分配内存；数组在内存中连续，链表不连续；数组元素在栈区，链表元素在堆区；数组利用下标定位，时间复杂度为0(1),链表定位元素时间复杂度0(n)； 数组插入或删除元素的时间复杂度0(n),链表的时间复杂度0(1)。链表：链表是一块不连续的动态空间，长度可变；链表需要按
14、顺序检索节点，效率低; 链表的优点是可以快速插入和删除节点，大小动态分配，长度不固定。链表不存在越界问题。数组：数组是一快连续的空间，声明时长度就需要固定。 数组的优点是速度快，数据操作直接使用偏移地址。数组有越界问题。16、静态链表是用数组存储节点数据，模拟链表的实现，但是没有用到指针。每个数组节点包括 两部分：data域和cursor （游标）域。data存储数据，cursor指明下个元素在数组中的下 标。（1）存取第i个元素时，需要从头遍历到i-1和元素，由第i-1个节点的cursor，才能知道 第i个元素存储的位置，因此和i是相关的。（2）使用数组对元素进行存储，在定义时大小已经确定。
15、（3）插入和删除操作无需移动元素，只需要修改cursor游标的值即可，就像修改动态链表 中的指针一样。17、一个有序数列，序列中的每一个值都能够被2或者3或者5所整除，这个序列的初始值从1 开始，但是1并不在这个数列中。求第1500个值是多少2、3、5的最小公倍数是30。 1,30内符合条件的数有22个。如果能看出31,60内也有22 个符合条件的数，那问题就容易解决了。也就是说，这些数具有周期性，且周期为30.第1500个数是：1500/22=68 1500%68=4。也就是说：第1500个数相当于经过了 68个周期，然后再取下一个周期内的第4个数。一个周期内的前4个数：2,3,4,5c故，结果为 68*30=2040+5=204518、顺序存储结构在物理上一般是连续存储，而链式存储一般不占用连续空间，相对而言，顺序存 储的存储密度就大（优点）。19、集合与线性表的区别在于是否允许元素重复；线性表可以是有序的，也可以是无序的
