当前位置：首页 > news >正文

26 线性表 · 顺序表

news 2025/7/4 0:50:01

一、线性表

二、顺序表

（一）概念与结构

（二）分类

1、静态顺序表

2、动态顺序表

3、动态顺序表与静态顺序表的区别

4、动态顺序表的实现

三、顺序表OJ

（一）移除指定元素

（二）删除有序数组中的重复项

（三）合并两个有序数组

四、顺序表存在的问题总结

一、线性表

线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。比如：水果有苹果、西瓜、草莓等；蔬菜有青菜、通心菜、南瓜等；线性表有顺序表、链表、栈、队列等。线性表是一种在实际中广泛使用的数据结构。

线性表的特性分为逻辑结构和物理结构：

① 物理结构：数据在内存上的存储形式；

② 逻辑结构：人为想象出来的数据的组织形式。

线性表在逻辑上是线性结构，也就说是连续的一条直线，认为数据是一个接着一个排列的。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

（一）概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。

顺序表不仅在逻辑结构上是线性的，而且物理结构也是线性的。

虽然顺序表的底层为数组，但是与数组还是有区别的。顺序表是对数组进行了封装，比数组多出了常用的增删查改等接口。可以理解为顺序表是数组的升级豪华版。

顺序表常用名：SeqList，单词的缩写为：sequence - 流利的、流畅的；list - 列表，合起来就叫顺序表。

（二）分类

1、静态顺序表

概念：使用固定长度数组来存储元素的顺序表。

//定义静态顺序表结构体
typedef int SLDateType;
#define N 7 //固定数组长度
typedef struct Static_SeqList
{SLDateType arr[N];int size;//记录有效数据的个数
}STL;

2、动态顺序表

概念：使用动态内存管理来创建数组的顺序表。

typedef int SLDatatype;typedef struct SeqList
{SLDatatype* arr;//基础数组int capacity;//数组的最大元素个数int size;//有效元素个数
}SL;

3、动态顺序表与静态顺序表的区别

① 静态顺序表的缺点：在定义之前需要知道数组的大小，若是不知具体大小的话，直接给个数字来定大小，可能会造成空间不够而丢失数据，或者造成空间浪费。

② 动态顺序表不存在静态顺序所有的缺点，所以动态顺序表更加优秀，平时更加倾向于动态顺序表的使用。

注意：

不管是静态还是动态顺序表，表中的数组类型都使用 typedef 一个类型然后取别名来定义，这样若果需求改变的话，可以一键更改顺序表的类型；

在静态顺序表中，顺序表的数组长度可以使用#define 来进行替换，这样也能一键修改数组的范围。

4、动态顺序表的实现

① 头文件【SeqList.h】：定义顺序表结构体，声明要提供的操作（起到目录作用）；

② cpp文件【SeqList.cpp】：编写具体实现各种操作（起到内容作用）；

③ 测试文件【test.cpp】：测试是否可以正常运行。

具体实现如下：

SeqList.h 文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<assert.h>
using namespace std;typedef int SLDateType;//一、定义顺序表结构体
typedef struct SeqList
{SLDateType* arr;int capacity;//存放动态申请空间的数组元素的总个数int size;//记录有效数据的个数
}SL;//二、声明顺序表初始化函数
void SLInit(SL& s);//三、声明顺序表的销毁
void SLDestroy(SL& s);//四、声明顺序表的插入操作：
//因为每次插入都要判断空间是不是满足，可以把扩容项提取出来
void SLCheckCapacity(SL& s);
//(一)声明尾插入：
void SLPushBack(SL& s, SLDateType num);
//(二)声明头插入：
void SLPushFront(SL& s, SLDateType num);//五、声明打印顺序表
void SLPrint(SL& s);//六、声明顺序表的删除
//(一)声明尾删除
void SLPopBack(SL& s);
//(二)声明头删除
void SLPopFront(SL& s);//七、在指定位置之前插入数据
void SLInsert(SL& s, SLDateType num, int pos);//八、删除指定位置的数据
void SLErase(SL & s, int pos);//九、声明顺序表查找
int SLFind(SL& s, SLDateType num);

SeqList.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"//一、顺序表初始化的定义
void SLInit(SL& s)
{s.arr = nullptr;s.capacity = s.size = 0;
}//二、顺序表销毁的定义
void SLDestroy(SL& s)
{if (s.arr)free(s.arr);s.arr = nullptr;s.capacity = s.size = 0;
}//三、顺序表插入的定义
//（一）顺序表尾插入的定义
void SLPushBack(SL& s, SLDateType num)
{//如果使用的是指针参数，则需要判断是否为空指针（【断言】或者【if判断直接返回空语句】）SLCheckCapacity(s); //把上面注释的代码提取成是否需要检测扩容//若空间足够，直接插入到size的位置，size++s.arr[s.size++] = num;
}//四、打印顺序表
void SLPrint(SL& s)
{for (int i = 0; i < s.size; i++){cout << s.arr[i] << " ";}cout << endl;
}//五、检查空间是否需要扩容
void SLCheckCapacity(SL& s)
{if (s.size == s.capacity)//判断有效数据长度是否等于空间元素总个数{int NewCapacity = s.capacity == 0 ? 4 : 2 * s.capacity;//预防初始的空间大小为0SLDateType* tmp = (SLDateType*)realloc(s.arr, sizeof(SLDateType) * NewCapacity);//扩容if (nullptr == tmp){perror("SLPushBack realloc error");exit(1);}s.arr = tmp;//扩容结束s.capacity = NewCapacity;//更新最大容量大小}
}//三、顺序表插入的定义
//（二）顺序表头插入的定义
void SLPushFront(SL& s, SLDateType num)
{//如果使用的是指针参数，则需要判断是否为空指针（【断言】或者【if判断直接返回空语句】）SLCheckCapacity(s);//检测扩容//整体向后移动一位for (int i = s.size; i > 0; i--){s.arr[i] = s.arr[i - 1];}//插入s.arr[0] = num;//扩容后增加有效个数s.size++;
}//六、定义删除
//(一)定义尾删除
void SLPopBack(SL& s)
{assert(s.arr);//判断数组不为空s.size--;//直接size--即可，因为打印也只会到size之前的位置，当需要头尾插入的时候，s.arr[size]都会被覆盖掉。
}
//(二)定义头删除
void SLPopFront(SL& s)
{assert(s.arr);//判断数组不为空for (int i = 0; i < s.size - 1; i++)//把后一个数组元素的值赋给前一个数组元素的值{s.arr[i] = s.arr[i + 1];}s.size--;//有效大小减一
}//七、定义在指定位置之前插入数据
void SLInsert(SL& s, SLDateType num, int pos)
{assert(s.arr);assert(pos >= 0 && pos <= s.size); //此处判断插入位置是否合理SLCheckCapacity(s);//凡是需要插入的地方都要判断一下空间是否足够//开始插入//把pos位置以后的地方整体后移for (int i = s.size;i > pos; i--){s.arr[i] = s.arr[i - 1];}//移动完成后插入，使有元素效个数+1s.arr[pos] = num;s.size++;
}//八、删除指定位置的数据
void SLErase(SL& s, int pos)
{//需要检测是否为空数组，若是空还继续删除就会报错assert(s.arr);assert(pos >= 0 && pos < s.size);for (int i = pos; i < s.size - 1; i++){s.arr[i] = s.arr[i + 1];}s.size--;
}//九、声明顺序表查找
int SLFind(SL& s, SLDateType num)
{assert(s.arr);for (int i = 0; i < s.size; i++){if (s.arr[i] == num)return i;//找到就返回下标}return -1;//没找到就返回-1。
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"void test01()//测试函数
{SL s;SLInit(s);//测试初始化for (int i = 1; i <= 10; i++)//测插入{SLPushBack(s, i);SLPushFront(s, i);}for (int i = 1; i <= 10; i++)//测试删除{SLPrint(s);//测试打印SLPopBack(s);//测试尾删除SLPopFront(s);//测试头删除}SLInsert(s, 100, 0);//测试指定位置插入SLErase(s, 6);//测试指定位置删除SLFind(s, 7);//测试查找SLDestroy(s);//测试销毁
}int main()
{test01();//使用测试函数return 0;
}

注意：

① 插入都要检查空间是否足够；

② 删除都要检查数组是否为空；

③ 指定位置进行插入或删除，在检测空间或空数组之后，还要检测插入位置是否合法。

三、顺序表OJ

（一）移除指定元素

题目链接：https://leetcode.cn/problems/remove-element/description/

解题思路：

创建两个下标，都指向第一个元素

① 若 src 下标指向的元素与指定删除元素相等，src++

② 若 src 下标指向的元素与指定删除元素不相等，dst++，nums[dst]= nums[src],，src++

解题代码如下：

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

（二）删除有序数组中的重复项

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

解题思路：

定义两个指针/变量，dst指向第一个位置，src指向下一个位置，判断src和dst位置的数据
① 相等，src++；
② 不相等，dst++，nums[dst]=nums[src]，src++。

解题代码如下：

int removeDuplicates(int* nums, int numsSize) {int src = 1, dest = 0;while (src < numsSize){if (nums[src] == nums[dest])src++;elsenums[++dest] = nums[src++];}return dest + 1;
}

（三）合并两个有序数组

题目链接：https://leetcode.cn/problems/merge-sorted-array/description/

思路：创建三个指针/变量，src1 指向第一个数组的最大有效元素，src2 指向第二个数组的最大有效元素，dest 指向第一个数组的最后一个元素；然后比较了src1和src2位置的数据，谁大，谁往dest位置放数据，放完数据后dest与比较大的元素的指标都src1 或 src2 都 --；还要考虑当 src1 < 0时，第二个数组还有元素没有合并进去，需要进行操作；而 src2 < 0时，则不需要额外的操作。

解题代码如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int src1 = m - 1, src2 = n - 1, dest = m + n - 1;while (src1 >= 0 && src2 >= 0){if (nums1[src1] > nums2[src2])nums1[dest--] = nums1[src1--];elsenums1[dest--] = nums2[src2--];}while (src2 >= 0)nums1[dest--] = nums2[src2--];
}