LV03-04-数据结构-线性表-顺序表操作

发表于 分类于 ， ， 本文字数： 7.1k 阅读时长 ≈ 26 分钟

本文主要是数据结构——顺序表的一些基础操作，如增删改查等的相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。

点击查看使用工具及版本
Windows windows11
Ubuntu Ubuntu16.04的64位版本
VMware® Workstation 16 Pro 16.2.3 build-19376536
SecureCRT Version 8.7.2 (x64 build 2214) - 正式版-2020年5月14日
开发板 正点原子 i.MX6ULL Linux阿尔法开发板
uboot NXP官方提供的uboot，NXP提供的版本为uboot-imx-rel_imx_4.1.15_2.1.0_ga(使用的uboot版本为U-Boot 2016.03)
linux内核 linux-4.15(NXP官方提供)
STM32开发板 正点原子战舰V3(STM32F103ZET6)
点击查看本文参考资料
参考方向 参考原文
------
点击查看相关文件下载
--- ---

这一部分主要是对顺序表各种操作的实现，例如顺序表的创建，插入，显示，删除，释放，去重等操作。

一、顺序表的创建

1.创建步骤

image-20220929161556161

【注意】

（1） L->last 的值代表了 data[N] 中最后一个有效数据的下标，后边的图会用箭头来指示，但是它并不是指针，若将 L->last 加上 1 ，就可以得到数组有效元素的个数。

（2）创建线性表的时候用到了 malloc 和 memset 两个函数，需要加上两个函数对应的头文件。

2.函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @Function   : seqlist_create
 * @brief      : 创建一个顺序表
 * @param arg  : none
 * @return     : seqlistlink 类型，返回创建的顺序表首地址
 * @Description:
 */
_seqlistlink seqlist_create(void)
{
    /* 0.相关变量定义 */
    _seqlistlink L; /* 定义一个结构体指针变量 L */
    /* 1. malloc 申请顺序表内存空间 */
    L = (_seqlistlink)malloc(sizeof(_seqlist)); /* stdlib.h 头文件中的函数 */
    /* 2. 判断是否申请成功 */
    if (L == NULL)
    {
        printf("[ERROR]sequence list malloc failed!\n");
        return L;
    }
    /* 3.申请的内存空间初始化 */
    memset(L, 0, sizeof(_seqlist)); /* string.h 头文件中的函数，数组元素全部赋值为0 */
    L->last = -1;                  /* 空表时为 -1 */
    return L;
}

二、顺序表的释放

1.释放步骤

image-20220929164701834

【注意】

（1）释放的时候直接释放顺序表结构体指针变量指向的内存空间即可。

（2）可以判断一下要释放的顺序表是否存在。

2.函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @Function   : seqlist_free
 * @brief      : 释放顺序表占用的内存空间
 * @param L    : _seqlistlink类型，表示要释放的顺序表的首地址
 * @return     : int类型，顺序表不存在返回-1,释放完成返回0
 * @Description: 
 */
int seqlist_free(_seqlistlink L)
{
	if (L == NULL)
		return -1;
	free(L);
	L = NULL;
	return 0;
}

三、顺序表的长度

1.求表长度步骤

image-20220929170123005

从上图可以看出，其实整个顺序表的长度是顺序表结构体成员 last 来决定的，它决定了顺序表中有效数据元素的个数，只要它是 -1，就代表顺序表中没有数据，即便是顺序表中的数据有一个值，但是我们依然认为这是一个空表。

【注意】为了使 last 成员可以和数组最后一个元素的下表对应，设置了初始的 last 成员为 -1，所以 last + 1 才是实际有效元素个数。

2.函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @Function   : seqlist_length
 * @brief      : 求顺序表长度
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回L->last+1,顺序表有效元素个数;返回-1,顺序表地址为NULL
 * @Description:
 */
int seqlist_length(_seqlistlink L)
{
    if (L == NULL)
        return -1;
    return (L->last + 1);
}

四、顺序表的空满

1.空满判定步骤

image-20220929185752607

【注意】顺序表 L 的空满由 L->last 成员决定，而非是顺序表数组成员中存储了多少个数据，

判断条件 说明
L->last = -1 认为顺序表为空
L->last = N - 1 认为顺序表为满

2.函数实现

2.1顺序表为空判定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @Function   : seqlist_empty
 * @brief      : 顺序表是否为空
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回1,表示顺序表为空;返回0,表示顺序表非空
 * @Description:
 */
int seqlist_empty(_seqlistlink L)
{
    if (L->last == -1)
        return 1;
    else
        return 0;
}

2.2顺序表为满判定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @Function   : seqlist_full
 * @brief      : 顺序表是否为满
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回1,表示顺序表为满;返回0,表示顺序表未满
 * @Description:
 */
int seqlist_full(_seqlistlink L)
{
    if (L->last == N - 1)
        return 1;
    else
        return 0;
}

五、顺序表的清空

1.清空步骤

image-20220930054050126

【注意】对于顺序表来说，里边是否存放了元素，存放了多少个元素是由顺序表中代表顺序表有效元素个数的 last 成员决定的。

判断条件 说明
L->last = -1 认为顺序表为空
L->last = N - 1 认为顺序表为满

所以，对于顺序表的清空，我们只需要将 L->last 赋值为 -1 ，就可以认为此顺序表已经清空。

2.函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @Function   : seqlist_clear
 * @brief      : 顺序表清空
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回-1,表示顺序表不存在，返回0,表示清空完成
 * @Description:
 */
int seqlist_clear(_seqlistlink L)
{
    if (L == NULL)
        return -1;

    memset(L, 0, sizeof(seqlist));
    L->last = -1;

    return 0;
}

六、顺序表数据插入

1.数据插入步骤

insert

如上图所示，我们分为头部插入，尾部插入和中间插入，分析过后，其实可以归结为一类，就是在指定位置插入数据，头部和尾部的时候是两种特殊性情况，但是处理方式就可以与中间插入的这种普遍情况一样。一般步骤如下：

image-20220930073755707

2.函数实现

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
/**
 * @Function   : seqlist_insert
 * @brief      : 顺序表数据按位置插入
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @param value：data_t 类型，表示要插入的数据
 * @param pos  ：int类型，表示要插入的位置, 有效区间为[0, L->last+1]
 * @return     : int类型，返回0,表示插入成功;返回-1,表示插入失败
 * @Description: 
 */
int seqlist_insert(_seqlistlink L, data_t value, int pos)
{
    int i = 0;
    /* 1. 判断顺序表是否已满 */
    if (L->last == N - 1)
    {
        printf("[WARN ]sequence list is full\n");
        return -1;
    }
    /* 2. 判断插入位置是否合法 [0, L->last+1]*/
    if (pos < 0 || pos > L->last + 1)
    {
        printf("[ERROR]pos is invalid!\n");
        return -1;
    }
    /* 3.移动插入位置后边的数据 */
    for (i = L->last; i >= pos; i--) /* L->last就代表了最后一个元素的下标 */
    {
        L->data[i + 1] = L->data[i]; /* pos下标后边的数据全部后移一个位置 */
    }
    /* 4.更新数据并更新顺序表长度 */
    L->data[pos] = value;
    L->last++;

    return 0;
}

七、顺序表数据删除

1.删除步骤

delect

有上图可知，我们删除顺序表指定位置数据的时候只需要将该位置后边所有元素前移一个位置即可，一般步骤如下：

image-20220930075917043

2.函数实现

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
/**
 * @Function   : seqlist_delete
 * @brief      : 删除顺序表指定位置元素
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @param pos  ：int类型，表示要删除的位置, 有效区间为[0, L->last]
 * @return     : int类型，返回0,表示删除成功;返回-1,表示删除失败
 * @Description:
 */
int seqlist_delete(_seqlistlink L, int pos)
{
    int i = 0;
    /* 1.判断顺序表是否为空 */
    if (L->last == -1)
    {
        printf("[WARN ]sequence list is empty!\n");
        return -1;
    }

    /* 2.判断 pos 是否合法，合法区间为 [0, L->last] */
    if (pos < 0 || pos > L->last)
    {
        printf("[ERROR]delete pos is invalid!\n");
        return -1;
    }

    /* 3.移动删除位置后的元素以填补空缺，涉及元素区间为 [pos+1, L->last] */
    for (i = pos + 1; i <= L->last; i++)
    {
        L->data[i - 1] = L->data[i];
    }

    /* 4.更新顺序表元素个数 */
    L->last--;

    return 0;
}

八、顺序表数据显示

1.数据显示步骤

image-20220930090451597

对于数据的显示，我们就像对数组遍历一样，遍历整个顺序表，然后打印出数据即可。

2.函数实现

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
/**
 * @Function   : seqlist_show
 * @brief      : 顺序表元素显示
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int类型，返回-1,表示顺序表不存在;返回0,表示显示完毕
 * @Description:
 */
int seqlist_show(_seqlistlink L)
{
    int i;
    /* 1. 判断顺序表是否存在 */
    if (L == NULL)
        return -1;
    /* 2. 判断顺序表是否为空 */
    if (L->last == -1)
    {
        printf("[WARN ]sequence list is empty!\n");
    }
    /* 3.开始遍历顺序表中所有元素，并打印 */
    printf("sequence list:");
    for (i = 0; i <= L->last; i++)
    {
        printf("%d ", L->data[i]);
    }
    puts(""); /* 自带换行符 */

    return 0;
}

九、顺序表数据查找

1.查找步骤

image-20220930091533839

对于顺序表中数据元素的查找，我们直接遍历整个顺序表，查看数据是否存在于顺序表中即可，若是有重复的数据，我们只返回首个出现的下标。

2.函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @Function   : seqlist_locate
 * @brief      : 在顺序表中查找指定数据位置（若有重复，则显示首次出现的位置）
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @param value：data_t类型，表示要查找的元素
 * @return     : int类型，返回-1,表示要查找的元素不存在或者顺序表不存在;返回非负数,表示要查找的数据的下标
 * @Description:
 */
int seqlist_locate(_seqlistlink L, data_t value)
{
    int i = 0;
    /* 1. 判断顺序表是否存在 */
    if (L == NULL)
        return -1;
    for (i = 0; i <= L->last; i++)
    {
        if (L->data[i] == value)
            return i;
    }

    return -1;
}

十、顺序表数据去重

1.数据去重步骤

delete_duplicate

【思路】

对于去重，我们这里使用的方式是从第二个数据开始（下标为 1 ），逐个与前边的数据相比较，若发现与前边的某个数据重复，则将该数据删除，也就是将当前数据后边的数据逐个左移，覆盖当前数据，然后重复比较，直至到顺序表结尾。

【注意】若有重复，原本 i+1 位置的元素补到第 i 个位置，此时 i 位置上的元素需要再进行比较，所以 i 不需要往后移；若没有重复，内层循环退出后，j 的值小于 0 ，只有在此种情况下 i 才需要往后移动。

2.函数实现

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
/**
 * @Function   : seqlist_delete_duplicate
 * @brief      : 在顺序表中删除重复元素，只保留首次出现的数据
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int类型，返回-1,表示顺序表不存在;返回0,表示去重完成
 * @Description:
 */
int seqlist_delete_duplicate(_seqlistlink L)
{
    int i = 0;
    int j = 0;

    if (L->last == 0)
        return -1;

    i = 1;
    /* i 从 1 开始，往后移动，第 i 个数依次与它前边的比较，相同的就直接把第 i 个位置元素删除 */
    while (i <= L->last)
    {
        j = i - 1;
        while (j >= 0) /* 逐个向前比较 */
        {
            if (L->data[i] == L->data[j]) /* 若有相同的，就删除这个位置的元素，并退出比较循环 */
            {
                seqlist_delete(L, i); /* 原本 i+1 位置的元素补到第 i 个位置 */
                break;
            }
            else /* 若没有相同的，继续向前比较 */
                j--;
        }
        /* 若有重复，原本 i+1 位置的元素补到第 i 个位置，此时 i 位置上的元素需要再进行比较，所以 i 不需要往后移
           若没有重复，上边循环退出后，j 的值小于 0，只有在此种情况下才需要往后移动。 */
        if (j < 0)
            i++;
    }

    return 0;
}

十一、顺序表数据合并

1.数据合并步骤

image-20221010084834683
  • （1）在 L1 中查找 L2 中的每个数据；
  • （2）若 L1 中已有，则继续下一个的查找，若 L1 中没有，则将此数据插入到 L1 后边。

2.函数实现

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
/**
 * @Function   : seqlist_merge
 * @brief      : 求两个顺序表并集，保持第二个顺序表不变
 * @param L1   ：_seqlistlink类型，表示顺序表1地址
 * @param L2   ：_seqlistlink类型，表示顺序表2地址
 * @return     : int类型，返回-1,表示合并失败;返回0,表示合并完成
 * @Description:
 */
int seqlist_merge(_seqlistlink L1, _seqlistlink L2)
{
    int i = 0;
    int ret = 0;

    while (i <= L2->last)
    {
        ret = seqlist_locate(L1, L2->data[i]);
        /* L1中无该元素，才插入该元素 */
        if (ret == -1)
        {
            if (seqlist_insert(L1, L2->data[i], L1->last + 1) == -1)
                return -1;
        }

        i++;
    }

    return 0;
}

十二、完整程序

1. seqlist.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
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
/** =====================================================
 * Copyright © hk. 2022-2025. All rights reserved.
 * File name  : seqlist.c
 * Author     : qidaink
 * Date       : 2022-09-29
 * Version    :
 * Description:
 * Others     :
 * Log        :
 * ======================================================
 */
#include "seqlist.h"

/**
 * @Function   : seqlist_create
 * @brief      : 创建一个顺序表
 * @param arg  : none
 * @return     : seqlistlink 类型，返回创建的顺序表首地址
 * @Description:
 */
_seqlistlink seqlist_create(void)
{
    /* 0.相关变量定义 */
    _seqlistlink L; /* 定义一个结构体指针变量 L */
    /* 1. malloc 申请顺序表内存空间 */
    L = (_seqlistlink)malloc(sizeof(_seqlist)); /* stdlib.h 头文件中的函数 */
    /* 2. 判断是否申请成功 */
    if (L == NULL)
    {
        printf("[ERROR]sequence list malloc failed!\n");
        return L;
    }
    /* 3.申请的内存空间初始化 */
    memset(L, 0, sizeof(_seqlist)); /* string.h 头文件中的函数，数组元素全部赋值为0 */
    L->last = -1;                   /* 空表时为 -1 */
    return L;
}
/**
 * @Function   : seqlist_free
 * @brief      : 释放顺序表占用的内存空间
 * @param L    : _seqlistlink类型，表示要释放的顺序表的首地址
 * @return     : int类型，顺序表不存在返回-1,释放完成返回0
 * @Description:
 */
int seqlist_free(_seqlistlink L)
{
    if (L == NULL)
        return -1;
    free(L);
    L = NULL;
    return 0;
}
/**
 * @Function   : seqlist_length
 * @brief      : 求顺序表长度
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回L->last+1,顺序表有效元素个数;返回-1,顺序表地址为NULL
 * @Description:
 */
int seqlist_length(_seqlistlink L)
{
    if (L == NULL)
        return -1;
    return (L->last + 1);
}

/**
 * @Function   : seqlist_empty
 * @brief      : 顺序表是否为空
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回1,表示顺序表为空;返回0,表示顺序表非空
 * @Description:
 */
int seqlist_empty(_seqlistlink L)
{
    if (L->last == -1)
        return 1;
    else
        return 0;
}

/**
 * @Function   : seqlist_full
 * @brief      : 顺序表是否为满
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回1,表示顺序表为满;返回0,表示顺序表未满
 * @Description:
 */
int seqlist_full(_seqlistlink L)
{
    if (L->last == N - 1)
        return 1;
    else
        return 0;
}

/**
 * @Function   : seqlist_clear
 * @brief      : 顺序表清空
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int 类型，返回-1,表示顺序表不存在，返回0,表示清空完成
 * @Description:
 */
int seqlist_clear(_seqlistlink L)
{
    if (L == NULL)
        return -1;

    memset(L, 0, sizeof(_seqlist));
    L->last = -1;

    return 0;
}
/**
 * @Function   : seqlist_insert
 * @brief      : 顺序表数据按位置插入
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @param value：data_t 类型，表示要插入的数据
 * @param pos  ：int类型，表示要插入的位置, 有效区间为[0, L->last+1]
 * @return     : int类型，返回0,表示插入成功;返回-1,表示插入失败
 * @Description:
 */
int seqlist_insert(_seqlistlink L, data_t value, int pos)
{
    int i = 0;
    /* 1. 判断顺序表是否已满 */
    if (L->last == N - 1)
    {
        printf("[WARN ]sequence list is full\n");
        return -1;
    }
    /* 2. 判断插入位置是否合法 [0, L->last+1]*/
    if (pos < 0 || pos > L->last + 1)
    {
        printf("[ERROR]pos is invalid!\n");
        return -1;
    }
    /* 3.移动插入位置后边的数据 */
    for (i = L->last; i >= pos; i--) /* L->last就代表了最后一个元素的下标 */
    {
        L->data[i + 1] = L->data[i]; /* pos下标后边的数据全部后移一个位置 */
    }
    /* 4.更新数据并更新顺序表长度 */
    L->data[pos] = value;
    L->last++;

    return 0;
}

/**
 * @Function   : seqlist_delete
 * @brief      : 删除顺序表指定位置元素
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @param pos  ：int类型，表示要删除的位置, 有效区间为[0, L->last]
 * @return     : int类型，返回0,表示删除成功;返回-1,表示删除失败
 * @Description:
 */
int seqlist_delete(_seqlistlink L, int pos)
{
    int i = 0;
    /* 1.判断顺序表是否为空 */
    if (L->last == -1)
    {
        printf("[WARN ]sequence list is empty!\n");
        return -1;
    }

    /* 2.判断 pos 是否合法，合法区间为 [0, L->last] */
    if (pos < 0 || pos > L->last)
    {
        printf("[ERROR]delete pos is invalid!\n");
        return -1;
    }

    /* 3.移动删除位置后的元素以填补空缺，涉及元素区间为 [pos+1, L->last] */
    for (i = pos + 1; i <= L->last; i++)
    {
        L->data[i - 1] = L->data[i];
    }

    /* 4.更新顺序表元素个数 */
    L->last--;

    return 0;
}

/**
 * @Function   : seqlist_show
 * @brief      : 顺序表元素显示
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int类型，返回-1,表示顺序表不存在;返回0,表示显示完毕
 * @Description:
 */
int seqlist_show(_seqlistlink L)
{
    int i;
    /* 1. 判断顺序表是否存在 */
    if (L == NULL)
        return -1;
    /* 2. 判断顺序表是否为空 */
    if (L->last == -1)
    {
        printf("[WARN ]sequence list is empty!\n");
    }
    /* 3.开始遍历顺序表中所有元素，并打印 */
    printf("sequence list:");
    for (i = 0; i <= L->last; i++)
    {
        printf("%d ", L->data[i]);
    }
    puts(""); /* 自带换行符 */

    return 0;
}

/**
 * @Function   : seqlist_locate
 * @brief      : 在顺序表中查找指定数据位置（若有重复，则显示首次出现的位置）
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @param value：data_t类型，表示要查找的元素
 * @return     : int类型，返回-1,表示要查找的元素不存在或者顺序表不存在;返回非负数,表示要查找的数据的下标
 * @Description:
 */
int seqlist_locate(_seqlistlink L, data_t value)
{
    int i = 0;
    /* 1. 判断顺序表是否存在 */
    if (L == NULL)
        return -1;
    for (i = 0; i <= L->last; i++)
    {
        if (L->data[i] == value)
            return i;
    }

    return -1;
}

/**
 * @Function   : seqlist_delete_duplicate
 * @brief      : 在顺序表中删除重复元素，只保留首次出现的数据
 * @param L    : _seqlistlink类型，表示顺序表的首地址
 * @return     : int类型，返回-1,表示顺序表不存在;返回0,表示去重完成
 * @Description:
 */
int seqlist_delete_duplicate(_seqlistlink L)
{
    int i = 0;
    int j = 0;

    if (L->last == 0)
        return -1;

    i = 1;
    /* i 从 1 开始，往后移动，第 i 个数依次与它前边的比较，相同的就直接把第 i 个位置元素删除 */
    while (i <= L->last)
    {
        j = i - 1;
        while (j >= 0) /* 逐个向前比较 */
        {
            if (L->data[i] == L->data[j]) /* 若有相同的，就删除这个位置的元素，并退出比较循环 */
            {
                seqlist_delete(L, i); /* 原本 i+1 位置的元素补到第 i 个位置 */
                break;
            }
            else /* 若没有相同的，继续向前比较 */
                j--;
        }
        /* 若有重复，原本 i+1 位置的元素补到第 i 个位置，此时 i 位置上的元素需要再进行比较，所以 i 不需要往后移
           若没有重复，上边循环退出后，j 的值小于 0，只有在此种情况下才需要往后移动。 */
        if (j < 0)
            i++;
    }

    return 0;
}

/**
 * @Function   : seqlist_merge
 * @brief      : 求两个顺序表并集，保持第二个顺序表不变
 * @param L1   ：_seqlistlink类型，表示顺序表1地址
 * @param L2   ：_seqlistlink类型，表示顺序表2地址
 * @return     : int类型，返回-1,表示合并失败;返回0,表示合并完成
 * @Description:
 */
int seqlist_merge(_seqlistlink L1, _seqlistlink L2)
{
    int i = 0;
    int ret = 0;

    while (i <= L2->last)
    {
        ret = seqlist_locate(L1, L2->data[i]);
        /* L1中无该元素，才插入该元素 */
        if (ret == -1)
        {
            if (seqlist_insert(L1, L2->data[i], L1->last + 1) == -1)
                return -1;
        }

        i++;
    }

    return 0;
}

2. seqlist.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
38
39
40
41
42
43
44
45
46
/** =====================================================
 * Copyright © hk. 2022-2025. All rights reserved.
 * File name  : seqlist.h
 * Author     : qidaink
 * Date       : 2022-09-29
 * Version    :
 * Description:
 * Others     :
 * Log        :
 * ======================================================
 */
#ifndef __SEQLIST_H__
#define __SEQLIST_H__

/* 头文件 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int data_t;

#define N 128

typedef struct __seqlist
{
    data_t data[N];
    int last;
} _seqlist, *_seqlistlink;

/* 函数声明 */

_seqlistlink seqlist_create(void);                         /* 创建一个顺序表 */
int seqlist_free(_seqlistlink L);                          /* 释放顺序表占用的内存空间 */
int seqlist_length(_seqlistlink L);                        /* 求顺序表长度 */
int seqlist_empty(_seqlistlink L);                         /* 顺序表是否为空 */
int seqlist_full(_seqlistlink L);                          /* 顺序表是否为满 */
int seqlist_clear(_seqlistlink L);                         /* 顺序表清空 */
int seqlist_insert(_seqlistlink L, data_t value, int pos); /* 顺序表数据按位置插入 */
int seqlist_delete(_seqlistlink L, int pos);               /* 删除顺序表指定位置元素 */
int seqlist_show(_seqlistlink L);                          /* 顺序表元素显示 */
int seqlist_locate(_seqlistlink L, data_t value);          /* 在顺序表中查找指定数据位置（若有重复，则显示首次出现的位置） */
int seqlist_delete_duplicate(_seqlistlink L);              /* 在顺序表中删除重复元素，只保留首次出现的数据 */
int seqlist_merge(_seqlistlink L1, _seqlistlink L2);       /* 求两个顺序表并集，保持第二个顺序表不变 */

#endif

3. Makefile

点击查看详情 
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
##============================================================================#
# Copyright © hk. 2022-2025. All rights reserved.
# File name  : Makefile
# Author     : qidaink
# Date       : 2022-09-29
# Version    : 
# Description: 
# Others     : 
# Log        : 
##============================================================================#
##

TARGET          := main
#============================================================================#
## 工具设置
# 设置交叉编译器名称
CROSS_COMPILE   :=
# 设置交叉编译器
CC              := $(CROSS_COMPILE)gcc
# 编译选项
CFLAGS          += -g -Wall
#============================================================================#
## 目录路径设置
# 头文件路径设置(.h)
INCDIRS 		:= .

# 源文件路径设置(.S .C)
SRCDIRS			:= .

# 生成的中间 .o 文件的位置
OBJDIRS         := .
#============================================================================#
# 生成编译器的 -I dir_path 参数 
INCLUDE			:= $(patsubst %, -I %, $(INCDIRS))

# 获取所有的 .C 文件名称(包含路径)
CFILES			:= $(foreach dir, $(SRCDIRS), $(wildcard $(dir)/*.c))

# 获取所有的 .C 文件名称(不包含路径)
CFILENDIR		:= $(notdir  $(CFILES))

# 指定所有的 .C 生成的 .o 文件名(包含将要存放的路径)
COBJS			:= $(patsubst %, $(OBJDIRS)/%, $(CFILENDIR:.c=.o))

# 将所有要生成的 .o 文件合并到一个变量中(都包含路径)
OBJS			:= $(COBJS)

# 设置源文件路径
VPATH			:= $(SRCDIRS)

#============================================================================#			
# 生成目标文件	   
$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) $^ -o $(TARGET)

# 隐含规则推导相关中间文件
$(COBJS) : $(OBJDIRS)/%.o : %.c
	$(CC) $(CFLAGS) -c $(INCLUDE) $<  -o $@ 
	
#============================================================================#	
.PHONY: clean clean_o
# 删除所有编译链接生成的文件命令
clean: clean_o
	@rm -vf $(TARGET)

# 删除所有的 .o 文件命令
clean_o:
	@rm -vf $(COBJS)

printf:
	@echo "CFLAGS    = $(CFLAGS)"
	@echo "INCDIRS   = $(INCDIRS)"
	@echo "SRCDIRS   = $(SRCDIRS)"
	@echo "INCLUDE   = $(INCLUDE)"
	@echo "CFILES    = $(CFILES)"
	@echo "CFILENDIR = $(CFILENDIR)"
	@echo "COBJS     = $(COBJS)"
	@echo "OBJS      = $(OBJS)"
	@echo "VPATH     = $(VPATH)"

4. 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
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
#include <stdio.h>
#include "seqlist.h"

/* 测试函数实现 */
void test_seqlist_insert()
{
	_seqlistlink L;

	L = seqlist_create();
	if (L == NULL) return;

	seqlist_insert(L, 1, 0);
	seqlist_insert(L, 2, 1);
	seqlist_insert(L, 3, 2);
	seqlist_insert(L, 4, 2);
	seqlist_insert(L, 5, 2);

	seqlist_show(L);
	seqlist_free(L);
}

void test_seqlist_clear()
{
	_seqlistlink L;

	L = seqlist_create();
	if (L == NULL) return;

	seqlist_insert(L, 1, 0);
	seqlist_insert(L, 2, 0);
	seqlist_insert(L, 3, 0);

	seqlist_show(L);
	seqlist_clear(L);
	seqlist_show(L);

	seqlist_free(L);
}

void test_selist_delete()
{
	_seqlistlink L;

	L = seqlist_create();
	if (L == NULL) return;
	seqlist_insert(L, 1, 0);
	seqlist_insert(L, 2, 0);
	seqlist_insert(L, 3, 0);
	seqlist_insert(L, 1, 0);

	seqlist_show(L);
	seqlist_delete(L, 1);
	seqlist_show(L);
	seqlist_delete(L, 5);
	seqlist_show(L);

	seqlist_free(L);
}

void test_seqlist_empty()
{
	_seqlistlink L;

	L = seqlist_create();
	if (L == NULL) return;
	printf("list_empty(L) = %d\n", seqlist_empty(L));
	seqlist_insert(L, 1, 0);
	seqlist_insert(L, 2, 0);
	seqlist_show(L);
	printf("list_empty(L) = %d\n", seqlist_empty(L));

	seqlist_free(L);
}

void test_seqlist_length()
{
	_seqlistlink L;

	L = seqlist_create();
	if (L == NULL) return;
	printf("seqlist_length(L) = %d\n", seqlist_length(L));
	seqlist_insert(L, 1, 0);
	seqlist_insert(L, 2, 0);
	seqlist_show(L);
	printf("seqlist_length(L) = %d\n", seqlist_length(L));

	seqlist_free(L);
}

void test_seqlist_locate()
{
	_seqlistlink L;

	L = seqlist_create();
	if (L == NULL) return;
	seqlist_insert(L, 1, 0);
	seqlist_insert(L, 2, 0);
	seqlist_insert(L, 3, 0);
	seqlist_insert(L, 1, 0);
	seqlist_show(L);
	printf("list_locate(L, 1) = %d\n", seqlist_locate(L, 1));
	printf("list_locate(L, 5) = %d\n", seqlist_locate(L, 5));

	seqlist_free(L);
}

void test_seqlist_delete_duplicate()
{
	_seqlistlink L;
	L = seqlist_create();
	if (L == NULL) return;

	seqlist_insert(L, 1, 0);
	seqlist_insert(L, 1, 1);
	seqlist_insert(L, 1, 2);
	seqlist_insert(L, 2, 3);
	seqlist_insert(L, 3, 4);
	seqlist_insert(L, 4, 5);
	seqlist_insert(L, 4, 6);
	seqlist_insert(L, 5, 7);
	seqlist_insert(L, 6, 8);

	seqlist_show(L);
	seqlist_delete_duplicate(L);
	seqlist_show(L);

	seqlist_free(L);
}

void test_seqlist_merge()
{
	_seqlistlink L1;
	_seqlistlink L2;

	L1 = seqlist_create();
	L2 = seqlist_create();
	if (L1 == NULL|| L2 == NULL) return;
	seqlist_insert(L1, 1, 0);
	seqlist_insert(L1, 2, 1);
	seqlist_insert(L1, 3, 2);
	seqlist_insert(L1, 4, 3);

	seqlist_insert(L2, 4, 0);
	seqlist_insert(L2, 5, 1);
	seqlist_insert(L2, 6, 2);
	seqlist_insert(L2, 7, 3);

	seqlist_show(L1);
	seqlist_show(L2);
	printf("====================\n");
	seqlist_merge(L1, L2);
	seqlist_show(L1);
	seqlist_show(L2);

	seqlist_free(L1);
	seqlist_free(L2);
}

int main(int argc, char *argv[])
{
	// test_seqlist_insert();
	// test_seqlist_clear();
	// test_selist_delete();
	// test_seqlist_empty();
	// test_seqlist_length();
	// test_seqlist_locate();
	// test_seqlist_delete_duplicate();
	test_seqlist_merge();
    return 0;
}