avatar
文章
22
标签
8
分类
1
首页
时间轴
标签
分类
关于
清单
Aemonair
首页
时间轴
标签
分类
关于
清单
数据结构C语言实现4.进一步封装的双向链表
|Study
阅读量:

====
引言

    在前面，我们已经对数据结构中的双向链表进行了阐述，在这一节，我们将会对双向链表进行更深层次的封装。
在C++的STL中，或者在java中，都会有一个概念叫做迭代器。迭代器提供对一个容器中的有范围的对象的访问。
迭代器就如同一个指针。这一节我们可以迭代器封装链表使用户接触不到底层数据结构，保证安全访问。
以及将我们常用到的函数封装在tools.h当中，使程序模块化，碎片化，冗余性低，便于提升和增加新功能。

一、双向链表定义
与上一节基本相同：
双向链表定义

'i_list.h'
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
#ifndef _DLIST_H_
#define _DLIST_H_

#include "iterator.h"                     // 这里我们增加了一个iterator迭代器的头文件

#define TRUE      (1)
#define FALSE     (0)
#define ZERO      (0)
#define ONLY_ONE  (1)
typedef unsigned char Boolean ;           // 布尔类型
typedef void (*Print_func)(void *value);  // 打印的函数指针

void print_int(void *data);

typedef struct Dlist_node{
    struct Dlist_node *prev;
    struct Dlist_node *next;              // 指向后一个节点
    void              *data;
}Dlist_node;

typedef struct Dlist Dlist;
//通用链表控制信息
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);
    
    // 迭代器接口：
    //指向链表头部
    void *(*iter_head)(Iterator *iter, Dlist *dlist);
    //指向链表尾部
    void *(*iter_tail)(Iterator *iter, Dlist *dlist);
    //指向前一个元素位置
    void *(*iter_prev)(Iterator *iter, Dlist *dlist);
    //指向后一个元素位置
    void *(*iter_next)(Iterator *iter, Dlist *dlist);
}Dlist;

//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);
//14.得到第几个节点
    Dlist_node *find_node(Dlist *dlist, int index);
#endif

* 工具类接口定义 *

1
2
3
4
5
6
7
8
9
10
11
12
#ifndef _TOOLS_H_
#define _TOOLS_H_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//工具类接口

void *Malloc(size_t size);
void swap(void *a, void *b, int length);
#endif

* 工具类接口实现 *

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
#include "tools.h"

//工具类接口

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);
}

二、迭代器的定义
iterator

* 迭代器的定义 *

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
#ifndef _ITERATOR_H_
#define _ITERATOR_H_

typedef struct Iterator
{
    void   *ptr;        //指针 void* 通用指针
    int   index;        //整型 index 指标 索引
    int    size;        //整型 size 大小
}Iterator;              //三个成员的一个结构体

/*
 * 正向迭代器
 * container(list、array、stack)容器
 */

//宏定义

#define FOREACH(iter, container) \
    for(container->iter_head(&(iter), container); \
    (iter).ptr; \
    container->iter_next(&(iter), container))

#define foreach FOREACH

#define FOREACH_REVERSE(iter, container) \
    for(container->iter_tail(&(iter), container); \
    (iter).ptr; \
    container->iter_prev(&(iter), container))

#define foreach_reverse FOREACH_REVERSE

#endif

由于迭代器是在链表中使用，所以我们把迭代器操作实现一起放在了链表的实现文件里。
我们可以从定义中看到，我们定义的foreach是一个正向、在container中通过ptr指针指向下一个迭代的正向迭代方法。
foreach_reverse正好是从tail尾开始向前iter_prev反向的反向迭代。

三、双向链表的接口实现

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
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
#include "dlist.h"
#include "tools.h"

// 整型的打印函数
void print_int(void *data)
{
    printf("%d ",*(int *)data);
}


// 迭代器的接口函数指针定义
static void *dlist_iter_head(Iterator *iter, Dlist *dlist);
static void *dlist_iter_tail(Iterator *iter, Dlist *dlist);
static void *dlist_iter_prev(Iterator *iter, Dlist *dlist);
static void *dlist_iter_next(Iterator *iter, Dlist *dlist);

//迭代器的接口函数指针实现
//1.dlist的头迭代指针
static void *dlist_iter_head(Iterator *iter, Dlist *dlist)
{
    if(iter == NULL || dlist == NULL)
    {
        return NULL;
    }
    iter->index = 0;
    iter->size = dlist->count;

    //dlist的头节点
    if(dlist->head->data == NULL || dlist->count == ZERO)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = dlist->head->data;
    }
    return iter->ptr;
}
//2.dlist的尾节点迭代
static void *dlist_iter_tail(Iterator *iter, Dlist *dlist)
{
    if(iter == NULL || dlist == NULL)
    {
        return NULL;
    }
    iter->index = dlist->count - 1;
    iter->size = dlist->count;

    //dlist的尾节点
    if(dlist->tail->data == NULL || dlist->count == ZERO)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = dlist->tail->data;
    }
    return iter->ptr;
}

//3.dlist迭代前一个(函数指针)
static void *dlist_iter_prev(Iterator *iter, Dlist *dlist)
{
    if(iter == NULL || dlist == NULL)
    {
        return NULL;
    }
    iter->index --;
    iter->size = dlist->count;

    if(iter->index <= ZERO)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = find_node(dlist, iter->index)->data;
    }
    return iter->ptr;
}

//4.dlist迭代后一个(函数指针)
static void *dlist_iter_next(Iterator *iter, Dlist *dlist)
{
    if(iter == NULL || dlist == NULL)
    {
        return NULL;
    }
    iter->index ++;
    iter->size = dlist->count;

    if(iter->index >= iter->size)
    {
        iter->ptr = NULL;
    }
    else
    {
        iter->ptr = find_node(dlist, iter->index)->data;
    }
    return iter->ptr;
}

//创建一个节点
Dlist_node *create_node(void);
Dlist_node *create_node(void)
{
    Dlist_node *node = (Dlist_node *)Malloc(sizeof(Dlist_node));
    bzero(node, sizeof(Dlist_node));

    return node;
}

//1.双端链表的初始化
Dlist *init_dlist(void)
{
    Dlist *dlist = (Dlist *)Malloc(sizeof(Dlist));
    bzero(dlist, sizeof(Dlist));

    //置函数指针
    dlist->iter_head = dlist_iter_head;
    dlist->iter_tail = dlist_iter_tail;
    dlist->iter_prev = dlist_iter_prev;
    dlist->iter_next = dlist_iter_next;
    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)
        {
            (*dlist)->free(p_node->data); //若我们有自己编写free函数，就用我们定义的free函数指针释放资源
        }
        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)
{
    //创建新节点
    Dlist_node *node = create_node();
    node->data = data ;

    if(dlist == NULL || data == NULL)
    {
        return FALSE;
    }
    if(dlist->count == ZERO)
    {
        dlist->tail = node;    //若dlist中没有元素则将dlist->tail也给这个节点
    }
    else
    {
        node->next = dlist->head;    //置node的next为头节点
        dlist->head->prev = node;    //head的前一个置是node
    }
    dlist->head = node;
    dlist->count ++;

    return TRUE;
}
//4.尾部插入
Boolean push_back(Dlist *dlist, void *data)
{
    if(dlist == NULL || data == 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.头部删除
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
    { 
        dlist->head = node->next;
        dlist->head->prev = NULL;
    }
/*
    dlist->free(node);
    node = NULL;
*/
    if(dlist->free != NULL)      //如果我们有相应的free函数
    {
        dlist->free(node->data); //调用自己的free函数
    }
    free(node);
    dlist->count -- ;
    
    return TRUE;
}
//6.尾部删除
Boolean pop_back(Dlist *dlist)
{
    if(dlist == NULL || dlist->count == ZERO)
    {
        return FALSE;
    }

    Dlist_node *node = dlist->tail;

    if(dlist->count == ONLY_ONE)
    {
        dlist->head = dlist->tail = NULL;
    }
    else
    {
        dlist->tail = node->prev;
        dlist->tail->next = NULL;
    }
    
    if(dlist->free != NULL)       //free函数指针
    {
        dlist->free(node->data);
    }
    free(node);
    dlist->count -- ;
    
    return TRUE;
}
//7.插入到当前节点前
Boolean insert_prev(Dlist *dlist, Dlist_node *node, void *value)
{
    Dlist_node *p_node = create_node();
    p_node->data = value;

    if(dlist == NULL || node == NULL )
    {
        return FALSE;
    }
    if(dlist->count == ONLY_ONE)
    {
        push_front(dlist, value);
        return TRUE;
    }
    else                          //普通情况下
    {
        p_node->next = node;
        p_node->prev = node->prev;
        
        node->prev->next = p_node;
        node->prev = p_node;
        dlist->count++;
    }
    return TRUE;
}
//8.插入到当前节点后
Boolean insert_next(Dlist *dlist, Dlist_node *node, void *value)
{
    Dlist_node *p_node = create_node();
    p_node->data = value;

    if(dlist == NULL || node == NULL )
    {
        return FALSE;
    }
    if(dlist->count == ONLY_ONE)
    {
        push_back(dlist, value);
        return TRUE;
    }
    else
    {
        p_node->next = node->next;
        p_node->prev = node;
        
        node->next->prev = p_node;
        node->next = p_node;
        dlist->count++;
    }
    return TRUE;
}
//9.删除某个节点
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
    {
        Dlist_node *p_node = node->next;
        node->data = p_node->data;

        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)
{
    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.得到第一个节点数据域
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.得到最后一个节点数据域
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.得到链表节点数量
int get_dlist_count(Dlist *dlist)
{
    if(dlist == NULL)
    {
        return -1;      //返回值一般用-1表示出错;
    }
    else
    {
        return dlist->count;
    }
}

//14.得到第几个节点
Dlist_node *find_node(Dlist *dlist, int index)
{
    int i = 0;
    Dlist_node *p_node = NULL;

    if(dlist == NULL || index > dlist->count || index < 0)  //判断条件
    {
        return NULL;
    }
    p_node = dlist->head;
    while(i++ < index)
    {
        p_node = p_node->next;
    }
    return p_node;
}

四、程序功能验证
main.c

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
#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;
    Iterator iter = {0};

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


    printf("---------foreach：\n");
    //这里，我们就用到了迭代的方法，用我们定义的foreach对dlist这个容器进行迭代的输出。
    foreach(iter, dlist)
    {
        print_int(iter.ptr);
    }
    printf("\n");
    show_dlist(dlist, print_int);
    for(i=0; i< sizeof(a)/sizeof(a[0]);++i)
    {
        push_back(dlist, &a[i]);
    }
    show_dlist(dlist, print_int);
    pop_back(dlist);
    show_dlist(dlist, print_int);
    
    insert_prev(dlist, dlist->head->next->next, &a[4]);
    show_dlist(dlist, print_int);

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

    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("\n the length:\n");
    printf("%d \n",get_dlist_count(dlist));

    foreach(iter, dlist)
    {
        print_int(iter.ptr);
    }
    printf("\n");
 
    destroy_dlist(&dlist);
    return 0;
}

编译运行结果

1
2
3
4
5
root@aemonair:i_dlist# cc.sh *.c
Compiling ...
-e CC      dlist.c main.c tools.c -g -lpthread
-e         Completed .
-e         Thu Jun 16 00:21:05 CST 2016

程序运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
root@aemonair:i_dlist# ./dlist 
5 4 3 2 1 
---------foreach：
4 3 2 1 
4 3 2 1 
4 3 2 1 1 2 3 4 5 
4 3 2 1 1 2 3 4 
4 3 5 2 1 1 2 3 4 
4 3 5 5 2 1 1 2 3 4 
4 3 5 2 1 1 2 3 4 

front:
4 
tail:
4
 the length:
9 
4 3 5 2 1 1 2 3 4

总结
这次，我们只是简单的对迭代器有了初步认识，并且进一步封装了双向链表。对于链表的基本操作并没有多大改进，只是着重强调了，对迭代器思想的认识。
同时，对双向链表的封装到了一定程度。我们可以实现通用的链表和接口，并用其实现其他的数据结构。

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