数据结构数组学习笔记

《数据结构数组学习笔记》由会员分享，可在线阅读，更多相关《数据结构数组学习笔记（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) .=j 时，k=i(i-1)/2+j-1;当 ij 时， k=j(j-1)/2+i-1;22、在程序设计中，要对两个16KX16K的多精度浮点数二维数组进行矩阵求和时，行优先读取和 列优先读取的区

9、别是行优先快23、关于int a10;问下面哪些不可以表示a1的地址？A. a+sizeof(i nt)/不正确，在32位机器上相当于指针运算a + 4B. & a0+1/正确，数组首元素地址加1,根据指针运算就是a1的地址C. (in t* )&a+1/正确，数组地址被强制类型转换为int*，然后加1,这样和B表示的一个意思D. (in t*)(char* )&a+sizeof(i nt)/正确，数据地址先被转换为char*，然后加4，根据指针运算公式，向前移动4 * sizeof(char)， 之后被转换为int*,显然是a1的地址24、若某线性表最常用得操作是存取任一指定序号的元素和在最

10、后进行插入和删除运算，则利用哪 顺序表存储方式最节省时间。线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算；进行任意位置存取，这个最省时省力的就是数组了，也就是顺序表。而且元素是在最后的位置进行插入和删除运算，也就不涉及其他元素进行位移的额外操作，最 多涉及的就是去扩展空间了。已知数组D的定义是int D48;，现在需要把这个数组作为实参传递给一个函数进行处理。下列 说明汇总可以作为对应的形参变量说明的是（）。int（*s）8, int D8int *s8; 定义一个指针数组，该数组中每个元素是一个指针，每个指针指向哪里就需要程序中 后续再定义了。int （*s）8; /定

11、义一个数组指针，该指针指向含8个元素的一维数组（数组中每个元素是int型）。区分int *pn;和int （*p）n;就要看运算符的优先级了。int *pn;中，运算符优先级高，先与p结合成为一个数组，再由int*说明这是一个整型指针数 组。int （*p）n;中（）优先级高，首先说明p是一个指针，指向一个整型的一维数组。26、线性表的顺序存储结构是一种随机存取的存储结构，顺序存储就是以数组的形式存储，那我们取某个元素就可以直接以下标的形式取出，不需要像 链表那样从头遍历，所以是随机存取27、对n个记录的线性表进行快速排序为减少算法的递归深度，每次分区后，先处理较短的部分。在快速排序中，需要使

12、用递归来分别处理左右子段，递归深度可以理解为系统栈保存的深度先 处理短的分段再处理长的分段，可以减少时间复杂度；如果按长的递归优先的话，那么短的递归会一直保存在栈中，直到长的处理完。短的优先的话, 长的递归调用没有进行，他是作为一个整体保存在栈中的，所以递归栈中的保留的递归数据少 止匕 o28、三元组转置：（1）将数组的行列值相互交换（2）将每个三元组的i和j相互交换（3）重排 三元组的之间的次序便可实现矩阵的转置http:/sharecourse.upl n.c n/courses/c_809_05/theory/module_5/module_5.html29、数组比线性表速度更快的是原地

13、逆序（1）原地逆序（2）返回中间节点（3）选择随机节点A, 线性表逻辑上是线性的，存储上可以是顺序的，可以是链式的B, 顺序存储和链式存储各有优缺点C, 链式存储可以连续，可以不连续，存储时不管其连续还是不连续，都是用指针指向下一个结 占八、D，二维数组是顺序存储的线性表，其元素都是线性表的元素，二维数组是其数组元素为线性表 的线性表。E,插入、删除和搜索是数据结构应该具备的基本操作31、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为 j=rj. next。32、当很频繁地对序列中部进行插入和删除操作时，应该选择使用的容器是list。C+ STL的

14、实现：(1) .vector底层数据结构为数组，支持快速随机访问(2) .list 底层数据结构为双向链表，支持快速增删(3) .deque 底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146, 支持首尾(中间不能)快速增删，也支持随机访问(4) .stack底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限制， 扩容耗时(5) .queue 底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限 制，扩容耗时(6) .45是适配器，而不叫容器，因为是对容器的再封装(7) .priority_queue的底层数据结构一般为vect

15、or为底层容器，堆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表，无序，可重复在java中，声明一个数组时，不能

16、直接限定数组长度，只有在创建实例化对象时，才能对给定 数组长度.。如下，1，2,3可以通过编译，4, 5不行。而Str ing是Object的子类，Str in g a、Str in ga、 Object a均可定义一个存放50个Str ing类型对象的数组。(1) . String a=new String50;(2) . String b;(3) . char c;(4) . String d50;(5) . char e50;34、几种常见的数据结构的操作性能对比如下图所示数据结构臺找插入删除遍历数组0(N)0(1)(XN)肴序数姐0(1ogN)O(N)O(H)O(N)链表0(N)0(1

17、)O(N)-有序链表0(N)0(N)O(N)0(N)二叉树（一般情况）O(logN)OOogN)O(logN)0(N)二叉树（最坏情况）0ocn由上图可见，平衡二叉树的查找，插入和删除性能都是O（logN），其中查找和删 除性能较好；哈希表的查找、插入和删除性能都是O（1），都是最好的。35、有两个N*N的矩阵A和B,想要在PC上按矩阵乘法基本算法编程实现计算A*B。假设N较大, 本机内存也很大，可以存下A、B和结果矩阵。那么，为了计算速度，A和B在内存中应该如 何存储（按行存指先存储第一行，再第二行，直到最后一行；按列存指先存储第一列，再第二 列，直到最后一列）？ A按行存，B按行存。我们来

18、看看传统的分块矩阵相乘：很明显依然是行乘以列的方式。再来看看Strassen矩阵相乘：同样是分块，只是计算方式不同STPASSrNS AICCriTItHP1A(F-H)P2(A +B)HP3(C +D)EP4D(G-E)P5(A +D)(E +出P5D)(G +H)P7(A -C)(E +F)P5 十 P4-P2P3 + P4+ PBAB =列的减法(f-h,g-e,b-d,a-c)，对角线的明显，涉及到行的加法(a+b,c+d,e+f,g+h), 加法(a+d,e+h)以及行歹列的乘法，所以无论是the product AB can be done in O(nAlg(7)!Afield按

19、行存，B按行存。A按行存，B按列存。计算速度都是差不多的。36、既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找37、在一个有8个int数据的数组中，随机给出数组的数据，找出最大和第二大元素一定需要进行(9) 次比较：比如A B C D E F G H,通过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次得到次大的数AEEG (7 次)FGHAACBCDE再选BCE中最大的(2次)，共9次，不

20、过可以这个方法比较次数是少一点，但是所需要的 空间大，要记下与沿途的最大值比较的数。数组指针和指针数组有什么区别数组指针只是一个指针变量，它占有内存中一个指针的存储空间；指针数组是多个指针变量，以数组形式存在内存当中，占有多个指针的存储空间；数组指针(也称行指针)定义 int (*p)n;()优先级高，首先说明p是一个指针，指向一个整型的一维数组，这个一维数组的长度是n,也 可以说是p的步长。也就是说执行p+1时，p要跨过n个整型数据的长度。如要将二维数组赋给一指针，应这样赋值：in t a34;in t (*p)4; 该语句是定义一个数组指针，指向含4个元素的一维数组。p=a;将该二维数组的

21、首地址赋给p,也就是a0或&a00p+;该语句执行过后，也就是p=p+1;p跨过行a0指向了行a1所以数组指针也称指向一维数组的指针，亦称行指针。指针数组定义 int *pn;优先级高，先与p结合成为一个数组，再由int*说明这是一个整型指针数组，它有n个指针类 型的数组元素。这里执行p+1是错误的，这样赋值也是错误的：p=a；因为p是个不可知的表 示，只存在p0、p1、p2.pn-1,而且它们分别是指针变量可以用来存放变量地址。但可以 这样*p=a;这里*p表示指针数组第一个元素的值，a的首地址的值。如要将二维数组赋给一指针数组：int *p3;in t a34;for(i=0;iv3;i+

22、)pi=ai;这里int *p3表示一个一维数组内存放着三个指针变量，分别是p0、p1、p2所以要分别赋值。这样两者的区别就豁然开朗了，数组指针只是一个指针变量，似乎是C语言里专门用来指向二 维数组的，它占有内存中一个指针的存储空间。指针数组是多个指针变量，以数组形式存在内 存当中，占有多个指针的存储空间。还需要说明的一点就是，同时用来指向二维数组时，其引用和用数组名引用都是一样的。比如要表示数组中 i 行 j 列一个元素：*(pi+j)、*(*(P+i)+j)、(*(P+i)j、pij【0、2、1、4、3、9、5、& 6、7】是以数组形式存储的最小堆，删除堆顶元素0后的结果是【1、 2、 5

23、、 4、 3、 9、 7、 8、 6】首先，题目有问题，0，2，1，4，3，9，5， 8，6, 7，原数组是这样才对得上号。第二，堆是一种经过排序的完全二叉树，最小堆： 根结点的键值是所有堆结点键值中最小者。根据这 个不难写出原来堆依次为 顶层0 第二层2 1 第三层4395 第四层867第三，最小堆删除堆顶后，用最后一个元素暂代堆 顶，然后变成顶层7 第二层2 1 第三层4 39 5 第四层8 6，721,故1和7对调，对调后 顶层1 第二层27 第三层4395 第四层8 6；因为975,5和7对调，对调后 顶层1第二层2 5 第三层4 39 7 第四层8 6；形成新的最小堆40、在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是0(n)41、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节,则用三元组表示该矩阵时, 所需的字节数是(66)每个元素要用行号，列号，元素值来表示，由于二维稀疏矩阵的大小都是在256之内，所以行号和 列号只需要char来存储。在用三元组表示稀疏矩阵，还要三个成员来记住，矩阵的行数列数，总的 元素数，所以所需的字节数是10* (1+1+1) *2+3*2=66