数据结构 顺序表1

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;    //有效数据个数为0ps->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是否为NULLassert(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是否为NULLassert(ps);//判断内存空间是否足够，是否需要增容SLcheckCapacity(ps);ps->p[ps->size++] = x;}

3.3.3 头删：

        将除首地址的元素外其余所以元素往前挪动一位，同时size也需往前挪动一位（size--），覆盖首元素即可（注：如果数组中没有元素，即size=0，此时是没有元素可以删的，所以此处应还需断言size是否为0）

思路分析：

代码实现（SeqList.c）：

void SLPopFront(SL* ps)
{//判断ps是否为NULLassert(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的值是否为0int 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是否为NULLassert(ps);SLcheckCapacity(ps);ps->p[ps->size++] = x;}//头插
void SLPushFront(SL* ps, SLDataTYpe x)
{//判断ps是否为NULLassert(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♪(･ω･)ﾉ！！！）