概述

线性表

线性表是由n(n≥0)个数据元素(结点) :a[0],a[1],a[2],…,a[n-1]组成的有限序列.

一个数据元素可以由若干个数据项组成.数据元素称为记录,而含有大量记录的线性表又称为文件.

线性表满足如下特点:

  • 存在一个唯一的没有前驱的(头)数据元素.(注意与具体实现中的"头结点"有别)
  • 存在一个唯一的没有后继的(尾)数据元素.
  • 除此之外,其他每一个数据元素均有一个直接前驱和一个直接后继数据元素.

说简单的,就是一堆数据排成单独的一列,这就是线性表.

链表

根据存储的方式不同,常规的线性表分为顺序表和链表.

所谓顺序表就是各个结点(元素)在内存中紧挨着存储,本质相当于一个数组:

image-20240306170538627

而所谓链表,其各个结点都是分散的,因此必须使用指针来进行"串联",形成一个链式结构,下图是其逻辑结构:

image-20240306165216730

但是一般情况下,各个结点的存储空间都是动态分配的,因此实际上他们的物理分布类似这样:

image-20240306170719517

即每个结点的位置是随机的,也因此各个结点间必须使用指针(指针域)(即图中的箭头)来进行链接,以保证能够正确访问和有序性.

链表的时间复杂度

由于每个节点是离散的,因此无法像顺序表(数组)那样使用"下标"进行"随机访问",只能从表的开始(表头)逐个向后查找,最终定位到指定的结点.

因此,可以知道,链表的各个基本操作的时间复杂度:

  • 插入结点到下标k(已定位到该位置): O(1)O(1)
  • 删除节点到下标k(已定位到该位置): O(1)O(1)
  • 访问(查找)某个节点: O(n)O(n)

实现

链表ADT需要实现如下基本的操作:

  • 创建一个空链表
  • 销毁一个链表
  • 从表头插入一个元素(头插)
  • 从表头删除一个元素
  • 从下标为i处插入一个元素
  • 删除下标为i的元素

使用C语言来实现该ADT.

ADT:抽象数据结构—解决代码的复用性—写好的轮子—拿来直接用就好.

linked_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
/*
 * @file: linked_list.h
 * @description: This is a head file for linked list ADT
 * @author: WAHAHA
 * @note: without head node
 * @Date: 2024-03-06 17:45:06
 * @LastEditTime: 2024-03-06 22:01:33
 * @FilePath: \data-structure\ADT_linked_list\linked_list.h
 */

#ifndef _LINKED_LIST_H_ // 宏保护,防止重复包含头文件
#define _LINKED_LIST_H_

 /* bool macro */
typedef int status; // 标准C语言没有bool类型,需要有一个平替
#define TRUE 1
#define FALSE 0

/* data type */
typedef int ElemType; // 数据元素类型

typedef struct list_node_s {
    ElemType data;
    struct list_node_s *next;
} list_node_t, **list_t; // 链表节点类型,链表类型

/* function declaration */
list_node_t *new_list(void); // 创建一个新的链表
status free_list(list_t); // 销毁链表

status list_insert_head(list_t, ElemType); // 头插法插入元素
status list_remove_head(list_t); // 头删除法删除元素

status list_insert_at(list_t,ElemType,int); // 在指定位置插入元素
status list_remove_at(list_t,int); // 删除指定位置的元素

#endif // _LINKED_LIST_H_

linked_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
/*
 * @file: linked_list.c
 * @description: Linked list implementation
 * @author: WAHAHA
 * @Date: 2024-03-06 17:45:25
 * @LastEditTime: 2024-03-06 22:57:58
 * @FilePath: \data-structure\ADT_linked_list\linked_list.c
 */

 /*
 typedef int ElemType; // 数据元素类型

 typedef struct list_node_s {
     ElemType data;
     struct list_node_s *next;
 } list_node_t, *list_t; // 链表节点类型,链表类型
  */


#include <linked_list.h>
#include <stdlib.h>

list_node_t *new_list(void)
{
    return NULL; // 改为仅有头指针
}

status free_list(list_t list)
{
    if (list == NULL)
        return FALSE;
    list_node_t *cur = *list, *temp = NULL;
    while (cur != NULL) {
        temp = cur;
        cur = cur->next;
        free(temp);
    }
    *list = NULL;
    return TRUE;
}

status list_insert_head(list_t list, ElemType value)
{
    if (list == NULL)
        return FALSE;
    // 构造结点
    list_node_t *new_node = (list_node_t *)malloc(sizeof(list_node_t));
    new_node->data = value;

    // 重定向指针
    new_node->next = *list;
    *list = new_node;
    return TRUE;
}

status list_remove_head(list_t list)
{
    list_node_t *temp = *list;
    *list = temp->next;
    free(temp);
    return TRUE;
}

status list_insert_at(list_t list, ElemType value, int index)
{
    if (list == NULL)
        return FALSE;

    // 插入到下标i处,就意味着pre要指向下标(i-1)的节点
    // pre初始是0,则意味着循环需要0,1,2,...,i-1 共i-1次
    list_node_t *pre = *list;
    for (int i = 0;i < index - 1;++i) {
        pre = pre->next;
    }
    // 此时pre指向结点i-1
    // 构造结点
    list_node_t *new_node = (list_node_t *)malloc(sizeof(list_node_t));
    new_node->data = value;
    // 插入到链表
    // 第一步
    new_node->next = pre->next;
    // 第二步
    pre->next = new_node;
    return TRUE;
}
status list_remove_at(list_t list, int index)
{
    if (list == NULL)
        return FALSE;
    list_node_t *pre = *list;
    // 遍历扫描,index-1次
    for (int i = 0;i < index - 1;++i) {
        pre = pre->next;
    }
    // 重定向指针
    list_node_t *temp = pre->next;
    pre->next = pre->next->next;
    // 释放内存
    free(temp);
    return TRUE;
}

test.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// test.c
#include <linked_list.h>

int main()
{
    list_node_t *head = new_list();
    int arr[] = { 1,2,3,4,5 };
    for (int i = 0;i < 5;++i) {
        list_insert_head(&head, arr[i]);
    }
    list_node_t *cur=head;
    for (int i = 0;i < 5;++i) {
        printf("[%d]:%d ",i,cur->data);
        cur=cur->next;
    }
    free_list(&head);
    return 0;
}