文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据结构与算法】数据结构初阶：动态顺序表各种方法（接口函数）复盘与整理

【数据结构与算法】数据结构初阶：动态顺序表各种方法（接口函数）复盘与整理

作者头像
艾莉丝努力练剑
发布于 2025-11-12 19:11:44
发布于 2025-11-12 19:11:44
1060
举报
文章被收录于专栏：C / C++C / C++

前言：本篇文章，我们复盘顺序表和链表相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们继续学习第二部分中的顺序表和链表部分内容啦。

半个多月前，博主更新了头插、尾删、头删、随机位置插入、随机位置删除、查找、修改、菜单等内容，本篇文章，我们就来复盘一下动态顺序表的内容，博主会添加很多新内容，希望对大家的顺序表学习有所帮助。

备注：

1、dst——destination——目标数据；

代码语言：txt
复制
 src——source——源数据。

2、在指定位置之后插入数据：

代码语言：javascript
复制
void SLInsertAfter(SL* ps, int pos, SLTDataType x);

3、退出码不为0，就有问题了。

4、编写代码过程中要勤测试，避免写出大量代码后再测试而导致出现问题，问题定位无从下手。

5、我们在指定位置插入数据是碰到这种情况，将8插入到1的前面时，如下图：

这样看起来可能还不够清楚，博主画了图二，更加清晰——

接下来就不能挪了，因为我只把pos及之后的数据往后挪动，也就意味着当i刚好等于pos的时候我们就不能再挪动数据了。

总之，我们在1之前插入一个8，后面的元素往后挪了，1虽然往后挪了，但是——

也就是说，这个8是插入到这里之后把1给覆盖了，1挪走了，这里其实在被8覆盖前还是1。

目录

一、动态顺序表

（1）SeqList.h

（2）SeqList.c

（3）test.c

二、顺序表实践——三道算法题

（一）移除元素

1、思路

2.1.1.1 思路1：

2.1.1.2 思路2：双指针法，创建两个变量，dst和src

2、实现

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

1、思路

2.2.1.1 思路1：

2.2.1.2 思路2：双指针法

2、实现

（三）合并两个有序数组

1、直接看题解

2、重新复盘一遍

2.3.2.1 思路1：

2.3.2.2 思路2：我们从后往前遍历数组，找大的（谁大谁先往后放）

结尾

一、动态顺序表

我们之前非常详细地介绍了静态顺序表和动态顺序表，今天我们复盘一下顺序表部分的一些重要知识点。动态顺序表的方法有尾插、头插、尾删、头删、指定位置之前插入、指定位置之后插入、指定位置(pos)删除、销毁、查找、修改。

像SeqList.h一般有这些操作：

代码语言：javascript
复制
#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
SLDataType* a;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插⼊/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

下面我们看一下顺序表整体的实现：

（1）SeqList.h

代码语言：javascript
复制
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义动态顺序表的结构
typedef int SLTDataType;
typedef struct SeqList 
{
	SLTDataType* arr;  //存储数据
	int size;  //有效数据个数
	int capacity; //空间大小
}SL;

//typedef struct SeqList SL;

void SLPrint(SL* ps);
void SLInit(SL* ps);
void SLDestroy(SL* ps);

//尾插
void SLPushBack(SL* ps, SLTDataType x);

//头插
void SLPushFront(SL* ps, SLTDataType x);

//尾删
void SLPopBack(SL* ps);

//头删
void SLPopFront(SL* ps);

//查找
int SLFind(SL* ps, SLTDataType x);

//指定位置之前插入
void SLInsert(SL* ps, int pos, SLTDataType x);

//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLTDataType x);

//删除pos(指定)位置的数据
void SLErase(SL* ps, int pos);

//修改
void SLModity(SL* ps, int pos, SLTDataType x);

（2）SeqList.c

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#include"SeqList.h"

void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

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

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//增容
		SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLTDataType x)
{
	assert(ps);
	//空间不够
	SLCheckCapacity(ps);
	//空间足够
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLTDataType x)
{
	//温柔的处理方式
	//if (ps == NULL)
	//{
	//	return;
	//}
	assert(ps != NULL); //等价于assert(ps）
	//空间不够
	SLCheckCapacity(ps);
	//数据整体向后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);
	ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	//数据整体向前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLTDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//未找到
	return -1;
}
//指定位置之前插入
void SLInsert(SL* ps, int pos, SLTDataType x)
{
	assert(ps);
	//0<= pos < ps->size
	assert(pos >= 0 && pos < ps->size);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//pos及之后数据向后挪动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLTDataType x)
{
	assert(ps);
	//0<= pos < ps->size
	assert(pos >= 0 && pos < ps->size);
	//判断空间是否足够
	SLCheckCapacity(ps);
	ps->arr[pos] = x;
	ps->size++;
}

//删除pos位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//pos:[0，ps->size)
	assert(pos >= 0 && pos < ps->size);

	//pos后面的数据向前挪动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//修改
void SLModity(SL* ps, int pos, SLTDataType x) 
{
	assert(pos < ps->size);
	ps->arr[pos] = x;
}

（3）test.c

代码语言：javascript
复制
#define  _CRT_SECURE_NO_WARNINGS  1

#include"SeqList.h"

void test01()
{
	SL sl;
	SLInit(&sl);

	//具备了一个空的顺序表
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	//SLPushFront(&sl, 1);
	//SLPushFront(&sl, 2);//2 1
	//SLPushFront(&sl, 3);//3 2 1
	//SLPushFront(&sl, 4);//4 3 2 1
	//SLPopBack(&sl);
	//SLPrint(&sl);//1 2 3
	//SLPopBack(&sl);
	//SLPrint(&sl);//1 2 
	//SLPopBack(&sl);
	//SLPrint(&sl);//1 
	//SLPopBack(&sl);
	//SLPrint(&sl);//
	//SLPopBack(&sl);

	////头删
	//SLPopFront(&sl);
	//SLPrint(&sl);
	//SLPopFront(&sl);
	//SLPrint(&sl);
	//SLPopFront(&sl);
	//SLPrint(&sl);
	//SLPopFront(&sl);
	//SLPrint(&sl);

	//SLPopFront(&sl);

	//测试查找
	int pos = SLFind(&sl, 3);
	//if (pos < 0)
	//{
	//	printf("未找到！\n");
	//}
	//else 
	// {
	//	printf("找到了！\n");
	//}
	//SLInsert(&sl, pos, 100);
	//SLPrint(&sl);
	//SLInsert(&sl, pos, 200);
	//SLPrint(&sl);
	//SLInsert(&sl, pos, 300);
	//SLPrint(&sl);
	//SLInsert(&sl, pos, 400);
	//SLPrint(&sl);
	SLErase(&sl, pos);
	SLPrint(&sl);

	SLDestroy(&sl);
}

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

当我们以后要用顺序表去存储数据，我们还用不用写插入、删除、查找、修改的操作？不需要了，我们直接去使用这个结构体本身就已经实现好的方法就可以了，这就是数据结构存在的意义。

二、顺序表实践——三道算法题

我们学习了顺序表之后，也该练练手了。这里博主准备了三道来自力扣的算法题，大家先想想，看看有什么思路，如果没有什么思路，就把图画一画，想清楚了再敲代码。

每道题的标题下面附上了题目的网址。

由于这些力扣题博主在力扣网站上都发了题解，故在此就不多赘言了。博主会把博主在力扣写的题解的网址一并挂在每道题目的题目截图下面，大家可以去链接那儿一头看看，非常详细。

为了方便uu们看题解，博主把三道题的力扣题解链接放在下面的块引用里面了——

题解：用双指针解决移除元素问题且时间复杂度O(n)空间复杂度O(1) 题解：双指针求解删除有序数组中的重复项 题解：双指针求解合并两个有序数组（利用有序的特性）

（一）移除元素

27,移除元素

题目描述：

题给示例：

题目提示：

1、思路
2.1.1.1 思路1：

申请新数组，遍历原数组，将不为val的值依次放入新数组中，再将新数组的数据导入原数组中。

复杂度：时间复杂度O(N)、空间复杂度O(N)

下面这不是一个伪代码——

for(遍历+放数据) for(导入原数组)

2.1.1.2 思路2：双指针法，创建两个变量，dst和src

1）如果src指向的数据是val，那么src++；

2）如果src指向的数据不是val，赋值(src给dst)，src和dst都++。

如下图所示——

src在前面探路（找出非val值）；dst在后面站岗（保存非val值） 。

2、实现

代码演示：

代码语言：javascript
复制
int removeElement(int* nums, int numsSize, int val) 
{
    int dst = 0;
    int src = 0;
    while(src < numsSize)
    {
        if(nums[src] != val)
        {
            nums[dst++] = nums[src++];
        }
        else
        {
            src++;
        }
    }
    return dst;
}

题解：用双指针解决移除元素问题且时间复杂度O(n)空间复杂度O(1)

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

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

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

题目描述：

题给示例：

题目提示：

1、思路
2.2.1.1 思路1：

创建一个新数组，遍历原数组，将不重复数据导入到原数组中，再将新数组中的数据导入到原数组当中，也是一种思路。

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

2.2.1.2 思路2：双指针法

我们创建两个变量dst和src，把dst和src错开，即创建两个变量，分别指向数组起始下一个位置，可知src=dst+1，分两种情况讨论：（1）如果src和dst值相等，src++；（2）如果src和dst值不相等，dst++，赋值，src++。注意：使用双指针方法的前提是有序数组，如果这是无序数组，就不能用这个方法了。

2、实现

代码演示：

代码语言：javascript
复制
// int removeDuplicates(int* nums, int numsSize) 
// {
//     int dst = 0,src = dst + 1;
//     while(src < numsSize)
//     {
//         if(nums[src] != nums[dst])
//         {
//             //src和dst值相等，src++
//             //src和dst值不相等，dst++，赋值，src++
//             dst++;
//             nums[dst] = nums[src];
//         }
//         src++;
//     }
//     return dst+1;
// }

//优化
int removeDuplicates(int* nums, int numsSize) 
{
    int dst = 0,src = dst + 1;
    while(src < numsSize)
    {
        if(nums[src] != nums[dst])
        {
            if(++dst != src)
            {
                nums[dst] = nums[src];
            }
        }
        src++;
    }
    return dst+1;
}

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

我们可以再优化一下——

代码语言：javascript
复制
// int removeDuplicates(int* nums, int numsSize) 
// {
//     int dst = 0,src = dst + 1;
//     while(src < numsSize)
//     {
//         if(nums[src] != nums[dst])
//         {
//             dst++;
//             nums[dst] = nums[src];
//         }
//         src++;
//     }
//     return dst+1;
// }

//优化
// int removeDuplicates(int* nums, int numsSize) 
// {
//     int dst = 0,src = dst + 1;
//     while(src < numsSize)
//     {
//         if(nums[src] != nums[dst])
//         {
//             if(++dst != src)
//             {
//                 nums[dst] = nums[src];
//             }
//         }
//         src++;
//     }
//     return dst+1;
// }

//再进一步优化
int removeDuplicates(int* nums, int numsSize) 
{
    int dst = 0,src = dst + 1;
    while(src < numsSize)
    {
        if(nums[src] != nums[dst] && ++dst != src)
        {
            nums[dst] = nums[src];
        }
        src++;
    }
    return dst+1;
}

题解：双指针求解删除有序数组中的重复项

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

（三）合并两个有序数组

88.合并两个有序数组

1、直接看题解

题目描述：

题给示例：

题目提示：

代码演示：

代码语言：javascript
复制
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;
        }
    }
        while(end2 >= 0)
        {
            nums1[end] = nums2[end2];
            --end;
            --end2;
        }
}

题解：双指针求解合并两个有序数组（利用有序的特性）

复杂度：时间复杂度O(m+n)，空间复杂度O(1) 。

2、重新复盘一遍

我们先看看可以怎么做——

2.3.2.1 思路1：

一种思路是我们先合并数组，再对nums1进行排序，不管是qsort排序也好，还是冒泡排序也好，总之思路1就是先合并再排序，这样也是一种思路，我们算一下，用冒泡排序的时间复杂度是O(N^2)，这是非常大的时间复杂度了，我们尽量不去写，我们想想还有没有什么思路？

2.3.2.2 思路2：我们从后往前遍历数组，找大的（谁大谁先往后放）

我们创建三个变量，l1、l2、l3，m、n是个数，-1之后才是下标，l1、l2、l3对应的是下标，都-1，

我们分这么几步：

1、比较谁大，谁大谁往后放——l1位置比l2大，l3位置放l1，l1、l3都--；否则放l2。 2、越界分三种情况讨论——l1越界（l2没有越界，需要特殊处理）、l2越界（不需要处理）、l1和l2同时越界（不存在，l1、l2一定是有先后的）。

代码演示：

代码语言：javascript
复制
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int l1 = m - 1;
    int l2 = n - 1;
    int l3 = m + n - 1;
    while(l1 >= 0 && l2 >= 0)
    {
        //比较谁大，谁大谁往后放
        if(nums1[l1] > nums2[l2])
        {
            nums1[l3--] = nums1[l1--];
        }
        else
        {
            nums1[l3--] = nums2[l2--];
        }
    }
    //l1越界（l2没有越界，需要特殊处理）
        while(l2 >= 0)
        {
            nums1[l3--] = nums2[l2--];
        }
    //l2越界（不需要处理）
    //l1、l2同时越界（不存在，l1、l2一定是有先后的）
}

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

结尾

往期回顾：

【数据结构与算法】数据结构初阶：详解顺序表和链表（二）

【数据结构与算法】数据结构初阶：详解顺序表和链表（一）

【数据结构】详解算法复杂度：时间复杂度和空间复杂度

本期内容需要回顾的C语言知识放在下面了（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了），大家如果对前面部分的知识点印象不深，可以去看看：

【动态内存管理】深入详解：malloc和free、calloc和realloc、常见的动态内存的错误、柔性数组、总结C/C++中程序内存区域划分

【自定义类型：结构体】：类型声明、结构体变量的创建与初始化、内存对齐、传参、位段

C语言指针深入详解（六）：sizeof和strlen的对比，【题解】数组和指针笔试题解析、指针运算笔试题解析

【深入详解】函数栈帧的创建与销毁：寄存器、压栈、出栈、调用、回收空间

结语：本篇文章到这里就结束了，对数据结构的顺序表知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-09-01，如有侵权请联系 cloudcommunity@tencent.com 删除
数组
指针
数据结构
数据
数据结构与算法

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数组
指针
数据结构
数据
数据结构与算法
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一、动态顺序表
    • （1）SeqList.h
    • （2）SeqList.c
    • （3）test.c
  • 二、顺序表实践——三道算法题
    • （一）移除元素
      • 1、思路
      • 2、实现
    • （二）删除有序数组中的重复项
      • 1、思路
      • 2、实现
    • （三）合并两个有序数组
      • 1、直接看题解
      • 2、重新复盘一遍
  • 结尾
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论