顺序表<数据结构 C 版>
创始人
2024-12-29 08:06:10
0次

目录

线性表

顺序表

动态顺序表类型

初始化

 销毁

打印

检查空间是否充足(扩容)

尾部插入

头部插入

尾部删除

头部删除

指定位置插入

指定位置删除

查找数据


线性表

        线性表是n个相同特性的数据元素组成的有限序列,其是一种广泛运用的数据结构,常见的线性表有顺序表、栈、链表、队列等。

        其在逻辑上是线性的,物理结构(存储结构)上不一定是线性的。


顺序表

        顺序表就是线性表的一种,它在逻辑结构与物理结构上都是连续的,一般情况下它的底层就是数组,在数组基础上多了增删查改操作。

顺序表有静态顺序表和动态顺序表,我们常常采用动态顺序表,因为它的扩容方便、空间浪费更少。


动态顺序表类型
typedef int SeqDataType;//将动态顺表的存储数据的类型重命名,方便后期统一修改    //动态顺序表 typedef struct SeqList {//命名:Sequence List顺序表 	SeqDataType* arr; 	int capacity;//动态顺序表的容量 	int size;//动态顺序表的有效个数 }SL;

初始化
//初始化 void SLInit(SL* s) { 	s->arr = NULL; 	s->capacity = s->size = 0; }

 销毁
//销毁 void SLDestory(SL* s) { 	if (!s->arr) {//等同于s->arr==NULL,判断要释放的空间是否是NULL,防止释放NULL 		perror("Destory Fail");//打印错误 		exit(1); 	} 	free(s->arr);//释放动态开辟的内存 	s->arr = NULL; 	s->capacity = s->size = 0; }

打印

打印操作方便我们检查错误。

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

检查空间是否充足(扩容)

插入操作会扩大空间大小,那么在进行插入操作前,我们应该检查空间是否充足(扩容)

//检查空间是否充足(扩容) void SLCheckCapacity(SL* s) { 	if (s->capacity == s->size) { 	//判断有效元素个数是否和空间大小相同,相同:空间用满了,要扩容 		int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2; 		//空间是否为0,是:赋个初值4(防止按倍数扩容出错) 		//不是:按两倍扩容,赋给临时变量,防止扩容失败对原capacity改变 		SeqDataType* p = (SeqDataType*)realloc(s->arr, sizeof(SeqDataType) *newcapacity); 		//这里是为s->arr扩容,不是为结构体(动态顺序表) 		if (!p) { 			perror("realloc fail"); 			exit(1); 		} 		s->arr = p; 		s->capacity = newcapacity; 	} } 

尾部插入
//尾插 void SLPushBack(SL* s, SeqDataType x) { 	assert(s); 	SLCheckCapacity(s);//检查空间是否充足 	s->arr[s->size++] = x;//尾部插入数据,并使有效元素加1 }

头部插入
//头插 void SLPushFront(SL* s, SeqDataType x) { 	assert(s);// 	SLCheckCapacity(s); 	for (int i = s->size ; i > 0; i--) { 		s->arr[i] = s->arr[i-1]; 	}//将数据整体后移一位,腾出第一位给头插,且循环条件初始化i等于s->size 	s->arr[0] = x; 	s->size++;//别忘了将有效数据个数加一 }

尾部删除
//尾删 void SLPopBack(SL* s) { 	assert(s->arr);//不能对空数组进行删除 	assert(s->size);//不能对有效元素0个的数组进行删除 	s->size--;//直接使有效元素个数减1即可 }

头部删除
//头删 void SLPopFront(SL* s) { 	assert(s->arr); 	assert(s->size); 	for (int i = 0; i < s->size - 1; i++) { 		s->arr[i] = s->arr[i + 1]; 	}//注意循环条件s->size-1,取到最后一个元素前一个位置 	s->size--; }

指定位置插入
//指定位置之前插入数据 void SLInsert(SL* s, int pos, SeqDataType x) { 	assert(s); 	assert(pos >= 0 && pos <= s->size);//pos=0时头插,pos=s->size时尾插, 	SLCheckCapacity(s); 	for (int i = s->size; i >pos; i++) {//从pos位置开始腾出位置给要插入的数据 		s->arr[i] = s->arr[i - 1]; 	} 	s->size++; 	s->arr[pos] = x; }

指定位置删除
//指定位置删除 void SLErase(SL* s, int pos) { 	assert(s->arr); 	assert(pos >= 0 && pos < s->size);//保证pos是可删除的 	for (int i = pos; i < s->size - 1; i++) {//使pos以后的数据向前移一位 		s->arr[i] = s->arr[i + 1]; 	} 	s->size--; }

查找数据
//查找数据 void SLFind(SL* s, SeqDataType x) { 	assert(s->arr); 	assert(s->size > 0); 	for (int i = 0; i < s->size; i++) {//遍历顺序表,找到值返回下标,找不到,返回-1 		if (s->arr[i] == x) { 			return i; 		} 	} 	return -1; }

最后我们来测试一下我们写的代码

相关内容

热门资讯

一分钟了解作弊器!七天娱乐作弊... 一分钟了解作弊器!七天娱乐作弊器多功能AIapp,七天娱乐竟然真的有作弊器app1、超多福利:超高返...
一分钟教会你辅助!道游互娱辅助... 一分钟教会你辅助!道游互娱辅助多功能AI软件,道游互娱原来存在有辅助软件1、道游互娱公共底牌简单,道...
教程攻略透视器!神牛大厅透视器... 教程攻略透视器!神牛大厅透视器多功能AI软件,神牛大厅好像有透视器软件1、任何神牛大厅透视是真的假的...
来一盘辅助!悠悠互娱辅助多功能... 来一盘辅助!悠悠互娱辅助多功能AIapp,悠悠互娱确实是有辅助app1、游戏颠覆性的策略玩法,独创攻...
分享个大家作弊器!上游大厅作弊... 分享个大家作弊器!上游大厅作弊器多功能AI工具,上游大厅一直存在有作弊器工具1、用户打开应用后不用登...
玩家必看科普外挂!千秋互娱外挂... 玩家必看科普外挂!千秋互娱外挂多功能AI工具,千秋互娱竟然是真的有外挂工具1、千秋互娱模拟器是什么优...
今日百科透视器!新漫游透视器多... 今日百科透视器!新漫游透视器多功能AI工具,新漫游果然真的是有透视器工具1、玩家可以在新漫游线上大神...
终于知道外挂!多多娱乐外挂多功... 终于知道外挂!多多娱乐外挂多功能AI技巧,多多娱乐确实真的是有外挂技巧1、用户打开应用后不用登录就可...
推荐一款作弊器!豪发娱乐作弊器... 推荐一款作弊器!豪发娱乐作弊器多功能AI插件,豪发娱乐一贯真的有作弊器插件1、豪发娱乐辅助软件下载优...
专业讨论透视器!道游互娱透视器... 专业讨论透视器!道游互娱透视器多功能AI软件,道游互娱都是是有透视器软件1、该软件可以轻松地帮助玩家...