• 【C语言】详解顺序表(SeqList)

    📒博客主页：要早起的杨同学的博客
    🎉欢迎关注🔎点赞👍收藏⭐️留言📝
    📌本文所属专栏：【数据结构】
    ✉️坚持和努力从早起开始！
    💬参考在线编程网站：🌐牛客网🌐力扣
    🙏作者水平有限，如果发现错误，敬请指正！感谢感谢！

    本文导航

    什么是线性表

    • 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
    • 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
      image-20220727111958285

    顺序表

    1.1 什么是顺序表

    • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
    • 顺序表：可动态增长的数组，要求数据是连续存储的

    2.1 顺序表的定义

    静态顺序表：使用定长数组存储元素

    • 缺陷：给小了不够用，给大了可能浪费，非常不实用
    #define N 200
typedef int SeqDataType;

typedef struct SeqList
{
	SLDataType a[N];  //定长数组
	int size;          //有效数据个数
}SeqList;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    image-20220727112150340

    动态顺序表：使用动态开辟的数组存储

    • 动态顺序表可根据我们的需要分配空间大小
    • size 表示当前顺序表中已存放的数据个数
    • capacity 表示顺序表总共能够存放的数据个数
    typedef int SeqDataType; //类型重命名，后续要存储其它类型时方便更改

typedef struct SeqList
{
	SeqDataType* a;    //指向动态开辟的数组
	size_t size;      //有效数据个数
	size_t capacity;  //容量大小
}SeqList;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    2.3 顺序表的接口实现

    静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。

    所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

    什么是接口函数？

    接口函数是在数据进行操作时进行调用的函数，通过调用数据结构的接口帮助你完成一系列操作.

    首先新建一个工程（ 博主使用的是 VS2022 ）此次用的是动态顺序表

    • SeqList.h（顺序表的类型定义、接口函数声明、引用的头文件）
    • SeqList.c（顺序表接口函数的实现）
    • test.c（主函数、测试顺序表各个接口功能）

    如图：

    image-20220727094036681

    • SeqList.h 头文件代码如下：
    #pragma once  //防止头文件被二次引用

#include   /*perror, printf*/
#include  /*assert*/
#include  /*realloc*/

typedef int SeqDataType;  //后续要存储其它类型时方便更改
//顺序表的动态存储
typedef struct SeqList
{
	SeqDataType* a;    //指向动态开辟的数组
	size_t size;      //有效数据个数
	size_t capacity;  //容量大小
}SeqList;

//初始化顺序表
void SLInit(SeqList* s);
//销毁顺序表
void SLDestory(SeqList* s);
//检查顺序表容量是否满了，好进行增容
void CheckCapacity(SeqList* s);
//顺序表尾插
void SLPushBack(SeqList* s, SeqDataType x);//O(1)
//顺序表头插，挪动数据
void SLPushFront(SeqList* s, SeqDataType x);//O(N)
//顺序表尾删
void SLPopBack(SeqList* s, SeqDataType x);//O(1)
//顺序表头删，挪动数据
void SLPopFront(SeqList* s, SeqDataType x);//O(n)

//打印顺序表
void SLPrint(const SeqList* s);
//查找顺序表里面的元素，找到返回下标，找不到返回-1
int SLFind(SeqList* s, SeqDataType x);
//在顺序表中间pos位置插入元素
void SLInsert(SeqList* s, size_t pos, SeqDataType x);
// 顺序表删除pos位置的值
void SLErase(SeqList* s, size_t pos);
//查看顺序表中数据个数
size_t SeqListSize(const SeqList* s);
//修改指定下标位置的数据
void SeqListAt(SeqList* s, size_t pos, SeqDataType x);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    这里重点讲解 SeqList.c 中各个接口函数的实现。

    1、初始化顺序表

    首先引入我们自己创建的头文件 #include “SeqList.h” ，我们就可以开始动手实现顺序表初始化函数了。

    首先通过 s 指向 a，将数组为空。因为是初始化，所以将有效数据个数和数组时即能存数据的空间容量一并置为0。

    记得一定要加上断言，防止传进来的指针为空

    void SLInit(SeqList* s)
{
	assert(s);  //断言

	s->a = NULL;  //初始顺序表为空
	s->size = 0;  //初始数据个数为0
	s->capacity = 0;  //初始空间容量为0
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    2、销毁（释放）顺序表

    记得一定要加上断言，防止传进来的指针为空

    void SLDestory(SeqList* s)
{
	assert(s);  //断言

	free(s->a);   //释放动态开辟的空间
	s->a = NULL;  //置空
	s->size = 0;  //数据个数置0
	s->capacity = 0;  //空间容量大小置0
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    3、检查顺序表容量是否满了，好进行增容

    后续我们会插入元素，如果空间不够，则使用realloc函数扩容。

    newcapacitv是扩容后的内存空间，newA是指向这个新的空间的指针。如果空间为0，则扩容可以放置4个元素的空间，如果空间已满，则在原来的空间基础上，增加1倍，为什么不采取插一个数据，增容一个空间的方式呢，因为这样也太麻烦了，代价也太大了，一般情况下，为了避免频繁的增容，当空间满了后，我们不会一个一个的去增，而是一次增容 2 倍，当然也不会一次增容太大，比如 3 倍 4 倍，空间可能会浪费，2 倍是一个折中的选择。

    void CheckCapacity(SeqList* s)
{
	assert(s);  //断言

	if (s->size == s->capacity)  //检查容量，满了则增容
	{
		size_t newcapacity;  //新容量
		if (s->capacity == 0)
			newcapacity = 4;  //原来容量为0，扩容为4
		else
			newcapacity = 2 * s->capacity;  //原来容量不为0，扩容为原来的2倍
		
		SeqDataType* newA = (SeqDataType*)realloc(s->a, sizeof(SeqDataType) * newcapacity);  //扩容
		if (newA == NULL)
		{
			perror("CheckCapacity");
			exit(-1);
		}
		s->a = newA;  // newA不为空，开辟成功
		s->capacity = newcapacity;  //更新容量
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    3、顺序表尾插

    尾插有三种情况：

    ① 第一种情况是顺序表压根就没有空间。

    ② 第二种情况就是我们创建的 capacity 空间满了。

    ③ 第三种情况是空间足够，直接插入数据即可。

    void SLPushBack(SeqList* s, SeqDataType x)
{
	assert(s);  //断言

	CheckCapacity(s);  //检查顺序表容量是否已满

	s->a[s->size] = x;  //尾插数据
	s->size++;  //有效数据个数+1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 测试其功能

    image-20220727103945366

    4、顺序表尾删

    不知道 SeqDataType是什么类型的数据，不能冒然的将顺序表最后一个数据赋值为 0，我们只需将有效数据个数 size 减 1 即可达到尾删的目的。

    void SLPopBack(SeqList* s, SeqDataType x)
{
	assert(s);  //断言
	assert(s->size > 0);  //顺序表不能为空

	//不知道SeqDataType是什么类型的数据，不能冒然的赋值为0
	//s->a[s->size - 1] = 0;
	s->size--;  //有效数据个数-1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 测试其功能
      image-20220727104258414

    5、顺序表头插

    思路：首先创建一个 end 变量用来指向要移动的数据，因为指向的是数据的下标，所以是 size 要减 1 。随后进入 while 循环，如果 end >= 0 说明还没有移动完，就会进入循环。循环体内利用下标，进行向后移动操作，移动结束后再 end-- ，进行下一个数据的向后移动。挪动数据成功后，就可以插入了。此时顺序表第一个位置就被腾出来了，就可以在下标0位置插入欲插入的数据 x 了。最后记得 size++ 。

    void SLPushFront(SeqList* s, SeqDataType x)
{
	assert(s);  //断言
	CheckCapacity(s);  //检查顺序表容量是否已满
    int end = s->size - 1;
    while (end >= 0)/顺序表中[0,size-1]的元素依次向后挪动一位
    {
        s->a[end + 1] = s->a[end];
        end--;
    }

    s->a[0] = x;//头插数据
    s->size++;//有效数据个数+1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    6、顺序表头删

    思路和头插类似，依次向前挪动，然后数量-1即size–

    如果头删多次调用，如何内存中已经没有元素了，size依然在减。所以这里依然会出现越界，所以需要断言。

    void SLPopFront(SeqList* s)
{
	assert(s);//断言
	assert(s->size > 0);//顺序表不能为空
	int begin = 1;
	while (begin < s->size)//顺序表中[1,size-1]的元素依次向前挪动一位
	{
		s->a[begin-1] = s->a[begin];
		begin++;
	}
	s->size--;//有效数据个数-1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 测试头删和头插功能

    image-20220727104658289

    7、打印顺序表

    void SLPrint(const SeqList* s)
{
	assert(s);
    if (s->size == 0)  //判断顺序表是否为空
	{
		printf("顺序表为空\n");
		return;
	}
	for (int i = 0; i < s -> size; i++)//打印顺序表
	{
		printf("%d ", s->a[i]);
	}
	printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    8、在顺序表中查找指定值

    //查找顺序表里面的元素，找到返回下标，找不到返回-1
int SLFind(SeqList* s, SeqDataType x)
{
	assert(s);
	for (int i = 0; i <s->size; i++)
	{
		if (s->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 测试其功能
      image-20220727104857682

    9、在顺序表指定下标位置插入数据（要注意下int与size_t间的转换问题）

    顺序表要求数据从第一个开始放并且数据是连续存储的，所以我们就要注意下指定的下标位置 pos 的位置了！有些位置并不可以，所以我们需要进行一些检查。

    将指定位置后的所有数据依次向后挪动一位，初始代码如下：

    int i = 0;
for (i = s->size - 1; i >= pos; i--)
	s->a[i + 1] = s->a[i];

    • 1
    • 2
    • 3
    • 原先这种写法，当顺序表为空 size = 0 时，会导致 i = -1，
      执行 i >= pos 时，因为pos是size_t类型的，i 被算术转换成无符号数，而无符号数的 -1 是一个值很大的正数，
      远大于 pos，满足条件进入循环，会造成越界访问
    • 注：转换并不会改变 i 本身的值，而是执行 i >= pos 时，生成一个临时的值与 pos 比较
    • 如果在顺序表头部插入数据 pos = 0，i 最终也会减减变成 -1，被算术转换后变成一个很大的数
    • 总结：避免负数给到无符号数，或者避免有符号数变成负数后，被算术转换或整型提升后，变成一个很大的数

    下面这样写就避免 i 变成 -1 负数了

    //在顺序表中间某个位置插入元素
void SLInsert(SeqList* s, size_t pos, SeqDataType x)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);//检查pos下标的合法性
	CheckCapacity(s);//检查顺序表容量是否已满
	size_t end = s->size;
	while (end > pos)//将pos位置后面的数据依次向后挪动一位
	{
		s->a[end] = s->a[end-1];
		--end;
	}
	s->a[pos] = x;//插入数据
	s->size++;//有效数据个数+1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 测试其功能

    image-20220727105129881

    • 实现了此接口，顺序表头插相当于在下标为 0 位置处插入数据，可以改进下顺序表头插的代码：
    void SLPushFront(SeqList* s, SeqDataType x)
{
	SLInsert(s, 0, x);  //改造头插接口
}

    • 1
    • 2
    • 3
    • 4

    10、在顺序表中删除指定下标位置的数据

    删除指定位置的数据，我们仍然要限制 pos 的位置。限制条件部分和 SLInsert不同的是，因为 s->size 这个位置没有效数据，所以删除的位置不能是 s->size！

    void SLErase(SeqList* s, size_t pos)
{
	assert(s);//断言
	assert(pos >= 0 && pos < s->size);//检查pos下标的合法性
	size_t end = pos;
	while (end < s->size-1)//将pos位置后面的数据依次向前挪动一位
	{
		s->a[end] = s->a[end+1];
		end++;
	}
	s->size--;//有效数据个数-1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 测试其功能

    image-20220727105225056

    • 实现了此接口，顺序表头删相当于删除下标为 0 位置处的数据，可以改进下顺序表头删的代码：
    //顺序表头删
void SLPopFront(SeqList* s)
{
	SLErase(s, 0);  //改造头删接口
}

    • 1
    • 2
    • 3
    • 4
    • 5

    11、查看顺序表中有效数据个数

    • 可能大家会有一个疑问，我在主函数里面直接通过定义的结构体变量直接访问就好了呀，为啥还要弄一个函数嘞
    • 在数据结构中有一个约定，如果要访问或修改数据结构中的数据，不要直接去访问，要去调用它的函数来访问和修改，这样更加规范安全，也更方便检查是否出现了越界等一些错误情况
    size_t SeqListSize(const SeqList* s)
{
	assert(s);  //断言

	return s->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 补充：

    越界不一定报错，系统对越界的检查是一种抽查

    • 越界读一般是检查不出来的
    • 越界写如果是修改到标志位才会检查出来

    （系统在数组末尾后设的有标志位，越界写时，恰好修改到标志位了，就会被检查出来）

    12、修改指定下标位置的数据

    void SeqListAt(SeqList* s, size_t pos, SeqDataType x)
{
	assert(s);  //断言
	assert(s->size > 0);  //顺序表不能为空
	assert(s >= 0 && pos < s->size);  //检查pos下标的合法性

	s->a[pos] = x;  //修改pos下标处对应的数据
}
t SeqListSize(const SeqList* s)
{
	assert(s);  //断言

	return s->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
  • 相关阅读:
    本地生活服务正在借助小程序迎战增量市场
    水电气能耗管理云平台
    众和策略：小盘和大盘的关系？
    解决mybatis用Map返回的字段全变大写的问题
    NLP（8）--利用RNN实现多分类任务
    Android --- Service
    利用FME读取Word中的表格
    【C++】C++基础解析，容易混淆的引用&&内联&&NULL与nullptr
    Python——基本数据类型的转换
    抖音矩阵系统。抖音矩阵系统。抖音矩阵系统。抖音矩阵系统。抖音矩阵系统。抖音矩阵系统。
  • 原文地址：https://blog.csdn.net/Y673789476/article/details/126014896