点这看我主页~
顺序表
- 一、预备知识
-
- 数据结构相关概念
- 二、顺序表
-
- 1、顺序表概念及结构
-
- 线性表
- 2、顺序表分类
-
- ①静态顺序表
- ②动态顺序表
-
- 顺序表初始化
- 顺序表销毁
- 顺序表打印
- 顺序表扩容
- 顺序表头插
- 顺序表头删
- 尾插
- 尾删
- 指定位置插
- 指定位置删
- 寻找某个数据在哪个位置
一、预备知识
数据结构相关概念
数据结构就是计算机存储、组织数据的方式，数据结构是用c语言代码来实现的一个内部结构，它能够存储数据且存储的数据能够方便查找
为什么需要数据结构呢？
程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况，通过数据结构，能够有效将数据组织和管理在一起，按照我们的方式任意对数据进行增删查改
数组是最基础的数据结构
因为最基础的数据结构能够提供的操作已经不能完全满足复杂算法的实现，我们来学习顺序表
二、顺序表
1、顺序表概念及结构
线性表
线性表是n个具有相同特性的数据元素的有限序列，常见的线性表有：顺序表、链表、栈、队列、字符串等
线性表在逻辑上是线性结构，也就是连续的一条直线，但物理结构不一定连续，线性表在物理上存储时，通常以数组和链式结构的形式存储
2、顺序表分类
顺序表的底层结构时数组，对数组的封装，实现了常用的增删查改
①静态顺序表
静态顺序表顾名思义就是使用定长的数组存储元素
typedef int SLDataType;
#define N 8
typedef struct SeqList
{
SLDataType a[N];
int size;
}SL;
它有一个很明显的缺点，就是空间问题，给少了不够用，给多了浪费，没有弹性
②动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;//有效元素个数
int capacity;//顺序表容量
}SL;
下面我们来实现顺序表：
这是顺序表的头文件，我们挨个实现
#define INIT_CAPACITY 4
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
SLDataType* a;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);
顺序表初始化
void SLInit(SL* ps);
void SLInit(SL* ps)
{
ps->a = NULL;//将指针a置为空
ps->capacity = 0;//指针没有指向任何数据，容量为0
ps->size = 0;//同上，无数据，为0
}
顺序表销毁
void SLDestroy(SL* ps)；
void SLDestroy(SL* ps)
{
if (ps->a)
{
free(ps->a);//释放a指向堆区的内存
ps->a = NULL;//将a指针置为空
}
if (ps->capacity)
ps->capacity = 0;
if (ps->size)
ps->size = 0;
}
顺序表打印
void SLPrint(SL* ps)；
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", *(ps->a + i));
}
}
顺序表扩容
void SLCheckCapacity(SL* ps)；
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//检查capacity是否为0，若为0，则开辟一块空间，若不为0，则将空间扩大一倍
SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * 2 * sizeof(SLDataType));
//使用realloc函数开辟动态内存
if (tmp == NULL)
{
perror(tmp);
return 1;
}
ps->a = tmp;
ps->capacity = newCapacity;
}
}
顺序表头插
void SLPushFront(SL* ps, SLDataType x)；
void SLPushFront(SL* ps, SLDataType x)
{
if (ps->a)//确保不为空第一种方法
{
SLCheckCapacity(ps);
for (int i = ps->size; i > 0; i--)
{
*(ps->a + i) = *(ps->a + i - 1);//从最后一位与空位开始交换，直到第一位空出来
}
*ps->a = x;//填补第一位
ps->size++;
}
}
顺序表头删
void SLPopFront(SL* ps);
void SLPopFront(SL* ps)
{
if (ps->a)
{
for (int i = 0; i < ps->size - 2; i++)
{
*(ps->a + i) = *(ps->a + i + 1);
}
ps->size--;//将size减一最后一位就不会被访问到，将其在数组中删除
}
}
尾插
void SLPushBack(SL* ps, SLDataType x);
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
*(ps->a + ps->size++) = x;//后置++先赋值后++，在最后一位放入x，然后size+1
}
尾删
void SLPopBack(SL* ps);
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;//直接删除
}
指定位置插
void SLInsert(SL* ps, int pos, SLDataType x);
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);//确保不为空第二种方法
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
{
*(ps->a + ps->size) = *(ps->a + ps->size - 1);
//将要插入的数字位置后的所有数字往后移一位，然后插入
}
*(ps->a + pos) = x;
ps->size++;//后置++
}
指定位置删
void SLErase(SL* ps, int pos);
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
for (int i = ps->size; i > pos; i--)
{
*(ps->a + pos) = *(ps->a + pos + 1);
}
//将所有指定位置以后的数字往前一位
ps->size--;//直接删除最后一位
}
寻找某个数据在哪个位置
int SLFind(SL* ps, SLDataType x);
int SLFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (x == *(ps->a + i))
{
return i;
}//遍历数组，找出然后返回
}
return -1;//找不到就返回一个无意义的数字
}
我的gitee中拿原件~
今天分享就到这里了~
版权声明：本文为博主作者：s_little_monster_原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/s_little_monster/article/details/137481579
