如何实现一个优美的链表

     面向对象的语言更接近人的思维方式，而且在很大程度上降低了代码的复杂性，同时提高了代码的可读性和可维护性，传统的 C 代码同样可以设计出比较易读，易维护，复杂度较低的优美代码，本文将通过一个实际的例子来说明这一点。

基础知识

结构体

除了提供基本数据类型外，·C 语言还提供给用户自己定制数据类型的能力，那就是结构体，在 C 语言中，你可以用结构体来表示任何实体。结构体正是面向对象语言中的类的概念的雏形，比如：

1. typedef struct
   
2. {
   
3.     float x;
   
4.     float y;
   
5. }Point;
   

复制代码

    定义了一个平面坐标系中的一个点，点中有两个域，x 坐标和 y 坐标。

结构体中的域称为结构体的成员。结构体中的数据类型可以是简单数据类型，也可以是其他的结构体，甚至结构体本身还可以嵌套，比如，一个标准的链表结构可以进行如下定义：

1. typedef struct node
   
2. {
   
3.     void *data;// 数据指针
   
4.     int dataLength;// 数据长度
   
5.     struct node *next;// 指向下一个节点
   
6. }Node;
   

复制代码

可以看到，结构体 node 中的 next 指针的类型又是 node 类型。

函数指针

    指针是 C 语言的灵魂，是 C 比其他语言更灵活，更强大的地方。所以学习 C 语言必须很好的掌握指针。函数指针，即指向函数在内存映射中的首地址的指针，通过函数指针，可以将函数作为参数传递给另一个函数，并在适当的时候调用，从而实现异步通信等功能。

比如， UNIX/Linux 系统中的信号注册函数，其原型如下：

1. void (*signal(int signo,void (*func)(int)))(int)

复制代码

   

    使用的时候，需要自己在外部定义一个信号处理函数 (signal handler), 然后使用 signal(sigNo, handler) 将处理程序注册在进程上，当信号发生时，进程就可以回调信号处理函数。

将函数指针作为结构体的成员

   

    正如前面提到的，结构体的成员可以是简单的数据结构，也可以是其他的结构体，当然，也可以是指针。当将函数指针作为结构体的成员，并且这些函数只用来操作本结构体中的数据时，就可以形成一个独立的实体，这个实体中既有数据，也有对数据的操作，这样自然就可以引出类(class)的概念。

面向对象语言的特性

   一般而言，继承，封装和多态被认为是面向对象语言所必须支持的三种特征，也正是通过这三种特征才可以体现出面向对象在哪些方面优于面向过程。由于语言开发商的宣传或其他的各种原因，使的表面上面向对象的思想要通过语言为载体而得以实现，然而实际上，面向对象是一种软件设计思想，完全是可以与具体实现无关的。

虽然如此，但是不可否认，这些所谓的纯面向对象的语言，在其代码的可读性以及与人的自然思维的匹配方面，比面向过程的语言要好的多。

语言层次的面向对象

     我们一般要描述一个对象，一般需要描述这个对象的一些属性，比如盒子(box) 是一个实体，它有 6 个面，有颜色，重量，是否为空等属性，并且可以放东西进去，可以取东西出来。在面向对象的语言中，通常将这样的对象抽象成一个类 (class):

1. class Box{
   
2.     clolr color;
   
3.     int weight;
   
4.     boolean empty;
   
5. 
   
6.     put(something);
   
7.     something get();
   
8. }
   

复制代码

   对盒子进行操作时，可以做一下动作：

1. Box.put(cake);
   
2. Box.get();// 取到某个东西，从盒子中。
   

复制代码

   

    而面向过程的语言中，通常是将实体传递给一个贯穿全局的函数来进行的，同样以 Box 为例，对 Box 进行操作时，往往是这样：

1. Put(Box, cake);// 将一个蛋糕放到盒子中
   
2. Get(Box);// 从盒子中取出某个东西来
   

复制代码

C 语言的面向对象

     如前所说，面向对象是一种软件设计的思想，是语言无关的。在此我将举一个链表(list)的例子来说明，如何在 C 语言中的设计出有面向对象风格的代码。

定义接口

接口是面向对象语言中的一个比较重要的概念，接口只对外部承诺实现该接口的实体可以完成什么样的功能，但是不暴露实现的方式。这样的好处是，实现者可以在不接触接口使用者的代码的情况下，对实现进行调整。

我们来看看链表的接口定义：

1. 链表的接口定义

1. #ifndef _ILIST_H
   
2. #define          _ILIST_H
   
3. 
   
4. // 定义链表中的节点结构
   
5. typedef struct node{
   
6.     void *data;
   
7.     struct node *next;
   
8. }Node;
   
9. 
   
10. // 定义链表结构
    
11. typedef struct list{
    
12.     struct list *_this;
    
13.     Node *head;
    
14.     int size;
    
15.     void (*insert)(void *node);// 函数指针
    
16.     void (*drop)(void *node);
    
17.     void (*clear)();
    
18.     int (*getSize)();
    
19.     void* (*get)(int index);
    
20.     void (*print)();
    
21. }List;
    
22. 
    
23. void insert(void *node);
    
24. void drop(void *node);
    
25. void clear();
    
26. int getSize();
    
27. void* get(int index);
    
28. void print();
    
29. 
    
30. #endif          /* _ILIST_H */
    

复制代码

     IList 接口中，可以清晰的看到，对于一个 list 实体 ( 也就是对象 ) 来说，可以在其上进行 insert, drop, clear, getSize, get(index) 以及 print 等操作。

接口的实现

2. 构造方法

1. Node *node = NULL;
   
2. List *list = NULL;
   
3. 
   
4. void insert(void *node);
   
5. void drop(void *node);
   
6. void clear();
   
7. int getSize();
   
8. void print();
   
9. void* get(int index);
   
10. 
    
11. List *ListConstruction(){
    
12.     list = (List*)malloc(sizeof(List));
    
13.     node = (Node*)malloc(sizeof(Node));
    
14.     list->head = node;
    
15.     list->insert = insert;// 将 insert 函数实现注册在 list 实体上
    
16.     list->drop = drop;
    
17.     list->clear = clear;
    
18.     list->size = 0;
    
19.     list->getSize = getSize;
    
20.     list->get = get;
    
21.     list->print = print;
    
22.     list->_this = list;// 用 _this 指针将 list 本身保存起来
    
23. 
    
24.     return (List*)list;
    
25. }
    

复制代码

需要注意的是此处的 _this 指针，_this 指针可以保证外部对 list 的操作映射到对 _this 的操作上，从而使得代码得到简化。

3. 插入及删除

1. // 将一个 node 插入到一个 list 对象上
   
2. void insert(void *node){
   
3.     Node *current = (Node*)malloc(sizeof(Node));
   
4. 
   
5.     current->data = node;
   
6.     current->next = list->_this->head->next;
   
7.     list->_this->head->next = current;
   
8.     (list->_this->size)++;
   
9. }
   
10. 
    
11. // 删除一个指定的节点 node
    
12. void drop(void *node){
    
13.     Node *t = list->_this->head;
    
14.     Node *d = NULL;
    
15.     int i = 0;
    
16.     for(i;i < list->_this->size;i++){
    
17.         d = list->_this->head->next;
    
18.         if(d->data == ((Node*)node)->data){
    
19.             list->_this->head->next = d->next;
    
20.             free(d);
    
21.             (list->_this->size)--;
    
22.             break;
    
23.         }else{
    
24.             list->_this->head = list->_this->head->next;
    
25.         }
    
26.     }
    
27.     list->_this->head = t;
    
28. 
    

复制代码

其他的实现代码可以参看下载部分，这里限于篇幅就不再意义列举出来。

测试

好了，前面做的一切工作都是为了保证我们的暴露给使用者的 API 可以尽量的简洁，优美，现在到测试的时候了：

4. 测试代码

1. int main(int argc, char** argv) {
   
2.     List *list = (List*)ListConstruction();// 构造一个新的链表
   
3. 
   
4. // 插入一些值做测试
   
5.     list->insert("Apple");
   
6.     list->insert("Borland");
   
7.     list->insert("Cisco");
   
8.     list->insert("Dell");
   
9.     list->insert("Electrolux");
   
10.     list->insert("FireFox");
    
11.     list->insert("Google");
    
12. 
    
13.     list->print();// 打印整个列表
    
14. 
    
15.     printf("list size = %d\n",list->getSize());
    
16. 
    
17.     Node node;
    
18.     node.data = "Electrolux";
    
19.     node.next = NULL;  
    
20.     list->drop(&node);// 删除一个节点
    
21. 
    
22.     node.data = "Cisco";
    
23.     node.next = NULL;
    
24.     list->drop(&node);// 删除另一个节点
    
25. 
    
26.     list->print();// 再次打印
    
27.     printf("list size = %d\n",list->getSize());
    
28.     list->clear();// 清空列表
    
29. 
    
30.     return 0;
    
31. }
    

复制代码

图：运行结果

结束语

    C 语言所诞生的UNIX平台提倡这样一种设计哲学：尽量进行简单的设计，让使用者如同搭积木一样的将这些简单的工具连接成强大的，完整的应用。 应该说，C 比较好的继承了这一点，C 语言非常简洁，非常强大，而由于 C 语言诞生的比较早，当时的面向对象的思想还不成熟，所以出现了大量的过程式的 C 应用，从而给人们一种 C 语言是面向过程的语言的错觉，其实 C 只是提供了一些简单，强大而通用的能力，至于你想将其搭成什么样的积木，则全靠你自己了。

精华推荐：
3分钟带你读懂C/C++学习路线
为什么来黑马程序员学C/C++？ 稳做IT贵族人才！
一张贴玩转C/C++：视频+源码+笔记+工具+面试

不错，不错