数据结构-顺序表（2）

news/2025/2/13 6:28:39/

目录

1. 线性表

2. 顺序表

2.1 动态顺序表

3. 接口实现

前期工作

3.1 初始化、销毁与检查容量

3.1.1 初始化

3.1.2 销毁

3.1.3 检查容量

3.2 尾插

3.3 尾删

3.4 头插

3.5 头删

3.6 插入

3.7 删除

顺序表源码

SeqList.h

SeqList.c

test.c

写在最后：

1. 线性表

线性表是n个具有相同特性的数据元素的有限序列，

常见的线性表：顺序表、链表、栈、队列、字符串等等。

2. 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。

2.1 动态顺序表

我们一般使用的都是动态的顺序表。

3. 接口实现

前期工作

在VS上建三个工程文件，

test.c用来测试顺序表；

SeqList.c用来实现接口；

SeqList.h用来包头文件，和创建动态顺序表的基本结构；

头文件如下：

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4//选择需要的类型
typedef int SLDatatype;//动态的顺序表
typedef struct SeqList
{SLDatatype* a;int size;	  //有效的数据个数int capacity; //顺序表的空间容量
}SL;//顺序表的增删查改://初始化顺序表
void SeqInit(SL* s);//销毁顺序表
void SeqDestory(SL* s);//打印顺序表
void SeqPrint(SL* s);//检查容量
void CheckCapacity(SL* s);//尾插
void SeqPushBack(SL* s, SLDatatype x);//尾删
void SeqPopBack(SL* s);//头插
void SeqPushFront(SL* s, SLDatatype x);//头删
void SeqPopFront(SL* s);//插入
void SeqInsert(SL* s, int pos, SLDatatype x);//删除
void SeqErase(SL* s, int pos);

3.1 初始化、销毁与检查容量

接口如下：

3.1.1 初始化

//初始化顺序表
void SeqInit(SL* ps)
{//结构体指针不能为空assert(ps);//开辟空间ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY);//检查if (ps->a == NULL){perror("malloc fail");}ps->size = 0;ps->capacity = INIT_CAPACITY;
}

3.1.2 销毁

//销毁顺序表
void SeqDestory(SL* ps)
{//结构体指针不能为空assert(ps);//释放并置空free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

3.1.3 检查容量

//检查容量
void CheckCapacity(SL* ps)
{//结构体指针不能为空assert(ps);if (ps->size == ps->capacity){//增容（两倍）SLDatatype* tmp = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2);//检查是否增容成功if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}

3.2 尾插

//尾插
void SeqPushBack(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, ps->size, x);/*单独实现//结构体指针不能为空assert(ps);//检查容量CheckCapacity(ps);//尾插ps->a[ps->size++] = x;*/
}

3.3 尾删

//尾删
void SeqPopBack(SL* ps)
{//代码复用SeqErase(ps, ps->size - 1);/*单独实现//结构体指针不能为空assert(ps);//检查顺序表是否为空assert(ps->size);//尾删ps->size--;*/
}

3.4 头插

//头插
void SeqPushFront(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, 0, x);/*单独实现//结构体指针不能为空assert(ps);//检查容量CheckCapacity(ps);//把值往后挪int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}//头插ps->a[0] = x;ps->size++;*/
}

3.5 头删

//头删
void SeqPopFront(SL* ps)
{//代码复用SeqErase(ps, 0);/*单独实现//结构体指针不能为空assert(ps);//当顺序表为零时就不能删了assert(ps->size);//将数据往前覆盖int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;*/
}

3.6 插入

//插入
void SeqInsert(SL* ps, int pos, SLDatatype x)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos <= ps->size);//检查容量CheckCapacity(ps);//往后挪动数据int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}//插入数据ps->a[pos] = x;ps->size++;
}

3.7 删除

//删除
void SeqErase(SL* ps, int pos)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos < ps->size);//挪动数据int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

我们发现，

其实顺序表核心的功能就是插入和删除，

只要我们完成这两个接口，

其他的接口的实现都是大同小异。

顺序表源码

SeqList.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4//选择需要的类型
typedef int SLDatatype;//动态的顺序表
typedef struct SeqList
{SLDatatype* a;int size;	  //有效的数据个数int capacity; //顺序表的空间容量
}SL;//顺序表的增删查改://初始化顺序表
void SeqInit(SL* s);//销毁顺序表
void SeqDestory(SL* s);//打印顺序表
void SeqPrint(SL* s);//检查容量
void CheckCapacity(SL* s);//尾插
void SeqPushBack(SL* s, SLDatatype x);//尾删
void SeqPopBack(SL* s);//头插
void SeqPushFront(SL* s, SLDatatype x);//头删
void SeqPopFront(SL* s);//插入
void SeqInsert(SL* s, int pos, SLDatatype x);//删除
void SeqErase(SL* s, int pos);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"//初始化顺序表
void SeqInit(SL* ps)
{//结构体指针不能为空assert(ps);//开辟空间ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY);//检查if (ps->a == NULL){perror("malloc fail");}ps->size = 0;ps->capacity = INIT_CAPACITY;
}//销毁顺序表
void SeqDestory(SL* ps)
{//结构体指针不能为空assert(ps);//释放并置空free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}//打印
void SeqPrint(SL* ps)
{//结构体指针不能为空assert(ps);//遍历打印for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]); }printf("\n");
}//检查容量
void CheckCapacity(SL* ps)
{//结构体指针不能为空assert(ps);if (ps->size == ps->capacity){//增容（两倍）SLDatatype* tmp = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2);//检查是否增容成功if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}//尾插
void SeqPushBack(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, ps->size, x);/*单独实现//结构体指针不能为空assert(ps);//检查容量CheckCapacity(ps);//尾插ps->a[ps->size++] = x;*/
}//尾删
void SeqPopBack(SL* ps)
{//代码复用SeqErase(ps, ps->size - 1);/*单独实现* //结构体指针不能为空assert(ps);//检查顺序表是否为空assert(ps->size);//尾删ps->size--;*/
}//头插
void SeqPushFront(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, 0, x);/*单独实现//结构体指针不能为空assert(ps);//检查容量CheckCapacity(ps);//把值往后挪int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}//头插ps->a[0] = x;ps->size++;*/
}//头删
void SeqPopFront(SL* ps)
{//代码复用SeqErase(ps, 0);/*单独实现//结构体指针不能为空assert(ps);//当顺序表为零时就不能删了assert(ps->size);//将数据往前覆盖int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;*/
}//插入
void SeqInsert(SL* ps, int pos, SLDatatype x)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos <= ps->size);//检查容量CheckCapacity(ps);//往后挪动数据int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}//插入数据ps->a[pos] = x;ps->size++;
}//删除
void SeqErase(SL* ps, int pos)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos < ps->size);//挪动数据int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"//测试接口
void SLTest()
{SL s;SeqInit(&s);SeqPushBack(&s, 1);SeqPushBack(&s, 2);SeqPushBack(&s, 3);SeqPushBack(&s, 4);SeqPushBack(&s, 5);SeqPushBack(&s, 6);SeqPrint(&s);SeqPopBack(&s);SeqPopBack(&s);SeqPrint(&s);SeqPushFront(&s, 10);SeqPushFront(&s, 50);SeqPrint(&s);SeqPopFront(&s);SeqPopFront(&s);SeqPopFront(&s);SeqPrint(&s);SeqDestory(&s);
}int main()
{SLTest();return 0;
}

测试结果无误。

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。


http://www.ppmy.cn/news/27639.html

相关文章

el-table大数据量渲染卡顿问题

el-table大数据量渲染卡顿问题

1、场景描述 在项目开发中&#xff0c;遇到在表格中一次性加载完的需求&#xff0c;且加载数量不少&#xff0c;有几百几千条&#xff0c;并且每条都可能有自己的下拉框&#xff0c;输入框来做编辑功能&#xff0c;此时普通的el-table肯定会导致浏览器卡死&#xff0c;那么怎么…
阅读更多...
【ArcGIS Pro二次开发】(7)：地图(Map)的基本操作

【ArcGIS Pro二次开发】(7)：地图(Map)的基本操作

地图是ArcGIS Pro中的基础起点&#xff0c;也是大多数工程的基础。主要用于显示表示空间数据的图层。 一、地图(Map)的基本操作示例 1、获取当前地图 var map MapView.Active.Map; 2、获取一级图层 var lys map.Layers; 用于获取地图中的单一图层&#xff0c;以及图层组…
阅读更多...
思科设备命令讲解（超基础二）

思科设备命令讲解（超基础二）

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…
阅读更多...
一篇文章读懂Android Framework

一篇文章读懂Android Framework

本文旨在将Framework的框架描绘出来&#xff0c;希望抛砖引玉&#xff0c;对于读者有一定的帮助。前言写在前面&#xff1a;1、有没有必要学习linux内核&#xff1f;我认为是很有必要的。学习linux内核有助于我们加深对一些概念的理解&#xff0c;比如“进程”、“线程”。推荐…
阅读更多...
蓝牙运动耳机哪个好，比较好的运动蓝牙耳机

蓝牙运动耳机哪个好，比较好的运动蓝牙耳机

很多想选择蓝牙运动耳机的朋友都不知道应该如何选择&#xff0c;运动首先需要注意的就是耳机的防水能力以及耳机佩戴舒适度&#xff0c;在运动当中会排出大量的汗水&#xff0c;耳机防水等级做到越高&#xff0c;可以更好地保护耳机不受汗水浸湿&#xff0c;下面就分享五款适合…
阅读更多...
线性数据结构：数组 Array

线性数据结构：数组 Array

一、前言数组是数据结构还是数据类型&#xff1f;数组只是个名称&#xff0c;它可以描述一组操作&#xff0c;也可以命名这组操作。数组的数据操作&#xff0c;是通过 idx->val 的方式来处理。它不是具体要求内存上要存储着连续的数据才叫数组&#xff0c;而是说&#xff0c…
阅读更多...
【Python入门第十七天】Python While 循环

【Python入门第十七天】Python While 循环

Python 循环 Python 有两个原始的循环命令&#xff1a; while 循环for 循环 while 循环 如果使用 while 循环&#xff0c;只要条件为真&#xff0c;我们就可以执行一组语句。 实例 只要 i 小于 7&#xff0c;打印 i&#xff1a; i 1 while i < 7:print(i)i 1运行实…
阅读更多...
详解数据库基本概念

详解数据库基本概念

数据库&#xff08;DataBase 简称 DB&#xff09;&#xff1a;是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合数据库管理系统&#xff08;DataBase Management System 简称 DBMS&#xff09;&#xff1a;是一种操纵和管理数据库的大型软件&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023