AHA'S BOOK

线性表是一组 按线性顺序排列的、具有相同特征的数据元素的有限序列，其中的数据元素之间存在一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（这句话只适用大部分线性表，而不是全部，如循环链表把最后一个数据元素的尾指针指向了首位结点）。线性表可以用于表示一串有序的数据，例如数组、链表、栈和队列等都是线性表的实现方式。

线性表中的「单链表」的实现，包括单链表的顺序存储（数组实现）和单链表的链式存储。这篇文章主要介绍单链表的顺序存储（数组实现）。

数组和链表的特点

首先介绍一下数组和链表的特点。

数组：创建数组时会在内存空间中划分出一块连续的内存，然后数据进入时会将数据按顺序存储在这块连续的内存中。因为数组在存储数据时是按顺序存储的，存储数据的内存也是连续的。所以，数组的特点就是寻址读取数据容易，插入和删除比较困难 / 费时。

链表：链表不同于数组，不会先划分出一块连续的内存，链表中的数据并不是连续的，链表在存储数据的内存中有两块区域，一块区域用来存储数据，一块区域用来记录下一个数据保存在哪里。虽然链表是线性表，但是并不会按线性的顺序存储数据。所以，链表在插入和删除时比较容易，在读取数据时比较麻烦。

这里的容易，即意味着时间复杂度低；麻烦，即意味着时间复杂度高。

链表的顺序存储（数组实现）

链表的 API 主要包括：

  • 创建并初始化链表
  • 查找链表中的元素
  • 向链表中插入元素
  • 删除链表中的元素
  • 获取链表的长度

链表结构定义

1
2
3
4
5
6
7
#define MAX_SIZE (100)

// 定义链表结构
typedef struct {
    int data[MAX_SIZE];  // 存储元素的数组
    int length;  // 链表的长度
} ArrayList;

这段代码定义了一个名为 ArrayList 的结构体，用来表示一个数组实现的链表。

该结构体包含两个成员变量：

  1. int data[MAX_SIZE]：一个整型数组，用来存储链表中的元素。
  2. int length：一个整型变量，表示链表的长度。

通过使用这个结构体，我们可以创建一个顺序存储结构的链表，其中元素按照顺序存储在数组中，并且可以通过索引来访问和修改链表中的元素。

创建并初始化链表

使用动态申请内存空间的方式创建并初始化一个链表。

1
2
3
4
5
6
7
ArrayList *initArrayList() {
    ArrayList *list = (ArrayList *)malloc(sizeof(ArrayList));
    memset(list->data, 0, MAX_SIZE * sizeof(int));
    list->length = 0;
    // printf("ArrayList size is %d bytes, data size is %d bytes.\n", sizeof(list), sizeof(list->data));
    return list;
}

查找链表中的元素

在链表中查找目标元素第一次出现时的索引，不存在则返回 -1。

1
2
3
4
5
6
7
8
9
int findArrayList(ArrayList *list, int target) {
    /* 查找成功的平均比较次数为(n+1)/2 */
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == target) {
            return i;  // 返回元素在链表中的索引
        }
    }
    return -1;  // 没有找到元素
}

为什么查找成功的平均比较次数为 n+12\frac {n+1}{2} 呢？

假设链表的长度为 nn，若元素在链表中存在，在最坏情况下，需要比较 nn 次才能找到元素；在最好情况下，只需要比较 11 次就能找到元素。因此，平均比较次数为 n+12\frac {n+1}{2}。

向链表中插入元素

向链表中指定的索引位置插入一个元素，可以在有效数据的最前面和最后面插入元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int insertArrayList(ArrayList *list, int index, int element) {
    if (list->length == MAX_SIZE) {
        printf("List is full! Unable to insert element.\n");
        return -1;
    } else if (index < 0 || index > list->length) {
        printf("Invalid index! Unable to insert element.\n");
        return -1;
    }

    for (int i = list->length - 1; i >= index; i--) {
        list->data[i + 1] = list->data[i];
    }
    list->data[index] = element;
    list->length++;  // 更新链表的长度
    return 0;
}

删除链表中的元素

删除链表中指定索引位置的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int deleteArrayList(ArrayList *list, int index) {
    if (list->length == 0) {
        printf("List is empty! Unable to delete element.\n");
        return -1;
    } else if (index < 0 || index >= list->length) {
        printf("Invalid index! Unable to delete element.\n");
        return -1;
    }

    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;  // 更新链表的长度
    return 0;
}

获取链表的长度

获取链表中有效数据元素的长度。

1
2
3
int getArrayListLength(ArrayList *list) {
    return list->length;
}

释放链表空间

1
2
3
void freeArrayList(ArrayList *list) {
    free(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
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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_SIZE (100)

// 定义链表结构
typedef struct {
    int data[MAX_SIZE];  // 存储元素的数组
    int length;  // 链表的长度
} ArrayList;

ArrayList *initArrayList() {
    ArrayList *list = (ArrayList *)malloc(sizeof(ArrayList));
    memset(list->data, 0, MAX_SIZE * sizeof(int));
    list->length = 0;
    printf("ArrayList size is %d bytes, data size is %d bytes.\n", sizeof(list), sizeof(list->data));
    return list;
}

int findArrayList(ArrayList *list, int target) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == target) {
            return i;  // 返回元素在链表中的索引
        }
    }
    return -1;  // 没有找到元素
}

int insertArrayList(ArrayList *list, int index, int element) {
    if (list->length == MAX_SIZE) {
        printf("List is full! Unable to insert element.\n");
        return -1;
    } else if (index < 0 || index > list->length) {
        printf("Invalid index! Unable to insert element.\n");
        return -1;
    }

    for (int i = list->length - 1; i >= index; i--) {
        list->data[i + 1] = list->data[i];
    }
    list->data[index] = element;
    list->length++;  // 更新链表的长度
    return 0;
}

int deleteArrayList(ArrayList *list, int index) {
    if (list->length == 0) {
        printf("List is empty! Unable to delete element.\n");
        return -1;
    } else if (index < 0 || index >= list->length) {
        printf("Invalid index! Unable to delete element.\n");
        return -1;
    }

    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;  // 更新链表的长度
    return 0;
}

int getArrayListLength(ArrayList *list) {
    return list->length;
}

void printArrayList(ArrayList *list) {
    for(int i = 0; i < list->length; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

void freeArrayList(ArrayList *list) {
    free(list);
}

int main() {
    ArrayList *list = initArrayList();

    insertArrayList(list, 0, 10);
    insertArrayList(list, 1, 20);
    insertArrayList(list, 2, 30);
    printArrayList(list);

    insertArrayList(list, 2, 40);
    insertArrayList(list, 0, 15);
    printArrayList(list);

    printf("Length of list: %d\n", getArrayListLength(list));

    int index = findArrayList(list, 20);
    if (index != -1) {
        printf("Element 20 is found at index %d\n", index);
    } else {
        printf("Element 20 is not found\n");
    }

    deleteArrayList(list, 1);
    printArrayList(list);

    printf("Length of list: %d\n", getArrayListLength(list));

    freeArrayList(list);

    return 0;
}

程序的输出结果为：

1
2
3
4
5
6
7
ArrayList size is 8 bytes, data size is 400 bytes.
10 20 30
15 10 20 40 30
Length of list: 5
Element 20 is found at index 2
15 20 40 30
Length of list: 4
aha
2023-10-07
数据结构 链表
Expand all Back to top Go to bottom Search in blogs
银河白
豆沙绿
杏仁黄
青草绿
秋叶褐