单链表

为什么单链表是数据结构的基础？

因为要模拟自然数集合的性质，一个前驱一个后继。
是在模拟穷举这个过程。

吐槽

看到有些书解释为什么要弄出个单链表，说因为需要容器，单链表是个容器。这种解释真是很让人无语，容器多了去了，数组不是个容器？

每个编程语言都有自己内置的容器，JavaScript内置数组和哈希表，python内置列表字典元组啥的，我还是喜欢PHP的内置容器，一个哈希表解决所有。

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

//状态码
typedef int Status;

//节点
typedef struct {
    void *data;
    struct Node *next;
} Node;

//链表
typedef Node *Link_list;

/**
 * 初始化链表
 * @param L 
 * @return Status
 */
Status init_link_list(Link_list *L);

/**
 * 修改节点数据
 * @param L 
 * @param i 
 * @param elm 
 * @return Status
 */
Status update_elem(Link_list L, int i, void **elm);

/**
 * 查找
 * @param L
 * @param e
 * @return Node
 */
Node *find_elem(Link_list *L, void *elm);

/**
 * 插入
 * @param L
 * @param i
 * @param elm
 * @return
 */
Status insert_list(Link_list *L, int i, void *elm);

/**
 * 删除
 * @param L
 * @param i
 * @return
 */
Status delete_node(Link_list *L, int i);

/**
 * 创建链表
 * @param L
 * @param n
 * @return
 */
Status create_list(Link_list *L, int n);

/* code */
Status init_link_list(Link_list *L) {
    (*L) = (Link_list) malloc(sizeof(Node));
    (*L)->next = NULL;
    return 0;
}

Status update_elem(Link_list L, int i, void **elm) {
    Link_list ptr = L->next;
    int j = 1;

    //遍历
    while (ptr && j < i) {
        j++;
        ptr = ptr->next;
    }

    if (!ptr || j > i) {
        return -1;
    }
    //修改
    *elm = ptr->data;
    return 0;
}

Node *find_elem(Link_list *L, void *elm) {
    Link_list ptr = (*L)->next;
    //遍历
    while (ptr && ptr->data != elm) {
        ptr = ptr->next;
    }
    return ptr;
}

Status insert_list(Link_list *L, int i, void *elm) {
    Link_list p = *L;
    int j = 0;

    while (p && (j < i - 1)) {
        p = p->next;
        j++;
    }

    if (!p || j > i - 1) {
        return -1;
    }

    Link_list node = (Link_list) malloc(sizeof(Node));

    node->data = elm;
    node->next = p->next;
    p->next = node;

    return 0;
}

Status delete_node(Link_list *L, int i) {
    Link_list p = *L;
    int j = 0;

    while ((p->next) && (j < i - 1)) {
        p = p->next;
        j++;
    }

    if (!p || j > i - 1) {
        return -1;
    }

    Link_list node = p->next;

    p->next = node->next;
    free(node);

    return 0;
}

Status create_list(Link_list *L, int n) {
    *L = (Link_list) malloc(sizeof(Node));
    (*L)->next = NULL;

    for (int i = 0; i < n; i++) {
        void *tmp;
        Link_list q;

        if (scanf("%p", &tmp) == 1) {
            Link_list node = (Link_list) malloc(sizeof(Node));
            node->data = tmp; // 录入数据
            q->next = node;   // 后插节点
            q = q->next;   // 指针后移
        } else
            return -1;
    }
}