当前位置:网站首页>顺序表的实现
顺序表的实现
2022-07-31 19:30:00 【照肆】
概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。简单地说,顺序表就是一个数组,在数组上完成数据的增删查改。但是顺序表的数据必须从第一个位置开始进行连续的存储。
顺序表的分类
静态顺序表:使用定长数组存储元素
动态顺序表:使用动态开辟的数组存储
比较选择顺序表和完善
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空
间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间
大小。但是上面的顺序表还有一点问题,就是这个数组只能存int类型的变量,我们存储其他类型的变量修改起来就比较麻烦,所以我们完善一下:
动态顺序表的实现
SeqList.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a; //指向动态数组指针
int size; //数据个数
int capacity; //容量空间大小
}SL;
void SListInit(SL* ps); //初始化
void SLPrintf(SL* ps); //打印
void SLCheckcapacity(SL* ps); //检查容量
void SLPushBack(SL* ps,SLDataType x); //尾插
void SLPushFront(SL* ps,SLDataType x); //头插
void SLPopBack(SL* ps); //尾删
void SLPopFront(SL* ps); //头删
void SLDestory(SL* ps); //调用销毁
void SLInsert(SL* ps, int pos, SLDataType x); //任意位置插入
void SLErase(SL* ps, int pos); //任意位置删除
int SLFind(SL* ps, SLDataType x); //查找
void SLModify(SL* ps,int pos,SLDataType x); //修改
SeqList.c:
#include"SeqList.h"
// 初始化
void SListInit(SL* ps)
{
assert(ps);
ps->a = 0;
ps->size = ps->capacity = 0;
}
//打印
void SLPrintf(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; ++i)
{
printf("%d", ps->a[i]);
}
printf("\n");
}
//检查容量
void SLCheckcapacity(SL* ps)
{
assert(ps);
//检查容量空间,满了扩容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity==0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
//调用销毁
void SLDestory(SL* ps)
{
assert(ps);
if (ps->a = 0)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
}
// 尾插
void SLPushBack(SL* ps,SLDataType x)
{
assert(ps);
检查容量空间,满了扩容
//if(ps->size == ps->capacity)
//{
// int newcapacity = ps->capacity==0 ? 4 : ps->capacity * 2;
//SLDataType* tmp = (SLDataType*)realloc(ps->a,newcapacity * sizeof(SLDataType));
//if (tmp == NULL)
//{
// printf("realloc fail\n");
// exit(-1);
//}
//ps->a = tmp;
//ps->capacity = newcapacity;
//}
SLCheckcapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
//头插
void SLPushFornt(SL* ps, SLDataType x)
{
assert(ps);
SLCheckcapacity(ps);
//挪动数据
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
//ps->a[ps->size-1]=0;
//温柔检查
/*if (ps->size == 0)
{
printf("SeqList is empty\n");
return;
}*/
//暴力检查
assert(ps->size>0);
ps->size--;
}
//头删
void SLPopFornt(SL* ps)
{
assert(ps);
assert(ps->size > 0);
int begin = 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}
//任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckcapacity(ps);
int end = ps->size - 1;
while (pos <= end)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
//任意位置删除
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size );
int begin = pos+1;
while (begin < ps->size)
{
ps->a[begin-1] = ps->a[begin];
++begin;
}
ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; ++i)
{
if (ps->a[i] == x)
{
return i;
}
return -1;
}
}
//修改
void SLModify(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
ps->a[pos] = x;
}
顺序表的问题
1. 中间/头部的插入删除,时间复杂度为O(N)
2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
边栏推荐
- 学生管理系统第一天:完成登录退出操作逻辑 PyQt5 + MySQL5.8
ojdbc8 "Recommended Collection"- leetcode 665. Non-decreasing Array 非递减数列(中等)
- [PIMF] OpenHarmony Thesis Club - Inventory of the open source Hongmeng tripartite library [3]
- MySQL---单行函数
- 有一说一,外包公司到底值不值得去?
- 高通cDSP简单编程例子(实现查询高通cDSP使用率、签名),RK3588 npu使用率查询
- 抖音根据关键词取视频列表 API
- 使用 Flutter 和 Firebase 制作!计数器应用程序
- 性能优化:记一次树的搜索接口优化思路
猜你喜欢
ResNet的基础:残差块的原理
MATLAB程序设计与应用 2.4 MATLAB常用内部函数
ThreadLocal
Three.js入门
SiC MOSFET的短路特性及保护
Basic configuration of OSPFv3
leetcode:6135. 图中的最长环【内向基环树 + 最长环板子 + 时间戳】
Jiuqi ny3p series voice chip replaces the domestic solution KT148A, which is more cost-effective and has a length of 420 seconds
ReentrantLock原理(未完待续)
35 MySQL interview questions and diagrams, this is also easy to understand
随机推荐
Go record - slice
GAC Honda Safety Experience Camp: "Danger" is the best teacher
Basic Grammar Introduction of Carbon Tutorial (Tutorial)
Qualcomm cDSP simple programming example (to query Qualcomm cDSP usage, signature), RK3588 npu usage query
leetcode 665. Non-decreasing Array 非递减数列(中等)
C# 之 扑克游戏 -- 21点规则介绍和代码实现
leetcode: 6135. The longest ring in the graph [inward base ring tree + longest ring board + timestamp]
【AcWing】第 62 场周赛 【2022.07.30】
leetcode:6135. 图中的最长环【内向基环树 + 最长环板子 + 时间戳】
Three. Introduction to js
MySQL---aggregate function
iNeuOS工业互联网操作系统,设备运维业务和“低代码”表单开发工具
Huawei mobile phone one-click to open "maintenance mode" to hide all data and make mobile phone privacy more secure
MySQL---创建和管理数据库和数据表
关注!海泰方圆加入《个人信息保护自律公约》
rj45 to the connector Gigabit (Fast Ethernet interface definition)
全网一触即发,自媒体人的内容分发全能助手——融媒宝
MySQL---排序与分页
spark报错OutOfMemory「建议收藏」
Jiuqi ny3p series voice chip replaces the domestic solution KT148A, which is more cost-effective and has a length of 420 seconds