数组以及链表相关

1、矩阵不仅表示多维数组，而且是表示图的重要工具。图的表示方法有邻接矩阵和邻接表。
2、对于不同的特殊矩阵应该采用不同的存储方式。
对称矩阵只需要存一半，三角矩阵也有自己的存储方式。

3、二维数组可以理解为一维的一维，一维数组是线性表，那么二维数组可以看成数据元素为线性表的线性表。
4、数组名代表的是数组的首地址，是一个地址常量，所以不能给数组名赋值。
char * strcpy(char * dest,const char * src) // c语言的方法，将src内容存放到dest中，
5、c语言宏定义后面不能有分号。
6、二维数组a[1……m,1……n] ，每个元素大小为2字节
列存储：a[i,j]的偏移量为
[(j-1)* m+(i-1)]*2
行存储：a[i,j]的偏移量为
[(i-1)*n+(j-1)]*2
注意：如果数组从零开始就不用减1了。
7、二叉树是按数的大小存储的，左小右大。随机数未经排序不能用二叉树存储。‘
随机数数据类型不一样，也不能用数组存储；
随机数不强调数据之间的关系，图不适合；
hash表离散存储，利用hash算法决定存储位置，遍历麻烦。

8、访问链表是链式存储结构时无法支持随机访问，要访问一个指定位置的元素必须从头开始做指针移动。
9、线性表有两种存储方式：顺序表，链式表。顺序表逻辑顺序和物理顺序一致。而链式表不是。

10、数组的长度是固定不变的，数组是线性表的一种。
而线性表有多种形式（顺序表，链式表），其长度可变。
11、队列、栈、链表、数组都是线性表。
关联数组是一种具有特殊索引方式的数组，不仅可以通过整数来索引它，还可以使用字符串或者其他类型的值（除了null）来索引它。
关联数组，又称映射（Map）、字典。是一种抽象的数据结构，它包含类似于（键、值）的有序对。 不是线性表。
关联数组和数组类似，由以名称作为键的字段和方法组成。它包含标量数据，可用索引值来单独选择这些数据，和数组不同的是，关联数组的索引值不是非负的的整数而是任意的标量，这些标量称为keys，可以在以后用于检索数组中的数值。
关联数组的元素没有特定的顺序，你可以把它们想象为一组卡片，每张卡片上半部分是索引而下半部分是数值。
12、二维数组定义：
int[2][3]={1,2,3,4,5,6},这种定义正确的，也就是二维数组也可以当做特殊的一维数组，可以用一维数组定义。

13、int(p)[4],()优先级最高先看小括号里的，首先p是一个指针，类型是int，后面的[4]表明这是一个指向一维整型数组的指针。
int *p[4]，[]优先级高，首先p[4]是一个数组，类型是int *，也就是这是一个存放4个整型指针（指向整型数据的指针）的数组。

14、快速排序：关键节点前面的元素都比它小，后面的元素都比它大。
选择排序：从剩余元素后面找最小元素和当前元素交换；
插入排序：关键元素前面的元素已经排好序。
15、二分查找，注意下一轮查找的low或high，应该是min+1或者min-1，而不是min,千万别犯浑。还有并不是high和low等于那个寻找的值，而是min的值等于寻找的值
16、稀疏矩阵压缩的存储方法是：三元组，十字链表，行逻辑链接的顺序表。
三元组表示稀疏矩阵可大大节省空间，但是当涉及到矩阵运算时，要大量移动元素。
十字链表表示法可以避免大量移动元素。
17、二维数组和一维数组的区别在于，二维数组可以理解为一维的一维。在一维中 * 表示取数值，在二维中 * 表示取第几行的地址，**表示取值。
18、注意：并不是所有的数据结构都有搜索算法，栈就没有搜索操作。
19、将10阶对称矩阵压缩存储到一维数组中，数组长度最少为：
主对角线都存：10个；
剩下的90个只存一半45个；
共55个。
20、线性结构应满足：有且只有一个根结点与每个结点最多有一个前件，也最多有一个后件。
虽然只有一个根节点的数据结构不一定是线性结构，但是所有一个以上根节点的数据结构一定是非线性结构。
21、顺序存储：在一块连续的存储区域一个接着一个的存放数据。顺序存储方式把逻辑上相邻的节点存储在物理位置相邻的存储单元里，节点间逻辑关系由存储单元的相邻关系来体现。顺序存储方式也称为顺序存储结构，一般采用数组或结构数组来描述。
优点：
在结点等长时可以随机存取；
存储密度高节省存储空间；
用结点的物理次序反映结点之间的逻辑关系。
缺点：
插入和删除结点时要大量移动结点；
必须静态分配连续空间。
链式存储：链式存储方式比较灵活，不要求逻辑上相邻的结点在物理位置上相邻，结点间的逻辑关系由附加的引用字段来表示。一个结点的引用字段往往指向下一个节点的存放位置。链式存储方式也称为链式存储结构。
优点：
插入和删除比较灵活，不需要大量移动结点。
动态分配空间比较灵活，不需要预先申请最大的连续空间。
缺点：
增加指针的空间开销。
检索必须沿链进行，不能随机存取。
22、广义表长度=属于最外层括号的逗号数加一；
广义表深度：删除几层括号后成为一个序列（括号层数）。
例如广义表E（（a,(a,b),((a,b),c)））的长度为0+1=1；
深度为4？

23、n个结点的二叉链表共有2n个链域，除了根节点以外，其他每个节点都被一个链域所指向，因此用到的链域为n-1个，即空域个数为：2n-(n-1)=n+1个。
24、栈是限定在一端进行插入和删除的线性表，允许插入和删除的一端称为栈顶。栈按照“先进后出（FILO）”或“后进先出”（LIFO）组织数据，栈具有记忆作用。
可以用浏览器网页的情况来理解，我们在浏览第一个网页A，点网页里的一个标题，进入网页B ，再在网页B里点击一个标题，进入网页C，这时连续按后退退回网页A，这说明浏览网页有记忆功能和，这和栈的原理差不多，所以说栈有记忆功能。
。
25、栈和链表是两种不同的数据结构。栈是逻辑结构的概念，是特殊线性表，而链表是存储结构的概念，二者不是同类项。
26、图和树是非线性数据结构。

27、栈是解决封闭对应问题的有效方法。比如在解析xml中，遇到标签是一对的话，一对中间嵌套一对，左标签不同都入栈，如果遇到与之对应的有标签就出栈，不能找到与之对应的标签，则说明标签不对称，是无效的xml文件。
栈的应用：符号匹配（一对符号），表达式求值，实现函数调用。
28、lchild（左孩子域）：
0：指示左孩子
1：指示节点的前驱
rchild（右孩子域）：
0：指示右孩子
1：指示节点的后驱。
29、在双向链表中插入某个节点时：
先修改待插入点的前驱和后驱，再修改原来两个节点中后一个节点的前驱以及前一个节点的后继，可以简单记为前驱，后继，前驱，后继的修改顺序。

30、头结点，是为了使空链表和非空链表的处理统一而在链表的头部增加一个结点，这样无论链表是否为空，头指针都指向头结点，头结点中不存数据而只是存放指向第一个节点的指针，没有头结点的链表，头指针就指向第一个节点。
31、单链表插入不需要移动元素，时间复杂度为O(1)，但是要保持有序状态，顺序存取需要按位置访问元素，时间复杂度为O(n)
32、如果数组a比数组b大很多，可能跨更多的页，缺页率高或者缓存命中更低。
一般小循环放外边，大循环放里面。
33、稀疏矩阵：矩阵中大多数元素为0元素。
用一个三元组存放矩阵中的元素，形式为（i,j,e）.其中i表示行号，j表示列号，e表示元素值。
每一个三元组表示一个稀疏矩阵中非零的元素。
34、short 2个字节。
sizeof;返回的值表示的含义如下：
数组：编译时分配的数组空间大小；
指针：存储该指针所用的空间大小（存储该指针的地址的长度，是长整型，应该为4）；
类型：该类型所占空间大小。
对象：对象的实际占用空间大小。
函数：函数的返回类型所占空间的大小。函数的返回类型不能是void。

比如short a[100]，sizeof（a）返回的是100*2=200

35、线性表长度的定义包含它所包含的元素的个数。
元素的类型决定了元素所占用存储空间的大小，但元素的个数不等价于元素的类型。
36、三元组的转置：行列互换，然后再按行排序。
37、如果链表数据是无序的，则单向搜索与双向搜索平均速度相同；
如果链表是有序的，而要搜索的数据距离最大值（最小值）较近，这种情况下双向搜索平均速度更快。
双向搜索更稳定，方差更小。

38、矩阵54的矩阵，有多少个长方形？
五行四列的表格（矩阵）有65条边，从六条边选两条（横向），从五条边中选两条（纵向），C（6,2）C（5,2）=1510=150.
39、concat函数的功能是：连接两个或多个数组。将返回连接数组后的副本，不影响原来的数组。
call函数调用一个对象的一个方法，以另一个对象替换当前对象。
js中的函数其实是对象，函数名是对函数对象的调用。
40、行优先读取和列优先读取的区别：
如果数组很大的话应该是行优先快，因为当数组过大的时候CPU无法一次性读取整个内存页面，这时候访问数据的时候就会发生页面置换，如果以列来访问就会发生频繁的置换，这时候就会消耗大量时间。
数组在内存中是按行优先存储，在虚存环境下，如果整个数组没有在内存中的话可以比列优先减少内存换进换出的次数。就算整个数组都在内存中，列优先访问a[i][j]还得计算一次乘法，行优先只需加1就可以了。
41、在字符数组中，如果元素加了双引号就是字符串，字符串本身也是一个一维数组，所以二维字符数组可以表示为元素为字符串的一维数组。
42、一般删除节点时会优先考虑删除节点。
第二种思路是：
把要删除的节点数据域的内容改成下一个节点的内容，再删除要删除的节点的下一个节点。
43、在一个长度为n的单链表尾部插入长度为m的单链表的算法时间复杂度为？
注意不是直接将单链表直接插到后面就行了，还要查找到链表m的末位位置。
尾插法：

将长度为m的单链表头部固定，设立一个指针进行尾部搜索，找到尾部的时间复杂度为O（m）
搜索长度为n的单链表的头结点，时间复杂度是O（1）
所以总的时间复杂度为O（m）
44、想构造链表需要一个指向此结构体的指针。这里指向此结构体的指针表示指向自身的指针域（自引结构）

list :底层数据结构为双向链表，支持快速删减；
vector:底层数据结构为数组，支持快速随机访问；
map：底层数据结构红黑树，除了hashmap无序，其他实现结构有序，不重复；
set：底层数据结构为红黑树，除了hashset无序，其他实现结构有序，不重复；
46、
随机存取-----顺序表；
顺序存取-----链表。
线性表的顺序存储结构和线性表的链式存储结构分别是随机存取和顺序存取；

47、设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端节点的位置分别是rear->next->next和rear，查找时间都是O（1），若用头指针来表示该链表，则查找终端节点的时间为O(n).
双链表如果没有指定是否含有尾指针，默认插入元素时，需要从头到尾搜索，再执行插入。想要在头部或者尾部快速执行插入和删除元素，需要增加头指针或尾指针，默认情况下没有。
48、

非循环的单链表只能找到他之后的节点。而循环链表因为是循环的，即使不是双向的，也能通过绕一圈的方式找到它前面的节点。所以可以说单循环链表从表中任一节点出发都能扫描到整个链表。
对于非循环的链表而言，头结点可以不存在，但是存在头结点作用会更好。而对于循环链表，必须需要头结点，不然的话，循环链表的最大作用循环就不好使了。
不断开原本的连接不能进行插入、删除。链表在内存中都是单独的存储单元，通过地址进行指向链接，不论是否是单循环还是双循环链表，在进行插入操作时都会断开。
但循环链表需要绕一圈才能找到它节点的直接前驱，并不容易，对于双向链表来说比较容易。

48、稀疏矩阵将非零元素所在行、列、非零元素的值组成一个三元组（i,j,v）：
在计算用三元组表示稀疏矩阵所需要的字节数时，不但需要计算非零元素的个数 * 3*每个元素所占的字节数，一般还要用三个整数来存储矩阵的行数、列数、和总元素个数，又需要3 * 每个元素所占的字节数。

49、char a[]=“string”; （√）
char a[]={0,1,2,3,4,5}; （√）
char a=“string”; （×）
或者用char *a="string"也对
将一个整型常量放到一个字符数组中，实际上就是把以该整型常量表示的ASCAII码放到内存单元中。（ASCAII码是以十进制整数表示的）
将一个字符常量放到一个字符变量中，实际上并不是把本身放到内存单元中去，而是把该字符的响应ASCAII代码放到内存单元中。

50、循环队列
进队：队尾指针（rear+1）%m;
出队：队头指针（front+1%m;
m为数组容量（容量不会因为出去了一个元素就改变的）
51、矩阵中的数据元素不可以是不同的数据类型。
52、广义表表头是第一个元素，表尾是除了表头之外的全部。
如果只有一个元素，那么表尾为空();

53、存储密度=单链表数据项所占空间/节点所占空间；
结点所占空间由数据项所占空间和存放后继结点地址的链域决定，所以存储密度小于1。

54、判断链表是否有环，可以用快慢指针来实现，两指针的移动速度不一样。如果相遇，则表示有环，否则表示无环。
比如：两个指针一个一次走一步，一个一次走两步，会相遇就表示有环。

55、双引号做了3件事：
申请了空间（在常量区），存放了字符串。
在字符串尾加上了‘/0’;
返回地址。
所以p="abcdefg"就是返回的地址赋值给了p.
56、要删除单向链表的最后一个节点，需要知道前一个节点，由于是单链表，不能直接由尾部接单得到前一个节点，与队列长度有关。
57、散列表的负载因子a,a=散列表中结点的数目/基本区域能能容纳的节点数。
58、删除双向链表的顺序应该是：先前驱，后后继。具体来说首先更新所要删除节点的前后节点的指针域（先前驱，后后继），然后再删除该节点。

59、队列有两种存储结构：循环队列和链队列
栈也有两种存储方法：一是顺序栈，二是链式栈。
60、线性链表只要求逻辑上的线性，至于物理存储位置不用关心，所以各元素的存储顺序是任意的。
61、折半查找法，成功时最大的比较次数是：[log2n]+1
100个元素的有序表，就看100能被2除多少次。

62、二维以上的数组其实是一种特殊的广义表；
数组一单建立，结构的元素个数和元素间的物理存储关系就不再变化；
数组是一种线性结构，但是数组中可以存储非线性表，比如完全二叉树；
数组采用顺序存储方式表示。（不要眼瞎，存取和存储差别很大）
63，在二维数组中，一维指针表示地址，在其基础上加个值还是一个地址，而且a[2][0]+2表示的是一个值+2不是地址。
64、数组从栈中分配空间，链表从堆中分配空间，但是在java中，new的东西都在堆，包括数组。
65、循环队列：当front=rear时，说明队列为空，元素个数为0,。
链表队列，在队列为链栈时，除了初始化构造皆为空外，当两个指针再次相遇时，这个链队列的元素为一个。
66、动态结构（比如线性链表，动态数组）不需要提前分配空间。
静态链表用的是结构数组，定义一个较大的结构数组作为备用节点空间（即存储池），需要提前分配较大的存储空间。静态链表的插入删除只需要改游标方可实现。

67、无向图的邻接表存储中，邻接表中的结点总数是边的2倍。
68、广义表中，tail取广义表除了第一个元素外的其它元素，head取第一个元素。
69、push()方法返回新数组的长度，并不是数组，不可以直接在用“.”操作符继续执行别的数组方法。
reverse()方法返回的是新数组；可以直接在用“.”操作符继续执行别的数组方法。
unshift()：向数组的开头添加一个或多个元素，返回新数组的长度。
splice()：从数组中添加/删除元素，返回被删除的元素。
sort()：返回排序后的数组。
70、渐进时间复杂度值n趋于无穷时的复杂度。
71、线性表：一对一
树：一对多
图：多对多
72、C语言中，字符串默认每个占用一字节，均以‘/0’结尾，‘/0’也占一字节。
char,short,int 各占1、2 、4个字节。