首页 > 代码库 > 深入理解C指针之六：指针和结构体
深入理解C指针之六：指针和结构体
C的结构体可以用来表示数据结构的元素，比如链表的节点，指针是把这些元素连接到一起的纽带。 结构体增强了数组等集合的实用性，每个结构体可以包含多个字段。如果不用结构体，可能要分别为每个字段声明一个数组，使用结构体，可以声明一个结构体的数组来组合这些字段。
结构体基础
声明结构体的方式有很多种，这里先讨论两种：
//第一种声明方式struct person{char* firstname;char* secondname;char* title;unsigned int age;};//第二种声明方式typedef struct _person{char* firstname;char* secondname;char* title;}Person;可以直接使用Person声明一个该结构体的实例，使用点表示法来访问其字段，也可以声明一个指向该结构体的指针，使用箭头操作符访问字段。
Person myperson;myperson.firstname = (char*) malloc (strlen("jack") + 1);strcpy(myperson.firstname,"jack");myperson.age = 18;Person* ptrPerson;ptrPerson = (Person*) malloc (sizeof(Person));ptrPerson -> firstname = (char*) malloc (strlen("rose") +1);strcpy(ptrPerson -> firstname, "rose");ptrPerson -> age = 16;对于指针的箭头写法 ptrPerson -> age，你也可以使用解引+点的写法 (*ptrPerson).age来代替。这样写稍微复杂了一些而已。
为结构体分配内存时，分配的内存大小至少是各个字段的长度和。不过，实际长度通常大于这个值，结构体的各个字段之间可能会有填充。如果某些数据类型需要对齐到边界，就会产生填充。比如，短整数通常对其到能被2整除的地址上，整数对齐到能被4整除的地址上。这意味着：
* 谨慎使用算数运算符；
* 结构体数组的元素之间可能存在额外的内存。
printf("size of person is %d\n", sizeof(myperson));//size of person is 16typedef struct _otherPerson{char* firstname;char* secondname;char* title;short age;}OtherPerson;OtherPerson otherPerson;printf("size of otherperson is %d\n", sizeof(otherPerson));//size of otherperson is 16把 int 改成 short ，发现结构体的大小还是16个字节，这是因为在 short age 处产生了填充。short类型实际还是占用了2个字节，只不过内存里产生了“缝隙”而已。
释放结构体
在为结构体分配内存时，运行时系统不会自动为结构体内部的指针分配内存。当结构体消失时，运行时系统也同样不会为其指针释放内存。假如我们声明了一个Person的结构体，Person person，然后为person的指针动态分配内存，那么使用完毕后必须记得手动释放动态分配的内存。因为person是一个局部变量，函数返回后person会消失，我们如果忘记释放内存，会导致内存泄露。如果使用Person* ptrPerson的方式，还要连ptrPerson的内存也释放掉。
重复分配然后释放结构体会产生一些开销，可能造成巨大的性能瓶颈。一个解决办法是为分配的结构体维护一个表。当用户不再需要某个结构体实例时，将其返回池中。当需要时，从池中获取一个对象。如果池中没有可用元素，就动态分配一个实例。这种方法能够按需使用和重复使用内存。可以用数组或链表等维护结构体池。如果使用数组来管理，需要注意数组的长度应该合适，不能太长或太短。
指针与数据结构
指针可以为数据结构提供更多的灵活性。这些灵活性可能来自动态内存分配，也可能来自切换指针引用的便利。内存无需像数组那样是连续的，只要总的内存大小正确就行。我们使用一个 Empolyee 结构体来说明几种常见数据结构。
typedef struct _empolyee{char name[32];unsigned char age;}Empolyee;typedef int (*COMPARE) (void*, void*);typedef void(*DISPLAY) (void*);int compareEmpolyee(Empolyee* e1, Empolyee* e2){return strcmp(e1 -> name, e2 -> name);}void displayEmpolyee(Empolyee* e){printf("name is %s age is %d\n", e-> name, e-> age);}链表是由一系列互相连接的节点组成的数据结构。通常会有一个节点成为头节点，其它节点顺序跟在头节点后面，最后一个节点称为尾节点。我们可以使用指针动态分配每个节点。链表有好几种类型，最简单的是单链表，一个节点到下一个节点只有一个连接，连接从头节点开始，到尾结点结束。循环链表没有尾节点，链表的最后一个节点又指向头节点。双链表用了两个链表，一个向前链接，一个向后链接，可以在两个方向上查找节点。
这张图大致描述了不同链表之间的链接方法。下面看一下怎么用结构体和指针实现一个简单的链表。
#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct _employee{char name[32];unsigned char age;}Employee;typedef int (*COMPARE) (void*, void*);typedef void(*DISPLAY) (void*);typedef struct _node{void* data;struct _node* next;}Node;typedef struct _linkedList{Node* head;Node* tail;Node* current;}LinkedList;int compareEmployee(Employee* e1, Employee* e2){return strcmp(e1 -> name, e2 -> name);}void displayEmployee(Employee* e){printf("name is %s age is %d\n", e-> name, e-> age);}void initializeList(LinkedList* list){list -> head = NULL;list -> tail = NULL;list -> current = NULL;}void addHead(LinkedList* list, void* data){Node* node = (Node*) malloc (sizeof(Node));node -> data = http://www.mamicode.com/data;>if(node == list -> tail){
list -> tail = tmp;
}}free(node);}void displayList(LinkedList* list, DISPLAY display){printf("\n********linkedlist********\n");Node* current = list -> head;while(current != NULL){display(current -> data);current = current -> next;}}main(){LinkedList linkedList;Employee *samuel = (Employee*) malloc (sizeof(Employee));strcpy(samuel -> name,"Samuel");samuel -> age = 15;Employee *sally = (Employee*) malloc (sizeof(Employee));strcpy(sally -> name,"Sally");sally -> age = 12;Employee *susan = (Employee*) malloc (sizeof(Employee));strcpy(susan -> name,"Susan");susan -> age = 18;initializeList(&linkedList);addHead(&linkedList, samuel);addHead(&linkedList, sally);addTail(&linkedList, susan);displayList(&linkedList, (DISPLAY)displayEmployee);Node* getNode(LinkedList* list, COMPARE compare, void* data){Node* node = list -> head;while(node != NULL){if(compare(node->data,data) == 0){return node;}node = node -> next;}return NULL;}Node* susanNode = getNode(&linkedList, (int (*)(void*,void*))compareEmployee, susan);delete(&linkedList, susanNode);displayList(&linkedList, (DISPLAY)displayEmployee);}addHead 和 addTail 负责往链表的头部和尾部添加新的节点。getNode 通过一个函数指针根据数据查找节点，然后在删除节点的时候把节点传给删除函数。总体来说这个示例非常直白简单。
队列是一种线性数据结构，通常支持两种操作：入队和出队。入队操作把元素添加到队列中，出队操作从队列中删除元素。一般来说，第一个添加到队列的元素也是第一个离开队列的元素，这种行为被称为先进先出。
可以用链表实现队列。入队操作就是添加到链表头，出队操作就是从链表尾删除节点。我们需要再定义一个从链表尾删除节点的方法来支持队列操作。
void deleteTail(LinkedList* list){Node* node = list -> tail;if(node == NULL){}else{if(list -> head == list -> tail){list -> head = list -> tail = NULL;}else{Node* tmp = list -> head;while( tmp -> next != list -> tail){tmp = tmp -> next;}list -> tail = tmp;tmp = tmp -> next;list -> tail -> next = NULL;free(tmp);}}}栈数据结构也是一种链表。对于栈，元素被推入栈顶，然后被弹出。当多个元素被推入和弹出时，栈的行为是先进后出。
可以用链表来实现栈操作。入栈可以使用 addHead 函数实现，出栈操作需要再定义一个删除头节点的函数。
void deleteHead(LinkedList* list){Node* node = list -> head;if(node == NULL){}else{if(list -> head == list -> tail ){list -> head = list -> tail = NULL;free(node);}else{list -> head = list -> head -> next;free(node);}}}最后来看看树。树的子节点连接到父节点，从整体看就像一颗倒过来的树，根节点表示 这种数据结构的开始元素。树可以有任意数量的子节点，但是二叉树比较常见，它的每个节点能有0个、1个或2个子节点。子节点要么是左节点，要么是右节点。没有子节点的节点称为叶子节点。我们可以动态分配节点，按需插入树中。
按照特定顺序向树中插入节点是很有意义的，这样可以让查询等操作变得容易。比如：插入新节点后，这个节点的所有左子节点的值都比父节点小，所有右子节点的值都比父节点的值大，这样的树称为二叉查找树。
typedef struct _tree{void* data;struct _tree* left;struct _tree* right;}TreeNode;void insertNode(TreeNode** root, COMPARE compare, void* data){TreeNode* node = (TreeNode*) malloc (sizeof(TreeNode));node -> data = http://www.mamicode.com/data;>这里实现了一个插入节点的方法，以及三种顺序的遍历树的方法。插入节点是按照大小排序来插入的，遍历树则根据何时执行操作（这里是display）分为中序（inOrder）、前序（preOrder）、后序（postOrder）三种方法。
* 中序：先往左，访问节点，再往右。
* 前序：访问节点，往左，再往右。
* 后序：往左，往右，再访问节点。
当然，你也可以自己定义把左边和右边完全翻转过来，先右边后左边。
深入理解C指针之六：指针和结构体