algorithm_in_c's Introduction

algorithm_in_c

C语言的数据结构和算法实现 - 代码中几乎每一行都添加了注释，通过这种甚至有点啰嗦的方式，希望让人们能够容易的掌握数据结构和算法

一开始我们不太懂，所以需要了解这些数据结构和算法，

渐渐地我们可以实现这些数据结构和算法，

但是实现之后不要忘了，我们应该对我们的实现进行评估，并且对结构和算法本身有一定的认识才行

所欲数据结构和算法的出现，必然是为了解决特定的问题，如果能基于问题出发理解数据结构和算法，则会印象更加深刻

如果对数据结构和算法有热情或者其他疑问，欢迎加入QQ群: 530133597

TODO - 有太多要做的事情，这里也只是罗列出一部分

编写非递归的方案
编写单元测试
重写和封装链表，栈，堆，树等结构
更直观的GUI来展示算法
完善各个数据结构和算法的数学推导

排序

查找

二分查找

数据结构

Tree - 树

Graph Theory - 图论

加密

[AES]
[Blowfish]
[IDEA]
[RC4]

一致性算法

[Paxos]

使用方法:

进入各个目录执行make即可编译文件，之后运行文件即可

Sort - 排序

BubbleSort 冒泡排序

InsertSort - Direct Insert Sort 插入排序(直接插入排序)

ShellSort 希尔排序

BinInsertSort 二分查找插入排序

直接插入排序对于大部分有序的序列排序时速度快。
二分插入排序在直接插入的基本上改变了查找元素插入位置的方法，对于完全无序的序列来说，速度会变快，但是对于大部分有序的序列反而会更慢。
希尔排序则利用直接插入排序对于大部分有序的序列速度快的特点，先让大部分序列有序，以此来提高排序效率。

SelectSort 选择排序

QuickSort 快速排序

MergeSort 归并排序

Search - 查找

BinarySearch 二分查找

data_structure - 数据结构

SingleLinkedList 单向链表

DoubleLinkedList 双向链表

SingleCircularLinkedList 单向循环链表

DoubleCircularLinkedList 双向循环链表

StackByArr 通过数组实现的栈

StackByDoubleLinkedList 通过双向链表实现的栈

Queue 通过双向链表实现的队列

PriorityQueue 通过双向链表实现的优先级队列

PriorityQueue 通过堆实现的优先级队列

HashTable 哈希表

哈希表的主要问题在于设计好的哈希函数(可以得到均匀分布的key)和如何处理哈希冲突(hash collision)
哈希表的长度应该是质数（也称为素数）
哈希表一直在避免的就是过多的聚集
哈希表处理冲突的主要三个方式是：
1. 线性再散列，就是如果冲突则按照步长一直找（步长与哈希表长度应该是互质的），找到一个空槽（slot）为止
2. 非线性再散列，如果冲突，则重新计算出一个哈希值
  
  以上两种再散列法的特点为：
  - 再散列法都不能删除元素，否则会导致元素找不到（因为每一个元素都可能发生过冲突，而如果这个元素被删除，那么跟其发生过冲突并且再散列的元素就找不到了）
  - 当散列表负载因子（插入表中的元素个数/可用槽的总数）增大时，再散列花费的时间也会越长
  - 表的大小就是所能容纳的元素的大小
3. 拉链法（是解决哈希冲突的最常用方法），在发生冲突的槽中使用链表存放冲突元素，也就是使用链表数组来解决冲突

Tree - 树

BinarySearchTree 二叉查找树

BalancedBinaryTree 平衡二叉树 - 又称为AVL树，因其作者（Adelson-Velskii and Landis）而得名

RedBlackTree 红黑树 - 通过为节点着色并且为色彩赋予一定的规则来实现平衡

B-Tree B树 - 又称为Balanced Tree，一棵多路搜索树，用途很广，几乎是所有数据库的默认索引结构

B+ Tree B+树 - 是一种读写代价更低，查询效率更稳定（因为非终端节点都是关键字的索引，所以每个关键字的查询长度相同）的B树的变形，适应于文件系统

B* Tree B*树 - B+树的变形，是一种对于子节点利用率更加高的B+树

algorithm_in_c's People

Contributors

Stargazers

Watchers

algorithm_in_c's Issues

开源GitHub用户社区象空网邀请您的加入

你好，开发者：
独自前行的道路是漫长的，你需要更多志同道合的伙伴。你的GitHub值得关注，你的想法值得表达，你的知识更需要分享。马上加入开源GitHub用户社区——象空网，和小伙伴们一起愉快的玩耍吧。
象空网GitHub地址：https://github.com/631320085/objnull，欢迎你贡献自己的力量。

Recommend Projects