【算法通关指南：数据结构与算法篇（一）】搞懂顺序表，数据结构入门第一步！C++ 模拟实现与全操作代码

小龙报

发布于 2025-12-15 15:56:57

1940

文章被收录于专栏：C\C++C\C++

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力 ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长

一、顺序表的概念

1.1 线性表的定义

线性表是n 个具有相同特性的数据元素的有序序列。线性表在逻辑上可以想象成是连续的⼀条线段，线段上有很多个点，⽐如下图：

故线性表是⼀个比较简单和基础的数据结构

1.2 线性表的顺序存储-顺序表

线性表的顺序存储就是顺序表。如果下图中的方格代表内存中的存储单元，那么存储顺序表中这个元素就是放在连续的位置上：

⼤家会发现，这不就是⽤⼀个数组把这些元素存储起来了嘛？是的，顺序表就是通过数组来实现的。

二、顺序表的模拟实现

PS：往后实现各种数据结构的时候，如果不做特殊说明，默认里面存储的就是int类型的数据。

2.1创建

//创建
const int N = 1e5 + 10;  // 定义静态数组的最⼤⻓度 
int a[N],n;  // 直接创建⼀个⼤数组来实现顺序表， n 表⽰当前有多少个元素

2.2添加⼀个元素

2.2.1尾插

//尾插
void puch_back(int x)
{
	a[++n] = x;   // 下标为 0 的位置空出来 
	
	// 这样操作⼀般根据个⼈习惯，也可以从 0 开始计数 
    // 不过有些问题从 1 计数，处理起来可以不⽤考虑边界情况 
   // 后续学习更深的算法的时候，就会感受到 
}

时间复杂度： 直接放在后⾯即可，时间复杂度为O(1)

2.2.2头插

//头插
void puch_front(int x)
{
	// 要把所有的元素全部右移⼀位，然后再放到头部位置 
	for (int i = n; i >= 1; i--)
	{
		a[i + 1] = a[i];
	}

	a[1] = x;// 把 x 放在⾸位 
	n++; //不要忘记总个数 +1 
}

时间复杂度： 由于需要将所有元素右移⼀位，时间复杂度为O(N) 。

2.2.3任意位置插入

// 任意位置插⼊ - 在位置 p 处，插⼊⼀个 x 
void  insert(int x, int p)
{
	for (int i = n; i >= p; i--)  // 注意顺序不要颠倒 
	{
		a[i + 1] = a[i];
	}

	a[p] = x;
	n++;   //// 不要忘记总个数 +1 
}

时间复杂度： 最坏情况下需要数组中所有元素右移，时间复杂度为O(N) 。

2.3删除⼀个元素

2.3.1尾删

//尾删
void pop_back()
{
	n--;
}

时间复杂度： 显然是O(1) 。

2.3.2头删

//头删
void pop_front()
{
	// 把所有元素向前移动⼀位 
	for (int i = 2; i <= n; i++)
	{
		a[i - 1] = a[i];
	}
	n--;   // 总个数 -1 
}

时间复杂度： 需要所有元素整体左移，时间复杂度为O(N) 。

2.3.3任意位置删

//任意位置删
void erase(int p)
{
	//把所有元素向前移动⼀位
	for (int i = p + 1; i <= n; i++)
	{
		a[i - 1] = a[i];
	}
	n--;   // 总个数 -1 
}

时间复杂度： 最坏情况下，所有元素都需要左移，时间复杂度为O(N) 。

2.4查找元素

2.4.1按值查找

// 查找这个数第⼀次出现的位置，找不到返回 0 
int find(int x)
{
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == x)
			return i;
	}
	return 0;
}

时间复杂度： 最坏情况下需要遍历整个数组，时间复杂度为O(N) 。

2.4.2按位置查找

// 返回 p 位置的数
int at(int p)
{
	return a[p];
}

时间复杂度： 这就是顺序表随机存取的特性，只要给我⼀个下标，就能快速访问到该元素。时间复杂度为O(1) 。

2.5 修改元素

// 把 p 位置的数修改成 x 
void change(int p, int x)
{
	a[p] = x;
}

时间复杂度： 这就是顺序表随机存取的特性，只要给我⼀个下标，就能快速访问到该元素。时间复杂度为O(1) 。

2.6 清空顺序表

// 清空顺序表 
void clear()
{
	n = 0;
}

时间复杂度： 要注意，我们⾃⼰实现的简单形式是O(1) 。但是，严谨的⽅式应该是O(N) 。

2.7所有测试代码

#include <iostream>
using namespace std;

//创建
const int N = 1e5 + 10;  // 定义静态数组的最⼤⻓度 
int a[N],n;  // 直接创建⼀个⼤数组来实现顺序表， n 表⽰当前有多少个元素    

//打印
void print()
{
	for (int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << endl;
}

//尾插
void push_back(int x)
{
	a[++n] = x;   // 下标为 0 的位置空出来 
	// 这样操作⼀般根据个⼈习惯，也可以从 0 开始计数 
    // 不过有些问题从 1 计数，处理起来可以不⽤考虑边界情况 
   // 后续学习更深的算法的时候，就会感受到 

}

//头插
void push_front(int x)
{
	// 要把所有的元素全部右移⼀位，然后再放到头部位置 
	for (int i = n; i >= 1; i--)
	{
		a[i + 1] = a[i];
	}

	a[1] = x;// 把 x 放在⾸位 
	n++; //不要忘记总个数 +1 
}

// 任意位置插⼊ - 在位置 p 处，插⼊⼀个 x 
void  insert(int x, int p)
{
	for (int i = n; i >= p; i--)  // 注意顺序不要颠倒 
	{
		a[i + 1] = a[i];
	}

	a[p] = x;
	n++;   //// 不要忘记总个数 +1 
}

//尾删
void pop_back()
{
	n--;
}

//头删
void pop_front()
{
	// 把所有元素向前移动⼀位 
	for (int i = 2; i <= n; i++)
	{
		a[i - 1] = a[i];
	}
	n--;   // 总个数 -1 
}

//任意位置删
void erase(int p)
{
	//把所有元素向前移动⼀位
	for (int i = p + 1; i <= n; i++)
	{
		a[i - 1] = a[i];
	}
	n--;   // 总个数 -1 
}

// 查找这个数第⼀次出现的位置，找不到返回 0 
int find(int x)
{
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == x)
			return i;
	}
	return 0;
}

// 返回 p 位置的数
int at(int p)
{
	return a[p];
}

// 把 p 位置的数修改成 x 
void change(int p, int x)
{
	a[p] = x;
}

// 清空顺序表 
void clear()
{
	n = 0;
}

int main()
{
	// 测试尾插 
	push_back(2);
	print();
	push_back(5);
	print();
	push_back(1);
	print();
	push_back(3);
	print();
	// 测试头插 
	push_front(10);
	print();
	// 测试任意位置插⼊ 
	insert(3, 0);
	print();
	 //测试尾删 
	 cout << "尾删：" << endl; 
	 pop_back();
	 print();
	 pop_back();
	 print();
	 pop_front();
	 pop_front();
	 print();
	 //测试任意位置删除 
	 cout << "任意位置删除：" << endl; 
	 erase(3);
	 print();
	 erase(2);
	 print();
	 erase(4);
	 print();
		for (int i = 1; i <= 10; i++)
		{
			cout << "查找" << i << ": ";
			cout << find(i) << endl;

	return 0;
}

总结

希望大家多多支持，我们下期再见！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-29，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

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

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

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

登录后参与评论

0 条评论

热度