数据结构-基础

1、概念：

        程序 == 数据结构 + 算法

2、程序的好坏

        可读性，稳定性，扩展性，时间复杂度，空间复杂度。

3、数据结构

        是指存储、组织数据的方式，以便高效地进行访问和修改。通过选择适当的数据结构，

        能够优化计算机程序的时间和空间效率。

4、分类

        逻辑结构

                线性结构（表），非线性结构（树，图）

        存储结构

                顺序存储，链式存储，索引存储，散列存储

5、数据结构：

        顺序表

        链表

        顺序栈

        链式栈

        队列

        树

        哈希表等

6、顺序表

        1、定义类型

                

 7、工程代码目录结构

        1、main.c :主函数程序代码

        2、fun.c ：功能程序代码

        3、fun.h ： 工程程序代码头文件

8、gdb调试工具

        l        查看代码

        b  行号/函数名         设置断点

        r        运行代码

        n         单步执行

        s        进入函数内部调试

        p   变量名        查看变量内容

        q         退出调试

9、链表

        链表（Linked List）是一种常见的数据结构，用于存储一系列数据元素。与数组不同，链表

        中的元素不是在连续的内存位置上存储，而是通过指针将每个元素链接到下一个元素

        

        链表的基本结构

                链表由一系列节点（Node）组成，每个节点包含两个部分：

                数据部分：存储实际的数据。

                指针部分：存储指向下一个节点的地址（在单链表中），或在双向链表中指向前一个

                和下一个节点的地址。

        

        单向链表（Singly Linked List）：

                 每个节点只包含一个指向下一个节点的指针。只有一个方向可以遍历链表。

        

        链表的优缺点

                优点：

                        动态大小：链表的大小是动态的，不像数组需要预先确定大小。

                        高效插入和删除：在链表中插入或删除元素时，无需移动其他元素，尤其是当

                        在链表的头部或尾部插入时，操作非常高效（O(1)时间复杂度）。

                缺点：

                        访问效率较低：访问链表中的某个元素需要从头节点开始逐一遍历，时间复

                        杂、 度为O(n)，相比之下，数组的访问是O(1)。

                        额外的内存消耗：每个节点需要额外存储指针，相比数组，需要更多的内存。

10、栈和队列

        1、栈与队列与表的区别

                栈和队列是一种特殊的表状结构

                栈和队列只允许在固定位置取出或者插入数据

                栈：先进后出

                队：先进先出

 11、树

        树是一种非线性的数据结构，由若干个节点组成，每个节点有一个父节点和若干个子

        节点。树的特点是没有环，并且节点之间存在父子关系。树的最顶层节点叫做根节点，

        而没有子节点的节点叫做叶子节点。

        树的基本特性：

                根节点：树的最顶层节点，没有父节点。

                父子关系：每个节点可以有多个子节点，但只能有一个父节点。

                层次结构：树的节点按层级排列，从根节点开始，根节点为第0层，它的子节点为

                第1层，以此类推。

                节点：树中的每个元素都称为节点。

                边：连接父节点与子节点之间的线叫做边。

                树的形式可以有很多种，例如：多叉树、二叉树、平衡树等。

12. 二叉树 (Binary Tree)

        二叉树是树的一种特殊形式，在二叉树中，每个节点最多有两个子节点，分别称为

        左子节点和右子节点。二叉树是一种非常重要的树形结构，广泛应用于搜索算法

        （如二叉搜索树）、表达式树等。

        二叉树的特点：

                每个节点最多有两个子节点（左子节点和右子节点）。

                具有递归的性质，左右子树也可以是二叉树。

        二叉树的类：

                满二叉树 (Full Binary Tree)：

                        每个节点要么没有子节点，要么有两个子节点。
                完全二叉树 (Complete Binary Tree)：

                        除了最底层外，其他层的节点都填满，且最底层的节点从左到右填充。
                平衡二叉树 (Balanced Binary Tree)：

                        每个节点的左右子树高度差不超过1。
                二叉搜索树 (Binary Search Tree, BST)：

                        左子树的值都小于根节点，右子树的值都大于根节点。

        

        二叉树的遍历方式：

                前序遍历 (Pre-order Traversal)：
                        根节点 -> 左子树 -> 右子树
                        访问顺序：根、左、右
                中序遍历 (In-order Traversal)：
                        左子树 -> 根节点 -> 右子树
                        访问顺序：左、根、右
                后序遍历 (Post-order Traversal)：
                        左子树 -> 右子树 -> 根节点
                        访问顺序：左、右、根
                层次遍历 (Level-order Traversal)：
                        按层次逐行访问，从根节点开始，逐层向下。

13、深度优先遍历 (DFS)

        深度优先遍历（DFS）是沿着图或树的深度探索每一条路径，直到走到最深处为止，

        然后回溯到上一层，继续探索其他路径。DFS 可以通过递归或使用栈来实现。

        DFS 思想：

                从起始节点开始，沿着一条路径一直深入，直到无法继续为止。

                一旦遇到无法继续的节点（叶节点或已访问的节点），就回溯到上一个节点，继续

                探索未被访问的邻接节点。

                在树结构中，DFS 是沿着树的深度逐层展开的。

        DFS 实现：

                选择一个节点作为起始节点。

                访问当前节点并标记为已访问。

                遍历当前节点的所有邻接节点，如果邻接节点未被访问，则递归调用 DFS 进行深度

                遍历。

                如果当前节点的所有邻接节点都已访问过，回溯到上一个节点。

 14、广度优先遍历 (BFS)

        广度优先遍历（BFS）是按层次逐层遍历图或树，从起始节点开始，首先访问所有邻接

        的节点，然后再访问邻接节点的邻接节点，直到遍历完整个图或树。

        BFS 思想：

                BFS 按层次进行遍历，先访问当前节点的所有邻接节点，再逐层访问。

                BFS 使用队列来实现，先进先出（FIFO）的特性保证了按层次遍历。

        BFS 实现：

                选择一个节点作为起始节点。

                将起始节点加入队列，并标记为已访问。

                从队列中取出一个节点，访问它并将其所有未访问的邻接节点加入队列。

                重复步骤 3，直到队列为空。

15、哈希曼表

        哈希曼表（Hash Map）是一种基于哈希（散列）技术的数据结构，用于实现高效的元

        素查找、插入和删除操作。它通过将键（key）映射到值（value）来存储数据，通常具

        有非常高的查找效率，平均时间复杂度为 O(1)，因此在许多应用中被广泛使用。

        哈希表的基本原理：

                哈希表通过 哈希函数 将键（key）映射到一个数组的位置（即索引）。该位置存储

                与该键相关的值（value）。哈希函数的目的是尽量将不同的键映射到数组中不同

                的位置，减少冲突的发生。

        哈希表的结构：

                数组：哈希表通常由一个数组构成，数组的每个元素用于存储一对键值对

                （key-value）。

                哈希函数：通过哈希函数将键（key）映射到数组的索引位置。

                冲突解决：由于不同的键可能会被映射到相同的索引（即哈希冲突），因此需要一

                种方法来解决冲突。

        哈希表的常见操作：

                插入 (Insert)：将一个键值对插入哈希表中。使用哈希函数计算键的索引，并将值

                存储在该索引位置。

        查找 (Search)：根据给定的键，使用哈希函数计算索引，查找对应的值。

        删除 (Delete)：删除给定键的键值对，移除该位置的元素。

        哈希冲突的解决方法：

        

                链地址法（Separate Chaining）：每个数组元素不仅存储一个值，而是存储一个链表

                或其他数据结构的引用。在发生冲突时，将相同索引的键值对存放到链表中。

                优点：处理冲突时非常灵活，不会浪费空间。
                缺点：如果哈希表的负载因子过大（链表过长），查找性能会下降。