qidao123.com技术社区-IT企服评测·应用市场

标题: 【数据结构】励志大厂版·初阶（复习+刷题）：线性表（次序表） [打印本页]

---

作者: 八卦阵    时间: 2025-4-17 03:47
标题: 【数据结构】励志大厂版·初阶（复习+刷题）：线性表（次序表）

前引：上一篇我们复习了复杂度，今天我们来通过实践回忆我们的线性表知识点，下面将讲解什么是线性表，次序结构又是什么，知识点简洁精髓，无废话可言，小编会从每个细节讲起，包含头文件的使用，分析每句代码的位置，这篇文章可作为你的绝佳复习资料哦，接待在批评区举行点评
目次
 知识点速览
代码实现与讲解
定义结构体
静态次序表
初始化
动态次序表
初始化
 存储元素
头插
 尾插
 头删
尾删
 随机删除
 随机插入
练习题一 
练习题二

---

 知识点速览

线性表： n 个具有相同特性的数据元素的有限序列。在逻辑上来说是线性结构，也就是说它存起来的数据像一条线一样（物理上并不一定是一连的），通常以数组、链表结构来存储（常见的线性表：次序表、链表、栈、队列、字符串......）
次序表：用一段物理地址一连的存储单位依次存储数据元素的线性结构，一般接纳数组存储，在数组上完成数据的增删查找（次序表可以分类为：静态次序表（定长数组存储）、动态次序表（动态开辟的数组存储））
代码实现与讲解

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

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

1. struct List
2. {
3.         //定长数组
4.         int arr[10];
5.         //当前数据个数
6.         int size;
7.         //最大存储量
8.         int max;
9. };

复制代码

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

 这里我们有几点可以优化 及 留意的地方：
（1）使用typedef 来重新定义变量，例如这个结构体被typedef重新定义之后，它的范例就可以             简写为 List

1. typedef struct List
2. {
3.         //定长数组
4.         int arr[10];
5.         //当前数据个数
6.         int size;
7.         //最大存储量
8.         int max;
9. }List;

复制代码

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

1. //定义变量类型
2. typedef int Plastic;
4. //宏定义常量
5. #define MAX 10
7. typedef struct List
8. {
9.         //定长数组
10.         Plastic arr[MAX];
11.         //当前数据个数
12.         Plastic size;
13.         //最大存储量
14.         Plastic max;
15. }List;

复制代码

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

静态次序表

我们已经定义完了结构体，下面我们来简单看看静态次序表，这里由于静态次序表与动态次序表除了开辟范例不一样，其它大抵相同，我们以动态次序表为主要的讲述对象
初始化

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

1. //初始化
2. Preliminary(&Static);

复制代码

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

1. void Preliminary(List* Static)
2. {
3.         //初始化当前数据个数
4.         Static->size = 0;
5.         //初始化最大存储个数
6.         Static->max = MAX;
7.         //初始化空间
8.         memset(Static->arr, 0, sizeof(Plastic) * MAX);
9. }

复制代码

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

初始化

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

1. typedef struct List
2. {
3.         //动态空间指针
4.         Plastic* arr;
5.         //当前数据个数
6.         Plastic size;
7.         //最大存储量
8.         Plastic max;
9. }List;

复制代码

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

1. void Preliminary(List* Static)
2. {
3.         //初始化当前数据个数
4.         Static->size = 0;
5.         //初始化最大存储个数
6.         Static->max = MAX;
8.         //开辟数组空间
9.         Static->arr = (int*)malloc(sizeof(Plastic) * MAX);
10.         //判断空间有效性
11.         if (Static->arr == NULL)
12.         {
13.                 printf("开辟空间失败\n");
14.                 return;
15.         }
16. }

复制代码

 存储元素

下面我们来将元素存储进动态空间，按照逻辑，我们应该考虑当前是否是满空间，否则就要扩容了，为了以后方便维护，和进步代码的可读性，我们先来实现扩容函数！下面的代码有几点留意！
（1）扩容空间的指针最好不要用原空间指针，由于扩容大概不是在原空间反面开辟
（2）如果扩容成功，必要将原空间指针与新空间指针毗连起来

1. //扩容
2. void Extend(List* Static)
3. {
4.         int* pc = (int*)realloc(Static->arr, sizeof(Plastic) * (Static->max) * 2);
5.         //判断扩容是否成功
6.         if (pc == NULL)
7.         {
8.                 printf("扩容失败\n");
9.                 return;
10.         }
11.         else
12.         {
13.                 //更新空间
14.                 Static->arr = pc;
15.                 Static->max *= 2;
16.                 printf("扩容成功\n");
17.         }
18. }

复制代码

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

1. void Storage(List* Static, int data)
2. {
3.         //如果空间已满，就进行扩容
4.         if (Static->size == Static->max)
5.         {
6.                 Extend(Static);
7.         }
9.         //存储元素
10.         Static->size++;
11.         Static->arr[Static->size - 1] = data;
12. }

复制代码

头插

头插前有两个操纵必要留意：
（1）留意空间是否存在，否则无法头插
（2）头插必要判断空间是否充裕，通常是判断size+1的元素空间是否越界
然后经过这两个判断之后，举行头插，为了使代码效率高，我们选择从后往前举行挪动之前的数据，然后再举行插入，思维演示如下：

头插之前

头插之后 

1. //头插
2. void Head(List* Static, int data)
3. {
4.         //如果空间不存在则无法头插
5.         if (Static->arr == NULL)
6.         {
7.                 printf("空间不存在无法头插\n");
8.                 return;
9.         }
11.         //判断空间是否充足
12.         if (Static->size + 1 == Static->max)
13.         {
14.                 Extend(Static);
15.         }
17.         int end = Static->size - 1;
18.         //移动元素
19.         while (end >= 0)
20.         {
21.                 Static->arr[end + 1] = Static->arr[end];
22.                 end--;
23.         }
24.         //插入元素
25.         Static->arr[0] = data;
26.         Static->size++;
27. }

复制代码

 尾插

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

1. void Tail(List* Static, int data)
2. {
3.         //判断空间是否充裕
4.         if (Static->size + 1 == Static->max)
5.         {
6.                 Extend(Static);
7.         }
9.         //插入
10.         Static->arr[Static->size] = data;
11.         Static->size++;
12. }

复制代码

 头删

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

头删之前

头删之后

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

复制代码

尾删

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

尾删之后

1. void Tail_Omit(List* Static)
2. {
3.         //判断能否删除
4.         if (Static->size == 0)
5.         {
6.                 printf("删除失败\n");
7.                 return;
8.         }
10.         //删除
11.         Static->size--;
12. }

复制代码

 随机删除

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

删除之后

1. //随机删除（下标位置删除）
2. Random_Omit(List* Static, int under)
3. {
4.         //找对应下标的元素
5.         int end = 0;
6.         while (end < Static->size && Static->arr[end] != Static->arr[under])
7.         {
8.                 end++;
9.         }
10.         //如果没有找到
11.         if (end == Static->size)
12.         {
13.                 printf("该元素不存在\n");
14.                 return;
15.         }
16.         //将后面的元素向前挪动
17.         while (end < Static->size - 1)
18.         {
19.                 Static->arr[end] = Static->arr[end + 1];
20.                 end++;
21.         }
22.         //元素个数减一
23.         Static->size--;
24. }

复制代码

 随机插入

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

插入之后

1. //随机插入（下标位置插入）
2. void Random_Insert(List* Static, int under, int data)
3. {
4.         //先判断该下标是否支持插入
5.         int end = 0;
6.         while (end < Static->size && end != under)
7.         {
8.                 end++;
9.         }
10.         //如果没有找到
11.         if (Static->size == end)
12.         {
13.                 printf("该位置无法插入\n");
14.                 return;
15.         }
16.         //该下标位置及后面的元素后移
17.         end = Static->size-1;
18.         while (end != under)
19.         {
20.                 Static->arr[end] = Static->arr[end-1];
21.                 end--;
22.         }
23.         //插入
24.         Static->arr[under] = data;
25.         Static->size++;
26. }

复制代码

练习题一 

小编来大概解读一下这个题目：给你一个值，将一个数组中与这个值相等的元素移除，其余元素                                                      按次序前移
思维方法：
（1）这一种是最简单的一种：就是创建另外一个数组空间，将这些符合规定的值全部存到这个新数组内里，然后返回不即是这个值的元素个数，这是最平凡的写法，小编就不演示了啊！
（2）算法解法思想：我们可以接纳双指针的方法，通过指针的快慢移动，来处理即是val的值，如果在力扣上不方便调试，大家可以放在本身的编译器上去观察数据变革，重点是学会，不是求速通
例题详解：
首先我们设置2个下标（a，b），a就负责找差别于val的值，找到之后b地点的下标元素就即是a地点下标的值，然后a、b都向前移动一位，就这样循环就行了，留意a不能越界，下面我绘图演示
我用数组【0、1、2、2、3、0、4、2】，val=2做例子，大家对着图配上代码梳理一遍思路！

1. int removeElement(int* nums, int  numsSize, int val)
2. {
3.         int a = 0;
4.         int b = 0;
5.         int k = 0;
7.         while (a < numsSize)
8.         {
9.         //a找不同
10.                 while (a < numsSize && nums[a] == val)
11.                 {
12.                         a++;
13.                 }
14.                 if (a >= numsSize)
15.                 {
16.                         break;
17.                 }
18.         //填埋、后移
19.                 nums[b] = nums[a];
20.                 a++;
21.                 b++;
22.                 k++;
23.         }
24.         return k;
25. }

复制代码

练习题二

思维方法：
（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中去

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

复制代码

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

1. void merge(int* nums1, int m, int* nums2, int n)
2. {
3.         int m1 = m - n - 1;
4.         int n1 = n - 1;
5.        
6.         int num = m - 1;
8.         while (n1 >= 0 && m1 >= 0)
9.         {
10.                 if (nums2[n1] >= nums1[m1] && n1 >= 0 && m1 >= 0)
11.                 {
12.                         nums1[num] = nums2[n1];
13.                         n1--;
14.                         num--;
15.                 }
16.                 if (nums1[m1] >= nums2[n1] && n1 >= 0 && m1 >= 0)
17.                 {
18.                         nums1[num] = nums1[m1];
19.                         m1--;
20.                         num--;
21.                 }
22.         }
23.     //如果nums2中有元素剩余，就拷贝到nums1
24.         if (m1 < 0)
25.         {
26.                 memcpy(nums1, nums2, sizeof(int) * (n1 + 1));
27.         }
28. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4