首页 > 其他分享 >【C语言】从零开始:用C语言实现顺序表

【C语言】从零开始:用C语言实现顺序表

时间:2024-03-31 23:31:59浏览次数:27  
标签:顺序 void SL C语言 assert 从零开始 sl data

欢迎来CILMY23的博客

本篇主题为 从零开始:用C语言实现顺序表

个人主页:CILMY23-CSDN博客

C语言专栏: http://t.csdnimg.cn/hQ5a9

Python系列专栏:http://t.csdnimg.cn/HqYo8

上一篇C语言博客: http://t.csdnimg.cn/I4Zgf

感谢观看,支持的可以给个一键三连,点赞关注+收藏。


目录

一、 什么是顺序表?

1.1 顺序表概念

1.2 顺序表结构及初始化

二、顺序表的功能实现

2.1 增 

2.1.1 头插

2.1.2 尾插

2.1.3 任意位置插入 

2.2 删

2.2.1 头删

2.2.2 尾删

2.2.3 任意位置删除 

2.3 查

2.4 改 

三、 顺序表其余功能

3.1 打印顺序表

3.2 销毁顺序表


本文前言

在学习完C语言后,我们扩展学习几种的数据结构,目的是为了最后的通讯录项目做铺垫

一、 什么是顺序表?

 如果不知道数据结构的概念可以看数据结构概念篇(http://t.csdnimg.cn/yPSMc

1.1 顺序表概念

在讲顺序表之前得先讲讲线性表

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

顺序表(Seqlist)是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存 储。在数组上完成数据的增删查改。

顺序表又分为静态和动态,而静态的顺序表就是固定的空间,那本篇主要以动态顺序表的实现为主。 

1.2 顺序表结构及初始化

 顺序表的结构如下所示:

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;			 // 起始位置
	size_t data;			 // 有效数据个数
	size_t capacity;		 // 空间容量
}SQ;

那在使用之前我们肯定是要初始化的,这里我们直接给了一个capacity = 4,意思是这个顺序表一开始就有4个空间(但这个时候实际还未创建好)

//顺序表的初始化
void SLInit(SL* sl)
{
	assert(sl);

	sl->a = NULL;
	sl->data = 0;
	sl->capacity = 4;
}

二、顺序表的功能实现

顺序表功能主要围绕四个部分,“增删查改”这四个字,当然我们还可以增加其他功能,这些是最基本的实现。 

 

2.1 增 

在插入前我们做的第一件事就是要看空间

空间的几种情况如下: 

因为该过程较为常用,我们使用函数进行封装,这样在每次插入前都检查一遍空间。因为一次只插入一个数据,所以当有效数据和空间相等的时候,说明此时已经没有足够空间了,那要进行扩容,如果我们没在初始化给顺序表一个空间,就要使用newcapacity 对 capacity 进行判断,多一步去检查capacity。

//顺序表的空间检查
void SLCheckCapacity(SL*sl)
{	
	//如果空间不够,就要扩容
	if (sl->data == sl->capacity)
	{
		SLDataType* psl;
		psl = (SLDataType*)realloc(sl->a, sl->capacity * 2 * sizeof(SLDataType));
		if (psl == NULL)
		{
			perror("realloc fail");
			return 1;
		}
		sl->a = psl;
		sl->capacity = sl->capacity*2;
	}
}

2.1.1 头插

//顺序表的头插
void SLPushFront(SL* sl, SLDataType x)
{
	assert(sl);
	//检查空间
	SLCheckCapacity(sl);
	//插入数据,前要移动数据
	for (size_t i = sl->data; i > 0; i--)
	{
		//从末尾开始移动数据
		sl->a[i] = sl->a[i - 1];
	}
	//移动完数据开始插入数据
	sl->a[0] = x;
	sl->data++;
}

2.1.2 尾插

//顺序表的尾插
void SLPushBack(SL* sl, SLDataType x)
{
	assert(sl);
	//插入前,检查空间
	SLCheckCapacity(sl);
	//插入数据
	sl->a[sl->data] = x;
	sl->data++;
}

2.1.3 任意位置插入

我们这里说的是在任意位置之前插入数据

void SLInsert(SL* sl, int pos, SLDataType x)
{
	assert(sl);
	//检查空间
	SLCheckCapacity(sl);
	//数据移动
	for (int i = sl->data - 1; i >= pos; i--)
	{
		sl->a[i + 1] = sl->a[i];
	}

	sl->a[pos] = x;
	sl->data++;
}

2.2 删

在删除的时候要判断顺序表是否为空,所以我们使用一个布尔类型来判断顺序表是否为空

//判断顺序表是否为空
bool SLIsEmpty(SL* sl)
{
	assert(sl);
	//当有效数据为0就为空的顺序表
	return sl->data == 0;
}

2.2.1 头删

 在删除的时候一定要保证size大于0,当然我还是更喜欢在删除的时候选择这种柔和的方式

void SLPopFront(SL* sl)
{
	assert(sl);
	if (sl->data > 0)
	{
		for (int i = 0; i < sl->data; i++)
		{
			sl->a[i] = sl->a[i - 1];
		}
		sl->data--;
	}
}

2.2.2 尾删

 注意,我们删除的时候不能让有效数据小于0.

//顺序表的尾删
void SLPopBack(SL* sl)
{
	assert(sl);
	//保证有效数据大于0
	if(sl->data > 0)
	sl->data -= 1;
}

2.2.3 任意位置删除 

void SLErase(SL* sl, int pos)
{
	assert(sl);
	assert(!SLIsEmpty(sl));

	//数据移动
	for (int i = pos; i < sl->data - 1; i++)
	{
		sl->a[i] = sl->a[i + 1];
	}

	sl->data--;
}

2.3 查

在顺序表中查询数据,如果找到了则返回下标位置,如果找不到就返回-1

//顺序表查找数据
int SLFind(SL* sl, SLDataType x)
{
	assert(sl);
	assert(!SLIsEmpty(sl));
	int i = 0;
	for (i = 0; i < sl->data; i++)
	{
		if (sl->a[i] == x)
		{
			return i;
		}
	}
	if (i == sl->data)
		return -1;
}

2.4 改 

在顺序表中修改指定位置的数据

//顺序表修改数据
void SLChange(SL* sl, SLDataType x)
{
	assert(sl);
	assert(!SLIsEmpty(sl));
	int i = 0;
	for (i = 0; i < sl->data; i++)
	{
		if (sl->a[i] == x)
		{
			sl ->a a[i] = x;
		}
	}
}

三、 顺序表其余功能

3.1 打印顺序表

//顺序表的打印
void SLPrint(SL* sl)
{
	if (sl->data != 0)
	{
		int i = 0;
		for (i = 0; i < sl->data;i++)
		{
			printf("%d ", sl->a[i]);
		}
		printf("\n");
	}
}

3.2 销毁顺序表 

有顺序表的初始化,那就有顺序表的销毁,因为是动态内存,所以我们就要用到free函数来释放空间

//顺序表的销毁
void SLDestroy(SL* sl)
{
	if (sl->a != NULL)
	{
		free(sl->a);
		sl->a = NULL;
		sl->capacity = 0;
		sl->data = 0;
	}
}

 感谢各位同伴的支持,本期顺序表就讲解到这啦,更详细的可以看,【数据结构和算法】4.超详细解析动态顺序表的实现(图文解析,附带源码)-CSDN博客

如果你觉得写的不错的话,可以给个一键三连,点赞,关注+收藏,若有不足,欢迎各位在评论区讨论。      

标签:顺序,void,SL,C语言,assert,从零开始,sl,data
From: https://blog.csdn.net/sobercq/article/details/137177492

相关文章

  • C语言中的基本结构3——循环结构篇
    C语言中的基本结构3——循环结构篇一、前言二、何为循环结构三、三种循环语句1.while2.do···while3.for四、循环的嵌套五、如何根据需要使用适合的循环语句?六、循环的辅助:continue和break1.continue2.break3.其余的方法:goto,return离开循环1.goto2.return七、结束语......
  • 学习笔记之嵌入式八股文(C语言)
    文章目录前言一、指针和变量二、关键字1.Volatile2.const3.static4.extern三、结构体1.结构体基本内容2.通过指针对结构体赋值3.结构体指针四、链表1.链表的基本内容2.链表的插入和删除五、堆、栈和队列1.栈(Stack)2.堆(Heap)3.队列前言笔者在学习时发......
  • C语言——常用库函数的使用及模拟实现
    C语言编译系统为使用者提供了很多的预定义库函数。用户在编写程序时,可以直接调用这些库函数。这里选择了一些常用的库函数,简单介绍各个函数的使用方法:字符串函数字符串函数函数分为长度不受限制的字符串函数,和长度受限制的字符串函数。长度不受限制的字符串函数包括strcpy函......
  • 数据结构 - 线性表 - 顺序表
    前言最近刚刚开始复习408数据结构,就想着把每个章节的代码部分汇总记录一下,写成一组文章,便于日后的复习和参考。本系列整体的框架和课后习题参考了王道的复习指导。在本系列的每篇文章中,我会先把该章节所对应数据结构的基础代码放上来,然后附上参考资料习题对应的题目代码。线性......
  • 快速排序(C语言实现)此文章由vivo的AI蓝心小v生成
    当然可以。快速排序是一种非常高效的排序算法,由英国计算机科学家霍尔(C.A.R.Hoare)于1962年提出。它的基本思想是采用分治法(DivideandConquer)来进行排序。###快速排序的基本步骤:1.**选择基准值(Pivot)**:从待排序的序列中选取一个元素作为基准值。这个元素可以是序列的第一......
  • 【C语言基础篇】字符串处理函数(四)strcmp的介绍及模拟实现
    目录 一、strcmp函数介绍函数原型函数参数功能描述返回值使用示例二、strcmp函数模拟实现思路代码测试         个人主页:    倔强的石头的博客        系列专栏 :C语言指南         C语言刷题系列  系列文章【C语言基础篇......
  • C语言——初出茅庐
               一、初识C语言                   1.C语言的起源                   2.C语言的基本结构                   3.C语言的特......
  • #include<初见C语言之指针(5)>
    目录一、sizeof和strlen的对比1. sizeof2.strlen二、数组和指针题解析1.⼀维数组1.1数组名理解2.字符数组 3. ⼆维数组三、指针运算题解析总结一、sizeof和strlen的对比1. sizeof我们前面介绍过sizeof是单目操作符sizeof括号中有表达式,不计算 计算变......
  • C语言----预处理(详解)
         好了书接上回。我在讲编译与链接的时候写过宏和条件建议。我说会在下一篇博客中讲解,那么来了。今天我们来详细的讲讲预处理。宏与条件编译也在其中,那么我们现在就来好好会会这个预处理吧。预定义符号    关于预定义符号,我暂时只知道几个。并且我知道的......
  • C语言----简单讲解编译与链接
        大家好,这次我们来讲讲我们写下代码后,源代码是变为执行文件的,这里我们将会使用用另外一种编译器(gcc),但是嘞因为鄙人对电脑的理解还是比较少的,所以对于我们进行对比的编译器(gcc)鄙人只能提供代码,以及一些网络上其他博主的图文,希望大家理解这样更加方便大家了解。(如果大......