C语言用指针支持数据结构

指针可以为简单或复杂的数据结构提供更多的灵活性。这些灵活性可能来自动态内存分配，也可能来自切换指针引用的便利性。内存无需像数组那样是连续的，只要总的内存大小对就可以。

在本节中，我们会研究几种可以用指针实现的常用数据结构。很多C库都会提供这里提到的数据结构，而且会提供更广泛的支持。不过，理解如何实现这些数据结构对于实现非标准的数据结构很有帮助。在某些平台上可能无法使用这些库，开发者需要实现自己的版本。

我们会研究以下四种不同的数据结构。

• 链表
  单链表
• 队列
  简单的先进先出队列
• 栈
  简单的栈
• 树
  二叉树

我们会结合函数指针和这些数据结构来说明它们处理通用结构时的强大能力。链表是非常有用的数据结构，我们会把它作为实现队列和栈的基础。

我们会利用一个雇员结构体说明这些数据结构。比如说，链表由互相连接的节点组成，每个节点会持有用户提供的数据，雇员结构体如下所示。unsigned char数据类型用来表示年龄，它足够装下人类的年龄了：

typedef struct _employee{
    char name[32];
    unsigned char age;
} Employee;    

每个名字用一个数组表示，对于这个字段，char指针可能是更灵活的数据类型，不过简单起见，我们还是选择了char数组。

我们会开发两个比较函数，第一个比较两个雇员然后返回一个整数，它模仿了strcmp函数，返回值0表示两个雇员结构体相等，-1表示第一个雇员比第二个雇员小，1表示第一个雇员比第二个雇员大。第二个函数则用来打印雇员：

int compareEmployee(Employee *e1, Employee *e2) {
    return strcmp(e1->name, e2->name);
}

void displayEmployee(Employee* employee) {
    printf("%s\t%d\n", employee->name, employee->age);
}

此外，我们还会用到两个函数指针，定义如下。DISPLAY函数指针表示一个接受void*参数并返回void的函数，目的是显示数据。第二个函数指针COMPARE比较两个指针引用的数据，它的返回值是0、-1或1，我们在介绍compareEmployee函数的时候解释过了：

typedef void(*DISPLAY)(void*);
typedef int(*COMPARE)(void*, void*);