当前位置:网站首页>顺序表的实现
顺序表的实现
2022-07-31 03:06:00 【蓝猫骑士】
目录
序言
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改
顺序表的实现一般可以分为两种:静态的顺序表(采用定长数组的形式进行存储) 和 动态的顺序表(使用动态开辟的数组进行存储)
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空
间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间
大小,所以下面我们实现动态顺序表。
关于框架结构:
顺序表的基本功能 增 删 查 找 改 插入 几大功能,我们用函数来实现 下面 我们 先来 对 结构体进行构造, 再对基本函数进行一个声明,以此来完成基本框架。
typedef struct SeqList
{
int* a;
int size; // 存储数据的个数
int capicity; // 因为我们这里是一个动态的顺序表,我们需要一个容量。
}SL;
// 初始化
void SeqListInit(SL* psl);
// 检查空间,如果满了,进行增容
void CheckCapacity(SL* psl);
// 顺序表尾插
void SeqListPushBack(SL* psl, int x);
// 顺序表尾删
void SeqListPopBack(SL* psl);
// 顺序表头插
void SeqListPushFront(SL* psl, int x);
// 顺序表头删
void SeqListPopFront(SL* psl);
// 顺序表查找
int SeqListFind(SL* psl, int x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* psl, size_t pos, int x);
// 顺序表删除pos位置的值
void SeqListErase(SL* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SL* psl);
// 顺序表打印
void SeqListPrint(SL* psl);
基本函数的构建
1.初始化数据
将 a 指针置为空 以及把size 和 capicity 的大小置为 0 ;
void SeqListInit(SL* psl)
{
assert(psl);
psl->a = NULL;
psl->size = psl->capicity = 0;
}
2.销毁数据
void SeqListDestory(SL* psl);
void SeqListDestory(SL* psl)
{
if (psl->a)
{
free(psl->a);
psl->a = NULL;
psl->capicity = psl->size = 0;
}
}
3.尾插(从尾部进行插入数据)
因为我们这里是动态的顺序表 插入数据的时候要考虑一下 我们的capicity容量是否充足?
这里我们要用到一个函数;void CheckCapacity(SL* psl)
判断是否有足够的内存区进行插入数据 不够的话 我们将进行动态的扩容;
检查扩容
void CheckCapacity(SL* psl)
void CheckCapacity(SL* psl)
{
assert(psl);
if (psl->capicity == psl->size)
{
int newcapicity = psl->size == 0 ? 4 : (psl->size) * 2;
int* tmp = (int*)realloc(psl->a,sizeof(int)*newcapicity);
if (tmp == NULL)
{
perror("ralloc fail");
return;
}
psl->a = tmp;
psl->capicity = newcapicity;
}
}
现在我们再来构造尾插:
void SeqListPushBack(SL* psl, int x)
{
assert(psl);
CheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
4.尾删
这个比较简单,我们前面说明了结构体中的 size 是用来对数据进行计数的;我们打印数据的时候就是根据 size 来进行打印的。现在既然提到了打印数据的问题 那么我们先写一个打印数据的这个函数
打印数据
void SeqListPrint(SL* psl);
void SeqListPrint(SL* psl)
{
assert(psl);
int i = 0;
for (i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
尾删
直接把 size 进行减减 就行了;因为我们是根据size的大小来判断数据的存储。
void SeqListPopBack(SL* psl)
{
assert(psl);
if (psl->size == 0)
{
return;
}
psl->size--;
}
5.头插
在 开头插入一个数据; 同样是插入 同样也需要 检查扩容;其实这里的头插 效率不高 还要遍历挪动数据;
void SeqListPushFront(SL* psl, int x)
{
assert(psl);
CheckCapacity(psl);
int i = 0;
for (i = psl->size+1; i > 0; i--)
{
psl->a[i] = psl->a[i-1];
}
psl->a[0] = x;
psl->size++;
}
6.头删
void SeqListPopFront(SL* psl)
{
assert(psl);
assert(psl->size > 0);
int i = 0;
for (i = 0; i < psl->size-1;i++)
{
psl->a[i] = psl->a[i + 1];
}
psl->size--;
}
7.顺序表查找
查找一个数据所在的下标 返回值为 int 如果不存在 则返回 -1。
int SeqListFind(SL* psl, int x)
{
assert(psl);
int i = 0;
for (i = 0; i < psl->size; i++)
{
if (psl->a[i] == x)
return i;
}
return -1;
}
8.顺序表在pos位置插入x
插入要引用 检查扩容
void SeqListInsert(SL* psl, size_t pos, int x)
{
assert(psl);
CheckCapacity(psl);
size_t i = 0;
for (i = psl->size + 1; i > pos; i--)
{
psl->a[i] = psl->a[i - 1];
}
psl->a[pos] = x;
psl->size++;
}
9.顺序表删除pos位置的值
利用 SeqListFind 来找出 pos 位置的下标 利用for遍历 数组 从 此下标位置 依次向前覆盖;
void SeqListErase(SL* psl, size_t pos)
{
assert(psl);
int A = SeqListFind(psl, pos);
int i = 0;
for (i = A; i < psl->size-1; i++)
{
psl->a[A] = psl->a[A + 1];
}
psl->size--;
}
改进和优化
我们知道 我们数据表里的数据 不一定都是整形 为了方便我们对数据进行修改;
我们可以预先用 #define 来 定义 类型的名称;
以上代码 断言部分并不充分,需要进行优化。
边栏推荐
- 分布式锁以及实现方式三种
- 2022 Nioke Multi-School League Game 4 Solution
- 7、私信列表
- php 网站的多语言设置(IP地址区分国内国外)
- mycat的主从关系 垂直分库 水平分表 以及mycat分片联表查询的配置详解(mysql5.7系列)
- Graphical lower_bound & upper_bound
- How to build a private yum source
- Mysql 45讲学习笔记(二十四)MYSQL主从一致
- 10. Redis implements likes (Set) and obtains the total number of likes
- C#远程调试
猜你喜欢
Several common errors when using MP
What is a distributed lock?Three ways of implementing distributed lock
[Compilation principle] Design principle and implementation of recursive descent parsing
学习DAVID数据库(1)
CefSharp入门-winform
加密公司向盗窃的黑客提供报价:保留一点,把剩下的归还
【C语言】表达式求值的一般方法
Mysql 45讲学习笔记(二十三)MYSQL怎么保证数据不丢
SQL injection Less54 (limited number of SQL injection + union injection)
TCP详解(三)
随机推荐
Recursive query single table - single table tree structure - (self-use)
【C语言】求两个整数m和n的最大公因数和最小公倍数之和一般方法,经典解法
The whole process scheduling, MySQL and Sqoop
php 网站的多语言设置(IP地址区分国内国外)
【C语言】表达式求值的一般方法
QML的使用
Problems that need to be solved in distributed system architecture
测试中的误报和漏报同样的值得反复修正
LeetCode简单题之找到和最大的长度为 K 的子序列
Number 16, top posts
LeetCode simple problem to find the subsequence of length K with the largest sum
SQALE 是什么
遗留系统的自动化策略
mycat的主从关系 垂直分库 水平分表 以及mycat分片联表查询的配置详解(mysql5.7系列)
【编译原理】递归下降语法分析设计原理与实现
【HCIP】ISIS
【Android】Room —— SQLite的替代品
MultipartFile file upload
Unity3D Button mouse hover enter and mouse hover exit button events
Mycat's master-slave relationship, vertical sub-database, horizontal sub-table, and detailed configuration of mycat fragmented table query (mysql5.7 series)