函数的实现在判断元素结点是否为头结点或尾结点时, 并未使用 list->head list->tail 指针 而是判断该结点是否存在前一结点element->prev或后一结点element->next是否为空 这样从而导致在向指定结点前面或后面插入元素时, 不能过早将element-prev element->next 指向新结点new_element 以避免判断头尾结点失败

单链表(Linked List)

 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
/* list.h */

#ifndef LIST_H
#define LIST_H

#include <stdlib.h>
/* 链表元素结构 */
typedef struct ListElmt_ {
    /* 指向实际数据地址 */
    void *data;
    /* 指向下一个结点元素的指针 */
    struct ListElmt_ *next;
}ListElmt;

/* 链表的结构定义 */
typedef struct List_ {
    /* 链表中元素的个数 */
    int size;
    /* 该函数由从链表结构派生而来的新类型使用 */
    int (*match)(const void *key1, const void *key2);
    /* 销毁链表时调用的析构函数 */
    void (*destroy)(void *data);
    /* 头结点 */
    ListElmt *head;
    /* 末尾结点 */
    ListElmt *tail;
}List;

/* 初始化 list 指定的链表,提供一个函数 destroy 以便在调用 list_destory 来销毁链表时做些必要的工作,如释放数据内存等 */
void list_init(List *list, void (*destory)(void *data));

/* 销毁链表 */
void list_destroy(List *list);

/* 单链表由于不清楚某一结点的前一结点,所以插入和删除只能操作该结点后的元素 */
/* 在element后插入一个元素,如果element为NULL,则在链表头头插入。成功返回0,失败返回-1 */
int list_ins_next(List *list, ListElmt *element, const void *data);

/* 移除element后的那个元素,如果element为NULL,则移除链表头元素。
调用返回后,data指向已移除元素中存储的数据。成功0,失败-1 */
int list_rem_next(List *list, ListElmt *element, void **data);

/* 返回元素个数 */
#define list_size(list) ((list)->size)

/* 返回链表头元素指针 */
#define list_head(list) ((list)->head)

/* 判断是否是头结点,是返回1,否则返回0 */
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)

/* 判断链表末尾结点,是返回1,否则返回0 */
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)

/* 返回结点中保存的数据 */
#define list_data(element) ((element)->data)

/* 返回element的下一个结点 */
#define list_next(element) ((element)->next)

#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
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
#include <stdlib.h>
#include <string.h>

#include "list.h"

void list_init(List *list, void (*destroy)(void *data))
{
    /* 初始化链表 */
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;

    return;
}

void list_destroy(List *list)
{
    void *data;
    /* 移除链表中所有元素 */
    while (list_size(list) > 0) {
        if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {
            /* 当 destroy 不为 NULL 时,对数据调用 */
            list->destroy(data);
        }
    }
    /* 清空置0链表内存 */
    memset(list, 0, sizeof(list));
    return;
}

int list_ins_next(List *list, ListElmt *element, const void *data)
{
    ListElmt *new_element;
    /* 为新元素申请内存 */
    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL) {
        return -1;
    }
    new_element->data = (void *)data;
    if (element == NULL) {
        /* 空链表时,新插入元素是末尾元素 */
        if (list_size(list) == 0) {
            list->tail = new_element;
        }
        new_element->next = list->head;
        list->head = new_element;
    } else {
        /* element 是末尾元素时,新插入元素是末尾元素 */
        if (element->next == NULL) {
            list->tail = new_element;
        }
        new_element->next = element->next;
        element->next = new_element;
    }
    /* 链表长度增加1 */
    list->size++;

    return 0;
}

int list_rem_next(List *list, ListElmt *element, void **data) {
    ListElmt *old_element;

    /* 空链表 */
    if (list->size == 0) {
        return -1;
    }
    if (element == NULL) {
        old_element = list->head;
        list->head = list->head->next;
        *data = old_element->data;

        /* 链表中只有一个元素时,删除后,head 和 tail 均指向 NULL */
        if (list_size(list) == 1) {
            lsit->tail = NULL
        }
    } else {
        /* element 是末尾结点时,返回 -1 */
        if (element->next == NULL) {
            return -1;
        }
        old_element = element->next;
        element->next = old_element->next;
        *data = old_element->data;

        /* element 下一结点为末尾结点时,删除后 element 为末尾结点 */
        if (element->next == NULL) {
            list->tail = element;
        }
    }
    /* 更改链表长度 */
    list->size--;
    return 0;
}

单链表应用:页帧管理(Frame Management)

  • 使用链表管理一个页表(page table),链表大小预设为页表的大小
  • 假定页表在系统启动的时候已经被初始化,并且页表中的元素数据 frame_number 已经映射到真正的物理内存
  • 链表是虚拟内存和物理内存的映射,页表的操作总是在头结点
  • 当需要申请一个真正的物理内存地址时,总是检查页表的大小,页表大小为 0 时即映射的内存已使用完;
  • 如果有可用的页表,alloc_frame 返回其页表号码,并释放其data指向的内存以便令程序可能使用
  • 释放页表时,重新为页表元素数据申请一个内存,如果没有可用内存,释放失败

页帧映射

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

/* 申请空闲页帧 */
int alloc_frame(List *frames)
{
    int frame_number, *data;

    if (list_size(frames) == 0) {
        /* 无可用物理内存 */
        return -1;
    } else {
        if (list_rem_next(frames, NULL, (void **)&data) != 0) {
            return -1;
        } else {
            /* 页表号是内存映射地址 */
            frame_number = *data;
            /* 释放该内存以及令程序使用 */
            free(data);
        }
    }
    return frmae_number;
}

int free_frame(List *frames, int frame_number)
{
    int *data;

    /* 重新申请一个内存来作页表的映射,避免程序申请页表时导致
       有空闲的页帧,实际却没有空闲的内存可用 */
    if ((data = (int *)malloc(sizeof(int))) == NULL) {
        return -1;
    }

    *data = frame_number;
    /* 将数据插入链表头结点 */
    if (list_ins_next(frames, NULL, data) != 0) {
        return -1;
    }
    return 0;
}
  • 双向链表(Doubly-Linked List)

双向链表

头文件

 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
/* dlist.h */
#ifndef DLIST_H
#define DLIST_H

/* 双向链表元素结构 */
typedef struct DListElmt_ {
    /* 指向存储的数据 */
    void *data;
    /* 指向前一结点 */
    struct DListElmt_ *prev;
    /* 指向后一个结点 */
    struct DListElmt_ *next;
}DListElmt;

/* 双向链表 */
typedef struct DList_ {
    /* 链表大小 */
    int size;
    int (*match)(const void *key1, const void *key2);
    /* 销毁时数据回调函数 */
    void (*destroy)(void *data);
    /* 头结点 */
    DListElmt *head;
    DListElmt *tail;
}DList;

/* 链表初始化 */
void dlist_init(DList *list, void (*destroy)(void *data));
/* 销毁链表 */
void destroy(DList *list);
/* 向element后插入一个结点,element为NULL时表示向空链表插入新结点 */
int dlist_ins_next(DList *list, DListElmt *element, const void *data);
/* 向element前插入一个结点,element为NULL时删除失败 */
inst dlist_ins_prev(DList *list, DListElmt *element, const void *data);
/* 由于有指向前一结点和后一结点的指针,所以双向链表可以直接删除指定结点 */
int dlist_remove(DList *list, DListElmt *element, void **data);
/* 返回链表大小 */
#define dlist_size(list) ((list)->size)
/* 返回链表头结点 */
#define dlist_head(list) ((list)->head)
/* 返回链表尾结点 */
#define dlist_tail(list) ((list)->tail)
/* 判断是否是头结点 */
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
/* 判断是否是尾结点 */
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
/* 返回结点指向数据 */
#define dlist_data(element) ((element)->data)
/* 返回结点的前一结点 */
#define dlist_prev(element) ((element)->prev)
/* 返回结点的后一结点 */
#define dlist_next(element) ((element)->next)

#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
 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
/* dlist.c */
#include <stdlib.h>
#include <string.h>
#include "dlist.h"

/* 初始化 */
void dlist_init(DList *list, void (*destroy)(void *data))
{
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL
    list->tail = NULL

    return;
}

/* 销毁 */
void dlist_destroy(DList *list)
{
    void *data;
    /* 删除所有结点 */
    while (dlist->size(list) > 0) {
        if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->destroy != NULL) {
            /* 调用数据回调函数 */
            list->destroy(data);
        }
    }
    memset(list, 0, size(DList));
    return;
}

/* 向后插入一结点 */
int dlist_ins_next(DList *list, DListElmt *element, const void *data)
{
    DListElmt *new_element;
    /* 为避免混淆, NULL 仅用向空链表插入元素 */
    if (element == NULL && dlist_size(list) != 0) {
        return -1;
    }
    /* 申请结点内存 */
    if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL) {
        return -1;
    }
    new_element->data = (void *)data;

    if (dlist_size(list) == 0) {
        /* 当链表为空时 */
        list->head = new_element;
        list->head->prev = NULL;
        list->head->next = NULL;
        list->tail = new_element;
    } else {
        /* 无论 element 情况如何, new_element 的 prev 和 next 指向不会变
        只会指向 element 和其后一结点 */
        new_element->next = element->next;
        new_element->prev = element;

        if (element->next == NULL) {
            /* 当链表中只有一个结点时, 新结点是末尾结点 */
            list->tail = new_element;
        } else {
            element->next->prev = new_element;
        }
        element->next = new_element;
    }
    list->size++;
    return 0;
}

/* 向结点前插入 */
int dlist_ins_prev(DList *list, DListElmt *element, const void *data)
{
    DListElmt *new_element;
    /* NULL 用作向空链表插入结点 */
    if (element == NULL && dlist_size(list) != 0) {
        return -1;
    }
    /* 申请结点内存 */
    if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL) {
        return -1;
    }
    new_element->data = data;

    if (dlist_size(list) == 0) {
        /* 空链表 */
        list->head = new_element;
        list->head->prev = NULL;
        list->head->next = NULL;
        list->tail = new_element;
    } else {
        /* 无论 element 情况如何, new_element 的 next 和 prev 指向不会变
        只会指向 element 和其前一结点 */
        new_element->next = element;
        new_element->prev = element->prev;

        if (element->prev == NULL) {
            /* element 是头结点时, 重新调整头结头指向 */
            list->head = new_element;
        } else {
            /* 非头结点时, 将前一结点的后结点指向 new_element */
            new_element->prev->next = new_element;
        }
        element->prev = new_element;
    }
    dlist->size++;
    return 0;
}

/* 删除结点 */
int dlist_remove(DList *list, DListElmt *element, void **data)
{
    /* 无法删除 NULL 或者空链表 */
    if (element == NULL || list_size(list) != 0) {
        return -1;
    }
    *data = element->data;

    if (list->head == element) {
        /* 删除头结点 */
        list->head = element->next;
        if (element->next == NULL) {
            /* 头结点也是末尾结点 */
            list->tail = NULL;
        } else {
            element->next->prev = NULL;
        }
    } else {
        element->prev->next = element->next;
        if (element->next == NULL) {
            /* element 是末尾结点 */
            list->tail = element->prev;
        } else {
            element->next->prev = element->prev;
        }
    }
    free(element);
    dlist->size--;
    return 0;
}
  • 循环链表(Circular Lists)

循环链表

 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
/* clist.h */
#ifndef CLIST_H
#define CLIST_H

#include <stdlib.h>

/* 结点定义 */
typedef struct CListElmt_ {
    /* 指向数据 */
    void *data;
    /* 指向下一结点 */
    struct CListElmt *next;
}CListElmt;

/* 链表定义 */
typedef struct CList_ {
    /* 链表大小 */
    int size;
    int (*match)(const void *key1, const void *key2);
    /* 链表销毁回调函数 */
    void (*destroy)(void *data);
    /* 头结点 */
    CListElmt *head;
}CList;
/* 初始化链表 */
void clist_init(CList *list, void (*destroy)(void *data));
/* 销毁链表 */
void clist_destroy(CList *list);
/* 向 element 后插入结点, 向空链表插入元素时, element 可以是任何值, 但避免混乱最好为 NULL */
int clist_ins_next(CList *list, CListElmt *element, const void *data);
/* 删除 element 后一结点, element 传入 NULL 返回-1 */
int clist_rem_next(CList *list, CListElmt *element, void **data);
/* 返回链表大小 */
#define clist_size(list) ((list)->size)
/* 返回头结点 */
#define clist_head(list) ((list)->head)
/* 返回结点数据 */
#define clist_data(element) ((element)->data)
/* 返回结点的下一结点 */
#define clist_next(element) ((element)->next)

#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
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
#include <stdlib.h>
#include <string.h>
#include "clist.h"

/* 初始化 */
void clist_init(CList *list, void (*destroy)(void *data))
{
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;

    return;
}

/* 销毁 */
void clist_destroy(CList *list)
{
    void *data;
    while (clist_size(list) > 0) {
        if (clist_rem_next(list, list->head, (void **)&data) == 0 && list->destroy != NULL) {
            list->destroy(data);
        }
    }
    memset(list, 0, sizeof(CList));
    return;
}

/* 插入结点 */
int clist_ins_next(CList *list, CListElmt *element, const void *data)
{
    CListElmt *new_element;
    if ((new_element = (CListElmt *)malloc(sizeof(CListElmt))) == NULL) {
        return -1;
    }
    new_element->data = (void *)data;

    if (list->size == 0) {
        /* 向空链表插入元素 */
        list->head = new_element;
        new_element->next = new_element;
    } else {
        new_element->next = element->next;
        element->next = new_element;
    }
    list->size++;
    return 0;
}

/* 删除结点 */
int clist_rem_next(CList *list, CListElmt *element, void **data)
{
    CListElmt *old_element;

    if (list_size(list) == 0 || element == NULL) {
        return -1;
    }

    *data = element->data;
    if (element->next == element) {
        /* 链表只有一个元素 */
        old_element = element;
        list->head = NULL;
    } else {
        old_element = element->next;
        element->next = old_element->next;
        if (list_head(list) == old_element) {
            list->head = old_element->next
        }
    }
    free(old_element);
    list->size--;
    return 0;
}