欢迎来到博主的新专栏——C语言数据结构
博主ID：代码小豪
再开始这篇文章之前，我们假设要对10个数据进行操作。这十个数据全都被声明成10个变量
int n1, n2, n3, n4, n5, n6, n7, n8, n9, n10;
如果我们准备为这些数据增加功能，将他们进行赋值，打印，交换等。就会发现一个特别棘手的问题，这些程序写起来太繁杂了，我们需要将这些数据一个个赋值，写十个printf函数才能将他们打印。更麻烦的是，连操作他们的函数都要十个形式参数。这不是太麻烦了嘛？
学习数据结构就是解决这个问题的好工具，当我们实现某一种功能时，如果选择了合适的数据结构和算法时，那么将这个功能的实现就会简单很多，效率也会变高。
顺序表
线性表是什么
在了解顺序表之前，我们得先明白线性表是什么，线性表的定义是这样的：
一个线性表是N个具有相同特性的数据元素组成的有限序列
我们将注意力放在关键词上
（1）有限:线性表中的元素是有限个的
（2）相同特性:在C语言中，可以理解为这些数据类型是一致的
（3）序列：这些数据元素被排列了，而且还是有顺序的排列了。
这么说都还有些抽象，以现实举例。小明夫妇打算在春节假期带一家四口去旅游，分别是小明两口子，和小明的儿子、女儿。但是有一个问题困扰住了夫妇两，因为孩子小啊。景区又大，人又多，小孩子要是一不小心走丢了就不好找了。
最后小明想到了一个办法。在景区里游玩的时候，他们一家四口手牵着手，小明牵着女儿，女儿又牵着小明的儿子，而儿子牵着妈妈。如果其中有一个人走丢，那么牵着手的人就能很快的感觉到。
小明夫妇的这个方法就是构成了线性表中的一个最重要的特征，那就是线性逻辑结构。在小明夫妇的方法当中，家里四个人（四个数据）以某种方式联系了起来，而且这个联系是具有顺序的。
从这里可以发现“线性”的关系，可以发现，小明一家之间都是一对一的关系（爸爸——女儿——儿子——妻子）。这个逻辑结构中并没有出现分支。
在线性表中，数据元素之间的关系都是一对一的，即除了首元素和末尾元素外，所有的元素都有一个前置的元素（前驱元素）和一个后置的元素（后继元素）。这些元素以某种方式联系在一起。
根据不同的线性联系方式，线性表是有多种类型的，而顺序表就是线性表中的其中一种。
顺序表的线性逻辑结构
在内存当中，十个声明的数据的存储形式是这样的，这十个变量的存储方式是随机存储。
现在，我们要想个方法使得这十个数据具有线性的逻辑结构，使得这些数据构成线性表
令n1为表头，n10为表尾，其余数据按照下标的顺序排列，即（n1,n2……ni……n10）。但是这样仍不是线性表，因为这些数据之间并没有“联系”，什么是数据之间的联系呢？就好比小明一家人之间牵着的“手”一样，没有这只手，他们之间就不能算是线性的结构。
参考小明夫妇的方法，让这些数据不在零零散散了，让他们按照顺序，存储在内存当中。
这样，这些数据不就联系起来了吗？我们只需要知道表中任意元素的地址，比如取n4的地址，那么n4前面是n3，n4后面是n5，而n5后面是n6，以此类推。
通过指针的加减运算就能访问到10个元素，再也不需要像开头那种存储方式一样，需要将十个元素分别进行操作。
这种具有顺序存储结构的线性表，被称为顺序表
静态顺序表
我们仔细回想以下顺序表的定义：将元素顺序存储在内存当中。
这不是数组吗！
所以C语言（或其他语言）可以通过数组来实现顺序表的
#define N 100
typedef int SLdatetype;
typedef struct SeqList
{
SLdatetype a[N];//顺序表的最大表长
int lenth;//顺序表的当前表长
};
用数组实现的顺序表有以下特点
（1）lenth是顺序表的当前长度
（2）由于顺序表有可能进行增加数据的操作，所以数组的元素个数>=顺序表中的元素个数
由于数组的元素个数在创建之后是固定的，所以将这种顺序表称为静态顺序表，由于静态顺序表在程序运行的过程中不能进行调整，所以顺序表的预留空间要足够大。
总体而言，静态顺序表虽然操作简单，但是不够灵活，而且造成的内存空间的浪费也较大。动态顺序表具有更多的优势。
动态顺序表
动态顺序表是使用动态内存来管理顺序表的空间。使用了动态内存之后，可以对顺序表中的空间进行扩容、修改等操作。
动态顺序表的定义如下：
typedef struct SeqList
{
SLdatetype* seqlist;
int capacity;
int size;
}SeqList;
seqlist是一个指针，主要作用是通过这个指针对顺序表进行操作。
capacity是顺序表的最大容量，如果数据进行操作时发现容量不够，可以对顺序表进行扩容
size是顺序表的当前数据的长度
动态顺序表通过动态内存分配的形式，对顺序表的空间管理更加的灵活，而且造成的空间浪费也会更容易管控。这是动态顺序表相对于静态顺序表的优势
顺序表的操作
和变量的声明与初始化类似，一个顺序表在创建时也是需要对顺序表进行声明与初始化的。这里将顺序表的初始化封装成一个函数
SeqList s1;
InitList(&s1);
这个新建的顺序表还没有任何数据，也没有为其分配动态内存的空间，因此将顺序表初始化成一个空表
void InitList(SeqList* psl)
{
psl->seqlist = NULL;
psl->capacity = 0;
psl->size = 0;
}
由于操作系统尚未为顺序表分配空间，因此将指针置为NULL，容量为0，大小也为0。
对顺序表初始化完成后，就可以对顺序表进行操作了。顺序表的操作无非是“增删查改”这几种。下面将对顺序表的操作进行讲解
为顺序表增加数据
尾插法
我们假设大街上有一群人在排队，现在，小明来到了排队的地方，那么他有几种方法排队呢？
第一种，就是排在队伍的后头，这样子大家也就和和气气的，什么事都没有发生。
在顺序表中，将数据添加在表尾的方法被称为尾插法，这种方法是时间复杂度最低的插入算法。假设现在顺序表的最大容量（capacity）为4，当前表长（size）为2。
当前的顺序表并没有达到最大容量的限制，因此只需要将数据排列到顺序表的末尾即可，我们可以计算一下新数据的位置。
新数据n3是顺序表的第三位，但是C语言中数组的下标是从[0]开始计算的，所以n3的位置是在下标为[2]的位置。可以发现，新数据的下标计数，与顺序表的当前表长（size）是一致的，因此可以让当前表长（size）作为尾插法使用时的数据下标。
ps1->seqlist[ps1->size] = n;
别忘了添加新数据后，当前表长要加1.
size++;
顺序表的扩容
如果新数据添加后超出了最大容量的限制（capacity==size）。那么此时数据是无法插入顺序表的
解决方法是使用realloc函数为顺序表进行扩容（关于动态内存分配函数的性质可以查看博主的上一个专栏，这里不在赘述），再进行数据插入。
扩容的方式有以下几种，这里简单说说优缺点
（1）单个元素扩容：每次扩容只增加一个元素的空间，这样子会导致realloc函数调用过多导致的运行时间增加，但是内存使用率会相当高
（2）固定多个元素扩容：使用空间换取时间效率的方法
（3）倍数扩容：每次扩容时，都将空间扩容1.5倍或者2倍。能让realloc函数的调用次数变得非常少，现在的计算机一般空间都比较大，建议使用第三种
bool SLCheckCapacity(SeqList* psl)
{
if (psl->size == psl->capacity)
{
int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
SLdatetype* ptmp = realloc(psl->seqlist, sizeof(SLdatetype) * newcapacity);
if (!ptmp)
{
perror("realloc capacity fail");
return false;
}
psl->seqlist = ptmp;
psl->capacity = newcapacity;
return true;
}
}
将这些扩容的程序封装成一个函数SLCheckCapacity
那么尾插法的算法用C语言编写出来是这样的
void datapushback(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
psl->seqlist[psl->size] = n;
psl->size++;
}
头插法
小明看到排队的人这么多，不行啊，我不等了。一下子插入进队伍的开头（错误示例，小朋友不要模仿）。此时队伍里的人为了给前面的人留出位置，每个人都要往后退一位，于是骂声四起。
将数据插入至表头的方法称为头插法，首先我们还是先判断顺序表是否要扩容，之后将数据插入至开头。
但是要注意，数据插入开头的方式并不是直接让开头的数据变为插入的数据。这样子会导致数据丢失。正确的方式是从表尾开始，数据依次往后挪动一位，直到表头的数据位置变成了空余的数据位置再插入新数据。
用c语言实现头插法的代码如下
void datepushfront(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
for (int i = psl->size; i > 0; i--)
{
psl->seqlist[i] = psl->seqlist[i - 1];
}
psl->seqlist[0] = n;
psl->size++;
}
任意位置的插入
小明的朋友在队伍里排队，看到在队外的小明便招呼小明过来一起排，那么这时候排队的人群就要分成两部分了，小明的朋友的后置的人就要依次往后退一步腾出空间，而前置的人则保持不动的位置
那么理解顺序表中任意位置的数据插入也是这个原理，首先要确定数据插入的位置，然后让这个位置后的数据往后一个空间，前置的数据则保持原位。
首先还是要先判断顺序表的空间是否足够，然后使用循环将后置数据往后一个空间，最后将数据插入指定位置。
现在来想想函数原型的参数应该是什么，首先是我们想要插入的顺序表，然后是数据插入的位置，最后是插入的数据的值。
那么函数原型如下：
void datainsert(SeqList* psl, int pos, SLdatetype n)
具体的代码实现如下
void datainsert(SeqList* psl, int pos, SLdatetype n)
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>psl->size)
//pos可以是表头，也可以是表尾，超出则不行
{
perror("pos illegal");
exit(EXIT_FAILURE);
}
SLCheckCapacity(psl);
for (int i = psl->size - 1; i >= pos; i--)
//注意这里的pos指的是元素插入的顺序表的下标，具体实现可以根据要求进行修改
{
psl->seqlist[i+1] = psl->seqlist[i];
}
psl->seqlist[pos] = n;
}
这里再讲讲pos这个参数，由于我的设想中pos的位置是参考下标的，所以for循环的取值如下，如果你需要的是其他实现（比如想要按照物理位置来选取pos，那么需要修改这些数据）。
如果你掌握了这个方法，那么我要恭喜你，你的头插法和尾插法白学了，因为这个方法可以在任意位置插入数据，包括表头和表尾（^_^Hiahiahia）
我们来计算一下顺序表的插入的时间复杂度 是多少，根据插入的位置可以分为以下三种情况
（1）插入表尾（O（1））。
（2）插入表头（O（N））。
（3）插入其他位置（F（pos）=n-pos）
平均的输入与指令执行次数的关系函数为N/2.
根据大O阶的推导公式，时间复杂度为O（N）
删除顺序表中的数据
现在小明插队的行为引来了众怒，他被排队的人群赶出了队列，于是后面被插队的人都往前了一步，队伍的总长度少了一个人。
如何删除一个数据呢，我们选择一个位置，将这个位置的数据清空（实际操作时只需要将该位置的数据用后继元素覆盖即可，不需要将这个位置的数据清空），并将后面的数据往前移动，最后将顺序表的表长减1.
思考一下函数原型是什么
首先要将顺序表传入函数，然后将指定的位置作为参数传入函数。函数原型如下：
void DataDelete(SeqList* psl, int pos);
代码实现如下：
void DataDelete(SeqList* psl, int pos)//删除顺序表中指定位置的数据
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>=psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
for (int i = pos; i <psl->size - 1; i++)
{
psl->seqlist[i] = psl->seqlist[i + 1];
}
psl->size--;
}
顺序表中数据的查找与修改
如果你掌握了前面有关顺序表的特性，那么查找和修改顺序表是一个易如反掌的事。
为什么这么说呢？因为仔细观看前面画的有关顺序表的图，有没有觉得那些顺序存储的元素特别眼熟？没错，他们和数组的原理是非常相似的，如果你会访问和修改数组，你就会访问和修改顺序表。
话不多说，直接上函数原型和代码
首先思考访问顺序表的函数需要什么参数，假如你要上门拜访一个人，那么是不是需要知道这个人所在的地点？
查找数据也是同理，需要输入查找的位置。
void FindListData(const SeqList* psl, int pos);
函数实现如下
void FindListData(SeqList* psl, int pos)
{
assert(psl);
assert(psl->size);
if (pos < 0 || pos >= psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
printf("%d\n", psl->seqlist[pos]);
}
修改也是同理，我这里使用标准的输入输出函数对数据进行修改，修改方法不唯一。
void ModifyListData(SeqList* psl, int pos)
{
assert(psl);
assert(psl->size);
if (pos < 0 || pos >= psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
printf("请输入修改后的数字");
scanf("%d", &(psl->seqlist[pos]));
}
如果大家在阅读完这篇文章后发现问题欢迎指正，如果家人们有疑问，欢迎私信博主求解。博主将在观看私信后回答问题。
最后附上顺序表的所有源码！
C语言实现顺序表的所有源码
博主将实现顺序表的代码分为一个头文件和一个源文件，其中，头文件用于声明，源文件用于定义函数。不要忘记在源文件中包含此头文件
头文件“seqlist.h”文章来源：https://www.toymoban.com/news/detail-804111.html
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define N 100
typedef int SLdatetype;
typedef struct SeqList
{
SLdatetype* seqlist;
int capacity;
int size;
}SeqList;
//顺序表的初始化与销毁
void InitList(SeqList* psl);
void ListDestory(SeqList* psl);
//头插法和尾插法
void datapushback(SeqList* psl, SLdatetype n);
void datapushfront(SeqList* psl, SLdatetype n);
//一些辅助函数
bool SLCheckCapacity(SeqList* psl);
void printlist(const SeqList* psl);
void dataPopback(SeqList* psl);//表尾删除操作
void dataPopfornt(SeqList* psl);//表头删除操作
void datainsert(SeqList* psl, int pos, SLdatetype n);//任意位置插入
void DataDelete(SeqList* psl, int pos);//任意位置删除
源文件“seqlist.c”：文章来源地址https://www.toymoban.com/news/detail-804111.html
#include"seqlist.h"
bool SLCheckCapacity(SeqList* psl)
{
if (psl->size == psl->capacity)
{
int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;
SLdatetype* ptmp = realloc(psl->seqlist, sizeof(SeqList) * newcapacity);
if (!ptmp)
{
perror("realloc capacity fail");
return false;
}
psl->seqlist = ptmp;
psl->capacity = newcapacity;
return true;
}
return true;
}
void InitList(SeqList* psl)
{
psl->seqlist = NULL;
psl->capacity = 0;
psl->size = 0;
}
void datapushback(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
psl->seqlist[psl->size] = n;
psl->size++;
}
void datapushfront(SeqList* psl, SLdatetype n)
{
SLCheckCapacity(psl);
for (int i = psl->size; i > 0; i--)
{
psl->seqlist[i] = psl->seqlist[i - 1];
}
psl->seqlist[0] = n;
psl->size++;
}
void printlist(const SeqList* psl)
{
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->seqlist[i]);
}
printf("\n");
}
void dataPopback(SeqList* psl)//尾删法
{
assert(psl);
assert(psl->size);
psl->size--;
}
void dataPopfornt(SeqList* psl)//头删法
{
assert(psl);
assert(psl->size);
for (int i = 0; i < psl->size; i++)
{
psl->seqlist[i-1] = psl->seqlist[i];
}
psl->size--;
}
void datainsert(SeqList* psl, int pos, SLdatetype n)
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>psl->size)
//pos可以是表头，也可以是表尾，超出则不行
{
perror("pos illegal");
exit(EXIT_FAILURE);
}
SLCheckCapacity(psl);
for (int i = psl->size - 1; i >= pos; i--)
//注意这里的pos指的是元素插入的顺序表的下标，具体实现可以根据要求进行修改
{
psl->seqlist[i+1] = psl->seqlist[i];
}
psl->seqlist[pos] = n;
psl->size++;
}
void DataDelete(SeqList* psl, int pos)//删除顺序表中指定位置的数据
{
assert(psl);
assert(psl->size);
if (pos<0 || pos>=psl->size)
{
perror("illegal pos");
exit(EXIT_FAILURE);
}
for (int i = pos; i <psl->size - 1; i++)
{
psl->seqlist[i] = psl->seqlist[i + 1];
}
psl->size--;
}
void ListDestory(SeqList* psl)
{
free(psl->seqlist);
psl->capacity = 0;
psl->size = 0;
}
到了这里，关于C语言数据结构（2）——线性表其一（顺序表）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
