【数据结构】万字超详解顺序表（比细狗还细）
我这个人走得很慢，但是我从不后退。 ——亚伯拉罕·林肯
目录
一.什么是线性表？
二.什么是顺序表？
三.接口函数的实现
1.创建工程
2.构造顺序表
3.初始化顺序表
3.初始化顺序表
4.顺序表的尾插
5.顺序表的头插
6.顺序表的尾删
7.顺序表的头删
8.在顺序表中查找一个数
9.在顺序表中指定位置插入
10.在顺序表中指定位置删除
11.在头插和尾插的功能实现可以使用指定位置插入的函数进行复用
四.很被动的实现顺序表
1.SeqList.h：
2.SeqList.c:
3.test.c:
五.以菜单的形式玩转顺序表
1.以菜单的形式写顺序表
六.主动的输入实现顺序表全部功能的代码
1.SeqList.h：
2.SeqList.c：
3.test.c：
一.什么是线性表？
线性表是最基本、最简单、也是最常用的一种数据结构。线性表是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
二.什么是顺序表？
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表其实就是数组，但是在数组的基础上，它还要求数据是从头开始的，并且是连续储存的，不能跳跃间隔。
这句话什么意思呢？我们举个例子来看：
#include<stdio.h>
int main()
{
int arr[5] = { 0 };
arr[4] = 5;
arr[1] = 6;
for (int i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
}
可以看出：数组可以跳着存入数据，不一定要连续。
总结：数组内存是连续的，但是储存数据可以不连续。 所以顺序表在数组的基础上还有一定的要求。
三.接口函数的实现
1.创建工程
创建工程我们也是像三子棋那样创建三个文件。SeqList.c，SeqList.h和test.c。
SeqList.h：函数的声明以及各种头文件。
SeqList.c：函数的实现，定义。
test.c：书写程序整体执行逻辑。
2.构造顺序表
构造顺序表一般有两种。
第一种：静态顺序表，使用定长数组来实现顺序表。
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费,开秒了不够用。
所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
第二种：动态顺序表，使用动态开辟的数组。
动态顺序表相对于静态顺序表来说，优点就是空间不够可以增容。
3.初始化顺序表
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a; //动态数组
size_t size; //有效的数据个数
size_t Capacity; //数组的容量大小
}SL;这里我们使用了两个typedef(类型重定义)。
第一个typedef将int定义为SLDateType，如果要定义其他的数据类型，如double，short，char等等只需要改变类型重定义这里，后面的也会跟着改变。
第二个typedef将结构体重新命名为SL。为了后面写结构体名称时，不那么麻烦，更方便简洁。
3.初始化顺序表
void SeqListInit(SL ps)//ps是形参
{
ps.a = 0;
ps.size = ps.Capacity = 0;
}
所以我们应当写成指针的形式，使用传址调用，这样改变形参也就会改变实参了。
正确的写法：
//初始化顺序表
void SeqListInit(SL*ps)
{
ps->a = NULL;//先将动态数组置为空指针
ps->size = ps->Capacity = 0;//有效个数和容量大小都设为0
}4.顺序表的尾插
尾插目的就是在动态数组的结尾开始放入数据，逐渐填充数组。
思路：
1.刚开始size和Capacity都初始化为的0，两个大小相等，肯定没法存放数据。然后我们开始扩容，把Capacity的值扩大为两倍，但是第一次Capacity的值为0，扩大两倍还是0。所以第一次我们把Capacity的值扩大为4，下一次就依次扩大为两倍。
2.然后把扩容的大小赋给动态数组的大小。
3.对动态数组进行尾插进数据，每插一个数据进去，a就加一次，直到a和Capacity的值大小一致，又重复1步骤，继续扩容。
//尾插
void SeqListPushBack(SL*ps, SLDateType x)
{
if (ps->size == ps->Capacity)//初始化都为0，肯定if成立进入语句
{ //这里一定要写成==，因为这里判断语句
int NewCapacity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;//这里使用一个三目操作符
SLDateType* temp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * NewCapacity);
if (temp == NULL)//如果开辟空间错误
{
printf("realloc is error\n");
exit(-1);//退出程序
}
ps->a = temp;
ps->Capacity = NewCapacity;
}
ps->a[ps->size] = x;
ps->size++;
}在test.c中的文件中，下面是我们要插入的5个数字。
void SeqListtest1()
{
SL s1;
SeqListInit(&s1);
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListPushBack(&s1, 5);
}我们再写一个打印函数，打印一下我们尾插的数据。
//打印函数
void SeqListprint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
这里说明我们尾插成功了，还是非常喜悦的。然后我们开始头插。
5.顺序表的头插
头插的方法：
注意事项：在头插的时候我们也要考虑容量的大小和数据个数的大小的关系，不够了，就要扩容。 尾插的时候也要考虑这种情况。我们不妨把扩容写成一个函数。每次有地方要扩容时，就调用一次，这样就很方便。
检查容量的函数：
//检查容量
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->Capacity)//初始化都为0，肯定if成立进入语句
{ //这里一定要写成==，因为这里判断语句
int NewCapacity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;//这里使用一个三目操作符
SLDateType* temp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * NewCapacity);
if (temp == NULL)//如果开辟空间错误
{
printf("realloc is error\n");
exit(-1);//退出程序
}
ps->a = temp;
ps->Capacity = NewCapacity;
}
}开始头插：
//头插
void SeqListPushFront(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);//检查容量
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[0] = x;
ps->size++;
}我们头插6，7两个数之后，打印出来看一下。
SeqListPushFront(&sl, 6);
SeqListPushFront(&sl, 7);
SeqListprint(&sl);
6.顺序表的尾删
尾删的方法非常简单，我们只需要把ps->size的值--即可，这样最后的数据自然会被删除。
//尾删
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);//这里断言一下，如果ps->size小于0之后，直接报错
ps->size--;
}这里调用三次尾删函数，所以就会依次删除三个后面的数字。
//尾删
printf("尾删之后为 ");
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListprint(&sl);
7.顺序表的头删
头删和头插的方法其实很相似，头插是往后面移动数据，而头删就是相反的，往前面移动数据。
后一个数字把前一个数字给覆盖掉，也就是头删了。
开始头删：
//头删
void SeqListPopFront(SL* ps)
{
int start = 0;
while (start < ps->size)
{
ps->a[start] = ps->a[start + 1];
start++;
}
ps->size--;
}
8.在顺序表中查找一个数
//在数组里面找一个数字，找到就返回下标，否则就是返回-1
int SeqListfind(SL* ps, SLDateType x)
{
int i = 0;
while (i < ps->size)
{
if (ps->a[i] == x)
{
return i;
}
i++;
}
return -1;
}//在数组里面找一个数字，找到就返回下标，否则就是返回-1
int ret=SeqListfind(&sl, 1);
if (ret != -1)
{
printf("找到数字1的下标为%d\n", ret);
}
else
printf("没找到\n");
9.在顺序表中指定位置插入
这个和头插是很相似的，只需要把你要指定的位置给往后面移动一位，然后你再把要插入的数字给填到空缺的位置即可。
注意事项：在插入数据的时候，我们必须要判断ps->size和ps->Capacity容量的大小。
即:判断容量的大小,所以我们在插入数据之前，需要调用检查容量的函数。
//在指定的位置插入一个数字
void SeqListInsert(SL* ps, int pos, SLDateType x)//pos是指定的下标位置
{
SeqListCheckCapacity(ps);//检查容量
int end = ps->size-1;
while (end>=pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
10.在顺序表中指定位置删除
这和头删是很相似的，只需要把指定的位置的后面的位置依次往前一位，把指定位置的地方给覆盖掉。
//在指定位置删除一个数字
void SeqListErase(SL* ps, int pos)
{
int end = pos;
while (end < ps->size)
{
ps->a[end] = ps->a[end + 1];
end++;
}
ps->size--;
}
11.在头插和尾插的功能实现可以使用指定位置插入的函数进行复用
之前说了在指定位置插入函数的功能实现是和头插和尾插函数是很相似的，这里我们就可以复用这个函数，来简化代码。
//头插
void SeqListPushFront(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);//检查容量
SeqListInsert(ps, 0, x);//调用插入函数来复用头插，头插就是在0的位置进行插入
} //头插
void SeqListPushFront(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);//检查容量
SeqListInsert(ps, 0, x);//调用插入函数来复用头插，头插就是在0的位置进行插入
}四.很被动的实现顺序表
1.SeqList.h：
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a; //动态数组
size_t size; //有效的数据个数
size_t Capacity; //数组的容量大小
}SL;
//初始化顺序表
void SeqListInit(SL*ps);
//尾插
void SeqListPushBack(SL*ps, SLDateType x);
//打印数据
void SeqListprint(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDateType x);
//尾删
void SeqListPopBack(SL* ps);
//头删
void SeqListPopFront(SL* ps);
//在数组里面找一个数字，找到就返回下标，否则就是返回-1
int SeqListfind(SL* ps, SLDateType x);
//在指定的位置插入一个数字
void SeqListInsert(SL* ps, int pos, SLDateType x);//pos是指定的下标位置
//在指定位置删除一个数字
void SeqListErase(SL* ps, int pos);
2.SeqList.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//检查容量
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->Capacity)//初始化都为0，肯定if成立进入语句
{ //这里一定要写成==，因为这里判断语句
int NewCapacity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;//这里使用一个三目操作符
SLDateType* temp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * NewCapacity);
if (temp == NULL)//如果开辟空间错误
{
printf("realloc is error\n");
exit(-1);//退出程序
}
ps->a = temp;
ps->Capacity = NewCapacity;
}
}
//初始化顺序表
void SeqListInit(SL*ps)
{
ps->a = NULL;//先将动态数组置为空指针
ps->size = ps->Capacity = 0;//有效个数和容量大小都设为0
}
//尾插
void SeqListPushFront(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);//检查容量
SeqListInsert(ps, ps->size, x);//调用插入函数来复用尾插，尾插就是在ps->size的位置进行插入
}
//打印函数
void SeqListprint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//头插
void SeqListPushFront(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);//检查容量
SeqListInsert(ps, 0, x);//调用插入函数来复用头插，头插就是在0的位置进行插入
}
//尾删
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);//这里断言一下，如果ps->size小于0之后，直接报错
ps->size--;
}
//头删
void SeqListPopFront(SL* ps)
{
int start = 0;
while (start < ps->size)
{
ps->a[start] = ps->a[start + 1];
start++;
}
ps->size--;
}
//在数组里面找一个数字，找到就返回下标，否则就是返回-1
int SeqListfind(SL* ps, SLDateType x)
{
int i = 0;
while (i < ps->size)
{
if (ps->a[i] == x)
{
return i;
}
i++;
}
return -1;
}
//在指定的位置插入一个数字
void SeqListInsert(SL* ps, int pos, SLDateType x)//pos是指定的下标位置
{
SeqListCheckCapacity(ps);//检查容量
int end = ps->size-1;
while (end>=pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//在指定位置删除一个数字
void SeqListErase(SL* ps, int pos)
{
int end = pos;
while (end < ps->size)
{
ps->a[end] = ps->a[end + 1];
end++;
}
ps->size--;
}
3.test.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
SL sl;
void SeqListtest1()
{
SeqListInit(&sl);//初始化顺序表
//尾插
printf("尾插的数据为 ");
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListprint(&sl);//打印函数
printf("\n");
//头插
printf("头插之后为 ");
SeqListPushFront(&sl, 6);
SeqListPushFront(&sl, 7);
SeqListprint(&sl);
printf("\n");
}
void SeqListtest2()
{
//尾删
printf("尾删之后为 ");
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListprint(&sl);
printf("\n");
//头删
printf("头删之后 ");
SeqListPopFront(&sl);
SeqListprint(&sl);
printf("\n");
}
void SeqListtest3()
{
//在数组里面找一个数字，找到就返回下标，否则就是返回-1
int ret=SeqListfind(&sl, 1);
if (ret != -1)
{
printf("找到数字1的下标为%d\n", ret);
}
else
printf("没找到\n");
//在指定的位置插入一个数字
printf("在下标为1的位置插入数字后为 ");
SeqListInsert(&sl, 1, 8);
SeqListprint(&sl);
//在指定位置删数字
printf("在下标为2的删除数字后为 ");
SeqListErase(&sl,2);
SeqListprint(&sl);
}
int main()
{
SeqListtest1();
SeqListtest2();
SeqListtest3();
return 0;
}五.以菜单的形式玩转顺序表
1.以菜单的形式写顺序表
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
SL sl;
SL* ps;
void test()
{
printf("\n*********************************\n");
printf("1.尾插 2.头插\n");
printf("3.尾删 4.头删\n");
printf("5.指定删 6.指定插\n");
printf("7.找一个数 -1.退出\n");
printf("**********************************\n");
printf("请选择你要进行的操作:>\n");
}
void Menutest()
{
SL sl;
SeqListInit(&sl);
int x = 0;
int y = 0;
int input = 0;
while (input != -1)
{
test();//每一次输入结束了，都会再次打印菜单
scanf("%d", &input);
switch (input)
{
case 1:
{
printf("请你输入要尾插的数字，以-1结束：");
scanf("%d", &x);
while (x != -1)//还是有缺陷，不能插入-1
{
SeqListPushBack(&sl, x);
scanf("%d", &x);
}
printf("尾插之后为：");
SeqListprint(&sl);
break;
}
case 2:
{
printf("请你输入要头插的数字，以-1结束：");
scanf("%d", &x);
while (x != -1)
{
SeqListPushFront(&sl, x);
scanf("%d", &x);
}
printf("尾插之后为：");
SeqListprint(&sl);
break;
}
case 3:
{
SeqListPopBack(&sl);
printf("尾删之后为：");
SeqListprint(&sl);
break;
}
case 4:
{
SeqListPopFront(&sl);
printf("头删之后为：");
SeqListprint(&sl);
break;
}
case 5:
{
printf("请你输入要删数字的下标：");
scanf("%d", &x);
SeqListErase(&sl, x);
printf("删除数字后：");
SeqListprint(&sl);
break;
}
case 6:
{
printf("请你输入要插数字的下标和数字：");
scanf("%d %d", &x, &y);
SeqListInsert(&sl, x, y);
printf("插入数字后：");
SeqListprint(&sl);
break;
}
case 7:
{
printf("请你输入你要找的数字:");
scanf("%d", &x);
int ret = SeqListfind(&sl, x);
if (ret != -1)
{
printf("查找的坐标为:");
printf("%d", ret);
}
break;
}
default:
printf("选择错误，请重新输入");
break;
}
}
}
int main()
{
Menutest();
SeqlistDestory(&sl);
return 0;
}六.主动的输入实现顺序表全部功能的代码
1.SeqList.h：
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a; //动态数组
size_t size; //有效的数据个数
size_t Capacity; //数组的容量大小
}SL;
//初始化顺序表
void SeqListInit(SL*ps);
//尾插
void SeqListPushBack(SL*ps, SLDateType x);
//打印数据
void SeqListprint(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDateType x);
//尾删
void SeqListPopBack(SL* ps);
//头删
void SeqListPopFront(SL* ps);
//在数组里面找一个数字，找到就返回下标，否则就是返回-1
int SeqListfind(SL* ps, SLDateType x);
//在指定的位置插入一个数字
void SeqListInsert(SL* ps, int pos, SLDateType x);//pos是指定的下标位置
//在指定位置删除一个数字
void SeqListErase(SL* ps, int pos);
//最后销毁空间
void SeqlistDestory(SL* ps);
2.SeqList.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//检查容量
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->Capacity)//初始化都为0，肯定if成立进入语句
{ //这里一定要写成==，因为这里判断语句
int NewCapacity = ps->Capacity == 0 ? 4 : ps->Capacity * 2;//这里使用一个三目操作符
SLDateType* temp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * NewCapacity);
if (temp == NULL)//如果开辟空间错误
{
printf("realloc is error\n");
exit(-1);//退出程序
}
ps->a = temp;
ps->Capacity = NewCapacity;
}
}
//初始化顺序表
void SeqListInit(SL*ps)
{
ps->a = NULL;//先将动态数组置为空指针
ps->size = ps->Capacity = 0;//有效个数和容量大小都设为0
}
//尾插
void SeqListPushBack(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);//检查容量
SeqListInsert(ps, ps->size, x);//调用插入函数来复用头插，头插就是在0的位置进行插入
}
//打印函数
void SeqListprint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
//头插
void SeqListPushFront(SL* ps, SLDateType x)
{
SeqListCheckCapacity(ps);//检查容量
SeqListInsert(ps, 0, x);//调用插入函数来复用头插，头插就是在0的位置进行插入
}
//尾删
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);//这里断言一下，如果ps->size小于0之后，直接报错
ps->size--;
}
//头删
void SeqListPopFront(SL* ps)
{
int start = 0;
while (start < ps->size)
{
ps->a[start] = ps->a[start + 1];
start++;
}
ps->size--;
}
//在数组里面找一个数字，找到就返回下标，否则就是返回-1
int SeqListfind(SL* ps, SLDateType x)
{
int i = 0;
while (i < ps->size)
{
if (ps->a[i] == x)
{
return i;
}
i++;
}
return -1;
}
//在指定的位置插入一个数字
void SeqListInsert(SL* ps, int pos, SLDateType x)//pos是指定的下标位置
{
SeqListCheckCapacity(ps);//检查容量
int end = ps->size-1;
while (end>=pos)
{
ps->a[end+1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size++;
}
//在指定位置删除一个数字
void SeqListErase(SL* ps, int pos)
{
int end = pos;
while (end < ps->size)
{
ps->a[end] = ps->a[end + 1];
end++;
}
ps->size--;
}
//最后销毁空间
void SeqlistDestory(SL* ps)
{
free(ps->a = NULL);
ps->size = ps->Capacity = 0;
}3.test.c：
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
SL sl;
SL* ps;
void test()
{
printf("\n*********************************\n");
printf("1.尾插 2.头插\n");
printf("3.尾删 4.头删\n");
printf("5.指定删 6.指定插\n");
printf("7.找一个数 -1.退出\n");
printf("**********************************\n");
printf("请选择你要进行的操作:>\n");
}
void Menutest()
{
SL sl;
SeqListInit(&sl);
int x = 0;
int y = 0;
int input = 0;
while (input != -1)
{
test();//每一次输入结束了，都会再次打印菜单
scanf("%d", &input);
switch (input)
{
case 1:
{
printf("请你输入要尾插的数字，以-1结束：");
scanf("%d", &x);
while (x != -1)//还是有缺陷，不能插入-1
{
SeqListPushBack(&sl, x);
scanf("%d", &x);
}
printf("尾插之后为：");
SeqListprint(&sl);
break;
}
case 2:
{
printf("请你输入要头插的数字，以-1结束：");
scanf("%d", &x);
while (x != -1)
{
SeqListPushFront(&sl, x);
scanf("%d", &x);
}
printf("尾插之后为：");
SeqListprint(&sl);
break;
}
case 3:
{
SeqListPopBack(&sl);
printf("尾删之后为：");
SeqListprint(&sl);
break;
}
case 4:
{
SeqListPopFront(&sl);
printf("头删之后为：");
SeqListprint(&sl);
break;
}
case 5:
{
printf("请你输入要删数字的下标：");
scanf("%d", &x);
SeqListErase(&sl, x);
printf("删除数字后：");
SeqListprint(&sl);
break;
}
case 6:
{
printf("请你输入要插数字的下标和数字：");
scanf("%d %d", &x, &y);
SeqListInsert(&sl, x, y);
printf("插入数字后：");
SeqListprint(&sl);
break;
}
case 7:
{
printf("请你输入你要找的数字:");
scanf("%d", &x);
int ret = SeqListfind(&sl, x);
if (ret != -1)
{
printf("查找的坐标为:");
printf("%d", ret);
}
break;
}
default:
printf("选择错误，请重新输入");
break;
}
}
}
int main()
{
Menutest();
SeqlistDestory(&sl);
return 0;
}