【数据结构】第二站：顺序表

目录

一、线性表

二、顺序表

1.顺序表的概念以及结构

2.顺序表的接口实现

3.顺序表完整代码

三、顺序表的经典题目

1.移除元素

2.删除有序数组中的重复项

3.合并两个有序数组

---

一、线性表

在了解顺序表前，我们得先了解线性表的概念

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
 

二、顺序表

1.顺序表的概念以及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改

顺序表一般可以分为静态顺序表和动态顺序表

静态顺序表

typedef int SLDateType;#define N 10typedef struct SeqList
{SLDateType a[N];int size;
}SL;

如上代码所示，就是静态顺序表的定义。但是静态顺序表很不好用，因为开多了内存浪费，开少了不够用

动态顺序表

//动态顺序表
typedef int SLDateType;typedef struct SeqList
{SLDateType* a;//指向数据的指针int size;int capacity; //容量
}SL;

如上代码所示，动态的顺序表就是通过一个指针来指向数据。为了动态管理，所以要添加一个容量的变量

2.顺序表的接口实现

我们使用顺序表的目的就是为了增删查改一些数据。为此接口主要围绕增删查改。

1.顺序表接口声明

//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表的销毁
void SeqListDestroy(SL* ps);
//顺序表的打印
void SeqListPrint(SL ps);
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x);
//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x);
//顺序表的尾删
void SeqListPopBack(SL* ps);
//顺序表的头删
void SeqListPopFront(SL* ps);
//顺序表的查找
int SeqListFind(SL* ps, SLDateType x);
//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x);
//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos);

如上代码所示，对于顺序表，我们主要的目的就是增删查改，因此我们所需要实现的接口就又初始化、销毁、打印、尾插、头插、尾删、头删、查找、在某位置插入、在某位置删除等

2.顺序表的初始化

//顺序表的初始化
void SeqListInit(SL* ps)
{assert(ps);ps->a = (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}

如上代码所示，我们的函数参数是顺序表的指针，返回类型是void。

首先肯定ps是不可能为空的，因为ps是顺序表的地址。

然后我们让顺序表的数据指针指向的数组初始容量设置为INIT_CAPACITY，这个容量由宏来自定义。然后判断是否开辟内存成功。

如果成功则将size置为0，size代表的是当前顺序表内已经存放的数据个数。

2.顺序表的销毁

//顺序表的销毁
void SeqListDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}

我们在来看一下顺序表的销毁，对于顺序表的销毁，也是比较简单的，我们的顺序表中，数据指针所指向的区域是在堆区的，所以我们要对这个堆区进行释放掉。然后将其置空，最后size和capacity都置为0即可

3.顺序表打印

//顺序表的打印
void SeqListPrint(SL s)
{int i = 0;for (i = 0; i < s.size; i++){printf("%d ", s.a[i]);}printf("\n");
}

如上代码所示，由于是打印数据，所以我们传一个形参就已经可以了。当然传顺序表的地址也是没有任何问题的。然后就是使用一个循环来进行打印即可。

4.顺序表的尾插以及扩容函数

//扩容函数
void CheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (ps->capacity) * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x)
{assert(ps);CheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

如上代码所示，我们想要对顺序表进行尾插，那么首先我们得确保一下当前的容量是否足够，为了代码的简洁，我们直接将检查容量封装成一个函数，在检查容量的过程中，如果size和capacity相等，那么就意味着函数需要扩容了。我们使用realloc函数进行扩容即可，需要注意的是，进行扩容的时候要使用一个新的指针进行接收这个扩容后的地址，不然一旦扩容失败，后果得不偿失。我们一般采用的是扩容二倍。当然这里我们可以根据自己的想法进行调整。

扩容成功以后，由于是一个数组，那么就很简单的直接将数组的最后一个元素直接赋值即可，然后size++就可以了

5.顺序表的头插

//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x)
{assert(ps);CheckCapacity(ps);int i = 0;for (i = ps->size - 1; i >= 0; i--){ps->a[i + 1] = ps->a[i];}ps->a[0] = x;ps->size++;
}

对于顺序表的头插，我们仍然是先检查容量，这里就体现我们之前将扩容封装成一个一个函数的优势了。然后使用一个循环，将整个数组的值向后移动一个空间。最后将第一个元素给插入x即可

6.顺序表的尾删

//顺序表的尾删
void SeqListPopBack(SL* ps)
{assert(ps);if (ps->size == 0){printf("无可删除数据\n");return;}ps->size--;
}

对于这个尾删，我们特别需要主要的是当size为0的时候，就没有数据，不需要删除即可，这里可以采用assert暴力截止，也可以使用return温柔的拦截

然后我们直接让size--就可以了

7.顺序表的头删

//顺序表的头删
void SeqListPopFront(SL* ps)
{assert(ps);if (ps->size == 0){printf("无可删除数据\n");return;}int i = 0;for (i = 0; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

对于顺序表的头删，也是需要注意size为0的情况，然后将从下标为1的元素开始，全体元素向前移动的一个空间即可，最后size--

8.顺序表的查找

//顺序表的查找
int SeqListFind(SL* ps, SLDateType x) 
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}

对于顺序表的查找，我们就直接采用循环遍历的方式即可，如果找到了，则返回下标，否则返回-1

9.顺序表在pos位置的插入

//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);CheckCapacity(ps);int i = 0;for (i = ps->size - 1; i >= pos; i--){ps->a[i + 1] = ps->a[i];}ps->a[pos] = x;ps->size++;
}

如上代码所示，在pos位置的插入，那么首先需要注意的是，pos的范围要合理，pos应该大于等于0且小于等于size，pos等于size其实就是尾插

然后检查容量，使用循环将原来pos以及之后的位置统一向后移动一个空间，然后将pos位置的值赋值即可，最后size++

10.顺序表在pos位置的删除

//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int i = 0;for (i = pos; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

对于在pos位置的删除，那么思路与前面也是极其相似的，首先需要注意的是pos的范围，这里要小心了，pos是不可以等于size的

然后就是通过循环，将pos后面的数据，统一向前覆盖即可

3.顺序表完整代码

SeqList.h

#pragma once
//静态顺序表
//typedef int SLDateType;
//
//#define N 10
//
//typedef struct SeqList
//{
//	SLDateType a[N];
//	int size;
//}SL;
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define INIT_CAPACITY 4
//动态顺序表
typedef int SLDateType;typedef struct SeqList
{SLDateType* a;//指向数据的指针int size;int capacity; //容量
}SL;//顺序表的初始化
void SeqListInit(SL* ps);
//顺序表的销毁
void SeqListDestroy(SL* ps);
//顺序表的打印
void SeqListPrint(SL ps);
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x);
//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x);
//顺序表的尾删
void SeqListPopBack(SL* ps);
//顺序表的头删
void SeqListPopFront(SL* ps);
//顺序表的查找
int SeqListFind(SL* ps, SLDateType x);
//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x);
//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"//顺序表的初始化
void SeqListInit(SL* ps)
{assert(ps);ps->a = (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}
//顺序表的销毁
void SeqListDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
//顺序表的打印
void SeqListPrint(SL s)
{int i = 0;for (i = 0; i < s.size; i++){printf("%d ", s.a[i]);}printf("\n");
}
//扩容函数
void CheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (ps->capacity) * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}
//顺序表的尾插
void SeqListPushBack(SL* ps,SLDateType x)
{assert(ps);CheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}
//顺序表的头插
void SeqListPushFront(SL* ps, SLDateType x)
{assert(ps);CheckCapacity(ps);int i = 0;for (i = ps->size - 1; i >= 0; i--){ps->a[i + 1] = ps->a[i];}ps->a[0] = x;ps->size++;
}
//顺序表的尾删
void SeqListPopBack(SL* ps)
{assert(ps);if (ps->size == 0){printf("无可删除数据\n");return;}ps->size--;
}
//顺序表的头删
void SeqListPopFront(SL* ps)
{assert(ps);if (ps->size == 0){printf("无可删除数据\n");return;}int i = 0;for (i = 0; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}
//顺序表的查找
int SeqListFind(SL* ps, SLDateType x) 
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}
//顺序表在pos位置的插入
void SeqListInsert(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);CheckCapacity(ps);int i = 0;for (i = ps->size - 1; i >= pos; i--){ps->a[i + 1] = ps->a[i];}ps->a[pos] = x;ps->size++;
}
//顺序表在pos位置的删除
void SeqListErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int i = 0;for (i = pos; i < ps->size - 1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"void TestSeqList1()
{SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListPrint(s);SeqListPushFront(&s, 4);SeqListPushFront(&s, 3);SeqListPushFront(&s, 2);SeqListPushFront(&s, 1);SeqListPrint(s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPopBack(&s);SeqListPrint(s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPopFront(&s);SeqListPrint(s);SeqListPopFront(&s);SeqListPrint(s);SeqListPopFront(&s);SeqListPrint(s);SeqListPopFront(&s);SeqListPrint(s);SeqListPopFront(&s);SeqListPrint(s);SeqListPopFront(&s);SeqListPopFront(&s);}
void TestSeqList2()
{SL s;SeqListInit(&s);SeqListPushBack(&s, 1);SeqListPushBack(&s, 2);SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListPrint(s);int pos = SeqListFind(&s, 3);SeqListInsert(&s, pos, 5);SeqListInsert(&s, pos, 6);SeqListInsert(&s, pos, 7);SeqListPrint(s);SeqListErase(&s, pos);SeqListErase(&s, pos);SeqListErase(&s, pos);SeqListPrint(s);}
int main()
{//TestSeqList1();TestSeqList2();return 0;
}

三、顺序表的经典题目

1.移除元素

题目链接：力扣

解一：暴力循环法

即利用顺序表在某个位置的删除，只要某个位置满足删除的条件，就将后面的数据全部移动到前面来。但是效率太低，时间复杂度达到了O(N²)

解二：使用新数组

开辟一个新的数组，如果原数组中的这个元素不是需要移除的元素，则直接拷贝到新数组中，如果是需要移除的元素，则不拷贝，最后将新数组拷贝到原来的数组中即可，如果新数组开辟在了堆区，那么要记得释放空间，这种方法的时间复杂度和空间复杂度均为O(N)，显然不满足题目要求

解三：使用双指针

思路与解二基本类似，但是不同的是，我们可以利用两个下标来实现我们的思路，我们设置两个下标src和dst，我们让src去遍历整个数组，如果在src处的值不是val，则将src处的值拷贝到dst中，然后src和dst均++

如果是val，则src++。其余不动，代码如下

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

2.删除有序数组中的重复项

题目描述：力扣

对于这道题，我们的思路和第一道题是基本一致的，采用双指针的方法

 如上图所示，我们使用src和dst两个下标，src初始值设置为1，dst设置为0，那么当src和dst的值相等的时候，src++。如果不相等，则先让dst++，然后将src处的值赋值给dst，最后src++。代码如下

int removeDuplicates(int* nums, int numsSize) {int src = 1;int dst = 0;for (src = 1; src < numsSize;){if (nums[src] == nums[dst]){src++;}else{dst++;nums[dst] = nums[src];src++;}}return dst + 1;
}

3.合并两个有序数组

题目描述：力扣

解一：直接合并，然后排序

最简单的方式就是直接暴力合并，然后采用排序算法就可以了。但是这是一个俗手。时间复杂度较高

解二：归并

对于这道题而言，我们可以采用归并的思路

首先是设置三个下标end1，end2，end。

然后我们循环比较end1和end2所指向的较大值，将较大值赋给end所指向的位置。然后赋值的end和被赋值的end均--。

当end2的值先变成了负数的时候，那么自然是最好的状态，此时肯定有序。

但是当end1的值先变成了负数的时候，那么end2的数据并未完全存放到nums1中，此时我们需要将end2的剩余元素给插入到nums1中

具体代码如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 = m - 1;int end2 = n - 1;int end = m + n - 1;while (end1 >= 0 && end2 >= 0){if (nums1[end1] > nums2[end2]){nums1[end] = nums1[end1];end--;end1--;}else{nums1[end] = nums2[end2];end--;end2--;}}if (end1 < 0){while (end2 >= 0){nums1[end] = nums2[end2];end2--;end--;}}
}

---

好了，本期内容就到这里

如果对你有帮助的话，不要忘记点赞加收藏哦！！！