9个常用数据结构与算法的C语言代码实现

　　动态数组是一种可以自动调整大小的数组，具有可变长度。在C语言中，可以使用指针和内存动态分配函数（如malloc和realloc）实现动态数组。

　　以下是一个简单的动态数组实现示例代码：

　　以上代码中，动态数组通过结构体实现，其中arr指向实际存储元素的数组，size表示当前数组中的元素个数，capacity表示数组最多可以容纳的元素个数。init函数用于初始化动态数组，append函数用于在数组末尾添加元素，如果数组容量不足，则动态扩展数组容量。print函数用于打印数组中的元素。在程序结束前，需要释放动态分配的内存。

　　链表是一种常见的数据结构，它由一组节点组成，每个节点包含一个值和一个指向下一个节点的指针。在C语言中，可以通过定义结构体来实现链表。

　　以下是一个简单的链表实现示例代码：

　　以上代码中，链表通过定义结构体来实现，其中data表示节点存储的值，next表示指向下一个节点的指针。insert函数用于在链表头部插入节点，print函数用于打印链表中的元素。在程序结束前，需要释放动态分配的内存

　　栈是一种后进先出（LIFO）的数据结构，它可以通过数组或链表实现。在C语言中，可以使用数组实现栈。

　　以下是一个简单的栈实现示例代码：

　　以上代码中，栈通过结构体实现，其中arr表示存储栈元素的数组，top表示栈顶元素的下标。init函数用于初始化栈，push函数用于将元素入栈，如果栈已满则报错，pop函数用于将栈顶元素出栈，如果栈为空则报错，peek函数用于查看栈顶元素，但不将其出栈。在程序结束前，不需要显式释放内存。

　　队列是一种先进先出（FIFO）的数据结构，它也可以通过数组或链表实现。在C语言中，可以使用数组实现队列。

　　以下是一个简单的队列实现示例代码：

　　以上代码中，队列通过结构体实现，其中arr表示存储队列元素的数组，front和rear分别表示队列头和队列尾元素的下标。init函数用于初始化队列，enqueue函数用于将元素入队，如果队列已满则报错，dequeue函数用于将队头元素出队，如果队列为空则报错，peek函数用于查看队头元素，但不将其出队。在程序结束前，不需要显式释放内存。

　　二叉树是一种树形结构，其中每个节点最多有两个子节点，分别为左子节点和右子节点。在C语言中，可以使用结构体和指针实现二叉树。

　　以下是一个简单的二叉树实现示例代码：

　　以上代码中，二叉树通过结构体实现，其中value表示节点的值，left和right分别表示左子节点和右子节点。create_node函数用于创建新节点，并返回指向该节点的指针。inorder_traversal函数用于中序遍历二叉树，即先遍历左子树，再遍历根节点，最后遍历右子树。在程序结束前，需要显式释放二叉树中所有节点的内存。

　　快速排序是一种常用的排序算法，其基本思想是通过选定一个基准元素，将待排序序列划分为两个子序列，其中一个子序列的所有元素均小于等于基准元素，另一个子序列的所有元素均大于等于基准元素，然后对两个子序列分别进行递归排序，最终将整个序列排序。

　　以下是一个简单的快速排序实现示例代码：

　　以上代码中，快速排序通过递归实现，其中partition函数用于选取基准元素，并将序列划分为两个子序列。具体地，选择最右边的元素为基准元素，使用i和j两个指针扫描整个序列，若arr[j]小于基准元素，则将其与arr[i+1]交换，并将i加1，最终将基准元素交换到i+1处。quick_sort函数用于递归排序子序列，直到整个序列有序。在程序结束前，不需要显式释放内存。

　　广度优先搜索是一种图遍历算法，其基本思想是从图中某个顶点开始，依次访问其所有邻居节点，然后再访问邻居节点的所有邻居节点，直到图中所有节点都被访问为止。在C语言中，可以使用队列实现广度优先搜索。

　　以下是一个简单的广度优先搜索实现示例代码：

　　以上是一个使用邻接表实现的BFS示例代码，其中使用了一个队列结构体，用于存储需要进行扩展的节点。首先将起始节点加入队列中，并标记为已访问过，然后不断从队列中取出一个节点，将其相连的未访问过的邻居节点加入队列，直到队列为空为止。这样遍历的过程就是一个层层扩展的过程，因此BFS也被称为“宽度优先搜索”。

　　上面的代码实现了一个简单的BFS算法，它可以接受从标准输入读入的图的描述，以及起始节点，然后打印出从起始节点开始的BFS遍历结果。其中，节点使用0~n-1的整数表示，图的描述使用每行两个整数u和v表示一条无向边。

　　二叉查找树是一种基于二分查找的数据结构，它具有以下性质：

　　左子树上所有节点的值均小于它的根节点的值右子树上所有节点的值均大于它的根节点的值左右子树都是二叉查找树

　　以下是一个简单的二叉查找树实现示例代码：

　　以上代码中，二叉查找树使用递归实现。insert函数用于向二叉查找树中插入一个节点，若当前节点为空，则将新节点插入；否则，根据当前节点的值和待插入节点的值大小关系，递归调用insert函数。inorder_traversal函数用于中序遍历二叉查找树，即先遍历左子树，然后访问根节点，最后遍历右子树。在程序结束前，需要显式释放内存。

　　哈希表是一种基于哈希函数实现的数据结构，它具有快速查找和插入的特点。在C语言中，可以使用数组和链表来实现哈希表。

　　以下是一个简单的哈希表实现示例代码：

　　以上代码中，哈希表使用链表解决哈希冲突，每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值，insert函数用于向哈希表中插入一个键值对，若当前位置为空，则直接插入；否则，将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值，若存在则返回其值，否则返回-1。

　　

　　这些常用的C语言数据结构、算法和功能代码示例，涵盖了常见的数据结构和算法，能够满足许多实际应用的需求。需要注意的是，在实际使用时，需要根据具体情况进行优化和改进，以适应不同的应用场景。

　　举报/反馈