资讯专栏INFORMATION COLUMN

【数据结构】 动态存储的顺序表

xiaodao / 909人阅读

摘要:文章目录顺序表的概念及结构分类静态顺序表使用定长数组存储元素。在数组上完成数据的增删查改。动态顺序表使用动态开辟的数组存储。结构体传参相关知识要有较好的掌握。

顺序表的概念及结构

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

分类

1. 静态顺序表:使用定长数组存储元素。

不常用,也不实用。需要根据情况提前确定容量。

2.动态顺序表:使用动态开辟的数组存储。

比较常用,通过动态开辟函数实现空间的开辟。可以做到用多少开辟多少。在空间开辟方面比较灵活。

相关接口的实现

动态开辟空间

数据结构

typedef int SLDateType;	typedef struct SeqList{	SLDateType* array;	size_t size;//实际容量	size_t capacity;//总容量}SeqList;

相关函数操作申明

//初始化内存空间extern void SeqListInit(SeqList *ps, int initCapacity);//内存空间释放extern void SeqListDestory(SeqList *ps);//输出函数extern void SeqListPrint(SeqList* ps);//尾插extern void SeqListPushBack(SeqList* ps, SLDateType x);//尾删extern void SeqListPopBack(SeqList* ps);//头插extern void SeqListPushFront(SeqList* ps, SLDateType x);//头删extern void SeqListPopFront(SeqList* ps);//查找  返回下标,-1表示未找到extern int SeqListFind(SeqList* ps, SLDateType x);// 顺序表在pos位置插入xextern void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);// 顺序表删除pos位置的值extern void SeqListErase(SeqList* ps, size_t pos);//测试函数extern void MyTsetFunction();

顺序表的操作相对较为简单,但应当注意细节。结构体传参相关知识要有较好的掌握。闲话少说,直接上代码:

相关代码分享

#include"SeqList.h"void SeqListInit(SeqList *ps, int initCapacity){	assert(ps);	ps->array = (SLDateType*)malloc(sizeof(SLDateType)*initCapacity);	if (NULL == ps->array)	{		return;	}	ps->capacity = initCapacity;	ps->size = 0;}void SeqListDestory(SeqList *ps){	assert(ps);	free(ps->array);	ps->array = NULL;	ps->capacity = 0;	ps->size = 0;}static void CheckCacpity(SeqList* ps){	if (ps->size == ps->capacity)	{		size_t newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//成倍扩大		ps->array = (SLDateType*)realloc(ps->array,sizeof(SLDateType)*newCapacity);		if (ps->array == NULL)		{			perror("realloc");			return;		}		ps->capacity = newCapacity;	}}void SeqListPrint(SeqList* ps){	assert(ps);	for (size_t i = 0; i < ps->size; i++)	{		printf("%d  ",ps->array[i]);	}	printf("/n");}//尾插void SeqListPushBack(SeqList* ps, SLDateType x){ 	assert(ps);	CheckCacpity(ps);	ps->array[ps->size] = x;	ps->size++;}//尾删void SeqListPopBack(SeqList* ps){	assert(ps);	ps->array[ps->size - 1] = 0;	ps->size--;}//头插void SeqListPushFront(SeqList* ps, SLDateType x){	assert(ps);	CheckCacpity(ps);	for (int i = ps->size - 1; i >= 0; i--)	{		ps->array[i + 1] = ps->array[i];	}	ps->array[0] = x;	ps->size++;}//头删void SeqListPopFront(SeqList* ps){	assert(ps);	for (size_t i = 1; i < ps->size; i++)	{		ps->array[i - 1] = ps->array[i];	}	ps->size--;}int SeqListFind(SeqList* ps, SLDateType x){	for (size_t i = 0; i < ps->size; i++)	{		if (ps->array[i] == x)			return i;	}	return -1;}void SeqListInsert(SeqList* ps, size_t pos, SLDateType x){	assert(ps);	if (pos > ps->size)		return;	CheckCacpity(ps);	for (size_t i = ps->size - 1; i >= pos; i--)	{		ps->array[i + 1] = ps->array[i];	}	ps->array[pos] = x;	ps->size++;}//删除pos处的数据void SeqListErase(SeqList* ps, size_t pos){	assert(ps);	if (pos<0 || pos>ps->size)		return;	for (size_t i = pos; i < ps->size-1; i++)	{		ps->array[i] = ps->array[i + 1];	}	ps->size--;}void MyTsetFunction(){	SeqList SL;	SeqListInit(&SL,5);	SeqListPushBack(&SL,1);	SeqListPushBack(&SL, 2);	SeqListPushBack(&SL, 3);	SeqListPushBack(&SL, 4);	SeqListPushBack(&SL, 5);	SeqListPrint(&SL);	SeqListPushFront(&SL, 2);	SeqListPushFront(&SL, 3);	SeqListPopBack(&SL);	SeqListPopFront(&SL);	SeqListInsert(&SL,5,100);	SeqListErase(&SL, 2);	SeqListPrint(&SL);	SeqListDestory(&SL);}

我采用的是多文件编辑的方式,详细源码见 我的Git,有需要的伙伴欢迎阅读~

最后,附上代码执行结果

思考与总结

1.顺序表的任意位置插入,时间复杂度高

任意位置插入数据,需要循环移动一部分数据,为要插入的数据腾出空间。所以它的时间复杂度为O(N);

2.扩容消耗大

增加容量时,需要对旧数据进行拷贝,并释放旧空间。此过程消耗太大。

3.扩容标准问题

增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。总之,扩容需要选择一个标准,但是实际情况总会出现空间浪费的情况。

如何解决?

下场的主角:链表~~,记得回访啊~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/125028.html

相关文章

  • 新学期预习吗?保姆级讲解数据结构顺序9个方法+手撕代码

    摘要:顺序表是一种使用数组存取的线性表。给位置的元素设为更新位置不合法删除第一次出现的关键字如下图,当前顺序表元素出现了两次,需要删除第一次出现的。 数据结构之顺序表 ...

    selfimpr 评论0 收藏0
  • 数据结构与算法之顺序

    摘要:前面的话本篇文章带大家认识数据结构与算法基础,顺序表动态,所谓的顺序表本质就是数组,它的特点是物理结构与逻辑结构都是连续的,最大的优点就是能够随机访问,最大的缺点是空间有限,就算扩容,也有可能存在大量的内存浪费。 ...

    roundstones 评论0 收藏0
  • 数据结构学习笔记--顺序

    摘要:优点实现方便,只需要会用数组就能够写出简单的静态顺序表。缺点相较于顺序表更难实现,有一定的使用门槛。顺序表实现顺序表结构静态顺序表结构由于静态顺序表不是本篇文章的主要内容所以只是稍微提及一下结构。 1.顺序表概念 顺序表是用以一段物理地址连续的存储单眼依次存储数据元素的线性结构,一般情况采用...

    haoguo 评论0 收藏0
  • 数据结构大总结(链篇)

    摘要:实际中更多是作为其他数据结构的子结构,如哈希桶图的邻接表等等。实际中使用的链表数据结构,都是带头双向循环链表。 文章目录 一.算法的时间复杂度和空间复杂度1.算法...

    不知名网友 评论0 收藏0
  • 数据结构 | 数组模拟实现顺序

    摘要:常见的线性表顺序表链表栈队列字符串顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。 目录 线性表和顺序表线性表顺序表...

    OldPanda 评论0 收藏0

发表评论

0条评论

xiaodao

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<