【数据结构】——较规范的链表操作方法

　　net小伙曾在文章【数据结构】双向链表的创建和读取和【数据结构】链式线性表的几种常用用法中写过关于线性表的操作方法，重新阅读发现代码很是稚嫩，现重新整理。

　　一般情况下我们会使用一个结构体head来作为双向链表的头部，head有两个指针域，一个指向链表的开始，一个指向链表的末尾。双向链表的指针域也有两个，一个指向前一个节点，一个指向后一个节点。两个结构体定义如下：

 1 #define TAILQ_HEAD(name, type)          
 2 　　struct name {                           
 3     　　struct type *tqh_first; /* first element */      
 4     　　struct type **tqh_last; /* addr of last next element */    
 5 　　}   
 6 #define TAILQ_ENTRY(type)                       
 7     struct {                                
 8         struct type *tqe_next;  /* next element */          
 9         struct type **tqe_prev; /* address of previous next element */  
10     }

　　使用二级指针是为了在遍历链表和删除链表的时候，代码更具有可读性。

　　完整的链表拓扑如下：

　　接下来直接给出代码，并附上一个小例子：

 1 #define TAILQ_HEAD(name, type)                  
 2         struct name {                                                   
 3                 struct type *tqh_first; /* first element */              
 4                 struct type **tqh_last; /* addr of last next element */    
 5         }
 6 #define TAILQ_ENTRY(type)                       
 7         struct {                                
 8                 struct type *tqe_next;  /* next element */          
 9                 struct type **tqe_prev; /* address of previous next element */  
10         }
11 
12 #define TAILQ_FIRST(head)   ((head)->tqh_first)
13 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
14 #define TAILQ_EMPTY(head)   ((head)->tqh_first == NULL)
15 #define TRASHIT(x)  do {(x) = (void *)-1;} while (0)
16 
17 #define TAILQ_INIT(head) do {                       
18         TAILQ_FIRST((head)) = NULL;                 
19         (head)->tqh_last = &TAILQ_FIRST((head));            
20 } while (0)
21 
22 #define TAILQ_INSERT_HEAD(head, elm, field) do {            
23         if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)   
24                 TAILQ_FIRST((head))->field.tqe_prev =           
25                 &TAILQ_NEXT((elm), field);              
26         else                                
27                 (head)->tqh_last = &TAILQ_NEXT((elm), field);       
28         TAILQ_FIRST((head)) = (elm);                    
29         (elm)->field.tqe_prev = &TAILQ_FIRST((head));           
30 } while (0)
31 
32 #define TAILQ_INSERT_TAIL(head, elm, field) do {            
33         TAILQ_NEXT((elm), field) = NULL;                
34         (elm)->field.tqe_prev = (head)->tqh_last;           
35         *(head)->tqh_last = (elm);                  
36         (head)->tqh_last = &TAILQ_NEXT((elm), field);           
37 } while (0)
38 
39 #define TAILQ_FOREACH(var, head, field)                 
40         for ((var) = TAILQ_FIRST((head));               
41                         (var);                          
42                         (var) = TAILQ_NEXT((var), field))
43 
44 #define TAILQ_REMOVE(head, elm, field) do {             
45         if ((TAILQ_NEXT((elm), field)) != NULL)             
46                 TAILQ_NEXT((elm), field)->field.tqe_prev =      
47                 (elm)->field.tqe_prev;              
48         else {                              
49                 (head)->tqh_last = (elm)->field.tqe_prev;       
50         }                               
51         *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);      
52         TRASHIT((elm)->field.tqe_next);                 
53         TRASHIT((elm)->field.tqe_prev);                 
54 } while (0)

queue.h

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 #include "queue.h"
 6 
 7 typedef struct _student_data {
 8         char name[64];
 9         int age;
10 }student_data_t;
11 
12 typedef struct _student_info{
13         struct _student_data student_data;
14         TAILQ_ENTRY(_student_info) next_student;
15 }student_info_t;
16 
17 #define MAX_NUM         4
18 
19 TAILQ_HEAD(student_head, _student_info) student_list;
20 
21 static student_data_t std[MAX_NUM] = {
22         {"lilei", 10},
23         {"hanmeimei", 12},
24         {"lili", 20},
25         {"lucy", 21}
26 };
27 
28 void insert_info(int num) {
29         int i;
30         student_info_t *student = NULL;
31 
32         for (i = 0; i < num; i++) {
33                 student = (student_info_t *)malloc(sizeof(student_info_t));
34                 strncpy(student->student_data.name, std[i].name, strlen(std[i].name));
35                 student->student_data.age = std[i].age;
36 
37                 TAILQ_INSERT_TAIL(&student_list, student, next_student);
38         }
39 }
40 
41 void show_info() {
42         student_info_t *tmp_info = NULL;
43 
44         printf("--------------------------------------------------
");
45         TAILQ_FOREACH(tmp_info, &student_list, next_student) {
46                 printf("name:%s age:%x
", 
47                                 tmp_info->student_data.name,
48                                 tmp_info->student_data.age
49                                 );
50         }
51         printf("--------------------------------------------------
");
52 }
53 
54 void delete_info() {
55         student_info_t *tmp_info = NULL;
56 
57 #if 0
58         TAILQ_FOREACH(tmp_info, &student_list, next_student) {
59                 TAILQ_REMOVE(&student_list, tmp_info, next_student);
60                 free(tmp_info);
61         }
62 #else
63         while(1) {
64                 TAILQ_FOREACH(tmp_info, &student_list, next_student) {
65                         TAILQ_REMOVE(&student_list, tmp_info, next_student);
66                         free(tmp_info);
67                         break;
68                 }
69                 if (!tmp_info)
70                         break;
71         }
72 #endif
73 }
74 
75 int main(int argc, char *argv[]) {
76 
77         TAILQ_INIT(&student_list);
78 
79         insert_info(MAX_NUM);
80         show_info();
81         delete_info();
82         show_info();
83 
84         return 0;
85 }

list.c

　　需要注意的是在删除的所有list的时候，不可以直接使用FOREACH遍历，并使用REMOVE进行循环删除。因为REMOVE会把tmp_info的指针域全部置空，FOREACH在下次遍历的时候会直接段错误。