数据结构_顺序表_尾插、尾删、头插、头删(附带详解)
前言
顺序表_尾插、尾删、头插、头删
一. 线性表
二. 顺序表 - - - 数组
2.1 什么是顺序表
- 顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
- 顺序表可动态增长的数组，要求数据是连续存储的。
2.2 顺序表一般可以分为
2.2.1 静态顺序表（使用定长数组存储元素）
- 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
- 所以基本使用动态顺序表，根据需要，动态的分配空间大小。 缺陷：给小了不够用，给大了，不实用。
2.2.2 动态顺序表：使用动态开辟的数组存储
- 动态顺序表可根据我们的需要分配空间
- size 表示当前顺序表中已存放的数据个数
- capacity 表示顺序表总共能够存放的数据个数
2.2.3 顺序表的接口实现
先建一个工程（此次用的是vs2019)用的是动态顺序表
- SeqList.h (顺序表的类型定义、接口函数声明、引用的头文件)
- SeqList.h （顺序表接口函数的实现）
- Test.c (主函数、测试顺序表各个接口功能)
- SeqList.h 头文件代码：
#pragma once // 防止头文件被二次引用
#include<stdio.h>
#include<assert.h> //assert
#include<stdlib.h> //realloc
typedef int SLDataType; //后续要存储其他类型时方便更改
//顺序表的动态存储
typedef struct SeqList
{
SLDataType* a;//指向动态开辟数组
size_t size; //有效数据个数
size_t capacity;//容量大小
}SeqList;
//初始化顺序表
void SeqListInit(SeqList* ps1);
//销毁顺序表
void SeqListDestory(SeqList* ps1);
//检查顺序表容量是否满了，好进行增容
void CheckCapacity(SeqList* ps1);
//顺序表尾插
void SeqListPushBack(SeqList* ps1, SLDataType x);//O(1)
//顺序表尾删
void SeqListPopBack(SeqList* ps1);//O(1)
//顺序表头插
void SeqListPushFront(SeqList* ps1, SLDataType x);//O(n)
//顺序表头删
void SeqListPopFront(SeqList* ps1);//O(n)
//打印顺序表
void SeqListPrint(const SeqList* ps1);
//在顺序表中查找指定的值
int SeqListFind(const SeqList* ps1, SLDataType x);
//在顺序表指定下标位置插入数据
void SeqListInsert(SeqList* ps1, size_t pos, SLDataType x);
//在顺序表中删除指定下标位置的数据
void SeqListErase(SeqList* ps1, size_t pos);
//查看顺序表中数据个数
size_t SeqListSize(const SeqList* ps1);
//修改指定下标位置的数据
void SeqListAt(SeqList* ps1, size_t pos, SLDataType x);三. SeqList.c 中各个接口的实现。
3.1 初始化顺序表
（要加上断言，防止传进来的指针为空）
void SeqListInit(SeqList* psl)
{
assert(psl != NULL);//断言
psl->a = NULL; //初始顺序表为空
psl->size = 0; //初始数据个数为0
psl->capacity = 0; //初始空间容量为0
}3.2 销毁（释放）顺序表
（也是要加上断言，防止传进来的指针为空）
//销毁（释放）顺序表
void SeqListDestory(SeqList* ps1)
{
assert(ps1 != NULL);//断言
free(ps1->a); //释放动态开辟的空间
ps1->a = NULL;//置空
ps1->size = 0;//数据个数置零
ps1->capacity = 0;//空间容量大小置零
}3.3 检查顺序表容量是否满了，好进行增容
多少倍都可以，不过一般扩2倍。2倍、1.5倍、是比较合适的方案。
void CheckCapacity(SeqList* ps1)//检查顺序表容量是否已满
{
//满了则扩容
if (ps1->size == ps1->capacity)
{
size_t Newcapacity;//新容量
if (ps1->capacity == 0)
Newcapacity = ps1->capacity = 4;//原来容量为零，扩容为4
else
Newcapacity = 2 * ps1->capacity;//原来容量不为0，扩容为原来2倍
SLDataType* p = (SLDataType*)realloc(ps1->a, Newcapacity * sizeof(SLDataType));//扩容
if (p == NULL)
{
perror("realloc");
exit(-1);
}
ps1->a = p;// P不为空、开辟成功
ps1->capacity = Newcapacity;//
//ps1->capacity *= 2;
}
}3.4 realloc 原地扩容、异地扩容
异地扩容，会帮你把原数据拷贝过去，并且原空间会释放
3.5 顺序表尾插
void SeqListPushBack(SeqList* ps1, SLDataType x)
{
assert(ps1 != NULL);
CheckCapacity(ps1); // 检查顺序表容量是否已满,满了则扩容
ps1->a[ps1->size] = x; //尾插数据
ps1->size++;//有效数据个数+1
}测试
void SeqListPrint(const SeqList* ps1)
{
int i = 0;
for (i = 0; i < ps1->size; i++)
{
printf("%d ", ps1->a[i]);
}
}
void TestSeqList1()
{
SeqList s1;
//初始化顺序表
SeqListInit(&s1);
//尾差数据
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPushBack(&s1, 6);
SeqListPrint(&s1);
SeqListDestory(&s1);
}
int main()
{
TestSeqList1();
return 0;
}3.6 顺序表尾删
SLDataType 不知道是什么类型的数据，不能冒然的将顺序表最后一个数据赋值为 0，我们只需将有效数据个数 size 减 1 即可达到尾删的目的。
void SeqListPopBack(SeqList* ps1 )
{
assert(ps1 !=NULL);
assert(ps1->size > 0);//顺序表不能为空
ps1->size--; //有效数据个数-1
}测试结果
完整代码
//尾删
void SeqListPushBack(SeqList* ps1, SLDataType x)
{
assert(ps1 != NULL);
CheckCapacity(ps1); // 检查顺序表容量是否已满,满了则扩容
ps1->a[ps1->size] = x; //尾插数据
ps1->size++;//有效数据个数+1
}
void SeqListPrint(const SeqList* ps1)
{
int i = 0;
for (i = 0; i < ps1->size; i++)
{
printf("%d ", ps1->a[i]);
}
printf("\n");
}
void SeqListPopBack(SeqList* ps1 )
{
assert(ps1 !=NULL);
assert(ps1->size > 0);//顺序表不能为空
ps1->size--; //有效数据个数-1
}
void TestSeqList1()
{
SeqList s1;
//初识化顺序表
SeqListInit(&s1);
//尾插数据
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPrint(&s1);
//尾删数据
SeqListPopBack(&s1);
SeqListPrint(&s1);
SeqListPopBack(&s1);
SeqListPrint(&s1);
SeqListDestory(&s1);
}
int main()
{
TestSeqList1();
return 0;
}3.7 顺序表头插
顺序表是连续的，所以头插时要依次挪动数据
//头插
void SeqListPushFront(SeqList* ps1, SLDataType x)
{
assert(ps1);
CheckCapacity(ps1);
int i = 0;
for (i = ps1->size - 1; i >= 0; i--)
{
ps1->a[i + 1] = ps1->a[i];
}
ps1->a[0] = x;//头插数据
ps1->size++;
}测试结果
完整代码
//头插
void SeqListPushFront(SeqList* ps1, SLDataType x)
{
assert(ps1);
CheckCapacity(ps1);
int i = 0;
for (i = ps1->size - 1; i >= 0; i--)
{
ps1->a[i + 1] = ps1->a[i];
}
ps1->a[0] = x;//头插数据
ps1->size++;
}
void SeqListPushBack(SeqList* ps1, SLDataType x)
{
assert(ps1 != NULL);
CheckCapacity(ps1); // 检查顺序表容量是否已满,满了则扩容
ps1->a[ps1->size] = x; //尾插数据
ps1->size++;//有效数据个数+1
}
void TestSeqList1()
{
SeqList s1;
//初始化顺序表
SeqListInit(&s1);
//尾插数据
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPrint(&s1);
//头插数据
SeqListPushFront(&s1, 11);
SeqListPushFront(&s1, 22);
SeqListPushFront(&s1, 33);
SeqListPrint(&s1);
SeqListDestory(&s1);
}
void SeqListPrint(const SeqList* ps1)
{
int i = 0;
for (i = 0; i < ps1->size; i++)
{
printf("%d ", ps1->a[i]);
}
printf("\n");
}
int main()
{
TestSeqList1();
return 0;
}3.8 顺序表头删
顺序表是连续的，头删时要依次挪动数据
//头删
void SeqListPopFront(SeqList* psl)
{
assert(psl); //断言
assert(psl->size > 0); //顺序表不能为空
int i = 0;
for (i = 1; i < psl->size; i++) //顺序表中[1,size-1]的元素依次向前挪动一位
{
psl->a[i - 1] = psl->a[i];
}
psl->size--; //有效数据个数-1
}测试结果
完整代码
void SeqListPushBack(SeqList* ps1, SLDataType x)
{
assert(ps1 != NULL);
CheckCapacity(ps1); // 检查顺序表容量是否已满,满了则扩容
ps1->a[ps1->size] = x; //尾插数据
ps1->size++;//有效数据个数+1
}
void SeqListPrint(const SeqList* ps1)
{
int i = 0;
for (i = 0; i < ps1->size; i++)
{
printf("%d ", ps1->a[i]);
}
printf("\n");
}
//头删
void SeqListPopFront(SeqList* psl)
{
assert(psl); //断言
assert(psl->size > 0); //顺序表不能为空
int i = 0;
for (i = 1; i < psl->size; i++) //顺序表中[1,size-1]的元素依次向前挪动一位
{
psl->a[i - 1] = psl->a[i];
}
psl->size--; //有效数据个数-1
}
void TestSeqList1()
{
SeqList s1;
//初始化顺序表
SeqListInit(&s1);
//尾插数据
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
SeqListPrint(&s1);
//头删数据
SeqListPopFront(&s1);
SeqListPopFront(&s1);
SeqListPrint(&s1);
SeqListDestory(&s1);
}
int main()
{
TestSeqList1();
return 0;
}四. 打印顺序表
五. 在顺序表中查找指定值
int SeqListFind(const SeqList* ps1, SLDataType x)
{
assert(ps1);
int i = 0;
for (i = 0; i < ps1->size; i++)
{
if (ps1->a[i] == x)
{
return i; //找到，返回该值下标
}
}
return -1; //没找到
}测试结果
完整代码
int SeqListFind(const SeqList* ps1, SLDataType x)
{
assert(ps1);
int i = 0;
for (i = 0; i < ps1->size; i++)
{
if (ps1->a[i] == x)
{
return i; //找到，返回该值下标
}
}
return -1; //没找到
}
void SeqListPushBack(SeqList* ps1, SLDataType x)
{
assert(ps1 != NULL);
CheckCapacity(ps1); // 检查顺序表容量是否已满,满了则扩容
ps1->a[ps1->size] = x; //尾插数据
ps1->size++;//有效数据个数+1
}
void TestSeqList1()
{
SeqList s1;
//初始化顺序表
SeqListInit(&s1);
//尾插数据
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 5);
SeqListPushBack(&s1, 7);
SeqListPushBack(&s1, 9);
//查找指定数据
int ret = SeqListFind(&s1, 7);
if (ret == -1)
printf("没找到\n");
else
printf("x=%d\n", s1.a[ret]);
SeqListDestory(&s1);
}
int main()
{
TestSeqList1();
return 0;
}六. 在顺序表指定下标位置插入数据
void SeqListInsert(SeqList* ps1, size_t pos, SLDataType x)
{
assert(ps1);
assert(pos >= 0 && pos <= ps1->size);//先检查pos下标的合法性
CheckCapacity(ps1);
size_t i = 0;
for (i = ps1->size; i > pos; i--)//将pos位置后面的数据依次向后挪动一位
{
ps1->a[i] = ps1->a[ i - 1];
}
ps1->a[pos] = x;
ps1->size++;
}测试结果
七. 在顺序表中删除指定下标位置的数据
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(psl->size > 0); //顺序表不能为空
assert(pos >= 0 && pos < psl->size); //检查pos下标的合法性
size_t i = 0;
for (i = pos + 1; i < psl->size; i++) //将pos位置后面的数据依次向前挪动一位
{
psl->a[i - 1] = psl->a[i];
}
psl->size--; //有效数据个数-1
}测试结果
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2023-10-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。