单链表

单链表由各个元素之间通过一个指针彼此连结起来而组成。链表的每个结点包含两个元素：数据成员和一个指向下一个结点的next指针。通过next指针将结点链接起来形成一个链。最后一个元素的next指针设置为NULL，表示链表的尾端。要访问链表中某个元素，需要从链表头开始访问，通过next依次进行访问，最终找到要寻找的元素。单链表只能从头到尾进行遍历。

链表中得每个结点都是动态分配的（在C语言中使用malloc函数），这些结点的位置都是离散的分布在内存中，所以在维护各个结点之间的信息时候要特别小心，防止丢失链接信息，造成无法访问信息和内存泄露。链表结构如图：

img

结点结构：

1
2
3
4
5
/* define a structed for linked list elements.*/
typedef struct ListElmt_{
 void *data;
 struct ListElmt_ *next;
}ListElm;

链表结构：

1
2
3
4
5
6
7
typedef struct forward_list{
    int size;              //链表长度 
    int (*match)(const void* key,const void* key); //用来找到对应的key
    void (*destroy)(void* data); //释放内存的函数与分配内存的函数对于
    ListElm *head;     //头指针
    ListElm *tail;    //尾指针
}forward_list;

接口函数为：

1
void list_init(forward_list *List,void (*destroy)(void *data));

功能：初始化由参数list指定的链表，并指定对应的内存释放函数

时间复杂度 : O(1)

1
void list_destroy(forward_list *list);

功能：销毁由参数list指定的链表，由指定的destroy函数释放内存

时间复杂度: O(n),

1
int list_insert(forward_list *list,ListElm *elem,const void* data);

返回值：如果插入元素成功则返回0，否则返回-1

时间复杂度 : O(1)

功能：向参数list指定的链表中的elem结点后插入一个新的元素，新结点中元素的值是data

1
int list_remove(forward_list *list,ListElm* elem,void** data);

返回值：如果删除元素成功则返回0，否则返回-1,

时间复杂度: O(1)

功能：删除参数list指定的链表中的elem后的一个结点，并将移除结点的数据储存到data中

1
int list_size(const forward_list* list)

返回值：返回指定链表的结点个数

时间复杂度 ： O(1)

1
ListElm* getHead(forward_list const*list)

返回值：返回指定链表的头结点

时间复杂度 ： O(1)

1
ListElm* getTail(forward_list const*list)

返回值：返回指定链表的尾结点

时间复杂度 ： O(1)

1
bool isHead(const forward_list * list,const ListElm *Node)

返回值：若Node是list链表头结点返回true,负责返回false

时间复杂度 ： O(1)

1
bool IsTail(const forward_list * list,const ListElm *Node)

返回值：若Node是list链表尾结点返回true,负责返回false

时间复杂度 ： O(1)

1
void* list_data(const ListElm *Node)

返回值： 结点中保存的数据data

时间复杂度 ： O(1)

1
ListElm* list_next(const ListElm* Node)

返回值：指定结点的下一个结点

时间复杂度 ： O(1)

代码实现：

forward_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
//
// Created by JSL
//

#ifndef FORWARD_LIST_H
#define FORWARD_LIST_H
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
/* define a structed for linked list elements.*/
typedef struct ListElmt_{
    void *data;
    struct  ListElmt_ *next;
}ListElm;
/*define a structure fir linekd list*/
typedef struct forward_list{
    int size;              //the size of forward_list
    int (*match)(const void* key1,const void* key2);
    void (*destroy)(void* data);
    ListElm *head;
    ListElm *tail;
}forward_list;
/* public interface */
void list_init(forward_list *forwardList,void (*destroy)(void *data));
void list_destroy(forward_list *list);
int list_insert(forward_list *list,ListElm *elem,const void* data);
int list_remove(forward_list *list,ListElm* elem,void** data);
int list_size(const forward_list* list);
ListElm* getHead(forward_list const*list);
ListElm* getTail(forward_list const*list);
bool isHead(const forward_list * list,const ListElm *Node);
bool IsTail(const forward_list * list,const ListElm *Node);
void* list_data(const ListElm *Node);
ListElm* list_next(const ListElm* Node);

#endif //FORWARD_LIST_FORWARD_LIST_H

forward_list.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
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
//
// Created by JSL 
//

#include "forward_list.h"
void list_init(forward_list *list,void (*destroy)(void *data))
{
    /*initialize the list*/
    list->size = 0;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
}
void list_destroy(forward_list *list)
{
    void *data;
    /*destroy the list remove each element*/
    while(list_size(list)>0) {
        if (list_remove(list, NULL, (void **) &data) == 0 && list->destroy != NULL) {
            /*call the user-defined function to free dynamically allocated data*/
            list->destroy(data);
        }
    }
    memset(list,0,sizeof(list));
}
//insert into the element after elem
int list_insert(forward_list *list,ListElm *elem,const void* data)
{
    ListElm *new_elem;
    //allocate the storage for the element
    if ((new_elem = (ListElm *)malloc(sizeof(ListElm))) == NULL)
        return -1;
    //insert into list
    new_elem->data = (void*)data;
    if (elem == NULL)
    {
        if (list_size(list) == 0)
            list->tail = new_elem;
        new_elem->next = list->head;
        list->head = new_elem;
    }
    else
    {
        if (elem->next == NULL)
            list->tail = new_elem;
        new_elem->next = elem->next;
        elem->next = new_elem;
    }
    list->size ++;
    return 0;
}
//remove the element after the elem
int list_remove(forward_list *list,ListElm* elem,void** data)
{
    ListElm *old_elem;
    if (list_size(list) == 0){
        return -1;
    }
    if (elem == NULL)
    {
        *data = list->head->data;
        old_elem = list->head;
        list->head = list->head->next;
        if (list_size(list)==1)
            list->tail = NULL;
    }
    else
    {
        if (elem->next == NULL)
            return -1;
        *data = elem->next->data;
        old_elem = elem->next;
        elem->next = elem->next->next;
        if (elem->next == NULL)
            list->tail = elem;
    }
    free(old_elem);
    list->size --;
    return 0;
}

int list_size(const forward_list* list)
{
    return list->size;
}
ListElm* getHead(forward_list const*list)
{
    return list->head;
}
ListElm* getTail(forward_list const*list)
{
    return list->tail;
}
bool isHead(const forward_list * list,const ListElm *Node)
{
    return Node == list->head;
}
bool IsTail(const forward_list * list,const ListElm *Node)
{
    return Node == list->tail;
}
void* list_data(const ListElm *Node)
{
    return Node->data;
}
ListElm* list_next(const ListElm* Node)
{
    return Node->next;
}

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
#include "forward_list.h"
int main(int argc,char* argv[])
{
    forward_list *list;
    list = (forward_list *)malloc(sizeof(forward_list));
    list_init(list,free);
    //插入数据
    int test1 = 10;
    int test2 = 20;
    int test3 = 30;
   list_insert(list,NULL,(void*)&test1);
   list_insert(list,NULL,(void*)&test2);
   list_insert(list,NULL,(void*)&test3);

    ListElm *head = getHead(list);
    ListElm *tail = getTail(list);
    while (head!= tail)
    {
        printf("data : %d\t",*((int*)list_data(head)));
        head = list_next(head);
    }
    //打印tail
    printf("data : %d\t",*((int*)list_data(head)));
    head = list_next(head);
    printf("\nlist size : %d\n",list_size(list));
    list_destroy(list);
    return 0;
}
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

I am what I am