前言——线性表

线性表（linearlist）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表有：顺序表、链表、栈、队列、字符串… 。在数据结构中，线性表是一种最基本、最常用的数据结构。我们在实际生活中看到的许多列表（例如十二星座列表）都是线性表的一种体现。

一、 顺序表概述

顺序表（Sequential List） 是线性表（Linear List）最基础的存储结构，采用连续内存空间依次存储数据元素。作为数据结构学习的入门基石，理解顺序表对掌握更复杂结构至关重要。

而数组则是一种物理上连续存储数据的结构，顺序表正是利用数组实现的线性表。

二、存储结构

• 物理连续：元素存储在地址连续的内存单元中
• 逻辑相邻：元素的逻辑顺序与物理顺序严格一致
• 随机访问：支持通过下标直接访问元素（时间复杂度$O(1)$）

顺序表作为线性表的最基础存储结构，在数据结构学习中具有重要地位。接下来，我们将通过实际代码来逐步实现顺序表的相关操作。

三、基础操作的实现

1. 项目结构说明

为了实现顺序表的各种操作，我们将创建以下文件：

SeqList.h（头文件）	声明数据结构及各个操作函数的接口
SeqList.c（源文件）	提供顺序表各个函数的具体实现
test.c（源文件）	通过调用各个接口验证顺序表的正确性

2.静态顺序表

(1) 静态顺序表的结构定义

/在 SeqList.h 中，我们可以定义一个固定大小的顺序表结构

#define N 100
typedef int SLDataType;  // 方便我们修改顺序表中存储的数据类型

// 静态顺序表的定义
typedef struct SeqList {
    int a[N];
    int size; // 当前顺序表中存储的数据个数
} SL;

(2) 静态顺序表的缺陷

不难发现，静态顺序表采用固定大小的数组来存储数据，存在以下两个主要缺点：

空间浪费：如果预分配的数组空间过大，会造成内存浪费；

容量受限：如果预分配空间过小，则在数据量增多时无法满足需求。

静态顺序表虽然实现简单，但由于无法动态扩展，因此在实际应用中往往不够灵活。接下来将介绍动态顺序表，它能够根据需要动态扩容，解决静态顺序表的缺陷。

3. 动态顺序表

动态顺序表使用动态分配的内存来存储数据，不仅保留了数组的连续性，还能根据数据量自动扩容，极大地提高了灵活性。下面给出动态顺序表的完整实现示例。

SeqList.h

在头文件中，我们定义了动态顺序表的结构体和各个接口函数的声明

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>  // 这些是之后实现函数将用到的头文件

typedef int SLDataType;

// 动态顺序表的结构定义
typedef struct SeqList {
	SLDataType* a;   // 动态分配的数组，用于存储数据
	int size;        // 当前顺序表中存储的数据个数
	int capacity;    // 数组的实际能够存储的数据个数
} SL;

// 动态顺序表的相关操作接口

// 初始化
void SeqListInit(SL* ps);
// 尾部插入
void SeqListPushBack(SL* ps, SLDataType x);
// 尾部删除
void SeqListPopBack(SL* ps);
// 头部插入
void SeqListPushFront(SL* ps, SLDataType x);
// 头部删除
void SeqListPopFront(SL* ps);
// 打印顺序表中的元素
void SeqListPrint(SL* ps);
// 销毁顺序表
void SeqListDestroy(SL* ps);
// 检查顺序表的容量
void SeqListCheckCapacity(SL* ps);

// 查找指定元素，找到返回下标，找不到返回 -1
int SeqListFind(SL* ps, SLDataType x);
// 在指定下标位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 在指定下标位置删除数据
void SeqListErase(SL* ps, int pos);

SeqList.c

在实现文件中，我们逐一实现各个接口。

(1) 顺序表的初始化

SeqListInit：初始化顺序表，将指针置为空、容量和大小置 0。

#include "SeqList.h"  // 注意在 SeqList.c 和 test.c 都要预先包含此头文件

void SeqListInit(SL* ps) {
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

(2) 动态顺序表的扩容

SeqListCheckCapacity：当我们的顺序表需要插入元素但是发现空间不够时，可以调用此函数来进行扩容。

void SeqListCheckCapacity(SL* ps) {
	// 若当前空间不足，则进行扩容
	if (ps->size == ps->capacity) {
        
        // 如果顺序表为空，那么将大小置为 4，不为空，则扩容至原大小的两倍
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        
        // 开辟一个新的空间，大小为 newcapacity，并将原来的数组a的内容拷贝过来
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
        
        // 判断是否开辟失败
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
        
        // 将原指针指向新开辟的内存地址，即完成扩容
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
    // 注意这一整个函数体都是包在一个 if 语句内的
}

• 关于 realloc

// 函数声明
void* realloc (void* ptr, size_t size);

意思就是如果你对原来的空间扩容，如果原来的空间时空的话，那么 realloc 的作用就相当于 malloc。

说明：为了避免频繁扩容，一般我们会选择扩容到原来的两倍

(3) 尾部插入元素

SeqListPushBack：尾部插入元素，首先检查空间，再将元素放到数组尾部。

void SeqListPushBack(SL* ps, SLDataType x) {
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

(4) 尾部删除元素

SeqListPopBack：尾部删除元素，注意如果顺序表本身为空就不能再删除了！所以删除前需要判断链表是否为空。

通常可以有两种方式判断是否为空：if 语句（温柔），assert函数（粗暴）。

void SeqListPopBack(SL* ps) {
	//if (ps->size > 0) {
	//	ps->size--;
	//}
    assert(ps->size > 0);
	ps->size--;
}

可以看到这里只需要将 size 的值减 1 即可，因为 size 实际上代表容器内有效数据的个数，之后的数据是什么都是无效的。

(5) 头部插入元素

SeqListPushFront：头部插入元素，需要将所有已有元素向后移动一位。

void SeqListPushFront(SL* ps, SLDataType x) {
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0) {
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

(6) 头部删除元素

SeqListPopFront：头部删除元素，删除后所有元素向前移动一位。

void SeqListPopFront(SL* ps) {
	assert(ps->size > 0);
	int begin = 1;
	while (begin < ps->size) {
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

(7) 查找指定元素

SeqListFind：遍历顺序表查找指定元素，找到目标返回元素的下标，没有找到则返回 -1。

int SeqListFind(SL* ps, SLDataType x) {
	for (int i = 0; i < ps->size; ++i) {
		if (ps->a[i] == x) {
			return i;
		}
	}
	return -1;
}

(8) 指定位置插入元素

SeqListInsert：在指定下标位置插入数据，需先检查 pos 和是否需要扩容，再将后续元素后移。

pos：表示待插入元素插入后所在的下标，也可理解为在 pos 下标处之前插入指定元素。

void SeqListInsert(SL* ps, int pos, SLDataType x) {
	assert(pos >= 0 && pos <= ps->size);  // 注意都有取等，pos == size 时表示尾部插入
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos) {
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

(9) 删除指定位置元素

SeqListErase：在指定位置删除数据，需检查 pos 和容器是否为空，再将后续元素前移。

pos：删除 pos 下标处的元素。

void SeqListErase(SL* ps, int pos) {
	assert(pos >= 0 && pos < ps->size);  // 注意这里 ps->size 一端不取等
    assert(ps->size > 0);
	int begin = pos + 1;
	while (begin < ps->size) {
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

(10) 打印元素

SeqListPrint：遍历数组，打印所有存储的元素。

void SeqListPrint(SL* ps) {
	for (int i = 0; i < ps->size; ++i) {
		printf("%d ", ps->a[i]);
	}
}

(11) 释放顺序表

SeqListDestroy：释放动态分配的内存，并重置顺序表。

void SeqListDestroy(SL* ps) {
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

(12) SeqList.c 完整代码

#include "SeqList.h"

void SeqListInit(SL* ps) {
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void SeqListCheckCapacity(SL* ps) {
	if (ps->size == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));

		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

void SeqListPushBack(SL* ps, SLDataType x) {
	SeqListCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;
}

void SeqListPopBack(SL* ps) {
	//if (ps->size > 0) {
	//	ps->size--;
	//}

	//或者下面这种方式
	assert(ps->size > 0);
	ps->size--;
}

void SeqListPushFront(SL* ps, SLDataType x) {
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0) {
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

void SeqListPopFront(SL* ps) {

	assert(ps->size > 0);

	int begin = 1;
	while (begin < ps->size) {
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

void SeqListPrint(SL* ps) {
	for (int i = 0; i < ps->size; ++i) {
		printf("%d ", ps->a[i]);
	}
}

void SeqListDestroy(SL* ps) {
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

int SeqListFind(SL* ps, SLDataType x) {
	for (int i = 0; i < ps->size; ++i) {
		if (ps->a[i] == x) {
			return i;
		}
	}
	return -1;
}

void SeqListInsert(SL* ps, int pos, SLDataType x) {

	assert(pos >= 0 && pos <= ps->size);  // 注意都有取等

	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos) {
		ps->a[end + 1] = ps->a[end];
		--end;
	}

	ps->a[pos] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos) {

	assert(pos >= 0 && pos < ps->size);  // size就没有等于了

	int begin = pos + 1;
	while (begin < ps->size) {
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;
}

test.c

在测试文件中，我们可以编写测试函数验证顺序表各项操作是否正确。下面给出一个简单的测试例子 SeqListTest，演示了尾部和头部插入删除操作，并打印结果：

#include "SeqList.h"

void SeqListTest() {
	SL s1;
	SeqListInit(&s1);
	// 尾部插入数据
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	// 头部插入数据
	SeqListPushFront(&s1, 1);
	SeqListPushFront(&s1, 2);
	SeqListPushFront(&s1, 3);
	SeqListPushFront(&s1, 4);
	SeqListPushFront(&s1, 5);

SeqListPrint(&s1);
printf("\n");

// 头部删除两个元素
SeqListPopFront(&s1);
SeqListPopFront(&s1);

SeqListPrint(&s1);

}

int main() {
	SeqListTest();
	return 0;
}

运行结果：

四、 练习

移除元素

• 思路 1：暴力求解

找到所有的 val，一次一次地挪动数据覆盖删除，最坏的情况：数组内全部是 val。

时间复杂度：$O(N^2)$，很显然，太慢了。

能否将时间复杂度优化至 $O(N)$？

• 思路 2：以空间换时间

遍历一次 nums 数组，把不是 val 的值，放到 tmp 数组，再把 tmp 数组的值拷贝回去。

时间复杂度：$O(N)$，空间复杂度：$O(N)$。

emm… 能不能再将空间复杂度优化至 $O(1)$？可以的！

• 思路 3：双指针

直接上代码

int removeElement(int* nums, int numsSize, int val) {
    int src = 0, dst = 0;
    while(src < numsSize){
        if(nums[src]!=val){
            nums[dst] = nums[src];
            src++;
            dst++;
        }
        else src++;
    }
    return dst;
}

删除有序数组中的重复项

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;  // 处理空数组情况

    int p1 = 0;  // 记录唯一元素存放的位置
    for (int p2 = 1; p2 < numsSize; ++p2) {
        if (nums[p1] != nums[p2]) {
            nums[++p1] = nums[p2];  // 只在遇到不同元素时才更新数组
        }
    }
    return p1 + 1;
}

合并两个有序数组

思路1：逆向归并

由于两个数组均已排好序，而且 nums1 有足够的空间存储两个数组的所有元素，所以可以逆向双指针策略，从两个数组的末尾开始比较，将较大的元素放入 nums1 的末尾。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int end1 = m-1,end2 = n-1;
    int end = m+n-1;

    while(end1 >= 0 && end2 >=  0){
        if(nums1[end1]>nums2[end2]){
            nums1[end--]=nums1[end1--];
        }
        else{
            nums1[end--]=nums2[end2--];
        }
    }

    while(end2>=0){
        nums1[end--]=nums2[end2--];
    }
}

思路2：双指针

利用一个额外的数组 sorted 存储合并后的有序结果。通过两个指针从两个数组的起始位置开始比较，将较小的元素依次放入 sorted 数组中，最后再将 sorted 中的元素复制回 nums1。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = 0, p2 = 0;
    int sorted[m + n];
    int cur;
    while (p1 < m || p2 < n) {
        if (p1 == m) {
            cur = nums2[p2++];
        } else if (p2 == n) {
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } else {
            cur = nums2[p2++];
        }
        sorted[p1 + p2 - 1] = cur;
    }
    for (int i = 0; i != m + n; ++i) {
        nums1[i] = sorted[i];
    }
}

思路3：合并数组再排序

int cmp(int* a, int* b) {
    return *a - *b;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    for (int i = 0; i != n; ++i) {
        nums1[m + i] = nums2[i];
    }
    qsort(nums1, nums1Size, sizeof(int), cmp);
}

五、小结

本篇主要介绍了线性表中的其中一种类型——顺序表。并介绍了顺序表的概念、存储结构和基础操作，通过代码实现了顺序表的增删查改等一系列操作。但是就算有了动态存储的顺序表，它依然有很多缺陷：

• 空间不够了需要扩容，而扩容是需要付出代价的。
• 我们空间满了基本都是扩2倍，可能就会导致一些空间的浪费，比如我有100个数据满了，扩容到200个，但是我只需要插入5个数据，那么这样就浪费了95个空间。
• 顺序表要求数据从开头位置连续存储，那么我们在开头或者中间位置插入删除数据就需要挪动数据，效率不高。

那么针对顺序表的缺陷，于是便设计出了另一种线性表——【链表】(想要学习链表点这里!)。

数据结构之——顺序表【完】