avatar
文章
22
标签
8
分类
1
首页
时间轴
标签
分类
关于
清单
Aemonair
首页
时间轴
标签
分类
关于
清单
数据结构C语言实现3.双端链表
|Study
阅读量:

引言

我们已经介绍了数据结构中的单向链表以及实现了一些接口，我们发现，链表中的一个节点通过一个next指针指向下一个节点，依次传递;如果我们想要找到一个特定的节点，就算我们增加了控制信息，也必定需要从头开始遍历，如果每个节点增加一个向前一个节点的指针，它的每个数据结点中就都有两个指针，分别指向直接后继和直接前驱。我们就会可以很方便地访问它的前驱结点和后继结点。

以此，为双端链表(双向链表)。

本文所有源程序可在double_list得到。

一、双端链表的定义

我们在Dlist_node的结构体中有两个Dlist_node指针的指针域，一个void* 指针指向的数据域。由于void *是可以指向任意数据类型的指针，从而我们实现了双端链表的通用结构。

1
2
3
4
5
6
7
//双端链表节点定义
typedef struct Dlist_node
{
    struct Dlist_node *prev;    //指向前一个节点
    struct Dlist_node *next;    //指向后一个节点
    void              *data;    //数据（指针）
}Dlist_node;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//通用链表控制信息
typedef struct Dlist
{
    struct Dlist_node *head;   //指向头结点
    struct Dlist_node *tail;
    int               count;

    //我们还定义了一些函数指针在控制信息里：

    //这是一个指向某个需要被释放的数据域的函数指针
    void (*free)(void *ptr);
    //比较节点数据域
    Boolean (*match)(void *value1, void *value2);
    //拷贝节点数据域
    void *(*copy_node)(void *value);
}Dlist;

从而我们得到的双端链表结构如图示：

双端链表结构

二、双端链表的接口定义：

我们仍旧定义了对双端链表的操作，如以下接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//1.双端链表的初始化
    Dlist *init_dlist(void);
//2.双端链表的销毁
    void destroy_dlist(Dlist **dlist);//二重指针
//3.头部插入
    Boolean push_front(Dlist *dlist, void *data);
//4.尾部插入
    Boolean push_back(Dlist *dlist, void *data);
//5.头部删除
    Boolean pop_front(Dlist *dlist);
//6.尾部删除
    Boolean pop_back(Dlist *dlist);
//7.插入到当前节点前
    Boolean insert_prev(Dlist *dlist, Dlist_node *node, void *value); 
//8.插入到当前节点后
    Boolean insert_next(Dlist *dlist, Dlist_node *node, void *value); 
//9.删除某个节点
    Boolean remove_dlist_node(Dlist *dlist, Dlist_node *node);
//10.显示双端链表信息
    void show_dlist(Dlist *dlist, Print_func print);
//11.得到第一个节点数据域
    Boolean  get_front(Dlist *dlist, void **value);
//12.得到最后一个节点数据域
    Boolean  get_tail(Dlist *dlist, void **value);
//13.得到链表节点数量
    int get_dlist_count(Dlist *dlist);

我们将这些信息连同定义的宏定义一齐放入dlist.h中，

1
2
3
4
5
6
7
8
9
10
#define TRUE      (1)
#define FALSE     (0)
#define ZERO      (0)
#define ONLY_ONE  (1)
//Boolean类型不是C语言的数据类型。
typedef unsigned char Boolean ;
//这是一个函数指针，用来输出void *的数据的值的函数指针。
typedef void (*Print_func)(void *value);
//实例：void *指向int，输出int类型的函数。
void print_int(void *data);

三、其他工具类函数定义

所谓工具类，即可以调用的多处可用的工具函数，如malloc的包裹函数，或者交换函数：

1
2
void *Malloc(size_t size);
void swap(void *a, void *b, int length);

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//工具类接口

void *Malloc(size_t size)
{
    void *result = malloc(size);
    if(result == NULL)
    {
        fprintf(stderr, "the memory is full !\n");
        exit(1);
    }
    return result;
}

void swap(void *a, void *b, int length)
{
    void *temp = Malloc(length);

    memcpy(temp, a, length);
    memcpy(a, b, length);
    memcpy(b, temp, length);

    free(temp);
}

其他对双端链表的有用操作工具：

1
2
3
4
5
6
7
8
9
10
11
12
void print_int(void *data)
{
    printf("%d ",*(int *)data);
}

Dlist_node *create_node(void)
{
    Dlist_node *node = (Dlist_node *)Malloc(sizeof(Dlist_node));
    bzero(node, sizeof(Dlist_node));

    return node;
}

三、双端链表节点的接口实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
//1.双端链表的初始化
Dlist *init_dlist(void)
{
    Dlist *dlist = (Dlist *)Malloc(sizeof(Dlist));
    bzero(dlist, sizeof(Dlist));

    return dlist;
}
//2.双端链表的销毁
void destroy_dlist(Dlist **dlist)//二重指针
{
    if(dlist == NULL || *dlist == NULL)
    {
        return;
    }
/*
    while((*dlist)->head)        //(*)->
    { 
        pop_back(*dlist);
    }
*/
    Dlist_node *p_node = (*dlist)->head;
    while((*dlist)->head != NULL)
    {
        (*dlist)->head = p_node->next;
        if((*dlist)->free != NULL) //函数指针free
        {
            (*dlist)->free(p_node->data);
        }
        free(p_node);
        p_node = (*dlist)->head;
    }
    free(*dlist);
    dlist = NULL;
}
//3.头部插入
    //  case 1:
    //     node
    //       |
    //   head tail 
    //
    //  case 2:
    //    node
    //    //
    //   node1==node2==node3
    //      \         /
    //       head|tail
Boolean push_front(Dlist *dlist, void *data)
{
    if(dlist == NULL || data == NULL)
    {
        return FALSE;
    }
    
    Dlist_node *node = create_node();  //调用链表工具
    node->data = data ;                //创建一个新节点

    if(dlist->count == ZERO)
    {
        dlist->tail = node;
    }
    else
    {
        node->next = dlist->head;
        dlist->head->prev = node;
    }
    dlist->head = node;                //头插
    dlist->count ++;

    return TRUE;
}
//4.尾部插入
    //  case 1:
    //     node
    //       |
    //   head tail 
    //
    //  case 2:
    //                  node
    //                    \\
    //   node1==node2==node3
    //      \         /
    //       head|tail
Boolean push_back(Dlist *dlist, void *data)
{
    if(dlist == NULL || data == NULL)           /*  error:value == NULL  */
    {
        return FALSE;
    }
    Dlist_node *node = create_node();           
    node->data = data ;
    if(dlist->count == ZERO)
    {
        dlist->head = node;
    }
    else
    {
        node->prev = dlist->tail;
        dlist->tail->next = node;
    }
    dlist->tail = node;
    dlist->count ++;

    return TRUE;                               
}

//5.头部删除
    //  case 1:
    //     (node)
    //       |
    //   head tail 
    //
    //  case 2:
    //   (node1)==node2==node3==node4
    //           /              /
    //          head         tail
Boolean pop_front(Dlist *dlist)
{
    if(dlist == NULL || dlist->count == ZERO)
    {
        return FALSE;
    }

    Dlist_node *node = dlist->head;       //头节点

    if(dlist->count == ONLY_ONE)
    {
        dlist->head = dlist->tail = NULL;
    }
    else
    {
  /*   node->next->prev = NULL;
   *   dlist->head = node->next;  //
   */   
       dlist->head = node->next;
       dlist->head->prev = NULL;
    }
/*
    dlist->free(node);            //free函数释放掉之前所指头节点的位置
    node = NULL;
*/
    if(dlist->free != NULL)       //这里我们调用我们自己的free指针函数
    {
        dlist->free(node->data);
    }
    free(node);
    dlist->count-- ;
    
    return TRUE;
}

//6.尾部删除
    //  case 1:
    //     (node)
    //       |
    //   head tail 
    //
    //  case 2:
    //   node1==node2==node3==(node4)
    //       \            \
    //      head         tail
Boolean pop_back(Dlist *dlist)
{
    if(dlist == NULL || dlist->count == ZERO)
    {
        return FALSE;
    }

    Dlist_node *node = dlist->tail;      //node指向尾节点

    if(dlist->count == ONLY_ONE)
    {
        dlist->head = dlist->tail = NULL;
    }
    else
    {
        dlist->tail = node->prev;
        dlist->tail->next = NULL;        //释放尾节点与链表的连接
    }
    
    if(dlist->free != NULL)
    {
        dlist->free(node->data);
    }
    free(node);
    dlist->count -- ;
    
    return TRUE;
}
//7.插入到当前节点前
    //
    //         node
    //        //  \\
    //   node1      node2==node3
    //      \              /
    //       head        tail
Boolean insert_prev(Dlist *dlist, Dlist_node *node, void *value)
{
    if(dlist == NULL || node == NULL )
    {
        return FALSE;
    }

    Dlist_node *p_node = create_node();
    p_node->data = value;                   //生成节点p->node

    if(dlist->count == ONLY_ONE)
    {
        push_front(dlist, value);           //只有一个节点时，头插
        return TRUE;
    }
    else
    {
        //        p_node
        //        //  \\
        //   node1      node
        p_node->next = node;
        p_node->prev = node->prev;
        
        node->prev->next = p_node;
        node->prev = p_node;
        dlist->count++;
    }
    return TRUE;
}
//8.插入到当前节点后
    //
    //         node
    //        //  \\
    //   node1      node2==node3
    //      \              /
    //       head        tail
Boolean insert_next(Dlist *dlist, Dlist_node *node, void *value)
{
    if(dlist == NULL || node == NULL )
    {
        return FALSE;
    }

    Dlist_node *p_node = create_node();
    p_node->data = value;                   //新节点p_node

    if(dlist->count == ONLY_ONE)
    {
        push_back(dlist, value);
        return TRUE;
    }
    else
    {
        //        p_node
        //       //    \\
        //     node     node1
        p_node->next = node->next;    //先把p_node信息挂在链表上
        p_node->prev = node;
        
        node->next->prev = p_node;    //再改变链表上的结构信息
        node->next = p_node;
        dlist->count++;
    }
    return TRUE;
}
//9.删除某个节点
    //  case 1:
    //     (node)
    //       |
    //   head tail 
    //
    //  case 2:
    //   node1==node2==(node3)==node4
    //       \                  /
    //      head             tail
Boolean remove_dlist_node(Dlist *dlist, Dlist_node *node)
{
    if(dlist == NULL || node == NULL)
    {
        return FALSE;
    }
    if(node->next == NULL)
    {
        return pop_back(dlist);    //在尾部，则尾删
    }
    else
    {
        //                  node   p_node
        //   node1==node2==(node3)==node4==node5
        //       \                         /
        //      head                     tail
        Dlist_node *p_node = node->next;
        node->data = p_node->data;
        
        //用node的下一个节点代替node
        
        node->next = p_node->next;
        p_node->next->prev = node;
    
        if(dlist->free != NULL)
        {
            dlist->free(p_node->data);
        }
        free(p_node);
        dlist->count -- ;
    }
    return TRUE;
}
//10.显示双端链表信息
void show_dlist(Dlist *dlist, Print_func print)  //我们的参数是print，是一个函数指针;
{
    Dlist_node *p_node = NULL;

    if(dlist != NULL && dlist->count >0)
    {
        for(p_node = dlist->head; p_node; p_node = p_node->next)
        {
            print(p_node->data);
        }
        printf("\n");
    }
}

//11.得到第一个节点数据域
    //**value是一个二重指针，可以用来保存void *类型的数据指针域
Boolean  get_front(Dlist *dlist, void **value)
{
    if(dlist == NULL || dlist->count == ZERO)
    {
        return FALSE;
    }
    if(value != NULL)
    {     
       *value = dlist->head->data;
    }
    return TRUE;
}
//12.得到最后一个节点数据域
    //与11同理
Boolean  get_tail(Dlist *dlist, void **value)
{
    if(dlist == NULL || dlist->count == ZERO)
    {
        return FALSE;
    }
    if(value != NULL)
    {     
       *value = dlist->tail->data;
    }
    return TRUE;
}
//13.得到链表节点数量
     //链表控制信息中有关于节点个数的变量count
int get_dlist_count(Dlist *dlist)
{
    if(dlist == NULL)
    {
        return -1;
    }
    else
    {
        return dlist->count;
    }
}

四、程序功能验证

验证程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include "dlist.h"
/*
void print_int(void *value);
void print_int(void *value)
{
    printf("%d ",*(int *)value);
 }
*/
int main(int argc, char **argv)
{
    int i = 0;
    int a[]={1,2,3,4,5};
    void *value;

    Dlist *dlist = NULL;
    dlist = init_dlist();
    printf("push_front(dlist, &a[i]);\n");
    for(i=0; i< sizeof(a)/sizeof(a[0]);++i)
    {
        push_front(dlist, &a[i]);
    }
    show_dlist(dlist, print_int);
    printf("pop_front(dlist);\n");
    pop_front(dlist);

    show_dlist(dlist, print_int);
    printf("push_back(dlist, &a[i]);\n");
    for(i=0; i< sizeof(a)/sizeof(a[0]);++i)
    {
        push_back(dlist, &a[i]);
    }
    show_dlist(dlist, print_int);
    printf("pop_back(dlist);\n");
    pop_back(dlist);
    show_dlist(dlist, print_int);
    
    printf("insert_prev(dlist, dlist->head->next->next, &a[4]);\n");
    insert_prev(dlist, dlist->head->next->next, &a[4]);
    show_dlist(dlist, print_int);

    printf("insert_next(dlist, dlist->head->next->next, &a[4]);\n");
    insert_next(dlist, dlist->head->next->next, &a[4]);
    show_dlist(dlist, print_int);

    printf("remove_dlist_node(dlist, dlist->head->next->next->next);\n");
    remove_dlist_node(dlist, dlist->head->next->next->next);
    show_dlist(dlist, print_int);
   
    get_front(dlist, &value);
    printf("\nfront:\n");
    print_int(value);

    get_tail(dlist, &value);
    printf("\ntail:\n");
    print_int(value);

    printf("\nthe length:\n");
    printf("%d \n",get_dlist_count(dlist));
    destroy_dlist(&dlist);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
root@aemonair:my_dlist# ./dlist 
push_front(dlist, &a[i]);
5 4 3 2 1 
pop_front(dlist);
4 3 2 1 
push_back(dlist, &a[i]);
4 3 2 1 1 2 3 4 5 
pop_back(dlist);
4 3 2 1 1 2 3 4 
insert_prev(dlist, dlist->head->next->next, &a[4]);
4 3 5 2 1 1 2 3 4 
insert_next(dlist, dlist->head->next->next, &a[4]);
4 3 5 5 2 1 1 2 3 4 
remove_dlist_node(dlist, dlist->head->next->next->next);
4 3 5 2 1 1 2 3 4 

front:
4 
tail:
4 
the length:
9

本文所有源程序可在Data_struct /double_list上得到。

总结：

本文简单的实现了较通用的双向链表，其中采用的通用思想不仅仅存在于封装操作，更是旨在使用void *指向的数据域，以及可以拓展的打印方式。
简单的接口，简单的操作，在对链表进行增删查改的时候，应该充分发挥其结构优势。
我们可以发现，作为一种很重要的数据结构，双向链表还是很重要的。今后还将继续对其进行更深一步的讨论。

文章作者: Air
文章链接: http://aemonair.github.io/2016/06/03/Data_Structure_03_Double_Linked_List/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Aemonair！
DataStructLinkedList
相关推荐
2020-04-29
数据结构C语言实现2.带控制信息的链表
2020-04-29
数据结构C语言实现4.进一步封装的双向链表
2020-04-29
数据结构C语言实现1.单链表
2020-04-29
数据结构C语言实现5.通用栈
2020-04-29
数据结构C语言实现6.通用队列
2020-04-29
数据结构C语言实现8.广义表
简