做网站体会心得,wordpress一键关注,制作简单的网站,wordpress侧边浮窗1. 数组 (Array)
定义
数组是一种线性数据结构#xff0c;用于存储固定大小的相同类型元素集合。每个元素都有一个索引#xff0c;用于快速访问。
特点
优点#xff1a;访问速度快#xff0c;通过索引直接访问O(1)时间复杂度。缺点#xff1a;大小固定#xff0c;插入…1. 数组 (Array)
定义
数组是一种线性数据结构用于存储固定大小的相同类型元素集合。每个元素都有一个索引用于快速访问。
特点
优点访问速度快通过索引直接访问O(1)时间复杂度。缺点大小固定插入和删除元素效率低需移动后续元素。插入元素的时间复杂度为O(n)删除元素的时间复杂度同样为O(n)。
应用场景
适合于元素数量固定且频繁查询的场景如排序数组、查找表等。多维数组常用于表示矩阵、图像、游戏地图等需要多个维度来描述的数据结构。
2. 链表 (Linked List)
定义
链表是一种由节点组成的数据结构每个节点包含存储数据的部分以及指向下一个节点的指针。通过节点之间的指针连接形成了链表的结构。链表可以分为单链表、双向链表和循环链表等不同类型它们各自具有特定的特点和应用场景。
数据元素节点存储的实际数据。数据可以是任意类型例如整数、字符、字符串、对象等。指针或引用指向下一个节点的指针。它存储了下一个节点在内存中的地址通过这个指针可以找到链表的下一个节点。 类型
单向链表
单链表是最简单的链表类型每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的尾节点指针为空表示链表的结束。单链表的插入、删除操作相对简单高效但随机访问的效率较低。 单向链表的特点
非连续存储单链表中的节点在内存中可以是任意位置不要求连续存储。每个节点通过指针指向下一个节点从而将它们连在一起。动态性相较于数组单链表的长度可以动态地增减不需要预先分配内存空间。这使得单链表在需要频繁插入和删除节点的场景中更加灵活。搜索效率相对较低由于单链表的节点只能通过指针一个一个地遍历因此搜索某个特定的节点需要遍历整个链表时间复杂度为O(n)其中n是链表的长度。相比之下数组可以使用索引直接访问元素搜索效率更高。内存空间的额外开销单链表中的每个节点除了存储数据外还需要存储下一个节点的指针这导致了额外的内存开销。插入和删除效率较高相对于数组单链表在插入和删除节点时效率较高。插入一个节点只需要改变相邻节点的指针而删除一个节点只需要改变前一个节点的指针指向下一个节点不需要移动其他元素。灵活性单链表可以方便地进行节点的插入和删除操作可以根据实际需要进行自由调整。
双向链表
每个节点包含数据、指向前一个节点和指向下一个节点的指针。
双向链表的特点
支持双向遍历相对于单向链表双向链表支持双向遍历可以从前往后、从后往前遍历链表。插入、删除节点效率更高相较于单向链表双向链表在插入和删除某个节点时只需要改变相邻两个节点的指向效率更高尤其是在删除链表中某个元素时更加便捷。需要更多的内存空间相比单向链表双向链表需要更多的内存空间来存储额外的指针增加了额外的空间开销。内存存储不连续相对于数组链表中节点的内存存储位置不连续需要使用指针进行串联这可以更加灵活地进行插入、删除和移动节点的操作。操作复杂度较高插入、删除、移动等操作需要修改前后节点的指针信息操作比较繁琐。
循环链表
链表的最后一个节点指向链表的第一个节点形成闭环。
循环链表特点
首位相连循环链表的最后一个节点指向链表的第一个节点使得链表成为一个环形结构。这样链表的结束节点与开始节点相连可以实现无限循环更加灵活和方便。操作始终成立由于循环链表始终是一个环形的结构因此操作例如插入、删除、查找等始终处于链表中这也保证了操作始终能够完成。遍历循环与单向链表相比在遍历时需要注意指针不要陷入死循环。否则会导致遍历永远无法结束。内存空间的额外开销与单向链表相比循环链表需要多一个指向头部节点的指针增加了额外的空间开销。插入和删除效率较高相对于数组循环链表在插入和删除节点时效率比较高。插入一个节点时只需要修改相邻节点的指针即可而删除一个节点时只需要改变前一个节点的指针指向下一个节点即可。
优缺点
优点动态分配内存插入和删除操作快O(1)只需改变指针。缺点访问速度慢需从头节点遍历最坏情况下O(n)。
应用场景
适用于频繁插入和删除操作的场景如实现堆栈、队列等。
3. 栈 (Stack)
定义
栈是一种特殊的线性结构遵循后进先出LIFO, Last In First Out原则。只允许在一端栈顶进行插入和删除操作。 操作
压栈Push在栈顶添加元素。弹栈Pop移除栈顶元素。栈的插入和删除操作只能在栈顶进行因此栈是一个只能从一端访问的数据结构。
应用场景
回溯算法、函数调用栈、括号匹配等。
4. 队列 (Queue)
定义
队列是一种线性结构遵循先进先出FIFO, First In First Out原则。一端添加元素队尾另一端移除元素队头。
操作
入队Enqueue在队尾添加元素。出队Dequeue从队头移除元素。
应用场景
任务调度、缓冲区管理等。
栈和队列的对比
结构栈和队列都是线性结构但栈只有一个入口栈顶和一个出口栈顶而队列有一个入口队尾和一个出口队头。 插入和删除操作栈的插入和删除操作只能在栈顶进行而队列的插入操作在队尾进行删除操作在队头进行。 访问顺序栈按照后进先出的顺序访问元素而队列按照先进先出的顺序访问元素。 应用场景栈常用于函数调用、表达式求值、回溯算法等场景而队列常用于任务调度、消息传递、缓冲区管理等场景。
5. 哈希表 (Hash Table)
定义
哈希表是一种通过哈希函数将键Key直接映射到值Value的数据结构提供了快速的查找、插入和删除操作。
哈希表的实现就是映射函数构造哈希表的映射函数构造方法也有很多常见的有直接定址法、 除留余数法、 乘余取整法、 数字分析法、 平方取中法、 折叠法、 随机数法等。
特点
优点平均时间复杂度为O(1)。缺点可能遇到哈希冲突需要解决冲突策略如开放寻址法、链地址法。
应用场景
字典、缓存、数据库索引等。
6. 树 (Tree)
定义
树是一种分层的非线性数据结构由节点Node和边Edge组成每个节点有零个或多个子节点且只有一个根节点。
树是由一个或多个节点或称为顶点的有限集合构成。在任何非空树中存在唯一一个称为根Root的节点没有父节点。除根节点外的每个节点都有一个父节点。每个节点可以有零个或多个子节点子树。树中的节点形成一种层次关系没有环路即节点之间不存在重复路径。子树之间相互独立即任意两个子树的节点集合不会相交。
基本术语
节点Node树中的基本单位存储数据元素。边Edge连接树中节点的链接表示父子关系。根节点Root Node没有父节点的节点。叶节点Leaf Node没有子节点的节点。子节点Child Node某个节点的直接下一级节点。父节点Parent Node直接位于某节点之上的节点。兄弟节点Sibling Node具有相同父节点的节点。度Degree节点的子节点数目。层次Level从根开始到某个节点的距离根节点处于第0层。高度Height树中节点的最大层次数。
操作
创建树初始化一个空树或构造指定结构的树。插入节点在树的指定位置添加新节点。删除节点移除树中的某个节点并保持树的特性。查找节点在树中搜索特定值的节点。遍历树按照某种顺序访问树中的所有节点常见的遍历方法有前序遍历、中序遍历、后序遍历和层序遍历。
特殊类型的树
二叉树每个节点最多有两个子节点的树。二叉搜索树BST二叉树的一种左子树所有节点的值小于其父节点右子树所有节点的值大于其父节点。平衡二叉树如AVL树、红黑树自平衡的二叉搜索树确保树的高度大致保持对数级别。B树、B树适用于文件系统和数据库索引的自平衡树。堆一种完全二叉树常用于优先队列实现。
应用场景
文件系统、数据库索引、表达式解析等。 7. 图 (Graph)
定义
图是由顶点Vertex和边Edge组成的非线性数据结构边可以连接任意两个顶点形成更复杂的关系网络。
类型
有向图 / 无向图加权图 / 非加权图
应用场景
社交网络、地图导航、网络路由等。
