当前位置: 首页 > article >正文

数据结构——顺序表seqlist

前言:大家好😍,本文主要介绍了数据结构——顺序表部分的内容

目录

一、线性表的定义

二、线性表的基本操作

三.顺序表

1.定义

2. 存储结构

3. 特点

四 顺序表操作

4.1初始化

4.2 插入

4.2.1头插

4.2.2 尾插

4.2.3 按位置插

4.3 删除

4.3.1 头删

4.3.2 尾删

 4.3.3 按位置删

4.3.4 按值删

4.4 查找 

4.5 删除值val出现的位置

4.6 其余操作

4.7 主函数测试


一、线性表的定义

线性表是具有相同数据类型n个数据元素有限序列,n为表长,当n=0时线性表时一个空表。用l命名线性表,表示为l=(a1,a2,  ,an)。

线性表除第一个元素之外,每个元素都有直接前驱,除最后一个元素之外每个元素都有直接后继

二、线性表的基本操作

Initlist(&L):初始化表,构造一个空的线性表L,构造一个空的线性表,分配内存空间

Destroylist(&L):销毁。销毁线性表并释放线性表L所占用的内存空间

Insertlist(&L,i,e):插入,在表L中第i个位置上插入指定元素e

Deletelist(&L,i,&e):删除,删除表L中第i个位置上的元素,并用e返回删除元素的值

LocateElem(L,e):按值查找,在表L中查找具有给定关键字e值的元素

   GetElem(L,i):按位查找,获取表L中第i个位置的元素的值

Length(L):求表长,返回线性表L的长度,即L中数据元素的个数

Printlist(L):输出,输出线性表所有元素值

Empty(L):判空,若L为空,返回true,否则返回false

对参数的修改结果需要引用&

三.顺序表

1.定义

顺序表是一种线性表的存储实现方式。线性表是具有相同数据类型的元素构成的有限序列,顺序表通过数组的形式将这些元素存储在内存中,并通过下标索引来访问和操作元素。

2. 存储结构

顺序表通常使用数组来实现,数组的每个位置存储一个元素。例如,一个顺序表可以表示为:

数组:[a0, a1, a2, ..., an-1]
其中,a0 是表头元素,an-1 是表尾元素。

3. 特点


优点:
随机访问:可以通过下标索引快速访问任意位置的元素,时间复杂度为 O(1)。
存储密度高:由于没有额外的指针存储空间,顺序表的存储利用率较高。
操作简单:基于数组的实现使得顺序表的操作逻辑相对简单。
缺点:
插入和删除效率低:插入或删除元素时,需要移动大量元素以保持顺序表的连续性,时间复杂度为 O(n)。
存储空间固定:顺序表的存储空间在初始化时需要预先分配,难以动态扩展。如果分配的空间不足,需要重新分配更大的空间并复制数据;如果分配过多,则会浪费空间。
内存碎片问题:频繁的动态扩展和收缩可能导致内存碎片化。

四 顺序表操作

点h文件中定义了一个顺序表(SeqList)的结构体

#define INIT_SIZE 10 //初始化时malloc购买的格子数量
//可库容的顺序表的结构体设计
typedef int ELEM_TYPE;
typedef struct SeqList
{
	ELEM_TYPE* elem;//用来接收malloc返回的数组首地址
	int length;//存放有效值个数
	int listsize;//存放数组的总的格子数
}SeqList, * PSeqList;
  • 作用:定义了一个宏 INIT_SIZE,表示顺序表初始化时分配的内存大小(即初始容量)。

  • INIT_SIZE 被设置为 10,表示初始化时会分配 10 个元素的空间。

  • 结构体名称SeqList,表示顺序表的结构体。

  • 指针类型别名PSeqList,表示指向 SeqList 的指针。

  • ELEM_TYPE* 表示 elem 是一个指针,指向 ELEM_TYPE 类型的数据。ELEM_TYPE 是一个类型别名

4.1初始化

void Init_SeqList(struct SeqList* psl)
{
	//0.安全处理   每一个函数都要写的
	assert(nullptr != psl);
	if (nullptr == psl)
	{
		exit(EXIT_FAILURE);
	}

	//1.对我们的 elem 用来去malloc 在堆区购买一块连续的空间
	psl->elem = (ELEM_TYPE*)malloc(INIT_SIZE * sizeof(ELEM_TYPE));
	if (NULL == psl->elem)
	{
		exit(EXIT_FAILURE);
	}

	//2.对我们的 length 初始化为0
	psl->length = 0;

	//3.对我们的 listsize 初始化为 INITSIZE
	psl->listsize = INIT_SIZE;

}
  • 类型转换malloc 返回的是 void* 类型的指针,需要强制转换为 ELEM_TYPE*

  • 安全检查:如果 malloc 分配失败(返回 NULL),程序会退出。

  • length:表示顺序表中当前存储的元素个数,初始值为 0。

  • listsize:表示顺序表当前分配的总容量,初始值为 INIT_SIZE

  • psl->elem 存储了这块内存的首地址。

  • 通过 psl->elem[i] 可以访问顺序表中的第 i 个元素。

  • 存储元素elem 指向的内存空间被用来存储顺序表中的所有元素。例如,如果 elem 指向的内存空间大小为 INIT_SIZE,则可以存储 INIT_SIZEELEM_TYPE 类型的元素。

4.2 插入

4.2.1头插

bool Insert_Seqlist_head(PSeqList psl, ELEM_TYPE val)
{
	//0.assert
	//0.5 判满
	if (Is_Full(psl))
	{
		Increase(psl);
	}

	//此时,肯定有空闲格子

	//1.集体向后挪(尾巴先动)
	for (int i = psl->length - 1; i >= 0; i--)
	{
		psl->elem[i + 1] = psl->elem[i];
	}

	//2.将val放入0号下标
	psl->elem[0] = val;

	//3.有效值个数+1
	psl->length++;
	return true;
}
  • 逻辑:从顺序表的尾部开始,逐个将元素向后移动一个位置。

    psl->elem[i + 1] = psl->elem[i]:将第 i 个元素移动到第 i + 1 个位置。
  • 循环条件:从 psl->length - 1 开始,直到 i = 0,确保所有元素都向后移动。

  • 更新顺序表的长度,反映新插入的元素。

  • 函数返回 true,表示插入操作成功

psl->length 表示顺序表中当前存储的有效元素的个数。例如:如果 psl->length 的值为 5,说明顺序表中有 5 个有效元素。

psl->length - 1 是对 psl->length 的值减去 1,如果 psl->length 为 5,那么最后一个有效元素的索引为 5 - 1 = 4。常用于从顺序表的最后一个有效元素开始,逐个向前遍历所有元素

4.2.2 尾插

bool Insert_Seqlist_tail(PSeqList psl, ELEM_TYPE val)
{
	//0.assert

	//0.5 判满
	if (Is_Full(psl))
	{
		Increase(psl);
	}

	//此时,肯定有空闲格子
	psl->elem[psl->length] = val;

	psl->length++;

	return true;
}

4.2.3 按位置插

bool Insert_Seqlist_pos(PSeqList psl, ELEM_TYPE val, int pos)
{
	//默认pos==0 则认为是头插

	//0.安全性处理   psl    pos合法性判断
	assert(nullptr != psl);
	assert(pos >= 0 && pos <= psl->length);

	//0.5 判满
	if (Is_Full(psl))
	{
		Increase(psl);
	}

	//此时,肯定有空闲格子
	//1.将插入位置之后的元素,统一向后挪动,把插入位置给空出来
	for (int i = psl->length - 1; i >= pos; i--)
	{
		psl->elem[i + 1] = psl->elem[i];
	}

	//2.插入

	psl->elem[pos] = val;

	//3.length++
	psl->length++;

	return true;
}

通过 psl->elem[i] 可以访问顺序表中的第 i 个元素。

4.3 删除

4.3.1 头删

bool Del_Seqlist_head(SeqList* psl)
{
	//0.assert

	//0.5 判空
	if (Is_Empty(psl))
		return false;

	//1.除了第一个元素之外,统一向前挪动
	for (int i = 1; i <= psl->length - 1; i++)
	{
		psl->elem[i - 1] = psl->elem[i];
	}

	//2.有效值个数-1
	psl->length--;

	return true;
}

//1.除了第一个元素之外,统一向前挪动
    for (int i = 1; i <= psl->length - 1; i++)
    {
        psl->elem[i - 1] = psl->elem[i];
    }

 //1.集体向后挪(尾巴先动)
    for (int i = psl->length - 1; i >= 0; i--)
    {
        psl->elem[i + 1] = psl->elem[i];
    }

4.3.2 尾删

//尾删
bool Del_Seqlist_tail(SeqList* psl)
{
	//0.assert

	//0.5 判空
	if (Is_Empty(psl))
		return false;

	psl->length--;

	return true;
}

 4.3.3 按位置删

bool Del_Seqlist_pos(SeqList* psl, int pos)
{
	//0.assert psl pos
	assert(psl != NULL);
	assert(pos >= 0 && pos < psl->length);

	//0.5 判空isempty
	if (Is_Empty(psl))
		return false;

	//1.将pos位置之后的有效值,统一向前覆盖(头先动)
	for (int i = pos + 1; i <= psl->length - 1; i++)
	{
		psl->elem[i - 1] = psl->elem[i];
	}


	//2.有效值个数-1
	psl->length--;

	return true;
}

4.3.4 按值删


//按值删(只删除这个val值出现的第一次的位置)
bool Del_Seqlist_val(SeqList* psl, ELEM_TYPE val)
{
	//0.assert
	//0.5 isempty

	//1.通过调用查找函数,查找val值在顺序表中的位置
	int index = Search_SeqList(psl, val);

	//2.若返回的位置下标为-1 返回假  若不等于-1,则此时怎么删
	if (index == -1)
		return false;

	return Del_Seqlist_pos(psl, index);
}

4.4 查找 


//4.查找数据是否已经存在(若存在,则只需要返回下标即可  找不到返回-1)
int Search_SeqList(PSeqList psl, ELEM_TYPE val)
{
	//0.assert

	for (int i = 0; i < psl->length; i++)
	{
		if (psl->elem[i] == val)
			return i;
	}

	return -1;
}

4.5 删除值val出现的位置

//删除当前val值出现的所有位置(1)
bool Del_SeqList_All_Val1(struct SeqList* psl, ELEM_TYPE val)
{
	int count = 0;
	for (int i = 0; i < psl->length; i++)
	{
		if (psl->elem[i] == val)
		{
			count++;
		}
	}

	for (int i = 0; i < count; i++)
	{
		int index = Search_SeqList(psl, val);
		Del_Seqlist_pos(psl, index);
	}

	return true;

}

 

//删除当前val值出现的所有位置(2)
bool Del_SeqList_All_Val2(struct SeqList* psl, ELEM_TYPE val)
{
	int qianfangkongxiangezishu = 0;
	for (int i = 0; i < psl->length; i++)
	{
		if (psl->elem[i] == val)
			qianfangkongxiangezishu++;
		else
			psl->elem[i - qianfangkongxiangezishu] = psl->elem[i];
	}
	psl->length = psl->length - qianfangkongxiangezishu;
	return true;
}

4.6 其余操作

//5.判空
bool Is_Empty(PSeqList psl)
{
	return psl->length == 0;
}

//6.判满
bool Is_Full(PSeqList psl)
{
	return psl->length == psl->listsize;
}

//7.扩容函数(1.5 2)   默认用2倍扩容
void Increase(PSeqList psl)
{
	ELEM_TYPE* tmp = (ELEM_TYPE*)realloc(psl->elem, psl->listsize * sizeof(ELEM_TYPE) * 2);
	if (tmp != nullptr)
	{
		psl->elem = tmp;
	}

}

//8.清空  (不释放已购买的内存)
void Clear(PSeqList psl)
{
	//malloc申请空间先不释放,而是认为所有格子里都是无效值
	psl->length = 0;
}

//9.销毁  (需要释放malloc购买的内存的)
void Destroy(PSeqList psl)
{
	free(psl->elem);
	psl->length = psl->listsize = 0;
}


//打印
void Show(PSeqList psl)
{
	//assert

	for (int i = 0; i < psl->length; i++)
	{
		printf("%d ", psl->elem[i]);
	}

	printf("\n");

}

4.7 主函数测试

int main()
{
	struct SeqList sq;

	Init_SeqList(&sq);

	Insert_Seqlist_head(&sq, 100);
	Insert_Seqlist_head(&sq, 101);
	Insert_Seqlist_head(&sq, 102);
	Insert_Seqlist_tail(&sq, 200);
	Insert_Seqlist_tail(&sq, 201);
	Insert_Seqlist_tail(&sq, 202);
	Insert_Seqlist_tail(&sq, 2000);
	Insert_Seqlist_tail(&sq, 2010);
	Insert_Seqlist_tail(&sq, 2020);
	Insert_Seqlist_pos(&sq, 10000, 3);
	Show(&sq);

	Insert_Seqlist_head(&sq, 111);
	Insert_Seqlist_tail(&sq, 222);
	Show(&sq);

	//删除
	Del_Seqlist_head(&sq);
	Del_Seqlist_tail(&sq);
	Show(&sq);

	Del_Seqlist_pos(&sq, 4);
	Show(&sq);
	Del_Seqlist_pos(&sq, 8);
	Show(&sq);
	Del_Seqlist_pos(&sq, 0);
	Show(&sq);

	Del_Seqlist_val(&sq, 201);
	Show(&sq);

	//Clear(&sq);
	//Show(&sq);

	//Destroy(&sq);
	//Show(&sq);

	//------------------------------------------------
	Insert_Seqlist_pos(&sq, 3, 2);
	Insert_Seqlist_pos(&sq, 3, 4);
	Insert_Seqlist_pos(&sq, 3, 6);
	Show(&sq);

	Del_SeqList_All_Val2(&sq, 3);
	Show(&sq);

	return 0;
}


http://www.kler.cn/a/584675.html

相关文章:

  • PostgreSQL16 的双向逻辑复制
  • Netty基础—4.NIO的使用简介一
  • 【贪心算法5】
  • 使用DeepSeek完成一个简单嵌入式开发
  • 如何优化AI模型的Prompt:深度指南
  • 基于jvisualvm的内存监控与远程连接配置指南
  • K8s 1.27.1 实战系列(十)PV PVC
  • C# Unity 唐老狮 No.9 模拟面试题
  • Vue:其他指令
  • Qt的QMenu 和 QAction的样式设置
  • golang从入门到做牛马:第二十篇-Go语言接口:行为的“契约”
  • C#类型转换大总结
  • 4.3 数组和集合的初始及赋值
  • 云原生可观测性:智能运维的数据中枢
  • DeepSeek-R1深度解读
  • HarmonyOS开发 - 电商App实例三( 网络请求axios)
  • nginx中proxy_pass和root的区别
  • STL-List模拟
  • 【QT】:QT图形化界面相关准备工作
  • 【python运行Janus-Pro-1B文生图功能】