链表和数组的区别是什么?

1、数组是将元素在内存中连续存放，有每个元素占用内存相同，可以通过下表迅速查找到相应的元素；但是如果要在数组中添加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中；同样道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素；如果应用需要快速访问数据，很少或者不插入和删除元素，就应该用数组；

2、链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存储在元素中的指针联系在一起的；比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素；如果要访问的链表中的一个元素，需要从第一个元素开始，一直找到需要的元素位置；但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了；如果应用需要经常插入和删除元素你就需要用链表数据结构了；

注意：在C++中，使用数组处理一组数据类型相同的数据，但是不允许动态定义数组的大小（即在使用数组之前必须确定数组的大小）；而在实际应用中，用户使用数组之前有时无法确定数组的大小，只能将数组定义成足够大小，这样数组中有些控件可能不被使用，从而造成内存空间的浪费；链表采用的动态分配内存的形式实现，需要时可以使用new分配内存空间，不需要时使用delete将已分配的空间释放掉，不会造成内存空间的浪费；

反射：反射提供的是runtime阶段获取类的实例、方法、属性等，并且能够调用方法的途径，这种动态获取类信息和调用方法的机制被称为反射；

反射机制提供的功能： 1、在运行时判断任意一个类所属的类； 2、在运行时构建任意一个类的对象； 3、在运行时判定任意一个类的所具有的成员变量和方法； 4、在运行时调用任意一个对象的方法； 5、生成动态代理；

哈希表原理理解：

哈希表是根据键码值而直接进行访问的数据结构；也就是说可以通过把关键码值映射到表中一个位置来访问记录，以加快查找速度；这个映射函数叫做散列函数；

数组名和指针的区别 int arr[] = {1,2,3,4,5}; 定义一个数组，数组名为 arr，分别打印arr 本身的地址，arr 首元素的地址，以及arr本身；发现三者的值是相同的； 变量的三要素：变量名称；变量，即名为arr变量自己的地址，该地址存储了 arr 变量；arr 的值，为所指对象的值；

1.数组名取地址得到的是数组名所指元素的地址；对指针取地址得到的是指针变量自身的地址； 2.数组名是常量指针，指针时变量指针； 总结： 1.数组名代表了一个指向数组首元素的常量指针，一经定义，不可更改，数组名作为常量指针，其类型与数组元素类型相同。指针是变量指针，定义之后仍可更改，其类型在定义时确定； 2.当出现 sizeof，和&操作符时，数组名不在当成指向一个元素的常量指针来使用，而指针仍当成指向一个元素的变量指针来使用；

CPU 的结构主要包括运算器、控制单元、寄存器、高速缓存器和它们之间通讯的数据、控制及状态的总线； GPU 是用在个人电脑、工作站、游戏机和一些移动设备上运行绘图运算工作的微处理器；

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称； 抽象数据类型：是指一个数学模型及定义在该模型上的一组操作；

算法时间复杂度定义：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级； 算法的时间复杂度，也就是算法的时间度量，记作：T（n）= O(f(n))。它表随问题规模的增大。算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度；其中 f(n)是问题规模n的某个函数；

指导大 O 阶： 1.用常数1取代运行时间中的所有加法常数 2.在修改后的运行次数函数中，只保留最高阶项 3.如果最高阶项存在且不是1，则去除与这个项相乘的常数 得到的结果就是大 O 阶

算法的空间复杂度定义：通过计算算法所需要的存储空间

线性表：0个或者多个数据元素的有限序列；在较复杂的线性表中，一个数据元素可以由若干个数据项组成； 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素； 顺序存储结构的三个属性： 1.存储空间的其实位置；数组 data 2.线性表的最大存储容量； 数组的长度 3.线性表的当前长度；length

数组的长度和线性表的长度的区别： 数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般是不变的； 线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的； 在任何时候，线性表的长度应该小于等于数组的长度； 使用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度； 存储器中每个存储单元都有自己的编号，这个编号称为地址；

线性表顺序存储结构的优缺点： 优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任意位置的元素； 缺点：插入和删除操作需要移动大量元素；当线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的的“碎片”

为了表示每个数据元素与其直接后继元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继元素的地址；我们把存储数据元素信息的域称为数据域，把直接存储后继位置的域称为指针域；指针域中存储的信息被称为指针或链；这两部分信息组成数据元素的存储映像，称为结点；n 个结点链接成一个链表，即为线性表的链式存储结构。因为此链表的每个结点中都只包含一个指针域，所以叫做单链表； 链表中第一个结点的存储位置叫做头结点；最后一个结点指针为空； 有时我们为了方便，会在单链表的第一个结点前附设一个结点，称为头结点；头结点的数据域可以不存储任何信息；也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点指针；

头指针： 1.头指针是指链表指向第一个结点的指针，若链表有头结点，则指向头结点的指针； 2.头指针具有标识作用，所以常用头指针冠以链表的名字； 3.无论链表是否为空，头指针均不为空；头指针是链表的必要元素； 头结点： 1.头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（也可存放链表的长度） 2.有了头结点，对在第一元素结点前插入结点和删除第一个结点，其操作与其它结点的操作就统一了 3.头结点不一定是链表必须要素

结点是由存放数据元素的数据域和存放后继结点地址的指针域组成；

单链表结构和顺序存储结构的对比： 存储分配方式： 1.顺序存储结构用一段连续的存储单元依次存储线性表的数据元素 2.单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素 时间性能： 1.查找 顺序存储结构 O(1) 单链表 O(n) 2.插入和删除 顺序存储结构需要平均移动表长一半的元素，时间为 O(n) 单链表在线出某位置的指针后，插入和删除时间仅为O(1) 空间性能： 1.顺序存储结构需要预分配存储控件，分大了，浪费；分小了易发生上溢； 2.单链表不需要分配存储控件，只要有就可以分配，元素个数不受限制；

通过上面👆的对比，我们可以得出一些经验性的结论： 若线性表需要频繁的查找，很少进行插入和删除操作时，宜采用顺序存储结构；若需要频繁插入和删除时，宜采用单链表结构； 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题；否则就使用顺序存储结构；

用数组描述的链表叫做静态链表 静态链表的优缺点： 优点： 再插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点； 缺点： 没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性；

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表； 双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域；

栈和队列： 栈是限定仅在表尾进行插入和删除操作的线性表；我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表； 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表；

栈的链式存储结构简称为链栈；

栈的应用—-递归 我们把一个直接调用自己或者通过一系列的调用语句间接的调用自己的函数称为递归函数； 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出；

栈的引用—-后缀表达式 9+（3-1）*3+10/2————->9 3 1 - 3 * + 10 2 / + 后缀表达式

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表； 我们把队列的这种头尾相接的顺序存储结构称为循环队列；循环队列的通用的计算队列长度公式为：rear - front + queueSize % queueSize

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而异；我们把它简称为链队列；

串是由零个或多个字符组成的有限序列，又名叫字符串；

KMP算法的设计：

节点拥有的子树数称为节点的度；度为0的节点称为叶子节点或终端节点；度不为0的节点称为非终端节点或分支节点。除根节点之外，分支节点也称为内部节点；树的度是树内各节点的度的最大值；

树中节点的最大层次称为树的深度或高度；

二叉树的特点： 1.每个节点最多有两棵子树，所有的二叉树不存在度大于2的节点；注意不是只有两个子树，而是最多有，没有子树或者只有一棵子树也都是可以的； 2.左子树和右子树都是有顺序的，次序不能颠倒； 3.即使树中某个节点只有一棵树，也要区分它是左子树还是右子树；

特殊二叉树： 斜树：所有的节点都只有左子树的二叉树叫做左斜树；所有节点都只有右子树的二叉树叫做右斜树；这两种树都称为斜树； 满二叉树： 在一棵二叉树中，如果所有分支节点都存在左子树和右子树。并且所有叶子都在同一层上，这样的二叉树称为满二叉树；特点：1.叶子只能出现在最下一层，出现在其他层就不可能达成平衡； 2.非叶子节点的度一定是2，否则就不是满二叉树； 3.在同样深度的二叉树中，满二叉树的节点个数最多，叶子数最多； 完全二叉树： 对一棵具有 n 个节点的二叉树按层序编号，如果编号为 i 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树；完全二叉树和满二叉树是有区别的，满二叉树一定是一棵完全二叉树，但是完全二叉树不一定是满二叉树；特点： 1.叶子节点只能出现在最下层； 2.最下层的叶子一定集中在左部连续的位置； 3.倒数二层，若有叶子节点，一定都在右部连续位置； 4.如果节点度为1，则改节点只有左孩子，即不存在只有右子树的情况； 5.同样节点数的二叉树，完全二叉树的深度最小；

二叉树的性质： 1.在二叉树中第 i 层上至多有2^(i-1)个节点 2.深度为 k 的二叉树至多有2^k-1个节点 3.对任何一个二叉树 T，如果其终端节点数为 n0,度为2的节点数为 n2,则 n0=n2+1 4.具有n个节点的完全二叉树的深度为

二叉树遍历是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次；

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树；

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支书目称为路径的长度； 树的路径长度就是从树根到每一个结点的路径长度之和；

带权路径长度 WPL 最小的二叉树称为赫夫曼树；也成为最优二叉树；