【数据结构】顺序表实现的层层分析！！

关注小庄顿顿解馋◍˃ ᗜ ˂◍

引言：本篇博客我们来认识数据结构其中之一的顺序表，我们将认识到什么是顺序表以及顺序表的实现，请放心食用~

文章目录

一.什么是顺序表
- 🏠 线性表
- 🏠 顺序表
二.顺序表的实现
- 🏠 静态顺序表
- 🏠 动态顺序表
- - 接口的实现
三.顺序表的优缺点

一.什么是顺序表

🏠 线性表

线性表是n个有相同特性数据元素的有限序列，是一种广泛使用的数据结构，常用的数据结构有链表，顺序表，队列和栈等

特点： 线性表在逻辑结构上是线性的(一条连续的直线),但在物理结构不一定连续。

理解：比如我们在排队时，我们脑海中认为我们队伍应该是排成一条直线的，实际上也应该如此，这里就是类似我们待会要讲的顺序表，但有有时不免有人会插队三五成群排在队伍左右边，类似我们线性表中的链表。

🏠 顺序表

顺序表是由一块连续的物理内存空间构成的，也就是说它的逻辑结构是线性，物理结构也是线性的。

那有什么结构是连续的一块的内存空间呢？

这里我们就可以用我们的数组来实现顺序表，你也可以理解为顺序表本质就是数组

二.顺序表的实现

我们一般用顺序表实现对我们的数据进行增删查改操作，来很好地运用我们的数据，顺序表一般分为静态顺序表和动态顺序表。

顺序表结构的分析
我们既然知道顺序表的本质是数组,那我们需要定义一个数组；
其次我们要对我们的数据进行增删查改操作，那我们进行增的时候得知道我们空间有多少容量吧，同时我们进行删除操作时也需要有“边界感”，如果不知道顺序表有没有数据就麻烦了。

因此，我们可以定义一个size来表示有效数据个数,用一个capacity代表顺序表的容量
在这里插入图片描述
注：这里由于数组下标是从0开始，所以我们的size要往前一步跟下标同步

🏠 静态顺序表

静态顺序表：使用定长数组来存储元素

静态顺序表的封装

//静态顺序表
typedef int Datatype;//相同类型元素 方便不同数据类型直接替换
#define N 100
struct Seqlist
{Datatype arr[N];int size;int capacity;
};

缺点: 静态顺序表的数组长度是限定的,导致无法灵活存放数据。空间大了导致浪费，空间小了导致数据丢失。

因此，在实际中，我们采用动态顺序表来操作我们的数据

🏠 动态顺序表

C语言动态内存管理工作是给我们程序员做的，给我们提供更多的灵活性，由程序员决定空间何时申请和释放。我们可利用这特点实现动态顺序表

//动态顺序表
typedef int Datatype; 
typedef struct Seqlist
{Datatype * arr;int size;int capacity;
}Seqlist;

接口的实现

顺序表的初始化

void InitSeqlist(Seqlist* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

注：这里要传结构体指针，通过传址调用来修改size和capacity

顺序表的打印
这里就体现size的用处了，从下标0开始，到size就停止打印

void PrintSeqlist(Seqlist* ps)
{assert(ps->size != 0);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}
}

顺序表的头插和尾插

顺序表的头插和尾插我们需要解决容量问题
对于空顺序表和空间足够的顺序表我们自然无需担心，但对于size==capacity时的顺序表就需要扩容了，那该怎么扩呢？

我们有三种扩容方式：

一次扩容一个空间
一次扩容固定大小空间
成倍数扩容（1.5或2倍）
理解：对于第一种扩容方式，有限次数扩容还好，但多次扩容会降低效率；对于第二种空间给少会数据丢失，给多会空间浪费
最好方法就是成倍扩容，参考文章数组成倍扩容原因

因此进行尾插和头插前要判断是否扩容，不够就成倍扩

void Capacity(Seqlist* ps)
{assert(ps);int newcapacity = 0;if (ps->capacity == ps->size){newcapacity = ps->capacity == 0 ? 4 : 2 * newcapacity;int* temp = (int*)realloc(ps->arr,newcapacity * sizeof(int));if(NULL == temp){perror("realloc failed");exit(1);}ps->arr = temp;}ps->capacity = newcapacity;
}

尾插直接让size下标的空间用来赋值就可以了

void Pushtail(Seqlist* ps, Datatype x)
{assert(ps);//判断是否要扩容Capacity(ps);ps->arr[ps->size++] = x;
}

注：插入数据，size代表的有效数据个数也要增加

头插要先实现数据的左移再插入

void Pushhead(Seqlist* ps, Datatype x)
{assert(ps);//判断容量问题Capacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

顺序表的头删和尾删
请思考一个问题，清除数据，是否一定要删除这个数据？
当然不是的，我们用不了这个数据使它失效也是可以的

尾删

void Deltail(Seqlist* ps)
{assert(ps->size);assert(ps);ps->size--;
}

头删直接左移数据再使数据无效即可

void Delhead(Seqlist* ps)
{assert(ps->size);assert(ps);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;//删除数据不代表一定要删除
}

注：删除数据，要使size代表的有效数据个数对应减少

指定位置删除数据和指定位置之前插入数据

删除数据注意size–就可以了，直接循环遍历到pos位置

void PosDel(Seqlist* ps, int pos)
{assert(ps);assert(ps->size);assert(pos > 0&&pos<=ps->size);//pos等于sizeif (pos == ps->size){ps->size--;return;}for (int i = pos - 1; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

注意 pos与下标差了1 还有pos的合法性

指定位置插入数据也是可以按照循环移动数据但要注意容量问题

void PosPush(Seqlist* ps, Datatype x, int pos)
{assert(ps);//要确保插入位置的合法性assert(pos >= 0 && pos < ps->size);int i = 0;Capacity(ps);for (i = ps->size; i > pos-1; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos-1] = x;ps->size++;
}

注意 pos合法性和下标关系

延伸：对于指定位置的插入和删除也可以采用memmove来实现

//顺序表的指定位置插入（memmove实现）
void SLInsert1(SL* ps, int pos, Datatype x)
{assert(ps);//要确保插入位置的合法性assert(pos >= 0 && pos < ps->size);Datatype arr2[1] = { 0 };arr2[0] = x;memmove(ps->arr+pos+1,ps->arr+pos,(ps->size-pos)*sizeof(Datatype));memmove(ps->arr + pos, arr2, 4);ps->size++;//记得插入后size要增加
}//顺序表指定位置的删除(memmove)
void SLErase1(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos <= ps->size);memmove(ps->arr+pos,ps->arr+pos+1,(ps->size-pos-1)*sizeof(Datatype));ps->size--;
}

查找数据
直接遍历即可

void SLFind(Seqlist* ps, Datatype x)
{assert(ps);assert(ps->size);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){printf("找到了下标为%d", i);return;}}printf("没找到!");return;
}