目录
一、简介
花了几天的时间从头开始使用c语言实现一些数据结构，这篇文章主要是记录顺序储存和链式存储。每一种数据结构我都实现了增、删、查、改等一些辅助的函数。为了验证程序的正确性我对这些函数都进行了测试，但是我不能保证我的测试样例足够丰富。这几天我一共实现了五种结构：动态顺序存储， 单向链表，使用数组实现静态链式储存， 单向循环链表（有头节点）和双向循环链表（无头节点)。代码在这里：
jiawen/c_datastructure – 码云 – 开源中国 (gitee.com)
我目前没有为这些代码写注释，因为程序没有那么长。
二、一些问题
1、递归free
我之前也学过数据结构并且使用了c语言实现了一些，但是前段时间在写完那个
json库
后，我觉得这些数据结构还是挺有趣的，同时我同学也跟我说找工作的时候，还是主要是看这些基础知识怎么样，所以我打算花一些时间在实现一遍这些数据结构。
在这里我最想讨论的是free时候的递归处理问题。因为我每次都要在这里写写画画来确定如何递归的调用free来释放空间。
我先把这几段代码贴在这里：
//singlecircularlist
static void list_free_(sclist src, sclist head)
{
//sclist tmp = src->next;
sclist tmp = src;
if (tmp != head) {
free(tmp->s);
sclist tmpe = tmp;
tmp = tmp->next;
free(tmpe);
tmpe = NULL;
list_free_(tmp, head);
}
//free(tmp);
return;
}
void list_free(sclist src)
{
//assert(src != NULL);
sclist tmp = src->next;
if (tmp != src) {
list_free_(tmp, src);
}
free(src);
src = NULL;
}
//single list
void list_free(sglist mylist)
{
assert(mylist != NULL);
if(mylist->next != NULL)
list_free(mylist->next);
if (mylist->s != NULL)
free(mylist->s);
free(mylist);
}
//static list that use array implement
void list_free(stlist *list, size_t pos)
{
assert(list != NULL);
size_t p = pos;
if (list[pos].next != 0) {
list_free(list, list[pos].next);
}
//PTR("the pos is %d", pos);
free((list[pos].s));
}
//doublecircularlist
void list_free(dclist src)
{
//assert(src != NULL);
dclist tmp = src;
dclist tmpe;
while (tmp != NULL) {
tmpe = tmp;
tmp = tmp->next;
free(tmpe->s);
free(tmpe);
if(tmp == src)
break;
tmpe = NULL;
}
}我选取了单链表，单向循环链表， 双向循环链表和用数组实现的链式存储结构。我想解释的是用数组实现的链式储存结构，其实这是个结构体数组， 然后结构体中有个数据用来记录下一个元素所在数据的位置，没有指针，但是这就像指针一样来记录下一个元素的位置，具体的可以看我实现的数据结构。我好想在纸上来说明这个过程，手握鼠标，敲键盘有点累了。
2、free单向循环链表：
我实现了两个函数，list_free(), list_free_(),其中list_free_()是真正的free函数，而list_free()主要free头节点。在函数list_free()中，有先判断该链表是否只有头节点，如果是，那么就不用调用list_free_()函数了，如果不是的话， 再调用list_free_(), 再这个函数中，先free掉第0个元素，再free掉第1个元素，以此类推直到碰到head节点。
3、free单向链表
对于单向链表，只需要判断它next指针是否为空来进行递归free，相对而言更简单。
4、free双向循环链表
这里没有使用递归来解决这个问题。而是使用了一个while（）循环。先free掉第0个元素，然后再free下一个元素，在这个过程中只需要判断我们要free掉的这个元素是否是第0个元素，如果是那就退出循环，free结束。
5、free使用数组实现链式存储结构
对于一个静态链表的递归free，只需要检查当前的元素所记录的下一个元素的位置是否是零来判断是否需要递归。
6、sizeof（）求字符串大小的问题
之前也遇到过这个问题，当时只是将sizeof换成strlen来解决这个问题，但是每次我都是默认使用的sizeof来得到大小，但是这对于使用指针定义的数组来说得到的是指针本身的大小，而不是字符串的大小，如果使用字符串定义的数组是可以用sizeof来得到它的大小的 。
三、总结
我真的是每次玩递归都要在纸上来画一画，看看怎么写这个函数才是正确的，希望以后能够熟练一点。也许我的代码中有我没有发现的bug，欢迎你指出（909244296@qq.com)。欢迎点赞收藏。