学习笔记---超基础+详细+新手的顺序表～～

---

目录

1.顺序表的前言

1.1 顺序表--->通讯录📇

1.2 数据结构的相关概念🏇

1.2.1 什么是数据结构

1.2.1 为什么需要数据结构

2. 顺序表概念及分类

2.1 顺序表的概念🐙

2.2 顺序表的分类🐫

2.2.1 顺序表和数组的区别

2.2.2 顺序表分类

1.静态顺序表

2. 动态顺序表 

3. 实现动态顺序表

3.1 要实现的目标🫵

3.2 创建（初始化）顺序表🌺

3.2.1 Seqlist.h

3.2.2 Seqlist.c

3.2.3 test.c

3.2.4 代码测试

3.3 销毁💥

3.3.1 Seqlist.h

3.3.2 Seqlist.c

3.3.3 test.c

3.3.4 代码测试

3.4 尾部插入数据🌈+打印顺序表

3.4.0 思路分析

3.4.1 Seqlist.h

3.4.2 Seqlist.c

3.4.3 test.c

3.4.4 代码测试

3.5 头部插入数据💫

3.5.0 思路分析

3.5.1 Seqlist.h

3.5.2 Seqlist.c

3.5.3 test.c

3.5.4 代码运行测试

3.6 尾部删除数据⛄️

3.6.0 思路分析

3.6.1 Seqlist.h

3.6.2 Seqlist.c

3.6.3 test.c

3.6.4 代码运行测试

​编辑

3.7 头部删除数据🌊

3.7.0 思路分析

3.7.1 Seqlist.h

3.7.2 Seqlist.c

3.7.3 test.c

3.7.4 代码运行测试

3.8 指定位置之前插入数据🍿

3.8.0 思路分析

3.8.1 Seqlist.h

3.8.2 Seqlist.c

3.8.3 test.c

3.8.4 代码运行测试

3.9 指定位置删除数据⚾️

3.9.0 思路分析

3.9.1 Seqlist.h

3.9.2 Seqlist.c

3.9.3 test.c

3.9.4 代码运行测试

4.0 查找数据🍺

4.0.1 Seqlist.h

4.0.2 Seqlist.c

4.0.3 test.c

4.0.4 代码运行测试
​​​​​​​​​​​​​​

---

1.顺序表的前言

1.1 顺序表--->通讯录📇

我们前面学习了C语言，它能够帮助我们实现通讯录📇项目，要想实现通讯录项⽬有两个技术关键：

1）C语⾔语法基础

2）数据结构之顺序表/链表（链表我们下下期讲）

1.2 数据结构的相关概念🏇

1.2.1 什么是数据结构

数据结构是计算机存储、组织数据的⽅式

数据：肉眼可见的信息，例如：数值1，2......  网页信息......

结构：借助数组这样的数据结构将⼤量的同一类型的数据组织在⼀起

总结：

1）能够存储数据（如顺序表、链表等结构）

2）存储的数据能够⽅便查找

---

1.2.1 为什么需要数据结构

我们要知道最简单的数据结构是数组

通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操作。

---

但是，数组不满足于复杂场景数据的管理：

1.数组仅存储同类型的数据  eg.int  arr[10]     char  arr[10]

2.数组可提供的接口不足以支撑复杂场景的数据处理--->这就是为什么我们要学习其他的数据结构：通过数据结构，我们可以先写出底层逻辑，然后直接调用。例如C语言的sizeof

2. 顺序表概念及分类

2.1 顺序表的概念🐙

顺序表是线性表的一种。（他们的关系可以类比于西瓜🍉和水果的关系（包含关系））

线性表：指的是具有相同特性的一类数据结构的总称。常⻅的线性表：顺序表、链表、栈、队列、字符串... 

相同特性：在逻辑结构上一定是线性的，在物理结构上不一定是线性的

逻辑结构：人为想象出来的，排列起来成线性，例如排队在逻辑结构上就是线性的（像一条线一样排列）

物理结构：内存存储上按照线性排列，例如数组的每个元素地址在物理结构上就是线性的（相邻元素地址是连续的）

顺序表的底层结构是数组--->顺序表在逻辑结构上一定是线性的，在物理结构上也一定是线性的

2.2 顺序表的分类🐫

2.2.1 顺序表和数组的区别

◦ 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝

2.2.2 顺序表分类

1.静态顺序表

概念：使⽤定⻓数组存储元素

//静态顺序表
struct Seqlist
{
int a[100];//定长数组
int size;//有效数据个数
}

---

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费

---

2. 动态顺序表 

概念：使⽤动态数组存储元素

//动态顺序表
struct Seqlist
{
int* a;//动态数组
int size;//有效数据个数
int capacity;//空间大小
}

---

动态顺序表优点：按需申请空间，不造成浪费或者不够用，还可以扩容

---

3. 实现动态顺序表

这里，我们需要创建头文件和源文件

头文件：结构的实现和声明，函数的声明

源文件：函数的具体实现和代码运行的测试

从而，更加方便第三方使用

3.1 要实现的目标🫵

我们需要多个接口帮助我们实现：创建（初始化）、一系列具体操作、销毁

具体操作（一切以实现通讯录为目标）包括：头部/尾部插入数据、头部/尾部删除数据、打印出顺序、指定位置插入/删除/查找数据、

---

3.2 创建（初始化）顺序表🌺

3.2.1 Seqlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//创建动态顺序表
typedef int SLDataType;//方便以后修改数据类型，因为我们不一定每次都需要int类型
typedef struct Seqlist
{SLDataType* a;//动态数组int size;//有效数据个数int capacity;//空间大小
}SL;//重命名顺序表名称，更加简短方便输入//对顺序表初始化
void SLInit(SL* sl);//初始化的函数声明，注意传址调用--->否则形参只是实参的临时拷贝

---

3.2.2 Seqlist.c

#include"Seqlist.h"
void SLInit(SL* sl)
{sl->a = NULL;sl->size = sl->capacity = 0;
}

---

3.2.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{SL sl;SLInit(&sl);
}
int main()
{SLtest();return 0;
}

---

3.2.4 代码测试

---

3.3 销毁💥

3.3.1 Seqlist.h

//对顺序表销毁
void SLDestroy(SL* sl);//函数声明

---

3.3.2 Seqlist.c

注意⚠️

assert（断言）也可以判断sl->a是否是NULL，但是assert比较暴力，会导致程序直接终止，而下面的方法不会影响后面的程序

//对顺序表销毁
void SLDestroy(SL* sl)
{if (sl->a)free(sl->a);sl->a = NULL;sl->size = sl->capacity = 0;
}

---

3.3.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

3.3.4 代码测试

---

3.4 尾部插入数据🌈+打印顺序表

3.4.0 思路分析

由于尾插/头插都需要判断空间够不够，所以我们直接把判断空间十分足够的函数单提出来

---

对怎样扩容的进一步解释：

---

3.4.1 Seqlist.h

//打印顺序表
void SLPrint(SL* sl);//尾部插入数据
void SLPushBack(SL* sl, SLDataType x);

---

3.4.2 Seqlist.c

//判断空间是否足够
void SLCheckCapacity(SL* sl)
{if (sl->size == sl->capacity) {//空间不足，扩容2倍//判断sl->capacity是否为0int newcapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;//判断原空间是否是0，不是直接*2扩容，是0直接赋值4SLDataType* tmp = (SLDataType*)realloc(sl->a, newcapacity * 2 * sizeof(SLDataType));//采用中间值tmp接收扩容的新空间--->申请空间也不一定成功，如果我们直接让ps->a接收，//但是扩容失败了，那么ps->a的空间直接变成0了//所以我们需要判断一下扩容是否成功if (tmp == NULL){perror("realloc fail!\n");return 1;}sl->a = tmp;//sl->capacity *=2；错误--->因为前面我们初始化sl->capacity=0,0*2=0--->报错--->判断一下sl->capacity是否为0sl->capacity = newcapacity;//记录现有空间大小}
}
//尾部插入数据
void SLPushBack(SL* sl, SLDataType x)
{assert(sl);//不能传过来空指针SLCheckCapacity(sl);//判断空间是否足够//插入数据sl->a[sl->size++] = x;
}//打印顺序表
void SLPrint(SL* sl)
{for (int i = 0; i < sl->size; i++){printf("%d ", sl->a[i]);}printf("\n");
}

---

3.4.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//尾插测试SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);//打印SLPrint(&sl);//销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

3.4.4 代码测试

---

3.5 头部插入数据💫

3.5.0 思路分析

思路和尾插类似，只不过插入数据的位置变了

---

3.5.1 Seqlist.h

//头部插入数据
void SLPushFront(SL* sl, SLDataType x);

---

3.5.2 Seqlist.c

//头部插入数据
void SLPushFront(SL* sl, SLDataType x)
{assert(sl);SLCheckCapacity(sl);//判断空间是否足够//插入数据for (int i = sl->size - 1; i >=0 ; i--){//最后一次进来的是i=0sl->a[i + 1] = sl->a[i];}sl->a[0] = x;sl->size++;
}

---

3.5.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//尾插测试SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);//打印SLPrint(&sl);//1 2 3 4//头插测试SLPushFront(& sl, 5);//打印SLPrint(&sl);//5 1 2 3 4//销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

3.5.4 代码运行测试

---

3.6 尾部删除数据⛄️

3.6.0 思路分析

---

3.6.1 Seqlist.h

//尾部删除数据
void SLPopBack(SL* sl);

---

3.6.2 Seqlist.c

bool SLIsEmpty(SL* sl)
{//判断顺序表是否为空assert(sl);return sl->size == 0;
}
//尾部删除数据
void SLPopBack(SL* sl)
{assert(sl);assert(!SLIsEmpty(sl));//顺序表不能为空sl->size--;
}

---

3.6.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//尾插测试SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);//打印SLPrint(&sl);//1 2 3 4//头插测试SLPushFront(& sl, 5);//打印SLPrint(&sl);//5 1 2 3 4//尾删测试//尾部删除数据SLPopBack(&sl);//打印SLPrint(&sl);//5 1 2 3 //销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

3.6.4 代码运行测试

---

3.7 头部删除数据🌊

3.7.0 思路分析

我们需要将后面的数据往前移动一位

---

3.7.1 Seqlist.h

//头部删除数据
void SLPopFront(SL* sl);

---

3.7.2 Seqlist.c

//头部删除数据
void SLPopFront(SL* sl)
{assert(sl);assert(!SLIsEmpty(sl));//顺序表不能为空for (int i = 0; i < sl->size-1; i++){//最后一次进来的是size-2sl->a[i] = sl->a[i + 1];}sl->size--;
}

---

3.7.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//尾插测试SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);//打印SLPrint(&sl);//1 2 3 4//头插测试SLPushFront(& sl, 5);//打印SLPrint(&sl);//5 1 2 3 4//尾删测试//尾部删除数据SLPopBack(&sl);//打印SLPrint(&sl);//5 1 2 3 //头部删除数据SLPopFront(&sl);//打印SLPrint(&sl);// 1 2 3//销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

3.7.4 代码运行测试

---

3.8 指定位置之前插入数据🍿

3.8.0 思路分析

---

3.8.1 Seqlist.h

//指定位置之前插入数据
void SLInsert(SL* sl, int pos, SLDataType x);

---

3.8.2 Seqlist.c

//指定位置之前插入数据
void SLInsert(SL* sl, int pos, SLDataType x)
{assert(sl);assert(pos >= 0 && pos <= sl->size);//pos确保合法SLCheckCapacity(sl);//判断空间是否足够--->是否需要扩容for (int i = sl->size - 1; i > pos - 1; i--){//最后进来的是possl->a[i+1] = sl->a[i];}sl->a[pos]=x;sl->size++;
}

---

3.8.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//尾插测试SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);//打印SLPrint(&sl);//1 2 3 4//头插测试SLPushFront(& sl, 5);//打印SLPrint(&sl);//5 1 2 3 4//尾删测试//尾部删除数据SLPopBack(&sl);//打印SLPrint(&sl);//5 1 2 3 //头部删除数据SLPopFront(&sl);//打印SLPrint(&sl);// 1 2 3//指定位置之前插入数据SLInsert(&sl, 1, 4);//打印SLPrint(&sl);// 4 1 2 3//销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

3.8.4 代码运行测试

---

3.9 指定位置删除数据⚾️

3.9.0 思路分析

---

3.9.1 Seqlist.h

//指定位置删除数据
void SLErase（SL* sl, int pos）;

---

3.9.2 Seqlist.c

//指定位置删除数据
void SLErase(SL* sl, int pos)
{assert(sl);assert(!SLIsEmpty(sl));//顺序表若为空--->不能删除assert(pos >= 0 && pos <= sl->size);//pos确保合法for (int i = pos; i <sl->size-1 ; i++){//最后进来的是size-2sl->a[i] = sl->a[i + 1];}sl->size--;
}

---

3.9.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//尾插测试SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);//打印SLPrint(&sl);//1 2 3 4//头插测试SLPushFront(& sl, 5);//打印SLPrint(&sl);//5 1 2 3 4//尾删测试//尾部删除数据SLPopBack(&sl);//打印SLPrint(&sl);//5 1 2 3 //头部删除数据SLPopFront(&sl);//打印SLPrint(&sl);// 1 2 3//指定位置之前插入数据SLInsert(&sl,0,4);//打印SLPrint(&sl);// 4 1 2 3//指定位置删除数据SLErase(&sl, 2);//打印SLPrint(&sl);// 4 1 3//销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

3.9.4 代码运行测试

---

4.0 查找数据🍺

4.0.1 Seqlist.h

//查找数据
bool SLFind(SL* sl, SLDataType x);

---

4.0.2 Seqlist.c

//查找数据
bool SLFind(SL* sl, SLDataType x)
{assert(sl);for (int i = 0; i < sl->size; i++){if (sl->a[i] == x)return true;}return false;
}

---

4.0.3 test.c

#include"Seqlist.h"
void SLtest()//测试创建的顺序表和初始化的接口
{//初始化测试SL sl;SLInit(&sl);//尾插测试SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);//打印SLPrint(&sl);//1 2 3 4//头插测试SLPushFront(& sl, 5);//打印SLPrint(&sl);//5 1 2 3 4//尾删测试//尾部删除数据SLPopBack(&sl);//打印SLPrint(&sl);//5 1 2 3 //头部删除数据SLPopFront(&sl);//打印SLPrint(&sl);// 1 2 3//指定位置之前插入数据SLInsert(&sl,0,4);//打印SLPrint(&sl);// 4 1 2 3//指定位置删除数据SLErase(&sl, 2);//打印SLPrint(&sl);// 4 1 3//查找数据测试bool ret=SLFind(&sl, 3);if (ret){printf("找到了！\n");}else{printf("没找到！\n");}//销毁测试SLDestroy(&sl);
}int main()
{SLtest();return 0;
}

---

4.0.4 代码运行测试

---

本次的分享到这里就结束了！！！

PS：小江目前只是个新手小白。欢迎大家在评论区讨论哦！有问题也可以讨论的！

如果对你有帮助的话，记得点赞👍+收藏⭐️+关注➕