顺序表详解

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️

一，线性表

定义：是一种逻辑结构，定义是：n个相同数据类型元素的有限序列，元素之间是一对一的相邻关系。

解析：也就是元素之间的关系是线性的，一个接着一个的，元素之间不会出现分支，都是一个接着一个的，逻辑上是线性的，这就是线性表的概念

二，顺序表

引言：顺序表是线性表的一种，线性表是规定了元素之间不出现分支，都是一个接着一个，逻辑上是线性的，但是没规定物理结构上是不是连续排列的

定义：逻辑上元素是线性的，并且物理结构上，元素是在内存中连续存放的，这就是顺序表

三，实现顺序表(动态)

顺序表的物理结构上是连续存放的元素，所以顺序表的底层就是数组，但是数组如果大小固定，那就是静态顺序表，用一个固定大小的数组进行封装，如果连续存放的空间是动态开辟的，那这个空间的大小就是动态的，和数组一样的物理存储结构，连续存放，这种用动态内存开辟的顺序表，就叫做动态顺序表

动态顺序表码源

• SeqList.h ⬇️⬇️⬇️

#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<assert.h>#include<stdlib.h>//动态顺序表typedefintSLDataType;//重命名这个顺序表里面元素的类型typedefstructSeqList{SLDataType*arr;//动态内存空间的地址：指针变量intcapacity;//顺序表的大小intsize;//顺序表实际存储的元素的个数}SL;//顺序表初始化voidSLInit(SL*ps);//只能传址调用，因为这个函数实现的就是初始化，在这之前顺序表没有初始化，无法进行传值调用//顺序表头插和尾插voidSLPushFront(SL*ps,SLDataType x);voidSLPushBack(SL*ps,SLDataType x);//顺序表的头删和尾删voidSLPopFront(SL*ps);voidSLPopBack(SL*ps);//指定位置之前插入数据voidSLInsert(SL*ps,intpos,SLDataType x);//指定位置删除数据voidSLErase(SL*ps,intpos);//顺序表销毁voidSLDestroy(SL*ps);//顺序表打印voidSLPrint(SL*ps);//顺序表中查找xintSLFind(SL*ps,SLDataType x);

• SeqList.c ⬇️⬇️⬇️

#define_CRT_SECURE_NO_WARNINGS1#include"SeqList.h"//顺序表初始化voidSLInit(SL*ps){ps->arr=NULL;ps->capacity=ps->size=0;}//顺序表销毁voidSLDestroy(SL*ps){assert(ps);if(ps->arr){free(ps->arr);}ps->arr=NULL;ps->capacity=ps->size=0;}//顺序表扩容voidSLCheckCapacity(SL*ps){if(ps->capacity==ps->size){intnewcapacity=ps->capacity==0?4:2*sizeof(ps->capacity);SLDataType*tmp=(SLDataType*)realloc(ps->arr,newcapacity*sizeof(SLDataType));//扩容失败if(tmp==NULL){perror("realloc");exit(1);}//扩容成功ps->arr=tmp;ps->capacity=newcapacity;}}//顺序表打印voidSLPrint(SL*ps){for(inti=0;i<ps->size;i++){printf("%d ",ps->arr[i]);}printf("\n");}//顺序表头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);//传进来的不能为NULLSLCheckCapacity(ps);for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[0]=x;ps->size++;}//顺序表尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);ps->arr[ps->size]=x;ps->size++;}//顺序表头删voidSLPopFront(SL*ps){assert(ps);assert(ps->size);for(inti=1;i<ps->size;i++){ps->arr[i-1]=ps->arr[i];}ps->size--;}//顺序表尾删voidSLPopBack(SL*ps){assert(ps);assert(ps->size);ps->size--;}//指定位置之前插入数据voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);SLCheckCapacity(ps);if(pos>=0&&pos<=ps->size){for(inti=ps->size;i>pos;i--){ps->arr[i]=ps->arr[i-1];}}ps->arr[pos]=x;ps->size++;}//指定位置删除数据voidSLErase(SL*ps,intpos){assert(ps->size);if(pos>=0&&pos<ps->size){for(inti=pos;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}}ps->size--;}//顺序表中查找xintSLFind(SL*ps,SLDataType x){assert(ps);for(inti=0;i<ps->size;i++){if(ps->arr[i]==x){returni;}}return-1;}

• text.c

#define_CRT_SECURE_NO_WARNINGS1#include"SeqList.h"voidslTest01(){//ctrl + d 快速复制//调用初始化函数，初始化顺序表SL s1;SLInit(&s1);//初始化以后对顺序表进行增删查改的操作//SLPuchBack(&s1, 1);//SLPuchBack(&s1, 2);//SLPuchBack(&s1, 3);//SLPuchBack(&s1, 4);//SLPuchBack(&s1, 100);//SLPuchBack(&s1, 200);//SLPuchBack(&s1, 300);//SLPopFront(&s1);//SLPrint(&s1);//SLPuchBack(&s1, 1);//SLPuchBack(&s1, 2);//SLPuchBack(&s1, 3);//SLPuchBack(&s1, 4);//SLPuchBack(&s1, 5);//SLPuchBack(&s1, 6);//SLPuchBack(&s1, 7);//SLPopFront(&s1);//SLPopBack(&s1);//SLPrint(&s1);//SLPuchBack(&s1, 1);//SLPuchBack(&s1, 2);//SLPuchBack(&s1, 3);//SLPuchBack(&s1, 4);//SLPuchBack(&s1, 5);//SLPuchBack(&s1, 6);//SLPuchBack(&s1, 7);//SLInsert(&s1, 2, 100);//SLPrint(&s1);//SLInsert(&s1, 0, 1);//SLInsert(&s1, 1, 2);//SLInsert(&s1, 2, 3);//SLInsert(&s1, 3, 4);//SLErase(&s1, 2);//SLPrint(&s1);//SLPushBack(&s1, 1);//SLPushBack(&s1, 2);//SLPushBack(&s1, 3);//SLPushBack(&s1, 4);//SLPushBack(&s1, 5);//SLPushBack(&s1, 6);//int a = SLFind(&s1, 4);//if (a >= 0)//{// printf("找到了，下标为%d ", a);//}}intmain(){slTest01();return0;}

动态顺序表结构创建

动态顺序表底层空间存放数据的部分就是由动态内存开辟的空间，然后把地址赋给一个指针变量，通过这个指针变量对动态内存空间进行增删检改操作，而一个表，需要的基本要素有顺序表的大小，顺序表中存放的实际元素的个数，顺序表中数据存放位置的地址，这样就可以创建好我们的顺序表了⬇️⬇️⬇️

//动态顺序表typedefintSLDataType;//重命名这个顺序表里面元素的类型typedefstructSeqList{SLDataType*arr;//动态内存空间的地址：指针变量intcapacity;//顺序表的大小intsize;//顺序表实际存储的元素的个数}SL;

⬆️⬆️⬆️顺序表就是一个结构体，顺序表中存储数据的空间就是一个动态内存开辟的空间，然后把起始地址赋给结构体中的一个指针变量成员，这样这个指针变量就有了操作这个动态内存空间的能力，而指针变量的类型就是每次访问这个动态内存权限的大小，而动态内存开辟的空间是堆区连续的空间，所以这块空间也可以当作是数组的空间，待会使用下标引用操作符就会很方便，而一个顺序表中，除了需要存储数据的空间，还需要标记动态空间的有效数据个数，以及标记动态空间的总大小，这样才方便我们对顺序表进行增删检改的操作同时我们对顺序表进行操作的时候会经常用到结构体类型，用typedef 给结构体类型起一个短一点的别名是很方便我们之后使用结构体类型的

我们把所有函数的声明都放在SeqList.h文件中，这样在使用顺序表和对顺序表进行操作的时候，只要在操作文件中，如text.c中包含这个SeqList.h头文件即可，同时结构体类型的创建依然是创建在SeqList.h文件里面，之后要创建结构体变量或者对结构体进行操作的时候，只需要包含一个SeqList.h头文件就行了

顺序表初始化

//顺序表初始化voidSLInit(SL*ps){ps->arr=NULL;ps->capacity=ps->size=0;}

⬆️⬆️⬆️我们创建好顺序表结构以后，对顺序表所有的操作都是把顺序表传入一个对应功能的函数中，对这个顺序表进行操作，所以顺序表的初始化，也就是一个有着对顺序表进行初始化功能的函数，传入的参数自然就是这个顺序表的地址，也就是结构体地址，初始化函数形参为结构体指针变量，也就是顺序表指针变量，因为我们仅仅是初始化，并没有对顺序表进行存储数据，初始化就是对顺序表中的成员赋值，因为没有进行存储数据所以arr 为 NULL，capacity 和 size 为0

顺序表空间开辟和扩容

//顺序表扩容voidSLCheckCapacity(SL*ps){if(ps->capacity==ps->size){intnewcapacity=ps->capacity==0?4:2*sizeof(ps->capacity);SLDataType*tmp=(SLDataType*)realloc(ps->arr,newcapacity*sizeof(SLDataType));//扩容失败if(tmp==NULL){perror("realloc");exit(1);}//扩容成功ps->arr=tmp;ps->capacity=newcapacity;}}

⬆️⬆️⬆️只有当capacity 和 size 相等的时候，顺序表中才无法存储数据，需要扩容，所以 if (ps->capacity == ps->size) 进入扩容，但是我们给顺序表初始化的时候给capacity 和 size 都赋值为0，所以我们要用一个三目操作符进行判断，如果capacity 为 0 的话，capacity == 0 的话，那就先给newcapacity 初始化4个元素，如果不为0，那就按原来空间大小的两倍进行扩容，记住这里的 capacity 只是一个数字，记录顺序表空间的大小，这个大小放在了realloc函数的参数中，就代表了字节数了，内存分配好了以后，就把新的大小赋给newcapacity,。然后我们用realloc函数对动态空间进行扩容，大小为newcapacity * 对应的元素类型大小，sizeof(SLDataType),老规矩把创建好的空间的地址放入另一个指针变量中，如果realloc开辟失败，也不会把原来动态内存空间的起始地址弄丢，扩容成功就把tmp 赋给 arr,然后把新的空间的大小赋给原空间的大小

顺序表的打印

//顺序表打印voidSLPrint(SL*ps){for(inti=0;i<ps->size;i++){printf("%d ",ps->arr[i]);}printf("\n");}

⬆️⬆️⬆️如果需要打印顺序表来直观的验证数据存入情况，就可以打印顺序表，传入顺序表的地址，使用下标引用操作符访问size之前的每一个元素，size是顺序表中有效的元素个数，但是如果作为下标的话，那就刚刚好是剩余空间的第一个元素的空间，之前就说过下标引用操作符就是arr[i] = *(arr + i)解引用，所以使用下标引用操作符对连续的空间进行访问的时候，就可以达到和访问数组一样的效果，因为和数组一样空间都是连续的，打印到下标size之前就可以打印出来所有元素

顺序表头插

//顺序表头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);//传进来的不能为NULLSLCheckCapacity(ps);for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[0]=x;ps->size++;}

⬆️⬆️⬆️参数传入顺序表和需要插入的数据，断言传进来的不能是NULL必须是顺序表的地址，任何插入都需要判断空间够不够如果不够就扩容，头插在第一个元素空间的位置插入数据，所以就要把所有数据的位置往后挪，腾出来第一个元素的空间，然后把需要插入的元素放进去就行，记得进行插入操作以后要对size++

顺序表尾插

//顺序表尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);ps->arr[ps->size]=x;ps->size++;}

⬆️⬆️⬆️判断传入地址是否为NULL以及判断空间够不够之后，在size放入需要插入的数据就可以了

顺序表头删

//顺序表头删voidSLPopFront(SL*ps){assert(ps);assert(ps->size);for(inti=1;i<ps->size;i++){ps->arr[i-1]=ps->arr[i];}ps->size--;}

⬆️⬆️⬆️逻辑就是把从第二个元素开始的所有的元素都往前挪动一个元素大小的空间，而且是从前往后挪，保证后面元素的顺序不变

顺序表尾删

/顺序表尾删voidSLPopBack(SL*ps){assert(ps);assert(ps->size);ps->size--;}

⬆️⬆️⬆️逻辑就是把size–即可，因为size定义的是有效元素的个数，size作为下标的时候我们是不会去访问到size对应的空间的，因为这个空间代表无元素，所以只要把size–就可以代表删除了最后的一个元素，因为这个元素，在我们操作函数中是访问不到的

顺序表指定位置之前插入数据

voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);SLCheckCapacity(ps);if(pos>=0&&pos<=ps->size){for(inti=ps->size;i>pos;i--){ps->arr[i]=ps->arr[i-1];}}ps->arr[pos]=x;ps->size++;}

⬆️⬆️⬆️插入的位置不可以随便插入，pos不可以插入到顺序表以外的空间，所以我们要对pos的大小进行限定，限定在有效元素中进行指定位置之前插入数据的操作，逻辑是把指定位置元素以及指定位置之后的元素都往后挪一个元素，因为在指定位置之前插入元素，这个插入的元素就把占据指定位置的空间，其他的元素都要往后挪，这样的话，只要把指定位置以及之后的元素都往后挪就行了，再在指定位置把元素插入进去就行了

顺序表指定位置删除数据

voidSLErase(SL*ps,intpos){assert(ps->size);if(pos>=0&&pos<ps->size){for(inti=pos;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}}ps->size--;}

⬆️⬆️⬆️删除指定位置的元素的话，也要规定删除的位置，只能在有效数据的范围内删除元素，逻辑上只要把指定位置元素后面的元素都往前挪一个位置就行了，这样子的话，指定位置的元素就被后面的元素覆盖掉了，相当于删除了

顺序表中查找x

intSLFind(SL*ps,SLDataType x){assert(ps);for(inti=0;i<ps->size;i++){if(ps->arr[i]==x){returni;}}return-1;}

在顺序表中寻找x元素逻辑上只需要从顺序表中的第一元素开始把后面每一个元素都和需要寻找的元素进行比较即可

顺序表销毁

//顺序表销毁voidSLDestroy(SL*ps){assert(ps);if(ps->arr){free(ps->arr);}ps->arr=NULL;ps->capacity=ps->size=0;}

⬆️⬆️⬆️顺序表的销毁需要判断传进来的是不是有效的地址，也就是是不是NULL地址，然后只有arr不会NULL的时候才进行销毁，因为如果NULL为空的话，说明这个顺序表并没有空间，不需要进行销毁，使用free函数释放arr 的动态内存空间以后要记得把arr置为NULL,不让其变为野指针，把capacity 和 size 都赋为0即可。

总结删除操作函数

所有的删除函数进行操作的时候都需要统一执行几个操作：1 判断传进来的地址是不是NULL，我们需要的是顺序表的地址 2 判断有效元素size 是否为0 ，如果size为0则代表没有效元素，不需要进行删除 3 进行删除以后要对 size–

总结插入操作函数

1 判断传进来的地址是不是NULL，我们需要的是顺序表的地址 2 调用SLCheckCapacity 函数判断空间够不够，如果不够函数则进行扩容操作 3 对有效元素size++

总结文件

把文件分为 text.c 和 SeqList.c 和 SeqList.h 顺序表结构定义和所有函数的声明都放在SeqList.h文件里面，只要包含SeqList.h函数就可以调用所有我们创建的操作函数，SeqList.c文件中就负责实现我们创建的操作函数，最后在text.c函数中创建我们顺序表，并使用我们调用我们创建的操作函数对创建的顺序表进行操作

总结for循环逻辑和条件判断

for(inti=?;?;?){ps->arr[?]=ps->arr[?]}

⬆️⬆️⬆️当我们需要让数据挪位的时候需要判断1 从前往后，还是从后往前，确保未移动的数据不要被移动的数据覆盖 2 先写循环体内容，确保移动顺序的逻辑 3 最后初始语句和 判断语句中确定循环体的起点和终点

• 点击表格内对应链接跳转对应内容⬇️⬇️⬇️