一些数据结构的实现方法

这绝对是一篇很水很水的文章,用来巩固自己对C指针的学习而已.

学了辣么久的C语言.写了辣么多的数据结构.你是否还在用数组模拟你的链表、二叉树、字典树&&平衡树?
今天无聊的我就来秀(shui)一(yi)秀(shui)我从大神那里学到的高逼格的实现方法把(对C语言指针有一定要求).

首先,定义数据结构的节点:

链表是这样的:

1
2
3
4
struct linkNode  {
    typename data;
    struct linkNode *next;
}; //别忘了这里需要分号哦,详见C语言的结构体定义.

喔这是最基本的实现.等下还可以有改进.

然后是二叉树(平衡树适用)的:

1
2
3
4
struct treeNode {
    typename data;
    struct treeNode *left, *right;
};

字典树:

1
2
3
4
5
struct tireNode {
    typename data;
    struct tireNode *child[26];
    //好吧,这里极端点就改成255吧,也用不了多少空间.
};

其实都是一样的规则,只是每个节点连出去的指针的数量在变化..好水！

然后,新建节点的规则:

首先定义全局变量(主要是为了申请空间,这是静态申请空间的方法,当然也可以申请动态内存):

1
2
3
struct linkNode head[MAX_LEN], *pbuf = head;
struct treeNode root[MAX_LEN], *pbuf = root;
struct tireNode root[MAX_LEN], *pbuf = root;

这里我就不考虑变量冲突的问题了,一般很少两种数据结构一起用的.

再然后,对节点的各种操作:

链表的插入节点操作:

1
2
3
4
5
void linkIns(typename x){
    ++pbuf->data = x;
    Pbuf->next = head;
    head->next = pbuf;
} //这里直接把节点插入到了链表头（你也可以自己改成插入到链表尾部）

(我们默认定义链表头不存放数据,不然会有bug).

下面是二叉树的操作:（二叉树的版本太多了,所以这里给出的最水最水的创建节点吧,至于节点放哪里自己看情况而定把）

1
2
3
4
5
6
struct treeNode* treeNodeNew(typename x)
{
    ++pbuf->data = x;
    pbuf->left = pbuf->right = NULL;
    return pbuf;
} //对你没看错就是这么简单.

下面是字典树的操作（字典树是以插入一个字符串为操作的）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void tireIns(char *s){
    struct  tireNode *p = root;
    while(*s!='\0') {
        char ch = *s++ - 'a';
    //如果处理的字符串是大写的a换成A即可
        //如果大小写混合或者有特殊字符.可以用别的方法
            //例如把child开成256的数组
        if(p->child[ch] == NULL) 
            p->child[ch] = ++pbuf;
        p = p->child[ch];
    }
    p->data ++; 
    //这里的操作自定义啦啦啦 ,这里举的栗子素统计字符串数量的啦啦啦
}

当然数据结构肯定不止这些操作惹~其他的自己发挥把..
毕竟每一次使用都会有不同的情况.

最后,查漏补缺

然后来看看这种静态的写法有什么缺点..（缺点还是很明显的 +_+#）
那就素！！删除节点的时候不释放内存空间！（因为是静态申请的嘛！）
所以！！我就就需要在删除节点的时候（如果算法不需要删除就不需要这个啦）新建一个节点回收的指针数组！(！！注意是指针数组不是数组指针)
我称这个叫 垃圾回收机制！

1
2
struct linkNode *recycleBin[MAX_LEN], **rpbuf=recyckeBin; 
void delete(struct linkNode * p) { ++rpbuf=p; }

只需要在删除节点之前使用这个函数！就代表这个节点被删除了！
另外两种就不写惹~一样的道理嘛！链表的理解了别的也就差不多了不是, 换汤不换药！
当然,回收垃圾肯定是要有用的..不然回收它干嘛..所以我把link函数写成了这样:

1
2
3
4
5
6
7
8
9
10
void linkIns(typename x){
    struct linkNode * pNew;
    if(rpbuf != recycleBin) pNew = rpbuf;  
    //判断垃圾箱是否为空,不空从垃圾箱拿节点
    else pNew = pbuf;                   
    //如果空就从pbuf开新节点
    ++pNew->data = x;
    pNew->next = head->next;
    head->next = pNew;
}

二叉字典树树的就不水了…基本一样..
最后附上一个水水的栈！！

1
2
3
4
5
typename stk[MAX_LEN],  *top = stk; 
    //我在想用bottom素不素逼格更高一点@_@
void push(typename x) { *++top = x; } //没错就素这么水！！
typename *pop() { return top == stk ?  NULL :  top--} 
    //没错一如既往的水！！

话说栈就没必要写垃圾回收机制惹不是嘛~╰(￣▽￣)╮
然后再来水一水 动态节点的写法…
主要用到一个函数malloc();函数原型详见C语言头文件 stdlib.h
嗯 使用这个函数之前请先#include <stdlib.h>
然后..嗯 新建节点要申请内存..例如:

1
2
3
4
5
6
struct linkNode * linkNodeNew(typename x){
    struct linkNode *plink = 
        (struct linkNode *)malloc(sizeof(struct linkNode));
    plink->data = x;
    return plink;
}

然后连接函数这样写:

1
2
3
4
void link(struct linkNode *cur){
    cur->next = head->  next;
    head->next = cur;
}  //当然还可以把两个函数合起来...

其他的就不写了 换汤不换药的东西..
然后是删除节点..这个就不需要垃圾回收了
一个free函数直接还给操作系统..

1
2
void delete(struct linkNode * p) { free(p); } 
//真的好水...