【数据结构初阶】--顺序表(二)

发布于：2025-07-13 ⋅ 阅读:(18) ⋅ 点赞:(0)

 

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。  

 前言：各位朋友们，从今天开始博主将恢复数据结构与算法专栏的更新，为大家分享数据结构初阶相关知识，用C语言与大家一起实现一些数据结构，那么我们这篇文章将会接着上次顺序表的初始化继续往后详细实现顺序表的头插，尾插，头删，尾删等功能。那么这里特别声明一下，博主会将这些功能分开实现，最后再单独为大家呈现本节所有内容的完整代码。

目录

一.顺序表的尾插

二.顺序表的头插

三.顺序表的尾删 

四.顺序表的头删

五.代码展现以及时间复杂度对比

SeqList.h：

SeqList.c： 

test.c： 

尾插，头插，尾删，头删时间复杂度对比：

一.顺序表的尾插

--这里分布实现的时候主要展示SeqList.c文件和test.c文件，头文件这里就不展示了。

SeqList.c：

//尾插
void SLPushBack(SL* ps, SLTDataType x)
{
	//空间不够
	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");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}

	//空间足够
	ps->arr[ps->size++] = x;//插入完后，size往后走
}

 重点提示： 

增容：我们一般成倍数增加，最好是两倍。这样可以有效降低增容的次数，就算可能会存在空间的浪费，但是不会太多。

我们再来看看在此过程中要注意的一些问题：

为了方便观察，我们再来实现一个打印顺序表的函数，很简单，这里就不解释了 

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

test.c： 

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);//1
	SLPushBack(&s, 2);//12
	SLPushBack(&s, 3);//123
	SLPushBack(&s, 4);//1234
	SLPrint(&s);//1 2 3 4

}

int main()
{
	test1();
}

--测试结果如下，成功打印出了经过4次尾插之后的顺序表

二.顺序表的头插

--头插和尾插都离不开空间的检查增容，所以我们在实现尾插之前可以直接用一个函数实现空间的检查，后续需要时直接复用就可以了。

//检查空间
void SLCheckCapacity(SL*ps)
{
	//扩容
	int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
	SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, newcapacity * sizeof(SLdatatype));
	if (tmp == NULL)
	{
		perror("realloc");
		exit(1);
	}
	ps->arr = tmp;
	ps->capacity = newcapacity;
}

 SeqList.c：

//头插
void SLPushFront(SL* ps, SLdatatype x)
{
    assert(ps);//ps！=NULL
	//检查空间是否足够
	SLCheckCapacity(ps);
	//空间足够
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

 重点提示：

这里其实没啥坑了，该说的我们都在前面说过了，值得注意的就是头插，顺序表中的其它元素一定是从后往前的顺序向后移动一位，如图所示。再就是利用assert断言判断ps不为空了，用if也可以这里就不演示了。

test.c： 

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	SLPushFront(&s, 5);
	SLPrint(&s);// 5 1 2 3 4
}

int main()
{
	test1();
}

--测试出来也没啥问题，在前面头插了一个5。 

三.顺序表的尾删 

--顺序表的尾删其实就很简单了，大家可以想想我们是使用free释放掉还是令ps->arr[ps->size-1]=0，然后ps->size--呢？其实两者都不需要，直接ps->size--就结束了，不需要其它的过程。

 SeqList.c：

//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);
	ps->size--;
}

重点提示： 

尾删这里直接就是ps->size--就可以了，不用其它的操作了。这里断言的时候注意ps->size也不能为0就行，不然删除不了。

test.c： 

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	SLPushFront(&s, 5);
	SLPrint(&s);// 5 1 2 3 4
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);// 5 1 2
}

int main()
{
	test1();
}

--测试之后没问题，尾删掉了两个数据，打印出来结果为5 1 2

四.顺序表的头删

SeqList.c：

//头删
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--;
}

重点提示： 

头删的断言和尾删一样，值得注意的是我们需要将数据按从前往后的顺序依次向前移动一位，注意最后循环的终止条件是i=ps->size-1，所以循环进行的条件就是i<ps->size-1。如图所示，1覆盖掉了原来的5。实现了头删，删除完后ps->size--就可以了。

test.c： 

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	SLPushFront(&s, 5);
	SLPrint(&s);// 5 1 2 3 4
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);// 5 1 2
	SLPopFront(&s);
	SLPrint(&s);//1 2
}

int main()
{
	test1();
}

--测试没有问题，头删掉一个5，最终结果打印出来是正确的

五.代码展现以及时间复杂度对比

SeqList.h：

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

typedef int SLdatatype;
typedef struct SeqList
{
	SLdatatype* arr;
	int size;
	int capacity;
}SL;

//顺序表初始化
void SLInit(SL* ps);

//打印顺序表
void SLPrint(SL* ps);

//尾插
void SLPushBack(SL* ps, SLdatatype x);
//头插
void SLPushFront(SL* ps, SLdatatype x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);

SeqList.c： 

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	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)
{
	//扩容
	int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
	SLdatatype* tmp = (SLdatatype*)realloc(ps->arr, newcapacity * sizeof(SLdatatype));
	if (tmp == NULL)
	{
		perror("realloc");
		exit(1);
	}
	ps->arr = tmp;
	ps->capacity = newcapacity;
}

//尾插
void SLPushBack(SL* ps, SLdatatype x)
{
	//检查空间是否足够
	SLCheckCapacity(ps);
	//空间足够
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLdatatype x)
{
	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--;
}

test.c： 

#include"SeqList.h"

void test1()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);//1 2 3 4
	SLPushFront(&s, 5);
	SLPrint(&s);// 5 1 2 3 4
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);// 5 1 2
	SLPopFront(&s);
	SLPrint(&s);//1 2
}

int main()
{
	test1();
}

尾插，头插，尾删，头删时间复杂度对比：

结论：我们通过对比可以看出顺序表的尾插，尾删的时间复杂度比头插，头删要好很多，所有我们可以看出如果操作尾部数据比较多的话，顺序表这个数据结构是比较优秀的。 

往期回顾：

【数据结构初阶】--算法复杂度的深度解析

【数据结构初阶】--顺序表(一)

结语：继上篇博客中我们实现的动态顺序表的初始化后，在本篇中我们完成了顺序表的尾插，头插，尾删，头删这四个接口的实现，那么顺序表的实现我们其实还没完全完成，博主将会在后续的博客中继续和大家一起实现顺序表中指定位置的插入和删除以及查找和修改这四个接口，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布