线性表的单链表存储

C 语言实现

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

typedef int tElem;
typedef struct List {
    tElem data;             // 数据域
    struct List * next;     // 指针域
} List, *pList;
typedef enum Status {
    ok = 1,Error = 0
} Status;


/*
 * 初始化
 * 步骤：
 *  为头结点申请一个内存空间。
 *  判断空间申请状态。
 *  让头结点的指针域指向 NULL。
*/
Status InitList(List * head)
{
    head = (pList) malloc(sizeof(List));
    if(head == NULL)
    {
        printf("空间申请失败！\n");
        return Error;
    }

    head->next = NULL;
    return ok;
}


/*
 * 获取线性表的长度
 * 步骤：
 *  定义一个计数器 count。
 *  定义一个临时变量 temp，初始值为头结点的下一个节点，因为计算链表长度时，是不计算头结点的，所以从头结点的下一个节点开始计数。
 *  遍历线性表，每遍历一次，计数器累加 1，同时让临时变量 temp 指向本身的下一个节点。
 *  最后输出 count 的值就是线性表当前的长度。
*/
Status ListEmpty(List * head)
{
    int count = 0;
    pList temp = head->next;
    while (temp != NULL)
    {
        count ++;
        temp = temp->next;
    }
    printf("线性表的长度为：%d\n",count);
}


/*
 * 头插入法插入一个元素
 * 步骤：
 *  判断头结点是否为空。
 *  定义一个临时变量 temp 并为其申请内存空间，用于存放插入的数据。
 *  令 temp 的数据域等于插入的数据 e。
 *  令 temp 的指针域指向头结点指针域指向的节点。
 *  最后，让头结点的指针域指向 temp。
 * 说明：
 *  利用头插入法插入的数据最后的顺序如下：
 *  初始化：head
 *  插入第一个元素 10：head -> 10 -> NULL
 *  插入第二个元素 20：head -> 20 -> 10 -> NULL
*/
Status ListHeadInsert(List * head,tElem e)
{
    if(head == NULL)
    {
        return Error;
    }

    pList temp = (pList) malloc(sizeof(List));
    temp->data = e;
    temp->next = head->next;
    head->next = temp;
    return ok;
}


/*
 * 尾插入法插入一个元素
 * 步骤：
 *  判断头结点是否为空。
 *  定义一个临时变量 item 用于遍历时接受线性表的每一个节点。
 *  定义一个临时变量 temp 并为其申请内存空间，用于存放插入的数据。
 *  令 item 等于头结点的下一个节点，因为在遍历时是从头结点的下一个节点开始的。
 *  令 temp 的数据域等于插入的数据 e。
 *  令 temp 的指针域指向 NULL。
 *  遍历线性表，当节点的指针域为 NULL 时，此时的 item 是离 head 最远的节点，也就是最后一个节点。
 *  最后令 item 的指针域指向 temp。
 * 说明：
 *  利用尾插入法插入的数据最后的顺序如下：
 *  初始化：head
 *  插入第一个数据 10：head -> 10 -> NULL
 *  插入第二个数据 20：head -> 10 -> 20 -> NULL
*/
Status ListTailInsert(List * head,tElem e)
{
    if(head == NULL)
    {
        return Error;
    }

    pList item = head->next;
    pList temp = (pList) malloc(sizeof(List));
    temp->data = e;
    temp->next = NULL;

    while (item->next != NULL)
    {
        item = item->next;
    }
    item->next = temp;
    return ok;
}


/*
 * 打印线性表
 * 步骤：
 *  定义一个计数器，用作节点的索引（可以不定义）
 *  定义一个临时变量 item，存入头结点的下一个节点，原因同上，打印时不打印头结点，从头结点的下一个节点开始打印。
 *  遍历线性表，当 item 的指针域为 NULL 时，item 已是线性表的最后一个元素了。
 *  循环体内对每个节点的数据与进行打印。
*/
    void ListTraverse(List * head)
{
    int count = 0;
    pList temp = head->next;
    while (temp != NULL)
    {
        count ++;
        printf("线性表的第 %d 个元素是：%d\n",count,temp->data);
        temp = temp->next;
    }
}


/*
 * 判断元素 e 是否在线性表中
 * 步骤：
 *  定义一个临时变量 temp 初始值给头结点的下一个节点
 *  遍历线性表，判断元素 e 是否在线性表中出现。若在线性表内，返回 1，否则返回 0。
*/
Status ListIsIn(List * head,tElem e)
{
    pList temp = head->next;
    while (temp != NULL)
    {
        if(temp->data == e)
        {
            return ok;
        }
        temp = temp->next;
    }
    return Error;
}

/*
 * 获取元素 e 前一个元素
 * 步骤：
 *  判断元素 e 是否在列表中。
 *  定义一个临时变量 temp，值为头结点的下一个节点。
 *  判断 temp 的数据域是否等于元素 e，若相等则表示 temp 是线性表的第一个元素，无前一个元素。
 *  遍历线性表，若 item 下一个节点的数据域等于 e，表示此时的 item 是元素 e 的前一个元素，打印 item 的数据域即可。
*/
Status PriorElem(List * head,tElem e)
{
    if(!ListIsIn(head,e))
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }

    pList temp = head->next;
    if(temp->data == e)
    {
        printf("元素 %d 是线性表的第一个元素，无前一个元素。\n");
        return Error;
    }

    while (temp->next != NULL)
    {
        if(temp->next->data == e)
        {
            printf("元素 %d 的前一个元素是：%d\n",e,temp->data);
            return ok;
        }
        temp = temp->next;
    }
}


/*
 * 获取元素 e 后一个元素
 * 步骤：
 *  判断元素 e 是否在列表中。
 *  定义一个临时变量 temp，值为头结点的下一个节点。
 *  遍历线性表，如果 temp 的数据域等于 e，则此时 temp 的指针域表示元素 e 的后一个节点，打印这个节点的数据域即可。
 *  若果 temp 的指针域为空，则 temp 表示线性表的最后一个元素，无后一个元素。
*/
Status NextElem(List * head,tElem e)
{
    if(!ListIsIn(head,e))
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }

    pList temp = head->next;
    while (temp->next != NULL)
    {
        if(temp->data == e)
        {
            printf("元素 %d 的后一个元素是：%d\n",e,temp->next->data);
            return ok;
        }
        temp = temp->next;
    }
    if(temp->next == NULL && temp->data == e)
    {
        printf("元素 %d 是线性表的最后一个元素，没有后一个元素。\n",e);
    }
}


/*
 * 删除元素 e
 * 步骤：
 *  判断元素 e 是否在列表中。
 *  定义一个临时变量 temp，值为头结点的下一个节点。
 *  遍历线性表，第一次循环是，若 temp 的数据域等于 e，则让头结点指向 temp 的下一个节点，这样就把 temp 这个节点挤出去了。
 *  若 temp 的下一个节点的数据域等于 e，说明此时的 temp 是元素 e 的前一个节点，让这个节点的指针域直接指向元素 e 所在节点的下一个节点即可。
*/
Status ListDelete(List * head,tElem e)
{
    if(!ListIsIn(head,e))
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }

    pList temp = head->next;
    while (temp != NULL)
    {
        if(temp->data == e)
        {
            head->next = temp->next;
            return ok;
        }
        if(temp->next->data == e)
        {
            temp->next = temp->next->next;
            return ok;
        }
        temp = temp->next;
    }
}


/*
 * 清空线性表
 * 步骤：
 *  直接让头结点的指针域指向空即可。
*/
void ClearList(List * head)
{
    head->next = NULL;
}


/*
 * 摧毁线性表
 * 步骤：
 *  直接释放头结点即可
*/
void DestroyList(List * head)
{
    free(head);
    printf("销毁成功！\n");
}

int main() {
    List head;

    // 初始化
    InitList(&head);

    // 统计线性表长度
    printf("初始化后：");
    ListEmpty(&head);
    printf("\n");

    // 头插入元素
    ListHeadInsert(&head,10);
    ListHeadInsert(&head,20);

    // 尾插入元素
    ListTailInsert(&head,30);
    ListTailInsert(&head,40);

    // 打印线性表
    ListTraverse(&head);
    printf("\n");

    // 获取元素 e 的前一个元素
    PriorElem(&head,10);
    PriorElem(&head,20);
    PriorElem(&head,50);
    printf("\n");

    // 获取元素 e 的后一个元素
    NextElem(&head,10);
    NextElem(&head,40);
    NextElem(&head,50);
    printf("\n");

    // 删除元素
    ListDelete(&head,50);
    ListDelete(&head,30);
    ListTraverse(&head);
    printf("\n");

    // 清空线性表
    ClearList(&head);
    printf("清空线性表后：");
    ListEmpty(&head);

    // 销毁线性表
    DestroyList(&head);

    return 0;
}

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

Java 实现

java

package Linear;

public class Demo02 {
    public static void main(String[] args) {
        ListNode head = new ListNode();

        // 头插
        head.HeadInsert(20);
        head.HeadInsert(10);

        // 尾插
        head.TailInsert(30);
        head.TailInsert(40);

        // 打印
        System.out.println("插入元素后：");
        head.printList();

        // 找前一节点
        head.PriorElem(10);

        // 找后一节点
        head.NextElem(10);

        // 删除元素
        head.DelItem(10);
        System.out.println("删除元素后：");
        head.printList();

        head.ClearList();
        System.out.println("清空线性表后：");
        head.printList();
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
        this.val = 0;
        this.next = null;
    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    // 头插元素
    public void HeadInsert(int e) {
        this.next = new ListNode(e, this.next);
    }

    // 尾插元素
    public void TailInsert(int e) {
        ListNode item = this.next;
        while (item.next != null) {
            item = item.next;
        }
        item.next = new ListNode(e);
    }

    // 打印线性表
    public void printList() {
        ListNode item = this.next;
        int count = 0;
        if (item == null) System.out.println("------ 线性表为空 ------");
        while (item != null) {
            count++;
            System.out.printf("\t线性表的第 %d 个元素是 %d\n", count, item.val);
            item = item.next;
        }
    }

    // 判断元素是否在线性表中
    public int WhetherExist(int e) {
        int state = 0;
        ListNode item = this.next;
        while (item != null) {
            if (item.val == e) {
                state = 1;
                break;
            }
            item = item.next;
        }
        return state;
    }

    // 获取指定元素的前一个元素
    public void PriorElem(int e) {
        if (this.WhetherExist(e) == 1) {
            if (this.next.val == e) {
                System.out.printf("元素 %d 是第一个元素，无前一元素\n", e);
            } else {
                ListNode item = this.next;
                while (item != null) {
                    if (item.next.val == e) break;
                    item = item.next;
                }
                System.out.printf("元素 %d 的前一个元素是 %d\n", e, item.val);
            }
        } else System.out.printf("元素 %d 不在线性表中\n", e);
    }

    // 获取指定元素的后一个元素
    public void NextElem(int e) {
        if (this.WhetherExist(e) == 1) {
            ListNode item = this.next;
            while (item != null) {
                if (item.val == e) break;
                item = item.next;
            }
            if (item.next == null) System.out.printf("元素 %d 是最后一个元素，无后一元素\n", e);
            else System.out.printf("元素 %d 的前后一个元素是 %d\n", e, item.next.val);
        } else System.out.printf("元素 %d 不在线性表中\n", e);
    }

    // 删除元素 e
    public void DelItem(int e) {
        if (this.WhetherExist(e) == 1) {
            ListNode item = this;
            while (item != null) {
                if (item.next.val == e) break;
                item = item.next;
            }
            item.next = item.next.next;
        } else System.out.printf("元素 %d 不在线性表中", e);
    }

    // 清空线性表
    public void ClearList() {
        this.next = null;
    }
}

JavaScript 实现

javascript

// 结构体的构造函数
function ListNode(val, next) {
    this.val = val || 0;
    this.next = next || null;
}

// 线性表变量(头节点)
let head;

/**
 * @description: 头插入法
 * @param {*} e 元素
 */
const HeadInsert = (e) => {
    let temp = new ListNode(e, head.next);
    head.next = temp;
}

/**
 * @description: 尾插入法
 * @param {*} e 元素
 */
const TailInsert = (e) => {
    let temp = new ListNode(e);
    let item = head;
    while (item.next) item = item.next;
    item.next = temp;
}

/**
 * @description: 遍历线性表
 */
const ErgodicList = () => {
    let count = 0;
    let item = head.next;
    while (item) {
        count++;
        console.log(`\t线性表的第 ${count} 个元素是 ${item.val}`);
        item = item.next;
    }
}

/**
 * @description: 判断元素是否在线性表中
 * @param {*} e 元素
 * @return {*} 状态 0-不存在，1-存在
 */
const WhetherExist = (e) => {
    let index = 0;
    let item = head.next;
    while (item) {
        if (item.val === e) {
            index = 1;
            break;
        }
        item = item.next;
    }
    return index;
}

/**
 * @description: 获取指定元素的前一个元素
 * @param {*} e 元素
 * @return {*} 前一个元素
 */
const PriorElem = (e) => {
    if (WhetherExist(e)) {
        let item = head.next;
        if (item.val === e) {
            console.log(`元素 ${e} 是线性表第一个元素，无前一个元素`);
            return;
        } else {
            while (item) {
                if (item.next.val === e) break;
                item = item.next;
            }
            return item.val;
        }
    } else {
        console.log(`元素 ${e} 不在线性表中`);
        return;
    }
}

/**
 * @description: 获取指定元素的后一个元素
 * @param {*} e 元素
 * @return {*} 后一个元素
 */
const NextElem = (e) => {
    if (WhetherExist(e)) {
        let item = head.next;
        while (item) {
            if (item.val === e) break;
            item = item.next;
        }
        if (item.next) return item.next.val;
        else {
            console.log(`元素 ${e} 是线性表最后一个元素，无后一个元素`);
            return;
        }
    } else {
        console.log(`元素 ${e} 不在线性表中`);
        return;
    }
}

/**
 * @description: 删除元素 e
 * @param {*} e 元素
 */
const DelItem = (e) => {
    if (WhetherExist(e)) {
        let item = head;
        while (item) {
            if (item.next.val === e) break;
            item = item.next;
        }
        item.next = item.next.next;
        return 1;
    } else {
        console.log(`元素 ${e} 不在线性表中`);
        return;
    }
}

/**
 * @description: 清空线性表
 */
const ClearList = () => {
    head.next = null;
}

const main = () => {
    head = new ListNode();
    HeadInsert(20);
    HeadInsert(10);
    console.log("头插入元素后：", head);

    TailInsert(30);
    TailInsert(40);
    console.log("尾插入元素后：", head);

    console.log("打印线性表：");
    ErgodicList();

    let eItem = 40;
    PriorElem(eItem) ? console.log(`元素 ${eItem} 的前一个元素是 ${PriorElem(eItem)}`) : '';
    NextElem(eItem) ? console.log(`元素 ${eItem} 的后一个元素是 ${NextElem(eItem)}`) : '';

    console.log(`删除元素 ${eItem} 后：`);
    DelItem(eItem) ? ErgodicList() : '';

    // ClearList();
    // console.log("清空元素后：",head);

}

main();

C 语言实现 ​

Java 实现 ​

JavaScript 实现 ​

C 语言实现

Java 实现

JavaScript 实现