4. 队列(Queue)
定义:一种先进先出(FIFO, First In First Out)的数据结构。
特点:
插入操作在队尾,删除操作在队头。
特殊形式:双端队列(Deque),允许两端插入和删除。
应用:
广度优先搜索(BFS)。
任务调度(如打印机任务队列)。
5. 树(Tree)
定义:一种层次化的数据结构,由节点组成,每个节点有零个或多个子节点。
特点:
根节点是树的起点。
叶节点没有子节点。
常用操作:遍历(前序、中序、后序、层序)、插入、删除。
种类:
二叉树:每个节点最多有两个子节点。
二叉搜索树(BST):左子树的值小于根节点,右子树的值大于根节点。
平衡树(如AVL树、红黑树):保证树的高度尽可能小。
应用:文件系统、数据库索引、表达式解析。
6. 图(Graph)
定义:由节点(顶点)和连接节点的边组成的数据结构。
特点:
可以是有向图或无向图。
边可以带权重(加权图)。
常用表示法:邻接矩阵、邻接表。
应用:
社交网络分析。
路径优化(如最短路径算法)。
电路设计。
|