在之前的C语言学习中我们已经深入理解了函数、指针、结构体、动态内存等知识点，在本篇中将利用这些知识点来实现顺序表，接下来就开始顺序表概念的了解以及学习顺序表各部分的原理，一起加油吧！！！
目录
1、顺序表的概念及结构
在了解顺序表的概念前我们首先要了解什么是线性表
线性表（linearlist）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使
⽤的数据结构，常可见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表的概念：顺序表的底层结构是数组，对数组的封装，，提供了很多现成的方法，实现了常用的增删改查等接口
（顺序表也是属于线性表，由于底层结构是数组所以在逻辑结构和物理结构上都是连续的）
2.静态顺序表与动态顺序表
静态顺序表概念是在定长数组的基础上实现顺序表，要实现静态顺序表实现要定义一个结构体，在这里面有两个结构体变量一个是数组，另一个是当前顺序表有效的数据个数
（注：以下将结构体名称写作Seqlist是因为顺序的英文单词是sequence，列表的单词是list，我们 就将顺序表简写为Seqlist）
struct Seqlist
{
int arr[100];
int size;//当前顺序表有效的数据个数
};而如果写成动态顺序表就会是以下形式
struct Seqlist
{
int* arr;
int size;//当前顺序表有效的数据个数
int capacity;//空间大小
};那么以上两种实现顺序表的方式哪种更好呢？
答案是动态顺序表更好，原因是静态顺序表存在以下的缺点：
静态顺序表的数组大小是一开始就确定下来的，且确定后就不可以更改，如果一开始的的数组大小给小了之后要再存储数据时就会存在空间不足的问题，如果一开始的的数组大小给大了，就会存在空间利用率低的问题，造成了内存空间的浪费
而动态顺序表就不存在以上的问题，要多少的内存空间就可以动态内存申请多大的空间，不够的时候再进行动态内存申请，所以在本篇实现顺序表使用的是动态顺序表
3、动态顺序表的实现
3.1 程序文件设置
在实现动态顺序表的程序当中我们是将程序分为三个文件，其中在Seq.c文件当中存放的是实现顺序表的方法，而在Seq.h文件内存放的是顺序表的结构以及声明，最后的test.c文件实现的就是顺序表各功能的测试
同时在test.c和Seq.c中都引用头文件#include"Seq.h",在Seq.h中引用相应库函数的头文件
3.2 顺序表的结构
在以上的动态顺序表的说明已经将动态顺序表的结构进行了描述
struct Seqlist
{
int* arr;
int size;//当前顺序表有效的数据个数
int capacity;//空间大小
};由于原本结构体 struct Seqlist的名过长在之后的引用不方便，使用我们就可以将其进行重命名，以下就是将其重命名为SL
同时以上的结构体中的指针指向的是存放的是整型的数据，但如果我们要改变数据的类型是如果是按照以上的方法就要将程序当中用到修改同类型的数据就要一个个去修改，这样就很麻烦，所以我们就可以将数组内元素的类型进行重命名，以下就将int重命名为SLDataType
以下就是再将以上的结构体进行优化后的代码
typedef int SLDataType;
typedef struct Seqlist
{
SLDataType* arr;
int size;//有效的数据个数
int capacity;//空间大小
}SL;//将struct Seqlist重命名为SL3.3 顺序表的初始化和销毁
由于以上我们的顺序表是基于数组，在利用动态内存管理的基础上实现的，所以在实现顺序表各功能前要对顺序表进行初始化，在使用完申请的内存空间后要对申请的内存空间进行销毁，将空间还给操作系统
在初始化过程将初始化函数命名为SLInit
在Seq.c先对初始化顺序表的函数进行以下声明
void SLInit(SL* ps);//初始化顺序表注：在以上的SL* ps接收的是结构体SL类型的指针，注意在此不能直接将结构体作为参数，原因是形成是实参的一份临时拷贝，使用的是传值调用函数不能直接改变相应内存数据的值
void SLInit(SL* ps)//顺序表初始化
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}在使用完顺序表后还要进行顺序表的销毁，在销毁过程将销毁函数命名为SLDestory
在Seq.c先对初始化顺序表的函数进行以下声明
void SLDestory(SL* ps);//销毁顺序表SLDestory函数完整代码如下：
由于以上动态顺序表的内存块是使用动态内存申请的，所以在销毁时要使用free释放，并且在释放后要将指针置为空
void SLDestory(SL* ps)//顺序表销毁
{
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}接下来就可以来实现顺序表的各功能
3.4 顺序表的打印
首先我们先在Seq.h内完成尾插函数的声明，由于打印数组不需要改变数组内的数据所以在此函数的参数是结构体变量
void SLPrint(SL ps);//打印顺序表函数实现：
void SLPrint(SL ps)//打印顺序表
{
int i = 0;
for (i; i < ps.size; i++)
{
printf("%d ", ps.arr[i]);
}
printf("\n");
}3.5 顺序表各功能的实现
3.5.1 尾部插入
首先我们先在Seq.h内完成尾插函数的声明，由于尾插是要改变数组内的数据所以在此函数的第一个参数还是结构体指针，第二个参数就为要插入的数据的值；其变量类型就是SLDataType
void SLPushBack(SL* ps, SLDataType x);//尾插首先先用图示的方法来理解尾插是如何实现的
如果用来数组大小为6，现在数组内有效元素个数size为4，现在我们要尾插一个5到数组的末尾 ，原本数组的下标只到3，现在就要在下标为size的位置插入数据5，这时就会使得数组内的有效个数size加一
接下来我们就来分析函数体内部是如何实现尾插的功能的
尾插函数实现：
在尾插过程中就是将要插入的数据放在原来数组下标为size的位置，之后size再加一
以上分析写成代码就变为以下形式
void SLPushBack(SL* ps, SLDataType x)//尾插
{
ps->arr[ps->size] = x;
ps->size++;
}但如果数组内的空间不足就无法实现尾插，所以在以上代码还要加上判断数组内的空间是否足够，如果不足要调整空间大小
当数组内空间完全填满数据时，size会等于capacity，在此之后在用一个三目操作符来判断数组一开始是否有空间，如果没有就给4个单位大小的空间，否则就将原空间大小乘二倍
之后用realloc来调整内存空间大小并将返回值强制类型转换为SLDateType，并判断内存空间是否申请成功，失败就直接用perror报错且退出函数；成功就将申请好的内存块的指针赋值给原数组的指针将数组的大小赋值为newcapacity注：在此的指针不能为空，否则就是对空指针进行解引用了，所以要在函数内加上assert断言
void SLPushBack(SL* ps, SLDataType x)//尾插 { assert(ps); if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断数组是否有占空间 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { perror("realloc"); exit(1); } ps->arr = tmp; ps->capacity = newcapacity; } ps->arr[ps->size] = x; ps->size++; }
在编写完尾插的代码我们就要在test.c内测试功能是否能正常实现
#include"Seq.h"
void test1()
{
SL s;
SLInit(&s);//初始化顺序表
//测试尾插
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLDestory(&s);//销毁顺序表
}
int main()
{
test1();
return 0;
}通过调试代码和运行代码检查可以得出以上尾插代码没问题
3.5.2 头部插入
首先我们先在Seq.h内完成头插函数的声明，由于头插是要改变数组内的数据所以在此函数的第一个参数还是结构体指针，第二个参数就为要插入的数据的值；其变量类型就是SLDataType
void SLPushPront(SL* ps, SLDataType x);//头插首先先用图示的方法来理解头插是如何实现的
例如以上数组要把1插到数组的头部就要先把每一个数组内的元素都往后移动一位，最后把要插入的1放在数组下标为0处，并且完成以上操作后size加一
接下来我们就可以来实现头插代码了
这时会有个问题在头插函数内也要判断数组的大小是否足够如果想以上尾插代码一样再把判断部分写一遍就会让程序代码很臃肿，所以我们就可以把判断数组空间的那部分独立设计为一个函数，之后只要再需要判断调整数组的大小就调用函数SLCheckCapacity就可以了void SLCheckCapacity(SL* ps)//检查空间是否足够，不足时增大空间大小 { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断数组是否有占空间 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { perror("realloc"); exit(1); } ps->arr = tmp; ps->capacity = newcapacity; } }头插函数的实现：
在以下代码中for循环中的最终结束时是pa->arr[1]=pa->arr[0]，所以for循环判断部分为i>0void SLPushPront(SL* ps, SLDataType x)//头插 { assert(ps); SLCheckCapacity(ps); for (int i = ps->size; i>0; i--) { ps->arr[i] = ps->arr[i-1]; } ps->arr[0] = x; ps->size++; }
在编写完头插的代码我们就要在test.c内测试功能是否能正常实现
#include"Seq.h"
void test2()
{
SL s;
SLInit(&s);//初始化顺序表
//测试头插
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
int main()
{
test2();
return 0;
}通过调试代码和运行代码检查可以得出以上头插代码没问题
3.5.3 尾部删除
首先我们先在Seq.h内完成尾删函数的声明，由于尾删是要改变数组内的数据所以在此函数的参数还是结构体指针
void SLPopBack(SL* ps);//尾删首先先用图示的方法来理解尾删是如何实现的
例如以上数组要把数组的尾部元素删除就需要size减一，在此之后size及以后的数组下标不会被使用，因此之后的数据内容不会产生影响
尾删函数的实现：
在尾删函数中参数也不能为空指针，因此需要使用assert断言并且在删除时候数组内的有效元素个数不能为0，使用也需要对size进行断言void SLPopBack(SL* ps)//尾删 { assert(ps); assert(ps->size); assert(ps->size); ps->size--; }
在编写完尾删的代码我们就要在test.c内测试功能是否能正常实现
#include"Seq.h"
void test3()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试尾删
SLPopBack(&s);
SLPopBack(&s);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
int main()
{
test3();
return 0;
}通过调试代码和运行代码检查可以得出以上尾删代码没问题
3.5.4 头部删除
首先我们先在Seq.h内完成尾删函数的声明，由于尾删是要改变数组内的数据所以在此函数的参数还是结构体指针
void SLPopPront(SL* ps);//头删首先先用图示的方法来理解头插是如何实现的
例如在以上数组中对其进行头删，就需要将数组内的每个元素向前移动一位，并且移动完后要将size减一
头删函数的实现：
在头删函数中参数也不能为空指针，因此需要使用assert断言并且在删除时候数组内的有效元素个数不能为0，使用也需要对size进行断言在以下代码中for循环中的最终结束时是pa->arr[ps->size-2]=pa->arr[ps->size-1]，所以for循环判断部分为i<ps->size-1
void SLPopPront(SL* ps)//头删 { assert(ps); assert(ps->size); for (int i =0; i<ps->size-1; i++) { ps->arr[i] = ps->arr[i+1]; } ps->size--; }
在编写完头删的代码我们就要在test.c内测试功能是否能正常实现
#include"Seq.h"
void test4()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试头删
SLPopPront(&s);
SLPopPront(&s);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
int main()
{
test4();
return 0;
}通过调试代码和运行代码检查可以得出以上头删代码没问题
3.5.5 任意位置前的删除
首先我们先在Seq.h内完成任意位置前删除的函数的声明，由于任意位置前的删除是要改变数组内的数据所以在此函数的第一个参数还是结构体指针，第二个参数就为要删除的数据的数组下标；其变量类型就是int
void SLErase(SL* ps, int pos);//任意位置删除首先先用图示的方法来理解任意位置前的删除是如何实现的
例如以上数组要在数组下标为2前的元素也就是要删除数组中的2，这就需要把数组下标为2及以后的元素向前移动一位，并且在完成以上操作时再把size减一
任意位置删除函数实现：
在任意位置前删除时，由于要删除的的数组下标不能为下标为size的元素，所以要删除的的数组下标范围为0到size-1 ，所以在此函数内要使用到assert来限定pos的范围
在此我们使用for循环来实现数组元素的移动，for循环中的最终结束时是pa->arr[ps->size-2]=pa->arr[ps->size-1]，所以for循环判断部分为i<=ps->size-2void SLErase(SL* ps, int pos)//任意位置删除 { assert(ps); assert(pos >= 0 && pos < ps->size); for (int i = pos; i<=ps->size-2; i++) { ps->arr[i] = ps->arr[i+1]; } --ps->size; }
在编写完任意位置的删除的代码我们就要在test.c内测试功能是否能正常实现
#include"Seq.h"
void test5()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试任意位置删除
SLErase(&s, 0);
SLPrint(s);
SLErase(&s, s.size-1);
SLPrint(s);
SLErase(&s, 1);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
int main()
{
test5();
return 0;
}通过调试代码和运行代码检查可以得出以上任意位置删除的代码没问题
3.5.6 任意位置前的插入
首先我们先在Seq.h内完成任意位置前插入的函数的声明，由于任意位置前的删除是要改变数组内的数据所以在此函数的第一个参数还是结构体指针，第二个参数就为要插入的数据的数组下标；其变量类型就是int，第三个参数是要插入的元素；其类型是SLDateType
void SLInsert(SL* ps, int pos, SLDataType x);//任意位置插入首先先用图示的方法来理解任意位置前的插入是如何实现的
例如要把以上数组下标为2的元素前插入元素6，这就要先把数组中下标为2以及之后的元素都向后移动一位，之后再把元素6插入到数组下标为2的位置，最后在以上操作结束后再把size加一
任意位置插入函数实现：
在任意位置插入中因为在数组下标为size前处插入就是相当与尾插，所以要插入的位置下标范围为0到size，所以在此函数内要使用到assert来限定pos的范围
在此我们使用for循环来实现数组元素的移动，for循环中的最终结束时是pa->arr[pos+1]=pa->arr[pos]，所以for循环判断部分为i>posvoid SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入 { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); for (int i = ps->size; i>pos; i--) { ps->arr[i] = ps->arr[i-1];//结束条件ps->arr[pos+1] = ps->arr[pos] } ps->arr[pos] = x; ps->size++; }
在编写完任意位置的插入的代码我们就要在test.c内测试功能是否能正常实现
#include"Seq.h"
void test6()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试任意位置插入
SLInsert(&s,0,99 );
SLPrint(s);
SLInsert(&s, s.size, 99);
SLPrint(s);
SLInsert(&s, 3, 99);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
int main()
{
test6();
return 0;
}通过调试代码和运行代码检查可以得出以上任意位置插入的代码没问题
3.5.7 顺序表数据查找
在实现查找顺序表内是否存在想要查找的元素就只需要编译数组内存在的元素并且与要查找的元素，如果存在就返回该数组元素的数组的下标，否则就返回-1
首先我们先在Seq.h内完成任意位置前插入的函数的声明
int SLFind(SL* ps, SLDataType x);//查找函数实现：
int SLFind(SL* ps, SLDataType x)//查找
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}在编写完查找的代码我们就要在test.c内测试功能是否能正常实现
#include"Seq.h"
void test7()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试查找
int find=SLFind(&s, 2);
if (find < 0)
{
printf("找不到");
}
else
{
printf("找到了，下标是%d", find);
}
SLDestory(&s);//销毁顺序表
}
int main()
{
test7();
return 0;
}通过运行代码检查可以得出以上任意位置插入的代码没问题
4.顺序表完整代码
Seq.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
typedef struct Seqlist
{
SLDataType* arr;
int size;//有效的数据个数
int capacity;//空间大小
}SL;//将struct Seqlist重命名为SL
void SLInit(SL* ps);//初始化
void SLDestory(SL* ps);//销毁
void SLCheckCapacity(SL* ps);//检查空间是否足够
void SLPrint(SL ps);//打印顺序表
void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushPront(SL* ps, SLDataType x);//头插
void SLPopBack(SL* ps);//尾删
void SLPopPront(SL* ps);//头删
void SLInsert(SL* ps, int pos, SLDataType x);//任意位置插入
void SLErase(SL* ps, int pos);//任意位置删除
int SLFind(SL* ps, SLDataType x);//查找Seq.c
#include"Seq.h"
void SLInit(SL* ps)//顺序表初始化
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLDestory(SL* ps)//顺序表销毁
{
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)//检查空间是否足够，不足时增大空间大小
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断数组是否有占空间
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
void SLPrint(SL ps)//打印顺序表
{
int i = 0;
for (i; i < ps.size; i++)
{
printf("%d ", ps.arr[i]);
}
printf("\n");
}
void SLPushBack(SL* ps, SLDataType x)//尾插
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
void SLPushPront(SL* ps, SLDataType x)//头插
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i-1]; //pa->arr[1]=pa->arr[0]
}
ps->arr[0] = x;
ps->size++;
}
void SLPopBack(SL* ps)//尾删
{
assert(ps);
assert(ps->size);
ps->size--;
}
void SLPopPront(SL* ps)//头删
{
assert(ps);
assert(ps->size);
for (int i =0; i<ps->size-1; i++)
{
ps->arr[i] = ps->arr[i+1];
}
ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i>pos; i--)
{
ps->arr[i] = ps->arr[i-1];//结束条件ps->arr[pos+1] = ps->arr[pos]
}
ps->arr[pos] = x;
ps->size++;
}
void SLErase(SL* ps, int pos)//任意位置删除
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i<=ps->size-2; i++)
{
ps->arr[i] = ps->arr[i+1];//结束条件ps->arr[ps->size-2] = ps->arr[ps->size-1]
}
--ps->size;
}
int SLFind(SL* ps, SLDataType x)//查找
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}test.c
#include"Seq.h"
void test1()
{
SL s;
SLInit(&s);//初始化顺序表
//测试尾插
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLDestory(&s);//销毁顺序表
}
void test2()
{
SL s;
SLInit(&s);//初始化顺序表
//测试头插
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
void test3()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试尾删
SLPopBack(&s);
SLPopBack(&s);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
void test4()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试头删
SLPopPront(&s);
SLPopPront(&s);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
void test5()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试任意位置删除
SLErase(&s, 0);
SLPrint(s);
SLErase(&s, s.size-1);
SLPrint(s);
SLErase(&s, 1);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}
void test6()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试任意位置插入
SLInsert(&s,0,99 );
SLPrint(s);
SLInsert(&s, s.size, 99);
SLPrint(s);
SLInsert(&s, 3, 99);
SLPrint(s);
SLDestory(&s);//销毁顺序表
}void test7()
{
SL s;
SLInit(&s);//初始化顺序表
SLPushPront(&s, 1);
SLPushPront(&s, 2);
SLPushPront(&s, 3);
SLPushPront(&s, 99);
SLPrint(s);
//测试查找
int find=SLFind(&s, 2);
if (find < 0)
{
printf("找不到");
}
else
{
printf("找到了，下标是%d", find);
}
SLDestory(&s);//销毁顺序表
}
int main()
{
test1();
return 0;
}以上就是顺序表的全部内容了，接下来会继续对顺序表的应用——通讯录进行讲解，未完待续，感谢你的支持！！！