C语言数据结构专题--顺序表(1基础)

前言

我们在对C语言有一定的了解之后,我们就可以开始数据结构的学习了,数据结构多用指针、结构体、动态内存开辟等知识,若对这些知识还不太了解的朋友,就需要加深其理解了,那么废话不多说,我们正式开始本节的学习

什么是数据结构

数据结构是由"数据" 和 "结构" 两个词相组合得到的 

那么什么是数据呢?

例如:常见的数字1、2、3、4、5等,手机通讯录里面保存的联系人信息(号码、名字等)、浏览器网页里面的信息,这些都统称为数据

什么是结构呢?

当我们需要使用大量同一类型的数据时,我们手动的定义大量独立的变量对程序来说可读性很差,我们往往可以借助数组等这些数据结构将大量的数据组织在一起,所以结构也可以理解为组织数据的方式

举个通俗易懂的例子:我们如果想要在一大片草场上寻找一名叫 "多莉" 的羊难度会很大,但是我们要在羊圈中找到 "多莉" 就会很简单,羊圈就好像一个结构,而羊就好似数据

概念:数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系 的数据元素的集合。数据结构反映数据的内部构成,即数据由那部分构成,以什么⽅式构成,以及数据元素之间呈现的结构

其中:在数据结构中最基础的数据结构就是数组

顺序表

顺序表是线性表的一种,其中:线性表是具有相同特征的数据结构的集合

线性表的特征:

1.物理结构不一定连续(数据间的地址不一定是连续的)

2.逻辑结构是连续的

顺序表在物理结构和逻辑结构层面上都是连续的

顺序表的底层就是数组,顺序表是在数组的基础上进行维护、封装

可能有人就会产生疑问:既然都有数组了,数组也可以实现数据的增加、删除、查询、修改功能,那么顺序表的存在又有什么意义呢?

当我们想修改、插入或者删除数组中的某个数据时,我们首先需要通过循环来查找数组之中已有元素的个数,再进行数据的修改、插入或者删除,我们每次进行操作的时候都需要进行循环的处理,这样就会很浪费时间和空间,此时顺序表的存在就有意义了

顺序表的底层虽然是数组,但是数组提供了很多现成的办法来处理数据,相比直接使用数组会更加的简洁高效

顺序表分类

1.静态顺序表

struct Seqlist
{
	int arr[100];
	int size;//记录顺序表当前有效数据的个数


};

静态顺序表的底层是一个定长的数组,在代码的编译阶段,我们就确认了数组的大小

2.动态顺序表

//动态顺序表
struct Seqlist
{
	int* arr;
	int size;//有效的数据个数
	int capacity;//记录空间大小
};

那么动态顺序表和静态顺序表二者相比较谁更好呢?

对于静态顺序表而言。若是数组大小给小了,则会导致空间不够用的问题,可能导致数据的丢失;若是数组大小给大了,则会导致空间的浪费

所以动态顺序表更好,因为它更加灵活

我们在实现顺序表时,我们通常把它分成两个文件

头文件:顺序表的结构,声明实现顺序表的方法(头文件实现的是类似于书的目录的功能)

源文件:实现顺序表的方法

同时我们在实现顺序表的时候还需要多创建一个文件,用于检测其功能是否正常

​
//动态顺序表
struct Seqlist
{
	int* arr;
	int size;//有效数据的个数
	int capacity;//空间大小
};

​

我们先在头文件中定义顺序表结构体,考虑到我们存入顺序表中的数据类型不一定为 int 类型,还有可能是 char 类型的数据,所以我们可以定义一下,用定义表示当前顺序表中存储数据的类型,具体操作如下:

typedef int SLDataType;

//动态顺序表
struct Seqlist
{
	SLDataType* arr;
	int size;//有效数据的个数
	int capacity;//空间大小
};

我们可以重命名一下结构体类型来简化代码:

//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;
	int size;//有效数据的个数
	int capacity;//空间大小
}SL;

下面我们就来实现一下顺序表的各种功能:

顺序表的初始化

在源文件中初始化前,我们需要在头文件中声明一下

void SLInit(SL ps);

此时我们就可以在源文件中初始化

#include"Seqlist.h"
void SLInit(SL s)
{
	s.arr = NULL;
	s.size = s.capacity = 0;

}

由于我们不知道初始化是否成功,我们就可以在测试文件中通过打印各个成员的值,通过在屏幕上面打印的值在观察出初始化是否成功

我们按照我们的常规理解来写出如下代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"


void SLTest01()
{
	SL s1;
	SLInit(s1);

}

int main()
{
	SLTest01();
	return 0;
}

当我们在运行程序的时候,我们发现它报错了

这个报错非常的奇怪,编译器说我们使用了未初始化的局部变量 s1,而我们现在所做的操作不正是要初始化吗?这样不是自相矛盾吗?

我们仔细分析一下就可以发现问题:

我们传入的 sl 是形式参数,我们采取的是传值操作,由于 sl 本来就是没有初始化的变量,无法进行传值操作,要想解决这个问题,我们需要使用传址操作,现在我们就来改一下代码:

#include"Seqlist.h"
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;

}
void SLInit(SL* ps);

此时我们的初始化代码就成功完成了

顺序表的销毁

因为数组的大小是动态开辟的,需要使用到动态内存函数,我们需要释放开辟的空间,那么我们就需要采取如下的操作:

顺序表的头部 插入 和 删除 + 顺序表的 尾部 插入 和 删除
顺序表的尾插

举个例子:若数组里面只有四个数据

0123

                              0                     1                  2                    3             4               5

此时 size = 4  capacity = 6,我们想要在它的尾部插入 x = 5

我们可以发现我们想要插入数据的地方的下标就是 size 的大小,同时再插入数据之前,我们需要先保证有空间允许去插入,如果空间不够,我们还需要去申请空间,那么我们该怎么申请空间呢?

首先,空间的申请需要使用到 malloc calloc realloc 函数,当申请的空间被使用完了我们还需要去增容,那么我们要申请多大的空间呢?一次增容又该增多大呢?

申请空间的规则:增容通常来说是成倍数的增加,一般是两倍增容,若空间是一个一个地去增加,那么插入数据也得一个一个的去插入,这样会非常的麻烦,若要频繁的增容,程序运行的效率就会大大降低;若一次进行大量的增容,就会造成空间的浪费。所以采取两倍两倍的增容是最合理的

4 --------> 8 --------> 16 --------> 32 --------> 64

通过以上几个注意事项,我们可以写出代码:

​
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	if (ps == NULL)
	{
		return;
	}
	//插入数据前看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		//判断capacity是否为0
		int newCapaciy = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, ps->newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
			//直接退出程序,不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapaciy;
	}
	
	ps->arr[ps->size] = x;
	++ps->size;
	//或者写作 ps->arr[ps->size++] = x;
	ps->size++;

}

​

注意:我们在增容的时候需要临时创建一个变量用于存储增容后的指针,若是直接将 其赋给 arr,倘若空间申请失败,原数据内容也会丢失,导致不可逆的错误

我们在 test.c 中测试一下这个代码

#include"Seqlist.h"


void SLTest01()
{
	SL s1;
	SLInit(&s1);
	//测试尾插代码
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPushBack(&s1, 5);

	//.....
	SLDestory(&s1);

}

int main()
{
	SLTest01();
	return 0;
}

这样我们的尾插操作就完成了

顺序表的头插

举个例子:

0123

                               0                 1                    2                     3              4(size)

在开始进行头插之前。我们同样的需要判断插入数据的空间够不够,不够的话我们需要增容。

头插需要在下标为0的地方插入数据,但是原数组下标为0的地方已经有了数据,这时我们应该怎么插入数据呢?

我们此时需要把原顺序表中的数据统一向后挪动一位

0123

若我们此时需要插入一个数据 x = 6

由于我们在进行头插和尾插之前都需要判断空间是否足够,此时我们就可以把判断空间的代码单独封装成一个函数:

void SLCheckCapacity(SL* ps)
{
	//插入数据前看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		//判断capacity是否为0
		int newCapaciy = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapaciy * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
			//直接退出程序,不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapaciy;
	}
}

在数据挪动的时候,我们可以发现:数组中的最后一个元素,经过挪动后,需要到达下标为 size 处

所以由此我们可以写出头插的代码:

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	if (ps == NULL)
	{
		return;
	}
	SLCheckCapacity(ps);
	//先让顺序表中的数据向后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]
	}
		ps->arr[0] = x;
		ps->size++;
	
}

我们再在 test.c 文件里面测试一下:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"


void SLTest01()
{
	SL s1;
	SLInit(&s1);
	//测试尾插代码
	SLPushFront(&s1, 1);
	SLPushFront(&s1, 2);
	SLPushFront(&s1, 3);
	SLPushFront(&s1, 4);
	SLPushFront(&s1, 5);

	//.....
	SLDestory(&s1);

}

int main()
{
	SLTest01();
	return 0;
}

我们运行调试,可以发现头插功能成功实现

由于每次都运行调试比较麻烦,我们来定义一个函数用于打印顺序表中的元素:

//打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}
顺序表的尾部删除
0123

我们首先需要判断顺序表是否为空,为空的话就不能执行删除操作

我们可以知道,每次删除完数据以后,数组里面的数据就会减少一个,所以 size--

此时我们就能够很轻松地写出尾部删除的代码:

//尾部删除
void SLPopBack(SL* ps)
{
	if (ps == NULL)
	{
		return;
	}

	if (ps->size == 0)
	{
		return;
	}

	--ps->size;

}
我们来测试一下
void SLTest01()
{
	SL s1;
	SLInit(&s1);
	测试尾插代码
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(s1);
	SLPopBack(&s1);
	SLPrint(s1);


	//.....
	SLDestory(&s1);

}

int main()
{
	SLTest01();
	return 0;
}
顺序表的头部删除

我们在删除完数据以后,需要把顺序表里原有的顺序整体向前挪动一位

根据这个,我们可以写出代码如下:

//头部删除
void SLPopFront(SL* ps)
{
	if (ps == NULL)
	{
		return;
	}

	if (ps->size == 0)
	{
		return;
	}

	//数据整体前挪
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

我们测试一下:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"


void SLTest01()
{
	SL s1;
	SLInit(&s1);
	测试尾插代码
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(s1);
	SLPopFront(&s1);
	SLPrint(s1);


	//.....
	SLDestory(&s1);

}

int main()
{
	SLTest01();
	return 0;
}

代码运行成功

顺序表代码合并

头文件

#pragma once
#include <stdio.h>
#include <stdlib.h>


typedef int SLDataType;

//动态顺序表
typedef struct Seqlist
{
	SLDataType* arr;
	int size;//有效数据的个数
	int capacity;//空间大小
}SL;

//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestory(SL* ps);
//顺序表的头部 插入 和 删除 + 顺序表的 尾部 插入 和 删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//顺序表的打印
void SLPrint(SL s);

源文件

#define _CRT_SECURE_NO_WARNINGS 1
//静态顺序表
//struct Seqlist
//{
//	int arr[100];
//	int size;//记录顺序表当前有效数据的个数
//
//
//};

//动态顺序表
//struct Seqlist
//{
//	int* arr;
//	int size;//有效的数据个数
//	int capacity;//记录空间大小
//};

#include"Seqlist.h"
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;

}

//顺序表的销毁
void SLDestory(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}

	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}


void SLCheckCapacity(SL* ps)
{
	//插入数据前看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		//判断capacity是否为0
		int newCapaciy = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapaciy * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
			//直接退出程序,不再继续执行
		}
		//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapaciy;
	}
}



//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	if (ps == NULL)
	{
		return;
	}
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	++ps->size;
	//或者写作 ps->arr[ps->size++] = x;

}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	if (ps == NULL)
	{
		return;
	}
	SLCheckCapacity(ps);
	//先让顺序表中的数据向后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]
	}
		ps->arr[0] = x;
		ps->size++;
	
}

//打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

//尾部删除
void SLPopBack(SL* ps)
{
	if (ps == NULL)
	{
		return;
	}

	if (ps->size == 0)
	{
		return;
	}

	--ps->size;

}
//头部删除
void SLPopFront(SL* ps)
{
	if (ps == NULL)
	{
		return;
	}

	if (ps->size == 0)
	{
		return;
	}

	//数据整体前挪
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

测试文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Seqlist.h"


void SLTest01()
{
	SL s1;
	SLInit(&s1);
	测试尾插代码
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(s1);
	SLPopBack(&s1);
	SLPrint(s1);


	//.....
	SLDestory(&s1);

}

int main()
{
	SLTest01();
	return 0;
}

结尾

顺序表代码的实现整体难度不是很大,但是要求我们在编写代码的时候要考虑仔细,若是有疏忽就很容易出现错误。因为顺序表的内容很多,我就将顺序表封装成了两节,本节我们讲解的是顺序表的基本内容,下一节为大家带来顺序表更高级的内容实现:顺序表删除、插入指定位置的数据。谢谢您的浏览

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/518492.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

36.基于CAS实现的java类

JUC, java.util.concurrent并发工具包下。 1.原子整数 AtomicInteger AtomicLong AtomicBoolean 底层用的CAS来实现。 AtomicInteger类的incrementAndGet方法&#xff0c;addAndGet方法 public static void main(String[] args) {AtomicInteger atomicInteger new Atom…

一文搞懂 ThreadLocal

简介 ThreadLocal存取的数据&#xff0c;总是与当前线程相关&#xff0c;也就是说&#xff0c;JVM 为每个运行的线程&#xff0c;绑定了私有的本地实例存取空间&#xff0c;从而为多线程环境常出现的并发访问问题提供了一种隔离机制。 ThreadLocal的作用是提供线程内的局部变…

未授权访问-api接口

特别注意api接口的一些命名规则 常见的是这种&#xff0c;具体要看开发人员怎么命名的 而确认api路径的最好办法还是去多出发几个功能点&#xff0c;看他的路径&#xff0c;比如下面触发多个功能点 对比得知两个路径都有pyr/user/这时候可能就会觉得这就是api路径&#xff0c;但…

Azure的VFP和虚拟IP地址

Azure 的Virtual filtering platform (VFP) 是Azure 网络地址转换,端口转换和端口分配的基础。 下面我们来深入介绍一下VFP的工作方式。 VFP的出站动作。 对于客户端地址作为虚拟IP的出站目的地址的时候,VFP 驱动会负责做以下两个动作。 源地址转换。端口地址转换。VFP 和 S…

一分钟了解mos管选型

在选择MOS管时&#xff0c;需要考虑多个关键参数以确保选用的MOS管能够满足特定应用的需求。下面是一些主要参数的介绍 额定电压&#xff08;Vds&#xff09; 也称为漏源电压&#xff0c;通常我们所说的耐压&#xff0c;是指MOS管能够承受的最大电压差。 在选择MOS管时&#xf…

数据湖概述:大数据演进阶段-数据湖

文章目录 一. 大数据发展过程1. 离线大数据平台2. Lambda架构&#xff1a;速度层批层3. Kappa架构&#xff1a;流批一体4. 大数据架构痛点总结 二. 数据湖助力于解决数据仓库痛点问题1. 数据湖特点2. 开源数据湖的架构 三. 数据湖和数据仓库理念的对比1. 数据湖和数据仓库对比2…

c++的STL(7) -- stack

stack容器概述 stack容器其实是实现了一种和栈相同结构的容器。 如图&#xff0c;栈这种结构有两端: 栈底和栈顶。 特殊之处在于&#xff0c;这种结构&#xff0c;我们对数据的操作(删除数据&#xff0c;修改数据&#xff0c;查询数据&#xff0c;添加数据)只能在一端进行(栈…

TAB标签美化 - SVG作为mask

今天觉得V3的标签不是很好看&#xff0c;忽然想起来之前看过Vue Admin Beautiful Pro的样式挺好的&#xff0c;顺手研究了一把。发现Vue Admin Beautiful是采用PNGmask css来解决的。于是乎打算把V3的标签页做点小美化&#xff0c;但是迁移过程发生些小插曲&#xff0c;在此记录…

第1讲——预备知识

一、视觉SLAM十四讲在讲些啥 SLAM&#xff1a;Simultaneous Localization and Mapping 翻译&#xff1a;同时定位与地图构建 搭载特定传感器的主体&#xff0c;在没有环境先验信息的情况下&#xff0c;于运动过程中建立环境的模型&#xff0c;同时估计自己的运动。 当特定传感…

Solidity入门1: 3. 函数类型

Solidity中的函数 solidity官方文档里把函数归到数值类型 函数结构 function <function name>(<parameter types>) {internal|external|public|private} [pure|view|payable] [returns (<return types>)] 看着些复杂&#xff0c;咱们从前往后一个一个看&…

【MySQL】:深入解析多表查询(上)

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; MySQL从入门到进阶 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一. 多表关系1.1 一对多1.2 多对多1.3 一对一 二. 多表查询概述2.1 概述2.2 分类…

Docker Desktop 不支持 host 网络模式

先把这个结论的放在前面&#xff0c;直接访问链接就能看到官方文档中已经明确说了不支持。 参考链接&#xff1a;docker desktop for windows 不支持 host 网络模式 以前对于 docker 的网络模式&#xff0c;一直只是了解&#xff0c;没有亲自尝试过。结果今天在尝试 docker 的 …

『大模型笔记』LLMs入门:从头理解与编码LLM的自注意力机制

LLMs入门&#xff1a;从头理解与编码LLM的自注意力机制 这里直接引用我语雀上的的文章&#xff1a;《从头理解与编码LLM的自注意力机制》

科东软件参加广州机器人产业联盟举办先进工业母机专家研讨会

工业母机是“制造机器的机器”&#xff0c;具有基础性、通用性、战略性特征&#xff0c;包括了减材切削机床、等材成形装备、增材制造装备及其控制系统等&#xff0c;是衡量国家工业水平和竞争力的重要标志。广东省作为全球知名的制造业基地&#xff0c;非常重视高端装备领域工…

python 笔记

文章目录 pdbpdb开始调试pythonpdb设置断点单步执行进入到函数的内部执行到下一个断点或程序结束调用栈查看命令查看当前函数调用堆栈向上一层函数查看调用堆栈查看源代码 importimport 用法 numpy导入numpy模块numpy常用函数np.argmaxnp.sum range生成连续序列生成不连续序列 …

【随笔】Git 高级篇 -- 撤销变更(十四)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

如何使用 Midjourney?2024年最新更新

一&#xff1a;基础篇 1&#xff1a;注册 首先&#xff0c;你需要注册一个 Discord 账号&#xff0c;然后加入 Midjourney 的 Discord 服务器。或者去 Midjourney 的官网点击右下角的 Join the Beta&#xff1a; ​ 2&#xff1a;在 Discord 公共服务器里使用 注册并进入到…

一、Docker部署GitLab(详细步骤)

Docker部署GitLab&#xff08;详细步骤&#xff09; 一、拉取镜像二、启动容器三、修改配置四、修改密码五、浏览器访问 一、拉取镜像 docker安装教程&#xff1a;https://qingsi.blog.csdn.net/article/details/131270071 docker pull gitlab/gitlab-ce:latest二、启动容器 …

MySQL数据库 数据库基本操作(三):表的增删查改(中)

1. 数据库的约束 1.1 约束类型(一般发生于表的创建中) NOT NULL - 指示某列不能存储 NULL 值。UNIQUE - 保证某列的每行必须有唯一的值。DEFAULT - 规定没有给列赋值时的默认值。PRIMARY KEY - NOT NULL 和 UNIQUE 的结合。确保某列&#xff08;或两个列多个列的结合&#xf…