数据结构 —— 顺序表（超详细图解 & 接口函数实现）

系列文章目录

文章目录

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一种十分优秀的解决实际问题的模板，是先进思想的结晶。博主将会用代码结合大量图解，对数据结构进行深度剖析，以便大家更好的学习数据结构的思想。

一、示例问题：酒店住宿

1.住宿需求

某公司需要一串连续的房间让员工住宿，但不清楚有多少员工将会入住

2.住宿管理

公司：首先安排了 3 个员工入住酒店

酒店：安排了 3 个连续房间 1 - 3 号房间

公司：又安排了 2 个员工入住

酒店：

1. 后面的 4 号房间空闲，但 5 号房有其他人入住，无法直接向后开辟房间
2. 重现寻找连续的 5 个房间

公司：又安排了 2 个员工入住

酒店：后面的 6 号和 7 号房间均空闲，直接向后面开辟两个房间

到此酒店成功满足了该公司的需求，通过这个示例问题引出了我们下面将要讲的顺序表，它们可以完美的描述并解决上述问题。

二、顺序表的概念

1.定义

顺序表：用一段地址连续的存储单元依此存储线性表的数据元素

顺序表就像是军训时，同学们站成一排，从左往右报数，每个人对应一个序号，这些序号是一个接着一个的有序排列。数组就是顺序表的一种，每个位置站着一名同学，他的序号就是数组的下标，通过序号就能找到那个同学。

2.结构

顺序表的结构类型

//重定义类型typedefint SeqDateType;//便于更改存储类型//顺序表类型typedefstructSeqList{
    SeqDateType *array;//顺序表int size;//有效数据的个数int capacity;//总容量}SeqList;

3.存储

存储：用动态开辟的一维数组来实现顺序表的存储结构

三、顺序表的接口函数

1.初始化

对顺序表的内容进行初始设置

//初始化voidSeqListInit(SeqList *pq){assert(pq);
    pq->array =NULL;//指针置空
    pq->capacity = pq->size =0;//大小和容量赋值为0}

2.容量检查

判断是否达到最大容量

• 达到最大容量 —— 扩容
• 没有达到最大容量 —— 不扩容

//判断是否存满voidSeqCheckCapacity(SeqList *pq){assert(pq);if(pq->size == pq->capacity){int newcapacity =(pq->capacity ==0)?4:(pq->capacity *2);//判断是否开辟空间 若没有自动开辟
        SeqDateType *newA =(SeqDateType *)realloc(pq->array,sizeof(SeqDateType)* newcapacity);if(newA ==NULL){perror("realloc fail:");exit(-1);}
        pq->array = newA;
        pq->capacity = newcapacity;}}

达到最大容量 —— 扩容

3.指定位置插入

指定位置 pos 插入数据

//指定位置插入voidSeqListInsert(SeqList *pq,int pos, SeqDateType x){assert(pq);assert(pos >=0&& pos <= pq->size);//判断扩容SeqCheckCapacity(pq);//向后推移int end = pq->size;while(end > pos){
        pq->array[end]= pq->array[end -1];
        end--;}
    pq->array[pos]= x;
    pq->size++;}

4.指定位置删除

删除指定位置 pos 的数据

//指定位置删除voidSeqListErase(SeqList *pq,int pos){assert(pq);assert(pos < pq->size);//向前推移for(int i = pos +1; i < pq->size; i++){
        pq->array[i -1]= pq->array[i];}
    pq->size--;}

5.指定位置修改

修改指定位置 pos 的数据

//修改数据voidSeqListModify(SeqList *pq,int pos, SeqDateType x){assert(pq);assert(pos >=0&& pos < pq->size);
    pq->array[pos]= x;}

6.查找数据

查找指定数据

• 存在 —— 返回第一次查找到的位置
• 不存在 —— 返回 NULL

//查找数据intSeqListFind(SeqList *pq, SeqDateType x){assert(pq);//查找数据for(int i =0; i < pq->size; i++){if(pq->array[i]== x){//如果找到了返回位置return i;}}return-1;//如果没找到返回-1}

7.头部插入

利用指定位置插入实现头插

//头部插入voidSeqListPushFront(SeqList *pq, SeqDateType x){SeqListInsert(pq,0, x);}

8.头部删除

利用指定位置删除实现头删

//头部删除voidSeqListPopFront(SeqList *pq){SeqListErase(pq,0);}

9.尾部插入

利用指定位置插入实现尾插

//尾部插入voidSeqListPushBack(SeqList *pq, SeqDateType x){SeqListInsert(pq, pq->size, x);}

10.尾部删除

利用指定位置删除实现尾删

//尾部删除voidSeqListPopBack(SeqList *pq){SeqListErase(pq, pq->size -1);}

四、总结

顺序表是解决实际问题时极其常用的一种数据结构，是非常重要的解决问题的方式。顺序表的各种借口的复现，有利于更好的学习数据结构的思想，有利于开阔视野，学习前辈的智慧结晶。对我们后续解决实际问题也会有很大帮助。