摘要:文章目录顺序表的概念及结构分类静态顺序表使用定长数组存储元素。在数组上完成数据的增删查改。动态顺序表使用动态开辟的数组存储。结构体传参相关知识要有较好的掌握。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
不常用,也不实用。需要根据情况提前确定容量。
比较常用,通过动态开辟函数实现空间的开辟。可以做到用多少开辟多少。在空间开辟方面比较灵活。
数据结构
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,有需要的伙伴欢迎阅读~
最后,附上代码执行结果
任意位置插入数据,需要循环移动一部分数据,为要插入的数据腾出空间。所以它的时间复杂度为O(N);
增加容量时,需要对旧数据进行拷贝,并释放旧空间。此过程消耗太大。
增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。总之,扩容需要选择一个标准,但是实际情况总会出现空间浪费的情况。
下场的主角:链表~~,记得回访啊~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/125028.html
摘要:顺序表是一种使用数组存取的线性表。给位置的元素设为更新位置不合法删除第一次出现的关键字如下图,当前顺序表元素出现了两次,需要删除第一次出现的。 数据结构之顺序表 ...
摘要:前面的话本篇文章带大家认识数据结构与算法基础,顺序表动态,所谓的顺序表本质就是数组,它的特点是物理结构与逻辑结构都是连续的,最大的优点就是能够随机访问,最大的缺点是空间有限,就算扩容,也有可能存在大量的内存浪费。 ...
摘要:优点实现方便,只需要会用数组就能够写出简单的静态顺序表。缺点相较于顺序表更难实现,有一定的使用门槛。顺序表实现顺序表结构静态顺序表结构由于静态顺序表不是本篇文章的主要内容所以只是稍微提及一下结构。 1.顺序表概念 顺序表是用以一段物理地址连续的存储单眼依次存储数据元素的线性结构,一般情况采用...
摘要:实际中更多是作为其他数据结构的子结构,如哈希桶图的邻接表等等。实际中使用的链表数据结构,都是带头双向循环链表。 文章目录 一.算法的时间复杂度和空间复杂度1.算法...
摘要:常见的线性表顺序表链表栈队列字符串顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。 目录 线性表和顺序表线性表顺序表...
阅读 910·2021-11-25 09:43
阅读 1418·2021-11-17 09:33
阅读 2947·2021-08-03 14:05
阅读 2001·2019-08-29 15:35
阅读 532·2019-08-29 13:30
阅读 3051·2019-08-29 13:20
阅读 2385·2019-08-23 18:15
阅读 1686·2019-08-23 14:57