数据结构

数据结构有哪些基本类型？

• 数组：数组是一种线性结构，它由一组具有相同类型的元素组成，这些元素按照一定的顺序排列并占据连续的存储空间，可以通过下标快速访问数组中的任意元素。
• 链表：链表也是一种线性结构，它由一系列结点组成，每个结点包含数据域和指向下一个结点的指针，结点之间通过指针相连，可以实现动态的插入、删除等操作。
• 栈：栈是一种特殊的线性结构，它具有“后进先出”的特点，即最后入栈的元素最先出栈。栈可以用数组或链表实现。
• 队列：队列也是一种特殊的线性结构，它具有“先进先出”的特点，即最先入队的元素最先出队。队列可以用数组或链表实现。
• 树：树是一种非线性结构，它由若干个结点组成，每个结点可以有若干个子结点，结点之间通过边相连。树可以用链表或数组实现。
• 图：图也是一种非线性结构，它由若干个结点和若干个边组成，结点之间通过边相连。图可以用邻接矩阵或邻接表等方式实现。
• 哈希表：哈希表是一种根据关键字直接访问内存存储位置的数据结构，它通过哈希函数将关键字映射到一个内存地址，并在该地址中存储对应的数据。哈希表可以用数组实现。

数据结构的分类有哪些？

线性结构

数据元素之间存在一对一的线性关系，包括数组、链表、栈、队列等。

树形结构

数据元素之间存在一对多的层次关系，包括二叉树、B树、堆等。

图形结构

数据元素之间存在多对多的关系，包括邻接矩阵、邻接表等。

散列结构

数据元素之间无明显的关系，通过哈希函数将元素映射到对应的存储位置上，包括哈希表等。

其他结构

如字符串、集合、堆栈等。

数据结构的存储方式有哪些？

数据结构的存储方式可以分为以下几种：

顺序存储

将数据元素存储在一段连续的存储区域内，通过元素的下标来访问数据元素，适用于随机访问操作频繁的情况，如数组。

链式存储

将数据元素存储在不连续的存储区域内，通过指针来连接各个元素，适用于插入和删除操作频繁的情况，如链表。

索引存储

在数据元素和存储位置之间建立一张索引表，通过索引表中的索引来访问数据元素，适用于数据元素较大，但存储位置较少的情况，如B树。

散列存储

通过散列函数将数据元素映射到对应的存储位置，适用于数据元素的访问和插入操作频繁的情况，如哈希表。

块式存储

将数据元素分为若干块，每块内部采用顺序存储，块与块之间采用链式存储，适用于数据元素较多，但单个块的存储空间有限的情况，如外部排序算法。

数据结构的遍历方式有哪些？

线性结构遍历

线性结构遍历一般是顺序遍历，从头到尾依次访问每个元素，如数组和链表。

树形结构遍历

树形结构遍历包括深度优先遍历和广度优先遍历。深度优先遍历有前序遍历、中序遍历和后序遍历三种方式，分别是先访问根节点、先访问左子树和先访问右子树。广度优先遍历是按层遍历，先访问根节点，然后依次访问每一层的节点。

图形结构遍历

图形结构遍历有深度优先遍历和广度优先遍历两种方式。深度优先遍历通常采用递归或栈来实现，广度优先遍历则需要使用队列来实现。

数据结构的排序方式有哪些？

冒泡排序

比较相邻元素的大小，将较大的元素交换到右侧，重复该过程直到排序完成。时间复杂度为O(n^2)。

选择排序

每次选择未排序部分中最小的元素，与未排序部分的第一个元素交换位置，重复该过程直到排序完成。时间复杂度为O(n^2)。

插入排序

将未排序元素插入到已排序元素中的正确位置，重复该过程直到排序完成。时间复杂度为O(n^2)。

快速排序

选取一个基准元素，将数组分为左右两部分，左边部分的元素均小于基准元素，右边部分的元素均大于基准元素，重复该过程直到排序完成。时间复杂度为O(nlogn)。

归并排序

将数组分为若干个子数组，分别对子数组进行排序，然后将排好序的子数组合并成一个有序的数组。时间复杂度为O(nlogn)。

堆排序

将数组构建成最大堆或最小堆，然后将堆顶元素与堆底元素交换位置，重复该过程直到排序完成。时间复杂度为O(nlogn)。

数据结构的红黑树和B树有什么区别？

数据结构

红黑树是一种二叉搜索树，每个节点要么是红色，要么是黑色；B树是一种多路平衡查找树，每个节点有多个子节点。

存储方式

红黑树一般采用链式存储方式，每个节点包含指向左右子树的指针和颜色标记；B树采用索引存储方式，每个节点包含指向子节点的指针和关键字。

插入和删除操作

红黑树的插入和删除操作相对简单，只需要进行颜色调整和旋转操作即可；B树的插入和删除操作较复杂，需要进行节点的分裂和合并操作。

查找效率

红黑树的查找效率较高，平均时间复杂度为O(log n)；B树的查找效率也很高，平均时间复杂度为O(logd n)，其中d为B树的阶数。

应用场景

红黑树适用于内存中的数据结构，常用于STL中的map和set等容器；B树适用于外存储数据结构，常用于数据库索引和文件系统等场景。

数据结构的AVL树和伸展树有什么区别？

平衡方式

AVL树通过旋转操作来保持平衡，每个节点的左右子树高度差不超过1；伸展树通过伸展操作来保持平衡，每次查找后将被查找节点伸展到根节点位置。

平衡因子

AVL树的平衡因子为左子树高度减去右子树高度的绝对值，只有平衡因子为-1、0、1的节点才是平衡的；伸展树没有平衡因子的概念，通过伸展操作来保持树的平衡。

调整方式

AVL树需要进行旋转操作来保持平衡，旋转操作会改变树的结构；伸展树通过伸展操作来保持平衡，伸展操作不会改变树的结构，只是改变节点的位置。

查找效率

AVL树的查找效率较高，平均时间复杂度为O(log n)；伸展树的查找效率也较高，但由于伸展操作的存在，最坏时间复杂度可能会退化到O(n)。

应用场景

AVL树适用于内存中的数据结构，常用于数据库索引、编译器和图形学等场景；伸展树适用于内存中的数据结构，常用于动态查找和缓存等场景。