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

【数据结构】励志大厂版·初阶（复习+刷题）：线性表（顺序表）

news 来源：原创 2025/8/25 23:46:50

前引：上一篇我们复习了复杂度，今天我们来通过实践回忆我们的线性表知识点，下面将讲解什么是线性表，顺序结构又是什么，知识点简洁精髓，无废话可言，小编会从每个细节讲起，包含头文件的使用，分析每句代码的位置，这篇文章可作为你的绝佳复习资料哦，欢迎在评论区进行点评

知识点速览

代码实现与讲解

定义结构体

静态顺序表

初始化

动态顺序表

初始化

存储元素

头插

尾插

头删

尾删

随机删除

随机插入

练习题一

练习题二

知识点速览

线性表： n 个具有相同特性的数据元素的有限序列。在逻辑上来说是线性结构，也就是说它存起来的数据像一条线一样（物理上并不一定是连续的），通常以数组、链表结构来存储（常见的线性表：顺序表、链表、栈、队列、字符串......）

顺序表：用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储，在数组上完成数据的增删查找（顺序表可以分类为：静态顺序表（定长数组存储）、动态顺序表（动态开辟的数组存储））

代码实现与讲解

上面我们知道顺序表有两种实现方式，一种是定长数组，另一种是动态开辟数组，下面小编将分别作讲解，内容详细，分析到位，不仅是小编的复习整理，也是学习记录！

定义结构体

静态数组来存储数据，咱们需要一个结构体，因为涉及到多个变量，比如当前存储的数据个数、最大空间、存储空间，结构体可以参考下面这样设计：

struct List
{//定长数组int arr[10];//当前数据个数int size;//最大存储量int max;
};

这样我们就定义了一个结构体，它的类型是 struct List ，类比 int 、char 一样属于数据类型。下面我们来创造结构体变量，有以下两种方式：直接创造 类型+名称这样创造。如下参考：

这里我们有几点可以优化及注意的地方：

（1）使用typedef 来重新定义变量，例如这个结构体被typedef重新定义之后，它的类型就可以简写为 List

typedef struct List
{//定长数组int arr[10];//当前数据个数int size;//最大存储量int max;
}List;

（2）同样我们可以用 typedef 来定义变量类型、用宏定义常量，可以方便以后进行代码维护

//定义变量类型
typedef int Plastic;//宏定义常量
#define MAX 10typedef struct List 
{//定长数组Plastic arr[MAX];//当前数据个数Plastic size;//最大存储量Plastic max;
}List;

（3）注意下面这两种写法，小编通过画图来进行注释

静态顺序表

我们已经定义完了结构体，下面我们来简单看看静态顺序表，这里因为静态顺序表与动态顺序表除了开辟类型不一样，其它大致相同，我们以动态顺序表为主要的讲述对象

初始化

这里需要注意，我们改变的是结构体的成员，需要取地址，因为实参是形参的一份临时拷贝，取地址的话，函数就拿到的是结构体的地址，否则就是对结构体的一份拷贝，不会真正改变，例如：

//初始化
Preliminary(&Static);

在初始化空间的时候，我们可以采用函数 memset ，这样可以避免使用几条代码的循环

void Preliminary(List* Static)
{//初始化当前数据个数Static->size = 0;//初始化最大存储个数Static->max = MAX;//初始化空间memset(Static->arr, 0, sizeof(Plastic) * MAX);
}

初始化完成之后，再按照数组那样取存储数据就好了，下面我们来重点讲解动态顺序表！

动态顺序表

初始化

跟之前的初始化其实大差不差，只是我们结构体里面存的数组变成了指针，需要初始化时开辟空间

typedef struct List 
{//动态空间指针Plastic* arr;//当前数据个数Plastic size;//最大存储量Plastic max;
}List;

下面我们来初始化结构体里面的变量，下面我们再通过调试来看初始化的结果

void Preliminary(List* Static)
{//初始化当前数据个数Static->size = 0;//初始化最大存储个数Static->max = MAX;//开辟数组空间Static->arr = (int*)malloc(sizeof(Plastic) * MAX);//判断空间有效性if (Static->arr == NULL){printf("开辟空间失败\n");return;}
}

存储元素

下面我们来将元素存储进动态空间，按照逻辑，我们应该考虑当前是否是满空间，否则就要扩容了，为了以后方便维护，和提高代码的可读性，我们先来实现扩容函数！下面的代码有几点注意！

（1）扩容空间的指针最好不要用原空间指针，因为扩容可能不是在原空间后面开辟

（2）如果扩容成功，需要将原空间指针与新空间指针连接起来

//扩容
void Extend(List* Static)
{int* pc = (int*)realloc(Static->arr, sizeof(Plastic) * (Static->max) * 2);//判断扩容是否成功if (pc == NULL){printf("扩容失败\n");return;}else{//更新空间Static->arr = pc;Static->max *= 2;printf("扩容成功\n");}
}

下面我们来存储数据（注意更新元素个数），并且通过调试来观察存储结果

void Storage(List* Static, int data)
{//如果空间已满，就进行扩容if (Static->size == Static->max){Extend(Static);}//存储元素Static->size++;Static->arr[Static->size - 1] = data;
}

头插

头插前有两个操作需要注意：

（1）注意空间是否存在，否则无法头插

（2）头插需要判断空间是否充裕，通常是判断size+1的元素空间是否越界

然后经过这两个判断之后，进行头插，为了使代码效率高，我们选择从后往前进行挪动之前的数据，然后再进行插入，思维演示如下：

头插之前

头插之后

//头插
void Head(List* Static, int data)
{//如果空间不存在则无法头插if (Static->arr == NULL){printf("空间不存在无法头插\n");return;}//判断空间是否充足if (Static->size + 1 == Static->max){Extend(Static);}int end = Static->size - 1;//移动元素while (end >= 0){Static->arr[end + 1] = Static->arr[end];end--;}//插入元素Static->arr[0] = data;Static->size++;
}

尾插

我们刚才设置的结构体里面有一个成员是记录当前元素个数的，咱们尾插的步骤就是：先找尾、再插入。这里刚好就是size下标的地方（注意判断空间是否充裕），由于过程简单，我们直接上代码

void Tail(List* Static, int data)
{//判断空间是否充裕if (Static->size + 1 == Static->max){Extend(Static);}//插入Static->arr[Static->size] = data;Static->size++;
}

头删

删除第一个元素，我们这里不需要判断空间是否支持删除，只需要判断删除的这个元素空间是否存在就行了（不存在就退出）。判断之后，这里最方便的方式是将元素向前挪动，需要控制下标不能越界

头删之前

头删之后

void Head_Omit(List* Static)
{//判断是否有元素可以删除if (Static->size == 0){printf("删除失败\n");return;}//从第一个元素开始将后面的元素往前挪动int end = 0;while (end < Static->size-1)//                 注意控制下标不能越界{Static->arr[end] = Static->arr[end + 1];end++;}//元素个数减一Static->size--;

尾删

尾插就不多说了，先判断空间是否支持删除（size > 0），然后size--即可

尾删之前

尾删之后

void Tail_Omit(List* Static)
{//判断能否删除if (Static->size == 0){printf("删除失败\n");return;}//删除Static->size--;
}

随机删除

随机删除小编就以提供下标为列，将对应下标的元素删除，需要考虑空间元素数量是否支持删除情况。小编提供的思路：先找到那个下标的元素，然后将后面的元素前移

删除之前

删除之后

//随机删除（下标位置删除）
Random_Omit(List* Static, int under)
{//找对应下标的元素int end = 0;while (end < Static->size && Static->arr[end] != Static->arr[under]){end++;}//如果没有找到if (end == Static->size){printf("该元素不存在\n");return;}//将后面的元素向前挪动while (end < Static->size - 1){Static->arr[end] = Static->arr[end + 1];end++;}//元素个数减一Static->size--;
}

随机插入

这里小编还是根据下标来找到插入的位置，先判断该下标是否支持插入，然后该下标原来的元素全部后移，再插入即可

插入之前

插入之后

//随机插入（下标位置插入）
void Random_Insert(List* Static, int under, int data)
{//先判断该下标是否支持插入int end = 0;while (end < Static->size && end != under){end++;}//如果没有找到if (Static->size == end){printf("该位置无法插入\n");return;}//该下标位置及后面的元素后移end = Static->size-1;while (end != under){Static->arr[end] = Static->arr[end-1];end--;}//插入Static->arr[under] = data;Static->size++;
}

练习题一

小编来大概解读一下这个题目：给你一个值，将一个数组中与这个值相等的元素移除，其余元素按顺序前移

思维方法：

（1）这一种是最简单的一种：就是创建另外一个数组空间，将这些符合规定的值全部存到这个新数组里面，然后返回不等于这个值的元素个数，这是最普通的写法，小编就不演示了啊！

（2）算法解法思想：我们可以采用双指针的方法，通过指针的快慢移动，来处理等于val的值，如果在力扣上不方便调试，大家可以放在自己的编译器上去观察数据变化，重点是学会，不是求速通

例题详解：

首先我们设置2个下标（a，b），a就负责找不同于val的值，找到之后b所在的下标元素就等于a所在下标的值，然后a、b都向前移动一位，就这样循环就行了，注意a不能越界，下面我画图演示

我用数组【0、1、2、2、3、0、4、2】，val=2做例子，大家对着图配上代码梳理一遍思路！

int removeElement(int* nums, int  numsSize, int val)
{int a = 0;int b = 0;int k = 0;while (a < numsSize){//a找不同while (a < numsSize && nums[a] == val){a++;}if (a >= numsSize){break;}//填埋、后移nums[b] = nums[a];a++;b++;k++;}return k;
}

练习题二

思维方法：

（1）此题我们还是可以通过双指针的思想来做，两个指针分别指向两个数组的起始位置，通过建立第三个数组空间，来根据双指针元素的大小进行顺序填充即可，但是此方法比较复杂（不推荐）

（2）找较大的元素，从后往前进行填充，这样也可以不用开辟新数组，详细解答过程如下

例题详解：

如果是 n1 先走完：

首先我们定义三个下标，例如num指向nums1的末尾，m1指向nums1初始数据末尾，n1指向nums2初始数据末尾，如下图：

然后我们通过找较大的值来从后向前填充。例如此时nums1【m1】>=nums2【n1】，num的位置就填充nums1【m1】，然后m1--，num--，例如：

接着通过循环来进行上面的操作：找两个数组中较大的值，填入num的位置，直到某个数组当前下标越界为止。【中间循环过程跳过】

此时我们按照上面的循环结束条件，两个数组的情况应该是下面这样的，nums1剩余的元素都是比nums2小的，自然也就不用管，直接达到了排序效果

如果是 m1 先走完：

我们再来看下面这种情况，如果是m1先走完，说明nums2中的剩余元素都是比nums1小的，m1走完也就结束了循环，存在nums2中有元素剩余，如图：

此时我们看到nums2的元素还没有走完，但是已经出循环了，这种情况就需要将nums2剩余的未排完的元素拷贝到nums1中去

if (m1 < 0)
{memcpy(nums1, nums2, sizeof(int) * (n1 + 1));
}

下面是总的代码，此题很有整理的必要，希望小编的讲解大家可以弄清楚！还是408真题哦！

void merge(int* nums1, int m, int* nums2, int n)
{int m1 = m - n - 1;int n1 = n - 1;int num = m - 1;while (n1 >= 0 && m1 >= 0){if (nums2[n1] >= nums1[m1] && n1 >= 0 && m1 >= 0){nums1[num] = nums2[n1];n1--;num--;}if (nums1[m1] >= nums2[n1] && n1 >= 0 && m1 >= 0){nums1[num] = nums1[m1];m1--;num--;}}//如果nums2中有元素剩余，就拷贝到nums1if (m1 < 0){memcpy(nums1, nums2, sizeof(int) * (n1 + 1));}
}

知识点速览

代码实现与讲解

定义结构体

静态顺序表

初始化

动态顺序表

初始化

存储元素

头插

尾插

头删

尾删

随机删除

随机插入

练习题一

练习题二

相关文章：