1. 何为顺序表:
顺序表是一种线性数据结构,是由一组地址连续的存储单元依次存储数据元素的结构,通常采用数组来实现。顺序表的特点是可以随机存取其中的任何一个元素,并且支持在任意位置上进行插入和删除操作。在顺序表中,每个元素的下标都是唯一的,而且在顺序表中,相邻的元素在内存中也是相邻的。
顺序表通常包含两个重要的属性:容量和长度。容量指该顺序表所能容纳的最大元素数量,而长度指当前已经存储的元素数量。当长度等于容量时,顺序表就已经满了,不能再插入元素。
2. 静态顺序表和动态顺序表的区别:
由于顺序表底层是用数组完成的,所以这个数组决定了我们这个顺序表的大小,同时也区分出了静态顺序表与动态顺序表,下面我们来一一了解:
静态顺序表:有着静态两字顾名思义则这个顺序表写好以后大小就固定死了,是不可以改变的(为了方便我们后期更改顺序表的类型,此处我们define定义一个变量,专门存放顺序表类型)
typedef int SLDataTYpe;
typedef struct SeqList
{
SLDataTYpe p[50]; //数组大小为50,代表这个顺序表可以存储50个元素
int size; //顺序表有效数据个数
int capacity; //顺序表空间大小
}SL; //将顺序表struct SeqList取别名为SL
动态顺序表:相较于静态,动态顺序表则在定义顺序表是写死数据的大小,而是定义了一个指针,等到后边需要用到顺序表的时候,再动态分配内存空间(C语言动态内存空间分配-CSDN博客)
typedef int SLDataTYpe;
typedef struct SeqList
{
SLDataTYpe* p;
int size; //顺序表有效数据个数
int capacity; //顺序表空间大小
}SL; //将顺序表struct SeqList取别名为SL
3. 顺序表的实现:
在本次项目当中我们以动态顺序表为例,来对顺序表各类功能的实现,项目文件分为SeqList.h(顺序表中各类函数的声明),SeqList.c(顺序表各类功能的实现),SeqList_test(对应顺序表各类功能的测试),实现环境为VS2022
3.1. 顺序表的初始化:
在SeqList.h声明一个函数用于实现顺序表的初始化,同时传入一个顺序表变量,SeqList.c实现顺序表的初始化,顺序表没被调用前,顺序表为NULL(注:要想调用SeqList.h中声明好的方法,则得包含该方法所在的头文件)
SeqList.h:
#pragma once
#include <stdio.h>
typedef int SLDataTYpe;
//动态顺序表
typedef struct SeqList
{
SLDataTYpe* p;
int size; //顺序表有效数据个数
int capacity; //顺序表空间大小
}SL; //将顺序表struct SeqList取别名为SL
//顺序表的初始化
void SLInit(SL* ps);
SeqList.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h" //头文件包含
//顺序表初始化的实现
void SLInit(SL* ps)
{
ps->p = NULL;
ps->size = 0; //有效数据个数为0
ps->capacity = 0; //空间大小为0
}
SeqList_test(在SeqList_test中调用SLInit函数,打开监视查看是否赋值成功):
void SLTest01()
{
SL s1;
SLInit(&s1);
}
int main()
{
SLTest01();
return 0;
}
测试结果:
(如上图所示,则初始化成功)
3.2. 顺序表的销毁:
顺序表的销毁分为两种情况,一是顺序表已写入数据,二是没有写入数据
SeqList.h:
#pragma once
#include <stdio.h>
typedef int SLDataTYpe;
//动态顺序表
typedef struct SeqList
{
SLDataTYpe* p;
int size; //顺序表有效数据个数
int capacity; //顺序表空间大小
}SL; //将顺序表struct SeqList取别名为SL
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDesttroy(SL* ps);
SeqList.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//顺序表初始化的实现
void SLInit(SL* ps)
{
ps->p = NULL;
ps->size = 0;
ps->capacity = 0;
}
//顺序表的销毁
void SLDesttroy(SL* ps)
{
if (ps->p) //判断是否为NULL
{
free(ps->p);
}
ps->p = NULL;
ps->size = 0;
ps->capacity = 0;
}
(由于代码量的缘故,后边只展示对应文件中要添加的代码)
3.3. 顺序表插入数据:
为了方便展示,关于SeqList.h文件当中的代码,统一展示在此处
//顺序表头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataTYpe x);
void SLPushFront(SL* ps, SLDataTYpe x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataTYpe x);
//删除指定位置数据
void SLErase(SL* ps, int pos);
3.3.1. 头插:
头插可以分为以下几点:
1. 函数传参:
void SLPushFront(SL* ps, SLDataTYpe x); //x为要插入的元素
2. 判断顺序表是否为空:
#include <assert.h> //头文件包含
assert(ps); //ps为要断言的变量
3. 判断顺序表空间是否够用:
由于后续我们要多次判断是否要增容,此处我们重新用一个函数完成顺序表的增容:
(注:realloc函数如果申请内存空间失败,则返回NULL,所以此处不可将realloc申请的空间直接赋给p->p这样会导致原来p->p中的数据全部清空,应先判断增容是否成功,再进行赋值)
void SLcheckCapacity(SL* p)
{
//插入数据前判断空间是否足够 如果数组大小与内存总大小相等,则申请空间
if (p->size == p->capacity)
{
//判断capacity的值是否为0,不为0则2倍增容
int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
//增容空间
SLDataTYpe* tmp = (SLDataTYpe*)realloc(p->p, 2 * newcapacity * sizeof(SLDataTYpe));
//判断增容是否成功
if (tmp == NULL)
{
perror("relloc fail");
exit(1);
}
//申请成功以后
p->p = tmp;
p->capacity = newcapacity;
}
}
4. 头部插入数据:
假设一个数组中已有数据a,b,c,d,现在要在头部添加一个元素f,我们应该如何添加?
思路分析:
代码实现(SeqList.c):
void SLPushFront(SL* ps, SLDataTYpe x)
{
//判断ps是否为NULL
assert(ps);
//判断内存空间是否足够,是否需要增容
SLcheckCapacity(ps);
//将顺序表中原有的数据整体往后挪一位
for (int i = ps->size; i > 0; i--)
{
ps->p[i] = ps->p[i - 1];
}
//添加元素
ps->p[0] = x;
//size向后挪动一位
ps->size++;
}
3.3.2. 尾插:
假设一个数组中已有数据a,b,c,d,现在要在最后添加一个元素f,我们应该如何添加?
思路分析:
代码实现(SeqList.c):
void SLPushBack(SL* ps, SLDataTYpe x)
{
//判断ps是否为NULL
assert(ps);
//判断内存空间是否足够,是否需要增容
SLcheckCapacity(ps);
ps->p[ps->size++] = x;
}
3.3.3 头删:
将除首地址的元素外其余所以元素往前挪动一位,同时size也需往前挪动一位(size--),覆盖首元素即可(注:如果数组中没有元素,即size=0,此时是没有元素可以删的,所以此处应还需断言size是否为0)
思路分析:
代码实现(SeqList.c):
void SLPopFront(SL* ps)
{
//判断ps是否为NULL
assert(ps);
//判断数组是否为空
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->p[i] = ps->p[i + 1];
}
ps->size--;
}
3.3.4 尾删:
当数组不为空时,size往前挪一位(注size代表的是数组的大小,即下标+1,也就是说size前边为整个数组,因此删除末尾元素时,我们只需要将size--即可)
思路分析:
代码实现(SeqList.c):
void SLPopBack(SL* ps)
{
//断言
assert(ps);
//判断顺序表是否为NULL,为空删除等于-1,越界
assert(ps->size);
//删除数据
ps->size--;
}
3.3.5 指定位置添加数据:
与头插相类似,此处只需要将指定位置的数据整体往后挪一位size++,由于和头插相类似,就不在此处重复直接看代码:
void SLInsert(SL* ps, int pos, SLDataTYpe x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size); //判断pos的有效范围
//插入数据:空间够不够
SLcheckCapacity(ps);
//让pos下标对应的数据,全部往后挪一位
for (int i = ps->size; i > pos; i--)
{
ps->p[i] = ps->p[i - 1];
}
ps->p[pos] = x;
ps->size++;
}
3.3.6 指定位置删除数据:
与添加相反,删除指定对应数据以后,指定位置后的元素整体往前挪一位,size--
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->p[i] = ps->p[i + 1];
}
ps->size--;
}
3.4 顺序表的打印:
遍历数组
代码实现(SeqList.h / SeqList.c):
//顺序表的打印
void SLPrintf(SL s);
void SLPrintf(SL s)
{
//打印
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.p[i]);
}
printf("\n");
}
3.5 顺序表的查找:
遍历数组,查找对应的元素,存在返回元素的下标,不存在返回无效下标-1
代码实现(SeqList.h / SeqList.c):
//查找
int SLFind(SL* ps, SLDataTYpe x); //数据有,返回值的下标,否则返回-1
查找
int SLFind(SL* ps, SLDataTYpe x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->p[i] == x)
{
//找到了
return i;
}
}
//没找到
return -1;
}
4.实现代码:
SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataTYpe;
//动态顺序表
typedef struct SeqList
{
SLDataTYpe* p;
int size; //顺序表有效数据个数
int capacity; //顺序表空间大小
}SL;
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDesttroy(SL* ps);
//顺序表头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataTYpe x);
void SLPushFront(SL* ps, SLDataTYpe x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataTYpe x);
//删除指定位置数据
void SLErase(SL* ps, int pos);
//顺序表的打印
void SLPrintf(SL s);
//查找
int SLFind(SL* ps, SLDataTYpe x); //数据有,返回值的下标,否则返回-1
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//顺序表初始化的实现
void SLInit(SL* ps)
{
ps->p = NULL;
ps->size = 0;
ps->capacity = 0;
}
//顺序表的销毁
void SLDesttroy(SL* ps)
{
if (ps->p)
{
free(ps->p);
}
ps->p = NULL;
ps->size = 0;
ps->capacity = 0;
}
//增容
void SLcheckCapacity(SL* p)
{
//插入数据前判断空间是否足够 如果数组大小与内存总大小相等,则申请空间
if (p->size == p->capacity)
{
//判断capacity的值是否为0
int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
//增容空间
SLDataTYpe* tmp = (SLDataTYpe*)realloc(p->p, 2 * newcapacity * sizeof(SLDataTYpe));
//判断增容是否成功
if (tmp == NULL)
{
perror("relloc fail");
exit(1);
}
//申请成功以后
p->p = tmp;
p->capacity = newcapacity;
}
}
//顺序表的尾插
void SLPushBack(SL* ps, SLDataTYpe x)
{
//判断ps是否为NULL
assert(ps);
SLcheckCapacity(ps);
ps->p[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLDataTYpe x)
{
//判断ps是否为NULL
assert(ps);
//增容
SLcheckCapacity(ps);
//将顺序表中原有的数据整体往后挪一位
for (int i = ps->size; i > 0; i--)
{
ps->p[i] = ps->p[i - 1];
}
ps->p[0] = x;
ps->size++;
}
//顺序表的打印
void SLPrintf(SL s)
{
//打印
for (int i = 0; i < s.size; i++)
{
printf("%d ", s.p[i]);
}
printf("\n");
}
//尾删
void SLPopBack(SL* ps)
{
//断言
assert(ps);
//判断顺序表是否为NULL,为空删除等于-1,越界
assert(ps->size);
//删除数据
ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->p[i] = ps->p[i + 1];
}
ps->size--;
}
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataTYpe x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size); //判断pos的有效范围
//插入数据:空间够不够
SLcheckCapacity(ps);
//让pos下标对应的数据,全部往后挪一位
for (int i = ps->size; i > pos; i--)
{
ps->p[i] = ps->p[i - 1];
}
ps->p[pos] = x;
ps->size++;
}
//删除指定位置数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->p[i] = ps->p[i + 1];
}
ps->size--;
}
//查找
int SLFind(SL* ps, SLDataTYpe x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->p[i] == x)
{
//找到了
return i;
}
}
//没找到
return -1;
}
SeqList_test.c(测试代码)
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SLTest01()
{
SL s1;
SLInit(&s1);
}
int main()
{
SLTest01();
return 0;
}
尾插
//SLPushBack(&s1, 1);
//SLPushBack(&s1, 2);
//SLPushBack(&s1, 3);
//SLPushBack(&s1, 4);
//SLPrintf(s1);
//SLPushBack(&s1, 5);
//SLPrintf(s1);
//SLPushFront(&s1, 5);
//SLPushFront(&s1, 6);
//SLPrintf(s1);
//
//
销毁
//SLDesttroy(&s1);
(有需要的小伙伴自取喔,最后还请点赞三联支持一下博主,Thanks♪(・ω・)ノ!!!)