摘要:在数组上完成数据的增删查改。静态顺序表的定长数组导致定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小。所以接下来我们就来实现动态顺序表。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可分为:
两者的结构区别如下图:
现实中,静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小。所以接下来我们就来实现动态顺序表。
初始化顺序表前我们首先要创建一个动态是顺序表:
typedef int SQDataType;//将指向数组的指针的类型重定义,方便后续类型的修改typedef struct SeqList //将该表重命名为 STL,方便操作{ SQDataType* a; //指向动态开辟的数组 int size; //有效数据个数 int capacity; //容量空间的大小}SLT;
初始化我们创建的顺序表:
void SeqListInit(SLT* ps1){ assert(ps1);//保证传入函数的参数不能为NULL ps1->a = NULL; ps1->size = ps1->capacity = 0;}
当一个数据要放入到顺序表中时,为了保证放入成功,我们通常要在放入前检查这个表的容量,若容量充足,则可放入,若容量已满,则需要进行增容:
void SeqListCheckCapacity(SLT* psl){ assert(psl); if (psl->size == psl->capacity) //当空间满时,进行动态扩容 { size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; //以两倍的方式扩容 psl->a = realloc(psl->a, newcapacity * sizeof(SQDataType)); psl->capacity = newcapacity; }}
在使用完顺序表后我们要销毁掉顺序表以避免内存泄露的问题,如下
void SeqListDestory(SLT* ps1){ assert(ps1); if (ps1->a) { free(ps1->a);//释放掉指针 ps1->a = NULL;//并将指针置空 } ps1->size = ps1->capacity = 0;}
为了能够看见我们对表的操作,我们还需一个打印出顺序表的接口:
void SeqListPrint(SLT* ps1){ assert(ps1); int i = 0; for (i = 0; i < ps1->size; i++) { printf("%d ", ps1->a[i]); } printf("/n");}
即在整个表的头部插入数据,实现头插我们要进行的操作就是将整个表的数据都向后挪动一个位置,这样顺序表的头部就会空出一个位置,我们将要插入的数据放入其中即可,实现如下:
void SeqListPushFront(SLT* psl, SQDataType x){ assert(psl); SeqListCheckCapacity(psl); //头插前检查容量是否满 int end = psl->size - 1; int i = 0; for (i = end; i >= 0; i--) { psl->a[i+1] = psl->a[i];//将数据都向后挪一个位置 } psl->a[0] = x; psl->size++; //头插后表的数据个数增加一个}
尾插就很简单实现,直接在表末放入数据即可
void SeqListPushBack(SLT* ps1, SQDataType x){ assert(ps1); SeqListCheckCapacity(ps1); ps1->a[ps1->size] = x; ps1->size++;}
当我们想在表的特定位置(任意位置)插入数据时,首先要知道想插入位置的下标(pos),然后依次再将表中从该下标开始到表尾的数据向后挪动一个位置,再将想插入的数据放入下标为 pos 的位置即可
void SeqListInsert(SLT* psl, size_t pos, SQDataType x){ assert(psl); assert(pos <= psl->size && pos >= 0); //保证插入的位置合理 SeqListCheckCapacity(psl); //插入前检查容量的大小 int end = psl->size; while (end > pos) { psl->a[end] = psl->a[end - 1];//表中的数据依次按从后向前的方式向后挪动 end--; } psl->a[pos] = x; psl->size++; //插入完后表中数据个数 +1}
头删只需将表中从第二个数据开始到最后一个数据都向前挪动一个位置,将第一个数据覆盖即可,然后整个表的数据个数减少一个
void SeqListPopFront(SLT* psl){ assert(psl); int begin = 1; for (begin = 1; begin < psl->size; begin++) { psl->a[begin - 1] = psl->a[begin];//表中的数据依次按从前向后的方式向前挪动 } psl->size--; //删除后数据-1}
实现起来非常简单,直接减掉最后一个数据即可(若要显示表的内容,则减去一个数据后,显示前size-1个数据即可)
void SeqListPopBack(SLT* ps1){ assert(ps1); ps1->size--;}
给定一个表中下标为 pos 的特定位置,删除该位置的数据只需将从将从该位置后的一个数据到表末的所有数据向前挪动一个位置,即将该pos处位置的数据覆盖即可
void SeqListErase(SLT* psl, size_t pos){ assert(psl); assert(pos < psl->size&& pos >= 0); //保证下标pos的合理性 int begin = pos; while (begin < psl->size) { psl->a[begin] = psl->a[begin + 1];//数据依次按从前向后的方式向前挪动 begin++; } psl->size--; //删除后数据-1}
即查找顺序表中特定位置 (下标为pos) 的数据,实现起来比较容易,将整个表遍历一遍即可
int SeqListFind(SLT* psl, SQDataType x){ assert(psl); int i = 0; for (i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; //若找到该数据,则返回该数据的下标 } } return -1; //若没有该数据,则返回-1}
即修改特定位置 (下标为pos) 的数据,在保证位置合理的情况下将要修改的值赋给该位置上的数据即可
void SeqListAt(SLT* psl, size_t pos, SQDataType x){ assert(psl); assert(pos < psl->size&& pos >= 0); psl->a[pos] = x;}
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/122142.html
单链表的基本操作【超详细备注和解释】 先赞后看好习惯 打字不容易,这都是很用心做的,希望得到支持你 大家的点赞和支持对于我来说是一种非常重要的动力 看完之后别忘记关注我哦!️️️ 强烈建议本篇收藏后再食用 文章目录 单链表基本介绍基本结构与顺序表的区别以及学习单链表的必要性 单链表的实现结点的定义以及头指针的创建单链表的遍历(打印接口的实现)【重点】开辟结点接口尾插接口尾删接口头插接口...
摘要:它是学习其他数据结构的基础。其中,用顺序存储结构表示的是顺序表,用链式存储结构表示的是链表。头插循环三要素,初始条件,,结束条件,,迭代过程。 线性表总结 文章目...
摘要:链表都有一个头指针,一般以来表示,存放的是一个地址。链表中的节点分为两类,头结点和一般节点,头结点是没有数据域的。链表的特性,使其在某些操作上比数组更加高效。例如当进行插入和删除操作时,链表操作的时间复杂度仅为。 ...
摘要:虽然有这么多的链表的结构,但是我们实际中最常用还是这两种结构单向无头不循环链表,双向带头循环链表,下面我们来学习这两种链表。 文章目录 链表一. 前言二. 链表的...
阅读 2247·2021-10-11 10:58
阅读 2548·2021-09-27 13:35
阅读 481·2021-09-23 11:22
阅读 814·2021-09-02 15:34
阅读 2680·2019-08-30 15:54
阅读 1462·2019-08-29 16:27
阅读 2325·2019-08-29 15:05
阅读 2225·2019-08-23 18:11